Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 129
Текст из файла (страница 129)
(4, й'з). Упражнения 8.5. Доказать результаты нэ примерз 8.18 с помощью методов й 5. 8.6. Пользуясь равевством (8.8), получить явную формулу для членов лннейной рекуррентной последовательности над полем Гз, определяемой рекур- рентным соотношением хи+а =- — заы + з„, и = О, 1,..., н начальными усло- знямн зз = зг =- 1 зз = О. 8.7. Пользуясь результатом, приведенным в замечании 8.23, получить явную формулу для членов рекуррентной последовательности иад полем з", определяемой ренуррентным соотношением з нз = азя+з + знех + ази, и = О, 1, , гДе и — пРнмнтнвиый элемент полЯ Км и начальными УсловиЯмн М==з)=;зх =.О,аз=! 8.8. Доказать, что члены з„, задаваемые формулой, приведенной в замечанин к.23, удовлетворяют однородному линейному ренуррентному соотношению с характеристическим многочленом 7 (х).
8.0. Доназать результат, приведенный в замечании 8.23, для случая е! з 2, 1,2,...,ш, не;=-1, еслиа!=.0 8.10. Представить элементы линейной рекуррентной последовательности над полем !) з, определяемой рекуррентиым соотношением з„ьз = зн+з+ з„, и О,:, .... и начальными условнямн з, = О, з, =. зз = 1, с помощью подходя- щей фуннцнн следа. 8.11. Доказать лемму 8.26, используя линейные рекуррентные последова- тельности, 8.12. Найти минимальный период последовательности, порожденной им. пульсом и удовлетворяющей линейному рекуррентному соотношению зн+т —— = зли+ янез+ зз+~ + зп. и = — О, 1, ..., над полем Гз.
8,13. Найти минимальный период последовательности, порожденной им- пульсом, соответствующей линейному ренуррентному соотношению з„ш = эдикт г заех + апет + зч, и =. О, 1, ..., над полем 8.14. Доказать теорему 8.27, пользуясь производящими функциями. 8,15.
Найти линейную рекуррентную последовательность наименьшего порядка над полем !)'з,минимальный период которой равен 21. 8.16. Найти лийейную рекуррентную последовательность наименьшего порядка над полем г'з,минимальный период которой равен 24. 8.17. Пусть г -- минимальный период последоеавельности Фибоначчи над полем г ч, т. е. последовательности, определнемой рекуррентным соотношением з„, — з„~, + зто п . — О, 1,..., н начальнымн условиями зз = О, з, =- 1, Пусть р — характеристика поля гчч.
Доказать, что г = 20, если р = 5, г делит р — 1, сслн р и Ш1 (щи 5), г делйт рз — 1 во всех остальных случаях. 8.18. Построить последовательность максимального периода над полем Гз, пчеющую мнвнмальный период, равный 80. 8.10. (т, й)-последовательностью де Вредна называется конечная последова- ныьность з,, з,... зп--ы содержащая М = т членов, взятых из множества, з содержащего а различимых элементов, такая, что все наборы длины й вида (з„, ззео ..., зя,з,), и = —.
О, 1, ..., Ф вЂ” 1, где нижние индексы берутся по модулю М, являются различными. Доказать, что если и'„и',, ... — последовательность й.го порядна, порожденная импульсом н являющаяся последовательностью макси- чальпого периода над полем Гч, то последовательность зэ —.. О, за= пя-т, 1 « -. н «С вЂ” 1, является (д, й)-последовательностью де Брейиа. 8.20.
Построить (2, 5)-последовательность де Брейна. 8.21. Пусть В (х) —.. 2 — к+ х' Е )г т (х). Найти первые шесть ненулевых членов формального степенного ряда 1/В (х). 8.22. Пусть д (х) †. — — 1 — х -(- хз, В (х) = ~~ ( --1)" х" Е Г з Пх)). ч=а ! !.~нгч первые пять ненулевых членов йюрмального степенного ряда А (х)/В (х).
582 Гл. 8. Линейные ренуррентные последовательности 6.23. Рассмотрим линейную рекуррентную последовательность над полем Кз, задаваемую рекуррентиым соотношением за+» =- зв»» + з„»з — зв»т + + з„, и = О, 1, ..., н начальнымн значениями з, =. з, =- зз †. 1, зз = з» = — 1... Представить производящую функцию этой последовательйостн в виде (8.15) 8.24.
Найти первые восемь членов последовательности, порожденной импульсом н соответствующей линейному рекуррентному соотношению за»з =- =- за+»+ зя+з+ зя, л = О, 1, ..., над полем Ф'з. Воспользоваться операцией деленна »слом. 8.2$. Пусть зз, зы ... — однородная линейная рекуррентная последователь.", ность над полем 2'».
Доказать, что множество всех многочленов ! (х) .= аг,х + : з + ... + а,х+ а, ~ 2» (х), таких, что аазя»ь+ ... + а,зчщ+ аы„О для всех и = О, 1, ..., образует идеал в кольце )Р» (х). Вывестн отсюда, что суще з ствует однозначно определенный минимальный многочлен рекуррентной после- ... довательности. 8.26. Рассмотрим линейную ренуррентную последовательность над полем 2"з,:, определяемую рекуррентным соотношением зящ =- зх»т+ злы+ за+*-1- з„, л = '.~ -.- О, 1, ..., н начальнымн зна~еннями з, = з, =- з, =- зз =.
з„=- О, зз == з, =. == з, =- 1. Используя метод доказательства теоремы 8,42, найти минимальный многочлен данной рекуррентиой последовательности 8.27. Рассмотрим линейную рекуррентную последовательность иад по. ~, лем Г», определяемую рекуррентным соотношением з„+» —— — 3»и+» — зя+з+ зя. л —. О, 1, ..., и начальиымн значениями щ = з, = з, .= 1, з, = — !.
Используя метод доказательства теоремы 8.42, найти минимальный многочлеи данной ре-' куррентной последовательности. 8.28. Показать, что однородная линейная рекуррентная последовательность,, над конечным полем явлнется чисто периодической последовательностью тогда н только тогда, когда ее минимальный многочлен т (х) удовлетворяет условшо гл (0) чь О. 6.29. Пусть дана однородная линейная рекуррентная последовательность! над нонечным полем и гл (х) — ее минимальный многочлеи.
Домазать, что длина. предпериода данной последовательности равняется кратности элемента 0 как, корня многочлена гл (х). 8.36. Доказать следствие 8.52, используя способ построения минимального ' многочлена, приведенный в доказательстве теоремы 8.42. 8.3!. Пользуясь критерием, полученным в теореме 8.51, найти минимальный, многочлен линейной рекуррентной последовательности над полем Кз, задаваемой рекуррентным соотношением з„»» = з„ез + зя»з + злы + з„, л.== О, 1, и вектором начального состояния (1, 1, 1, О, О, 1).
8.32. Найти минимальный период линейной рекуррентной последователь- " ности нз упр. 8.25. 8.33. Найти минимальный период линейной рекуррентной последователь- '; ности иэ упр. 6.27. 8.34. Найти мнинмальный период линейной рекуррентной последовательности над полем 3'з, задаваемой рекуррентным соотноц~еннем за»» =- за+г+ + зч»»+ ямы+ зь, л = О, 1,, н иачальнымн значениями щ = з~ — за —— = 3» = — зт = О, зз = — з» = зз = зз = 1. 8.35. Найти минимальный период линейной рекуррентиой последовательности над полем Кз, заданной рекуррентным соотношением з„»» —.—.
за»» — за»з+ + зч+з+ з». л = О, 1, ..., н начальными значениями зз:= з, =- 1, зз = — зз — — О, з,= — !. 8.36. Найти минимальный период линейной рекуррентной последовательности иад полем 2», определяемой рекуррентным соотношением зв»» = з»+з+ + за»з — за — 1, л = О, 1, ..., и вентором начального состояния (О, — 1, 1, 0). 8.37.
Доказать, что линейная рекурреитная последовательность А-го порядка яь з,„... над полем Г» имеет минимальный период, равный », только в следующих случая х: Упражнения (а) А=!, 4 — простое число, з„> =з„+а, в=0,1, ...,и Е Г»; (») й = 2, д = 2, з„»з = зв + 1, л = О, 1, .... 8.38. Пусть дана однородная линейная рекуррентная последовательность нзд полем Гч н т(х) Е й'ч [х) — ее минимальный многочлеи, отличный о-[ константы. Пусть корни этого многочлена отличны от нуля и не валяются крат нымн.
Доказать, что минимальный период данной последовательности равен такому наименьшему натуральному числу г, при котором выполняется равенство гг" =. 1 для всех корней сг многочлена гл (х). 8.39. Донаэать, что если однородной линейной рекуррентной последова тельиости о над полем Ге соответствует минимальный многочлен Г(х) Е й'ч [х' и бей ([ (х)) = л ~ 1, то любую последовательность из множества Я (Г (х)) можнс единственным образом представи~ь в виде линейной комбинации исходной после довательиости о=о!а> и последовательностей о! >, о! >, ..., о!" >>, полученных с помощью сдвигов исходной последовательности о, с нозффициентами из поля Гч. 8.40.
Пусть [, (х), ..., [ь (х) — попарно взаимно простые нормированные многочлены над полем й'ч, не являющиеся константамн. Показать, что простран. ство 5 ([, (х) ... [ь (х)) является прямой суммой линейных подпространств 6 (Д (х)), ..., 5 ([ь (х)). 8.41. ПУсть д„зы ... — одноРоднаи линейнаЯ РекУРРеитиаЯ последовательность над полем К = йе, а Г(х) — ее харантеристический многочлен. Пусть [ (Н =- Д (х) ... [, (х), где >! (х) — различные нормированные неприводимые многочлены над полем К. Пусть, далее, сг! (! = 1, ..., г) является фиксированным корнем многочлена [! (х) в его поле разложения Р! над К. Доказать, что существуют однозначно определенные элементы О, Е гт, ..., О, ч г"„для которых выполняется равенство з„ = Тгл [д [6>а>) + + Тгк [О а,"), я = О, 1, ...
8.42. Пользуясь обозначениями, введенными в упр. 8.41, показать, что [(х) является минимальным многочленом последовательности аь з„, ... тогда и только тогда, когда 0> Ф О для всех ! = 1, „., г, Получить отсюда, что число последовательностей в 8 ([(х)), минимальным многочленом которых является [ (х), задается формулой ц ' — 1у... (д ' — 1), где А! =- дай ([! (х)), ! = 1, ..., г. 8.43, Пусть о, и аз — последомтельностн, порожденные импульсом, наз полем ге, связанные с линейными рекуррентными соотношениями з„», = з »з -[ + з» (и = О.
1, ...) н зх+з = зв+т + з„ (л = О, 1, ...) соответственно. Йайтв минимальный период последовательности о + а . 8 44. Пусть аг — линейная рекуррентная последовательность над полем Гз заданная ренуррентным соотношением з„+з — — з„+з — зв»г — з» и вектором начального состояния (О, 1, 0). Пусть о, — линейная рекуррентная последовательность над тем же полем, заданная рекуррентным соотношением зх»» = ш»з — зв+з+ зл, л = О, 1, ..., и векторам начального состояния (1, 1, 1, О, 1). Пользуясь методом, приведенным в примере 8.58, найти минн мальный многочлен последовательности о = о, + оз. 8.46. Найти минимальн>46 период последовательности о иэ Упр 8 44. 8.46. Пусть дана однородная линейная рекуррентная последовательность иад полем х'з и х» + хз + х» + 1 П й з [х[ — ее минимальный многочлен.
Найти минимальный многочлен последовательности, являющийся бинарным дополнением н исходной. 8 47 Пусть [(х) = х»+ х + х + х + х + минимальные периоды последовательностей из 3 ([ (х)), а также число последовательностей, соответствующих каждому значению минимального периода. 8.48.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
