Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 110
Текст из файла (страница 110)
П 8.5. Определение. Периодическая последовательность в„, с минимальным периодом г называется чисто периодической, если равенство в„,г =- вв выполняется для всех п =- О, 1, „, . Следующее условие, которое иногда встречается в литературе, эквивалентно определению чисто периодической последовательности. 8.6, Лемма.
Последовательность дн в„... является чисто периодической тогда и только тогда, когда суи(ествует целое число г» О„л»акое, что вв», = ав для всех п = О, 1, .... Доказал»ельство. Необходимость приведенного условия очевидна. Далее, если условие выполняется, то в„в„... является периодической последовательностью н, следовательно, имеет минимальный период г„причем равенство в„,„, = ав справедливо для всех п» и, н некоторого и, е 1»). Пусть теперь л — произвольное целое неотрицательное число, и выберем такое целое т =:= л,, для которого т = л (глос( г).
Тогда в„,„, = в,„, = — 8„- в„, откуда вытекает, что последовательность а„в„... является чисто периодической в смысле определения 8.5. () Пусть в„вы ... — периодическая последовательность, а г— ее минимальный период, Наименьшее неотрицательное целое число л„, такое, что в„,„= ав для всех п» л„называется предпсриодом этой последовательности.
Периодическая последовательность является чисто периодической, если ее предпериод Равен О. Вернемся теперь к линейным рекуррентным последовательностям над конечными полями н установим основные результаты о свойствах периодичности у таких последовательностей.
8 7. Теорема. Пусть г'» — произвольное конечное поле, а й— ""которое натуральное число. Тогда каждая линейная рекуррентноя последовательность й-го порядка над полем г'» является периодической, При мпом ее минимальный период г удовлетворяет "сровенству г < д», а в случае однородной последовательности— неравенству г < у» — 1. , Показательство. Заметим прежде всего, что существует ровно Различных упорядоченных наборов по й элементов нз поля Г». 5* Гл. 8. Линейные ренуррентные последовательности Поэтому если расслютреть совокупность векторов состояний в О 4 т л дь, данной линейной рекуррентной последовательное й-го порядка ннд полем К„то для некоторых г, 1, О ~ г' < 1 ( должно выполняться равенство з; = зг.
Из соответствующе' линейного рекуррентного соотношения и принципа математич ской индукции можно получить равенство з„„. г == з„для в и .. г'. Последнее означает, что наша линейная рекуррентная и" следовательность является периодической последовательностью если г — ее минимальный период, то г . 1' — г' ~ г)". Рассмотр теперь однородную линейную рекуррентную последовательность.' Если ни один нз ее векторов состояний не является нулев вектором, то, проведя аналогичные рассуждения с заменой на гге — 1, можно получить неравенство г;-., г)' — 1.
Если один нз ее векторов состояний является нулевым вектором, все следующие за ним векторы состояний тоже являются нул выми векторами и, значит, последователыюсть имеет пери г =-= 1 с-. г)ь — !. Теорема доказана. 8.8. Пример. Верхняя оценка для г, полученная в теореме 8. достижима. Это можно показать, рассмотрев линейную рекурре ную последовательность первого порядка над полем Гр (р — пр ' етое число), задаваемую соотношением з„„=- ьв + 1, п = 1, ..., н произвольным начальным значением з, р К„. Если Ге " произвольное конечное поле, а д — примитивный элемент это поля (см.
определение 2.9), то однородная линейная рекуррентн ' последовательность первого порядка над этим полем, задаваем " соотношением зн„, = пз„, и = О, 1, ..., з, ~ О, имеет минимал ный период г == г! — 1. Таким образом, доказана достижим верхней границы для г и в однородном случае. Позже мы покаже что в случае произвольного поля К и любого целого )г )~ ! сущ' ствует однородная линейная рекуррентная последовательносгг й-го порядка над полем Ке, имеющая минимальный период г =- гг" — ! (см, теорему 8.33). 8.0. Пример. Нетрудно заметить, что минимальный пери ' однородной линейной рекуррентной последовательности перво.
порядка над полем Ге делит число г) — 1. Однако для )г )~ минимальный период однородной линейной рекуррентной п . следовательности гг-го порядка не обязан делить число де — 1„' Так, например, можно проверить, что рекуррентная последовв' тельность зе„з„... над полем К„задаваемая рекуррентным с ношением з„,. =- з„„+ з„. гг = О, 1, ..., и начальными зна ниями зе'-- О, хг = 1, имеет минимальный период, равный 20.
8.10. Пример. Лиггейная рекуррентная последовательн над конечным полем является периодической последовательность но не обязана быть чисто периодической последовательность Для доказательства этого достаточно, например, рассмотр 1 !. Регистры сдвига с обратной связью 50! линейную рекуррентную последовательность ~, з„... 2-го поРядка над полем г'я, задаваемую рекуррентным соотношением ,, -- з„„„п = О, 1, ..., и условием д, ~= в,. и Следующий результат дает важное достаточное условие для чистой периодичности линейной рекуррентной последовательности.
8,11. Теорема. Пусть ~, в„... — линейная рекуррентная иостед вательность над конечным полем, удовлеигворяюи(ая линейн..ну рекуррентному соотношению (8.1). Если коэффициент а в (8 1) не равен О, то последовательность дь в„... является чис/ио периодической. Доказа/иельство. По теореме 8.7 линейная рекуррентная последовательность ва, з,, ... является периодической последовательностью. Если / — ее минимальный период, а и, — предпеРиод, то з„,„= в„для всех и ~~ и,.
Допустим, что в нашем случае и„,е- 1. Из соотношения (8,1), полагая п =- и + / — 1 и учитывая, что а, ~= О, получаем — 1/ Ьт» —.-- ао (Вт-~-Я вЂ” ЬЬ» аа — 1Вя~+а — 2-1-» ' ' ' а!Ва -1-» а) = — 1/ = ао (вт-са — ~ — аа,за +а, — ° ° ° — а,з„— а). Используя соотношение (8.1) для и = и„— 1, приходим и такому же выражению и для ва, 1, откуда следует равенство зя„~,, --- з„„~ . Последнее противоречит тому, что и является нредпеРиодом послеДовательности Дь во ....
(з 1!усть в„, в,, ... — однородная линейная рекуррентная последовательность степени й над полем !г'ч, удовлетворяющая линейному рекуррентному соотношению з„,я = а„,в„„, + а„,в„вя,+ +а,в„, и =О, 1,..., (8.2) где а, Е Г,, 0 (1 (й — 1. С этой линейной рекуррентной последовательностью можно связать матрицу А над полем Га размера й;/ й следующего вида: 0 0 0...0 ао 1 0 0...0 ат 010...0 аз (8.3) 0 0 0...1 аят ~:-с1и к -- 1, то под матрицей А понимается матрица А = (аа) Размера 1к!.
Заметим, что матрица А зависит только от линейРекуррентного соотношения, определяющего данную рекуррентную последовательность. Гл. 8. Линеяыыс рекуррсогные послелоаательности 8.12. Лемма. Если з„э„... — однородная линейная рекуррен ная последовательность над полем Гч, удовлетворяющая соотн шению (8.2), а А — матрица, связанная с этой последовате пастью и задаваемая равенством (8,3), т о для векторов сосгпоян последовательности дь э,, ... справедливо равенство з„= — -з„А", п=--О, 1, ...
(8 Доказательство. Так как за = (э„, э„„, ..., э„,„,), то, к' нетрудно проверить, для всех и ~~ О выполняется равенст ' з„„=- а„А, откуда по индукции получается (8.4). Заметим, что множество всех невырожденных й и я-митр над полем Еч образует конечную группу относительно операци матричного умножения. (Зта группа называется общей линейно группой бь(й, го).) 8.!3. Теорема.
Пусть э„, э„... — однородная линейная реку . рентная последовательность и-го порядка над полем Гю так что выполняется соотношение (8.2) и а, Ф О. Тогда минилгальн период данной последовательности делит порядок связанной с не' матрицы А, определенной формулой (8.3) и рассмагприваемой к ' элемент общей линейной группы 6Е (Ь, !)'ч), Доказательство. Так как де1 А = ( — !)ь ' а, Ф О, то и трица А действительно является элементом группы 6Е (я, !1' Если т — порядок А как элемента группы 6Е (к, Ко), то из лемм' 8.12 получаем, что з„, =- заАлч~ =- а,А" =-з„для всех п)~ Отсюда следует, что т является периодом рассматриваемой р куррентной последовательности.
Утверждение теоремы вытека теперь из леммы 8.4. Отметим, что приведенные выше рассуждения вместе с лемм 8.6 дают другое доказательство теоремы 8.1! для однородно случая. Кроме того, из теоремы 8.!3 следует, в частности, ч минимальный период последовательности э„э,, ... делит порядо группы бь (й, К ), который, как известно, равен ум и (г) — 1)(уа — 1)... (у — 1) Пусть теперь з„э„... — неоднородная линейная рекуррентна последовательность Ь-го порядка над полем !1', удовлетворяюща соотношению (8.!).