Свойства сумм и произведений подмножеств произвольного конечного поля

Задачи, рассматриваемые в диссертации, относятся к бурно развивающемуся в настоящее время разделу теории чисел, называемому «Аддитивной комбинаторикой». Впечатляющие результаты, достигнутые в этой области, обусловлены разнообразием методов, используемых при изучении задач из этой области. Данная работа использует преимущественно комбинаторные методы. Результаты диссертации так или иначе связаны с аналогами проблемы Варинга и с задачами изучения роста суммы и произведения подмножеств конечных полей.

Рассмотрим некоторое непустое множество X с определенной на нем бинарной операцией *: А х В —> X. Тогда можно определить операцию * на парах подмножеств X следующей формулой: А* В = {а*Ь: а € A, b € В}. В частности, если, А и В — подмножества кольца, то можно рассмотреть две операции на подмножествах: сложение, А + В : — {а+ 6: a G Д6 G В} и умножение АВ — А • В := {ab: a € А: Ъ Е J5}. Определим для некоторого к? N и множества, А его кратную сумму к, А = А + А. + А, кю степень v V ^ к этого подмножества Ак = <А ¦ А •. • Д и операцию умножения произвольv к ного элемента кольца Ъ на подмножество b* А = {6} • А. Иногда, если это не приведет к путанице в обозначениях, знак * будет отпускаться.

Мы будем в дальнейшем обозначать мощность множества, А следующим образом: В качестве кольца будет рассматриваться конечное поле из q = рг элементов для произвольного простого р. Оно будет обозначаться через Fg. Для некоторого множества У С F? определим множество его обратимых элементов У* : — Y {0}. Ниже всегда будет предполагаться, что р — некоторое простое число. Так как произвольное конечное поле характеристики р содержит подполе, изоморфное Fp, то мы без дополнительных оговорок будем считать, что Fp С F9. Рассматривая произвольный элемент х G W* мы можем определить его мультипликативный порядок ovdqx как наименьшее натуральное I такое, что х1 = 1. Для любого действительного у символом [у] обозначается его целая часть, т. е. наибольшее целое число, не превосходящее у, а {у} обозначает дробную часть у.

Определим также операцию сложения произвольного элемента h 6 F9 с подмножеством hfА = {/г} + А. Операция умножения множеств всегда имеет больший приоритет, чем сложение, поэтому, например, запись тА1 для некоторых натуральных т и I следует понимать как m-кратную сумму 1-й степени множества А.

Гипотеза, называемая сейчас проблемой Варинга, была высказана им в 1770 г. в следующем виде:

Доказать, что всякое натуральное число является суммой не более четырех квадратов, девяти кубов, девятнадцати биквадратов и т. д.

По-видимому, предполагалось, что для любого натурального п ^ 2 существует число s (n) с тем свойством, что всякое натуральное число пред-ставимо в виде суммы n-х степеней положительных чисел, причем количество слагаемых не превосходит s. Наименьшее s (n), обладающее таким свойством принято обозначать д (п). Над оценками на д (п) работали много ученых. Здесь следует отметить имена Лагранжа ([1], глава 5), Д. Гильберта [2], Ю. В. Линника [3], Диксона [4−11] и Пиллаи [12]. Принято обозначать через G (n) наименьшее число s с тем свойством, что все достаточно большие представимы в виде суммы не более, чем s п-х степеней натуральных чисел. Харди и Литтлвуд [13−18] получили первые оценки на G (n). Далее их результаты были последовательно улучшены И. М. Виноградовым [19], [20], А. А. Карацубой [21], Р. Боном, Т. Були [22,23]. Наилучшая известная автору этой работы оценка G (n) принадлежит Т. Були [24]. Он доказал, что G (n) ^ n (lnn + lnlnn + O (l)). Функцию G (n) можно тривиально оценить снизу так: G (ri) ^ п. Последнее неравенство означает, что граница, полученная Були, близка к оптимальному своему значению.

