Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 114
Текст из файла (страница 114)
Тот факт. что рассматриваемая последа, тельность является чисто периодической последовательность' минимальный период которой равен д» вЂ” 1, есть следствие рем 8.28 и 3.16. Остальное легко вытекает из теоремы 8.7. 8.34. Пример. Характеристическим многочленом рассмот ного в примере 8.2 линейного рекуррентного соотношения полем Г» эо»» зь+» '! ал+»+ зь+» зо и () э 3. Прои»»едящие функции 5!5 ~вдается многочлен г'(х) = х' — х« — х» — х' — 1 Е Г» (х).
Так ак 1 (х) — примитивный многочлен над полем 11», то каждая куррентная последовательность с ненулевым начальным векром, задаваемая указанным линейным рекуррентным соотношением, является последовательностью максимального периода над полем Г». Если в качестве вектора начального состояния выбрать произвольный ненулевой вектор, то мы получим последовательность ве, в,, ..., имеющую в соответствии с теоремой 8.33 минимальный период 2' — 1 =- !27.
Таким образом, все возможные ненулевые векторы из г'4» встречаются в качестве векторов состояний этой последовательности. Любая другая последовательность максимального периода, получаемая из этого же линейного рекуррентного соотношения, представляет собой некоторый сдвиг последовательности в„з,, .... П $3. Производящие функции До сих пор при изучении линейных рекуррентных последовательностей мы пользовались понятиямн линейной алгебры, алгебры многочленов и теории конечных полей. Использование алгебраического аппарата формальных степенных рядов позволит нам получить другие замечательные результаты, связанные с линейнымн рекуррентными последовательностями.
Пусть дана произвольная последовательность в„в4, ... элементов поля г«. С этой последовательностью можно связать ее иронзводящую функцию от переменной х, которая является просто формальным выражением вида 0(к) = во+в,х+в,х'+ ° ° ° +в„хл+... ~~ в хл (8 13) »=о где х — формальная переменная. В основе этого подхода лежит мысль, что в функции 6 (х) «собраны» в определенном порядке все члены последовательности в, и,, „так что функция 4» (х) может некоторым образом отражать свойства этой последовательности. Название «производящая функция», строго говоря, валяется неправильным, так как мы рассматриваем 44 (х) не как Функцию аргумента х, а просто как некоторый формальный объект (аналогично многочлены в сущности тоже можно рассматривать как формальные объекты, которые не следует путать с функциями).
Термин «производящая функция» был пере. иссек сюда со случая последовательностей действительных или комплексных чисел„где может оказаться, что ряд, аналогичный (8 13), сходится при подстановке некоторого действительного ".Ои комплексного числа х, вместо переменной х, что позволяет "риписать какое-то конкретное значение функции б (х,). В рассматриваемой же ситуации вопрос о сходимости или расходимости 6" Гл. 8. Линейные рекуррентные последовательности Ы6 ряда (8.!3) не возникает, так как мы рассматриваем О (х) к «иероглнф» последовательности ло, з,, .... В общем случае выражение вида В(х) = Ь„+Ь,х+Ь»ха+ .
+Ь„х"-,'- . =- ~' Ь„х", л=а где Ь,, Ь,, ... — последовательность элементов из Г, называ Р трормальным с«те«пенным рядом (над полем Г ). В таком к тексте члены Ь„, Ь„... нашей последовательйости называю также коэффичиентами формального степенного ряда. Прил тельное «формальный» вновь отражает ту мысль, что сходим ' или расходимость этих выражений (какой бы смысл мы в это вкладывалн) не имеет никакого отношения к их изучению. формальных степенных ряда над г« В (х) =- ~~ Ь„х" и С(х) = ~н с„х" л.=о в=о считаются равными, если Ь„= — с„для всех и =- О, 1, ....
Так, образом, множество всех формальных степенных рядов над . находится во взаимно однозначном соответствии с множест всех последовательностей, состоящих из элементов поля Может показаться,что мы ничего не выиграем от перехода к мальным степенным рядам. На самом деле «смысл существова этих объектов состоит в том, что мы можем наделить множес формальных степенных рядов над г«богатой н интересной гебраической структурой, причем совершенно естественным об ' зом. Это будет обсуждаться впоследствии. Заметим, во-первых, что многочлен р (х) = р„+ р,х + + рлх« ~ К«(х] тоже можно рассматривать как формальный степенной ряд К«, отождествляя его с рядом Р(х) =- р,+ р,х —, +р«х«ч О х«+'+О.х».ьв+ .
Введем теперь алгебраические операции сложения и умножеи формальных степенных рядов таким образом, чтобы они являл перенесением на множество формальных степенных рядов с ветствующих операций, определенных на многочленах. Подр нее, если В(х) = ~ Ь„х" и С(х) = ~, с„хл л=о л о $ 3. Производящие функции 517 два формальных степенных ряда над Ке, то определим их „илу как формальный степенной ряд В(х)+С(х) = ~~ (Ь„+оп)х", п=е а их произведение — как формальный степенной ряд В(х)С(х) = ~~ д„х", где д„= ~; Ьпс„„, а = О, 1, и=О Если В (х) и С (х) оба являются многочленами над Ке, то определенные выше операции совпадают со сложением и умножением обычных многочленов.
Здесь же надо отметить, что принцип подстановки, который так полезен в алгебре мнагочленов, не действителен для формальных степенных рядов по той простой причине, что выражение В (а), где а — элемент поля Ке, а В (х)— формальный степенной ряд над Ге, может быть бессмысленным. Это плата за то, что мы игнорируем вопросы сходимости рядов. 8.35. Пример.
Пусть В(х) = 2+х' и С(х) = 1+х+ха+ + х" + ° = ~~ 1 х" п=е — формальные степенные ряды над полем Гз. Тогда ОЭ В(х)+С(х) =х+2хз+хз+ ° +хи+ = ~ д„хп, где д„== О, д, = 1, и', = 2 и и'„= 1 для всех л ) 3, а В (х) С (х) =-- 2 + 2х + О х'+ О хз + ... == 2+ 2х. Е) Очевидно, что сложение формальных степенных рядов над Г является ассоциативной н коммутативной операцией. Формальсп ный степенной ряд О ==- ~ О.х" является нулем относительно п=о пп операции сложения. Если В (х) =- ~~ Ь„хп — произвольный форе=о мальный степенной ряд надКе, то обратным к нему относительно пп ~~~рации сложения является степенной ряд ~~ ( — Ь„) х", который п=о обозначается через — В (х).
Обычно мы будем писать В (х) — С (х) вместо В (х) -1- ( — С (х)). Очевидно, что н операция умножения формальных степенных р~д~~ над Г» является коммутативной операцией, а формальный 5!8 Гл. 8. Лииейиые реиурреитиые последовательности степенной ряд ! =- 1 + О х + О х'+ ... + О хл +... — един ' ный элемент относительно операции умножения. Умноже ' является ассоциативной операцией, так как если В (х) =- ~~ Ь„х", С(х) = ~ с„х", Р(х) = ~л д„х", л=о л=о и=о то оба формальных степенных ряда (В (х) С (х)) Р (х) и В (х) (С (х) Р (х)) равняются Ь;с(с(ь) х", и=о~а ( ЮСС!л! где Е (и) — множество всех упорядоченных троек (Е (, й), (). ()~ О, й )~ О, (+ (+ й — — и.
Кроме того, справедлив за дистрибутивности л ( л и~о~с~о-боои-Х (Н ь,л„<-л. ~)*" = л =О О=О ( л л =Е ~ЕЬ"..+Е Ь.д., "=- л=О О=О Ь=.О -Х (л ь„,„,)* ~ ь (ь кл„,)*. = В (х) С (х) + В (х) Р (х). Тем самым мы показали. что множество всех формальн' степенных рядов над Г с введенными там операциями сложе н умножения становится коммутативным кольцом с единиц Это кольцо называется кольцом формальных степенных р над полем Г и обозначается через Г ((хЦ. Кольцо многочле ' Г [х ( является подкольцом кольца г р ЦхЦ. Более силь .
утверждение содержится в следующей теореме. 8.36. Теорема. Кольцо ((р ([х([ формальных степенных р над полем (('р является областью целостности, которая содерМ кольцо'многочленов (Г [х( в качестве подкольца. Доказательство. Остается проверить, что Гр [[хЦ не сод жит делителей нуля, т. е. что произведение двух элементов коль' "г [[хЦ равняется нулю тогда и только тогда, когда один,' И9 й 3. Производящие функции сомножителей равен нулю. Предположим противное. Пусть В (х) С (х) =- О, и пРи этом В(х) --- ~ Ь„х" ФО, С(х) = ~ с„х" ~0 в=о ь: —.в лежат в 1я ЦхЦ. Пусть й — наименьшее натуральное число, тля которого Ьд ~д О, а т — наименьшее натуральное число, кля которого с нь О. Тогда коэффициент при х' в произ- ведении В (х) С (х) равняется Ьдс чь О, а это противоречит то- мд, что В (х) С (х) =-- О.
Для приложений нам понадобится выяснить, какие из элемен- тов кольца Кр ЦхЦ обратимы относительно операции умножения, с для какйх элементов В (х) Е Гя ЦхЦ найдутся соответ- ствуя>щие элементы С (х) С К ЦхЦ, такие, что В (х) С (х) = 1. Обратимые степенные ряды можно легко охарактеризовать. 8,37. Теорема. Формальный степенной ряд Ю В(х) = ~~ Ь„х" Ет'яЦхЦ «=о >меегп обратный относительно операции умножения элемент тогда и только тогда, когда Ьв чь О, Локазательство. Если С(х) =- ~„с„х" в=в --- такой элемент из [' ЦхЦ, что В (х) С (х) = !. то коэффициенты Ь,, Ь,, ...
и с„, с,., должны удовлетворять следующей бесконечной системе уравнений: Ь„с„ = 1, Ь,,—:Ьс =О, Ь,с, -, 'Ь,с, -т Ь,св == О, Ь с + Ь\с \ 1 Ь со 0 Вз первого уравнения мы получаем. что обязательно Ьо Ф О. При этом если это условие удовлетворяется. то со однозначно '>пределяется из первого уравнения. Переходя ко второму уравнению, видим, что теперь можно однозначно определить с,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
