Namespaces
Variants
Actions

Difference between revisions of "Vinogradov method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(Category:Number theory)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
{{TEX|done}}
 
A new method for estimating trigonometric sums (see [[Trigonometric sums, method of|Trigonometric sums, method of]]). By Vinogradov's method one may obtain very accurate estimates of a wide class of trigonometric sums, in which the summation variable runs through a sequence of integers, prime numbers, etc. In this way many classical problems in [[Analytic number theory|analytic number theory]] can be solved (the distribution of the fractional parts of a wide class of functions, the distribution of prime numbers in series of natural numbers, additive problems such as the Waring and Goldbach problems, etc.).
 
A new method for estimating trigonometric sums (see [[Trigonometric sums, method of|Trigonometric sums, method of]]). By Vinogradov's method one may obtain very accurate estimates of a wide class of trigonometric sums, in which the summation variable runs through a sequence of integers, prime numbers, etc. In this way many classical problems in [[Analytic number theory|analytic number theory]] can be solved (the distribution of the fractional parts of a wide class of functions, the distribution of prime numbers in series of natural numbers, additive problems such as the Waring and Goldbach problems, etc.).
  
One distinguishes two parts in Vinogradov's method: The method of estimating Weyl sums (cf. [[Weyl sum|Weyl sum]]) and the method of estimating trigonometric sums with prime numbers. Both these parts utilize Vinogradov's basic idea — to wit, the idea of smoothing double trigonometric sums, which may be described as follows. Given the sum
+
One distinguishes two parts in Vinogradov's method: The method of estimating Weyl sums (cf. [[Weyl sum|Weyl sum]]) and the method of estimating trigonometric sums with prime numbers. Both these parts utilize Vinogradov's basic idea — to wit, the idea of smoothing double trigonometric sums, which may be described as follows. Given the sum\[ W=\sum_u\sum_v\psi_1(u)\psi_2(v) e^{2\pi i\alpha uv},\]where the summation variables $u$ and $v$ run through the values of (not necessarily successive) integers in respective sets $U$ and $V$, $A<u<2A$. Let $\psi_1(u)$ and $\psi_2(v)$ be arbitrary complex-valued functions. Then
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966901.png" /></td> </tr></table>
+
\[ \lvert W\rvert^2\leq B\sum_{A< u\leq 2A}\left\lvert \sum_v\psi_2(v)e^{2\pi i\alpha uv}\right\rvert^2,\]
  
where the summation variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966902.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966903.png" /> run through the values of (not necessarily successive) integers in respective sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966904.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966905.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966906.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966907.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966908.png" /> be arbitrary complex-valued functions. Then
+
where $u$ runs through the successive integers in the interval $(A,2A]$ (smoothing), and
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v0966909.png" /></td> </tr></table>
+
\[ B=\sum_n\lvert \psi_1(u)\rvert^2.\]
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669010.png" /> runs through the successive integers in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669011.png" /> (smoothing), and
+
==Vinogradov's method for estimating Weyl sums.==
 
 
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669012.png" /></td> </tr></table>
 
  
==Vinogradov's method for estimating Weyl sums.==
 
 
The sums to be estimated are
 
The sums to be estimated are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669013.png" /></td> </tr></table>
+
\[ S=\sum_{1\leq x\leq P}e^{2\pi if(x)},\]
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669014.png" />; here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669015.png" /> are real numbers. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669016.png" /> one finds
+
where $f(x)=\alpha_{n+1}x^{n+1}+\cdots+\alpha_1x$; here $\alpha_{n+1},\ldots,\alpha_1$ are real numbers. For $Y=[P^{1-n^2/4}]$ one finds
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669017.png" /></td> </tr></table>
+
\begin{align*}
 +
S&=Y^{-1}\sum_{1\leq x\leq P}\sum_{1\leq y\leq Y}e^{2\pi if(x+y)}+2\theta Y\\
 +
&=Y^{-1}\sum_{1\leq x\leq P}\sum_{1\leq y\leq Y}e^{2\pi i\mathfrak{A}}+2\theta Y=Y^{-1}W+2\theta Y,
 +
