Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
* \\ч
ч
?ГУ"
sSi
№
обладающий следующим свойством: нормированный многочлен положительной
степени f(x)?fp \х] является характеристичен ским многочленом данной
последовательности s0, slt ... тогда и только тогда, когда / (х) делится
на т {х).
Доказательство. Пусть Д, (л') ? Fg [х 3 - характеристический) многочлен
однородного линейного рекуррентного соотношения! которому удовлетворяет
наша последовательность, и пустьН0 (х) ф ? Fg 1х;\ - многочлен вида
(8.10), определяемый многочленом) /0 (х) и исходной последовательностью
%, slT ... . Если d (х) нормированный многочлен, являющийся наибольшим
общим де! лителем многочленов /0 (#) и Н0 (х), то мы можем записать Д,
(ж) =
= m {х) d ix), ho (#) = b (х) d (я), где m (л:), b (я) ? Fg U1. До кажем,
чтот (х) и есть искомый многочлен. Очевидно, что m (лр) нормированный
многочлен. Пусть теперь / (х) ? Fg lx] - произ* вольный
характеристический многочлен данной последователь ноети, н пусть Н (я) ?
Fg lx] многочлен вида (8.10), определи:!! емый многочленом / (#) и данной
последовательностью. Применяя ;j теорему 8!40, получаем, что для
производящей функции G {х) нашей последовательности имеет место равенство
*><*) ?(*)
г>:
*
\.W
:К
Щ
G(x)
fa (х) f* (*)
ж
• А
§ 4. Минимальный многочлен
525
где go (*) и gM- многочлены, задаваемые формулой (8 16). Следовательно, g
(.г) /о (х) - g0 (*) /* (*) и, используя (8.18), приходим к равенству
h (х) /о (х) = - x^eif (*))-'g(\/x)x6ee (/* <*" Го (1/лг) =
= - *deg {/0 U"-lg0 (I/jr) Xй** <*" /* (1/Х) = Л0 (X) / (X).
После деления обеих частей равенства на d (х) получаем
h (х-) пг (х) - b (х) / (х). Тогда в силу того, что т (х) и b
(х) вза-
имно просты, т (ж) делит / (х).
Предположим теперь, что / (х) С Fg txl - нормированный многочлен
положительной степени, который делится на т (х), т. е. f (х) = т (х) с
(х), с (х) ? F^ [х]. Переходя к возвратным многочленам, получаем /* (х)
= т* (х) с* (х). Кроме того, имеет
место равенство h& (х) т (х) = b (х) /0 (х). Отсюда, используя
соотношение (8.18), получаем
g0(x)m*{x) = -xa**V*ixrt-%(l/x)xd*" <m<*" т(1/х) =
= - xdee <т (1/х) xde" </• <*"/" (1/х).
Так как deg (b (х)) < deg (т (х)), произведение первых двух сомножителей
(включая знак минус) в правой части приведенного выше равенства является
многочленом а (х) ? F? [х]. Следовательно, справедливо равенство gu (х)
т* (х) = а (х)/о W- То-гда из теоремы 8.40 следует, что производящую
функцию G (х) нашей последовательности можно представить в виде
л /уч = &(*) а(х) _ а (*) с* (х) а (х) с* (х)
uw Г(х) т*(х) т*(х)с*(х) /• (х) '
Так как
deg (а (х) с* (х)) ^=deg (а (х)) + deg (с* (х)) <
< deg (m (х)) + deg (с (х)) = deg (/ (х)),
то из второй части теоремы 8.40 следует, что / (х) является
характеристическим многочленом нашей последовательности. Очевидно, что
существует только один многочлен т (х) с указанными свой-
Однозначно определенный в теореме 8.42 многочлен т (х) ? €F? [х],
соответствующий последовательности s," Sj, называется минимальным
многочленом этой последовательности. Если sn • 0 для всех п > 0, то
минимальный многочлен этой последовательности равен 1. Для всех других
однородных линейных рекуррентных последовательностей т (х) является
нормнрован-ным многочленом степени deg (т (х))>0 и представляет собой
характеристический многочлен линейного рекуррентного соотношения
минимально возможного порядка, которому удовлетво-
526
Гл. 8, Линейные рекуррентные последовательности
ряет наша последовательность. Другой метод вычисления мини малыюго
многочлена будет приведен в § 6 настоящей главы,
8.43. Пример. Пусть последовательность % ... являете
линейной рекуррентной последовательностью над нолем f определяемой
рекуррентным соотношением
Л
и вектором начального состояния (I, 1,0, 1). Для того чтоб найти
минимальный многочлен этой последовательности, будещ действовать так же*
как при доказательстве теоремы 8.42. Мо жно взять
!л
V
/о (*)
X'
1
V".
Тогда из (8.10) следует, что /?0 (х) = х3 -f х. Наибольший общи делитель
многочленов /" (х) и Л0 (х) равен d (х) = х2 + 1. таким образом,
минимальный многочлен последовательности ^ ... равняется т (х) - /0 (x)/d
{х) = хг + х + 1- Легко про;
s
х>
верить* что наша последовательность удовлетворяет лииеином рекуррентному
соотношению
" ^П+1 + ^71" Я (tm) 0, 1 ,
#
что находится в соответствии с общей теорией. Заметим, ч ord (т (х))
равен 3 и совпадает с минимальным периодом наш последовательности (ср. с
примером 8.41). В теореме 8.44 мы пока*
жем, что это справедливо и в общем случае.
1/-
Минимальный многочлен играет ведущую роль при определен нии минимального
периода линейной рекуррентной последовав тельности. Это видно, например,
из следующего результата
8.44. Теорема. Пусть s0, si( ... - однородная линейная ре* куррентная
последовательность над полем fg с минимальным мшщ гочленом т (х) ? Fq
[х\. Тогда минимальный период этой пд~: следоватвльности равняется ord (т
(х)). ',4
