Содержание к диссертации
Введение
1 Предварительные технические результаты. 12
1.1 Размерность подмножеств, их аддитивная структура 12
1.2 Множество отношений разностей 14
1.3 Рост подмножеств при их сложении 22
2 Произведения двух подмножеств конечного поля . 25
2.1 Симметричный и антисимметричный случай 25
2.2 Общий случай 28
2.3 Задача Эрдеша-Грэхэма 31
3 Произведения многих подмножеств поля вычетов по простому модулю . 36
3.1 Предварительные результаты 36
3.2 Доказательство основного результата 39
4 Степени больших подмножеств полей размерности 2 и 3. 45
4.1 Степени подмножеств поля Fp2 45
4.2 Аналог леммы 4.1.3 для произвольного поля 51
4.3 Аналоги леммы 4.1.4 для произвольного поля 54
4.4 Доказательство результата для поля рз 59
5 Свойства степеней подмножеств произвольных полей . 65
5.1 Теорема о больших подмножествах произвольного поля 65
5.2 Обобщение лемм 4.1.6 и 4.1.7 на случай произвольного поля 68
5.3 Степени подмножеств поля р4 и свойства больших степеней подмножества конечного поля 71
5.4 Неулучшаемость степени подмножеств в теоремах 4.1.1, 4.4.1, 5.3.1 и 5.3.2 77
Литература 81
- Размерность подмножеств, их аддитивная структура
- Симметричный и антисимметричный случай
- Аналог леммы 4.1.3 для произвольного поля
- Степени подмножеств поля р4 и свойства больших степеней подмножества конечного поля
Введение к работе
Задачи, рассматриваемые в диссертации, относятся к бурно развивающемуся в настоящее время разделу теории чисел, называемому "Аддитивной комбинаторикой". Впечатляющие результаты, достигнутые в этой области, обусловлены разнообразием методов, используемых при изучении задач из этой области. Данная работа использует преимущественно комбинаторные методы. Результаты диссертации так или иначе связаны с аналогами проблемы Варинга и с задачами изучения роста суммы и произведения подмножеств конечных полей.
Рассмотрим некоторое непустое множество X с определенной на нем бинарной операцией * : А х В —> X. Тогда можно определить операцию * на парах подмножеств X следующей формулой: А* В = {а * 6 : а Є Л, b В}. В частности, если Ли В — подмножества кольца, то можно рассмотреть две операции на подмножествах: сложение А -\- В :— {а -\- b : а Є Л, b Є В} и умножение АВ — Л В := {ab : а Є Л, Ъ Є В}. Определим для некоторого & Є N и множества Л его кратную сумму к А = А-\- А... + А, к-ю степень
к ,_ этого подмножества Ак = Д Л ... Д и операцию умножения произволь-
к ного элемента кольца b на подмножество Ъ * Л = {&} Л. Иногда, если это не
приведет к путанице в обозначениях, знак * будет отпускаться.
Мы будем в дальнейшем обозначать мощность множества Л следующим образом: \А\. В качестве кольца будет рассматриваться конечное поле из q = рг элементов для произвольного простого р. Оно будет обозначаться через q. Для некоторого множества Y С Fq определим множество его обратимых элементов Y* :— Y \ {0}. Ниже всегда будет предполагаться, что р — некоторое простое число. Так как произвольное конечное поле характеристики р содержит подполе, изоморфное р, то мы без дополнительных оговорок будем считать, что Fp С F?. Рассматривая произвольный элемент х Є F*, мы можем определить его мультипликативный порядок ordga; как наименьшее натуральное / такое, что х1 = 1. Для любого действительного у символом [у] обозначается его целая часть, т.е. наибольшее целое число, не превосходящее у, а {у} обозначает дробную часть у.
Определим также операцию сложения произвольного элемента h Є q
с подмножеством h + A = {h} + А. Операция умножения множеств всегда имеет больший приоритет, чем сложение, поэтому, например, запись тА1 для некоторых натуральных т и I следует понимать как ш-кратную сумму 1-й степени множества А.
Гипотеза, называемая сейчас проблемой Варинга, была высказана им в 1770 г. в следующем виде:
Доказать, что всякое натуральное число является суммой не более четырех квадратов, девяти кубов, девятнадцати биквадратов и т.д.
По-видимому, предполагалось, что для любого натурального n ^ 2 существует число s(n) с тем свойством, что всякое натуральное число представимо в виде суммы п-х степеней положительных чисел, причем количество слагаемых не превосходит s. Наименьшее s(ri), обладающее таким свойством принято обозначать д(п). Над оценками на д(п) работали много ученых. Здесь следует отметить имена Лагранжа( [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 + 0(1)). Функцию G(n) можно тривиально оценить снизу так: G(n) ^ п. Последнее неравенство означает, что граница, полученная Були, близка к оптимальному своему значению.
Определение 0.0.1. Рассмотрим произвольное полукольцо R. Множество А С R является базисом R порядка к, если каждый элемент х Є R представим в виде Х\ + Х2 + + Хк = х% где хі, Х2, , Xk Є Л, но существует такой
Элемент Xq Є -R, ЧТО ^1+^2 + .-.+ Xk-l ф Xq ДЛЯ ЛЮбыХ Хі, Ж2, . . - , Xfr-l Є А.
Мы будем обозначать порядок базиса А символом к(А).
Л.Г. Шнирельман [25] изучал проблему суммирования последовательностей натуральных чисел общего вида, сведения о которых касаются лишь определенной им плотности расположения в них членов. Неулучшаемая оценка порядка базиса подмножества N U {0} через его плотность вытекает из теоремы Г.Б. Манна [26]. Аналогичный результат для порядка базиса подмножества р выводится из теоремы Коши-Давенпорта (теорема 1.3.1).
Известно, что в поле р для фиксированных к Є N и є > 0 случайно сгенерированное множество мощности > р~+є является базисом порядка А; с большой вероятностью (стремящейся к 1 при р —» со). В работе [27] А.А. Карацуба строит конструктивные примеры базисов мощности, близкой к оптимальной, в кольце вычетов по модулю степени простого числа.
Определение 0.0.2. Подмножество X С q называется особым, если существует элемент d Є q и нетривиальное подполе S С Fg такие, что X С dS. В частности, любое подмножество Y, \Y\ = 1, является особым.
В этой работе будет изучаться следующие задачи:
Вопрос 0.0.1. Даны натуральное число п и действительное є > 0. Рассмотрим также п подмножеств А\, Ач,..., Ап С р таких, что -\А2\-... \Ап\ > р1+. Доказать, что для некоторого натурального N = N(n, є) верно равенство NAi А2-...-Ап = р.
Вопрос 0.0.2. Для любого натурального п ^ 2, действительного числа є Є (0,1) и неособого подмножества А С q,q = рг, такого, что \А\ > д"^, найти такое натуральное число т — т{уь,г), что существует натуральное N = N(n, г, є) для которого выполнено равенство NAm = F^.
Согласно лемме 1.2.1, равенство NAm — q верно для любого неособого множества, если положить N — q — 1ит — г. Нас же интересуют значения N и т, не зависящие от р.
Первые оценки на мощность кратных сумм и степеней в конечных полях были получены в известной работе Ж. Бургена, Н. Катца и Т. Тао [28]. Большинство работ в этом направлении, написанных позже, а также результаты диссертации, так или иначе используют идеи этой статьи.
Определение 0.0.3. Подмножество X является симметричным, если
х = -х.
Определение 0.0.4. Назовем подмножество X антисимметричным, если X П (-Х) = 0.
Следующие три теоремы, доказанные в главе 2, используются в доказательствах основных результатов диссертации и также интересны сами по себе.
Теорема 2.1.1. Если X С q и Y С q таковы, что Y антисимметрично и \X\\Y\ > q, то 8XY = q.
Теорема 2.1.2. Рассмотрим подмножества X C.q uY Q q такие, что Y симметрично. Если выполнено неравенство \X\\Y\ > q, то 8XY = Fg.
Теорема 2.2.3. Рассмотрим произвольные подмножества X,Y С q такие, что |Х||У| > q. Тогда выполнено равенство 16XY — q.
Теорема 2.2.3 была улучшена М. Рудневым [29]. Он получил следующий результат.
Теорема 0.0.1. Рассмотрим произвольные подмножества X, Y С q такие, что \X\\Y\ > q. Тогда выполнено равенство 10XY = q.
Отметим, что в случае поля р при наличии более сильных предположений на мощности множеств X и Y, а именно, |Х||У| > р1+є для некоторого є > 0,-равенство NXY = р, 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 можно применить к одной из задач в поле р, сформулированных Эрдешем и Грэхэмом в работе [31]. Она формулируется так.
Существует ли для любого є > 0 такое к (є) Є N, что для любого достаточно большого простого р и для любого целого с существует к < к(є) попарно различных целых чисел Хі таких, что 1 ^ хг^ рє, г = 1,2,..., к, и
^xr1 = c(modp), (1)
г=1
где здесь и в дальнейшем xj1 - наименьшее положительное целое такое, что х^гХі = l(modp)7
Крут [32] показал, что можно выбрать к < log3+0^ р попарно различных чрЇсєл на интервале [1,рє], чтобы выполнялось равенство (1).
Следующим результатом в этом направлении была работа И.Е. Шпарлин-ского [33]. Он использует оценки тригонометрических сумм А.А.' Карацубы ( [34], [35], [36]) и устанавливает, что для любого є > 0 и для .достаточно большого р можно выбрать к = 4є-3 + О (є-2) попарно различных чисел Хі, г = 1,..., к, таких, что 1 ^ Х{ ^ ре и выполняется равенство (1).
В параграфе 2.3 будет доказано, что
Теорема 2.3.1. Для любого є > 0, для любого достаточно большого про
стого р и для любого класса вычетов a(modp) существует положительные
попарно различные целые х\,..., х2\ ^ рє, где N ~ 8 ([^ + |] + і) , такие,
что і і
а = \- -\ (modp).
Х\ Х]у
Таким образом, теорема 2.3.1 улучшает результат И.Е. Шпарлинского.
Если бы аналог теоремы 2.3.1 удалось доказать при N ^ |, где с - некоторая константа, то была бы доказана гипотеза А.А. Карацубы, сформулированная в работе [37] на стр. 83 (смотри также [38], стр. 225).
Крут [39] доказал, что для любого є Є (0,1] и для любой степени к ^ 1 существует N = N(k,e) такое, что для любого достаточно большого простого р и для любого класса вычетов a{modp) существует положительные целые хі,..., гедг ^ рє, удовлетворяющие сравнению:
а = (хг)-1 + + (^у)-1 (modp).
При помощи техники, развитой Ж. Бургеном [40], в главе 3 доказывается обобщение теорем 2.2.3 и 0.0.1.
Теорема 3.2.1. Для любых подмножеств А\, А2,..., Ап С Fp, п ^ 2, таких, что \Аі\ ^ 2,1 ^ і ^ п и
\Аг\-\А2\-...-\Ап\>р1+
для некоторого г > 0, мы имеем
NA1-A2....-An = Fp,
{
10, если п = 2;
10-max{l,24([log2 (J)] + l)}, еслип = 3;
16n-2 max{1120,320(-11 - [log2(e(rc - 2))])}, если n > 3.
Теперь перейдем к рассмотрению вопроса 0.0.2. Ясно, что для особых подмножеств А С Fq выполнено неравенство ІЛМ"1! = |iL>| < q для любых натуральных N и т, а это означает, что в случае особости А натурального числа 777., удовлетворяющего условиям вопроса 0.0.2, не существует. В диссертации доказывается существование т и получается верхняя оценка на это число для неособых подмножеств. Согласно теореме 5.4.2, для любых лиг число 777, можно оценить снизу так: т^ п.
В статье [41] было доказано следующее утверждение (теорема 1.2).
Теорема 0.0.2. Для любого целого п > 1, любого 5 > 0 и є > 0, удовлетворяющих условиям 5 > 1/(п — є) и 0 < є < п, существует целое
/У<15-4п1п(2 + 1/є),
удовлетворяющее условию: для любого подмножества А С Fp; такого, что \А\ > р5 выполнено множественное равенство
NAn = Fp.
Обобщение теоремы 0.0.2 для поля Fp2 доказано в параграфе 4.1. Мы выведем такую теорему.
Теорема 4.1.1. Для любого целого числа п ^ 2, для любых чисел є Є (0; 1), любого простого р и любого неособого множества А такого, что А С Fp27 \А\ > р~Е, мы имеем NAn = Fp2, где
N = s 5
10, если п = 2;
6 (5 4П - 32) (3 + [log2 (і)]) , если п^З.
Доказательство теоремы 4.1.1 использует обобщение метода, предложенного в доказательстве теоремы 0.0.2. На основании тех же идей выводится теорема 4.4.1.
Теорема 4.4.1. Рассмотрим произвольное неособое подмножество А С
Fp3; такое, что \А\ ^ р^ для некоторого натурального п ^ 2 и действительного є Є (0,1). Тогда имеет место соотношение:
Fp3,
10,
если п = 2;
N = { 120(2 + [log2 (J)]), если п = 3;
(5 4П - 32) (3 + [log2 (]) , если п > 4.
Обобщая ключевые леммы из доказательства теоремы 4.4.1 на случай
произвольного поля в параграфе 5.3, можно получить теоремы 5.3.2 и 5.3.1.
Теорема 5.3.2. Для любого неособого подмножества А С р4, такого,
что \А\ > р«^ для некоторого натурального п ^ 2 и действительного є Є (0,1), выполнено равенство
МпАп = Fp4,
10,
если п — 2
Мп= {
8320(3+[log2(f)"
20480 (3+[log2(i)])(^
max {120 (2 + [log2 (]) , 2400} , если п = 3
если п — 4; |) е/ш n ^ 5.
Теорема 5.3.1. Для произвольного неособого подмножества А С q, г ^
3; такого, что \А\ > q^1 для некоторого натурального п ^ г и действительного є Є (0,1), имеет место соотношение:
MnAn = Fq,-
Мп =
10 2^М+1 (3 + [log2 ()]) &4Г-1 10.21=^1^(3+^(])^1
если п — г; если п ^ г + 1.
Отметим, что в случае поля Fg, г ^ 5 задача о нахождении наименьшей степени множества А в вопросе 0.0.2 сложна и в настоящий момент не решена. Возьмем произвольный примитивный элемент Є F* и рассмотрим подмножество Л = Fp+Fp. В доказательстве теоремы 5.4.2 установлено, что элементы {1,,... ,г-1} линейно независимы. Тогда А1 С FP+FP+.. .+*FP для любого натурального 1 ^/^г-2и поэтому &\т(А1) ^ / + 1. Если рассмотреть произвольное натуральное число п, + є ^ п ^ г — 2, то выполнено
неравенство |Л| = р2 > q*^, но dim(An) < п + 1 < г, а значит NAn ф F^ для любого натурального N, а если г = 2к -\-1 для некоторого натурального к и п = к + 1, то dim(A2n-3) = dim(^r~2) <г-1и поэтому iVA2"-3 ф q для любого натурального N. Однако, в параграфе 5.1 будет показано, что для т = 2п — 2 требуемое N всегда существует.
Теорема 5.1.1. Дано произвольное неособое подмножество A cq такое, что \А\ > q^ для некоторого є Є (0,1). Тогда выполнено равенство
NA2n-2 = ^
м _ Г 10, если п = 2;
~ \ 6П~3 max {30-(3+[log2(i)]), 160-(1+ [log2n])}, если п ^3.
Из теорем 4.1.1, 4.4.1, 5.3.2, 5.3.1 и 5.1.1 будут выведены следствия для двух подмножеств специального вида.
Все перечисленные результаты можно считать качественными свидетельствами роста подмножеств при их сложении с собой или возведении в степень. Это явление хорошо известно для конечных подмножеств натуральных чисел. Известная гипотеза Эрдеша и Семереди [42] утверждает, что
тах{|А4|,|А + Л|}^ \А\2~.
В работе [42] доказано, что max{|./L4|, \А + А\} ^ |А|1+5 для некоторого
> 0. Позже в ряде работ была найдена нижняя граница на S : 5 ^ ^( [43]),
> i( [44]), 5>\{ [45]), 6^±-є( [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].
Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору СВ. Конягину за постановки задач и постоянное внимание. Автор также благодарен профессору Ж. Бургену (Университет Высших Исследований, Принстон, США) и профессору М. Рудневу (Университет Бристоля, Бристоль, Великобритания) за плодотворные обсуждения поставленных задач и постоянную поддержку. Автор выражает благодарность всему коллективу кафедры общих проблем управления механико-математического факультета МГУ, а также доктору физико-математических наук, члену-корреспонденту РАН Ю. В. Нестеренко и доктору физико-математических наук, доценту Н. Г. Мощевитину за поддержку и внимание.
Размерность подмножеств, их аддитивная структура
Теперь перейдем к рассмотрению вопроса 0.0.2. Ясно, что для особых подмножеств А С Fq выполнено неравенство ІЛМ"1! = iL q для любых натуральных N и т, а это означает, что в случае особости А натурального числа 777., удовлетворяющего условиям вопроса 0.0.2, не существует. В диссертации доказывается существование т и получается верхняя оценка на это число для неособых подмножеств. Согласно теореме 5.4.2, для любых лиг число 777, можно оценить снизу так: т п.
В статье [41] было доказано следующее утверждение (теорема 1.2). Теорема 0.0.2. Для любого целого п 1, любого 5 0 и є 0, удовлетворяющих условиям 5 1/(п — є) и 0 є п, существует целое /У 15-4п1п(2 + 1/є), удовлетворяющее условию: для любого подмножества А С Fp; такого, что \А\ р5 выполнено множественное равенство NAn = Fp. Обобщение теоремы 0.0.2 для поля Fp2 доказано в параграфе 4.1. Мы выведем такую теорему. Теорема 4.1.1. Для любого целого числа п 2, для любых чисел є Є (0; 1), любого простого р и любого неособого множества А такого, что А С Fp27 \А\ р Е, мы имеем NAn = Fp2, где Доказательство теоремы 4.1.1 использует обобщение метода, предложенного в доказательстве теоремы 0.0.2. На основании тех же идей выводится теорема 4.4.1. Теорема 4.4.1. Рассмотрим произвольное неособое подмножество А С Fp3; такое, что \А\ р для некоторого натурального п 2 и действительного є Є (0,1). Тогда имеет место соотношение: Обобщая ключевые леммы из доказательства теоремы 4.4.1 на случай произвольного поля в параграфе 5.3, можно получить теоремы 5.3.2 и 5.3.1. Теорема 5.3.2. Для любого неособого подмножества А С р4, такого, что \А\ р« для некоторого натурального п 2 и действительного є Є (0,1), выполнено равенство если п — 4; ) е/ш n 5. Теорема 5.3.1. Для произвольного неособого подмножества А С q, г 3; такого, что \А\ q 1 для некоторого натурального п г и действительного є Є (0,1), имеет место соотношение: Отметим, что в случае поля Fg, г 5 задача о нахождении наименьшей степени множества А в вопросе 0.0.2 сложна и в настоящий момент не решена. Возьмем произвольный примитивный элемент Є F и рассмотрим подмножество Л = Fp+Fp. В доказательстве теоремы 5.4.2 установлено, что элементы {1,,... ,г-1} линейно независимы. Тогда А1 С FP+FP+.. .+ FP для любого натурального 1 / г-2и поэтому &\т(А1) / + 1. Если рассмотреть произвольное натуральное число п, + є п г — 2, то выполнено неравенство Л = р2 q , но dim(An) п + 1 г, а значит NAn ф F для любого натурального N, а если г = 2к -\-1 для некоторого натурального к и п = к + 1, то dim(A2n-3) = dim( r 2) г-1и поэтому iVA2"-3 ф q для любого натурального N. Однако, в параграфе 5.1 будет показано, что для т = 2п — 2 требуемое N всегда существует. Теорема 5.1.1. Дано произвольное неособое подмножество A cq такое, что \А\ q для некоторого є Є (0,1). Тогда выполнено равенство Из теорем 4.1.1, 4.4.1, 5.3.2, 5.3.1 и 5.1.1 будут выведены следствия для двух подмножеств специального вида. Все перечисленные результаты можно считать качественными свидетельствами роста подмножеств при их сложении с собой или возведении в степень. Это явление хорошо известно для конечных подмножеств натуральных чисел. Известная гипотеза Эрдеша и Семереди [42] утверждает, что В работе [42] доказано, что max{./L4, \А + А\} А1+5 для некоторого 5 0. Позже в ряде работ была найдена нижняя граница на S : 5 ( [43]), 6 i( [44]), 5 \{ [45]), 6 ±-є( [46]), 5 \-е{ [47]), где є 0 - произ-вольное действительное число. Последние три результата установлены для подмножеств действительной оси. Аналогичных теорем для конечных колец не было до работы [28]. После этого было в этом направлении было сделано достаточно много. Здесь можно упомянуть работы автора совместно с Ж. Вургеном и СВ. Конягиным [48], статьи М. Гараева [49], [50] и [51], а также результаты Н.Каца и Ч. Шеня [52], [53]. Следует отметить, что результаты, аналогичные результатам диссертации получены в работах Д. Коверта, Д. Харта, А. Иосевича, Д. Коха, М. Руднева и И. Шолумоши [54], [55], [56] и [57]. В этих же статьях авторы находят целый ряд приложений этих результатов к различным вопросам, в частности к задаче Эрдеша о расстояниях и задаче Эрдеша-Фалконера. В работах [54], [55], [56] и [57] используются оценки тригонометрических сумм, при помощи которых авторы доказывают, что степени множеств являются базисами ограниченного порядка. Этот подход требует более жестких требований на нижнюю границу мощности множеств. Комбинаторные методы, используемые в диссертации, позволяют установить в некоторых случаях более сильные результаты. В работах [40], [48], [58], [59] и [60] доказываются различные версии неравенств на суммы-произведения в конечных полях, устанавливается их взаимосвязь с оценками тригонометрических сумм и рассматриваются их различные приложения. Данная работа продолжает упомянутые исследования.
Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору СВ. Конягину за постановки задач и постоянное внимание. Автор также благодарен профессору Ж. Бургену (Университет Высших Исследований, Принстон, США) и профессору М. Рудневу (Университет Бристоля, Бристоль, Великобритания) за плодотворные обсуждения поставленных задач и постоянную поддержку. Автор выражает благодарность всему коллективу кафедры общих проблем управления механико-математического факультета МГУ, а также доктору физико-математических наук, члену-корреспонденту РАН Ю. В. Нестеренко и доктору физико-математических наук, доценту Н. Г. Мощевитину за поддержку и внимание.
Симметричный и антисимметричный случай
Ясно, что для любых двух элементов ?i, #2 Є G верны включения д\ + д2 + Q[X, У] С ?! -f- Q[X, У] С Q[X, У] и поэтому gi 4- д2 Є G, а это означает, что G — аддитивная подгруппа. Аналогично, для любых двух элементов /і /2 -Fo выполнены соотношения (/і + f2)G С ДС + /2 С G-f G = G и fif2G С /XG С G?, поэтому /і + /2 Є Fo и /1/2 Є 7. Из последних включений следует, что Fo — подполе. Рассмотрим произвольные элементы д Є G, г Є F и выведем: r ? + а значит rg+Q[X, Y] = Q[X, Y] и rg Є G. Из последнего соотношения следует, что г Є .Fo и поэтому fCi Q,
Если У 1 F, то существует элемент /б7и элементы Xi, #2 Є X, 7/1, 2/2 Є У такие, что y Z 2 - Q[X,Y]. Далее, используя лемму 1.2.2 мы видим, что Последнее неравенство доказывает лемму 1.2.9 в этом случае. Пусть теперь справедливо включение У С F и имеет место равенство (1.10). Заметим, что F С FQ, а значит У С FQ. ЕСЛИ J O 7 Fq, то последнее соотношение противоречит неособости множества У. Если же FQ = Fg, то G = Fg, а, следовательно, Q[X, У] = q. Последнее равенство противоречит условиям леммы. Лемма 1.2.9 доказана полностью. 1.3 Рост подмножеств при их сложении. Лемма 1.3.1 доказана в работе [41]. Она является простым следствием неравенства треугольника Ружи( [61], лемма 2.6). Лемма 1.3.1. Если У CF?- некоторое подмножество и к — произвольное натуральное число, то \kY\ \Yf-k\Y-Y\1-2l-\ Теорема 1.3.1 является классическим результатом, доказанным Коши и Давенпортом. Теорема 1.3.1. Если А\, А2,..., Ак Q Fp, к 2 — произвольные подмнооїсе-ства, то \Аг + А2 + ... + Ак\ min(Ai + \А2\ + ... + \Ак\ -(к- 1),р). Впоследствии этот результат был обобщен для случая подмножеств произвольных групп по сложению М. Кнессером ( [61], теорема 5.5 или [62]). Здесь мы сформулируем вариант его теоремы, использующийся в доказательствах результатов диссертации. Теорема 1.3.2. Для произвольных подмножеств X, У С q верно неравенство Доказательство. Возьмем произвольный элемент х Є q и рассмотрим множество х — X. Из неравенства \х — Х = Х следует, что множества х — X и X имеют непустое пересечение, а это означает, что существуют элементы х\,хъ Є X, такие, что х — Х\ = X2 х = х\ + х-}. Утверждение леммы 1.3.2 теперь легко выводится из последнего равенства. Лемма 1.3.2 доказана. Из теоремы 1.3.2 следует Лемма 1.3.3. Рассмотрим произвольное подмножество В С q, такое, что \В\ 2. Тогда выполнен один из двух следующих пунктов: (И) существует аддитивная подгруппа GCFg такая, что В Qb + G для некоторого be В и\В\ l\G\. Более того, мооюпо утвероюдатъ, что B + B = 2b + G. Доказательство. Применяя теорему 1.3.2, выводим \В + В\ 2\В + Syml{B + В)\- \Symi(B + В)\ 2\в\ - купців + в)\. {ІЛ } Так как Sym B + B) является аддитивной подгруппой qi то существует натуральное число 0 I г, такое, что Sym1(J5 4- В)\ = р1. Заметим, что Sym1(B + В) С Sym1(i? + Sym1(JB + В)). Из леммы 1.1.4 легко вывести, что \В + Sym1(S + В)\ = тр1 для некоторого натурального т. Из неравенства (1.11) следует, что \В + В\7 (2т-1)р1. (1.12) Предположим, что выполнено соотношение \В + В\ \В\. Тогда из неравенства (1.11) мы получим 1\В\ 2\В\ - ISym B + В)\ & \В\ 2р\ откуда следует, что \В + В\ 2р1 = Зр1. Последнее соотношение вместе с неравенством (1.12) дает нам условие 2т — 1 3, из которого следует, что т может принимать только одно значение: т = 1. Если т = 1, то \В + Sym i? + В)\ = \утг(В-\-В)\ = р1. Возьмем произвольный элемент b Є В и рассмотрим множество В = В — Ь. Ясно, что В + Syn {В Л-В) = Synij {В + В) и поэтому В С Synij (В + В). Вспоминая определение В , мы выводим соотношение В С b + Sym1(JB + В). Из (1.12) можно получить неравенство \В + В\ р1. Принимая во внимание включение В + -В С 26 + Sym1(B + Б), мы видим, что \В + .В = Sym1(5 + В)\ = р1. Теперь легко понять, что, если \В\ = р , то верно неравенство \В + В\ f-S, ав противном случае мы получаем утверждение (и). Для завершения доказательства леммы 1.3.3 осталось заметить, что, согласно лемме 1.3.2, В + В — 26 + Sym1(5 4- В), если \В\ р1. Лемма 1.3.3 доказана полностью. Лемма 1.3.4. Если мноснсество X С q,q = рг неособо, к г, то для любого натурального 1 1 верно неравенство Более того, если Q[X, X] % р, то последнее соотношение верно для любого l luk r-l.
Доказательство. Из леммы 1.3.3 вытекает, что либо верна оценка 2zXfc () \Хк\, либо существует элемент Ъ Є q и аддитивная подгруппа G С Fg, такие, что 21Хк = Ъ + G. Во втором случае выполнено соотношение 21Хк — 21Хк — G. Если G = q, то лемма 1.3.4 доказана. Если же подгруппа G нетривиальна, то dim X — 21Хк) г — 1. С другой стороны, из леммы 1.1.2 легко вывести равенство dim(2zXfc — 21Хк) — г. Полученное противоречие завершает доказательство первого утверждения леммы 1.3.4. Если Q[X,X] % Wp, то dim(2/X - 2іX) 2. Поэтому, согласно лемме 1.1.2, верно соотношение dim(2iXr" 1 — 2іХг_1) — г. Повторив рассуждения первой части доказательства, легко убедимся в том, что неравенство 2 r-i mjn J j xr_1,g верно. Лемма 1.3.4 доказана полностью.
Аналог леммы 4.1.3 для произвольного поля
В этом параграфе все подмножества лежат в поле q,q = рг и мы предполагаем, что г 3 и р 2. Цель этого параграфа — доказать предложение 4.2.1, которое является аналогом леммы 4.1.3 в поле q.
Доказательство. Так как Q[X, X] ф р, то можно рассмотреть элемент $. р, такой, что Є Q[X,X]. Более того, если Q[X,X] С Fp2, то из леммы 4.1.1 следует, что Q[X, X] = р2. Последнее равенство противоречит условию леммы 4.2.1, поэтому мы без ограничения общности можно считать, что Fp2, є Q[X,X]. Отметим следующие свойства множества Q[X,X] : для любого х Є Q[X,X] и для любого Ъ Є р элементы х -h b Є Q[X,X] и Є Q[X,X], если х ф 0. Мы будем обозначать множество квадратных матриц с двумя строками и элементами из поля р символом M2(FP). Для удобства сопоставим каждой матрице из Мг (р) с ненулевой второй строкой элемент из множества F c+F по следующему правилу:
Данное соответствие не является взаимно-однозначным. Назовем матрицу требуемой, если соответствующий ей элемент лежит в Q[X, X]. Описанные выше свойства множества Q[X, X] можно переформулировать так: преобразование перестановки строк требуемой матрицы сохраняет ее требуемость, таким же свойством обладает прибавление к верхней строке нижней строки, умноженной на произвольный элемент поля р. Первое преобразование умножает определитель матрицы на —1, второе — сохраняет его без изменения. Из определения элемента мы выводим, что матрица I „ .. 1 — требуема. Теперь преобразуем ее следующим образом:
Легко понять, что все матрицы трехпараметрического семейства (4.8) имеют определитель 1 и требуемы. Теперь нужно выяснить, сколько различных матриц в этом семействе. Рассмотрим произвольную матрицу X Є Мг(Рр),Х =(1 2 ) с опре \%3 Х у делителем 1. Предположим сначала, что х% ф 0. Докажем, что существует только один набор значений параметров (2/1,2/2,2/3) Fp х F х Fp, для которых матрица (4.8) совпадает с матрицей X. Действительно, из равенства этих матриц вытекают, что параметры 2/i,2/2,2/3 однозначно выражаются через элементы матрицы X следующим образом: у і = - ,2/2 — з,2/з — —Ц а значит, различным значениям параметров 2/1,2/2,2/3,2/2 Ф 0 соответствуют различные матрицы семейства (4.8). Мы нашли р2(р — 1) различных требуемых матриц. Если матрица X, такова, что х$ — 0, то аналогичные выражения параметров 2/1,2/2,2/3 через элементы матрицы X выглядят так: 2/2 = з — 0,2/1+2/3 — X2- Кроме того, если матрица X, удовлетворяющая условию х$ = 0, принадлежит множеству матриц (4.8), то Х\ — х± = 1 и поэтому в этом случае мы получаем еще р различных требуемых матриц. Осталось понять, каким матрицам семейства (4.8) соответствует один и тот же элемент. Так как матрице вида ( п -, ) соответствует элемент -f с, то при условии 7/2 = 0 мы получаем р различных элементов, которым соответствуют матрицы семейства. Рассмотрим случай х% 0. Пусть двум разным матрицам v (Х\ 372\ хг (ХЛ Хо\ л X = I 1 и X — I / /I с определителями, равными 1, соответствует V #з Х\) \х% Хл) один элемент. Это условие эквивалентно равенству: —— = -г—— & {хг + 2:2)( + Щ) = (2q + 2)( + хА). Рассмотрев поле q как алгебраическое расширение поля р, полученное присоединением к нему элемента , последнее равенство можно рассматривать как равенство многочленов (заметим, что . Fp2 и поэтому является алгебраическим элементом порядка, большего, чем 2). Поскольку многочлен не может иметь два различных разложения, то написанное равенство может иметь место только в том случае, когда xit; + Х2 делит один из многочленов хг + х2 или хз + Х4 и то же выполнено для многочлена х3 + ГЕ4, причем они делят различные многочлены. Так как равенство х\{; + Х2 = К(хз + х±) невозможно ни для какой константы К Є Ер(иначе бы определитель матрицы X был бы равен 0), то для некоторой с Є F выполнено соотношение Х\, + 2 = с(хг + х2) и одновременно для той же константы х% + 4 = с(ж3 + ХА)- 3 последних равенств легко вывести, что і 2 1. Так как определитель матрицы СООо СОС л J X равен 1, то с2 = 1 и, следовательно, с Є {—1,1}. Поэтому трехпараметри ческому семейству матриц (4.8) при условии т/2 Ф 0 соответствует не менее Р2(Р-1) iL- —- различных элемента. / ПҐ /V _ \ / /V» гр \ Осталось доказать, что матрицам X = I и J = /1 2], удо влетворяющим условиям ж3 7 0 и ж3 = 0 и имеющим определитель 1, не соответствует один и тот же элемент. Действительно, из обратного предположения следует, что —— = х х + х2) & хг + х2 = х х + х2)(х3, + ж4). ж3 + ж4 Так как Fp2, то не является алгебраическим элементом второго порядка и последнее равенство невозможно, что приводит нас к противоречию. Из требуемости матриц семейства (4.8) вытекает принадлежность всех полученных элементов множеству Q[X,X]. Очевидно, что все эти элементы не равны нулю(только вырожденная матрица может соответствовать нулю). Лемма 4.2.1 доказана. Предложение 4.2.1. Для любого неособого подмножества X С Fq, удовлетворяющего условию \Х\ 1, выполнено соотношение: 1 х2 + н +р ; Доказательство. Заменяя множество X на множество - Х,х Є X, мы не изменим мощности множеств, участвующих в формулировке предложения 4.2.1. Поэтому можно без ограничения общности считать, что 1 Є X. Пусть Q[X,X] таково, что 1 + Q[X,X] 2 Q[X,X]. Тогда, применив лемму 1.2.5, где в качестве множеств X и Y мы возьмем множество X, а вместо элемента а подставим 1, мы получаем:
Степени подмножеств поля р4 и свойства больших степеней подмножества конечного поля
Следствие 5.3.1. Для любой подгруппы по умнооїсеиию Н С q, не ле-зісащей ни в каком нетривиальном подполе q и удовлетворяющей условию для некоторого натурального п г и действительного є 0, имеет место равенство МпН = q, где Мп — число, определенное в формулировке теоремы 5.3.1.
Следствие 5.3.2. Рассмотрим произвольное натуральное число п г и любое действительное є 0. Тогда для любого натурального k д +1, произвольного элемента д, не лежащего ни в каком нетривиальном подполе q, такого, что ordqg к, и множества А — {дх : 0 х кп} выполнено равенство МпА = q, где Мп — число, определенное в формулировке теоремы 5.3.1. Доказательство. Если oidqg = kn, то А является подгруппой по умножению, и поэтому утверждение следствия 5.3.2 вытекает из следствия 5.3.1. Если же ovdqg kn, то, определяя подмножество AQ = {gx : 0 х k} , легко видеть, что \AQ\ q1 и AQ С А, поэтому из теоремы 5.3.1 следует равенство МпА = q, где Мп — число, определенное в формулировке этой теоремы. Следствие 5.3.2 доказано полностью. Теорема 5.3.2. Для любого неособого подмножества А С р4, такого, что \А\ р" для некоторого натурального п 2 и действительного є Є (0,1), выполнено равенство Г 10, если п = 2; Доказательство. Утверждение теоремы 5.3.2 для случая п = 2 следует из теоремы 0.0.1, а для случая п 4 — из теоремы 5.3.1. Осталось доказать теорему 5.3.2 для п = 3. Заметим сначала, что dim(A — А) 2, так как в противном случае \А\ \А — А р, что противоречит условию \А\ рз=7. Из соотношения dim(A — А) 2 следует, что Q[A, А] 2 Fp и, согласно леммам 1.1.1 и 1.1.2, неравенства dim(L42) 3 и dim(/A2 — 1А2) 3 верны для любого натурального I 2. Если \А\2 -, то из предложения 4.2.1 вытекает соотношение 3А2 - ЗА2 V ; Л 33 . i42 + i+p A2 + f б Используя лемму 1.3.1, мы видим, что 12А2 ЗА2 ЗА2 - ЗА2і ЛР3" б» Из леммы 1.3.3 мы выведем, что либо 1б 12А2 512А2 p3_s либо существуют элемент b Є Fp4 и аддитивная подгруппа G С Fp4, такие, что 16 12А2 = 166 -f G. В первом случае, при р 11, выполнено неравенство 192А2А р3 Р4. Теперь, используя теорему 0.0.1, мы получим соотношение 1920 А3 = р4. Пусть существует элемент Ъ Є Fp4 и аддитивная подгруппа G С Fp4, такие, что 192А2 = 166+G. Если G = р4, то верно равенство 192А2 = р4. Если же С С Fp4, то используя выше доказанную оценку dim(192A2 — 192А2) = dim(G) 3, мы видим, что 192А2 = р3 и, если р 11, верно неравенство 192А2А 4 р4+2 р4. Применяя теоремы 2.1.1 и 2.1.2(множество 192А2 симметрично, если 16& Є G и антисимметрично иначе), мы получим равенство 1536А3 = Fp4. Если р 11, то, согласно лемме 1.2.1, выполнено соотношение 2400А3 = Fp4. Объединяя полученные равенства, мы завершаем рассмотрение случая А2 у. Если А2 -, то из предложения 4.2.1 вытекает соотношение А2 + Щр±+р " A2 + f 2 Определим параметр IQ = 2 + [log2 ( )] . Используя лемму 1.3.1, мы видим, что -і -і 3/0Л2 ЗА2 ЗЛ2 - ЗА2\ \А\2 =т ±\А\2-Є. Из леммы 1.3.3 мы выведем, что либо 121QA2\ 2\31оА2\, либо существуют элемент 6 Є Fp4 и аддитивная подгруппа G С Fp4, такие, что 12 0А2 = 46 + G. В первом случае выполнено неравенство 112/( 421./4 И3-Г Р4- Теперь, используя теорему 0.0.1, мы получим соотношение 120Zo 43 = Fp4. Пусть существует элемент 6 Є Fp4 и аддитивная подгруппа G С Fp4, такие, что 12ZQA2 = 46+G. Если G = РА, то верно равенство 12l0A2 = Fp4. Если же G С Fp4, то используя выше доказанную оценку dim(1 21QА2 — 121QA2) = dim(G) 3, мы видим, что 12 А2 = р3 и верно неравенство 12Zo 42A р3+з=г р4. Применяя теоремы 2.1.1 и 2.1.2(множество 121QA2 симметрично, если 46 Є G и антисимметрично иначе), мы получим равенство 96loA3 = Fp4. Объединяя полученные равенства, мы завершаем доказательство теоремы 5.3.2. Следствие 5.3.3 очевидным образом вытекает из теоремы 5.3.2. Следствие 5.3.3. Для любой подгруппы по умножению Н С р , не леснса-щей ни в каком нетривиальном подполе р4 и удовлетворяющей условию \Н\ р" для некоторого натурального п)2 к действительного є О, имеет место равенство МпН = р4, где Мп — число, определенное в формулировке теоремы 5.3.2. Следствие 5.3.4. Рассмотрим произвольное натуральное число п 2 и Г 4 любое действительное є 0. Тогда для любого натурального к р + 1, произвольного элемента д, не лежащего ни в каком нетривиальном подполе р , такого, что oidqg к, и множества А — {дх : 0 х кп} выполнено равенство МпА — pi, где Мп — число, определенное в формулировке теоремы 5.3.2.
Доказательство. Если ordg ? кп, то А является подгруппой по умножению, и поэтому утверждение следствия 5.3.4 вытекает из следствия 5.3.3. Если же ordg# кп, то, определяя подмножество AQ = {gx : 0 х к} , легко видеть, что Ло Р"1 и AQ С А, поэтому из теоремы 5.3.2 следует равенство МпА = р4, где Мп — число, определенное в формулировке этой теоремы. Следствие 5.3.4 доказано полностью.