\end{align*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669018.png" /></td> </tr></table>
+
where $\mathfrak{A}=\alpha_{n+1}x^{n+1}+A_n(y)x^n+\cdots+A_1(y)x+A_0(y)$, the letter $W$ denotes the double sum over $x$ and $y$, and $\lvert \theta\rvert\leq 1$. Moreover, letting $\mathfrak{B}$ denote the expression
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669019.png" />, the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669020.png" /> denotes the double sum over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669022.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669023.png" />. Moreover, letting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669024.png" /> denote the expression
+
\[ \alpha_{n+1}x^{n+1}+(A_n(y)+B_n)x^n+\cdots+(A_1(y)+B_1)x\]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669025.png" /></td> </tr></table>
+
one has
  
one has
+
\[\lvert W\rvert\leq \sum_{1\leq y\leq Y}\left\lvert \sum_{1\leq x\leq P}e^{2\pi i\mathfrak{B}}\right\rvert+Y_nP^{1-n^2/4},\]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669026.png" /></td> </tr></table>
+
for arbitrary $B_n,\ldots,B_1$ from the domain
  
for arbitrary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669027.png" /> from the domain
+
\[\lvert B_n\rvert\leq L_n=P^{-n-n^2/4},\ldots,\lvert B_1\rvert\leq L_1=P^{-1-n^2/4}.\]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669028.png" /></td> </tr></table>
+
For any integer $k\geq 1$:
  
For any integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669029.png" />:
+
\begin{align*}
 +
\lvert W\rvert^{2k}
 +
&\leq 2^kY^{2k-1}\sum_{1\leq y\leq Y}\int_{\lvert B_n\rvert\leq L_n}\cdots \int_{\lvert B_1\rvert\leq L_1}\left\lvert \sum_{1\leq x\leq P} e^{2\pi i\mathfrak{B}}\right\rvert\mathrm{d}B_n\cdots\mathrm{d}B_1+2^k(Y_nP^{1-n^2/4})^{2k}\\
 +
&\leq 2^kY^{2k-1}G(Y)\int_0^1\cdots \int_0^1\left\lvert \sum_{1\leq x\leq P}e^{2\pi i\mathfrak{C}}\right\rvert^{2k}\mathrm{d}\gamma_n\cdots\mathrm{d}\gamma_1+2^k(Y_nP^{1-n^2/4})^{2k},
 +
\end{align*}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669030.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669031.png" /></td> </tr></table>
+
where $\mathfrak{C}=\alpha_{n+1}x^{n+1}+\gamma_nx^n+\cdots+\gamma_1x$ and $G(Y)$ is the maximum number of cases of coincidence of points with coordinates
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669032.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669033.png" /></td> </tr></table>
+
\[ \{A_n(y)+B_n\},\{A_{n-1}(y)+B_{n-1}\},\ldots,\{A_1(y)+B_1\}.\]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669034.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669035.png" /></td> </tr></table>
+
Here the braces denote the fractional part of the enclosed number, while $y$ varies between 1 and $Y$, and
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669036.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669037.png" /> is the maximum number of cases of coincidence of points with coordinates
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669038.png" /></td> </tr></table>
+
\[\lvert B_n\rvert\leq L_n,\ldots,\lvert B_1\rvert\leq L_1.\]
  
Here the braces denote the fractional part of the enclosed number, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669039.png" /> varies between 1 and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669040.png" />, and
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669041.png" /></td> </tr></table>
+
If the coefficients $\alpha_{n+1},\ldots,\alpha_2$ of the polynomial $f(x)$ have certain arithmetical properties, it is possible to obtain the estimate $G(Y)\leq Y^{0.9}$. In addition, the last integral does not exceed the number of solutions of the system of equations:
  
If the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669042.png" /> of the polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669043.png" /> have certain arithmetical properties, it is possible to obtain the estimate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669044.png" />. In addition, the last integral does not exceed the number of solutions of the system of equations:
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669045.png" /></td> </tr></table>
+
\begin{align*}
 +
x_1^n+\cdots+x_k^n &= y_1^n+\cdots+y_k^n,\\
 +
x_1^{n-1}+\cdots+x_k^{n-1} &= y_1^{n-1}+\cdots+y_k^{n-1},\\
 +
\vdots\\
 +
x_1+\cdots+x_k &= y_1+\cdots+y_k,
 +
\end{align*}
 +
\[ 1\leq x_1,\ldots,y_k\leq P.\]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669046.png" /></td> </tr></table>
 
  
 
The number of solutions of this system is estimated using the [[Vinogradov theorem about the average|Vinogradov theorem about the average]], which is fundamental in Vinogradov's method for estimating Weyl sums (cf. [[Vinogradov estimates|Vinogradov estimates]]).
 
The number of solutions of this system is estimated using the [[Vinogradov theorem about the average|Vinogradov theorem about the average]], which is fundamental in Vinogradov's method for estimating Weyl sums (cf. [[Vinogradov estimates|Vinogradov estimates]]).
 +
  
 
==Vinogradov's method for estimating trigonometric sums with prime numbers.==
 
==Vinogradov's method for estimating trigonometric sums with prime numbers.==
 +
 +
 
The sums to be estimated are
 
The sums to be estimated are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669047.png" /></td> </tr></table>
 
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669048.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669049.png" /> are real numbers. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669050.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669051.png" />. Using the well-known property of the Möbius function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669052.png" /> is reduced to a small number of sums (this number is not larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669053.png" />) of the form
+
\[ S' = \sum_{p\leq P}e^{2\pi i f(p) },\]
 +
 
 +
 
 +
where $f(p)=\alpha_np^n+\cdots+\alpha_1p$, and $\alpha_n,\ldots,\alpha_1$ are real numbers. Let $D=\prod_{p\leq H}p$, where $H\leq P^{0.25}$. Using the well-known property of the Möbius function, $S'$ is reduced to a small number of sums (this number is not larger than $\ln P/\ln H$) of the form
 +
 
 +
 
 +
\[W_S=\sum_{d_1\mid D}\cdots \sum_{d_s\mid D}\sum_{m_1>0}\cdots\sum_{m_s>0}\mu(d_1)\cdots\mu(d_s)e^{2\pi i f(m_1\cdots m_sd_1\cdots d_s)},\]
 +
 
 +
 
 +
where $m_1\cdots m_sd_1\cdots d_s\leq P$. In the multiple sum $W_S$ the variables $m_1,\ldots,m_s$ run through the entire summation intervals. The sums $W_S$ in which the summation interval over at least one variable $m$ is long are estimated by Vinogradov's method for estimating Weyl sums. Otherwise the summation interval over one of the summation variables $d$, $d\mid D$, will be long. In such a case one uses the following lemma of Vinogradov which, together with the idea of smoothing double sums, is fundamental to Vinogradov's method for estimating trigonometric sums with prime numbers.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669054.png" /></td> </tr></table>
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669055.png" /></td> </tr></table>
+
Lemma. Let $0\leq \sigma\leq 1/3$ and let $D$ be the product of all primes not larger than $x^{\sigma}$; all divisors $d$ of $D$ not larger than $x$ may then be distributed over fewer than $x^{\epsilon}$ sets with the following properties:
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669056.png" />. In the multiple sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669057.png" /> the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669058.png" /> run through the entire summation intervals. The sums <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669059.png" /> in which the summation interval over at least one variable <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669060.png" /> is long are estimated by Vinogradov's method for estimating Weyl sums. Otherwise the summation interval over one of the summation variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669061.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669062.png" />, will be long. In such a case one uses the following lemma of Vinogradov which, together with the idea of smoothing double sums, is fundamental to Vinogradov's method for estimating trigonometric sums with prime numbers.
 
  
Lemma. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669063.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669064.png" /> be the product of all primes not larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669065.png" />; all divisors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669066.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669067.png" /> not larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669068.png" /> may then be distributed over fewer than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669069.png" /> sets with the following properties:
+
1) the numbers $d$ belonging to one of these sets have the same number $\beta$ of prime factors and therefore the same value of $\mu(d)=(-1)^\beta$;
  
