Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 123
Текст из файла (страница 123)
является чисто периодической последовательность ' н что и == О. Для произвольного вектора-столбца Ь =- (Ьо, Ь" ..., Ь„,)т из пространства Ьо и произвольного целого числа положим а(Ь; Ь) = а(Ьо Ьт . Ь»-»1 Ь) = т — ! )йлт — Х(Ьоз„+ Ьт „„+ ° + Ь„, л,„,)е( — ). л=о Общий член под знаком суммы, рассматриваемый как функция и, имеет период г.
Поэтому мы можем записать а(Ь; 6) = ~~У )!(Ь,зла+ Ьтз„,о-> +Ь» тз„,») е( /й(л+1) ~ ",- л=о Используя линейное рекуррентное соотношение (8.)), получи' т †! 1а (Ь1 т!) ~ Е Х(Ьозптт ) Ьтзп+о ! ' ' ' + Ь»-озпо»-т + Ь»-талал + л=о -!с Ь„,атал„+ + Ь,,а„,з„,„, + Ь,,а)е !» — 11 т — ! ~ Х(Ь» таоз„+ (Ьо + Ь„,а,) зл ! -',- ) л.=о г йл'! + (Ь», + Ь»,а»,)зл,„,)е (— = (а(Ь„,а„Ьо+ Ь»,а,, ..., Ь» о+ Ь,,а„,; Ь)(. Это равенство может быть записано в виде ! а (Ь; Ь) ( — ( а (А Ь; й) (, где А — матрица, определяемая формулой (8.3). По индукции; получаем, что )а(Ь; Ь)! =(а(А!Ь; й)( для всех () О.
(832 Пусть д =- (), О, ..., 0) Е Г, — вектор-столбец, и пусть да' д,, ... — векторы состояний ймпульсной функции до, д„ й 7. Распределение элементов ЗО7 Х!о(Ь: й)!'=~о(Ь; й) (Ь; Ь)= ь ь Х("О(ат Зл) ! Ьт(З!ле!— «е.«!, ...,«! Е "Г» лз,л — О 76 (т — и)Х вЂ” зл !)+ +Ь««(з„,«! — зл,«!))е( )= ~Ф (а(т — л) ) т. л=о Х(Ь.(.— з.))Х(Ь,(.„, — .„)) «,, ьо ...О«, с !г» Х(Ь«(з . — — з., ))= г — ! =,'~, '("', ") )( ~ Х(Ь.(.— л)))" т, л=е «О,К» Х(Ь«- (з «-т — з +«-!)) ) ° «|,,ЕК» Заметим, что для с Е Г» из (5.9) следует Ьс = ( О, если счьО, если с=О, «Е!Р» (8.34) удовлетворяющей (8.б). Тогда мы утверждаем, что два вектора состояний д и д, совпадают в том и только том случае, когда А с) -= Алд. Действительно, если с) = с)„, то из леммы 8.)5 следует равенство А д = А"д. С другой стороны, если А д .=- Алд, то А «!б = А"асти, значит, Ат (А)о) = А" (А!4) для всех )'-.'-.
О. Но в силу того, что векторы д, Ас(, Аэб, ..., А' — !!! образуют базис векторно~о пространства Г над полем Г», мы получаем, чтоАт = А", откуда полемме835следует, чтоб = с(„, Все различные векторы последовательности де, 4!.... исчерпываются векторами да, д„..., дн !. Следовательно, как мы только что показали, различными векторами среди последовательности векторов д, Ас), АЧ, ... являются в точности векторы д, Ад, ..., Ап — !д. Воспользовавшись равенством (8.32), получаем я — ! )с)о(д; й)!О= ~~ )о(А!с); й)~э =: ~~1о(Ь; Ь)(т, (8.33) у=-о ь где последняя сумма берется по всем векторам Ь нз пространства В»".
В то же время ззз Гн. З. Линейные рекуррентные носледовательностн Гаким образом, вклад в последнее выражение в формуле (8. дают только те упорядоченные пары (т, и), для которых однов менно выполняются равенства з =- з„, ..., з,„, =- з„,„' Однако в силу того, что 0 ( т, и ( г — 1, это возможно ли при т = и. Отсюда следует, что ~ )о(Ь; й))в = «д».
Объединяя это равенство с неравенством (8.33), получаем ( о (»1; й) ( ( ( †) д»«', что и доказывает (8.30). Неравенство (8.31) следует из (8.30 если положить й = О. 8.79. Замечание. Пусть К является нетривиальным аддити ' яым характером поля Гч, и пусть»р — произвольный мультипл катнвный характер того же поля. Тогда сумму Гаусса 0('т К) = т(с)К(ь) акга можно рассматривать как частный случай суммы из (8.30). Чт показать это, выберем примитивный элемент д поля Гч и рассм рим линейную рекуррентную последовательность з,, з,..., 1- порядка над полем Гч, определяемую равенством за = 1 и рек рентным соотношением з„„= дз„, и = О, 1, ..., Тогда г = — Р =- д — 1, а и, = О.
Заметим, что»р (и) = е (й!г) для некотор целого и. На основании этого мы можем записать г — ! в — ! Если»р является нетривиальным характером, то в этом случ ' нз равенства (5.15) следует, что обе части соотношения (8. совпадают. Суммы, фигурирующие в теореме 8.78, брались по полно !ериоду данной линейной рекуррентной последовательности Следующий результат позволяет оценивать суммы, берущи по отрезку полного периода. Для этого нам потребуется така вспомогательная лемма: й В.ВО. Лемма. Для любых положип!ельных целых чисел г и спраеедлиео неравенство в — ! ~ ' е ( н! ) ( — г 1од г + — г + й«. (8 35,; ь=о !=о 7.
Распределение элен!ентоа Даказаагельство. Для г = 1 неравенство !8.35) тривиально. '(ля «>2 е 1 (/2 Сг — 1, . 12: !1, означает расстояние от действительного числа ! до бли- н!21!1!!его целого числа. Отщода следует, что 2-1 Н вЂ” 1 ! г/21 ~) е ( / ) «» ~2, созес л )( — (-~ 11/ 2 11, созес — + /ч' е !.=о 2=1 а —.! (8.36) г,равнивая суммы с соответствующими интегралами„получаем ! г/2 л/г созес — ' ! г/21 лх + ) созес — ' дх е г 1 н/2 + †„ ) созес ! д! -= и/г г л л г 2г + — !огас(д — ' < созес — + — !он —.
и 2г г л л лк л СО2ЕС вЂ ' — СОЗЕС— г созес— л г л = созес— г л = созес— г Лл11 г б справедливо неравенство (л/г) ' ебп (л/г) ) (л/б) ' . . !и (л/6); следовательно. 21п (и/г) ) 3/г. Отсюда вытекает, что ~г/2! ль ! /! ! л! х ! У созес — < — г(ояг Ч- ( — — — )оя — )г для г~~6, г л (3 л 2) и — 1 1', значит, !.г/22 Х ла ! ! созес — ( — г !одг + — г для г ~~ 6. г л в А.=-1 /для г =- 3, 4, 5 неравенство (8.35) легко получить из (8.36).
)(ля г =- 2 справедливость неравенства (8,35) проверяется непосредственно. Б 8 81. Теорема. Пусть з,, з, — - линейная рекуррентная последовательность /2-га порядка над полем !г'2, а числа г, п, и 12 Гл. 8. Линейные рекуррентные последовательности такие тке, как и в теореме 8.78. Тогда для любого нетривиально аддитивного характера у поля го справедливо неравенсигво и !.л'"-! '! У т(в„) ( —., ) дюе(= !оиг ',.—: — ), л=и где и )~ ио и ! «!у' «г. х!олазал!еи!ьство. На шем с равенства ~~1 '!~х кч ! ~ (6!л — и — г! ) !- о л..о л.:.
« л=-:и где 1.:-,' М ., Оно справедливо, так как сумма по 1' равняется 1 прп и ..' п .. и+ !ь! — 1 и 0 при а !- !т'.==. и.;,'.' и + г —. 1. Переставл ' соответствующим образом члены, получаем Е "!««+ЕЖ Г"'",'"))(г. " ( )! откуда в силу (8.30) следует и-!- н — ! « — ! и — ! и.! à — ! ~ Х(.) ~+~ ~„' ( "",+") ~' у(н) ( — ",") ~ Г! и ь- о !'=-о л-..и т — ! М вЂ” ! — ( — ) с!тчт ~ ~ е( ~ ) л=-о р о Применяя теперь лемму 8.80, получаем искомое неравенств"' Следует отметить, что неравенства, полученные в теорем 8,78 и 8.81, представляют интерес лишь в случае, когда мин мальный период г последовательности в„в,, ...
достаточно вели Для малых г этн результаты становятся слабее тривиальной оцен ', «л-Л вЂ” ! 7,(ви) .: У дла ! .'М-':. г. л=и Для получения нетривиальных утверждений г должно быть больше' чем дю'. Пусть в,, вт, ... — линейная рекуррентная последовательност над полем ~е, г — ее минимальный период, а и, — ее предперио: Если Ь Е К„, то через Е (Ь) обозначим число таких и, ио ( п п„-'; г — 1, для которых в„= — Ь. Иными словами, Е (Ь) рав няется числу появлений элемента Ь Е Ко на полном периоде лн нейной рекуррентной последовательности.
561 $7. Распределение элементов Если в„, в,, ... является рекуррентной последовательностью Ь-го порядка и максимального периода, то о (Ь) можно определить явно. В соответствии с теоремой 8.33 в этом случае г = о» вЂ” 1, а и„= О. Тогда векторы состояний нашей последовательности аь в,, ..., в,, пробегают все ненулевые векторы пространства К~. Следовательно, 2 (Ь) равняется числу ненулевых векторов пространства К, с Ь в качестве своей первой координаты. Элементарный подсчет показывает, что# (Ь) = д» вЂ” ' для всех Ь ~ 0 и Л (0) = гу' — ' — 1.
Таким образом, в последовательности максимального периода над полем 1'» все элементы поля К встречаются иа полном периоде одинаково часто (с точностью до малого отклонения для нулевого элемента). В общем случае столь равномерного распределения элементов ожидать не приходится. Однако можно оценить разницу между действительным числом появлений данного элемента и идеальным числом г!д. Если г достаточно велико, это отклонение сравин~ельно мало. 8.82.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
