Русская Википедия:Тригонометрическая сумма

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Exp-sum-of-quadratic-residues-11.gif

Пример: тригонометрическая сумма над квадратичными вычетами по модулю <math>m=11</math>. Разнонаправленность векторов (изгиб пути из разноцветных линий) делает абсолютное значение суммы (длину жёлтой линии) меньше числа слагаемых. Это общий момент для тригонометрических сумм в целом, а модуль таких сумм при растущем <math>m</math> и вовсе имеет порядок <math>\sqrt{m}</math>.

Тригонометрическая сумма — это конечная сумма комплексных чисел, геометрически соответствующих векторам на единичной окружности, то есть вида <math>e(\varphi) := \cos \varphi + i \sin \varphi\ .</math>

Такие суммы по значениями <math>\varphi</math>, образованным из множества чисел или элементов группы, изучаются в аналитической теории чисел. Верхние оценки на них позволяют оценивать число решений уравнений с переменными из рассматриваемых множеств.

Геометрические свойства синусов и косинусов из определения <math>e(\varphi)</math> не играют в методе ключевой роли. Формула Эйлера

<math>e(\varphi) = e^{2 \pi \varphi i}</math>

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

Когда <math>\varphi</math> рационально, слагаемое является корнем из единицы. В современной литературе принято обозначение

<math>e_q(a) := e \left( \frac{a}{q} \right) = e^{2 \pi \frac{a}{q} i}\ .</math>

Суммы с такими слагаемыми используются для изучения множеств значений по модулю <math>q</math>. Они наиболее популярны.

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

Основные свойства

Через тригонометрические суммы можно выражать утверждения о равенстве нулю:

• для любых <math>m \in {\mathbb N},\ a \in {\mathbb Z}</math> верно, что <math>\sum \limits_{x=0}^{m-1} {e_m(a x)} = \begin{cases} m, & a \equiv 0 \pmod m \\ 0, & a \not \equiv 0 \pmod m \end{cases}</math>;

• аналогично, для любого <math>n \in {\mathbb Z}</math> верно, что <math>\int \limits_{0}^{1} {e(\alpha n) d \alpha} = \begin{cases} 1, & n = 0 \\ 0, & n \not = 0 \end{cases}</math>.

Используя общую структуру абелевых групп, можно получить аналогичные выражения для любой такой группы вместо <math>Шаблон:\mathbb Z_m</math> и <math>Шаблон:\mathbb Z</math>.

При выводе оценок часто используют соображения о том, что:

• произведение и сопряжение (а значит, и чётные степени модулей) тригонометрических сумм также будет тригонометрической суммой — перемножая суммы, по-разному группируя слагаемые и применяя неравенство Гёльдера, можно переходить от одного множества или уравнения к другим, решая ту же задачу;

• для любых <math>\varphi_1, \dots, \varphi_n</math> верна тривиальная оценка <math>\Bigg\vert { \sum \limits_{i=1}^{n} e(\varphi_i) } \Bigg\vert \le n</math>.

Приложения

Число решений уравнений

Выражение

Для множеств <math>A_1, \dots, A_k</math> и функции <math>f : A_1 \times \dots \times A_k \to {\mathbb Z}_m</math> число решений уравнения

<math>f(x_1, \dots, x_k) \equiv 0 \pmod m,\ x_1 \in A_1, \dots, x_k \in A_k</math>

можно выразить через тригонометрическую сумму как сумму скобок Айверсона:

<math>\sum \limits_{x_1 \in A_1, \dots, x_k \in A_k} {[f(x_1, \dots, x_k) \equiv 0 \pmod m]} = \frac{1}{m} \sum \limits_{x_1 \in A_1, \dots, x_k \in A_k} \sum \limits_{t=0}^{m-1} {e_m(t f(x_1, \dots, x_k))}\ .</math>

Аналогично, для целочисленной <math>f</math> и решений <math>f(x_1, \dots, x_k) = 0</math> допустимо представление

<math>\sum \limits_{x_1 \in A_1, \dots, x_k \in A_k} {[f(x_1, \dots, x_k) = 0]} = \sum \limits_{x_1 \in A_1, \dots, x_k \in A_k} \int \limits_{0}^{1} e(\alpha f(x_1, \dots, x_k)) d \alpha\ .</math>

