Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
изучалось распределение минимальных периодов для случая линейных
оекуррентных соотношений над Z/(m). Вопрос, какие значения может
принимать минимальный период линейной рекуррентной последовательности k-
ro порядка над полем Fg при фиксированных k и щ, изучался в книге
Luneburg [2, ch. 32, 33].
Тот факт, что в результате почленного умножения линейных оекуррентных
последовательностей получается снова линейная рекуррентная
последовательность, был отмечен еще в статье FOeagne [1], где
исследовались последовательности действительных чисел и был доказан более
слабый вариант теоремы 8.67, а именно, что для этого случая
S(/iW) S (Л* W) s S (М*) v ... v/*(*)).
Для конечных полей операция почленного умножения последовательностей
впервые изучалась в книге Selmer [3, ch. 4]. Болес тщательное
исследование этого вопроса было проделано в работе Zierler, MiHs [ 1 ]>
где были получены теоремы 8.67 и 8.72. В этой же работе было показано,
как использовать полученные результаты для нахождения многочлена g (х) из
теоремы 8.65 в общем случае. Взаимосвязь между множествами S (/ (х)) и S
((/ (х))А) изучалась з статье Fillmore, Marx [1]. Некоторые элементарные
замечания относительно операции почленного умножения последовательностей
содержатся в работе Brousseau [1]. В статье Furstenberg 11] получен
аналог следствия 8.66 для более общих типов после-довательностей над
полем fq.
Операция над последовательностями, называемая децимацией (decimation) или
разрядкой, была предложена Голомбом (Golomb (И) и определяется следующим
образом: если а - последовательность элементов s0, sb s2, ... из поля Fg,
a d ? N - натуральное число, то разреженная последовательность a(d)
состоит нз членов s0, sd, s2d, ..., т. е. cfH) получается путем выбора
каждого d-ro члена исходной последовательности а, начиная cs0, Частные
случаи этой операции появлялись в работах Hall [3] и Ward [3]. Подробное
исследование этой операции было проделано в работах Golomb [2] и Zierler
[4]. Основное внимание уделялось разрядке последовательностей
максимального периода ввиду того, что все последовательности k-ro порядка
над полем Fg, имеющие максимальный период, могут быть получены (с
точностью до сдвига) из одной последовательности такого типа с помощью
соответствующей разрядки (см. Golomb [2], Selmer [3, ch. 5]). Дальней-
576 Гл. 8. Линейные рекуррентные последовательности
К-Й!
Vi
i
*> * Я
•р?
шее исследование свойств этой операции проводилось в работа^ Arazi 11],
Duvall, Mortick [1|, Golomb [4, ch. 3, 4], Selmer Щ ch. 5], Surbock,
Weinrichter [1], Willett [2] и Павлов, Походзе# т. Вели f (х) -
нормированный многочлен, не являющийс константой, над полем fqnf (0) Ф 0,
то последовательности ст ? S (/' (х)) называется характеристической
последовательif
частью для f (х), если - ст. Это понятие было впервые введен и
исследовано в работе Gold [1]. В работе Willett [4] ириведенц-таблицы
характеристических последовательностей для примитив^ ных многочленов над
полем р2- В статье Willett [5] доказано, что множество характеристических
последовательностей для / (х) образует подпространство пространства S (/
(х)) и размерность этого подпространства равняется числу различных
нормированных не^| приводимых делителей многочлена / (х).
В работе Goka [1] рассматривалась операция перехода от по
еледовательноети s0, slt s2, ... над полем р2 к последовательности s0 f
sb ^ f Sj, s2 + sg, ... сумм соседних членов. Эта операция под названием
"взятие производной" изучалась и в статье Nathanson {1]. Обратная к ней
операция изучалась в работах Nathanson ИЗ, 12], а различные ее обобщения
- в работах Nathanson s
[3], 15J. Способы разложения периодических последовательностей над полем
р2 рассматривались в статьях Hwang, Sheng, Hsieh 11] и Weng [1].
§ 6. Подробную сводку соотношений между линейными рекуррентными
последовательностями и ганкелевыми определителями можно найти в книге
Polya, Szego [ 1, sec. VII, prob-17-29]. Теорема 8.75 была впервые
получена Кронекером (КщМ пескег [4]) для последовательностей над полем
дейетвительй|р|| чисел, но его доказательство справедливо для любого
noi||j|| Другие варианты теоремы Кронекера можно найти в работу" d'Ocagne
[1], Mai 1 let [1] и Perrin [1]. Обсуждение этих детер нантных критериев
можно также найти в работах Ltinebi [2, ch. 26],Selmer [3, ch. 4] и
Willett [3].
Алгоритм Берлекэмпа-Месси был получен в работах Б лекзмпа (Berlekamp [4])
и Месси (Massey [4]) в связи с одной дачей из теории кодирования (см, § 2
следующей главы и комм тарни к нему в конце главы). Бартон (Burton {1 3)
упростил эт$ алгоритм для случая поля Ff/ при четном q. В статье
Berlekamp; Fredricksen, Proto 11 j отмечено, что в то время как любых Ш
последовательных членов однородной линейной рекуррентной
последовательности над полем SFfr имеющей минимальный мно- | гочлен
степени 1, будет достаточно для определения минимального многочлена,
никакого числа членов, меньшего 2k, не будет достаточно для его