Определение 0.0.1. Рассмотрим произвольное полукольцо R. Множество, А С R является базисом R порядка к, если каждый элемент х Е R представим в виде х + Х2—. + Хк = х% где х, Х2, •. •, хь Е А, но существует такой элемент я: о? R, что + + ¦ - • + ф xq для любых х, Х2, ¦ ¦ -, Xk-i Е А. Мы будем обозначать порядок базиса, А символом к (А).

Л.Г. Шнирельман [25] изучал проблему суммирования последовательностей натуральных чисел общего вида, сведения о которых касаются лишь определенной им плотности расположения в них членов. Неулучшаемая оценка порядка базиса подмножества N U {0} через его плотность вытекает из теоремы Г. Б. Манна [26]. Аналогичный результат для порядка базиса подмножества ¥-р выводится из теоремы Коши-Давенпорта (теорема 1.3.1).

Известно, что в поле Fp для фиксированных к G N и е > 0 случайно сгенерированное множество мощности > является базисом порядка к с большой вероятностью (стремящейся к 1 при р —" оо). В работе [27] А. А. Карацуба строит конструктивные примеры базисов мощности, близкой к оптимальной, в кольце вычетов по модулю степени простого числа.

Определение 0.0.2. Подмножество I С F9 называется особым, если существует элемент d G F9 и нетривиальное подполе 5 С F9 такие, что X С dS. В частности, любое подмножество У, |У| = 1, является особым.

В этой работе будет изучаться следующие задачи:

Вопрос 0.0.1. Даны натуральное число п и действительное е > 0. Рассмотрим также п подмножеств Ai, А2,., Ап С Fp таких, что Ai• А2- • • ¦ • Ап > р1+£. Доказать, что для некоторого натурального N = N (n, е) верно равенство NAi • А2 •. ¦ Ап = Fp.

Вопрос 0.0.2. Для любого натурального п ^ 2, действительного числа е? (0,1) и неособого подмножества, А С Fq, q = рг, такого, что, А > q*^, найти такое натуральное число т — т{п. г), что существует натуральное N = N{n, г, е) для которого выполнено равенство NAm = F9.

Согласно лемме 1.2.1, равенство NAm — Fg верно для любого неособого множества, если положить N — q — 1ит — г. Нас же интересуют значения N и т, не зависящие от р.

Первые оценки на мощность кратных сумм и степеней в конечных полях были получены в известной работе Ж. Бургена, Н. Катца и Т. Тао [28]. Большинство работ в этом направлении, написанных позже, а также результаты диссертации, так или иначе используют идеи этой статьи.

Определение 0.0.3. Подмножество X является симметричным, если Х = -Х.

Определение 0.0.4. Назовем подмножество X антисимметричным, если X П (-Х) = 0.

Следующие три теоремы, доказанные в главе 2, используются в доказательствах основных результатов диссертации и также интересны сами по себе.

Теорема 2.1.1. Если X С F9 и Y С Fg таковы, что Y антисимметрично и X\Y > q, то 8XY = ?q.

Теорема 2.1.2. Рассмотрим подмножества X С F^ и Y С такие, что Y симметрично. Если выполнено неравенство |Х||У| > q, то 8XY =.

F,.

Теорема 2.2.3. Рассмотрим произвольные подмножества X, Y С F? такие, что |Х||У| > q. Тогда выполнено равенство 16XY — Fq.

Теорема 2.2.3 была улучшена М. Рудневым [29]. Он получил следующий результат.

Теорема 0.0.1. Рассмотрим произвольные подмножества С F9 такие, что |Х||У| > q. Тогда выполнено равенство 10XY = Fg.

Отметим, что в случае поля Fp при наличии более сильных предположений на мощности множеств X и Y, а именно, |Х||У| > р1+£ для некоторого е > 0,-равенство NXY = Fp, N = N{e), легко вытекает из известных оценок тригонометрических сумм (например, [30], страница 103, упражнение 8а:). Однако, такой подход не позволяет доказать теоремы 2.1.1, 2.1.2, 2.2.3 и 0.0.1.

Теорема 0.0.1 будет использована при доказательстве многих результатов настоящей работы.

Теоремы 2.1.1 и 2.1.2 можно применить к одной из задач в поле Fp, сформулированных Эрдешем и Грэхэмом в работе [31]. Она формулируется так.

Существует ли для любого? > 0 такое к{е) 6 N, что для любого достаточно большого простого р и для любого целого с существует к < к (е) попарно различных целых чисел Xi таких, что 1 ^ Xi ^ р£, i = 1,2,., к, и к.

Y^x?=c{madp), (1) г=1 где здесь и в дальнейшем xj1 — наименьшее положительное целое такое, что х^гхг = 1 (modp)7.

Крут [32] показал, что можно выбрать к < log3+o (1) р попарно различных чисел на интервале [1,ре], чтобы выполнялось равенство (1).

Следующим результатом в этом направлении была работа И.Е. Шпарлин-ского [33]. Он использует оценки тригонометрических сумм А.А.' Карацубы ([34], [35], [36]) и устанавливает, что для любого? > 0 и для. достаточно большого р можно выбрать к = 4е-3 + О (е-2) попарно различных чисел Xi, г = 1,., к, таких, что 1 ^ ^ ре и выполняется равенство (1).

В параграфе 2.3 будет доказано, что.

Теорема 2.3.1. Для любого? > 0, для любого достаточно большого простого р и для любого класса вычетов a (modp) существует положительные попарно различные целые rci,., х2 ^ р£, где N ~ 8 • (+ |] + l)2- такие, что ^ ^ а =—Ь- • • • Ч—(modp).

