Научная литература
booksshare.net -> Добавить материал -> Физика -> Лидл Р. -> "Конечные поля. Том 1" -> 229

Конечные поля. Том 1 - Лидл Р.

Лидл Р., Нидеррайтер Г. Конечные поля. Том 1 — М.: Мир, 1988. — 430 c.
ISBN 5-03-000065-8
Скачать (прямая ссылка): konechniepolya1988.djvu
Предыдущая << 1 .. 223 224 225 226 227 228 < 229 > 230 231 232 233 234 235 .. 371 >> Следующая

(х)) k. Пусть s (х) будет соответствующим возвратным минимальным
многочленом. Тогда 5 (0) = 1, deg (s (jc)) <Н из (8.15) мы
получаем, что существует многочлен и (х) ? Fg fx], для
которого выполняются соотношения
s (х) G (х) = и (х) и deg (и (х)) ^ deg (m (х)) - 1 ^ k - 1. Положим в
(8.28) /= 2к. Воспользовавшись (8.23) и (8.24), получаем
deg (h%k (х) и (х)) < -i- (2k + 2 -J- m2k) + k - 1 = 2k |-
deg (s (x) v%k (x)) < k -f -j- (2k + m2fe) = 2k f -j m2k,
откуда
deg (Ьгк (x) и (x) - s (x) v2h (x)) <26 + 4 m*h'
554
Гл. 8. Линейные рекуррентные последовательности
. ;ъЩ
С другой стороны,
deg (h2k (х) и(х}-$ (х) v2k (дг)) =* deg (x2kU2k (л-)) > 2k,
и все эти неравенства совместимы лишь при т2к > 0. Вновь в пользовавшись
соотношениями (8.23) и (8*24), нетрудно про рнть, что deg (g2k {х) и (х))
< 2k - 1/2 - (1/2) m2k и deg (5 * u2k (*)) С - 1/2 - (1/2) m2k. Тогда из
(8.29) вытекает, Щ
deg (x2kV2k (х)) = deg (g2h (x) и (x) - s (x) u2h (дг)) < 2k.
Но это возможно лишь при условии, что V2h (х) является нулев многочленом.
Следовательно, из (8.29) вытекает, что^ (х) и (х)
= s (х) и2к (х). Полагая / = 2k и умножая обе части равенст (8.28) и a
g2h (х), приходим к равенству
thk (*) g2h (х) u(x)-s (х) g2h (x) v2h (x) =
- s (x) (Aah (x) u2k (x) ~ g2h (x)v2h (x)) = x2kU2k (x) g2h (j.
Учитывая (8.27), получаем s (x) = U2it (x) g2h (x), откуда вы кает, что и
(х) = U2h (х) и2к (х). Так как s (х) является возврат иым минимальным
многочленом, из второй части теоремы 8 следует, что многочлены s (х) и и
(х)-взаимно просты. В силу это многочлен U2h (х) обязан быть константой,
а так как по (8. U2k (0) = 1, то и2к (х) = 1. Значит, s (х) - gu (х)
и соотв
ственно и (х) - и2к (х). Если deg (m (х)) - k, то
М = (-
X
как и утверждалось ранее. Если же deg (т (х)) = t ^ k, то s (х)
- (х)> и (х) u21 W* msi > G* Очевидно, что max (deg (s (x]
1 + deg (и (дг))) < t, и из второй части теоремы 8.40 вытек;
t = шах (deg (s (х)), 1 + deg (и (х))).
т (х) = xbs (-j- ) = xkg2k
Тогда из (8.23) и (8.24) следует, что
t == max (deg (g2i (x))t 1 4- deg (un (x))) < t -|
If
,'W
2
1
У
Is
m2i.
Таким образом, равно 0 или 1. Кроме того, заметим, gj (х) - s (х) и Ь} =
0 для всех //> 2L Тогда т} - + /
- 2Гдля всех j 1> 21 по Определению nij. Полагая j - 2k, пол] чаем t - k
+ (1/2) m2* - (1/2) тш, н так как т2% или 1, то
. , 1 1
равняется
•>}%
t
т.:
= г.
Таким образом,
а
т (х) = xrs
1
X
(4-) ¦
Чш
* А
т
что соответствует нашему утверждению.
" * :
§ 7. Распределение элементов
555
§ 7. Распределение элементов в линейных рекуррентных последовательностях
В этом параграфе нас будет интересовать следующий вопрос сколько раз
встречается тот или иной элемент поля на том или ином отрезке линейной
рекуррентной последовательности над полем Тя. Для получения общих
результатов в этом напраа лении займемся сначала детальным изучением
свойств тритоне метрических сумм, связанных с линейными рекуррентными по
следовательностями. Тогда станет очевидным, что в случае ли нейных
рекуррентных последовательностей с большим миннмаль ным периодом на любом
отрезке последовательности, составляю щем ее полный пернод, а также на
отрезках, являющихся суще* ственной частью полного периода, элементы
основного поля ветре чаются приблизительно с одинаковой частотой.
Пусть Sq, ... - линейная рекуррентная последовательность k-го порядка над
полем Тя, удовлетворяющая соотношению (8.1) Пусть г - минимальный период
этой последовательности, а п0 -¦ ее предпернод, т. е. sn+r - sn для всех
п яа. Свяжем с этой последовательностью целое положительное число R,
определенное следующим образом. Рассмотрим рекуррентную
последовательность, являющуюся импульсной функцией и удовлетворяющую
соотношению (8.6). Пусть гг - минимальный период этой последовательности,
a я* - ее предпернод. Положим тогда R = гг + я*, Разумеется, R зависит
только от линейного рекуррентного соотношения (8.1), а не от конкретного
вида последовательности Sq, $1у ... Если sfl, Si, ... является однородной
линейной рекуррентной последовательностью с характеристическим
многочленом f М G Fqlx], то rt - ord (f (д:)), а если, кроме того, j (0)
Ф 0, то по теореме 8.27 R - ord П (х)). По той же теореме в однородном
случае г делнт г1 и г R.
В тригонометрических суммах, которые мы собираемся рассматривать, будут
использоваться аддитивные характеры поля Fч, изучавшиеся в гл. 5, которым
будут приписаны веса, определенные с помощью функции е (t) = е2я(/, где t
- действительный аргумент.
8.78. Теорема. Пусть s0, s,, ... - линейная рекуррентная
последовательность k-го порядка над полем г - ее минимальный период, а п0
- пред пер иод. Пусть, далее, R - целое положительное число, определенное
выше. Если % - нетривиальный аддитивный характер поля ш для любого целого
числа h справедливо
неравенство.
u-f~f-1
для всех и п0. (8.30)
556
Гл. 8. Линейные рекуррентные последовательности
• А
В частности,
цЛ~г-|
У
JmJ
tl^U
Предыдущая << 1 .. 223 224 225 226 227 228 < 229 > 230 231 232 233 234 235 .. 371 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed