Множество больших тригонометрических сумм

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

Для удобства изложения далее в статье используется сокращение МБТС, хотя оно не является общепринятым.

Предпосылки к изучению

В классическом методе тригонометрических сумм часто требуется оценить сверху значение модуля суммы ${\displaystyle \sum \limits _{x\in X}{e^{\frac {ax}{n}}}}$ для некоторого подмножества ${\displaystyle X\subset {\mathbb {Z} }_{n}}$ циклической группы. Если эта сумма имеет малый модуль при всех ${\displaystyle a\not \equiv 0{\pmod {n}}}$, то из этого можно сделать выводы о равномерности распределения ${\displaystyle X}$ среди непрерывных отрезков вычетов по модулю ${\displaystyle n}$. Это оказывается верным, например, для множества квадратичных вычетов^[1] (и вообще степенных вычетов^[2]), дискретных логарифмов последовательных чисел^[3] или (для простых ${\displaystyle n}$) выражений вида ${\displaystyle a+a^{-1}}$, где ${\displaystyle a^{-1}}$ — обратный элемент ${\displaystyle {\mathbb {F} }_{n}}$ относительно умножения (суммы Клоостермана)^[4].

Естественным образом возникает вопрос: если не для всех ${\displaystyle a\not \equiv 0{\pmod {n}}}$ рассматриваемые суммы имеют малый модуль, то для сколь многих ${\displaystyle a}$ этот модуль может быть очень большим, и для каких именно наборов значений ${\displaystyle a}$ это может выполняться? Например, очевидно, что если это выполняется для ${\displaystyle a}$, то и для ${\displaystyle -a}$ тоже, но возникает вопрос о существовании других таких всеобщих закономерностей, не зависящих от природы множества ${\displaystyle X}$.

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

Определение

Закономерности, касающиеся МБТС, рассматриваются, как правило, исходя из двух параметров — размера основного множества и границы, по которой отделяются значения тригонометрических сумм. Иногда для удобства границу на тригонометрические суммы записывают не в явном виде, а параметризуют через её отношение к размеру множества (поскольку модуль суммы, очевидно, никогда не больше размера множества). Из-за этого, а также от различной нормировки коэффициентов Фурье, выражения в формулировках определений и теорем у разных авторов могут различаться, но суть исследуемых соотношений остаётся той же.

Пусть ${\displaystyle N}$ — натуральное число, ${\displaystyle A\subset {\mathbb {Z} }_{N}}$, ${\displaystyle |A|=\delta N}$ Пусть также ${\displaystyle {\widehat {A}}(\xi )=\sum \limits _{x\in A}{e^{2\pi {\frac {\xi x}{N}}i}}}$ обозначает ${\displaystyle \xi }$-й коэффициент Фурье (не нормированный) характеристической функции ${\displaystyle A}$. Тогда множества больших тригонометрических сумм с параметром определяются (с точностью до параметра ${\displaystyle \alpha }$) как ${\displaystyle {\mathcal {R}}_{\alpha }={\mathcal {R}}_{\alpha }(A)=\left\lbrace {\xi :|{\widehat {A}}(\xi )|\geq \alpha N}\right\rbrace }$[5]

Некоторые приёмы изучения

Приближение функции множеством

Для построения примеров множеств, обладающих МБТС с теми или иными свойствами, часто строятся функции, обладающие соответствующие коэффициентами Фурье, а потом на этом основании констатируется существование множеств, коэффициенты Фурье которых не сильно отличаются от коэффициентов этих функций^[6][7][8]. Основания для этого даёт следующая лемма, доказательство которой восходит к общей линейно-алгебраической идее и выходит за рамки науки о МБТС.

Если ${\displaystyle f:{\mathbb {Z} }_{N}\to [0;1]}$, то существует множество ${\displaystyle S\subset {\mathbb {Z} }_{N}}$ размера ${\displaystyle \left\lfloor {\sum \limits _{x}{f(x)}}\right\rfloor }$ такое, что ${\displaystyle \forall r\in {\mathbb {Z} }_{N}:|{\widehat {S}}(r)-{\widehat {f}}(r)|\leq 20{\sqrt {N}}}$[9]