Х Х]у.

Таким образом, теорема 2.3.1 улучшает результат И. Е. Шпарлинского.

Если бы аналог теоремы 2.3.1 удалось доказать при N ^ где с — некоторая константа, то была бы доказана гипотеза А. А. Карацубы, сформулированная в работе [37] на стр. 83 (смотри также [38], стр. 225).

Крут [39] доказал, что для любого? G (0,1] и для любой степени k ^ 1 существует N = N (k, E) такое, что для любого достаточно большого простого р и для любого класса вычетов a{modp) существует положительные целые ждг ^ //, удовлетворяющие сравнению: а = (40 + • •' + 04Г1 {modp).

При помощи техники, развитой Ж. Бургеном [40], в главе 3 доказывается обобщение теорем 2.2.3 и 0.0.1.

Теорема 3.2.1. Для любых подмножеств А}, А2,., Ап С Fp, п ^ 2, таких, что Ai ^ 2,1 ^ i ^ п и.

A1-A2-.-An>vl+? для некоторого? > 0, мы имеем.

NA1-A2.-An = Fp, где.

10, если п = 2;

N = ^ 10 ¦ max{1,24 ([log2 (J)] + l)}, если n = 3;

16n-2 ¦ max{1120,320(-ll — [log2(e (n — 2))])}, если n > 3.

Теперь перейдем к рассмотрению вопроса 0.0.2. Ясно, что для особых подмножеств, А С Fg выполнено неравенство NAm ^ S < q для любых натуральных N и т, а это означает, что в случае особости, А натурального числа т, удовлетворяющего условиям вопроса 0.0.2, не существует. В диссертации доказывается существование т и получается верхняя оценка на это число для неособых подмножеств. Согласно теореме 5.4.2, для любых п и г число т можно оценить снизу так: т ^ п.

В статье [41] было доказано следующее утверждение (теорема 1.2).

Теорема 0.0.2. Для любого целого п > 1, любого 5 > 0 и s > 0, удовлетворяющих условиям 5 >1/{п — е) и 0 < е < п, существует целое.

N < 15−4п1п (2 + 1/?), удовлетворяющее условию: для любого подмножества, А С Fpтакого, что, А > р5 выполнено множественное равенство.

NAn = Fp.

Обобщение теоремы 0.0.2 для поля Fp2 доказано в параграфе 4.1. Мы выведем такую теорему.

