Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
0 для
всех л - О, I, образует идеал в кольце Fg \х]. Вывести отсюда, что суще-
; ствует однозначно определенный минимальный многочлен рекуррентной
последовательности.
8.26. Рассмотрим линейную рекуррентную последовательность над полем F2
определяемую рекуррентным соотношением sn+n + Sn+s + sri) n =*
= 0, 1, и начальными значениями s0 = % = s4 = sg = s" ~~ 0, st (tm) s2 =
= $7 - 1. Используя метод доказательства теоремы 8.42, найти минимальный!
ш
многочлен дайной рекуррентной последовательности.
8.27. Рассмотрим линейную рекуррентную последовательность над полем Fg.
определяемую рекуррентным соотношением s^-h ~~ 3%+2-s?i+i "Т snr п = 0,
1, и начальными значениями Sq - sA - s2 1, s3 ~ -I. Используя метод
доказательства теоремы 8,42, найти минимальный многочлен данной
рекуррентной последовательности.
8.28. Показать, что однородная линейная рекуррентная последовательности;
над конечным полем является чисто периодической последовательностью
тогда! и только тогда, когда ее минимальный многочлен т (х) удовлетворяет
условию т, (0) ф 0.
8.29. Пусть дана однородная линейная рекуррентная последовательность! над
конечным полем и т (х) - ее минимальный многочлен. Доказать, что длина
предпернода данной последовательности равняется кратности элемента 0 как
корня многочлена т (х).
8.30. Доказать следствие 8.52, используя способ построения минимального ;
многочлена, приведенный в доказательстве теоремы 8.42.
8.31. Пользуясь критерием, полученным в теореме 8.51, найти минимальный ;
многочлен линейной рекуррентной последовательности над полем F2s задава-
. емой рекуррентным соотношением sn+fi - sR+3 -f sn+2 4- sn+1 ~j~ sn, n=
0, I, и вектором начального состояния (1, 1, 1, 0, 0, 1).
8.32. Найти минимальный пернод линейной рекуррентной последовательности
из упр. 8.26.
8.33. Найти минимальный период линейной рекуррентной последовательности
из упр. 8.27.
8.34. Найти минимальный период линейной рекуррентной последовательности
над полем Г2, задаваемой рекуррентным соотношением + sR+4 -f- sn+! -f sn,
n - 0, I, и начальными значениями - xe - s7 - 0, s3 - s4 - s5 - % - 1.
8.35. Найти минимальный период линейной рекуррентной последовательности
над полем F3, заданной рекуррентным соотношением sn +& = sn4.4 - sn+3 +
4" ?п+з + ft- 0, 1, и начальными значениями Sq - ¦ st ~ 1, s2 - s3 - 0,
Si = - I.
8.36. Найти минимальный период линейной рекуррентной последовательности
над полем F3) определяемой рекуррентным соотношением sn4.4 -- sn+3 ¦+
+ -.% - U п - 0, 1, .... и вектором начального состояния (0, -I,
1,0).
8.37. Доказать, что линейная рекуррентная последовательность k-ro порядка
ц, sb ... над полем Fg имеет минимальный пернод, равный } только в
следующих случаях?
5ХЯ
ь
чД"
ч
•' tt
= Sn+7"h So = Si = s2 =
I
Упражнения
583
(a) k = I, q - простое число, sn+i = sn + a, ft - О, I, ..., а ? F*;
(b) ft - 2, ? - 2, %+2 = sn + 1, ft = 0, I.......
8.38. Пусть дана однородная линейная рекуррентная последовательности над
полем Fg н т (дг) ? Fg [д:] - ее минимальный многочлен, отличный от
константы. Пусть корни этого многочлена отлнчкы от нуля н не являются
крат кымн. Доказать, что минимальный период данной последовательности
равен такому наименьшему натуральному числу г, при котором выполняется
равенство
а? I для всех корней а многочлена m (х).
8.38. Доказать, что еслн однородной линейной рекуррентной последова
тельностн о над полем Fg соответствует минимальный многочлен / (х) ? Fg
[х и fieg (f (4) = п > I, то любую последовательность нз множества S (f
(лг)) можно единственным образом представить в виде линейной комбинации
исходной после
довательности a=o(0J н последовательностей о(1), о(2\ полученных
с помощью сдвигов исходной последовательности а, с коэффициентами из поля
Fg-
в. 40. Пусть fi (х), ..., fh (х) - попарно взаимно простые нормированные
многочлены над полем Fg, не являющиеся константамн. Показать, что
простратт ство 5 (/* fx) ... fk (х)) является прямой суммой линейных
подпространств
S (/,(*)).
8.41. Пусть So, ... - однородная линейная рекуррентная последователь-
iгость над полем Л" ~ IFg, a f (лг) - ее характеристический многочлен.
Пусть f (*) - fi(x) ... fr (х), где fi fx) - различные нормированные
неприводимые многочлены над полем К. Пусть, далее, сс* (с = \, ..., г)
является фиксированным корнем многочлена /* (х) в его поле разложения F*
над К- Доказать, что существуют однозначно определенные элементы 8* ? Flt
..., Qf ? Fr, для которых выполняется равенство
8.42. Пользуясь обозначеннями, введенными в упр. 8.41, показать, что /
fx) является минимальным многочленом последовательности Se, $i, ... тогда
и только тогда, когда 0* Ф 0 для всех i - I, ..., г. Получить отсюда, что
число последовательностей в S (f (х)), минимальным многочленом которых
является
/ (х), задается формулой (9*1- l).,. {д*г~ l), где А* = deg (Д fx)), ( -
1, .... г,
8.43. Пусть Oj и о2 - последовательности, порожденные импульсом, над