Свойства сумм и произведений подмножеств произвольного конечного поля тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В.ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 511.235.1

0034В4ЭТЭ

Глибичук Алексей Анатольевич

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

01.01.06 - математическая логика, высшая алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

/ ......

Москва 2009

003464973

Работа выполнена на кафедре общих проблем управления Механико-Математического факультета Московского государственного университета имени М. В. Ломоносова.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор Сергей Владимирович Конягин

доктор физико-математических наук, профессор Сергей Александрович Степанов

кандидат физико-математических наук, старший научный сотрудник Максим Александрович Королёв

Хабаровское отделение института прикладной математики Дальневосточного отделения Российской Академии Наук

Защита диссертации состоится 17 апреля 2009 г. в 16 ч. 45 м. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 10 марта 2009 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

Общая характеристика работы

Актуальность темы.

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

Гипотеза, называемая сейчас проблемой Варинга, была высказана им в 1770 г. Она формулируется так: доказать, что для любого натурального п > 2 существует число s(n) с тем свойством, что всякое натуральное число пред-ставимо в виде суммы п-х степеней натуральных чисел, причем количество слагаемых не превосходит s(n). Многие математики занимались этой проблемой и задачами, с нею связанными. Среди обширной литературы, посвященной проблеме Варинга и ее обобщениям, следует упомянуть работы Д.Гильберта1, Ю.В. Линника2, Л. Диксона3, С. Пиллаи4,Г. Харди и Д. Литт-лвуда5, И.М, Виноградова6, A.A. Карацубы7, Р. Бона6 и Т. Були9. Методы, предложенные в этих работах, зачастую использовались в других задачах и легли в основание новых математических теорий.

Определение 1. Рассмотрим произвольное полукольцо R. Множество А С R является базисом R порядка fee N, если каждый элемент х € R представим в виде xi + Х2 +... + Xk — где ij, х2,..., Хк € А, но существует такой элемент xq G R, что Х\ + хч +... + Xfe_i ф хо дая любых х\, xi,..., Хк-\ € А.

Таким образом, проблема Варинга может быть переформулирована следующим образом: для любого натурального n найдется такое число s(n), что множество п-х степеней целых неотрицательных чисел образует базис порядка, не превосходящего s(n), в полукольце целых неотрицательных чисел.

'Д. Гильберт, Избранные труди в двух томах, 1998, Москва, Факториал, с. 312 — 328.

2Ю.В. Линних, Элементарное решение проблемы Waring'a по методу Шпирелъмана, Матем. сб., т. 12(54), 1943, выл. 2, стр. 225 - 230

3L.E. Dickson, Researches on Waring'a problem, Carnegie Inst, of Washington Publications, vol. 464, 1936.

■'S. Pillai , On Waring's problem, Journal of Indian Math. Soc., ser. 2, -vol. 2, 1937, pp. 213 — 214.

5G.H. Hardy, J.E. Littlewood, A new solution of Waring's problem, Q.J. Math., vol. 48, 1919, pp. 272 — 293.

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

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

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

9T. D. Wooley, Large improvements in Waring's problem, Ann. of Math., vol. 135,1992, no. 1, pp. 131—164.

Если F, — поле порядка g, то множество п-х степеней ненулевых элементов F, образует подгруппу порядка -фщ мультипликативной группы F* поля. Поэтому для оценки числа слагаемых в проблеме Варинга достаточно оценить порядок базисности подгруппы H С F*. Такие оценки хорошо известны, если |Я| существенно больше ^/q. Используя метод С. А. Степанова10 можно получить нетривиальные оценки тригонометрических сумм11 по подгруппам F* для простого р и вывести из них нетривиальные оценки порядка базисности этой подгруппы, если ее мощность существенно больше р«. Известна также задача исследования базисных свойств подмножеств конечных полей, более общих, чем подгруппы, а именно, множеств последовательных степеней фиксированного элемента поля.12

Известно, что в поле Fp для фиксированных к £ N и е > 0 случайно сгенерированное множество мощности > р*+е является базисом порядка к с большой вероятностью (стремящейся к 1 при р —> оо). A.A. Карацуба13 строит конструктивные примеры базисов мощности, близкой к оптимальной, в кольце вычетов по модулю степени простого числа.

Недавний прогресс в исследовании базисных свойств относительно небольших специфических подмножеств конечных полей связан с появлением оценок сумм и произведений подмножеств таких полей. Вначале аналогичные оценки рассматривались для конечных подмножеств множества натуральных и действительных чисел.