Теорема 4.1.1. Для любого целого числа п ^ 2, для любых чисел г ?

0- 1), любого простого р и любого неособого множества, А такого, что 2.

А С Fp27 А > р^, мы имеем NAn = Fp2, где.

Г 10, если п 2;

I § (5 • 4я — 32) (3 + [log2 (i)]), если п ^ 3.

Доказательство теоремы 4.1.1 использует обобщение метода, предложенного в доказательстве теоремы 0.0.2. На основании тех же идей выводится теорема 4.4.1.

Теорема 4.4.1. Рассмотрим произвольное неособое подмножество, А С 3.

Fp3- такое, что, А ^ р^ для некоторого натурального п ^ 2 и действительного г? (0,1). Тогда имеет место соотношение:

NAn = Fp3, где.

N =.

10, если п — 2;

120(2 + [log2 (J)]), если п = 3;

5 • 4п — 32) (3 + [log2 (J)]), если п > 4.

Обобщая ключевые леммы из доказательства теоремы 4.4.1 на случай произвольного поля в параграфе 5.3, можно получить теоремы 5.3.2 и 5.3.1. Теорема 5.3.2. Для любого неособого подмножества, А С Fp4- такого, что, А > рп-е для некоторого натурального п ^ 2 и действительного е G (0,1), выполнено равенство.

МпАп = F р4, где.

10,.

Мп = < если п — 2 если п = 3 если п — 4 max {120 (2+ [log2 Q)]), 2400}, 8320(3+[log2 (f)l),.

20 480 (3 + [log2 (J)J) (^4n~1 — I) если n ^ 5.

Теорема 5.3.1. Для произвольного неособого подмножества, А С Fg, г ^ 3, такого, что > q^ для некоторого натурального п ^ г и действительного? Е (0,1), имеет место соотношение:

МпАп = F, где.

7'.

Мп =.

10 • 2[10¹−1]+1 (3 + [log2 (§)]) — I), если п = гl ^^ e/j/ о/' f]+1 (3 + [log2 (i)]) — I), еслип^г + 1.

Отметим, что в случае поля Fg, г ^ 5 задача о нахождении наименьшей степени множества, А в вопросе 0.0.2 сложна и в настоящий момент не решена. Возьмем произвольный примитивный элемент? ? F* и рассмотрим подмножество, А = Fp+^Fp. В доказательстве теоремы 5.4.2 установлено, что элементы {1,?,. линейно независимы. Тогда А1 С Fp-b?Fp-{-. для любого натурального 1 ^ / ^ г-2 и поэтому dim (Az) ^ I + 1. Если рассмотреть произвольное натуральное число п, § +? ^ п ^ г — 2, то выполнено неравенство |А| = р2 > qно dim (An) < n + 1 < г, а значит NAn ф F^ для любого натурального N, а если г = 2к + 1 для некоторого натурального к и п = к + 1, то dim (A2n3) = dim (Ar~2) < г — 1 и поэтому NA2n~z ф? q для любого натурального N. Однако, в параграфе 5.1 будет показано, что для т = 2п — 2 требуемое N всегда существует.

Теорема 5.1.1. Дано произвольное неособое подмножество, А С F5 такое, что, А > q^ для некоторого е € (0,1). Тогда выполнено равенство.

NA2n-2 = ^ где N.

10, если п = 2;

6n~3 max {30 • (3 + [log2 (?)]), 160 ¦ (1 + [log2 те])}, если n ^ 3.

Из теорем 4.1.1, 4.4.1, 5.3.2, 5.3.1 и 5.1.1 будут выведены следствия для двух подмножеств специального вида.

Все перечисленные результаты можно считать качественными свидетельствами роста подмножеств при их сложении с собой или возведении в степень. Это явление хорошо известно для конечных подмножеств натуральных чисел. Известная гипотеза Эрдеша и Семереди [42] утверждает, что max{AA, A + A} ^ |А|2~£.

В работе [42] доказано, что тах{|АА|, А + А} ^ для некоторого.

S > 0. Позже в ряде работ была найдена хгажняя граница на S: 5 ^ [43]),? > U [44]), 5>{ [45]), [46]), 5>-е{ [47]), где? > 0 — произвольное действительное число. Последние три результата установлены для подмножеств действительной оси. Аналогичных теорем для конечных колец не было до работы [28]. После этого было в этом направлении было сделано достаточно много. Здесь можно упомянуть работы автора совместно с Ж. Вургеном и С. В. Конягиным [48], статьи М. Гараева [49], [50] и [51], а также результаты Н. Каца и Ч. Шеня [52], [53]. Следует отметить, что результаты, аналогичные результатам диссертации получены в работах Д. Коверта, Д. Харта, А. Иосевича, Д. Коха, М. Руднева и И. Шолумоши [54], [55], [56] и [57]. В этих же статьях авторы находят целый ряд приложений этих результатов к различным вопросам, в частности к задаче Эрдеша о расстояниях и задаче Эрдеша-Фалконера. В работах [54], [55], [56] и [57] используются оценки тригонометрических сумм, при помощи которых авторы доказывают, что степени множеств являются базисами ограниченного порядка. Этот подход требует более жестких требований на нижнюю границу мощности множеств. Комбинаторные методы, используемые в диссертации, позволяют установить в некоторых случаях более сильные результаты. В работах [40], [48], [58], [59] и [60] доказываются различные версии неравенств на суммы-произведения в конечных полях, устанавливается их взаимосвязь с оценками тригонометрических сумм и рассматриваются их различные приложения. Данная работа продолжает упомянутые исследования.