1) the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669070.png" /> belonging to one of these sets have the same number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669071.png" /> of prime factors and therefore the same value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669072.png" />;
 
  
2) one of these sets — the so-called simplest set — consists of the single number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669073.png" />. For each of the remaining sets there is a number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669074.png" /> such that all numbers of this set satisfy the relation
+
2) one of these sets — the so-called simplest set — consists of the single number $d=1$. For each of the remaining sets there is a number $\phi$ such that all numbers of this set satisfy the relation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669075.png" /></td> </tr></table>
+
\[\phi< d\leq \phi^{1+\epsilon_1},\hspace{1cm} \epsilon_1=\epsilon_1(\epsilon);\]
  
3) for each set of numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669076.png" /> other than the simplest set there exist, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669077.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669078.png" />, two sets of numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669079.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669080.png" />, with corresponding numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669081.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669082.png" /> satisfying the relations
+
3) for each set of numbers $d$ other than the simplest set there exist, for any $U$, $0\leq U\leq \phi$, two sets of numbers $d'$ and $d''$, with corresponding numbers $\phi'$ and $\phi''$ satisfying the relations
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669083.png" /></td> </tr></table>
+
\[U<\phi'\leq Ux^{\sigma},\hspace{1cm}\phi'\phi''=\phi,\]
  