Если А и В — подмножества конечного поля, то можно рассмотреть две операции: сложение А + В :— {a -f Ь : а € А, Ь G В} и умножение А ■ В — А • В := {ab : а €Е А,Ь € В}. Определим для некоторого к £ N

и множества А его кратную сумму к А = А + А... + А и к- ю степень это-

v *

к

го подмножества Ак = А • А •... • Д. Гипотеза П. Эрдеша и Э. Семереди14

к

утверждает, что для любого конечного непустого подмножества Л С N и

10С. А. Степанов,

О числе точек гиперэллиптической кривой над простым конечным полем, Известия РАН СССР.Серия математическая, т. 33, 1969, стр. 1171 — 1181.

"С. В. Конягин, Оценки тригонометрических сумм по подгруппам и суммы Гаусса, IV международная конференция «Современные проблемы теории чисел их приложениякАктуальяые проблемы.Часть III, стр. 86 - 114.

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

Z. Rudnick, A. Zaharescu, The distribution of spaces between small powers of a primitive mot, Israel Journal of Math., vol. 120, 2000, pp. 271 - 287.

M. Vâjâitu, A. Zaharescu, Differences between powers of a primitive root, International Journal of Mathematical Sciences, vol. 29, 2002, pp. 325 — 331.

»A.A.

Карацуба, Лравилътше множества no заданному модулю, Acta Matern. Et. Informât., Univ. Ostraviensis, 1998, v. 6, p. 129—134.

14P. Erdôs, E. Szeraerédi, On sums and products of integers, Studies in Pure Mathematics, Birkhauser, Basel, 1983, pp. 213 - 218.

произвольного действительного числа е > 0 верно неравенство:

тах{|Л • А\, |А + Л|} > с(е)|А|2-£, ф) > 0.

В той же работе доказано, что тах{|А • А\, jА + А|} > с\А\1+5,с > 0 для некоторого 6 > 0. Позже была получена версия последнего неравенства с точными константами, которые в ряде работ последовательно улучшались. Наилучшая в настоящий момент оценка доказана И. Шолумоши15. Она имеет вид: шах{|Л • А\, |А + Л]} > |А|з~Е, где е > 0 — произвольное действительное число, и верна также для конечных подмножеств множества комплексных чисел. Аналогичных теорем для конечных колец не было до работы Ж. Бургена, Н. Катца и Т. Тао16, которые показали, что, если А — подмножество поля порядка р для некоторого простого р, удовлетворяющее условию ps < \А\ < р1'6, где 5 > 0 — произвольное действительное число, то тах{|А -А\, |Л + А\} > с\А\1+а, причем константы си а зависят только от S. Затем Ж. Бурген и С. В. Конягин17 (вторая работа выполнена в соавторстве с диссертантом) получили аналогичную оценку, предполагая, что А удовлетворяет более слабому условию: \А\ < pl~s для некоторого действительного S > 0. Из результата этих статей вытекает, что порядок базисности мультипликативной подгруппы Н С F*, |Я| > ps, ограничена сверху величиной, зависящей только от 5. Аналогичные вопросы для подгрупп произвольных конечных полей оставались открытыми.

В ряде работ Ж. Бургена18 получены обобщения теоремы о суммах и произведениях подмножеств и найдены многочисленные приложения этих результатов к задачам оценивания модулей различных тригонометрических сумм, проблемам р - адической теории, алгебраической теории чисел, криптографии и другим разделам математики. X. Хельфготт19 использует неравенства на суммы и произведения подмножеств для получения оценок на диаметр графа Кэли. Оценки на а в неравенстве для сумм и произведений

15J. Solymosi, Bounding multiplicative energy by the sumset, arXiv:0806.1040v3, math.CO.

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

17J. Bourgain, S.V. Konyagin, Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order, C. R. Math. Acad. Sci. Paris, vol. 337, 2003, no. 2, pp. 75-80.

J. Bourgain, A. GHbichuk, S. Konyagin, Estimates for the number of sums and products and for exponential sums in fields of prime order, Journal of London Math. Society, vol. 73, N.2, 2006, pp. 380 — 398.

18J. Bourgain, Multilinear exponential sums in prime fields under optimal entropy conditions on the sources, to appear in Geom and Funct. Anal.

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

J. Bourgain, 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.

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

