Тригонометрическая сумма

Для множеств ${\displaystyle A_{1},\dots ,A_{k}}$ и функции ${\displaystyle f:A_{1}\times \dots \times A_{k}\to {\mathbb {Z} }_{m}}$ число решений уравнения

${\displaystyle f(x_{1},\dots ,x_{k})\equiv 0{\pmod {m}},\ x_{1}\in A_{1},\dots ,x_{k}\in A_{k}}$

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

${\displaystyle \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}(tf(x_{1},\dots ,x_{k}))}\ .}$

Аналогично, для целочисленной ${\displaystyle f}$ и решений ${\displaystyle f(x_{1},\dots ,x_{k})=0}$ допустимо представление

${\displaystyle \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 \ .}$

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

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

Тригонометрические выражения наиболее полезны когда функция ${\displaystyle f}$ хорошо разлагается на слагаемые. Например, если

${\displaystyle f(x_{1},\dots ,x_{k})=f_{1}(x_{1})+\dots +f_{k}(x_{k})\ ,}$

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

${\displaystyle \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}(tf_{i}(x_{i}))}\right)\leq \sum \limits _{t=0}^{m-1}\prod \limits _{i=1}^{k}{\Bigg \vert }\sum \limits _{x_{i}\in A_{i}}{e_{m}(tf_{i}(x_{i}))}{\Bigg \vert }\ .}$

Суммы ${\displaystyle \sum \limits _{x_{i}\in A_{i}}{e_{m}(tf_{i}(x_{i}))}}$ по отдельности друг от друга не имеют комбинаторной интерпретации, но могут быть оценены аналитически. Именно это делает метод тригонометрических сумм нетривиальным.

При ${\displaystyle t=0}$ все слагаемые вырождаются в ${\displaystyle e(0)=1}$, так что эта часть суммы всегда равна ${\displaystyle |A_{1}|\dots |A_{k}|}$ и называется главным членом. Поэтому оценки числа решений через тригонометрические суммы чаще всего не могут быть лучше чем ${\displaystyle {\frac {|A_{1}|\dots |A_{k}|}{m}}}$. В частности, именно такая величина нужна в доказательстве равномерного распределения. При работе с интегралами роль главного члена среди интервала ${\displaystyle [0;1]}$ выполняют окрестности несократимых дробей с малыми знаменателями[7].

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

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

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

${\displaystyle \sum \limits _{a=1}^{m}{{\Bigg \vert }{\sum \limits _{x\in I}{e_{m}(ax)}}{\Bigg \vert }}\leq m\ln m}$

Благодаря этому оценку тригонометрических сумм над множеством в ${\displaystyle {\mathbb {Z} }_{m}}$ можно преобразовывать в утверждение о его равномерном распределении в ${\displaystyle {\mathbb {Z} }_{m}}$[10]:

Чаще всего подобные результаты удобно получать для простого ${\displaystyle m}$. Известны оценки таких сумм для квадратичных вычетов[11], других степеней[12], индексов (дискретных логарифмов) чисел из интервала[13], обратных элементов для интервала[14] и даже для произвольной мультипликативной подгруппы размера ${\displaystyle p^{\varepsilon }}$ (для любого фиксированного ${\displaystyle \varepsilon >0}$)[15]. Похожий метод применим для доказательства равномерного распределения вещественных последовательностей в интервале ${\displaystyle (0;1)}$.

По аналогии с этим, суммы мультипликативных характеров можно воспринимать как показатель равномерности относительно структуры мультипликативной группы ${\displaystyle {\mathbb {F} }_{p}}$. Такие суммы хорошо изучены для интервалов, множества значений многочленов и сдвигов простых чисел[16].