Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
последовательности о равняется минимальному периоду последовательности
а2. Далее, из данной последовательности ст2 ? S {g (х)) можно получить qh
различных последовательностей из S (/ (х)), прибавляя к а2 любую нз qh
последовательностей из S (У'). Следовательно, еслн rit г( - минимальные
периоды последовательностей из S (g (х)), a Nlt ..., Nt число
последовательностей из S(g(x)), имеющих минимальные периоды, равные
соответственно гъ ..., rit то для каждого С 1 С существует ровно
qhNt последовательностей
из множества S (/ (х)), имеющих минимальный период г*, и никаких других
минимальных периодов у последовательностей из S (f (х)) быть не может.
Пусть теперь h - 0; тогда / (0) Ф 0. Предположим, сначала, ято / (х) -
неприводимый многочлен над полем (F?. В этом случае нз теоремы 8.44 и
8,50 мы получаем, что каждая последовательность из S {/ (х)) с ненулевым
вектором начального состояния имеет минимальный период, равный ord (/
(х)). Значит, одна последовательность из S (/ (х)) имеет минимальный
период 1, у остальные q^u (f (хц ~ j последовательностей имеют
минимальный период ord (/ (х)).
Далее, рассмотрим случай, когда / (х) является степенью неприводимого
многочлена. Тогда представим / (х) в виде / (х) -Ш (х))Д где g (х) ? fq
1x1 - нормированный неприводимый многочлен над полем f?. а Ь >- 2 - целое
число. Тогда минимальный многочлен любой последовательности из множества
if (х)) с нулевым начальным вектором имеет вид (g (х))с, где 3 с •/ Ь. По
теореме 8.53
S (g (х)) ^ S {{g (x)f) c,.,gS(/ (*)).
1 а к и м образом, если deg (g (х)) k, то имеется qk - I послед о-
540
Гл. 8. Линейные рекуррентные последовательности
вательностей из S (f (л:)) с минимальным многочленом g (ж). д-ik __ дк
последовательностей нз S (f (х)) с минимальным мног^ членом (g (д:))2 и
т. д. В общем случае для любого с -- 1, 2, уществует ровно qck- qic~^k
последовательностей из множе
ства S {f (л:)), для которых минимальный многочлен равняет) (g (д:))с.
Объединяя полученные результаты с результатами ti рем 3.8 и 8.44.
получаем следующую теорему.
8,63* Теорема* Пусть f (дг) = (g (х))6, где g (х) ? Ixl нормированный
неприводимый многочлен над полем f 7, g (0) ф deg (g (л:)) ~ k, ord (g
(л;)) - e, Ь - натуральное число. Пу< i- минимальное целое число, такое,
что pi !>- Ь, где р - теристика поля f q. Тогда S (f (л:)) содержит
следующее последовательностей со следующими минимальными периодам I
последовательность с минимальным периодом 1 * qk- 1 т довательностей с
минимальным периодом е, а если Ь> 2,
I
qkpt __ qkpi- последовательностей с минимальным периодом в}
¦dl
sm
j = 1, 2,
* I
i- 1
и q
kb
Я
kp
t-\
последовательностей
с
нимальным периодом ер1.
В случае когда [ (х) ? f" UJ
¦т
- произвольный нормиров ный многочлен положительной степени, ^(0)^0, то
иачщ с его канонического разложения
k
f(X)
П fe (X))
•Ii
%
'¦Ж
где gi (х) - различные нормированные неприводимые многочлб! над полем fq,
a bt - целые положительные числа. Тогда из т ремы 8.55 следует, что
S ((?i М)*1) + ' ' ' 4- S ((gh (x)fh)-
для минимальных S (f (а:)), можно поЛ
s а (л-)) =
В самом деле, для каждой последовательности а из S (f (ж)) ществует
единственное представление вида cr= or, + ... +
где a, g S (fe (*))')> 1 < I < h. Из, теоремы 8.63 известно, ж кие
минимальные периоды могут иметь последовательности
s(fe (д:))*?). Аналогичные результаты риодов последовательностей, лежащих
в чить, воспользовавшись теоремой 8.59.
8*64. Пример, Пусть
f (,v) = (х2 + х + I)2 (х4 + х5 + !) С F2 U J.
По теореме 8.63 S,({x2 + х f I)2) содержит последовательно с минимальным
периодом I, 3 последовательности с минимальн периодом 3 и 12
последовательностей с минимальным периодом В то же время S 0с4 + х3 1)
содержит последовательность с М
нимальным периодом 1 и 15 последовательностей с мииимальй
Ш
. <1{ > • • К?
хт
§ 5. Семейства линейных последовательностей
541
периодом 15. Значит, образуя все возможные суммы из последо*
вательиостей, входящих в S ((х2 + х + I)2) и S (х4 + х3 + I)" и пользуясь
теоремой 8.59, получаем, что S (f (х)) содержит I последовательность с
минимальным периодом 1, 3 последовательности с минимальным периодом 3, 12
последовательностей с минимальным периодом 6, 60 последовательностей с
минимальным периодом 15 и 180 последовательностей с минимальным периодом
30. 0
Мы только что исследовали поведение линейных рекуррентных
последовательностей относительно операции почленного сложения.
Аналогичную теорию можно развить и для операции почленного умножения,
хотя сделать это гораздо труднее. Если а-последовательность s{[, slt ...,
а т - последовательность г0, 4- ¦ ¦ наД нолем FrP то определим их
произведение от как последовательность s04, Mi Аналогично определяется
произведение любого конечного числа последовательностей. Пусть S -
векторное пространство над полем F<p состоящее из всех
последовательностей иад полем Гч относительно обычных операций почленного
