Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
минимальный многочлен, то другой метод, основан ный на суммах Гаусса,
приводит к несколько лучшим оценка?
В приводимом ниже доказательстве мы воспользуемся формулам для сумм
Гаусса из теоремы 5.11.
8.84. Теорема. Пусть s0, Sj, ... ¦- однородная линейная реку рентная
последовательность над полем и г ее минимальны! период. Предположим, что
.минимальный многочлен этой поелЩ дова тельное та т (х) является
неприводимым многочленом степей* k над полем fq и при этом удовлетворяет
условию т (0) Ф '.05
\7.
¦Ш
Пусть Н
2(0)
наименьшее общее кратное чисел г и q - 1, Тогда
1 )г
1
Ч
.к
q^.
фЩ
дЗ
%'!¦
а при Ь Ф 0
г(ь) -
h-1
Я r
qk - 1
С
г
J
q* - I
k
1/2 \ n{k!2)-\
(8.381
/<т
Доказательство. Положим К 2 Ffjf, и пусть F - поле разл* жени я
многочлена т (х) над полем Д\ Пусть а ? F - коре*
§ 7. Распределение элементов 563
многочлена т (х); тогда афО, так как т (0) Ф 0. По теореме 8.24 найдется
0 ? F, такой, что
sn ^TrF/K(Qa")> п ~ 0. 1, ... . (8.39)
Очевидно, что 0=^=0. Пусть V - канонический аддитивный ха-
рактер поля К (см. (5.6)). Тогда из соотношения (5.9) вытекает, что для
любого фиксированного элемента Ь ? К
I f h если sn = Ь,
- У V (с (Ь - sn)) = Л ^ .
Я ^ и [0, если ВпфЬ,
с? к
что вместе с (8.39) дает
г-I
2 <*>=-j 2 2 vфс) (Ttf,k
е ? к
Если X обозначает канонический аддитивный характер поля F, то У и X
связаны между собой равенством X' (Тг/?/^ (Р)) - X (Р) для всех р ? F
(см. (5.7)). Таким образом,
г- 1
2 (о=12х' <*> 2 ^с9а")
с е к о
г-1
X' (&с) X (c0att). (8.40)
с ? л*
п=О
В силу (5.17)
Я (r) = 7ГГ7 2 0^ Ч+(Р).
где р ? f *, а суммирование производится по всем мультипликативным
характерам ф поля F. Для элемента с ? К* получаем
г-1 г-1
^ х ("е"") = -Д-J- 2 2 G tt. Ч ч> (<#"")
л-0 гг-0 ф
г-i
I
2 4 (С0) О (4, Я) 2 4'(а)'1.
Внутренняя сумма в последнем выражении является суммой членов
геометрической прогрессии. Она равняется нулю, если ф (а) Ф ^ 1 в силу
того, что ф (а)г = ф (аг) - ф (1) = 1. Таким образом,
504
Гл. 8. Линейные рекуррентные последовательности
нам необходимо суммировать лишь по множеству У, состоящем из всех таких
характеров ф, для которых ър (а) = 1. Поэтому
Г
-- ^ т (св)G • 5-
X (с(r)ап)
ж
%¦
I
I
Подставляя это выражение в (8.40), получаем
Z (Ь = )-
Я , q(tf ~ I)
4'(сВ)0(ф, Я)
"'¦'Л
•H-V-
.lO
с ? К
"к
Г
Я
q (qk - \)
^ф(8)0(ф, X) ^ ф(с)Х'(6с).
: Г5/. !
Я*
л?.'
1Р G л с е х*
Если через ф' обозначить ограничение характера ф на К*t то вну| треннюю
сумму можно рассматривать как сумму Гаусса па полем К с аддитивным
характером Х'ь (с) = X' (Ьс) для с ? Тогда
Z(h)
.д
№
Пусть теперь b 0. Еслн Х'ь является тривиальным аддитц ным характером
поля К, то сумма Гаусса G (ф', Щ обращает^ в 0 во всех случаях, кроме
случая, когда ф' является тривиальн характером, В последнем случае G (ф\
Ц) - ц- 1. Следов тельно, нмеет смысл брать сумму в (8.41) по множеству
Л, сос ящему из всех таких характеров ф, для которых ф (а) - 1 и является
тривиальным характером. Тогда
{q~ 1 )г
I
Z(0)
я
(/-1)
т,
I:
• '№• •, -Mr
Тривиальный мультипликативный характер дает в сумму вклад равный -Г и,
следовательно,
Z (0) -
(4*-' -1)
г
Я1
I
(д - 1) г
</(?*- I)
^ ф (0) G (ф, X),
¦'Ж
-Ж : 'Ш
hk
• -tv
где звездочка означает, что тривиальный мультипликативны^ характер
исключен из области суммирования. В силу того, что
является нетривиальным характером, получаем, что | G (фт Х)| :
qk?2 для любого нетривиального ф. Отсюда
Ж 1
Z( 0)
(?
к-I
I)
е-1
(Я~1)г
q{qk - 0
(Ml - 09
к/2
(S.42).
Обозначим через Н наименьшую подгруппу группы F* жащую а и К*. Элемент а
в циклической группе F* имеет
содер:
>ж
Й
§ 7. Распределение элементов
565
п следовательно, |#| = Л, где h - НОК (г, ц - 1). Далее, ф? А тогда и
только тогда, когда ф (р) - 1 для всех р ? Н. Иными словами, Л является
аннулятором Н в группе (F*)" (см. стр. 239). Тогда по теореме 5.6
\А | = ¦ (8.43]
Теперь неравенство (8,37) непосредственно следует нз (8,42; и (8.43).
Рассмотрим случай b Ф 0, Вернемся к формуле (8,41) и заметим прежде
всего, что аддитивный характер является нетри виальным. Следовательно,
тривиальный мультипликативный характер дает в сумму из (8.41) вклад,
равный 1. Таким образом, мы можем записать
%
J
й
Теперь G (ф\ Ц) - - 1, если характер ф' является тривиальным, н | G (if',
Xj)| = если характер ф' нетривиален. Отсюда следует, что
йк~1г
1(b)- 4
fl*-l
- I
Так как J является аннулятором в (F*)* подгруппы группы F*. порожденной
элементом а, то по теореме 5.6 | /1 - (дк - 1)/г Вместе с (8,43) это дает
(8.38), что и завершает доказательство теоремы.
Можно также получить результаты, касающиеся распределения элементов
основного поля на отрезках последовательности, меньших полного периода.
Пусть s0, slt ... - произвольная линейная рекуррентная последовательность
над полем F<?, г - ее мини мальный период, а п0 - предпериод. Пусть Ь ?
F<? - произвольный элемент поля, N0 >- п0 и 1 ^ N < г. Тогда через Z (Ь;
