Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Очевидно, что г^ является периодом суммарной последовательности о - j о2.
Таким образом, минимальный период последовательности а, равный г, должен
делить произведение г\Гг, Следовательно, г можно представить в виде г =
did2i где dL и d2 - положительные делители чисел гх и га соответственно.
В частности, dxr2 является периодом последовательности о. Если ах
обозначает последовательность s0, st> а сг2 - последовательность t0, iit
.то
"Г- in-\-dlr3 - Д ¦ tn
для всех достаточно больших п. Но in+dlr3 ^ in для всех достаточно
больших п, отсюда получаем, что sn+aira - sn для всех достаточно больших
п. Следовательно,>! делит dtr2, а так как гг и г2 взаимно просты, то п
делит dx> и, значит, dx - гг. Аналогично доказывается и равенство d2 =
г2. ?
В случае конечного поля Р2 можно ввести интересную операцию над
последовательностями элементов этого поля, называемую операцией бинарного
дополнения. Так, если о-последовательность иад полем то ее бинарное
дополнение, обозначаемое через а, получается из о заменой каждого
элемента, равного 0, на 1, а каждого элемента, равного I, - на 0.
Бинарное дополнение можно рассматривать как частный случай операции
сложения последовательностей, так как последовательность а можно
получить, прибавляя к а последовательность !, !, !, ... . Следовательно,
если а является однородной линейной рекуррентной Последовательностью, то
к о является однородной линейной рекуррентной последовательностью.
Очевидно, что минимальный период д совпадает с минимальным периодом а.
Минимальный многочлен последовательности а легко можно получить из
минимального многочлена исходной последовательности а.
8.62. Теорема. Пусть о - однородная линейная рекуррентная
Последовательность над полем р2, ад - ее бинарное дополнение.
538
Гл. 8. Линейные рекуррентные последовательности
'гз
if
С--
т (а)
Представим минимальный многочлен m (а) ? F2 Iх 1 последова-
тельности о в виде т (а) = (х 4- \)hmr (а), где h 0, гщ (л*) ?
2 [a], гщ (1) - !. Тогда минимальный многочлен т (а) по-ледоеательноети о
задается формулой
(х Щ \)т (а), если h ~ 0;
гщ (х), если h i;
га (а), если й;>!.
Доказательство. Пусть е - последовательность иад полем |Г&! все члены
которой равны 1. Так как о - о + е, а минимальн многочлен
последовательности в равен х -f 1, случай h - следует из теоремы 8.57.
Если k 1, то из теоремы 8.55 вытекает^ что о - о i в ? S (т (х)). Тогда т
(а) делит т (а). Если т (М является постоянным многочленом, равным !, то
д является ну левой последовательностью и о - е, а следовательно, теорем
а этом случае справедлива. Предположим теперь, что deg (th (а))
> 0. Из теорем 8.53 и 8.55 следует, что о = a j е ? S (т (х)I - (х + !)),
и тогда т (а) делит га (а) (х + !). Отсюда для h получаем, что либо га
(х) = т (х), либо т (а) - (а 4- l)ft l гщ (х Если h > !, то о-о 4 е ? S
(th (а)), откуда следует, ч т (а) --- т (а). Если же h 1, то пусть о -
последовательное^;
од), S j, ,. ., 3
а
Щ (X) = X
k
к-I
ft ft
f- a
о
'•d
является многочленом положительной степени (случай многочлен нулевой
степени тривиален). Положим
-О, I,
"О Sn
п
Так как т (а) - (х 4- 1) тл (х) - характеристический многочля
последовательности s0, sb то легко получить, что ми+1 ~ й для всех п > 0.
Следовательно, ип = н0 для всех п 0, и тог, обязательно выполняется
равенство и0 = !, так как иначе т1 был бы характеристическим многочленом
последовательности Таким образом.
n+k
1
ft ft ft
для всех
. о?
"Т
... + а0 ~ К получаем 4""0(sn f 1) для всех п >0,
Поскольку га* (!) - ! 4 ак^
4" ^ " &h-1 4~ 0 "1"
а это означает, что гщ (а) является характеристическим мно членом
последовательности д. Таким образом, в случае h -имеет место равенство m
(а-) = тл (а), что и завершает доказ гельство теоремы.
Напомним, что S (/ (а)) обозначает множество всех одноро, иых линейных
рекуррентных последовательностей иад полем с характеристическим
многочленом /(а), где / (а) € Fg W 7!
УШ
§ 5, Семейства линейных последовательностей
539
нормированный многочлен положительной степени, Мы хотим, во-первых, найти
те целые положительные числа, которые могут встречаться в качестве
минимальных периодов у последовательностей нз множества S {/ (х)), а во-
вторых, определить, для сколь-них последовательностей из S {/ (х)) данное
число может быть
0 инима льи ьш пери одом,
Запишем многочлен / (х) в виде / (х) = xhg(x), где h >• 0 - целое число,
g (х) ? fq [х\, g (0) Ф 0. Случаи, когда g (х) является константой,
тривиален, так как тогда каждая последовательность из S (j (х)) имеет
минимальный период К Если /г !, a g (х) является многочленом
положительной степени, то, как это было показано в замечаниях, следующих
за теоремой 8.55, каждая последовательность а ? S (/ (х)) может быть
единственным образом представлена в виде о - f а2, где а* ? S (У1), ip f
S (х)). Все члены последовательности с^,. кроме, может быть, конечного
числа первых членов, равняются 0. Таким образом, минимальный период
