Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 119

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 119)

з,, ..., то легко получить, что и„„= для всех и > О. Следовательно, и„= и„для всех п ~ О, и тот ' обязательно выполняется равенство и, = 1, так как иначе т, г был бы характеристическим многочленом последовательности Таким образом, з„,ь+! =ад гз„,ь г+ +а„з„для всех пьО. Поскольку т, (1) = 1 + аь г + ... -'- а„= 1, получаем з„,ь+! = а„,(з„,„, +!)+ . —,:-а„(з„+!) для всех п)~0,': а это означает.

что т, (х) является характеристическим мног членом последовательности о. Таким образом, в случае (г =, имеет место равенство т (х) =- т, (х), что и завершает доказ ' тельство теоремы. Напомним, что 5 (7'(х)) обозначает множество всех одиар ных линейных рекурректных последовательностей над полем !Г' с характеристическим многочленом 1' (х), где г (х) р Ео (х) 1 о. Семейства лиисйиых последовательностей 539 иормпроваииый миогочлеи положительной степени. Мы хотим, „о-первых, найти те целые положительные числа, которые могут „, пречаться в качестве минимальных периодов у последователь„г,сгей из множества 5 (1 (х)), а во-вторых, определить, для сколькпт последовательностей из 5 (! (х)) данное число может быть сипимальиым периодом.

