О распределении значений аналогов сумм Клостермана

3. Prokhorov E.I., Ропотareva L.A., Permyakov Е.А., Kumskov M.I. Fuzzy classification and fast rules for refusal in the QSAR problem // Pattern Recogn. and Image Anal. 2011. 21, N 3. 542-544.

4. Прохоров Е.И. Нейронные сети для построения ограничений допустимости в задаче "структура-свойство" // Нейрокомпьютеры: разработка, применение. 2012. № 10. 46-56.

5. Herbei R., Wegkamp M. Classification with reject option // Can. J. Statist. 2006. 4, N 4. 709-721.

6. Yuksel S.E., Wilson J.N., Gader P.D. Twenty years of mixture of experts // IEEE Trans. Neural Networks Learning Syst. 2012. 23, N 8. 1177-1193.

7. Stone M. Cross-validatory choice and assessment of statistical predictions //J. Roy. Statist. Soc. B. 1974. N 36. 111-147.

8. Amours D., Desnoyers S., Silva I., Poirier G.G. Poly(ADP-ribosyl)ation reactions in the regulation of nuclear functions // Biochem. J. 1999. 342, N 2. 249-268.

9. Кумсков M.И., Смоленский Е.А., Пономарева Л. А., Митюшев Д.Ф., Зефиров П. С. Системы структурных дескрипторов для решения задач "структура-свойство" // Докл. РАН. 1994. 336, № 1. 64-66.

10. Vapnik V.N. The nature of statistical learning theory. N.Y.; L.: Springer, 1998.

11. Thomas R., Karsten B. Multilayer perceptron kernel // Proc. 24th SIBGRAPI Conf. on Graphics, Patterns and Images. Maceio, Alagoas, Brazil, 2011. 337-343.

Поступила в редакцию 11.02.2013

УДК 511.37

О РАСПРЕДЕЛЕНИИ ЗНАЧЕНИЙ АНАЛОГОВ СУММ КЛОСТЕРМАНА

И. С. Тимергалиев1

Доказана теорема о распределении значений аналогов сумм Клостермана. Получены асимптотические формулы для дробных моментов этих сумм.

Ключевые слова: аналоги сумм Клостермана, распределение значений, дробные моменты.

A theorem on the value distribution of analogues of Kloosterman's sums is proved. Asymptotic formulas of fractional moments are proved.

Key words: analogues of Kloosterman's sums, values distribution, fractional moments.

В работе fl] получены оценки аналогов сумм Клостермана, а в работе [2] установлены асимптотические формулы для четных моментов подобных сумм и доказаны законы распределения значений данных сумм. В. Н. Чубариков поставил вопрос о скорости стремления к предельному распределению. Настоящая работа посвящена ответу на этот вопрос.

Пусть p — простое число, h < p и x — натуральное число. Рассмотрим сумму

Sp(x; h) = ^ e2nixq*/P,

q^h

где суммирование ведется по простым числам q, и q* определяется из сравнения

qq* = 1(mod p).

Для того чтобы в дальнейшем провести теоретико-вероятностную аналогию, положим z = n(h) и

£ = =

Sp

' Тимергалиев Ире к Саматович — асп. каф. математического анализа мех.-мат. ф-та МГУ, e-mail: irek_tim@mail.ru.

Предположим, что ж принимает значения из интервала 1 ^ х ^ р с одинаковой вероятностью 1/р. Тогда момент порядка 2г случайной величины £р(х) будет равен

I А 1 Р

II

ме/ = АР(Г) = = —гТ.

Х=1 Х=1

2г

Обозначим через Т(Л) = ТР(Л) число решений сравнения

9* + ... + 9* - 9*+1 - ... - 9*г = 0(тос1 р).

Ясно, что

1 р

поскольку верно следующее равенство:

I у- е2^гЖт/р = | если т = °(ШОс1 р); р Х=1 1 0, если т ф 0(тос1 р).

Найдем асимптотическую формулу для величины Т(Л,) при Л, < р и Л, ^ те. Справедливо следующее утверждение.

Лемма. Пусть , . ..,д2г — простые числа, не превосходящие Л, и Л2г-1 < (2г)-1р. Тогда

для числа, Т(Л) = ТР(Л) решений сравнения

д* + ... + д* - д*+1 - ... - ф 0

при Н —> оо и г ^ л/г. имеет место асимптотическая формула

Т (Л) = г!гг + 0г!г2гг-1,