19H.A. Helfgott, Growth and generation in 5Lj(Z/pZ), Annals of Mathematics, ser. 2, vol. 167, no. 2, 2008, pp. 601 — 623.

были улучшены в работах Гараева20, Катца и Шена21.

Методы, разработанные в статье Ж. Бургена, Н. Катца и Т. Тао, выявляют взаимосвязь проблемы Эрдеша-Семереди для конечных полей с задачей о базисных свойствах множества произведений ограниченного количества элементов подмножества А конечного поля. Последняя задача является основным объектом исследования настоящей работы. Если Fp — поле простого по-рядкар и А — его подмножество, удовлетворяющее условию |Л| > р?+£, е > О,

99

то из классических оценок тригонометрических сумм нетрудно получить, что множество попарных произведений элементов множества А образует базис, порядок которого не превосходит некоторого числа, зависящего только от е. Если же множество А имеет меньшую мощность, то для исследования базисных свойств множеств А • А, А ■ А ■ А,... приходится использовать методы и результаты работ, связанных с суммами и произведениями подмножеств конечных полей. Данная работа продолжает упомянутые исследования.

Цель работы.

Цель настоящей работы — исследовать базисные свойства множества произведений ограниченного количества элементов из подмножества конечного поля при минимальных ограничениях на его мощность и структуру, и в частности, множества последовательных степеней фиксированного элемента.

Научная новизна.

В диссертации решены следующие новые задачи:

1. Доказано, что любой элемент конечного поля представим в виде суммы не более 16 слагаемых из произведения двух больших подмножеств этого поля.

2. Доказано, что в поле Fp, где р — простое число, произведение произвольного количества множеств при минимальном ограничении на их мощность является базисом ограниченного порядка.

20М. Z. Garaev, The sum-product estimate for large subsets of prime fields, Proc. Amer. Math. Soc., vol. 136, no. 8, 2008, pp. 2735-2739.

M. Z. Gaiaev, An explicit sum-product estimate in Fp for subsets of incomparable sizes, The Electronic Journal of Combinatorics, vol. 15, 2008, #Я 58.

M. Z. Garaev, An explicit sum-product estimate in Fp, Int. Math. Res. Not. IMRN, no. 11, Art. ID rnm035, 2007, 11 pp.

21 N. H. Katz, Ch.-Y. Shen, A slight improvement to Garaev's sum product estimate, Proc. Amer. Math. Soc., vol. 136 , no. 7, 2008, pp. 2499-2504.

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

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

3. Доказано, что произвольная степень подмножества конечного поля при минимальных ограничениях на его мощность и структуру является базисом, порядок которого может быть оценен числом, не зависящим от характеристики этого поля.

Основные методы исследования.

В работе используются методы арифметической комбинаторики, теории полей и линейной алгебры.

Теоретическая и практическая ценность работы.

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

Апробация работы.

Результаты диссертации докладывались на следующих научно - исследовательских семинарах и конференциях:

1. Кафедральный семинар кафедры теории чисел под руководством д.ф-м.н., чл.-корр. РАН Ю.В. Нестеренко и д.ф.-м.н., профессора Н. Г. Мощеви-тина.

2. Семинар «Аналитическая теория чисел» под руководством д.ф.-м.н., проф. A.A. Карацубы.

3. Научно-исследовательский семинар по алгебре, проводимый кафедрой высшей алгебры МГУ им. Ломоносова.

4. Семинаре по теории функций под руководством к.ф.-м.н., доц. В.Б. Демидовича, д.ф.-м.н., проф. С.В.Конягина и к.ф.-м.н., доц. A.C. Кочурова

— неоднократно, по мере получения результатов.

5. Международная конференция по аддитивной комбинаторике (Монреаль, Канада, 6 — 12 апреля 2006 г.).

6. Международная конференция «Clay-Fields Conference on Additive Combinatorics, Number Theory, and Harmonic Analysis» (Торонто, Канада, 5

- 13 апреля 2008г.).

7. Специальная программа по арифметической комбинаторике, проходившей в Институте Высших Исследований(Принстон, США, 23 сентября — 23 декабря 2007г.).

Публикации.

Основное содержание диссертации было опубликовано в четырех работах, список которых приведен в конце автореферата [1] — [4].

Структура и объем диссертации.

Диссертация состоит из введения и 5 глав и списка литературы. Полный объем диссертации — 84 страницы, библиография включает 68 наименований.

