Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Phong 11], Robinson D. W. [2] и Selmer [3, ch. 3, 4]. Отметим в связи с
теоремой 8.19, что Грот (Groth [1]) использовал число линейно независимых
векторов состояний для введения меры сложности на последовательностях над
полем f2-Понятие характеристического многочлена и основная идея теоремы
8.21 восходят еще к Лагранжу (Lagrange [1], [5]), который получил
аналогичную теорему для линейных рекуррентных последовательностей иад
полем действительных чисел. Результат, приведенный в замечании 8.23,
хорошо известен для линейных рекуррентных последовательностей над полем
действительных или комплексных чисел (см. Jordan Ch. [1, ch. 11], Milne-
Thomson [1, ch. 13] и Маркушевнч [1]). Нетрудно заметить, что этот
результат может быть перенесен иа случай конечных полей при наличии
ограничений на кратность корней характеристического многочлена. Но и без
этих ограничений все же имеются способы получения представления в явном
виде для членов последовательности (см. Fillmore, Marx ЕЕ ]). Положим в
теореме 8.21 все равными 1. Получаемая при этом последовательность
привлекала внимание исследователей (см. Selmer Е2], [3, ch. 5], Ward 13],
[4], Wegner [2], [4]). Теорему 8.24 можно найти у ван Линта (van Lint [1,
ch. 3]), Более сложная формула справедлива для случая, когда
характеристический многочлен не имеет крат-
572
Гл. 8, Линейные рекуррентные последовательности
V* .2
' *
-Л
ных корней (см, Niederreiter [8] и упр, 8.41). Аракелов и Варщ; мов fl 1
показали, что я-й член однородной рекуррентной поел* довательности k-го
порядка над полем Fq может быть представлю в виде
.П
П
gQ (rt) s0
• * I
f gh-1 (") Sk-
.QY
1*
где gi (п) ? Fg- Здесь же изучались выражения для gi (п). Алг ритмы для
вычисления sn при больших п обсуждаются в работа Gries, Levin fl),
Miller, Brown fl ], Pettorossi 11], Pettoros&ij Burstall 11], Selmer 13,
ch. 5], Urbanek 11], Wilson, Shortt [lj Теорема 8.25 по существу получена
Уордом (Ward 15]). Резу* таты из линейной алгебры, использованные при
доказательст леммы 8.26, а именно то, что /является минимальным
миогочлеио соответствующей сопровождающей матрицы, можно найти, в пример,
в книге Hoffman, Kunze fl, ch. 7]. Лемма 8.26 и теоре
8.27 непосредственно приводят к результатам о порядке сопрово дающих
матриц как элементов группы GL (к, Fg), таким, на
№
мер, как верхняя граница ql
для порядка таких мат
полученная Гунтой (Gupta 11]). Линейные рекуррентные пос довательности,
характеристические многочлены которых являют трехчленами, изучались в
работах Goldstein, Zierler fl ], Lunn$ Pleasants, Stephens fl ], Young fl
i и Аракелов, Тененгольц 11 Кумари (Kumari [1 ]) рассматривал другой
специальный кл$ линейных рекуррентных последовательностей.
Первое детальное изучение последовательностей макси май ного периода
(называемых также пг-последовательностями вд (в электронике)
псевдослучайными последовательностями (pseu noise sequences)) было
предпринято Голомбом (Golomb 11 но там эти исследования ограничивались
случаем последовате иостей над полем F2 (см. также Golomb 12], 14, ch. 3,
4, 6], lomb, Welsh fl ]). Более глубокое исследование таких после;
вательностей над произвольным полем Fg можно найти в работ Zierler 14],
Selmer 13]. В статье Daykin, Dresel, Hilton fl ] pa сматривались
последовательности 2-ro порядка, имеющие мальиый период. Ряд работ был
посвящен эффективным методШ построения последовательностей максимального
периода (см. Ва Spittle, Liu 11 1, Eier, Malleck fl 3, Harvey fl ],
Lempel 11 ], Lempfa^ Eastman fl ], Mohrmann 11 ], 12], Scholefield fl ],
Surbock, richter 11 ]). Различные обобщения последовательностей мального
периода встречаются в работах MacWilliams, Sloane 11 Nomura, Miyakawa,1
mai, Fukuda [1], 13], Sakata 11] и Нечаев П
Построение последовательностей де Брейна с использование
последовательностей максимального периода (см. упр. 8.19) бый предложено
Маителем (Mantel 11]), см. также работу Rees П ' Существование (т, ^-
последовательностей де Брейна для прой вольных параметров т н к было
впервые доказано Мартин
1
W
¦XW
Ш
т
Комментарии
573
(Martin Ell), а частный случай m = 2 был изучен ранее в работе Flye
Sainte-Marie Ell- Последовательности де Брейна получили свое название
после появления работы de Bruijn Е1]. Другие результаты о
последовательностях де Брейна можно найти, например, в работах Arazi Е2],
Fredricksen ЕЕ 1, Fredricksen, Kessler [[], Golomb 14, ch. 6], Golomb,
Welch El), Good El], а также а обзорной статье Fredricksen Е2]. Связанное
с этим понятие кодового кольца изучали Радченко и Филиппов El J, E2J.
Другое приложение к комбинаторике последовательности максимального
периода находят в теории разностных множеств (см. определение 9.75). Эти
вопросы освещаются в работах Butson El ], Golomb 13, ch. 4]. Laxton,
Anderson [1 ], Selmer 13, ch. 6]. Работа Butson (1 ] содержит также
приложение к построению матриц Адамара (см, определение 9.86). Этой же
