Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 127
Текст из файла (страница 127)
4]. Теорема 8.44 пре ' ставляет собой важное связующее звено с теорией порядков мно членов (см. з ! гл. 3 настоящей монографии). Теорема 8.5! о '" видным образом связана с детерминантным критерием нз й: ' настоящей главы, где также содержится и другой метод нахож ния минимальных многочленов. Фитцпатрик (ГВгра1г]сй [!]) исследовал проблему получен " линейной рекуррентной последовательности над полем Гт зада ного заранее периода с помощью рекуррентного соотношен минимально возможного порядка.
Много работ было посвящ определению минимального периода последовательности Фи наччи над Г„или У!(и) (см. Вагпег [1], Са11!п [1], ГцВоп, Могг [!), НаВоп [1], К!цучег [1], Машанова]с!з [1), ]тоЬ]пзоп О. [1), 5(ап1еу [!], [2], Тас]с)!пд [1), ч!псе [1], 17!пзоп [1), Ж [1]), а также более общих последовательностей 2-го порядка н Г или У/(и) (см. ВцпбзсЬиЬ, БЬ]не [2), К!зз, Вш МшЬ РЬо 11[, моЬ!пзоп ь). %'. [3], 5ш!1Ь, Нодара]! [1), 5опипег [2], [4], 'тату]ег [1), Уа]ач!81 [1), [2], Уа!ач]81, Кг!зЬпа [1)).
Иссл ванна, касающиеся минимальных периодов линейных рекурре ных последовательностей высших порядков над кольцами выч ' тов, проводились в работах СагппсЬае! [2], ]3], Епяз1гош [1' [2], На]1 [3), Магг] [2), [5]. й 5. Основополагающей работой по структуре векторн пространств 3 (7 (х)) является работа Х]ег!ег [4), где получе теоремы 8.53, 8.54, 8.55 н 8.56, а также результаты о минимальн " ' периоде суммарных последовательностей. Пространства 3 (7 (х изучались также в работах Г1!!тоге, Магх [1 ] и Ве!тег [3, сЬ. 3, 4 ь Операция бинарного дополнения изучалась в книге Бе!лег [ сЬ. 6]. В статье Кшпаг, Кшпаг] [1) рассматривался эффект пер, хода к бинарному дополнению только в одном или в двух места' ' на длине одного периода.
Теорема 8.63 была получена в ра 'т]7агс] [5] для случая конечных простых полей. Переход к прои вольному 7 (х). описанный вслед за теоремой 8.63 (ср. с примеро 8.64), можно также получить с помощью символического мето Комментарии нз 4 5 следующей главы, который пригоден и для более общего ;лучая. Распределение минимальных периодов в 5 (7 (х)), назынаемое также цикловой структурой пространства 5 (7(х)), обсуждается в работах ГИ!тоге, Магх [1], 5е!шег [3, сЬ. 4) и Х!ег1ег 14). Вопрос совпадения, возникающий в этом контексте, был решен в работе [)пчаИ, К!Ыег [1]. В статье Фагй [9] изучанось распределение минимальных периодов для случая линейных оекуррентных соотношений над У/(гп). Вопрос, какие значения нижет принимать минимальный период линейной рекуррентной последовательности я-го порядка иад полем К при фнисированных й н д, изучался в книге [.йпеЬпгп [2, сЬ.
32, 33]. Тот факт, что в результате почленного умножения линейных пекуррентных последовательностей получается снова линейная оекуррентная последовательность, был отмечен еще в статье ГОсадпе [1), где исследовались последовательности действительших чисел и был доказан более слабый вариант теоремы 8.67, а именно, что для этого случая 5 (7,(х)) ... 5ф,(х)) ы 5(71(х) н ... ч7н(х)). Для конечных полей операция почленного умножения последозательностей впервые изучалась в книге 5е!тег [3, сЬ. 4].
Более ,щательное исследование этого вопроса было проделано в работе /[ег[ег, МИ!з [1], где были получены теоремы 8.67 и 8.72. В этой же работе было показано, как использовать полученные результаты для нахождения многочлена д (х) из теоремы 8.65 в общем случае. Взаимосвязь между множествами 5 (7 (х)) и 5 ((7 (х))") изучалась 1 статье РИ!шоте, Магх [1]. Некоторые элементарные замечания , тносительно операции почленного умножения последовательностей содержатся в работе Вгоиззеап [1]. В статье Гпгз(епЬегд ~! 1 получен аналог следствия 8.66 для более общих типов последовательностей над полем [!'ч. Операция над последовательностями, называемая децимацией !йесппаИоп) или разрядкой, была предложена Голомбом (Со!ошЬ [11) и определяется следующим образом: если о — последовательность элементов з,, з,, з,, ...
нз поля ге, а й ~ [ч — натуральное число, то разреженная последовательность оы~ состоит из членов з,, зю з„,, ..., т. е. оои полУчаетсЯ пУтем выбоРа каждого а-го члейа исходной последовательности о, начиная с з,. Частные случаи этой операции появлялись в работах НаИ [3] и Фагй [3]. 1!одробное исследование этой операции было проделано в работах Оо!ошЬ [2] и Х!ег1ег [4).
Основное внимание уделялось разрядке последовательностей максимального периода ввиду того, что все последовательности я-го порядка над полем [['е, имеющие максимальный период, могут быть получены (с точностью до сдвига) пз одной последовательности такого типа с помощью соответствующей разрядки (см, Оо!отЬ [2], Ве1тег [3, сЬ.
5]). Дальней- зтб Гл. 8. Линейные ренуррентные последовательности шее исследование свойств этой операции проводилось в работах Агаг! !1), ОцуаП, МогВсй [1], С«о!огпЬ 14, сЬ. 3, 4], Бе1гпег 13« сЬ. 5), БигЬосй, %е!пг)сЛ[ег [!], %11!е[1 [2) и Павлов, Походзе " 1! ). Если ? (х) — нормированный многочлен, не являющийся константой, над полем Ре и ) (0) чь О, то последовательность о Р 5 (1 (х)) называется характсрастическои последователь-' носгпею для !' (х), если о!«> == о. это понятие было впервые введено,„' и исследовано в работе Оо!д [1[.
В работе %1!!с[1 [4] приведены' таблицы характеристических последовательностей для примитив-, ных многочленов над полем Г,. В статье %1! !е[1 [5) доказано, что. множество характеристических последовательностей для 1(х) об. разует подпространство пространства 5 (1 (х)) и размерность этого., подпространства равняется числу различных нормированных не-:: приводимых делителей многочлена 1 (х). В работе СоМа [1] рассматривалась операция перехода от по-', следовательности з,, з,, зе ... над полем Р«к последовательности х» + з>, з, + з», з» + з,, ... сумм соседних членов. Эта операция" под названием «взятие производной» изучалась н в статье Ь]а1Лапзоп [1].
Обратная к ней операция изучалась в работах Ь)а[Лапзоп.' [11, [2], а различные ее обобщения — в работах [ча[Лапзоп; [3], ]5[. Способы разложения периодических последовательностей над полем Г«рассматривались в статьях Ншапя, ЗЛепя, Нз!еЬ [1] и %епя [1]. й 6. 11одробную сводку соотношений между .чннейными ре- ' куррентными последовательностями и ганкелевыми определите-, лями можно найти в книге Рб!уа, Бгеяо [1, зес.
Ч!1, ргоЬ. 1 1? — 29[. Теорема 8.?5 была впервые получена Кронекером (Кго. пес]сег [4)) для последовательностей над полем действительнмд,."[~ чисел, но его доказательство справедливо для любого пол[[;;:,д Другие варианты теоремы Кронекера можно найти в раба г]'Осаяпе [1], МаШе1 [1] и РегНп [1].
Обсуждение этих детер нантных критериев можно также найти в работах 1.йпеЬ [2, сЛ. 26],$е!гпег 13, сЛ. 4] и Тйг11!е11 [3]. Алгоритм Берлекэмпа — Месси был получен в работах Б лекэмпа (Вег!ейатр [4]) и Месси (Маззеу [4]) в связи с одной дачей из теории кодирования (см. 9 2 следующей главы и комм тарии к нему в конце главы). Бартон (Вцг1оп 11)) упростил э алгоритм для случая поля Р при четном д. В статье Вег!ейа«пр Ргебисйзеп, Рго1о [11 отмечено, что в то время как любых 2Й ;:", последовательных членов однородной линейной рекуррентной 1 последовательности над полем ]р«, имеющей минимальйый многочлен степени я ) 1, будет достаточно для определения минимального многочлена.
никакого числа членов, меньшего 2гг, не будет достаточно для его определения при условии, что д ~ 2. Если же о = 2, то 2й — 1 членов иногда может быть достаточно ' для определения минимального многочлена, но 2й — 2 никогда не , Комментария 577 будет достаточно. Дальнейшие замечаиия по этому вопросу, о[носящиеся к случаю д = 2, можно найти в работе О!Иоп, Могг!з [!). Густавсои (Оца1ачаоп [1]) оценил среднее число сложений и умножений, требуемое алгоритмом Берлекэмпа — Месси. Обсуждение этого алгоритма можно также найти в книге ВогпЛо[1, НоЛп [1, сЛ.
9], Еще ряд замечаний и ссылок по поводу этого же алгоритма можно найти в комментариях к ч 2 следующей главы. $ 7. Первой работой, посвященной распределению элементов основного поля в рекурреитиой последовательности, является работа 5сагр!з !2], в которой изучается Я (О) для линейных рекуррентиых последовательностей 2-го порядка над полем с нечетным д. Позднее в статье %агб [3[ изучалось распределение элементов в линейных рекуррентиых последовательностях 3-го порядка иад полем [[' . Случаи последовательностей более высокого порядка рассматривались в работах НаИ [3], [4[. Мощный метод тригонометрических сумм был впервые применен для исследования этих вопросов Коробовым [1).
Теоремы 8.78 и 8.8! являются частными случаями результатов Нидеррайтера (ЛИедегге!1ег [5), [6!). Оценку (8.3!) в большинстве случаев можно улучшить (см. упр. 8,66). Оценка, полученная в теореме 8.81, оказывается неулучшаемой (см. ЛИег[егге![ег [5)). Другими работами по тригонометрическим суммам такого вида являются статьи )ч!ег[егге![ег [7), [8) и Нечаев [5), [6]. Случай более общих рекуррентных соотношений рассматривался в работах ЛИег[егге!1ег [!1] и Нечаев [2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
