Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
видно, что т (х) зависит только от первых членов последовательности s0(
slt ... , Следователь но,
изводящую функцию G (х) в алгоритме можно заменить мно членом
§ 6. Характеризация линейных последовательностей 551
8.76. Пример. Первые 8 членов однородной линейной рекуррентной
последовательности над полем f9 порядка к С 4 имеют
вид
4, 2, 1, О, 1, 2, 1, 0. Для того чтобы найти ее минимальный многочлен,
применим алгоритм Берлекэмпа - Месси с многочленом
G? (х) - 2х 4 х* + х4 + 2л4 -f х9 ? (F3 [х]
вместо производящей функции G (х). В следующей таблице приводятся
промежуточные результаты, полученные в процессе работы алгоритма.
/ < tj (*> v*> т. *г
0 1 X 0 0
I I X2 1 2
2 1 h 2х 1
3 1 - х - Ьх2 2х3 0 0
4 1 - ~ X ~ - X2 2х3 1 2
5 1 + х - L Xs 4- 2Х2 2х 4~ 2х2 4- 2т3 -1 2
6 1 4- х3 2ха 4- Зх3 + 2х4 0 1
7 1 - х8 4~ 2Х34- х4 х 4- х4 0 1
8 ¦ ¦"-" - 2х 4* х2 4- 2х(r) 0
В этом случае г - |_4 -f 1/2 - m8/2j - 4 и, следовательно, т (я) - х* +
+ х2 + 2х. Таким образом, линейное рекур-
рентное соотношение наименьшего порядка, которому удовлетворяет данная
последовательность, имеет вид
^п+4 ~ sn+g -j- 2sn+2 4" ^п+1" - 0, 1, ... . Q
8.77. Пример. Найдем однородную лниейную рекуррентную последовательность
наименьшего порядка над полем fa, первые 8 членов которой - это 1, I, 0,
0, 1,0, 1, 1. Применим алгоритм Берлекэмпа - Месси, используя многочлен
G7 (х) = I 4~ х + х* + ~ Xе 4" х7 ? Fs lx] вместо производящей функции G
(х). Этапы вычисления приводятся в следующей таблице.
" / Sj (*) kj {*) т.
0 1 X 0 1
1 1 4-. х X 0 0
2 1 4- х X3 1 1
3 1 4- х -f X2 х 4- х2 - 1 1
4 1 х2 4- х3 0 1
5 1.4- ха 4~ х3 X 0 0
6 1 ^ Ь х2 Ь х3 X2 1 0
7 1 - - х8- - X3 X3 2 0
8 1 - L X2 L X3 3
552
Гл, 8. Линейные рекуррентные последовательности
В этом случае г -¦ J_4 4- Ь;2 - щ/2J - 3 и, следовательн т (а) ~ х3 4- л'
-j- 1. Таким образом, заданные элементы образу^ начальный отрезок
однородной линейной рекуррентной по довательности s0, slf ... ,
удовлетворяющей рекуррентному соа ношению sn+3 = srl+l 4~'s", п = 0, 1,
... , и не существует реку ! рентной последовательности меньшего порядка,
имеющей тот начальный отрезок.
Докажем теперь в общем случае, что после конечного чн шагов алгоритм
Берлекэмпа - Mecca приводит к искомому мтЩ мольному многочлену. Для этого
введем вспомогательные мной члены uj (х), Pj (а) € F7 (*1. Определим их
следующими рек р е нт м ыми фор м у л а м и:
М,
и(} (а) 0, v0 (х)
Hj+1 (х) = Uj (X) - bjVj (X),
- 1
.*1?
."1.
(8.2
V
(х) -
hi xuj(x), еслн hi Ф 0, m/> О, (8.2L
ат>; (а)
в противном случае
для всех / 0, 1, ... , Мы утверждаем, что для всех />
О
..-ч •
•4 д
i
deg (gj (a)) < ~7(i - 1 mf)t deg (A, (a))
(/ 4~ 2 ~r %)* (8.^
Ь ч
•Д
Для 0 это очевидно ввиду (8,19), Если неравенства (8. доказаны для
некоторого /> 0, то нз (8,20) следует, что в случс, когда bj Ф 0, rrij >
0,
deg (gj,i (¦*>) < max (deg (gj (x)), deg (A, (*))) <
"у (/ 'h 2-4- mi) ' - ~2 (i 4' 2 - mj+г).
В противном случае
deg (gj+i (A)) < 4- (j f 1 trij) 4 (7 4- 2 - ш
¦ 4-f .•Щ,
¦Д
;+ij
).
2 'j f ' "Т/ 2
Второе неравенство в (8,23) доказывается аналогичным образа: Индукцией по
/ можно также доказать, что для любого /> выполняются неравенства
d / "-*
. Д.
deg (иу (а)) < у (/ -- 1 от/j, deg (ty (a)) < у (/ 4 ms). (8.
5:: hP
Для всех / Дз 0 вспомогательные многочлены Uj (х) и Vj (х) заны с
многочленами gj (а) и hj (а) следующими соотношениями
gj (a) G (а) = uj (а) 4- bixi (mod аД-1). (8
hj (a) G (a) = vj (a) j- x1 (mod x<; r). (8
§ 6. Характеризация линейных последовательностей
553
В самом деле, для /= 0 (8.25) и (8.26) следуют из (8.19), (8.21) и
определения константы 50* Предполагая, что соотношения (8.25) и (8.26)
доказаны для некоторого />0, получаем
gH 1 lx) G (дг) = gj (X) G (x) - bjhj (x) G (x) =
= Uj (x) + bjX> + c^1x'+' - bj (Vj (x) + x> + d,+iX'+') =
= Uui M + (m°d x*+2)(
*
где cJ+lt dJ+lt e*+1 ? Fg - некоторые подходящие коэффициенты. Поскольку
[как это можно показать но индукции, то из (8.24) получаем deg (uj+i (я))
< /. Таким образом, является коэффициентом при х1 ^ в g;+1 (х) G (х) и,
следовательно, 0+1 " ^J+i- Соотношение (8.26) для / > 0 доказывается
аналогичным образом.
Далее, по индукции легко доказать, что* для всех / ^ О
hj (х) щ (х) - gj (х) vj (x) = xL (8.27)
Пусть теперь s (x), и (x) - многочлены над полем Fy, связанные
соотношением s (х) G (х) = и (х) и условием s (0) - I. Тогда нз (8.26)
следует, что
hj (х) и (х) - s (х) Vj (х) ~ s (х) (hj (х) G (х) - Vj (х)) =
= s (х) х/ = xj (mod х'-И),
и тогда для некоторого Vj (х) ? Fa fx] получаем
hj (х) и (х) - s (х) Vj (х) = xjUj (х), где Uj (0) = I. (8.28)
Аналогично, пользуясь (8.25), можно показать, что существует Vj (х) ? F(/
fx], для которого справедливо равенство
gj (х) и (х) - s (х) Uj (х) = xtVj (х). (8.29)
Предположим теперь, что минимальный многочлен m (х) данной однородной
линейной рекуррентной последовательности удовлетворяет условию deg (m