Краткое содержание работы

Во введении обсуждаются предварительные сведения и формулируются основные определения. Через обозначается мощность множества X. Если ^ = рг является степенью простого числа р, то обозначает поле из д элементов. Для множеств Х,У с¥9 и. натурального к вводятся обозначения

ХУ = {ху: х€Х,у 6 У},

Хк = {х1...хк : хь...,хкеХ),

кХ ~ {XI-1-----ЬХк : х1,...,хк€ X}.

Множество А С Р, названо особым, если оно покрывается каким-либо множеством вида {ск : 5 € 5}, где й е 5 — собственное подполе поля и неособым в противном случае. Мультипликативный порядок огс!дх произвольного элемента х € \ {0} определяется как наименьшее натуральное I такое, что х1 = 1.

Содержание главы 1.

В первой главе мы обсуждаем предварительные сведения и формулируем основные определения. В параграфе 1.1 определяется размерность произвольного подмножества конечного поля и доказывается нижняя оценка на размерность степени неособого подмножества. Также устанавливаются структура подмножеств X, У С ¥д, удовлетворяющих условию |-Х-ЬУ| = |Х|, где символ обозначает мощность подмножества X. В параграфе 1.2 доказываются основные оценки сумм-произведений, которые можно вывести, используя свойства множества отношений разностей. Здесь также доказано, что для данного неособого подмножества I С = рг, его степень Хг является базисом порядка, не превышающего д — 1. Легко понять, что любая степень особого подмножества не может быть базисом. В параграфе 1.3 формулируются классические оценки на сумму произвольных подмножеств: неравенство Коши-Давенпорта, неравенство треугольника Ружи и неравенство Кнессера. Кроме того, доказывается две оценки на сумму подмножеств, использующиеся в доказательстве ряда результатов работы.

Содержание главы 2.

Назовем множество X симметричным, если оно вместе с каждым своим элементом х содержит элемент —х, и антисимметричным, если из включения х € X следует, что —х £ X. Во параграфе 2.1 доказываются такие утверждения.

Теорема 1. Если X С F, и Y С F? таковы, что Y антисимметрично и \X\\Y\>g, mo8{XY) = fr

Теорема 2. Рассмотрим подмножества X С F? и Y С Fg такие, что Y симметрично. Если выполнено неравенство > q, то 8(ХУ) = Ff.

Из теорем 1 и 2 выводятся такие следствия.

Следствие 1. Если Н - мультипликативная подгруппа F?\ {0}г |Н| > y/q, то 8Н = Fq.

Следствие 2. Пусть A - {gx : х е N, 0 < х < 2[y/q\}, где g 6 Fg \ {0} -некоторый элемент такой, что ordqg > ^/q. Тогда 8А — Fq.

Кроме того, в этом параграфе устанавливается, что условие |Х||У| > q в теоремах 1 и 2 является неулучшаемым. В параграфе 2.2 из этих теорем выводятся такие результаты.

Теорема 3. Если X С Fg \ {0} — произвольное подмножество такое, что 1*1 > 0 + 41) у/я. mo8(X2)=Fq.

Теорема 4. Рассмотрим произвольные подмножества X, Y С Fq такие, что l^rflVI > q. Тогда выполнено равенство 16(ЛГК) = Fg.

Теорема 4 была улучшена М. Рудневым23. Он показал, что при тех же ограничениях на множества X и Y выполнено равенство 10(ХУ) = Fg. Следует отметить, что Д. Коверт24, Д. Харт25, А. Иосевич20, Д. Кох, М. Руднев27, И. Шолумоши, М. Гараев, В. Гарсия и С.В. Конягин28 в своих работах находят различные приложения теоремы 4 к ряду вопросов, в частности к задаче

"м. Rudiiev, An improved estimate on sums of product sets, arXiv:0805. 2696vl, math.CO.

2iD. Covert, D. Hart, A. Iosevich, D. Koh, M. Rudnev, Generalized incidence theorems, homogeneous forms, and sum-product estimates in finite fields, arXiv: 0801.0728v2, math.CO.

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

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

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

"M. Rudnev, An improved estimate on sums of product sets, arXiv:0805. 2696vl, math.CO. г8М. Гараев, В. Гарсиа, С.В. Конягин, Проблема Барита с т-функцией Рамануджапа, Известия РАН. Серия математическая, т. 72, 20(18, №1, стр. 39-50.