Основные результаты диссертации опубликованы в работах автора [65], [66], [67] и [68].

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору С. В. Конягину за постановки задач и постоянное внимание. Автор также благодарен профессору Ж. Бургену (Университет Высших Исследований, Принстон, США) и профессору М. Рудневу (Университет Бристоля, Бристоль, Великобритания) за плодотворные обсуждения поставленных задач и постоянную поддержку. Автор выражает благодарность всему коллективу кафедры общих проблем управления механико-математического факультета МГУ, а также доктору физико-математических наук, члену-корреспонденту РАН Ю. В. Нестерен-ко и доктору физико-математических наук, доценту Н. Г. Мощевитину за поддержку и внимание.

1. Hardy G.H., Littlewood J.E., Some problems of «Partitio Numerorum». IV The singular series in Waring’s problem, Math. Z., vol. 12, 1922, pp. 161 — 188.

2. Hardy G.H., Littlewood J.E., Some problems of «Partitio Numerorum». VI Further researches in Waring’s problem, Math. Z., vol. 23, 1925, pp. 1 — 37.

3. Hardy G.H., Littlewood J.E., Some problems of «Partitio Numerorum». VIII The number Г (к) in Waring’s problem, Proc. London Math. Soc., ser. 2, vol. 28, 1928, pp. 518 542.

4. Виноградов И. М., Избранные труды, M., Издательство АН СССР, 1952.

5. Виноградов И. М., К вопросу о верхней границе для G (n), Изв. РАН СССР, сер. матем., 1959, т. 23, вып. 5, стр. 637—642.

6. Карацуба А. А., О функции G (n) в проблеме Варинга, Изв. АН СССР. Сер. матем., 1985, т. 49, вып. 5, стр. 935—947.

7. Vaughan R. С., Wooley Т. D., On Waring’s problem: some refinements, Proc. London Math. Soc., vol. 63, no. 1, 1991, pp. 35−68.

8. Вон P., Метод Харди-Литтлвуда, Москва, Мир, 1985.

9. Wooley Т. D., Large improvements in Waring’s problem, Ann. of Math., vol. 135, no. 1, 1992, pp. 131−164.

10. Шнирельман Л. Г., Об аддитивных свойствах чисел, Ростов н/Д, Изв. донец, политехи, ин-та, том 14, N 2−3, 1930, стр. 3 — 28.

