Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 124
Текст из файла (страница 124)
Теорема. Пусть»„, в„... — .шнейния рекуррентная последовательность Ь-го порядка над полем К, г — ее минимальный период, а )с такое же, как и в теореме 8.78. Tогда для любого элемента Ь Е Г» Доказательство. Зафиксируем Ь Е К» и определим на действительнозначную функцию 6» следующим образом: бь (Ь) = ( и 6» (е) == 0 для всех с Ф Ь. В силу (5.!0) функцию 6» можно представить в виде 6„(с) = — ~у )((с — Ь), Ч и 'ш у Е ~Г».
а сумма берется по всем аддитивным характерам у жх»я,г», Тогда ь,+у †! и,. г! — 1 ~); Х (Ь) ~~~, Х ( ) Выделяя слагаемое соответствующее тривиальному аддитивному характеру поля К», и помечая звездочкой сумму, в которой сума за». 2»в Гл. а. Линейные рекуррентние последовательности мирование производится по всем характерам, кроме тривиал ного, получаем н„'-à — ~ ~(б) - — '„=- —,','~„''Х(б! ',~ Х(.н) х л=е~ Используя (8.3!) и учитывая то, что существует а — ! петри' виальных аддитивных характеров поля Е, получаем н„ьс -1 !.о) —, -' г' ~ „о.)/ .
( ~ ) ( е )' "е Х е=нц 8.83. Следствие. Пусть эьо э,, ....— однородная линейная куррентная последовательность над полем Гч и г — ее минимал" чый период. Пусть минимальный многочлен этой последовател" ности т (х) Е Г (х ! имеет степень Ф . ! и удовлегпворяет ус вию т (О) ~ О. Тогда для любого элемента I> е Рч справедли ' неравенство Доказагпельапво. По теореме 8.44 г = огд (т (х)). Кроме тог' в силу замечания, предшествучоцьего теореме 8.78. П = огд (т (хр Тогда искомый результат следует нз теоремы 8.82 Если линейная рекуррентная последовательность имеет н приводимый минимальный многочлен, то другой метод.
основан ный на суммах Гаусса, приводит к несколько лучшим оценка.' В приводимом ниже доказательстве мы воспользуемся формулам для сумм Гаусса из теоремы 5. ! !. 8.84. Теорема. Пусть эа, э,, ... — однородная линейная реку '. рентная последовательноппь над полем Гп и г - ее минимальны' период. Предположим, что л~инимальныйп .нногочлен этой посл довательногти т (х) являюпся неприводимым многочленом степен й над полем Г и при этом удовлетворяет условию т (О) чи, Пусть й — наименыиее общее кратное чисел г и у -- ! . Тогда ! ( — !)г анри у~О ! е — ! г(Ь) — ', ' 1<~ — ' — — „' + "— ' у -)д!егв>-. (8.
Доказательспио. Положим К = !Гч, и пусть г" — поле разл жения многочлена т (х) над полем К. Пусть а р: г" — коре 4 7. Распределение элементов Обз многочлена т (х); тогда а~О, так как и (О) чь О. По теореме 8,24 найдется 0 Е Р, такой, что з„= Тгр7к (Оал), и = О, 1, (8.39) Очевидно, что 0 чь О. Пусть Л' — канонический аддитивный ха- рактер поля К (см.
(5.6)). Тогда из соотношения (5.9) вытекает, что для любого фиксированного элемента Ь С К 1 1, если з„=- Ь, — У Л (с(Ь вЂ” з„))=~,' се к что вместе с (8.39) дает с †! Л (Ь) = — ~, ~ Л' (Ьс) Л' (Тгр,к ( —.с8ал)). л=е се К с — ! У(Ь) = ! ~~), Л'(Ьс) 7 Л(8 л) = счк л=е с — ! = — '+ — ' У Л (Ьс) Х,Л (с8 ). .Е~ л=о (8.40) В силу (5,17) ЛФ) = —,„', ~б(Ф, Л) ф(Р), где 1! Е Рл, а суммирование производится по всем мультипликативным характерам эр поля Р. Для элемента сЕ К* получаем à — ! с — ! Л (с0ал) у э1 ~ (э(! Л) ф (с8ал) = э=э л='л! с — ! !э, ф (с8) 6 (ф, Л) !), ф (а)".
л=э онутренняя сумма в последнем выражении является суммой чле"ов геометрической прогрессии. Она равняется нулю, если эр (а) чь ~ 1 в силу того, что эр (а) = эр (а') = 'ф (1) = 1. Таким образом, з* Если Л обозначает канонический аддитивный характер поля Р, то Л' и Л связаны между собой равенством Л' (Тгррк (Р)) = Л (р) для всех () Р Р (см. (5.7)). Таким образом, Гл. 8. Линейные рекуррентные последовательности нам необходимо суммировать лишь по множеству л', состоящем ' из всех таких характеров ~, для которых 4) (а) =- 1.
Поэтому е — ! ~~! Л (сг)а") —.— 1е ф (с8) 0 (ер, Л). ч~ — ! а=.е чс и Подставляя это выражение в (8.40), получаем 2(Ь вЂ” ) — 4 ~ Л'(Ьс) ~~) ф(с8)б(+, Л) —-- сй к* вел = — 4 „~~1, Ф(8)б(Ф, Л) У Ф(с)Л'(Ьс). Фсл ° с к' Если через 4" обозначить ограничение характера 4 на К*, то вну' треннюю сумму можно рассматривать как сумму Гаусса на полем К с аддитивным характером Л;(с) = Л'(Ьс) для с Е К'" Тогда 2(Ь) =- — 4, ~, ф(8)6(чК Л)0(ф', Ль).
(8.41, ч (ч' — !) а с г Пусть теперь Ь вЂ” О. Если Л„' является тривиальным аддити ', ным характером поля К, то сумма Гаусса б (4', Ль) обраща в О во всех случаях, кроме случая, когда ~р' является тривиальн характером. В последнем случае 0 (4', ль) — ч — 1. следов ' тельно, имеет смысл брать сумму в (8.41) по множеству А, сос ящему из всех таких характеров ~, для которых $ (а) — — 1 и ф является тривиальным характером.
Тогда г(О)= — '+ " "' У4(8)аМ, Л). оба Тривиальный мультипликативный характер дает в сумму вклад, равный — 1 и, следовательно, г(о) — (' ')' == "„"' ~'*р(8)аМ, Л), — ч(ч" — !) с.> ел А где звездочка означает, что тривиальный мультипликативный, характер исключен из области суммирования.
В силу того, что является нетривиальным характером, получаем, что !сг (ер, Л) ~ =, — Ч"е для любого нетривиального 4ь Отсюда г(О) (', ')' 1~. ", '!' ()А~ !)д -. (8.44: ч' — ! ~ ч(ч' — !) Обозначим через Н наименьшую подгруппу группы се, сойеР: жащую и и К", Элемент се в циклической группе ге имеет поряЮФ 4 7. Распределение элементов следовательно, !Н! =- Л, где Л = НОК 4 с А тогда и только тогда, когда ф (р) = Иными словами, А является аннулятором Н стр, 239). Тогда по теореме 5.6 е (г, о — 1). Далее, 1 для всех () Е Н.
в группе (г")" (см. (8. 43, Теперь б (ф', Ц) =- — 1, если характер !Р' является тривиальным, и 1б (ч!', Ц) ~ = д!!э, если характер !Р' нетривиален. Отсюда следует, что — ! 2(Ь) — ' 1<,' (1 А~ 1+(!,1~ 1 А!)о!м)у!ег»-!. Так как 7 является аннулятором в (ге) подгруппы группы г*. порожденной элементом сс, то по теореме 5.6 ~,7~ =- (дл — 1)/г Вместе с (8,43) это дает (8.38), что и завершает доказательстве теоремы.
Можно также получить результаты, касающиеся распределения элементов основного поля на отрезках последовательности, меньших полного периода. Пусть э, э„... — произвольная линейная рекуррентная последовательность над полем Кц, г — ее мини. мальный период, а и — предпериод. Пусть Ь С Ке — произволь. ный элемент поля, Л!' > и и 1 ~< Л! < г. Тогда через Я (Ь; Л!„Л!) обозначим число таких и, Л!а ( и ( Лг„+ Лà — 1, дла котоРых а„ = Ь, 8.85. Теорема.
Пусть в„э„... — линейная рекуррентная последовательность й-го порядка над полем ге, г — ее минимальный период, а па — предпериод, и пусть число Н выбрано так же, как и в теореме 8.78. Тогда для любого элемента Ь ~ г справедливо неравенство !3(Ь; Л(„Л() — +~ <(! — ~') ( 8) У""( — „'! йг+ ь + )' где Лг ) и и 1 ( Лг .< г. Теперь неравенство (8.37) непосредственно следует из (8,42; и (8.43). Рассмотрим случай Ь Ф О.
Вернемся к формуле (8,41) и заметим прежде всего, что аддитивный характер Ц является петри. виальным. Следовательно, тривиальный мультипликативный характер дает в сумму из (8.41) вклад, равный 1. Таким образом, мы можем записать 2(Ь) — ~; = ' У*ф(В)б(ф, Л)б(ф, Ц). чеэ 666 Гл, 8. Линейные рекуррентные последовательности Доказательство. Используя обозначения и метод доказатель' ства теоремы 8.82, нетрудно получить равенство г[ь; [у,, [у! -- ~~ = —,' '~ 'х [й! нс-М ь х В силу того, что имеется ровяо д — 1 нетривиальных аддитив ных характеров поля Ге, из теоремы 8.81 получаем то; а., м — — ', (: —,' 2„' 2„ра+ К ьлн -,.
(1 -- — ) ( — ) де~'т( — [ойг р — + — ). Метод доказательства теоремы 8.84 также может быть испол зован для исследования распределения элементов поля [г'ч и отрезках последовательности, меньших полного период [см. упр. 8.69, 8,70 и 8.7!). Комментарии $ !. Теория линейных рекуррентных последовательносте имеет очень давнюю историю. В гл. 17 книги Диксона О!сЫоп [40' она прослеживается с 1202 по 1918 г.
Первоначально внимани уделялось линейным рекуррентным последовательностям цел чисел, особенно знаменитой последовательности Фибоначчи Ро, те' Ра, ..., определяемой условиямн Ре = — О, те, = 1 в соотношение". Р„„= Р„„+ Р„, и = О, 1, ..., Позднее линейные рекуррент'-' ные последовательности над полем действительных или комплекс'-': ных чисел рассматривались в основном в связи с исчислением' конечных разностей. Интерес к линейным рекуррентным после. довательностям над конечными полями возник после того, каи. линейные рекуррентные последовательности над Е стали рассмат--: ривать по модулю простого числа р, получая таким образом ли-';" нейные рекуррентные последовательности над полем г .
Начиная:. с 50-х г. ХХ в., линейные рекуррентные последовательности над, конечными полями нашли важное приложение в теории кодиро-;. вания и в электронике ввиду нх связи с переключательными схе-: мами. Краткий обзор истории развития этого направления запериод с 1918 г. можно найти в книге Бе[шег 13, с[т. 21. Важными классическими работами по теории линейных ре-; куррентных последовательностей являются работы 1.псаз [11 И; г['Осанне [11. Обзор этой тематики можно также найти в книгах, 1 исая 12, с[т. 17, 181 и Вас1ппап [5, с[т. 21.
Первый заметный' вклад в теорию линейных рекуррентных последовательностей. над конечными полями был сделан в статьях Мап1е! [1! для слу-'. Комментарнн чая простого поля Г и 5сагр!з [21 для общего случая Гч, Все последующие работы вплоть до середины ХХ в. сконцентрированы вокруг линейных рекуррентных последовательностей над кольцами У и У,'(пг) (см.
Вей (11, СагпйсЛае! (! 1, (21, 13), Епдэ!гопз ! ! 1, (21, НаП 1! 1, 121, 131, 141, магд (21, 131, (4), (71, 181, (9), [! ! 1, 1!21, 1!41, 118) и особенно фундаментальную работу цгагб 15 ]). Кроме того, линейные рекуррентные последовательности над произвольными полями рассматривались в работе %агб (!), а линейные рекуррентные последовательности над произвольными коммутативными кольцамн — в статьях Ттагг[ (131, (!5). Основополагающей работой по современной теории линейных рекуррентных последовательностей над конечными полями является работа 2(ег!ег [4). Обсуждение этой теории можно найти в книгах ЕЬгЛЛо[Е, Ваг!ее (1, сЛ. !3), РогпЛо[Е, НоЛп [1, сЛ.
8). ОП! (2 !. Оо!о~пЬ, 141, Е.ЬпеЬцгд, (21. Ре!егзоп, %е(г[оп. 1! 1. а также в лекциях Бе!шег 13) и в обзорной статье РП!аоге, Магх [11. По поводу более подробной информации о последовательностях Фибоначчи см. ВасЛспапп (5, сЛ. 21, 3агг[еп (! ), Кпц!Л 12, сЛ. 11 н Воробьев ! ! 1, а также журнал «ЕЕЬопасс! (,Епаг!ег[у». Линейные рекуррентцые последовательности действительных или комплексных чисел чсследовались, в частности, в книгах 3огг[ап СЛ. (1, сЬ. !1), М!!пе-ТЛопззоп 11, сЬ. !31, Моп!е1 1! 1, Ь[бг(цпг[ [1, сЛ.
!01, Гель- фонд 11, гл. 51 и Маркушевич 11). Описание технической реализации регистров сдвига с обратной связью и составляющих их элементов приводится в работе МсС!цз!геу [! 1. В статье Е)о!Л (11 обсуждается эффективное построение регистров сдвига с обратной связью с полем ]Га в качестве основного поля.
Связь между регистрами сдвига с обратной связью и линейными рекуррентными последовательностями подчеркивается в работах Оо!огпЬ [4]. Ре1егзоп, Же[дон 11) и Ве[щег 13 ). Обсуждение работы регистра сдвига с обратной связью с точки зрения теории переключательных схем н теории конечных автоматов можно найти в книгах Воо!Л (1, сЛ. 81, СПП [2], Оо!опзЬ (4, сЛ. 21, ЕадеЛ, Ро(а[г 11, сЛ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