г(9е \в\ ^ 1, а при г ^ г верно неравенство Т(Л) ^ 2гггг.

на

Q = ... ^дг+1 . ..<?2г ф 0(тоё р),

получим сравнение

52 ... 9г9г+1 . . . 52г + ... + 91 ... 9г-19г+1 ... ?2г -

-д1... <?гдг+2 ... <?2г ... - 91 ... 9г+1... ?2г-1 ф 0(тоё р). Поскольку каждое слагаемое в этом сравнении меньше, чем р/(2г), оно будет уравнением

91 9г 9г+1 92г

Наборы (дг+1,..., 92Г) которые являются перестановкой набора (91,..., ), являются решениями по-

Т1

г!г(г - 1)(г - 2)... (г - г + 1) < Т^Л) < г!гг.

Оценим сверху число решений д1,...,дг, дг+1,..., ^2г, для которых дг+1,..., 92Г не является перестановкой набора (91,..., ). Без ограничения общности можно считать, что (91 ^ ... ^ дг) и (дг+1 ^ ... ^ 92г )•

Пусть 9 — максимальное из чисел и такое, что

Тогда уравнение (2) можно переписать в виде

Q Q Q Q

Рассмотрим случай 9 > г.

Без ограничения общности положим 9 = Пусть так же £ таково, что 9^+1 = ... = 9« = 9 и ^ = 9^+1. Очевидно, что £ ^ 8 - 1 91 ^ 92 ^ ... ^ < 9 и 9г+1 ^ ^г+2 ^ ... ^ 9Г+« <

Обозначим С?! = --—^-—. Тогда О1 = где (А, а) = 1. Равенство (3) равносильно

Чв + 1 ...дг 'Ч.г + в + 1 ...д2г

следующему уравнению:

01 _ О1

91 9« 9г+1 9г+«

из которого, если собрать все слагаемые, равные в левой части, а остальные в правой, следует равенство

где (В, 9) = 1. Из равенства (4) получаем следующую цепочку:

(в - ¿)9«-4-1А = ^ (в - £)  А = 9  В ^

^ 9 \ (8 - £) ^ г > (8 - £) >9,

что противоречит первоначальному предположению.

Рассмотрим теперь случай 9 ^ г. Очевидно, что уравнение (3) имеет не более г2« решений и соответственно уравнение (2) имеет не более г2«гг-« решений. Отсюда следуют неравенства

г!г(г - 1)(г - 2)... (г - г + 1) < Т(Л) < г!гг + г2«гг-«.

Для г ^ г можно записать следующее неравенство:

Т{к) < гггг + гггг (-У <2гггг.

/ 2 \ ^

Пусть теперь г < л/г. Тогда верно неравенство г2згг~8 = гг*_1г2 ( ^ ) < гт~гг2. Обозначим

П = Ф - - 2)... (г - г + 1) = - ^ ... - ^

Поделив это равенство на гг и прологарифмировав его, получаем

-5=1>И>

к=1 4 7

Так как верно неравенство А; ^ г — 1 < у7^, то1 — — и, считая, что г ^ 4, заключаем

к/г к 2к ^-= ^ —.

1 — - г — лЛг -г