and such that, for a certain natural number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669084.png" />, one obtains each number in the chosen set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669085.png" /> times if, out of all the products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669086.png" /> one selects only those which satisfy the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669087.png" />.
+
and such that, for a certain natural number $B$, one obtains each number in the chosen set $B$ times if, out of all the products $d'd''$ one selects only those which satisfy the relation $(d',d'')=1$.
  
The application of point 3) of this lemma, with a suitable value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669088.png" />, yields
+
The application of point 3) of this lemma, with a suitable value of $U$, yields
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669089.png" /></td> </tr></table>
+
\[ W_S=\sum_u\sum_v\psi_1(u)\psi_2(v)e^{2\pi i f(uv) },\]
  
where the variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669090.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669091.png" /> run through long summation intervals. It is possible to deduce Vinogradov's estimate for trigonometric sums with prime numbers from this lemma (cf. [[Vinogradov estimates|Vinogradov estimates]]).
+
where the variables $u$ and $v$ run through long summation intervals. It is possible to deduce Vinogradov's estimate for trigonometric sums with prime numbers from this lemma (cf. [[Vinogradov estimates|Vinogradov estimates]]).
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669092.png" /> can be properly approximated, in a certain sense, by a polynomial, Vinogradov's method can be used to estimate sums of the type
+
If $F(x)$ can be properly approximated, in a certain sense, by a polynomial, Vinogradov's method can be used to estimate sums of the type
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669093.png" /></td> </tr></table>
+
\[S=\sum_{1\leq x\leq P}e^{2\pi i F(x)},\hspace{1cm} S'=\sum_{p\leq P}e^{2\pi i F(p)}\]
  
 
(see [[#References|[2]]], ). Sums of the type
 
(see [[#References|[2]]], ). Sums of the type
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669094.png" /></td> </tr></table>
+
\[ \sum_{p\leq P}\chi(p+a),\hspace{1cm} \sum_{1\leq n\leq N}\mu(n)\chi(n+a)\]
  
and other types can also be estimated by the method. It is possible in this way to solve problems on the distribution of power residues, primitive roots, etc., in sequences of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669095.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669096.png" /> is a given integer, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v096/v096690/v09669097.png" /> runs through the successive prime numbers [[#References|[3]]], [[#References|[5]]]. For the application of Vinogradov's method in analytic number theory see [[#References|[1]]], [[#References|[2]]], , [[#References|[5]]], [[#References|[6]]].
+
and other types can also be estimated by the method. It is possible in this way to solve problems on the distribution of power residues, primitive roots, etc., in sequences of the type $p+a$, where $a>0$ is a given integer, while $p$ runs through the successive prime numbers [[#References|[3]]], [[#References|[5]]]. For the application of Vinogradov's method in analytic number theory see [[#References|[1]]], [[#References|[2]]], , [[#References|[5]]], [[#References|[6]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Interscience  (1954)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  I.M. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Estimates of a sum, distribution of primes in an arithmetic series"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''30'''  (1966)  pp. 481–496  (In Russian)</TD></TR><TR><TD valign="top">[4a]</TD> <TD valign="top">  A.A. Karatsuba,  "Estimates for trigonometric sums by Vinogradov's method, and applications"  ''Proc. Steklov Inst. Math.'' , '''112'''  (1971)  pp. 251–265  ''Trudy Mat. Inst. Steklov.'' , '''112'''  (1971)  pp. 241–255</TD></TR><TR><TD valign="top">[4b]</TD> <TD valign="top">  A.A. Karatsuba,  "On some problems of prime number theory connected with I.M. Vinogradov's method"  ''Proc. Steklov Inst. Math.'' , '''132'''  (1973)  pp. 293–298  ''Trudy Mat. Inst. Steklov.'' , '''132'''  (1973)  pp. 257–261</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  L.-K. Hua,  "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , ''Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen'' , '''1''' :  2  (1959)  (Heft 13, Teil 1)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  K. Chandrasekharan,  "Arithmetical functions" , Springer  (1970)</TD></TR></table>
 
 
  
  
====Comments====
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Interscience  (1954)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  I.M. Vinogradov,  "Selected works" , Springer  (1985)  (Translated from Russian)</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top">  I.M. Vinogradov,  "Estimates of a sum, distribution of primes in an arithmetic series"  ''Izv. Akad. Nauk SSSR Ser. Mat.'' , '''30'''  (1966)  pp. 481–496  (In Russian)</TD></TR>
 +
<TR><TD valign="top">[4a]</TD> <TD valign="top">  A.A. Karatsuba,  "Estimates for trigonometric sums by Vinogradov's method, and applications"  ''Proc. Steklov Inst. Math.'' , '''112'''  (1971)  pp. 251–265  ''Trudy Mat. Inst. Steklov.'' , '''112'''  (1971)  pp. 241–255</TD></TR>
 +
<TR><TD valign="top">[4b]</TD> <TD valign="top">  A.A. Karatsuba,  "On some problems of prime number theory connected with I.M. Vinogradov's method"  ''Proc. Steklov Inst. Math.'' , '''132'''  (1973)  pp. 293–298  ''Trudy Mat. Inst. Steklov.'' , '''132'''  (1973)  pp. 257–261</TD></TR>
 +
<TR><TD valign="top">[5]</TD> <TD valign="top">  L.-K. Hua,  "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , ''Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen'' , '''1''' :  2  (1959)  (Heft 13, Teil 1)</TD></TR>
 +
<TR><TD valign="top">[6]</TD> <TD valign="top">  K. Chandrasekharan,  "Arithmetical functions" , Springer  (1970)</TD></TR>
 +
</table>
  
 +
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  R.C. Vaughan,  "The Hardy–Littlewood method" , Cambridge Univ. Press  (1981)</TD></TR>
 +
</table>
  
====References====
+
[[Category:Number theory]]
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  R.C. Vaughan,  "The Hardy–Littlewood method" , Cambridge Univ. Press  (1981)</TD></TR></table>
 

Latest revision as of 09:42, 9 November 2014

A new method for estimating trigonometric sums (see Trigonometric sums, method of). By Vinogradov's method one may obtain very accurate estimates of a wide class of trigonometric sums, in which the summation variable runs through a sequence of integers, prime numbers, etc. In this way many classical problems in analytic number theory can be solved (the distribution of the fractional parts of a wide class of functions, the distribution of prime numbers in series of natural numbers, additive problems such as the Waring and Goldbach problems, etc.).

One distinguishes two parts in Vinogradov's method: The method of estimating Weyl sums (cf. Weyl sum) and the method of estimating trigonometric sums with prime numbers. Both these parts utilize Vinogradov's basic idea — to wit, the idea of smoothing double trigonometric sums, which may be described as follows. Given the sum\[ W=\sum_u\sum_v\psi_1(u)\psi_2(v) e^{2\pi i\alpha uv},\]where the summation variables $u$ and $v$ run through the values of (not necessarily successive) integers in respective sets $U$ and $V$, $A<u<2A$. Let $\psi_1(u)$ and $\psi_2(v)$ be arbitrary complex-valued functions. Then

\[ \lvert W\rvert^2\leq B\sum_{A< u\leq 2A}\left\lvert \sum_v\psi_2(v)e^{2\pi i\alpha uv}\right\rvert^2,\]

where $u$ runs through the successive integers in the interval $(A,2A]$ (smoothing), and

\[ B=\sum_n\lvert \psi_1(u)\rvert^2.\]

Vinogradov's method for estimating Weyl sums.

The sums to be estimated are

\[ S=\sum_{1\leq x\leq P}e^{2\pi if(x)},\]

where $f(x)=\alpha_{n+1}x^{n+1}+\cdots+\alpha_1x$; here $\alpha_{n+1},\ldots,\alpha_1$ are real numbers. For $Y=[P^{1-n^2/4}]$ one finds

\begin{align*} S&=Y^{-1}\sum_{1\leq x\leq P}\sum_{1\leq y\leq Y}e^{2\pi if(x+y)}+2\theta Y\\ &=Y^{-1}\sum_{1\leq x\leq P}\sum_{1\leq y\leq Y}e^{2\pi i\mathfrak{A}}+2\theta Y=Y^{-1}W+2\theta Y, \end{align*}

where $\mathfrak{A}=\alpha_{n+1}x^{n+1}+A_n(y)x^n+\cdots+A_1(y)x+A_0(y)$, the letter $W$ denotes the double sum over $x$ and $y$, and $\lvert \theta\rvert\leq 1$. Moreover, letting $\mathfrak{B}$ denote the expression

\[ \alpha_{n+1}x^{n+1}+(A_n(y)+B_n)x^n+\cdots+(A_1(y)+B_1)x\]

one has

\[\lvert W\rvert\leq \sum_{1\leq y\leq Y}\left\lvert \sum_{1\leq x\leq P}e^{2\pi i\mathfrak{B}}\right\rvert+Y_nP^{1-n^2/4},\]

for arbitrary $B_n,\ldots,B_1$ from the domain

\[\lvert B_n\rvert\leq L_n=P^{-n-n^2/4},\ldots,\lvert B_1\rvert\leq L_1=P^{-1-n^2/4}.\]

For any integer $k\geq 1$:

\begin{align*} \lvert W\rvert^{2k} &\leq 2^kY^{2k-1}\sum_{1\leq y\leq Y}\int_{\lvert B_n\rvert\leq L_n}\cdots \int_{\lvert B_1\rvert\leq L_1}\left\lvert \sum_{1\leq x\leq P} e^{2\pi i\mathfrak{B}}\right\rvert\mathrm{d}B_n\cdots\mathrm{d}B_1+2^k(Y_nP^{1-n^2/4})^{2k}\\ &\leq 2^kY^{2k-1}G(Y)\int_0^1\cdots \int_0^1\left\lvert \sum_{1\leq x\leq P}e^{2\pi i\mathfrak{C}}\right\rvert^{2k}\mathrm{d}\gamma_n\cdots\mathrm{d}\gamma_1+2^k(Y_nP^{1-n^2/4})^{2k}, \end{align*}


where $\mathfrak{C}=\alpha_{n+1}x^{n+1}+\gamma_nx^n+\cdots+\gamma_1x$ and $G(Y)$ is the maximum number of cases of coincidence of points with coordinates


\[ \{A_n(y)+B_n\},\{A_{n-1}(y)+B_{n-1}\},\ldots,\{A_1(y)+B_1\}.\]


Here the braces denote the fractional part of the enclosed number, while $y$ varies between 1 and $Y$, and


\[\lvert B_n\rvert\leq L_n,\ldots,\lvert B_1\rvert\leq L_1.\]


If the coefficients $\alpha_{n+1},\ldots,\alpha_2$ of the polynomial $f(x)$ have certain arithmetical properties, it is possible to obtain the estimate $G(Y)\leq Y^{0.9}$. In addition, the last integral does not exceed the number of solutions of the system of equations:


\begin{align*} x_1^n+\cdots+x_k^n &= y_1^n+\cdots+y_k^n,\\ x_1^{n-1}+\cdots+x_k^{n-1} &= y_1^{n-1}+\cdots+y_k^{n-1},\\ \vdots\\ x_1+\cdots+x_k &= y_1+\cdots+y_k, \end{align*} \[ 1\leq x_1,\ldots,y_k\leq P.\]


The number of solutions of this system is estimated using the Vinogradov theorem about the average, which is fundamental in Vinogradov's method for estimating Weyl sums (cf. Vinogradov estimates).


Vinogradov's method for estimating trigonometric sums with prime numbers.

The sums to be estimated are


\[ S' = \sum_{p\leq P}e^{2\pi i f(p) },\]


where $f(p)=\alpha_np^n+\cdots+\alpha_1p$, and $\alpha_n,\ldots,\alpha_1$ are real numbers. Let $D=\prod_{p\leq H}p$, where $H\leq P^{0.25}$. Using the well-known property of the Möbius function, $S'$ is reduced to a small number of sums (this number is not larger than $\ln P/\ln H$) of the form


\[W_S=\sum_{d_1\mid D}\cdots \sum_{d_s\mid D}\sum_{m_1>0}\cdots\sum_{m_s>0}\mu(d_1)\cdots\mu(d_s)e^{2\pi i f(m_1\cdots m_sd_1\cdots d_s)},\]


where $m_1\cdots m_sd_1\cdots d_s\leq P$. In the multiple sum $W_S$ the variables $m_1,\ldots,m_s$ run through the entire summation intervals. The sums $W_S$ in which the summation interval over at least one variable $m$ is long are estimated by Vinogradov's method for estimating Weyl sums. Otherwise the summation interval over one of the summation variables $d$, $d\mid D$, will be long. In such a case one uses the following lemma of Vinogradov which, together with the idea of smoothing double sums, is fundamental to Vinogradov's method for estimating trigonometric sums with prime numbers.


Lemma. Let $0\leq \sigma\leq 1/3$ and let $D$ be the product of all primes not larger than $x^{\sigma}$; all divisors $d$ of $D$ not larger than $x$ may then be distributed over fewer than $x^{\epsilon}$ sets with the following properties:


1) the numbers $d$ belonging to one of these sets have the same number $\beta$ of prime factors and therefore the same value of $\mu(d)=(-1)^\beta$;


2) one of these sets — the so-called simplest set — consists of the single number $d=1$. For each of the remaining sets there is a number $\phi$ such that all numbers of this set satisfy the relation

\[\phi< d\leq \phi^{1+\epsilon_1},\hspace{1cm} \epsilon_1=\epsilon_1(\epsilon);\]

3) for each set of numbers $d$ other than the simplest set there exist, for any $U$, $0\leq U\leq \phi$, two sets of numbers $d'$ and $d''$, with corresponding numbers $\phi'$ and $\phi''$ satisfying the relations

\[U<\phi'\leq Ux^{\sigma},\hspace{1cm}\phi'\phi''=\phi,\]

and such that, for a certain natural number $B$, one obtains each number in the chosen set $B$ times if, out of all the products $d'd''$ one selects only those which satisfy the relation $(d',d'')=1$.

The application of point 3) of this lemma, with a suitable value of $U$, yields

\[ W_S=\sum_u\sum_v\psi_1(u)\psi_2(v)e^{2\pi i f(uv) },\]

where the variables $u$ and $v$ run through long summation intervals. It is possible to deduce Vinogradov's estimate for trigonometric sums with prime numbers from this lemma (cf. Vinogradov estimates).

If $F(x)$ can be properly approximated, in a certain sense, by a polynomial, Vinogradov's method can be used to estimate sums of the type

\[S=\sum_{1\leq x\leq P}e^{2\pi i F(x)},\hspace{1cm} S'=\sum_{p\leq P}e^{2\pi i F(p)}\]

(see [2], ). Sums of the type

\[ \sum_{p\leq P}\chi(p+a),\hspace{1cm} \sum_{1\leq n\leq N}\mu(n)\chi(n+a)\]

and other types can also be estimated by the method. It is possible in this way to solve problems on the distribution of power residues, primitive roots, etc., in sequences of the type $p+a$, where $a>0$ is a given integer, while $p$ runs through the successive prime numbers [3], [5]. For the application of Vinogradov's method in analytic number theory see [1], [2], , [5], [6].

References

[1] I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers" , Interscience (1954) (Translated from Russian)
[2] I.M. Vinogradov, "Selected works" , Springer (1985) (Translated from Russian)
[3] I.M. Vinogradov, "Estimates of a sum, distribution of primes in an arithmetic series" Izv. Akad. Nauk SSSR Ser. Mat. , 30 (1966) pp. 481–496 (In Russian)
[4a] A.A. Karatsuba, "Estimates for trigonometric sums by Vinogradov's method, and applications" Proc. Steklov Inst. Math. , 112 (1971) pp. 251–265 Trudy Mat. Inst. Steklov. , 112 (1971) pp. 241–255
[4b] A.A. Karatsuba, "On some problems of prime number theory connected with I.M. Vinogradov's method" Proc. Steklov Inst. Math. , 132 (1973) pp. 293–298 Trudy Mat. Inst. Steklov. , 132 (1973) pp. 257–261
[5] L.-K. Hua, "Abschätzungen von Exponentialsummen und ihre Anwendung in der Zahlentheorie" , Enzyklopaedie der Mathematischen Wissenschaften mit Einschluss ihrer Anwendungen , 1 : 2 (1959) (Heft 13, Teil 1)
[6] K. Chandrasekharan, "Arithmetical functions" , Springer (1970)
[a1] R.C. Vaughan, "The Hardy–Littlewood method" , Cambridge Univ. Press (1981)
How to Cite This Entry:
Vinogradov method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Vinogradov_method&oldid=12709
This article was adapted from an original article by A.A. Karatsuba (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article