Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 113
Текст из файла (страница 113)
импульсная фуикция. характеристический миогочлеи 51! 1=.слн г-..-. Г < К то из (8.11) и периодичности нашей последовательности вытекает, что г — ! с,= ~; агэ„„г= ~;а„„...,— !=1 — г+! 1=0 а — ! — 1.1, а — ! — 1+г — 2~;, „,; — 2'. 3=г 1.=ΠŠ— ! — 1 Š— ! — 1-1-г =- 2' к! а!гг+!Эггг ~ аггг-г+!Э! 1=О 1=ΠŠ†! — 1 Š†! — 1+г аьегмз1 — ~~а а!~1 гыв1 = д1. 1=0 1=-О Таким образом, теорема доказана. Г.: Лемма 3.1 утверждает, что для любого многочлена ) (х) Е ~ К„]х], 1 (0) Ф О, найдется натуральное число е, такое, что )'(х) делит х' — 1. Это приводит к понятию порядка многочлена /'(х! (см, определение 3.2), который обозначается через огд О'(х)).
8.26. Лемма. Пусть )(х) = ха — аа,х" — ' — а„,х' — ' — — а, ~ []'О [х], гг ': 1, а, Ф О. Тогда огд Д (х)) равняется порядку матрицы А, определяемой формулой (8.3) и рассматриваемой как элемент ру сгг'. (й, Ео). Доказательство. Ввиду того что А — сопровождающая магрппа многочлена ) (х), то 7 (х) в свою очередь является минимальныч многочленом матрицы А. Следовательно, если 1' — единичная 11 '; й-матрнца над полем К то равенство А' = ( для некоторого натурального числа е выполняется тогда и только тогда, когда многочлен ( (х) делит х' — 1. Искомый результат следует теперь из определений порядка многочлена 7 (х) и порядка матрицы А как элемента группы ог'.(К 'о'О).
[:] 8.27. Теорема. Пусть э„, э,, ... — однородная линейная рекуррентная последовательность над полем КО и г' (х) с [ГО [х!— характеристический многочлен этой последовательности. Тогда иинимальный период этой последовательности делит огс[ () (х)), а лгинимальный период соответствующей импульсной функции равняется огд () (х)). При этом если 7' (0) чь О, то обе последава'пельности являю!пса чисто периодическими. Доказательство.
Если ) (0) ~ О, то в силу леммы 8.26 результат является простой переформулировкой утверждений теорем " !3 н 8.17. В этом случае чистая периодичность будет следовать из теоремы 8.11. Если же 7 (0) = О, то представим ) (х) в виде ) (х) =- хай (х), где й (0) ~ 0 (как в определении 3.2), и положим 5<2 Гл.
8. Линейные ренуррентнне последовательности г„— з„,„, п:-- О, 1, .... Если дец (д (х)) > О, то <в. <<, ... — оди родная линейная рекуррентная последовательность с характер стическим многочленом у (х). Ее минимальный период совпада ' с минимальным периодом последовательности з„з,, .... Значи как было показано выше, минимальный период последовател ности вв, з<, ... делит число от<( (у (х)) = от<( () (х)).
Соответству щее утверждение для импульсной функции доказывается англ гичным образом. Если же у (х) — постоянный многочлен, то те рема становится тривиальной. Заметим, что прн Г (0) ~ 0 минимальный период импульсн<' функции можно также получить нз равенства (8.9) следующи способом. Для импульсной функции, характеристический мно член которой равен 7'(х), многочлен 6 (х), появляющийся в фо ' муле (8.10), равен просто — 1. Значит, если г — минимальн период импульсной функции, то на основании (8.9) Г (х) дел х' — 1, и, следовательно, г ь огб () (х)).
С другой стороны, основании первой части утверждения теоремы 8.27 г должен делят огд () (х)). Таким образом, получаем искомое равенство г =< =- от<) 0'(х)). 8.28 Теорема. Пусть во, з,, ... — однородния линейная рекур' рентния последовительность над полем г' сненулевым вектора' начального состояния. Пусть ее .характеристический многочле <'(х) Е Е !х! является неприводи,ным л<ногочленом над полем и удовлетворяет условию ) (0) ~ О.
Тогди последовательность за з<, ... является чисто периодической последовательностью и минимальный период г равен ог<) ()'(х)). Доказательство. Из теоремы 8.27 вытекает, что рассматр'"' ваемая последовательность является чисто периодической и минимальный период г делит огд ()<(х)). С другой сторон из (8.9) следует, что 7" (х) делит (х' — !) Ь (х).
Так как з (х), следовательно, и п(х) являются ненулевыми многочленами так как дец ()< (х)) < дед О< (х)), то из неприводимости г ( вытекает, что миогочлен ) (х) делит х" — 1, и, значит, г ) огдО' (х)). Дадим теперь другое доказательство следствия 3.4. Для уд ства приведем еще раз его формулировку.
8.29. Теорема. Пусть )< (х) Е К„(х ! — неприводимый мно",' гочлен над полем Кр и <(ец (! (х)) — -- й, Тогда огд (! (х)) дели<<в дд ь Доказительство. Не теряя общности, можно считать, ч 7 (х) является нормированным многочленом и ) (0) чь О. Рассмо"', З 2. Импульсная функция, Характеристический миогпчлен 5!Э грим однородную линейную рекуррентную последовательность иад полем Ка с характеристическим многочленом ) (х) и ненулевым вектором начального состояния. По теореме 8.23 эта последовательность является чисто периодической, и минимальный пе,код этой последовательности равняется огс) Д (х)). Тогда в ней встречаются огс) () (х)) различных векторов состояний. Если огс) () (х)) меньше г)» — 1, общего числа ненулевых )с-мернык векторов над полем ге, то можно выбрать й-мерный вектор, который не встречается в качестве одного из векторов состояния указанной выше последовательности.
Возьмем этот вектор в качестве вектора начального состояния другой однородной линейной рекуррснтпой последовательности над полем Ге с тем же характеригтнческим многочленом ) (х). Ни один нз е = огг1 () (х)) различных векторов состояния этой последовательности не равняется ни одному вектору состояния предыдущей последовательности. В противном случае этн две последовательности. начиная с какого-то мсс|н, должны были бы совпадать, и тогда вектор начального состояния второй последовательности должен был бы встретиться и первой последовательности в качестве одного нз ее векторов состояния, что противоречит его выбору.
Продолжая указанным выше образом строить новые рекуррентные последовательности, получаем разбиение множества, состоящего из г)ь — 1 ненулевых )г-черных векторов над полем Еч, па подмножества мощности с = огг) (Г" (х)) каждое, что и доказывает утверждение теоремы.
Д 8.30. Пример. Рассмотрим линейное рекуррептное соотношение ь„„, =-= з„„+ з„,а + з„„+ зн, и -- О, 1, ..., над полем Ге. Соответствующий характеристический многочлен Г (х) = — х" — х' — х' — х — 1 Е Ге [х! является неприводимым миогочленом над полем Га Кроме того, (" (х) делит хгя — ! и не является делителем многочлена вида х' — ! нн для какого О < е с < 21. Таким образом, огг) () (х)) =- 21. Импульсная функция, соответствующая данному рекуррентному соотношению, имеет вид <Х'Д О, О, О, 1, О, 1, О, О, 1, О, О, 1, 1, О, О, 1.
О, 1, 1, О, О, О, О, О, 1, .... Как и должно быть. эта последовательность пернодичпа с мигшмзльным периодом г = 21. Если в качестве вектора начального состояния взять вектор (О. О, О, О. !. 1), то мы получим бинарную последовательность . О, О, О, 1, 1, 1, 1, О, 1. 1. О, 1, О, 1, О, 1, 1.
1. О, 1, О, О. О, О, 1. 1,,... г ь1иннмальным периодом г = 21. Если же в качестве вентора начального состояния взять вектор (О, О, О, 1, О, О), то мы получим бнн"рную последовательность О О. О, 1, О, О, О, 1, 1, О. 1, 1. 1, 1, 1, 1, О. О, 1, 1, 1, О, О. О, 1. О, О, ..., Гл. а. Линейные рекуррентяые последовательности также имеющую минимальный период 2!. При этом каждый:' ненулевых 6-мерных векторов над полем г» появляется в кач вектора состояния в точности в одной из этих трех послед тельностей. Если в качестве вектора начального состояния вз ' любой ненулевой вектор, то мы получим рекуррентную после вательность, имеющую минимальный период, равный 21, и сов ' дающую с точностью до сдвига с одной нз трех полученных вы"' последовательностей.
:3 8.3!. Пример. Если многочлен )'(х) Е Е„(х! степени й п ' водйм, то его порядок огд (!" (х)) не обязательно делит число д» вЂ”;, Чтобы показать это, рассмотрим, например, многочлен 7'(х) "' =- х' -г х+ 1 Е ((» 1х). Этот многочлеп приводйм, так как ! (х) = х» -' х 1- 1 — (х» -»- х' ь 1) (х' -( х + !). Из теоремы 8.27 и примера 8.14 следует, что огд (!' (х)) равен и не является делителем числа 2' — 1 = 31. Для приложений особый интерес представляют линейи рекуррентные последовательности, имеющие очень большой и нимальный период. Из теоремы 8.7 известно, что для однород линейной рекуррентной последовательности й-го порядка полем Е минимальный период не может превышать д»вЂ” Для того чтобы построить рекуррентную последовательно минимальный период которой в точности равен д» вЂ” 1, поспал зуемся понятием примитивного многочлеиа (см.
определение 3.1 8.32. Определение. Однородная линейная рекуррентная следовательность над полем Гр, характеристический многочл которой является примитивным многочленом пад полем а вектор начального состояния — ненулевым вектором, на вается последовательностью максимального периода над полем 8.33. Теорема. Кажда» последовательность й-го»»прядка.( максимального периода над полем (Г„не~гнется чисто периода ской последовательностью, а ее минимальныи период равняв ц» — 1, наибольшему из возможных значений, которое мо принимать минимальный период однородной линейной рекурре ной последовате.»ьности й-го порядка над полем Доказательство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