Изменение индикаторной функции при фильтрации коэффициентов Фурье по различным значениям ${\displaystyle \alpha }$

Фильтрация коэффициентов Фурье

Для вывода общих утверждений об МБТС некоторых множеств удобно использовать^[10][11] функции, образованные из индикаторной функции множества фильтрацией коэффициентов Фурье по этому МБТС, то есть такую функцию ${\displaystyle f}$, что

${\displaystyle {\widehat {f}}(\xi )={\begin{cases}{\widehat {1_{A}}}(\xi )&\xi \in {\mathcal {R}}_{\alpha }(A)\\0&\xi \not \in {\mathcal {R}}_{\alpha }(A)\end{cases}}}$

Оказывается, что у таких функций большая часть суммы значений также концентрируется в ${\displaystyle A}$.

Свойства

Размер

Из равенства ${\displaystyle \sum \limits _{\xi }{|{\widehat {A}}(\xi )|^{2}}=|A|^{2}}$ легко получается. что ${\displaystyle |{\mathcal {R}}_{\alpha }|<{\frac {\delta }{\alpha ^{2}}}}$.

Для некоторых значений ${\displaystyle \delta ,\alpha }$ эта оценка достаточно точна по порядку роста.

Пример — квадратичные вычеты

Если ${\displaystyle Q_{p}\subset {\mathbb {Z} }_{p}}$ — множество квадратичных вычетов по простому модулю ${\displaystyle p}$, ${\displaystyle \delta ={\frac {p+1}{2p}},\ \alpha \approx {\frac {1}{2{\sqrt {p}}}}}$, то для ${\displaystyle |{\mathcal {R}}_{\alpha }(Q_{p})|=p}$ оценка превращается в неравенство близкое к ${\displaystyle |{\mathcal {R}}_{\alpha }(Q_{p})|<2(p+1)}$.

С помощью конструкции вида ${\displaystyle \bigcup \limits _{s=0}^{k-1}{(sp+Q_{p})}\subset {\mathbb {Z} }_{kp}}$ эту идею можно обобщить на МБТС с меньшей относительно модуля границей на значение суммы. При этом между оценкой и реальным размером МБТС образуется та же разница.

Пример — подряд идущие числа

В примере с квадратичными вычетами величина ${\displaystyle \delta ={\frac {p+1}{2p}}\approx {\frac {1}{2}}}$ близка к фиксированной. Чтобы найти примеры с произвольной величиной ${\displaystyle \delta }$, достаточно рассмотреть множество ${\displaystyle A=\{1,2,\dots ,m\}\subset {\mathbb {Z} }_{N}}$, где ${\displaystyle m\ll N}$.

Тогда ${\displaystyle \forall \xi <{\frac {N}{4m}}\forall a\in A:\ \arg \left({e^{2\pi {\frac {\xi a}{N}}i}}\right)<{\frac {\pi }{2}}}$ (то есть направления векторов, соответствующих ${\displaystyle e^{2\pi {\frac {\xi a}{N}}i}}$, ограничены довольно узким углом) и поэтому ${\displaystyle \forall \xi <{\frac {N}{4m}}:|{\widehat {A}}(\xi )|\gg {\frac {m}{2}}}$, так что верна оценка снизу ${\displaystyle |{\mathcal {R}}_{\frac {m}{2N}}(A)|\geq \left\lfloor {\frac {N}{4m}}\right\rfloor }$. Более того, так как ${\displaystyle |{\widehat {A}}(\xi )|=|{\widehat {A}}(-\xi )|}$, то верно даже, что ${\displaystyle |{\mathcal {R}}_{\frac {m}{2N}}(A)|\geq \left\lfloor {\frac {N}{2m}}\right\rfloor }$

