Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Доказательство. Если г - минимальный пернод последовав тельности sQi slf
.... а я0 - ее предпериод, то = sn для всеЖ п ^ п0. Значит, наша
последовательность удовлетворяет одно** родному рекуррентному соотношению
П
0, 1,
Й
Тогда по теореме 8.42 многочлен т (х) делит многочлен хп"~^Г - хпо == хп"
(хг - 1). Отсюда получаем, что т {х) имеет т (х) = xh g (х), где h < n0.
a g (х) ? Fg lx], g (0) Ф 0 и g делит xr - 1. Из определения порядка
многочлена следует, что ord (т (х)) = ord(g (х)) <; г. С другой стороны,
по теорем^
8.27 г делит ord (т (х)), откуда и следует, что г = ord (m(x)).
iP.
§ 4. Минимальный многочлен
527
8.45* Пример, Пусть s0, slt ...- линейная однородная последовательность
над полем f2t удовлетворяющая рекуррентному соотношению sn+& = sn+1 + sn,
п - О, I, ..., с вектором начального состояния (I, 1, КО, 1). Следуя
методу доказательства теоремы 8.42, возьмем f0 (дсЪ = хь - х,- 1 - + х~Ь
1 G
^ f2 (8.10) получаем, что hQ (х) = х4 -f- я* + х2. Тогда
^ (х) = х2 -f х -f 1, н, таким образом, минимальный многочлен т (ж) нашей
последовательности равен /0 {x)id {х) = х3 -f- х2 + 1. Так как ord (т
(х)) = 7, то отсюда по теореме 8.44 получаем, что минимальный период
нашей последовательности равен 7 (ср. с примером 8.18). Q
Из приведенного только что примера видно, как можно находить минимальный
период линейной рекуррентной последовательности, ие вычисляя ее членов.
Этот метод особенно эффективен, если в нашем распоряжении имеется таблица
порядков многочленов. Так как такие таблицы обычно включают в себя лишь
сведения о порядках неприводимых многочленов (см. § 2, гл. 10), для
нахождения порядка данного многочлена необходимо воспользоваться
теоремами 3.8 и 3.9 (ср. с примером 3.10).
8*46* Пример. Метод, использованный в примере 8*45, можно также применять
н в случае неоднородной линейной рекуррентной последовательности. Пусть
se, s1( ... - последовательность над полем f2, удовлетворяющая
рекуррентному соотношению
Зл+4 = Sn+g 5л+1 -{- Sn 1, ft ~ 0, 1,
с вектором начального состояния (1, 1,0, 1). В соответствии с (8.5) эту
же последовательность можно получить с помощью однородного линейного
рекуррентного соотношения
Sn+5 " S7143 "f~ Sn+2 "Ь Sn> ft - 0, 1,
выбирая вектор начального состояния равным (1, 1,0, 1,0). Действуя так
же, как в примере 8.45, находим соответствующий характеристический
многочлен
/ (х) = х5 4- х* + х? 4- 1 -- (х + I)3 (х2 + х 4- 1) ? Fa [х],
который в данном случае совпадает с минимальным многочленом т (я) нашей
последовательности. Так как по теореме 3.8 °rd ((х + I)3) = 4, a ord (х2
-f х + 1) = 3, нз теоремы 3.9 следует, что ord (т (х)) = 12. Поэтому
последовательность s0, ... яв-
ляется чисто периодической последовательностью с минимальным периодом,
равным 12. ?
8.47. Пример. Рассмотрим линейную рекуррентную последовательность Si, ...
над полем задаваемую рекуррентным
соотношением
S7l+4 " St*+2 Н~ S7l+1> я ~ 0, 1, ,.*"
528 Гл. 8. Линейные рекуррентные последовательности
с вектором начального состояния (1, 0, 1, 0). Тогда
f (х) ~ х4 + х2 + х - х (х$ 4 х -j- 1) ? Fa lx 3
./з.
'Ш
'-Л '
- характеристический многочлен нашей последовательности в силу того, что
ни х, ни х3 -f- х 4 1 ие является характеристик ским многочленом этой
последовательности, получаем т (х) ~ х* 4 х2 + х. Таким образом,
последовательность s0, slf является периодической, но не чисто
периодической, а ее мй мальиый период равняется ord (m (х)) = 7.
8.48. Теорема. Пусть s(}, sx, ... - однородная линейная куррентная
последовательность над полем Fq, а Ь-некопщ натуральное число. Тогда
минимальный многочлен тх (х) сдви той последовательности s6, s6+1, ...
делит минимальный мн член т (х) исходной последовательности s", .s,..
Если % $х, .
чисто периодическая последовательность, то тЛ (х) - т (х).
*
Доказательство. Для того чтобы доказать первое утвержде в силу теоремы
8.42 достаточно показать, что любое одноро линейное рекуррентное
соотношение, которому удовлетвор исходная последовательность s0, slt
также справедливо для сдвинутой последовательности. Последнее очевидно,
доказательства второго утверждения рассмотрим однородное нейиое
рекуррентное соотношение
fr
г I
"К
№
• • 1>
%
¦I
'• i
45:
-4 OqS
rt+&"
rt
0, 1,
* * *
'. :m
•V •
A.-
(c)
- s
rt
которому удовлетворяет сдвинутая последовательность.
г - период последовательности s0, sx так что sn+r
всех п 0. Выберем целое число с, для Которого сг используя линейное
рекуррентное соотношение, в котором заменено на п 4 сг - Ь, и учитывая
свойство периодичности лучаем, что
1
¦floSn, rt>0.
Последнее означает, что последовательность sx, ... удо творяет тому же
линейному рекуррентному соотношению, чт<*$ сдвинутая последовательность.
Применяя вновь теорему 8. получаем, что тх (х) - т (х).
8.49. Пример. Пусть s", sx,
линейная рекуррентная
следовательность над полем F2, рассмотренная в примере 8. Ее минимальный
многочлен равен х4 4 х2 4 х, в то время к минимальный многочлен сдвинутой