Эрдеша о расстояниях, задаче Эрдеша-Фалконера и проблеме Варинга с т-функцией Рамануджана.

В параграфе 2.3 получается приложение теорем 1-4 к задаче Эрдеша-Грэхэма29, который формулируется так: существует ли для любого е > О такое к(е) € N, что для любого достаточно большого простого р и для любого целого с существует к < к(е) попарно различных целых чисел таких, что 1 < Xi < р*, г — 1,2,..., к, и

к

^xf1 = c{mod р), »=i

где запись х^1 обозначает наименьшее положительное целое такое, что х^х{ = 1 (mod р)7 Доказан такой результат.

Теорема 5. Для любого е > 0, для любого достаточно большого простого р и для любого класса вычетов a(mod р) существует положительные попарно различные натуральные числа xi,...,xff К Р£, где N = 8 ([j 4-+ l)2, такие, что ^ ^

as--1-----1--(mod р).

Xi Xff

Содержание главы 3.

В параграфе 3.1 доказываются оценю! сумм-произведений, необходимые для доказательства основного результата главы 3. В параграфе 3.2 выводится основной результат, который формулируется следующим образом.

Теорема 6. Для любых подмножеств А\,А2,... ,Ап С Fр,п > 2, таких, что > 2,1 < i ^ п, и

\А1\.\А2\-....\Ап\>р1+*

для некоторого е > 0, мы имеем

N(A1-A2-...-An)=¥p,

где

(10, если п = 2;

10 • max {1,24 ([log2 (*)] + 1)} , если п = 3;

1б"-2 • тах{1120,320(—11 - [log2(e(n - 2))])}, если п > 3.

Теорема 6 обобщает теорему 4 для поля Fp.

ИР. Erdös, R.L. Graham, Old and new problems and results in combinational number theory, Monograph. Enseign. Math., voi. 28,1980.

jv=/ i0-

Содержание главы 4.

В параграфе 4.1 выводится такой результат о базисных свойствах произвольной степени достаточно большого неособого подмножества конечного поля.

Теорема 7. Для любого целого числа п ^ 2, для любых чисел е € (0; 1), любого простого р и любого неособого множества А такого, что А С Fp2, |Л| > р^, мы имеем N(An) = где

если п = 2; 32) (3 + [log2 (f)]), еслип^ 3.

В параграфе 4.2 доказывается нижняя оценка на мощность множества 3(Х2) — 3(Л'2) для любого неособого подмножества X Ç Fg. В параграфе 4.3 получается нижняя граница на мощность множества NkXk — NkXk, где XÇF„g= рг и Nk = /с > 3. Основные результаты параграфов 4.2 и

4.3 используются в доказательствах всех последующих теорем. В параграфе

4.4 устанавливается такая теорема.

Теорема 8. Рассмотрим произвольное неособое подмножество А С Fp3, такое, что |Л| ^ для некоторого натурального п ^ 2 и действительного е € (0,1). Тогда имеет место соотношение:

(10, если п = 2;

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

|(5 • 4" — 32) (3 + [log2 (j)]), если п^ 4.

Из теорем 7 и 8 выводятся следствия, аналогичные следствиям 1 и 2.

Содержание главы 5.

В параграфе 5.1 доказывается, что произвольное неособое подмножество конечного поля в некоторой степени, зависящей только от его мощности, является базисом ограниченного порядка. А именно, установлен такой результат.

Теорема 9. Дано произвольное неособое подмножество AcF, такое, что |j4] > qñ^ для некоторого е 6 (0,1). Тогда выполнено равенство

N(A2n~2) = Fj,

где

если п = 2;

> тах {30 • (3 + [log2 (¿)] ), 160 • (1 + [log2 n])} , если n > 3.

\ б""3

Отметим, что показатель степени 2п — 2, вообще говоря, неулучшаем. Из теоремы 9 выводятся такие следствия для множеств специального вида.

Следствие 3. Для любой подгруппы по умножению Н С Fg, не лежащей ни в каком нетривиальном подполе ¥q и удовлетворяющей условию \Н\ > qдля некоторого натурального п ) 2 « действительного е > 0, имеет место равенство NH = F?, где N — число, определенное в формулировке теоремы 9.

Следствие 4. Рассмотрим произвольное натуральное число п ^ 2 и любое действительное е > 0. Тогда для любого натурального k > + 1; произвольного элемента д, не лежащего ни в каком нетривиальном подполе Fq, такого, что ord9g ^ к, и множества А = {дх : 0 < х ^ к(2п — 2)} выполнено равенство NA = F?, где N — число, определенное в формулировке теоремы 9.

Из следствия 3 вытекает, что если Н CF, - подгруппа, не лежащая ни в каком нетривиальном подполе Fq и удовлетворяющая условию \Н\ > qs, то NH = Fg,iV = N(r,6). Аналогичное утверждение при более сильных ограничениях на подгруппу Я вытекает из результата Ж. Бургена и М. Ч. Чанг.30

В параграфе 5.2 доказываются необходимые следствия из оценок параграфов 4.2 и 4.3, которые используются в параграфе 5.3 для доказательства теоремы 10.

Теорема 10. Для произвольного неособого подмножества А С F„r ^ 3, такого, что |Л| > для некоторого натурального и действительного е € (0,1), имеет место соотношение:

ЩА»)=Щ, (1)

где

N = Í 10 • 2^]+1 (3 + [Iog2 (?)]) (ЬГ1 - i) . если п = r¡ \ 10 • (3 + [logí (i)]) - i) , если n > r + 1.

