Русская Википедия:Теорема Виноградова о среднем
Теорема Виноградова о среднем — теорема аналитической теории чисел об оценке среднего значения интеграла некоторых тригонометрических сумм, называемого также интегралом Виноградова; ключевой результат, используемый в методе тригонометрических сумм. Теорема представляет интерес, в частности, потому что оцениваемый в ней интеграл равен количеству решений в целых числах из достаточно большого интервала системы уравнений специального вида.
Принятые в статье обозначения
Поскольку теорема прямым образом касается тригонометрических сумм (а значит, и экспонент с комплексным показателем), то для краткости и удобства мы будем пользоваться обозначением <math>e\left({\alpha}\right) = e^{2 \pi \alpha i}</math>, где <math>\alpha \in {\mathbb R}</math> может быть любым числом.
Общее описание задачи
Пусть заданы фиксированные натуральные числа <math>n, k</math>. Рассмотрим систему уравнений
- <math> \left\{ \begin{matrix} x_1 + x_2 + \dots + x_k = y_1 + y_2 + \dots + y_k \\ {x_1}^2 + {x_2}^2 + \dots + {x_k}^2 = {y_1}^2 + {y_2}^2 + \dots + {y_k}^2 \\ \dots \\ {x_1}^n + {x_2}^n + \dots + {x_k}^n = {y_1}^n + {y_2}^n + \dots + {y_k}^n \end{matrix} \right. </math>
или, более формально,
- <math>\sum \limits_{j=1}^{k} {{x_j}^i} = \sum \limits_{j=1}^{k} {{y_j}^i}, i=1,\dots,n</math>
Потребность в рассмотрении такой системы возникает, например, при аналитическом решении проблемы Варинга, но может (в изменённых формулировках) применяться и в других областях.
Если обозначить через <math>J_{k,n}(P)</math> количество целочисленных решений указанной системы в пределах <math>x_i, y_i \in [1;P], i=1,\dots,k</math>, то основной вопрос формулируется так: как быстро растёт <math>J_{k,n}(P)</math> с ростом <math>P</math>?
Тривиальная оценкой, очевидно, будет <math>J_{k,n}(P) \le P^{2k}</math>
Теорема Виноградова даёт непосредственные (не асимптотические) намного лучшие, чем тривиальные, оценки сверху на величину <math>J_{k,n}(P)</math> при фиксированных <math>k</math> и <math>n</math>.
Формулировка в виде интеграла
Как обычно при использовании тригонометрических сумм, условие соответствия переменных уравнению можно выразить тождеством
- <math>\Bigg[ \sum \limits_{j=1}^{k} {{x_j}^i} - \sum \limits_{j=1}^{k} {{y_j}^i} = 0 \Bigg] = \int \limits_{0}^{1} { e \left({ \left({\sum \limits_{j=1}^{k} {{x_j}^i} - \sum \limits_{j=1}^{k} {{y_j}^i}}\right) \alpha }\right) d \alpha}</math>
Следовательно, количество решений системы уравнений удовлетворяет выражению
- <math>J_{n,k}(P) = \sum \limits_{1 \le x_j, y_j \le P} { \prod \limits_{i=1}^{n} { \int \limits_{0}^{1} { e \left({ \left({\sum \limits_{j=1}^{k} {{x_j}^i} - \sum \limits_{j=1}^{k} {{y_j}^i}}\right) \alpha }\right) d \alpha} } } = \sum \limits_{1 \le x_j, y_j \le P} \int \limits_{0}^{1} \dots \int \limits_{0}^{1} { e \left({ \sum \limits_{i=1}^{n} {\left({ \sum \limits_{j=1}^{k} {{x_j}^i} - \sum \limits_{j=1}^{k} {{y_j}^i} }\right) \alpha_i} }\right) } d \alpha_1 \dots d \alpha_n =</math>
- <math>= \int \limits_{0}^{1} \dots \int \limits_{0}^{1} { \sum \limits_{1 \le x_j, y_j \le P} e \left({ \sum \limits_{i=1}^{n} {\left({ \sum \limits_{j=1}^{k} {{x_j}^i} - \sum \limits_{j=1}^{k} {{y_j}^i} }\right) \alpha_i} }\right) } d \alpha_1 \dots d \alpha_n = \int \limits_{0}^{1} \dots \int \limits_{0}^{1} { \sum \limits_{1 \le x_j, y_j \le P} e {\left({ \sum \limits_{j=1}^{k} {\left({\sum \limits_{i=1}^{n} {x_j}^i \alpha_i}\right)} - \sum \limits_{j=1}^{k} {\left({\sum \limits_{i=1}^{n} {y_j}^i \alpha_i}\right)} }\right)} } d \alpha_1 \dots d \alpha_n =</math>
- <math>= \int \limits_{0}^{1} \dots \int \limits_{0}^{1} { \Bigg\vert{ \sum \limits_{x=1}^{P} e \left({ \sum \limits_{i=1}^{n} {\alpha_i x^i} }\right) }\Bigg\vert^{2k} } d \alpha_1 \dots d \alpha_n = \int \limits_{0}^{1} \dots \int \limits_{0}^{1} { \Bigg\vert{ \sum \limits_{x=1}^{P} e \left({ \alpha_1 x + \alpha_2 x^2 + \dots + \alpha_k x^k }\right) }\Bigg\vert^{2k} } d \alpha_1 \dots d \alpha_n</math>
Таким образом, искомая величина оценивается через интеграл по суммам Вейля и её можно оценивать, применяя общие для этих сумм методы.
Формулировки теоремы
Хотя основным преимуществом теоремы является ограничение порядка роста <math>J_{k,n}(P)</math> относительно <math>P</math>, сопровождающий этот порядок роста постоянный (при фиксрованных <math>k</math> и <math>n</math>) множитель при доказательстве также удаётся выразить явно.
Кроме того, оценки, получаемые в теореме, оказываются тем лучше, чем больше параметр <math>k</math> превосходит параметр <math>n</math>. Поэтому обычно вводится дополнительный параметр <math>\tau</math>, выражающий отношение <math>\frac{k}{n}</math> или каким-либо иным образом параметризующий рост <math>k</math> относительно <math>n</math>.
В связи с этим, а также в связи со сложностью доказательств теоремы и большим количеством деталей в нём, в различных формулировках теоремы используемые константы и выражения, зависящие только от <math>k</math> и <math>n</math>, могут отличаться. В частности, значения таких множителей уменьшались, а ограничения на значения <math>(k,n)</math> ослаблялись в разное время разными математиками.
В книге И. М. Виноградова 1971 года даётся следующая формулировка:
Шаблон:Рамка Пусть <math>n \ge 12</math>. Для целого <math>\tau</math> обозначим <math>k_{\tau} = n \tau + \left\lfloor{\frac{n(n+1)}{4} + 1}\right\rfloor</math>.
Тогда при <math>k > k_{\tau}</math> выполнено <math>J_{k,n}(P) < (20n)^{\frac{n(n+1)}{2} \tau} P^{2k - \frac{n(n+1)}{2} + \frac{n(n+1)}{2} \left({1 - \frac{1}{n}}\right)^\tau}</math> Шаблон:Конец рамки
В учебнике А. А. Карацубы 1983 года доказывается:
Шаблон:Рамка Пусть <math>\tau > 0</math> — целое, <math>k \ge n \tau</math>, <math>P \ge 1</math>. Тогда <math>J_{k,n}(P) \le D_{\tau, n} P^{2k - \delta(\tau, n)}</math>, где
<math>\delta(\tau, n) = \frac{n(n+1)}{2} \left({1 - \left({1 - \frac{1}{n}}\right)^{\tau}}\right)</math>;
<math>D_{\tau, n} = (n \tau)^{6 n \tau} (2n)^{4 n (n+1) \tau}</math>
Основная лемма
Суть утверждения
Вопрос об оценке числа решения системы уравнений
- <math> \left\{ \begin{matrix} x_1 + x_2 + \dots + x_k = y_1 + y_2 + \dots + y_k \\ {x_1}^2 + {x_2}^2 + \dots + {x_k}^2 = {y_1}^2 + {y_2}^2 + \dots + {y_k}^2 \\ \dots \\ {x_1}^n + {x_2}^n + \dots + {x_k}^n = {y_1}^n + {y_2}^n + \dots + {y_k}^n \end{matrix} \right. </math>
напрямую связан с вопросом о числе решений системы
- <math> \left\{ \begin{matrix} x_1 + x_2 + \dots + x_k = \lambda_1 \\ {x_1}^2 + {x_2}^2 + \dots + {x_k}^2 = \lambda_2 \\ \dots \\ {x_1}^n + {x_2}^n + \dots + {x_k}^n = \lambda_k \end{matrix} \right. </math>
при фиксированных <math>\lambda_1, \dots, \lambda_k</math>. Задачу, похожую на эту, но несколько облегчённую специальными условиями и ослаблением требований, удаётся решить напрямую. Именно решение такой задачи составляет основную лемму, играющую главную роль в доказательстве теоремы Виноградова. Специальные условия, необходимые для возможности непосредственного решения задачи, заключаются в том, что:
- предполагается, что количество переменных равно количеству уравнений;
- предполагается, что переменные принимают значения из разных, сильно отстоящих друг от друга, интервалов — то есть разница между любыми разными <math>x_i</math> и <math>x_j</math> превосходит некоторую заранее заданную величину;
- вместо требования равенства <math>{x_1}^s + {x_2}^s + \dots + {x_k}^s = \lambda_s</math> анализируется требование принадлежности к относительно короткому интервалу, то есть <math>{x_1}^s + {x_2}^s + \dots + {x_k}^s \in I_s</math> для заданного интервала <math>I_s</math> малой длины.
Ограниченность количества решений при заданных условиях очевидна ввиду выпуклости функций <math>x^2, x^3, \dots, x^n</math> — действительно, если функция <math>f</math> выпукла, а интервалы существенно далеко отстоят друг от друга, то и различие величин производной этой функции на этих интервалах сильно отличается. Это означает, что значения <math>f</math> на числах из второго интервала будут расположены на координатной прямой более разреженно, чем значения на числах из первого интервала. Следовательно, одинаковые по величине (но разнонаправленные) изменения каких-то двух переменных влекут, в большинстве случаев, неодинаковое по величине изменение значения функции, так что когда сумма <math>x_1+x_2</math> остаётся в рамках некоторого короткого интервала при изменении переменной <math>x_1</math>, то сумма <math>f(x_1)+f(x_2)</math> меняет значения в очень большом интервале. Если этот большой интервал больше требуемого, то количество решений, соответственно, будет маленьким.
Однако сами по себе соображения выпуклости в классическом доказательстве теоремы не используются, поскольку оно напрямую анализирует свойства целых степеней и коэффициенты получаемых из них многочленов.
Строгая формулировка
Здесь приводится формулировка из книги Карацубы. Формулировка в книге Виноградова аналогична, только несколько отличны множители, зависящие от <math>n</math>.
Шаблон:Рамка Пусть <math>n>2, P>{(2n)}^{4n}</math>, <math>H={(2n)}^{4}</math>, <math>R = \frac{P}{H}</math>. Пусть также <math>v_1, \dots, v_n</math> пробегают целые числа интервалов
- <math>X_1 < v_1 \le Y_1, \dots, X_n < v_n \le Y_n,</math>
где при некотором <math>\omega</math> с условием <math>0 \le \omega < P</math> имеем
- <math>-\omega < X_1,\ X_1+R=Y_1,\ Y_1+R \le X_2, \dots, X_n+R=Y_n, Y_n \le -\omega + P</math>
Тогда число <math>E_1</math> систем значений <math>v_1, \dots, v_n</math> таких, что суммы <math>V_1 = v_1 + \dots + v_n, \dots, V_n={v_1}^n+\dots+{v_n}^n</math> лежат, соответственно, в каких-либо интервалах с длинами <math>1, \dots, P^{n-1}</math>, удовлетворяет неравенству
- <math>E_1 < e^{r(n)-1} H^{\frac{n(n-1)}{2}},\ r(n)=-\frac{n^2}{2} \ln{n} + \frac{3}{4} n^2 + \frac{3}{2} n</math>
А если <math>{v_1}^{*}, \dots, {v_n}^{*}</math> пробегают те же значения, что и <math>v_1,\dots,v_n</math> (независимо от последних), то число <math>E</math> случаев, когда разности <math>V_1-{V_1}^{*}, \dots, V_n-{V_n}^{*}</math> лежат соответственно в каких-либо интервалах с длинами <math>P^{1-\frac{1}{n}}, \dots, P^{n\left({1-\frac{1}{n}}\right)}</math>, удовлетворяет неравенству
- <math>E < 2 e^{r(n)} H^{\frac{n(n-2)}{2}} P^{\frac{3n-1}{2}}</math>
Краткая схема доказательства
Основную сложность составляет доказательство оценки на <math>E_1</math>. Из неё оценка на <math>E</math> выводится тривиально.
Пусть есть две системы <math>(\eta_1,\dots,\eta_n)</math> и <math>(\eta_1+\xi_1, \dots, \eta_n+\xi_n)</math>, суммы степеней которых принадлежат заданным интервалам <math>I_1, \dots, I_n</math> и <math>\xi_n>0</math>. Это фактически означает, что
- <math> \left\{ \begin{matrix} (\eta_1 + \xi_1) - \eta_1 + \dots + (\eta_n + \xi_n) - \eta_n = \theta_1 |I_1| \\ (\eta_1 + \xi_1)^2 - {\eta_1}^2 + \dots + (\eta_n + \xi_n)^2 - {\eta_n}^2 = \theta_2 |I_2| \\ \dots \\ (\eta_1 + \xi_1)^n - {\eta_1}^n + \dots + (\eta_n + \xi_n)^n - {\eta_n}^n = \theta_n |I_n| \end{matrix} \right.</math>
где <math>\eta_1, \dots, \eta_n \in (-1;1)</math>. Если во все слагаемые подставить выражение <math>(\eta_i + \xi_i)^s - {\eta_i}^s = \frac{(\eta_i + \xi_i)^s - {\eta_i}^s}{\xi^s} \xi^s</math> и выразить <math>\xi_s</math> по методу Крамера через дроби вида <math>\frac{(\eta_i + \xi_i)^s - {\eta_i}^s}{\xi^s}</math> (явно раскрыв определители), то из теоремы Лагранжа будет следовать, что <math>\xi_s</math> удовлетворяет при некоторых <math>x_1 \in (\eta_1, \eta_1+\xi_1), \dots, x_n \in (\eta_n, \eta_n+\xi_n)</math> решению системы уравнений
- <math> \left\{ \begin{matrix} \xi_1 + \dots + \xi_n = \theta_1 |I_1| \\ x_1 \xi_1 + \dots x_n \xi_n = \theta_2 |I_2| \\ \dots \\ {x_1}^{n-1} \xi_1 + \dots {x_n}^{n-1} \xi_n = \theta |I_n| \end{matrix} \right.</math>
Матрица коэффициентов этой системы является матрицей Вандермонда и анализ решений системы оказывается легко произвести, исходя из общеизвестного выражения определителя таких матриц.
Схема доказательства теоремы
Теорема доказывается в интегральной формулировке. Доказательство проводится индукцией по <math>n</math> и <math>P</math> в несколько этапов:
- Интервал <math>[1;P]</math> разбивается на некоторое (зависящее от <math>n</math>) количество подинтервалов, и кратная тригонометрическая сумма под интегралом раскладывается на совокупность таких сумм по каждой возможной комбинации <math>k</math> таких интервалов;
- Все наборы подинтервалов делятся на две группы:
- наборы, среди которых есть хотя бы <math>n</math> таких, что никакие два из них не соседние и не совпадают;
- все остальные наборы.
- После этого общее количество решений ограничивается суммой количеств решений для наборов каждого из этих двух множеств (умноженной на константу 2).
- Из первого множества наборов выбирается какой-то один, для которого квадрат модуля тригонометрической суммы максимален. После этого сумма по всем наборам оценивается тривиально умножением суммы по лучшему набору на количество наборов.
- Через неравенство между арифметическим и геометрическим средними в выбранном наборе из первого множества <math>2k-2n</math> из <math>2k</math> переменных «вгоняются» в какой-то один интервал (то есть доказывается, что если они пробегают некоторый, один для всех, интервал вместо своего, то количество решений не уменьшается). То есть на данном этапе система уравнений приведена к виду, когда <math>2n</math> переменных пробегают разные, отстоящие друг от друга интервалы, а <math>2k-2n</math> переменных пробегают какой-то один и тот же интервал.
- Количество решений получившейся системы уравнений выражается суммой по произведениям количеств представлений того или иного числа
- Количество представлений разностью сумм переменных из <math>2k-2n</math> одинаковых интервалов выносится за скобки и оценивается через предположение индукции (поскольку и количество переменных и диапазон их значений малы по сравнению с начальными);
- После вынесения множителя за скобки выражение для количества решений уравнения превращается в выражение для количества решений неравенства, ограничивающего разность двух степенных сумм. Количество решений этого неравенства оценивается через основную лемму.
- Для второго множества наборов подинтервалов просто доказывается, что таких наборов очень мало. Далее опять все переменные приводятся к одному (но меньшему по длине, чем <math>P</math>) интервалу, а это уже позволяет применить предположение индукции к наилучшему из них (в смысле наибольшего количества решений).
Приложения
Исторически теорема впервые была использована при решении проблемы Варинга, однако иногда применяется и в других областях теории чисел — например, для оценки коротких сумм Клоостермана[1].
Примечания
Литература