Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
X (sn)
1/2
R
qkl'2 для всех и .> щ
(8.311
Доказательство. Заменив вектор начального состояния иа вектор sH (что не
влияет на верхнюю границу в (8.30)), м можем, не теряя общности,
предположить, что последователь! ность s0, slf ... является чисто
периодической последовательность и что и ~ 0. Для произвольного вектора-
столбца b (Ь0,
... , fr*_i)T из пространства F* и произвольного целого числа положим
(т(Ь; А) о(Ьф Ьи ,.bh_x\ Л) ^
т-\
X (bi}sn 4" Ь * * * ~Ь bk-lsn+k-l) е
Нп
п~0
Общий член под знаком суммы, рассматриваемый как функция п, имеет период
г. Поэтому мы можем записать
•,ц
• "*чч
• :*Г§ - .W
":$Г
г- 1
П+1
+ м
I fr
Ь bh-i&n+h) е
h (п I- 1)
^ 41
/ I
М .*|1 "
Используя линейное рекуррентное соотношение (8.1), получаё
г I
S x(^"sn+1 + ^lSn+2 h * * * + I fyk-la0'V4
a (b; h)| =
о
T Vi?iiSn+i -f-
* fr fr
bh-lah-lsn+k~\ 4 bk-\a)e
hn
t- 1
S X (bk-iaQ$n 4" (bQ 4' bk^ai) sn+l f
n=0
* ft *
ft Й -*
r
¦:-4
vvll
" 4#
:a
¦ Д
•• 4V
¦ Д ' 4'5?
•Л'.'
' Z У
bQ -\- Ьк_хаи
4 fr *
b
fe-2 '
&
¦I
Это равенство может быть записано в виде
j о (b; Н) | - | а (ЛЬ; А) |,
где А - матрица, определяемая формулой (8.3). По индукциЩ получаем, что
о(Ь; А)|~|а(Л*Ь; А) | для всех /> 0.
(8.
S.SS
k
Пусть d (1, 0, ... , 0) ? SFJ - вектор-столбец, и пусть dlf ...^векторы
состояний импульсной функции dQ, dlt
¦i.-л
' м
§ 7. Распределение элементов
557
удовлетворяющей (8.6). Тогда мы утверждаем, что два вектора состояний dm
и du совпадают в том и только том случае, когда дт$ And. Действительно,
если dm - dn, то из леммы 8Л5 следует равенство Amd = And. С другой
стороны, если Amd - - /f"d, то Aml ld - 4fl+'dH, значит, Ат (/Ud) - Ап
M'd) для всех /¦> 0. Но в силу того, что векторы d, Ad, A2d, ... , Ак~М
образуют базис векторного пространства F? над полем Fv, мы получаем, что
Ат - Ап, откуда по лемме 8.15 следует, что dm - drt.
Все различные векторы последовательности d0, db ... исчерпываются
векторами dy, dT, ... , dn_i. Следовательно, как мы только что показали,
различными векторами среди последовательности векторов d, Ad, AM, ...
являются в точности векторы d, Ad, ... , zl^'d. Воспользовавшись
равенством (8.32), получаем
RI о (d; А) р = ? | а (А<А\ А) |2 < ? | а (Ь; А) |2, (8.33)
/=о ь
где последняя сумма берется по всем векторам b нз пространства F?. В то
же время
| a (b; к) |(r) = ^ ff (b; к) о (b; к) =
ь
г- I
2 ? Д (^rrt+1
* ¦ -" € F\j т*
г-1
) I ••• Ь (Smtft-l - sin-A-l))e --------------------------6 =
e lh(m~n) ^ _
Ш, M=fl
2 X(&o(Sm-Sn))x(&l (^m +1 - Sn+i)) ¦ ¦ ¦
^o' S'
* • • X Фк-i Sn+ft-l)) =
e(АДу-L) ( V X(b0(Sm-
У, X (Sm+fc-l - S/t+fc-l)) |. (8.34)
Заметим, что для с ? fq из (5.9) следует
Sf 0, если сф 0,
%(&) - | . еслн с - о,
Гл. 8. Линейные рекуррентные последовательности
Гакнм образом, вклад в последнее выражение в формуле (8. дают только те
упорядоченные пары (т, /?), для которых однов]
•"'3
менно выполняются равенства sm - sn, Однако в силу того, что 0 т, п г -
при т = п. Отсюда следует, что
'т +Й.-1
'"4-М
i, это возможно ли
S | о (b; /i) Р ь
= rqK
.га
¦i
Объединяя это равенство с неравенством (8.33), получаем
Г \ 1/2
о(6; Н) |<
R
Я
ft/2
ч т
что и доказывает (8.30). Неравенство (8.31) следует из (8. если положить
h - 0.
8.79. Замечание. Пусть % является нетривиальным аддити ным характером
поля fq, и пусть хр - произвольный мультипл# кативный характер того же
поля. Тогда сумму Гаусса
х)= ? т (с) х (с>
е г;
••Ч!
.s'S"
можно рассматривать как частный случай суммы из (8.30). Чт показать это,
выберем примитивный элемент g поля Тя и рассм рим линейную рекуррентную
последовательность %, sl5 ... I-порядка над полем определяемую равенством
.s0 1 и рек$
рентным соотношением $п+1 - gsn, п = 0, 1, ... , Тогда г - R - q - 1, а
п.ц = 0. Заметим, что ф (g) - е (hlr) для некотор целого к. На основании
этого мы можем записать
Bid
Ш
Т:-1
а №. у.) = У/х Ю + (g") = У] у, (s")
т-1
е
hn
¦&J
5 л", .
Если ф является нетривиальным характером, то в этом случ; из равенства
(5.15) следует, что обе части соотношения (8. совпадают.
Суммы, фигурирующие в теореме 8.78, брались по полно периоду данной
линейной рекуррентной последовательности Следующий результат позволяет
оценивать суммы, берущнееШ по отрезку полного периода. Для этого нам
потребуется така вспомогательная лемма:
8.80. Лемма. Для любых положительных целых чисел г и справедливо
неравенство
li 6
/~о
Of)
V>4
2
2
< -rlogrT-g-r +N.
(8.
§ 7. Распределение элементов
559
Доказательство, Для Идя г >¦ 2
г - i неравенство (8.35) тривиально,
^....
4 V
з / ы
Пт
•г.:: О
е (HNlr) - 1 j \ е (А/г) - J |
sin я || hfr ||
cosec я
А
г
\ ?
1 < A<r - 1,
где | означает расстояние от действительного числа i до бли жайшего
целого числа. Отсюда следует, что
Г-~ 1
/i-л
А! - 1
Z * (Т
П=0
г-1
cosec л
h
г
л=1
1//2J
ЛД . j f
cosec---------h А'-
(8.36)
'павнивая суммы с соответствующими интегралами, получаем