Поскольку 1п (1 — > — -р-х, то с учетом полученного выше неравенства имеем

п Г- 2к _ г

1Пи>у

гг /

Из последнего неравенства следует

г' ^ г г

к=1

г(г — 1) _

/е" * < П-

_г(г-1) г(г-1) . , г2

А с учетом того, что е г >1--^—>1 ——, мы получаем следующие неравенства:

т\гг - т\т2гг-1 < Т(Н) < т\гг + гг-1т2.

Оценим меру ¡л больших значений суммы вр{х). ¡л = -, где V = ^{ж : [¿^(ж)! ^ Лу^} — количество х,

Таким образом, можно записать Т(Н) = т\гг + вт1т2гг 1, где \в\ ^ 1.

V

для которых выполняется неравенство в скобках.

А2

Теорема 1. Для, меры, /л больших значений суммы вр(х) верно неравенство ¡л < 6 • е~~. Доказательство. Очевидно, что при Л > л/г имеем V = 0. Поэтому можно считать, что Л ^ -/х. Тогда

1 р

^ \ 2г г V ,, ^ о». . ^

= -{Х^г < - £ = т.

В лемме было показано, что Т(К) ^ 2гггг, откуда следует, что /л ^ 2

Для г

верны неравенства —— 1 < г ^ — ^ С учетом данных неравенств получаем

/л < 2 • е"г < 2 • е • < 6 • е"

Теорема доказана.

Справедлива следующая теорема о скорости сходимости распределения рассматриваемой случайной величины.

Теорема 2. Пусть £р(х) — величина, определенная выше. Тогда найдется такое р0, что для любого р > р0 справедливо равенство

2

*Р(х) = 1 - е-х + Яр,

где -Рр(ж) — функция распределения величины £р(ж) и \Ир\ ^

Доказательство. Пусть Н = 1п р. Тогда существует такое р1, что пр и р > р1 тер но неравенство

(2г)~1р > ¡г2,1"-1 = (1пр)2г~1. Следовательно, для г ^ л/г будем иметь Ар(г) = г! + = г! + д1^, где

\в\ ^ 1. Тогда при г ^ справедливо равенство Ар(г) = г! + .

Неравенства г = 7г(/г) ^ 2ын = 2ЫЫр ^ верны для всех р начиная с некоторого р2-

Положим ро = т&х(р1,р2). Тогда при р > ро и г ^ верно следующее равенство:

т2г(р) = г\ (1 +

(1п р)1/4 ) ' где \в1\ ^ 1.

Применим следствие 1 теоремы 1 работы [3]: положим к = | и N = [|1п1пр] +1. Тогда N ^ 1п(1п Ру/8 + 1 < пр)1/2 ^ а значит, при р > ро для 1 ^ г ^ N верно, что

ГП2г(р) = г\ (1 + 6>1

(1п р)1/4

Отсюда имеем ад = 1 - е-' + г» №1 < = ^^ <

доказана.

1 р

Пусть та{р) = - £,р(х) — моменты рассматриваемой случайной величины. Докажем справедли-

х=1

вость следующей теоремы о дробных моментах.

Теорема 3. Пусть £р(х) — велич ина, определенная выше. Тогда найдется такое р0, что для любого р > Ро м0<а<^у1п1пр справедливо равенство

ша(р) = Г(0,5а + 1) + вЯр,

2

2

А

е

где Г(-) — гамма-функция Эйлера, \0\ ^ 1м

0 < а < 30; 30 ^ а ^ ^уДаТар] 2^3" л/1п 1II р < а ^ 1п1пр,

(. а±2 о20 2 1 { \/1п Р \ \ ^

' ) = 23 . Г (| + 1) ехр .

Доказательство. Пусть Л, = 1пр. Повторяя рассуждения, проведенные при доказательстве теоремы 2, получим, что существует такое ро, что при р > ро и г ^ -\/(Ыр)1/2 верно равенство

где \0\ ^ 1.

Положим р = Поскольку 1п (Ыр)1/4] + 1 < Ы^пр)1/8 + 1 ^ ^(1п р)1/2, то можно применить теорему 1 из работы [4].

В нашем случае ф V!, 6 = 1 и /(р) = (1п р)1/4, откуда получаем требуемое утверждение. Теорема доказана.

В заключение автор приносит благодарность научному руководителю д.ф.-м.н. Р. Н. Бояринову за постановку задачи и внимание к работе.

СПИСОК ЛИТЕРАТУРЫ

1. Карацуба А.А. Аналоги сумм Клостермана // Изв. РАН. Сер. матем. 1995. 59, № 5. 93-102.

2. Жимбо Э.К., Чубариков В.Н. О распределении арифметических функций по простому модулю // Дискретн. матем. 2001. 13, вып. 3. 32-41.

3. Бояринов Р.Н. О скорости сходимости распределений случайных величин // Докл. РАН. 2010. 435, № 3. 295-297.

4. Бояринов Р.Н. О дробных моментах случайных величин // Докл. РАН. 2011. 436, № 3. 299-301.

Поступила в редакцию 10.10.2012

УДК 511

О НЕКОТОРЫХ ДОСТАТОЧНЫХ УСЛОВИЯХ РАВНОМЕРНОСТИ СИСТЕМ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ

П. Б. Тарасов1

Для произвольной конечной системы A функций k-значной логики, принимающих значения из множества Es = {0,s — 1} k ^ s ^ 2, такой, что замкнутый класс, порожденный ограничением функций из A та множество Es, содержит мажоритарную функцию, доказано существование констант с и d, таких, что для любой функции f G [A] глубина Da(/) и сложность LA(f ) функции f в классе формул над A связаны соотношением Da(/ ) < сlog2 La(/)+ d.

Ключевые слова: равномерность конечных систем, многозначная логика, полиномиальная эквивалентность, мажоритарная функция.

A k Es =

{0,1,...,s — 1} k > s > 2, such that the closed class generated by restriction of functions from

A Es с

1 Тарасов Павел Борисович — асп. каф. дискретной математики мех.-мат. ф-та МГУ, e-mail: tarasov.p.bgmail.com.

Rp =