Однако при ${\displaystyle \delta ={\frac {m}{N}},\ \alpha ={\frac {m}{2N}}}$ оценка сверху превращается в неравенство ${\displaystyle |{\mathcal {R}}_{\alpha }(A)|\leq 4{\frac {N}{m}}}$.

Получается, что ${\displaystyle \left\lfloor {\frac {N}{2m}}\right\rfloor \leq |{\mathcal {R}}_{\alpha }(A)|\leq 4{\frac {N}{m}}}$ и оценка сверху также точна до умножения на константу.

Структура

Степень структурированности МБТС в разных смыслах может быть оценена достаточно точна когда они достаточно велики. В случае, когда они имеют малый размер, МБТС могут быть вполне произвольными.

Аддитивная энергия

С одной стороны, МБТС допускают нижнюю оценку на аддитивную энергию любого своего подмножества.

Если ${\displaystyle B\subset {\mathcal {R}}_{\alpha }}$, то ${\displaystyle T_{k}(B)\gg _{k}{\frac {\alpha ^{2k}}{\delta ^{2k-1}}}|B|^{2k}}$[11]

Краткое описание идеи доказательства

Достаточно похожим образом оценить энергию множеств вида ${\displaystyle B'\subset {\mathcal {R}}_{\alpha }\setminus {\mathcal {R}}_{2\alpha }}$ и просуммировать результаты по значениям ${\displaystyle \alpha ,2\alpha ,4\alpha ,\dots }$

Для оценки энергии ${\displaystyle B'}$ используется функция. коэффициенты Фурье которой суть коэффициенты ${\displaystyle 1_{A}}$, отфильтрованные по ${\displaystyle B'}$. Так как, из общих соображений, значения такой функции очень насыщены в ${\displaystyle A}$, то достаточно с помощью серии неравенств Гёльдера и операций со свёртками оценить эту насыщенность через конструкцию ${\displaystyle \sum \limits _{u}{{{\Bigg \vert }{\sum \limits _{r}{{\widehat {f}}(r){\overline {{\widehat {f}}(r-u)}}}}{\Bigg \vert }}^{2}}}$ и некий множитель, зависящий от ${\displaystyle |A|}$ (то есть от ${\displaystyle \delta }$). Конструкция же ${\displaystyle \sum \limits _{u}{{{\Bigg \vert }{\sum \limits _{r}{{\widehat {f}}(r){\overline {{\widehat {f}}(r-u)}}}}{\Bigg \vert }}^{2}}}$, благодаря вычитанию ${\displaystyle {\mathcal {R}}_{2\alpha }}$ из ${\displaystyle B'}$ (то есть благодаря условию на оценку ${\displaystyle {\widehat {f}}(\xi )}$ сверху), оценивается сверху через величину аддитивной энергии (с некоторым добавочным множителем).

С другой стороны, при некоторых дополнительных (не слишком сильных) условиях на параметры ${\displaystyle k,\alpha ,\delta }$ существует множество ${\displaystyle A}$, для которого верна и верхняя оценка ${\displaystyle T_{k}({\mathcal {R}}_{\alpha })\ll _{k}{\frac {\delta }{\alpha ^{2k}}}}$, причём ${\displaystyle |{\mathcal {R}}_{\alpha }|\gg {\frac {\delta }{\alpha ^{2}}}}$^[12]. Это говорит о том, что иногда МБТС могут быть всё-таки достаточно большими и бесструктурными одновременно.

Конструкция

Для построения используется множество ${\displaystyle \Lambda }$, обладающее специальным образом усиленным свойством диссоциативности.

Само множество ${\displaystyle A}$ определяется как объединение сдвигов ${\displaystyle |\Lambda |}$ различных арифметических прогрессий с разностями ${\displaystyle \lambda \in \Lambda }$, причём сдвиги выбираются таким образом. чтобы каждая новая добавляемая во множество прогрессия имела с уже построенным множеством как можно меньшее пересечение.

МБТС такого множества содержит в себе объединение такого же количества других арифметических прогрессий (что позволяет говорить о его большом размере) и одновременно с этим само содержится в объединении тех же арифметических прогрессий, только более удлинённых в обе стороны (а это позволяет из общих комбинаторных соображений вывести, что его аддитивная энергия не велика).

В случае, когда ${\displaystyle {\mathcal {R}}_{\alpha }}$ имеет максимально возможный размер, эти оценки (если первую рассматривать для ${\displaystyle B={\mathcal {R}}_{\alpha }}$) совпадают с точностью до константы, зависящей от ${\displaystyle k}$. То есть для довольно широкого класса значений параметров ${\displaystyle \delta ,\alpha }$ существуют множества, мера структурированности МБТС которых определена почти однозначно, причём их МБТС оказываются тем более бесструктурны, чем больше в них элементов (чем больше разница между ${\displaystyle \delta }$ и ${\displaystyle \alpha }$).

Аддитивная размерность

Другая изучаемая характеристика — аддитивная размерность МБТС, то есть размер максиимального содержащегося в нём диссоциативного множества. Далее эта величина обозначается как ${\displaystyle \dim _{+}({\mathcal {R}}_{\alpha })}$.

Чанг в 2002 году доказала, что ${\displaystyle \dim _{+}({\mathcal {R}}_{\alpha })\ll {\left({\frac {\delta }{\alpha }}\right)}^{2}\log {\left({\frac {1}{\delta }}\right)}}$^[13][14]. Основу доказательства составляло применение неравенства Рудина к функции, образованной из индикаторной функции множества фильтрацией коэффициентов Фурье по ${\displaystyle {\mathcal {R}}_{\alpha }}$^[10].

В то же время Грин в 2003 году показал, что при условиях

• ${\displaystyle \delta \leq {\frac {1}{8}}}$

• ${\displaystyle \alpha \leq {\frac {\delta }{32}}}$

• ${\displaystyle {\left({\frac {\delta }{\alpha }}\right)}^{2}\log {\left({\frac {1}{\delta }}\right)}\leq {\frac {\log N}{\log \log N}}}$

существует множество ${\displaystyle A}$, для которого ${\displaystyle \dim _{+}({\mathcal {R}}_{\alpha })\gg {\left({\frac {\delta }{\alpha }}\right)}^{2}\log {\left({\frac {1}{\delta }}\right)}}$^[15][7].

То есть при рассмотрении достаточно больших значений сумм аддитивную размерность МБТС также можно оценить достаточно точно.

Произвольность

Если МБТС достаточно мало́ по сравнению со своим максимально возможным размером, то общая оценка на аддитивную энергию оказывается тривиальной, то есть не позволяет ничего сказать о внутренней структуре множества.

Оказывается, что в этом случае о ней ничего сказать и нельзя — то есть произвольное множество может быть малым МБТС.

Теорема (Шкредов) Если ${\displaystyle \delta <{\frac {1}{2}}}$ ${\displaystyle 20{\frac {1}{\sqrt {N}}}<\alpha \leq {\frac {\delta }{2}}}$ ${\displaystyle |S|\leq {\frac {\delta }{2\alpha }}}$ ${\displaystyle S=-S}$ то ${\displaystyle \exists A:\ |A|=\left\lfloor {\delta N}\right\rfloor }$ и ${\displaystyle {\mathcal {R}}_{\alpha }(A)=S}$[6]

Краткое описание идеи доказательства

Достаточно рассмотреть функцию ${\displaystyle f}$ такую, что

${\displaystyle {\widehat {f}}(\xi )={\begin{cases}\delta &\xi =0\\2\alpha &\xi \in S\setminus \{0\}\\0&\xi \not \in S\end{cases}}}$

и применить лемму о приближении её коэффициентов Фурье через коэффициенты Фурье индикаторной функцию множества.

Основным ограничением здесь служит ${\displaystyle |S|\leq {\frac {\delta }{2\alpha }}}$ — остальные обусловлены общей природой тригонометрических сумм.

Ограничение на размер может быть ослаблено до ${\displaystyle |S|\leq {\frac {\delta }{\alpha }}\log {\frac {1}{\delta }}}$ если добавить условие на то, что ${\displaystyle S}$ обладает некоторым свойством, являющимся вариацией диссоциативности^[16].

Связь между МБТС разных множеств

МБТС множеств размера ${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor }$ (половина размера группы) в некотором смысле покрывают структуру всех остальных МБТС.

Теорема (Грин) Если ${\displaystyle \alpha \geq 80{\frac {1}{\sqrt {N}}}}$, то для всякого ${\displaystyle A\subset {\mathbb {Z} }_{N}}$ существует ${\displaystyle B\subset {\mathbb {Z} }_{N}}$ такое, что ${\displaystyle |B|=\left\lfloor {\frac {N}{2}}\right\rfloor }$ и ${\displaystyle {\mathcal {R}}_{\alpha }(A)\subset {\mathcal {R}}_{\frac {\alpha }{4}}(B)}$[8]

Обобщения

МБТС могут изучаться не только для циклических, но и для любых групп если правильным образом обобщить понятие коэффициента Фурье^[17].

Например, для любого ${\displaystyle \alpha <{\frac {1}{2}}}$ и множества ${\displaystyle A\subset {\mathbb {Z} }_{2}^{n}}$ его ${\displaystyle \alpha }$-МБТС содержит в себе подгруппу размера ${\displaystyle {}^{\left({\frac {1}{\alpha ^{3}}}\right)}2}$ (последнее выражение означает тетрацию)^[18].

Приложения

Чанг применила оценки на аддитивную размерность МБТС к улучшению оценок в теореме Фреймана^[14].

Литература

• Б. И. Сегал. Тригонометрические суммы и некоторые их применения к теории чисел (рус.) // Успехи математических наук. — 1946. — Вып. 3—4 (13-14). — С. 147—193.

• М. А. Королёв. Методы оценок коротких сумм Клоостермана (рус.) // Чебышевский сборник. — 2016. — Т. 17, вып. 4. — С. 79—109.

• И. Д. Шкредов. Некоторые примеры множеств больших тригонометрических сумм (рус.) // Математический сборник. — 2007. — Т. 198, вып. 12. — С. 105—140.

• И. Д. Шкредов. О множествах больших тригонометрических сумм (рус.) // Известия РАН, серия математика. — 2008. — Т. 72, вып. 1. — С. 161—182.

• Mei-Chu Chang. A polynomial bound in Freiman's theorem (англ.) // Duke Mathematical Journal. — 2002. — Vol. 113, iss. 3. — P. 399—419.

• Ben Green. Some Constructions in the Inverse Spectral Theory of Cyclic Groups (англ.) // Combinatorics, Probability and Computing. — 2003. — Vol. 12, iss. 2. — P. 127-138.

• Ben Green. A Szemerédi-type regularity lemma in abelian groups, with applications (англ.) // Geometric & Functional Analysis GAFA. — 2005. — Vol. 15, iss. 2. — P. 340-376.

Примечания

1. Сегал, 1946, с. 151.
2. Сегал, 1946, с. 159—160.
3. Сегал, 1946, с. 163.
4. Королёв, 2016, с. 81—82.
5. Шкредов, 2008, с. 161.
6. Шкредов, 2007, с. 109, предложение 2.1.
7. Грин, 2003, с. 131—133, леммы 3.2, 3.3.
8. Грин, 2003, с. 129, лемма 2.3.
9. Грин, 2003, с. 129, лемма 2.2.
10. Препринт работы Чанг Архивная копия от 1 декабря 2016 на Wayback Machine, с. 17, лемма 3.1
11. Шкредов, 2008, с. 163, теорема 5.
12. Шкредов, 2007, с. 118, теорема 2.11.
13. Шкредов, 2008, с. 162, теорема 1 (без доказательства).
14. Чанг, 2002.
15. Шкредов, 2008, с. 162, теорема 4 (без доказательства).
16. Шкредов, 2007, с. 112, предложение 2.9.
17. Шкредов, 2007, с. 108.
18. Грин, 2005, с. 345, теорема 2.1.