11. Mann Н.В., A proof of the fundamental theorem on the density of sums of sets of positive integers, Annals of Math., ser. 2, vol. 43, 1942, pp. 523 — 527.

12. Карацуба, А А., Правильные множества по заданному модулю, Acta Matem. Et. Informat., Univ. Ostraviensis, 1998, v. 6, p. 129—134.

13. Bourgain J., Katz N., Tao Т., A sum-product estimate in finite fields and their applications, Geom and Funct. Anal, vol. 14, 2004, pp. 27—57.

14. Rudnev M., An improved estimate on sums of product sets, arXiv:0805. 2696vl, math.CO.

15. Виноградов И. M., Основы теории чисел, Москва-Ижевск, НИЦ «Регулярная и хаотическая динамика», 2005.

16. Erdos P., Graham R.L., Old and new problems and results in combinational number theory, Monograph. Enseign. Math., vol. 28, 1980.

17. Croot E.S., On some questions of Erdos and Graham about Egyptian fractions, Mathematika, 1999, vol. 46, pp. 359—372.

18. Sparlinski I.E., On a question of Erdos and Graham, Arch.Math.Basel, vol. 78, 2002, pp. 445−448.

19. Katz N. H., Shen Ch.-Y, Garaev's inequality in finite fields not of prime order, Online J. Anal. Comb., No. 3, Art. 3, 2008, 6 pp.

20. Covert D., Hart D., Iosevich А., К oh D., Rudnev M., Generalized incidence theorems, homogeneous forms, and sum-product estimates in finite fields, arXiv: 0801.0728v2, math.CO.

21. Hart D., Iosevich A., Solymosi J., Sum-product estimates in finite fields via Kloosterman sums, IMRN, vol. 2007, 2007, article ID: rmn007.

22. Hart D., Iosevich A., Koh D., Rudnev M., Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdos-Falconer distance conjecture, arXiv: 0707.3473v2, math.CA.

23. Hart D., Iosevich A., Sums and products in finite fields: an integral geometric viewpoint, arXiv: 0705.4256v4, math.NT.

24. Bourgain J., Mordell’s exponential sum estimate revisited, J. Amer. Math. Soc., vol. 18, 2005, pp. 477 499.

25. Bourgain J., More on the sum-product phenomenon in prime fields and its applications, International Journal of Number Theory, vol. 1, no. 1, 2005, pp. 1 32.

26. Bourgain J.} Estimates on exponential sums related to the Diffie-Hellman distributions, GAFA, vol. 15, 2005, pp. 1 34.

27. Tao TVu V., Additive combinatorics, Cambridge University Press, Cambridge, 2006.

28. Kneser M., Abschatzungen der asymptotischen Dichte von Summenmengen, Math. Z, vol. 58, 1953, pp. 459 484.

29. Шкредов И. Д., О некоторых аддитивных задачах, связанных с показательной функцией, Успехи мат. наук, т. 58, вып. 4(2003), стр. 165 — 166.

30. Burgess D.A., Elliott P.D.T.A., The average of the least primitive root, Mathematika, vol. 15, 1968, pp. 39 — 50. Работы автора по теме диссертации.

31. Глибичук А. А., Комбинаторные свойства множеств вычетов по простому модулю и задача Эрдеша-Грэхэма, Мат. Заметки, т. 79, 2006, стр. 384— 395.

32. Глибичук А. А. Свойства сумм и произведений подмножеств конечного поля простого порядка, Чебышевский сборник, том 8, вып. 2, 2007, стр. 30 43.

33. Глибичук А. А., Аддитивные свойства произведений подмножеств поля Fp2, Вестник Московского Государственного Университета. Серия l. Ma-тематика.Механика, № 1, 2009, стр. 3 — 8.

34. Глибичук А. А., Свойства степеней больших подмножеств в поле из pz элементов, депонировано в ВИНИТИ РАН 30.09.2008 г. № 769-В2008.