Запишем миогочлеи 1 (х) в виде г (х) —.- хад(х), где Ь - 0— целое число, а (х) ~ Гч (х), а(0) ~ О. Случай, когда д (х) яв,*ьс,ся константой, тривиален, так как тогда каждая последова,сльиость из 5 (!' (х)) имеет минимальный период 1. Если Ь ) 1, л й (х) является миогочлеиом положительной степени, то, как ч~о было показано в замечаниях, следующих за теоремой 8.55, ьл кдая последовательность а Е 5 (( (х)) может быть единственным образом представлена в виде а == о, + а„где о, ~ 5 (х"), 5 (д (х)). Все члены последовательности а,, кроме, может бы;ь. конечного числа первых членов, равйяются О, Таким образом, минимальный период последовательности а равняется (шппмальиому периоду последовательиости аа Далее, из данной ;оследовательиости ав ~ 5 (д (х)) можно получить г)ь различных шкледовательиостей из 5 (1 (х)), прибавляя к а, любую из а" кпедовательиостей из 5 (х"), Следовательно, если г„..., г,— шпимальиые периоды последовательностей из 5 (й (х)), а Ж,, Л,, — число последовательностей из 5 (д (х)), имеющих минича тьиые периоды, равные соответственно г,,, го то для каж.юго Е 1 -'(е й существует ровно а"Жс последовательностей из множества 5 (((х)), имеющих минимальный период г;, и никак х других минимальных периодов у последовательностей из 5 1,,' (х)) быть ие может.

Пусть теперь Ь =- 0; тогда 1' (0) ~ О. Предположим, сначала, 1 (х) — иеприводимый миогочлеи иад полем Кч. В этом случае пз теоремы 8.44 и 8,50 мы получаем, что каждая последозз:.сльиость из 5 (1 (х)) с ненулевым вектором начального состоя, ио имеет минимальный период, равный огд (((х)). Значит, одна ледовательиость из 5 (~ (х)) имеет минимальный период 1, а остальные ивсе и ио1 — 1 последовательностей имеют мини; льный период огд () (х)). Далее, рассмотрим случай, когда 1 (х) является степенью ие'ц1иводпмого миогочлеиа.

Тогда представим ) (х) в виде 1 (х) =- 'И (х))', где а (х) р 'Кч (х) — нормированный иеприводимый ' югочлен иад полем 'Гч, а Ь ' 2 — целое число. Тогда миничгтьиый миогочлеи любой последовательиости из множества 5 г) (х)) с нулевым начальным вектором имеет вид (д (х))', где ' с с Ь. По теореме 8,53 5 (а (х)) ~ 5 ((д (х))') ~ ." ': — 5 О' (х)) !аипм образом, если деа (а (х)) =- lс, то имеется да — ! последо- 840 Гл. 8. Линейные рекуррентные последовательности вательностей из 5 (1' (х)) с минимальным многочленом д (х у໠— д» последовательностей из 5 (1(х)) с минимальным мног членом (й (х))' н т. д.

В общем случае для любого с =- 1, 2, ..., существует ровно о'» — ои — '>» последовательностей нз множ: ства 5 (1 (х)), для которых минимальный многочлен равняет" (й (х))'. Объединяя полученные результаты с результатами т рем 3.8 и 8.44, получаем следующую теорему. 8.63. Теорема. Пусть 1! (х) = (д (х))", где д (х) ~ "г"„!х! '. нормированный неприводимьтй многочлен над полем !г'ч, д (0) чь бей (д (х)) =- й, огб (й (х)) =- е, Ь вЂ” натуральное чйсло.

Пус г — минимальное целое число, такое, что р') Ь, где р — хар теристика поля Г . Тогда 5 (Г'(х)) содержит следующее чис последовательностей со следующими минимальными период ! последовательность с минимальным периодом 1, о» вЂ” 1 пос ' довательностей с минимальным периодом е, а если Ь ) 2, о»р' — о»»~ ' последовательностей с минимальным периодом е" ! = 1, 2, ..., ! — 1, и д»ь — 4»л' ' последовательностей с м' нимальным периодом ер'. В случае когда 1(х) 5 Кч !х! — произвольный нормнров ' ный многочлен положнтельйой степени, !' (0) ~ О, то нач с его канонического разложения 1(х) = П (д!(х))", !сл где й! (х) — различные нормированные неприводимые многочле ' над полем Гч, а Ь; — целые положительные числа. Тогда из ремы 8.55 следует, что 5 (1 (х)) =- 5 ((й! (х)) ') + " + 5 ((йь (х))»).

В самом деле, для каждой последовательности о нз 5 (! (х)) ществует единственное представление нида о = — о„+ ... + где о, Е 5 ((д! (х))" ), 1 ( ! ° Ь. Из,теоремы 8.63 известно, кне минимальные периоды могут иметь последовательности 5 ((д! (х))ь!). Аналогичные результаты для минимальных риодов последонательностей, лежащих в 5 О'(х)), можно пол чить, воспользовавшись теоремой 8.59.

8.64. Пример. Пусть ~ (х) = (х' + х + 1)' (х' + ха + 1) ~ Г, !х !. По теореме 8.63 5 ((х'+ х + 1)') содержит последовательн с минимальным периодом 1, 3 последовательности с минимальн, периодом 3 и 12 последовательностей с минимальным периодом В то же время 5 (хл + ха + 1) содержит последовательность с нимальным периодом 1 и 15 последовательностей с минимальн, 4 З. Семейства линейных последовательиостей 64! периодом 15. Значит, образуя все возможные суммы из последовательностей, входящих в 5 ((хе+ х+ 1)') и 5 (х'+ хе+ 1)* и пользуясь теоремой 8.59, получаем, что 5 (~ (х)) содержит 1 последовательность с минимальным периодом 1, 3 последовательиосги с минимальным периодом 3, 12 последовательностей с минимальным периодом 6, 60 последовательностей с минимальным ,и рподом 15 и 180 последовательностей с минимальным перион~м 30.

!:! А!ы только что исследовали поведение линейных рекуррентиых последовательностей относительно операции почленного сложения. Аналогичную теорию можно развить и для операции почлениого умножения, хотя сделать зто гораздо труднее. Если о — последовательность з,, з,, ..., а т — последовательность над полем К„ то определим нх произведение от как последовательность зе1„ з~, ....

Аналогично определяется произведение любого конечного числа последовательностей. Пусть 5 --- векторное пространство над полем Ке, состоящее из всех последовательностей над полем К относительно обычных операций почленного сложения последовательностей и умножения последовательностей на константу. Пусть ~, (х), '., ге (х) — нормированные многочлены над полем Ке, не являющиеся постояииымн, и пусть 5 ()т (х)) ... 5 (гь (х)) — подпространство пространства 5, порожденное всеми произведениями вида о, ...

о„, и; с 5 (!"; (х)), ! = 1„2, ..., й. Тогда имеется следующий фундаментальный результат. 8.65. Теорема. Если 1, (х), ..., Л~ (х) — нормированные много- члены над полем Ке, не Явлаюи(иесЯ постоЯнными, то сУЩествцет не являющийся постоянным нормированный многочлен а (х) р Е Гч (х), такой, что 5 Уе (х)) " 5 ()л (х)) = 5 (И' (х)). Доказательство. Положим Е = 5 (), (х)) ... 5 ф, (х)).

Так как в каждом 5 ф (х)), 1 ( ! ( и, содержится последовательность с начальным членом 1, векторное пространство Е содержит ненулевую последовательность. Далее, Е порождено конечным числом последовательностей и, значит, является конечномерным пространством. Из того, что каждое множество 5 Д, (х)), ( = 1, ..., й, замкнуто относительно операции сдвига входящих в него последовательностей, получаем, что Е обладает таким же свойством, и тогда утверждение доказываемой теоремы следует из теоремы 856 П 8.66.

Следствие. Произведение любого конечного числа линей"ых рекуррентных последовательностей над полем !!'е само является линейной рекуррентной последовательностью над Ге. Доказательство. Из замечания, приведенного после (8.5), следует, что данную рекуррентную последовательность всегда 542 Гл, а. Линейные реиуррентные носледоаательности можно рассматривать как однородную рекуррентную послед вательпость. Тогда искомый результат содержится в теореме 8. Явно определить многочлен д (х), существование которого у верждается в теореме 8.65, в общем случае совсем не прост Однако в ряде частных случаев это сделать легче, Пусть ), (х), ..., )ь (х) — многочлены пад полем Кч, не явля ющиеся константами.

Определим г', (х) ч ... ч )и (х) как но ' мированный миогочлен, корни которого являются различными эл ' ментами вида а, ... аь, где а; — корень миогочлена ), (х) нз поЛ разложения многочлена ), (х) ... (ь (х) над полем 1(ч. Элемен являющийся сопряженным (над 11'и) к произведению а, ...

Характеристики

Список файлов книги