Из теорем 4 и 10 вытекает, что равенство (1), где N — N(n, е) справедливо для любого неособого подмножества Л С F^ такого, что |Л| > р7^7, в случаях п=2ип^4. Однако, аналогичное утверждение верно и в случае п = 3, что доказано в параграфе 5.3. Таким образом, равенство (1), где N = N(n,r,e), справедливо при г<4и, вообще говоря, несправедливо при г > 4.

30J. Bcmrgain, М.С. Chang, A Gauss sum estimate in arbitrary finite field, C.R. Acad. Sei. Palis, Ser. 1, vol. 342, 2006, pp. 643 - 646.

В параграфе 5.4 доказывается, что степень п у множества Ап в теоремах 7, 8 и 10 неулучшаема, а именно, устанавливается справедливость такой теоремы.

Теорема 11. Для любых натуральных чисел п ^ 2, г ^ 1, действительного числа 0 < е < 1 и любого натурального N существуют простое число р и подмножество AÇ¥g,q = рг, такое, что |Л| > q^ и N(An~1) ф Fe.

Благодарности.

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

Список публикаций по теме диссертации.

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

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

[3] A.A. Глибичук, Аддитивные свойства произведений подмножеств поля ï>, Вестник Московского Государственного Университета. Серия 1.Математика.Механика, №1, 2009, стр. 3 — 8,

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

Издательство ЦПИ при механико-математическом факультете МГУ имени М. В. Ломоносова

Подписано в печать £Ц ¿У, Формат 60x90 1/16. Усл. печ. л. {,0 Тираж {'ОО экз. Заказ /3

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение

1 Предварительные технические результаты.

1.1 Размерность подмножеств, их аддитивная структура.

1.2 Множество отношений разностей.

1.3 Рост подмножеств при их сложении.

2 Произведения двух подмножеств конечного поля.

2.1 Симметричный и антисимметричный случай.

2.2 Общий случай.

2.3 Задача Эрдеша-Грэхэма.

3 Произведения многих подмножеств поля вычетов по простому модулю.

3.1 Предварительные результаты.

3.2 Доказательство основного результата.

4 Степени больших подмножеств полей размерности 2 и 3.

4.1 Степени подмножеств поля Fp2.

4.2 Аналог леммы 4.1.3 для произвольного поля.

4.3 Аналоги леммы 4.1.4 для произвольного поля.

4.4 Доказательство результата для поля Fp3.

5 Свойства степеней подмножеств произвольных полей.

5.1 Теорема о больших подмножествах произвольного поля.

5.2 Обобщение лемм 4.1.6 и 4.1.7 на случай произвольного поля.

5.3 Степени подмножеств поля Fp4 и свойства больших степеней подмножества конечного поля.

5.4 Неулучшаемость степени подмножеств в теоремах 4.1.1, 4.4.1, 5.3.1 и 5.3.2.

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

Рассмотрим некоторое непустое множество 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 с подмножеством h -f- А = {/г} + А. Операция умножения множеств всегда имеет больший приоритет, чем сложение, поэтому, например, запись тА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),

20480 (3 + [log2 (J)J) (^4n~1 - I) если n ^ 5.

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

МпАп = F, где

7'

Мп =

10 • 2[10^1-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.