Эти конструкции легко обобщить на системы уравнений.

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

Использование

Тригонометрические выражения наиболее полезны когда функция <math>f</math> хорошо разлагается на слагаемые. Например, если

<math>f(x_1, \dots, x_k) = f_1(x_1) + \dots + f_k(x_k)\ ,</math>

то, меняя порядок суммирования, можно получить выражение

<math>\sum \limits_{x_1 \in A_1, \dots, x_k \in A_k} \sum \limits_{t=0}^{m-1} {e_m(t (f_1(x_1) + \dots f_k(x_k)))} = \sum \limits_{t=0}^{m-1} \prod \limits_{i=1}^{k} \left( \sum \limits_{x_i \in A_i} {e_m(t f_i(x_i))} \right) \le \sum \limits_{t=0}^{m-1} \prod \limits_{i=1}^{k} \Bigg\vert \sum \limits_{x_i \in A_i} {e_m(t f_i(x_i))} \Bigg\vert \ .</math>

Суммы <math>\sum \limits_{x_i \in A_i} {e_m(t f_i(x_i))}</math> по отдельности друг от друга не имеют комбинаторной интерпретации, но могут быть оценены аналитически. Именно это делает метод тригонометрических сумм нетривиальным.

При <math>t=0</math> все слагаемые вырождаются в <math>e(0)=1</math>, так что эта часть суммы всегда равна <math>|A_1| \dots |A_k|</math> и называется главным членом. Поэтому оценки числа решений через тригонометрические суммы чаще всего не могут быть лучше чем <math>\frac{|A_1| \dots |A_k|}{m}</math>. В частности, именно такая величина нужна в доказательстве равномерного распределения. При работе с интегралами роль главного члена среди интервала <math>[0;1]</math> выполняют окрестности несократимых дробей с малыми знаменателямиШаблон:Sfn.

Нюансы

О связи уравнений и тригонометрических сумм следует отметить два нюанса. Во-первых, иногда бывает удобно переходить не от уравнения к суммам, а наоборот в ходе оценке суммы после её преобразований переходить к анализу простого или известного уравнения. Во-вторых, чисто комбинаторные преобразования уравнений можно выражать на языке тригонометрических сумм. Поэтому в литературе, посвящённой тригонометрическим суммам, часто эти преобразования так и излагают, без упоминания о том, что то же самое можно сделать элементарно. Тем не менее, существует много случаев, когда прямое элементарное переложение невозможно.

Равномерное распределение

Файл:Distribution-of-exp-sum-values.png

Если функцию, так или иначе связанную с умножением, применить к интервалу, то тригонометрическая сумма над получившимся множеством, как правило, будет иметь порядок <math>\sqrt{n}</math>, где <math>n</math> — длина интервала (число слагаемых). Этот эффект известен как «square-root barier» и свидетельствует о равномерном распределении множества с очень малым остаточным членом (порядка <math>\sqrt{n} \log p</math>).
На графике <math>g</math> — первообразный корень, <math>{\rm ind}</math> — дискретный логарифм. Для других больших интервалов вместо <math>[1;p/5]</math> результаты будут похожими.

Для любого интервала <math>I=\{ M,M+1,\dots,N-1,N \}</math> в кольце вычетов <math>{\mathbb Z}_m</math> можно оценить связанную с ним тригонометрическую сумму

<math>\sum \limits_{a=1}^{m} { \Bigg\vert { \sum \limits_{x \in I} {e_m(ax)} } \Bigg\vert } \le m \ln m</math>

Благодаря этому оценку тригонометрических сумм над множеством в <math>{\mathbb Z}_m</math> можно преобразовывать в утверждение о его равномерном распределении в <math>{\mathbb Z}_m</math>:

Шаблон:Рамка Если для множества <math>A \subset {\mathbb Z}_m</math> и любого <math>t \in {\mathbb Z}_m \setminus \{ 0 \}</math> верна оценка <math>\Bigg\vert { \sum \limits_{a \in A} {e_m(ta)} } \Bigg\vert = o \left( { \frac{|A|}{\log m} } \right)</math>, то для любых <math>0 \le \delta_1 < \delta_2 \le 1</math> можно показать, что <math>|A \cap [\delta_1 m ; \delta_2 m]| = (\delta_2 - \delta_1 + o(1)) |A|</math> Шаблон:Конец рамки

