Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
такое, что Е?^'И) - 0 для всех п > т. Если D(nJ = 0 для не;
торого > т, то по лемме 8.73 D{nk) = 0 для всех п >
противоречит выбору &-f I. Следовательно, D("fe) ф 0 для вс п > т.
Положим s" ^ (sB, sB+i5 ..., sn+k). Заметим, что для в м > m векторы sft,
s"+1, ..., sn+fc, будучи строками определ
теля Е>^+|) = 0, линейно зависимы иад полем fq. В силу '
что Ф 0, векторы s", линейно незавне
над §q, и, значит, является линейной комбинацией вектор
nQ, W
¦¦¦* *п+й~1* Но индукцин легко получить, что для вс; п т вектор s",
является линейной комбинацией векторов Щ W- Sm+fe-i. Последние
представляют собой k векторов п]
странства F
H-t
а следовательно, существует ненулевой векг^
(й0, аи , аь) С Fjfl, для которого выполняются равен
+ a\sn+i Ь ' ^' Д- ahsn+h = Q Рри т < п < т + к - Ь ш
§ 6. Характеризация линейных последовательностей
549
Отсюда вытекает, что
I ft
4- aks
n±k
О для всех m
или
По^и+?п ~f~ ^l^a+m+l * * * 4" &к^п+т+к ~ ^ ДЛЯ BC6X tl ^> 0.
Таким образом, показано, что последовательность s*, ... удовлетворяет
однородному линейному рекуррентному соотношению, имеющему порядок не
более чем т + к, П
8.75. Теорема. Последовательность s0, sx, ... элементов из поля Fq
является однородной линейной рекуррентной последовательностью с
минимальным многочленом степени к тогда и только
тогда, когда Dor) - 0 для всех г к 4~ I и k 4 1 - наименьшее натуральное
число, для которого выполняется это равенство.
Доказательство. Докажем необходимость. Если данная рекуррентная
последовательность является нулевой последовательностью, то необходимость
условий очевидна. В случае когда последовательность отлична от нулевой,
мы имеем k 1, и тогда Dor} ~ 0 для всех г > k 4- 1, так как (к 4~ 1)-я
строка определителя
Don является линейной комбинацией первых к строк. В свою
'очередь нз теоремы 8.51 следует, что Dofe) ф 0. Таким образом,
необходимость условий доказана для всех случаев.
Для доказательства достаточности допустим, что выполняются приведенные
условия для ганкелевых определителей. Пользуясь
леммой 8.73, индукцией по п можно показать, что D{P ~ 0 для
всех г > & 4-1 и всех п > 0. В частности, Dn+l) - 0 для всех п > 0, и
тогда по теореме 8.74 последовательность ... яв-
ляется линейной рекуррентной последовательностью. Если ее минимальный
многочлен нмеет степень^, то, как мы уже показали
выше, В(р - 0 для всех г ^ d + 1 и + 1 является наименьшим натуральным
числом, для которого выполняется это равенство. Отсюда получаем, что d =
к. ?
Если известно, что однородная линейная рекуррентная последовательность
имеет минимальный многочлен степени к 1, то сам минимальный многочлен
полностью определяется первыми 2к членами этой последовательности. Чтобы
убедиться в этом, запишем уравнения (8.2) для п - 0, 1 к - I и получим
систему из k линейных уравнений относительно неизвестных а0, аь
являющихся коэффициентами искомого минималь-
но многочлена. Определитель этой системы равняется D(0k\
м по теореме 8.51 D\ьк) Ф 0. Таким образом, рассматриваемая система
уравнений нмеет единственное решение.
550
Гл. 8. Линейные рекуррентные последовательности
Важным вопросом является нахождение практического метод для вычисления
минимального многочлена данной однородно линейной рекуррентной
последовательности. Один такой мето уже был предложен в процессе
доказательства теоремы 8.4 Этот метод предполагает предварительное знание
характерист ческого многочлена данной последовательности н основывает на
нахождении наибольшего общего делителя многочленов полем Ниже мы приведем
и обсудим другой метод нахожденц минимальных многочленов. Этот метод
представляет собой реку сивный алгоритм (так называемый алгоритм
Берлекэмпа -который после конечного числа шагов дает искомый минимально
многочлен при условии, что нам заранее известна верхняя гр ница для
степени искомого минимального многочлена.
Пусть s0t slt ... - последовательность иад полем fq и G (х)
оо
-- 2 -V" -
п=0
0, lf ... определим многочлены gj (х), hj (х) ? F(/ fx], цел числа ntj и
элементы bj ? fq следующим образом. Для / = полагаем
gQ (х) - 1, ho (х) == х, т0 - 0. (8.1
Затем последовательно полагаем bj равным коэффициенту п х/ в gj (х) G (х)
и
8иг W = gj (х)
_ | t>T'xgi(x),
соответствующая производящая функция. Для /
faj+l (*^)
bjhj (х),
если Ь]ф0, т}
0,
xhj(x) в противном случае,
(8.
т
j+i
-Ш}у
Щ h 1
если bj^O, mj > 0, в противном случае.
Если s". s
О" 'Н 9
ri ( <
однородная линейная рекуррентная послед
вательность с минимальным многочленом степени k, то в резулй тате мы
получим, что g2h (х) равняется возвратному мннимал^ ному многочлену.
Таким образом, искомый минимальный MHorgj член т (х) определяется
равенством т (х) - xkg2h (1/х). Ес заранее известно лишь, что deg (т (х))
< k, то положим г ~ [А + 1/2 - m2ki2j, где (_#J означает наибольшее целое
число, й! превосходящее у. Тогда минимальный многочлен т (х) опред ляетея
равенством т (х) = xrg2k (1/х). В обоих случаях из ал г ритма сразу же
