Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
1//2J
;д nh л
cosec - - cosec -
I//2J
nh
cosec -
П
h-^2
Lr/2J
л
+ I
ПХ J
cosec - ax
Я/2
cosec
Л
-j- - Г cosec t dt -¦=
Tt J
я/г
cosec j- h log ctg < cosec Д + log
2r
Tt
Для г Д 6 справедливо неравенство (л/т)"1 sin (л/r) (л/6)-1 -
sin (л/6); следовательно, sin (л/r) > 3/г, Отсюда вытекает, что
Iг/П
nh
\д
> , cosec -
-I г
h i
v,
J.
n
r logr + (
1
I
Я
log -y } Г ДЛЯ r ;> 6,
и. значит,
I//2J
TtH- . 1 4 ,1 S'
cosec -y- <7 - r log r + ~g* г для r 6,
r - 3, 4, 5 неравенство (8.35) легко получить из (8.36), Для г - 2
справедливость неравенства (8.35) проверяется не-щсгвенно. ?
8.81, Теорема. Пусть s0, Sj,
линейная рекуррентная
ПОС
}сдедовательность к-го порядка над полем а числа г, пй и R
560
Гл. 8. Линейные рекуррентные последовательности
такие же, как и в теореме 8.78. Тогда для любого нетривиальное^
аддитивного характера % поля р[? справедливо неравенство
n±N-\
у
п--и
<(¦
г
У R
1/2
f I *• >
q-'!-
л.
1о?Т
2
Лг
5
г
где и > щ и 1 с N < г.
Дотзаглельбггшо. Начнем с равенства
/-• . .V I
""/С X(Srt)
4т-¦
П - U п^и
и \ г 1 /V -1
v
Т \
/ I
й
' /2 (л
л
У)
/=о
л с"
где 1
¦v.
ау
•1>5-
.1>Л"Й
S'jiL
Л
Оно справедливо, так как сумма по / равняется 1 при и < /г
¦< гг + N 1 и 0 при и \ N < гг < и + г i. Переставл соответствующим
образом члены, получаем
r-\ {N-1
n + bi- I
У X ы = -j- УI У
/
е
А (и -¦! - /)
W-J Г -1
А=0 -'/-О
У X (Sn)е
Нп
г
/
\
/
откуда в силу (8.30) следует
X(Sn)
П'-И
2
ft-о
Лг-1
А 4- /)
г
1-0 Г
R
Лп
I/Й
>k/2
N-1
2 2
ft^O /z^O
С
А/
J !
Применяя теперь лемму 8.80, получаем искомое неравенств1
Ш
Следует отметить, что неравенства, полученные в теорем., 8.78 и 8.81,
представляют интерес лишь в случае, когда мин| мальный нсрнод г
последовательности s0, sT, ... достаточно велим Для малых г эти
результаты становятся слабее тривиальной оценз|
ы+Л' -1
? х("п)
п^и
N для \ N\>C г.
.fy?T
Я
Vi •* л
Для получения нетривиальных утверждений г должно быть бодьш^ чем qkt2,
''
Пусть %, S|. ... - линейная рекуррентная последовательности над полем г -
ее минимальный период, а гг0 ее предпернод§ Если b С Fy, то через Z (Ь)
обозначим число таких гг, гг0 < п -гг0 + г - 1, для которых - А. Иными
словами, Z (b) ра
ияется числу появлений элемента b ? на полном периоде лЩ нейной
рекуррентной последовательности.
§ 7. Распределение элементов
561
Если So. $1. является рекуррентной последовательностью &-го порядка и
максимального периода, то Z (6) можно определить явно. В соответствии с
теоремой 8.33 в этом случае г ~ qk - I, а пд = 0. Тогда векторы состояний
нашей последовательности
s0, sb " V-i пробегают все ненулевые векторы пространства fj.
Следовательно, Z (Ь) равняется числу ненулевых векторов пространства fj с
b в качестве своей первой координаты. Элементарный подсчет показывает,
что Z (b) = qk~l для всех b Ф 0 н Z (0) - qk-1 - I Таким образом, в
последовательности максимального периода над полем Fg все элементы поля
Fq встречаются на полном периоде одинаково часто (с точностью до малого
отклонения для нулевого элемента).
В общем случае столь равномерного распределения элементов ожидать не
приходится. Однако можно оценить разницу между действительным числом
появлений данного элемента и идеальным числом rlq. Если г достаточно
велико, это отклонение сравнительно мало.
8.82. Теорема. Пусть 5(>, х,, ... - линейная рекуррентная
последовательность k-го порядка над полем Fyг г - ее минимальный период,
a R такое же, как и в теореме 8.78. Тогда для любого элемента b ? F9
Доказательство. Зафиксируем Ь ? F^ и определим на Fo действительнозначную
функцию Ьь следующим образом: б6 (b) = I и 6Ь (с) - 0 для всех с ф Ь. В
силу (5Л0) функцию можно
представить в виде
6ь (с) = у 2 X'(с - *>•
У.
где с ? а сумма берется но всем аддитивным характерам ноля Fy- Тогда
Я
S * (0 S г (s..)-
n=^n
о
Выделяя слагаемое, соответствующее тривиальному аддитивному характеру
поля fgr. и помечая звездочкой сумму, в которой сум-
9 Зак, 243
Гл. 8. Линейные рекуррентные последовательности
¦"*{
мирование производится по всем характерам, кроме трнвиал иого, получаем
л у- г-]
Т==у23р) 2
%
п-п
•38
О
Используя (8.31) и учитывая то, что существует q виальных аддитивных
характеров поли iF4, получаем
1
нетр!|
• • IS
• м
Z (Ь) -
г
1
<'
_Ь| I, _
I
Я
V
X
ne-j г -I
2
П-^/Гй
1
1
1
г
Я
ч
Д/2
Г
8.83. Следствие, Пусть s0, ... - однородная линейная рщ
куррентная последовательность над полем F9 и г -~ ее ммнималШ ный период.
Пусть минимальный многочлен этой последовател ноет и т (х) ? \ х} имеет
степен ь k > 1 и удовлетворяет уел
вию т (0) Ф 0. Тогда для любого элемента Ь ? f4 справедли неравенство
< (I -Ж) е/2-
ш.
Z{b)
г
Ч
Ч
Я#\ч
Ж
№
т.
Ш
Доказательство. По теореме 8.44 г (tm) ord (т (х)), Кроме тог в силу
замечания, предшествующего теореме 8.78, R = ord (m Тогда искомый
результат следует нз теоремы 8.82.
Если линейная рекуррентная последовательность имеет н| приводимый