Чаще всего подобные результаты удобно получать для простого <math>m</math>. Известны оценки таких сумм для квадратичных вычетовШаблон:Sfn, других степеней, индексов (дискретных логарифмов) чисел из интервала, обратных элементов для интервала и даже для произвольной мультипликативной подгруппы размера <math>p^{\varepsilon}</math> (для любого фиксированного <math>\varepsilon > 0</math>). Похожий метод применим для доказательства равномерного распределения вещественных последовательностей в интервале <math>(0;1)</math>.

По аналогии с этим, суммы мультипликативных характеров можно воспринимать как показатель равномерности относительно структуры мультипликативной группы <math>{\mathbb F}_p</math>. Такие суммы хорошо изучены для интервалов, множества значений многочленов и сдвигов простых чиселШаблон:Sfn.

История

Первое использование тригонометрических сумм относят к исследованию Гаусса о квадратичном законе взаимности (1795 г.). Он оценивал суммы с квадратичными вычетами, то есть вида <math>\sum \limits_{x=1}^{p} {e_p(a x^2)},\ a \in {\mathbb Z}_p</math>. Вскоре Дирихле применил суммы характеров с коэффициентами к изучению распределения простых чисел в арифметических прогрессиях.

В конце XIX — начале XX века тригонометрических суммы стали использовать для исследования распределения последовательностейШаблон:SfnШаблон:Sfn.

Значимым событием стало применение тригонометрических сумм к решению проблемы Варинга двумя способами: круговым методом Харди-Литтлвуда и переосмыслившим его методом И. М. ВиноградоваШаблон:Sfn. Виноградов впоследствии развил свой метод для получения результатов о простых числах, в том числе решения тернарной проблемы Гольдбаха для достаточно больших чисел и аналога проблемы Варинга для простых чисел.

Клаус Рот и позже Уильям Тимоти Гауэрс применили технику кругового метода для доказательства теоремы Семереди. Впоследствии тригонометрические суммы были использованы во многих задачах аддитивной комбинаторикиШаблон:Sfn.

Суммы с собственными названиями

• суммы Рамануджана для <math>a \in {\mathbb Z}_q,\ (a,q)=1</math>:

<math>\sum \limits_{1 \le x \le q \atop (x, q) = 1} {e_q(ax)}</math>

• суммы Гаусса <math>a \in {\mathbb Z}_q</math>:

<math>\sum \limits_{x=1}^{q} {e_q(a x^2)}</math>

• суммы Вейля для многочлена <math>f</math> с вещественными (не целыми) коэффициентами и интервала <math>[a;b]</math>:

<math>\sum \limits_{a \le n \le b} {e(f(n))}</math>

• суммы Клоостермана, связанные с обратными элементами <math>x^{-1}</math>, где <math>x \in {\mathbb Z}_p,\ x x^{-1} \equiv 1 \pmod p</math>. Например, для <math>a, b \in {\mathbb Z}_q</math>:

<math>\sum \limits_{1 \le x \le q \atop (x, q) = 1} {e(a x + b x^{-1})}</math>

• дискретное преобразование Фурье для индикаторной функции множества <math>A \subset {\mathbb Z}_m,\ t \in {\mathbb Z}_m</math>:

<math>\widehat{A}(t) = \sum \limits_{a \in A} {e_m(at)}</math>

• мультилинейные суммы для множеств <math>A_1, \dots, A_k \subset {\mathbb Z}_m</math>:

<math>\sum \limits_{a_1 \in A_1} \dots \sum \limits_{a_k \in A_k} {e_m(a_1 \dots a_k)}</math>

• суммы мультипликативных характеров по множеству <math>A \subset {\mathbb F}_p^{*}</math> (функция <math>{\rm ind}</math> означает дискретный логарифм, а параметр <math>t \in {\mathbb Z}_p</math> соответствует выбранному характеру):

<math>\sum \limits_{a \in A} {e_p(t \cdot {\rm ind}(a))}\ ,</math>

Обобщения

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

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья

• Шаблон:Статья