Namespaces
Variants
Actions

Difference between revisions of "Exponential sum estimates"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (correction)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 91 formulas, 86 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|part}}
 
Exponential sums have the form
 
Exponential sums have the form
  
<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/e/e130/e130070/e1300701.png" /></td> </tr></table>
+
\begin{equation*} S = \sum _ { n \in A } e ^ { 2 \pi i f ( n ) }, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300702.png" /> is a finite set of integers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300703.png" /> is a real-valued function (cf. also [[Trigonometric sum|Trigonometric sum]]). The basic problem is to show, under suitable circumstances, that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300704.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300705.png" />. Unless there are obvious reasons to the contrary one actually expects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300706.png" /> to have order around <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300707.png" />. Exponential sums in more than one variable also occur, and much of what is stated below can be generalized to such sums.
+
where $A$ is a finite set of integers and $f$ is a real-valued function (cf. also [[Trigonometric sum|Trigonometric sum]]). The basic problem is to show, under suitable circumstances, that $S = o ( \# A )$ as $\# A \rightarrow \infty$. Unless there are obvious reasons to the contrary one actually expects $S$ to have order around $( \# A ) ^ { 1 / 2 }$. Exponential sums in more than one variable also occur, and much of what is stated below can be generalized to such sums.
  
 
==Arithmetic sums.==
 
==Arithmetic sums.==
There are two common types of exponential sum encountered in [[Analytic number theory|analytic number theory]]. In the first type, one starts with polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300708.png" />, a positive integer modulus <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e1300709.png" />, and a finite interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007010.png" />. One then takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007011.png" /> as the set of integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007012.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007013.png" />, and sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007014.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007015.png" /> is any integer for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007016.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007017.png" />, such a sum is called complete. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007018.png" /> one may estimate the incomplete sum in terms of complete ones via the bound
+
There are two common types of exponential sum encountered in [[Analytic number theory|analytic number theory]]. In the first type, one starts with polynomials $g ( X ) , h ( X ) \in \mathbf{Z} [ X ]$, a positive integer modulus $q$, and a finite interval $I \subset \mathbf{R}$. One then takes $A$ as the set of integers $n \in I$ for which $\operatorname{GCD} ( h ( n ) , q ) = 1$, and sets $f ( n ) = g ( n ) \overline { h ( n ) } / q$, where $\overline { h ( n ) }$ is any integer for which $h ( n ) \overline { h ( n ) } \equiv 1 ( \operatorname { mod } q )$. When $I = ( 0 , q ]$, such a sum is called complete. When $I \subseteq ( 0 , q ]$ one may estimate the incomplete sum in terms of complete ones via the bound
  
<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/e/e130/e130070/e13007019.png" /></td> </tr></table>
+
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007019.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/e/e130/e130070/e13007020.png" /></td> </tr></table>
+
<table class="eq" style="width:100%;"> <tr><td style="width:94%;text-align:center;" valign="top"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007020.png"/></td> </tr></table>
  
Complete sums have multiplicative properties which enable one to reduce consideration to the case in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007021.png" /> is a prime number or a power of a prime number. Moreover, Weil's Riemann hypothesis for curves over finite fields (see [[#References|[a4]]], for example) shows that, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007022.png" /> is prime, then
+
Complete sums have multiplicative properties which enable one to reduce consideration to the case in which $q$ is a prime number or a power of a prime number. Moreover, Weil's Riemann hypothesis for curves over finite fields (see [[#References|[a4]]], for example) shows that, if $q$ is prime, 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/e/e130/e130070/e13007023.png" /></td> </tr></table>
+
\begin{equation*} \left| \sum _ { n \in I \atop ( h ( n ) , q ) = 1 } e ^ { 2 \pi i g ( n ) \overline { h  ( n )} / q } \right| \leq ( \operatorname { deg } ( g ) + \operatorname { deg } ( h ) ) \sqrt { q }, \end{equation*}
  
except when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007024.png" /> is constant modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007025.png" />. For powers of a prime number the situation is more complicated, but broadly similar. It follows that, for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007026.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007028.png" /> prime, the incomplete sum will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007029.png" /> as soon as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007030.png" />. It is an important outstanding problem (as of 2000) to improve on this in general.
+
except when $g ( n ) \overline { h ( n ) }$ is constant modulo $q$. For powers of a prime number the situation is more complicated, but broadly similar. It follows that, for fixed $g$ and $h$ and $q$ prime, the incomplete sum will be $o ( \# A )$ as soon as $\# A / ( \sqrt { q }\operatorname { log } q  ) \rightarrow \infty$. It is an important outstanding problem (as of 2000) to improve on this in general.
  
 
==Analytic sums.==
 
==Analytic sums.==
The second type of exponential sum arises when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007031.png" /> extends to a suitably smooth function on a real interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007032.png" />. Important examples correspond to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007033.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007034.png" />, or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007035.png" />, which occur in the theory of Waring's problem and the [[Riemann zeta-function|Riemann zeta-function]], respectively (cf. also [[Waring problem|Waring problem]]; [[Zeta-function|Zeta-function]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007036.png" /> with positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007037.png" />. One typically imposes the condition that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007038.png" /> with
+
The second type of exponential sum arises when $f$ extends to a suitably smooth function on a real interval $I$. Important examples correspond to $f ( n ) = \alpha n ^ { k }$ for $k \in \mathbf{N}$, or $f ( n ) = ( t / 2 \pi ) \operatorname { log } n$, which occur in the theory of Waring's problem and the [[Riemann zeta-function|Riemann zeta-function]], respectively (cf. also [[Waring problem|Waring problem]]; [[Zeta-function|Zeta-function]]). Let $I = ( N , N + M ]$ with positive integers $M \leq N$. One typically imposes the condition that $f \in C ^ { \infty } [ N , N + M ]$ with
  
<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/e/e130/e130070/e13007039.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
\begin{equation} \tag{a1} c _ { k } T N ^ { - k } \leq \left| f ^ { ( k ) } ( x ) \right| \leq c _ { k } ^ { \prime } T N ^ { - k } \end{equation}
  
<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/e/e130/e130070/e13007040.png" /></td> </tr></table>
+
\begin{equation*} ( k \in {\bf N} , N \leq x \leq N + M ), \end{equation*}
  
for suitable constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007042.png" />. Methods due to H. Weyl (see [[#References|[a5]]], Chap. 2), J. van der Corput (see [[#References|[a1]]]), I.M. Vinogradov and N.M. Korobov (see [[#References|[a3]]], Chap. 6), and E. Bombieri and H. Iwaniec (see [[#References|[a2]]]) have been used for sums of this type.
+
for suitable constants <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007041.png"/>, $ { c } _ { k } ^ { \prime }$. Methods due to H. Weyl (see [[#References|[a5]]], Chap. 2), J. van der Corput (see [[#References|[a1]]]), I.M. Vinogradov and N.M. Korobov (see [[#References|[a3]]], Chap. 6), and E. Bombieri and H. Iwaniec (see [[#References|[a2]]]) have been used for sums of this type.
  
 
===Van der Corput's method.===
 
===Van der Corput's method.===
Of the above approaches, the method of van der Corput is perhaps the most versatile. It is based on two processes, which convert the original sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007043.png" /> into other sums. The A-process uses the inequality
+
Of the above approaches, the method of van der Corput is perhaps the most versatile. It is based on two processes, which convert the original sum $S$ into other sums. The A-process uses the inequality
  
<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/e/e130/e130070/e13007044.png" /></td> </tr></table>
+
\begin{equation*} \left| \sum _ { M &lt; n \leq M + N } e ^ { 2 \pi i f ( n ) } \right| ^ { 2 } \ll \end{equation*}
  
<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/e/e130/e130070/e13007045.png" /></td> </tr></table>
+
\begin{equation*} \ll \frac { N ^ { 2 } } { H } + \frac { N } { H } \sum _ { 1 \leq h \leq H } \left| \sum_ { M &lt; n \leq M + N - h } e ^ { 2 \pi i ( \, f ( n + h ) - f ( n ) ) } \right|, \end{equation*}
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007046.png" /> satisfies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007047.png" />. This has the effect of replacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007048.png" /> by a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007049.png" /> which satisfies (a1) with a smaller value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007050.png" />. To describe the B-process it is assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007051.png" /> is decreasing, and one writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007053.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007054.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007055.png" />. The B-process then derives from the the estimate
+
where $H \in \mathbf{N}$ satisfies $H \leq N$. This has the effect of replacing $f$ by a function $f ( x + h ) - f ( x )$ which satisfies (a1) with a smaller value of $T$. To describe the B-process it is assumed that $f ^ { \prime }$ is decreasing, and one writes $f ^ { \prime } ( M + N ) = A$, $f ^ { \prime } ( N ) = B$ and $f ^ { \prime } ( x _ { m } ) = m$ for $A &lt; m \leq A + B$. The B-process then derives from the estimate
  
<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/e/e130/e130070/e13007056.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { M &lt; n \leq M + N } e ^ { 2 \pi i f ( n ) } = \end{equation*}
  
<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/e/e130/e130070/e13007057.png" /></td> </tr></table>
+
\begin{equation*} = e ^ { - i \pi / 4 } \sum _ { A &lt; m \leq A + B } | f ^ { \prime } ( x _ { m } ) | ^ { - 1 / 2 } e ^ { 2 \pi i ( f ( x _ { m } ) - m x _ { m } ) } + \end{equation*}
  
<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/e/e130/e130070/e13007058.png" /></td> </tr></table>
+
\begin{equation*} + O ( T ^ { 1 / 3 } ) + O ( N ^ { 2 } T ^ { - 1 / 2 } ), \end{equation*}
  
which may be viewed as a form of the [[Poisson summation formula|Poisson summation formula]]. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007059.png" />, the B-process transforms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007060.png" /> into a sum with the same value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007061.png" /> but a shorter range. In applications one uses the A-process repeatedly, with various values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007062.png" />, until one has a sum to which the B-process can be applied effectively. One may then estimate the resulting shorter sum either via a trivial bound or by repeating the argument. In particular, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007063.png" /> iterations of the A-process, followed by the B-process and a trivial estimate lead to van der Corput's <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007065.png" />th derivative estimate: Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007066.png" /> be an integer, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007067.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007068.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007069.png" /> integers. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007070.png" /> on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007071.png" />. Then, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007072.png" />, one has
+
which may be viewed as a form of the [[Poisson summation formula|Poisson summation formula]]. When $T \ll N ^ { 2 }$, the B-process transforms $S$ into a sum with the same value of $T$ but a shorter range. In applications one uses the A-process repeatedly, with various values of $H$, until one has a sum to which the B-process can be applied effectively. One may then estimate the resulting shorter sum either via a trivial bound or by repeating the argument. In particular, $k - 2$ iterations of the A-process, followed by the B-process and a trivial estimate lead to van der Corput's $k$th derivative estimate: Let $k \geq 2$ be an integer, and let $f \in C ^ { k } [ N , N + M ]$ with $M$, $N$ integers. Suppose that $0 &lt; \lambda _ { k } \leq | f ^ { ( k ) } ( x ) | \leq A \lambda _ { k }$ on $[ N , N + M ]$. Then, if $K = 2 ^ { k - 1 }$, one has
  
<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/e/e130/e130070/e13007073.png" /></td> </tr></table>
+
\begin{equation*} \sum _ { M &lt; n \leq M + N } e ^ { 2 \pi i f ( n ) } \ll \end{equation*}
  
<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/e/e130/e130070/e13007074.png" /></td> </tr></table>
+
\begin{equation*} \ll A ^ { 2 / K } N \lambda _ { k } ^ { 1 / ( 2 K - 2 ) } + M ^ { 1 - 2 / K } \lambda _ { k } ^ { - 1 / ( 2 K - 2 ) }, \end{equation*}
  
uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007075.png" />.
+
uniformly in $k$.
  
 
===Exponent pairs.===
 
===Exponent pairs.===
Many bounds of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007076.png" /> subject to (a1), or similar slightly stronger conditions, have been proved. If one has such a bound, one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007077.png" /> is an exponent pair. Thus, the van der Corput third-derivative estimate shows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007078.png" /> is an exponent pair. The case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007079.png" /> is of particular interest, since it leads to a bound for the Riemann zeta-function, of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007080.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007081.png" />. Although van der Corput's method leads to a rich source of exponent pairs, better results can be derived by more complicated methods. Thus, M.N. Huxley [[#References|[a2]]], Chap. 17, shows that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007082.png" /> is an exponent pair whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007083.png" />, using the [[Bombieri–Iwaniec method|Bombieri–Iwaniec method]]. It is conjectured that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007084.png" /> is an exponent pair for any positive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007085.png" />. This can be seen as a generalization of the [[Lindelöf hypothesis|Lindelöf hypothesis]] for the Riemann zeta-function.
+
Many bounds of the form $S \ll ( T / N ) ^ { p } N ^ { q }$ subject to (a1), or similar slightly stronger conditions, have been proved. If one has such a bound, one says that $( p , q )$ is an exponent pair. Thus, the van der Corput third-derivative estimate shows that $( 1 / 6,2 / 3 )$ is an exponent pair. The case $q = p + 1 / 2$ is of particular interest, since it leads to a bound for the Riemann zeta-function, of the form $\zeta ( 1 / 2 + i t ) \ll t ^ { p } \operatorname { log } t$ for $t \geq 2$. Although van der Corput's method leads to a rich source of exponent pairs, better results can be derived by more complicated methods. Thus, M.N. Huxley [[#References|[a2]]], Chap. 17, shows that $( p , p + 1 / 2 )$ is an exponent pair whenever $p &gt; 89 / 570$, using the [[Bombieri–Iwaniec method|Bombieri–Iwaniec method]]. It is conjectured that $( p , p + 1 / 2 )$ is an exponent pair for any positive $p$. This can be seen as a generalization of the [[Lindelöf hypothesis|Lindelöf hypothesis]] for the Riemann zeta-function.
  
 
===The Vinogradov–Korobov method.===
 
===The Vinogradov–Korobov method.===
When (a1) holds with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007086.png" /> larger than about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007087.png" />, the van der Corput method is inferior to that given by Vinogradov and Korobov. This range of values is important in establishing zero-free regions for the Riemann zeta-function, for example. The method reduces the problem to an estimate for the number of solutions of the simultaneous equations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007088.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007089.png" /> with positive integer variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e130/e130070/e13007090.png" />. This is provided by Vinogradov's mean value theorem (cf. also [[Vinogradov method|Vinogradov method]]).
+
When (a1) holds with $T$ larger than about $N ^ { 20 }$, the van der Corput method is inferior to that given by Vinogradov and Korobov. This range of values is important in establishing zero-free regions for the Riemann zeta-function, for example. The method reduces the problem to an estimate for the number of solutions of the simultaneous equations $\sum _ { i = 1 } ^ { k } m _ { i } ^ { h } = \sum _ { i = 1 } ^ { k } n _ { i } ^ { h }$ for $1 \leq h \leq H$ with positive integer variables $m _ { i } , n _ { i } \leq P$. This is provided by Vinogradov's mean value theorem (cf. also [[Vinogradov method|Vinogradov method]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.W. Graham,  G. Kolesnik,  "Van der Corput's method for exponential sums" , ''London Math. Soc. Lecture Notes'' , '''126''' , Cambridge Univ. Press  (1991)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M.N. Huxley,  "Area, lattice points and exponential sums" , ''London Math. Soc. Monographs'' , '''13''' , Clarendon Press  (1996)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Ivić,  "The Riemann zeta-function" , Wiley  (1985)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  W.M. Schmidt,  "Equations over finite fields. An elementary approach" , ''Lecture Notes in Mathematics'' , '''536''' , Springer  (1976)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  R.C. Vaughan,  "The Hardy–Littlewood method" , ''Tracts in Math.'' , '''80''' , Cambridge Univ. Press  (1981)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  N.M. Korobov,  "Exponential sums and their applications" , Kluwer Acad. Publ.  (1992)</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  S.W. Graham,  G. Kolesnik,  "Van der Corput's method for exponential sums" , ''London Math. Soc. Lecture Notes'' , '''126''' , Cambridge Univ. Press  (1991)</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  M.N. Huxley,  "Area, lattice points and exponential sums" , ''London Math. Soc. Monographs'' , '''13''' , Clarendon Press  (1996)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  A. Ivić,  "The Riemann zeta-function" , Wiley  (1985)</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  W.M. Schmidt,  "Equations over finite fields. An elementary approach" , ''Lecture Notes in Mathematics'' , '''536''' , Springer  (1976)</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  R.C. Vaughan,  "The Hardy–Littlewood method" , ''Tracts in Math.'' , '''80''' , Cambridge Univ. Press  (1981)</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  N.M. Korobov,  "Exponential sums and their applications" , Kluwer Acad. Publ.  (1992)</td></tr></table>

Latest revision as of 12:26, 12 December 2020

Exponential sums have the form

\begin{equation*} S = \sum _ { n \in A } e ^ { 2 \pi i f ( n ) }, \end{equation*}

where $A$ is a finite set of integers and $f$ is a real-valued function (cf. also Trigonometric sum). The basic problem is to show, under suitable circumstances, that $S = o ( \# A )$ as $\# A \rightarrow \infty$. Unless there are obvious reasons to the contrary one actually expects $S$ to have order around $( \# A ) ^ { 1 / 2 }$. Exponential sums in more than one variable also occur, and much of what is stated below can be generalized to such sums.

Arithmetic sums.

There are two common types of exponential sum encountered in analytic number theory. In the first type, one starts with polynomials $g ( X ) , h ( X ) \in \mathbf{Z} [ X ]$, a positive integer modulus $q$, and a finite interval $I \subset \mathbf{R}$. One then takes $A$ as the set of integers $n \in I$ for which $\operatorname{GCD} ( h ( n ) , q ) = 1$, and sets $f ( n ) = g ( n ) \overline { h ( n ) } / q$, where $\overline { h ( n ) }$ is any integer for which $h ( n ) \overline { h ( n ) } \equiv 1 ( \operatorname { mod } q )$. When $I = ( 0 , q ]$, such a sum is called complete. When $I \subseteq ( 0 , q ]$ one may estimate the incomplete sum in terms of complete ones via the bound

Complete sums have multiplicative properties which enable one to reduce consideration to the case in which $q$ is a prime number or a power of a prime number. Moreover, Weil's Riemann hypothesis for curves over finite fields (see [a4], for example) shows that, if $q$ is prime, then

\begin{equation*} \left| \sum _ { n \in I \atop ( h ( n ) , q ) = 1 } e ^ { 2 \pi i g ( n ) \overline { h ( n )} / q } \right| \leq ( \operatorname { deg } ( g ) + \operatorname { deg } ( h ) ) \sqrt { q }, \end{equation*}

except when $g ( n ) \overline { h ( n ) }$ is constant modulo $q$. For powers of a prime number the situation is more complicated, but broadly similar. It follows that, for fixed $g$ and $h$ and $q$ prime, the incomplete sum will be $o ( \# A )$ as soon as $\# A / ( \sqrt { q }\operatorname { log } q ) \rightarrow \infty$. It is an important outstanding problem (as of 2000) to improve on this in general.

Analytic sums.

The second type of exponential sum arises when $f$ extends to a suitably smooth function on a real interval $I$. Important examples correspond to $f ( n ) = \alpha n ^ { k }$ for $k \in \mathbf{N}$, or $f ( n ) = ( t / 2 \pi ) \operatorname { log } n$, which occur in the theory of Waring's problem and the Riemann zeta-function, respectively (cf. also Waring problem; Zeta-function). Let $I = ( N , N + M ]$ with positive integers $M \leq N$. One typically imposes the condition that $f \in C ^ { \infty } [ N , N + M ]$ with

\begin{equation} \tag{a1} c _ { k } T N ^ { - k } \leq \left| f ^ { ( k ) } ( x ) \right| \leq c _ { k } ^ { \prime } T N ^ { - k } \end{equation}

\begin{equation*} ( k \in {\bf N} , N \leq x \leq N + M ), \end{equation*}

for suitable constants , $ { c } _ { k } ^ { \prime }$. Methods due to H. Weyl (see [a5], Chap. 2), J. van der Corput (see [a1]), I.M. Vinogradov and N.M. Korobov (see [a3], Chap. 6), and E. Bombieri and H. Iwaniec (see [a2]) have been used for sums of this type.

Van der Corput's method.

Of the above approaches, the method of van der Corput is perhaps the most versatile. It is based on two processes, which convert the original sum $S$ into other sums. The A-process uses the inequality

\begin{equation*} \left| \sum _ { M < n \leq M + N } e ^ { 2 \pi i f ( n ) } \right| ^ { 2 } \ll \end{equation*}

\begin{equation*} \ll \frac { N ^ { 2 } } { H } + \frac { N } { H } \sum _ { 1 \leq h \leq H } \left| \sum_ { M < n \leq M + N - h } e ^ { 2 \pi i ( \, f ( n + h ) - f ( n ) ) } \right|, \end{equation*}

where $H \in \mathbf{N}$ satisfies $H \leq N$. This has the effect of replacing $f$ by a function $f ( x + h ) - f ( x )$ which satisfies (a1) with a smaller value of $T$. To describe the B-process it is assumed that $f ^ { \prime }$ is decreasing, and one writes $f ^ { \prime } ( M + N ) = A$, $f ^ { \prime } ( N ) = B$ and $f ^ { \prime } ( x _ { m } ) = m$ for $A < m \leq A + B$. The B-process then derives from the estimate

\begin{equation*} \sum _ { M < n \leq M + N } e ^ { 2 \pi i f ( n ) } = \end{equation*}

\begin{equation*} = e ^ { - i \pi / 4 } \sum _ { A < m \leq A + B } | f ^ { \prime } ( x _ { m } ) | ^ { - 1 / 2 } e ^ { 2 \pi i ( f ( x _ { m } ) - m x _ { m } ) } + \end{equation*}

\begin{equation*} + O ( T ^ { 1 / 3 } ) + O ( N ^ { 2 } T ^ { - 1 / 2 } ), \end{equation*}

which may be viewed as a form of the Poisson summation formula. When $T \ll N ^ { 2 }$, the B-process transforms $S$ into a sum with the same value of $T$ but a shorter range. In applications one uses the A-process repeatedly, with various values of $H$, until one has a sum to which the B-process can be applied effectively. One may then estimate the resulting shorter sum either via a trivial bound or by repeating the argument. In particular, $k - 2$ iterations of the A-process, followed by the B-process and a trivial estimate lead to van der Corput's $k$th derivative estimate: Let $k \geq 2$ be an integer, and let $f \in C ^ { k } [ N , N + M ]$ with $M$, $N$ integers. Suppose that $0 < \lambda _ { k } \leq | f ^ { ( k ) } ( x ) | \leq A \lambda _ { k }$ on $[ N , N + M ]$. Then, if $K = 2 ^ { k - 1 }$, one has

\begin{equation*} \sum _ { M < n \leq M + N } e ^ { 2 \pi i f ( n ) } \ll \end{equation*}

\begin{equation*} \ll A ^ { 2 / K } N \lambda _ { k } ^ { 1 / ( 2 K - 2 ) } + M ^ { 1 - 2 / K } \lambda _ { k } ^ { - 1 / ( 2 K - 2 ) }, \end{equation*}

uniformly in $k$.

Exponent pairs.

Many bounds of the form $S \ll ( T / N ) ^ { p } N ^ { q }$ subject to (a1), or similar slightly stronger conditions, have been proved. If one has such a bound, one says that $( p , q )$ is an exponent pair. Thus, the van der Corput third-derivative estimate shows that $( 1 / 6,2 / 3 )$ is an exponent pair. The case $q = p + 1 / 2$ is of particular interest, since it leads to a bound for the Riemann zeta-function, of the form $\zeta ( 1 / 2 + i t ) \ll t ^ { p } \operatorname { log } t$ for $t \geq 2$. Although van der Corput's method leads to a rich source of exponent pairs, better results can be derived by more complicated methods. Thus, M.N. Huxley [a2], Chap. 17, shows that $( p , p + 1 / 2 )$ is an exponent pair whenever $p > 89 / 570$, using the Bombieri–Iwaniec method. It is conjectured that $( p , p + 1 / 2 )$ is an exponent pair for any positive $p$. This can be seen as a generalization of the Lindelöf hypothesis for the Riemann zeta-function.

The Vinogradov–Korobov method.

When (a1) holds with $T$ larger than about $N ^ { 20 }$, the van der Corput method is inferior to that given by Vinogradov and Korobov. This range of values is important in establishing zero-free regions for the Riemann zeta-function, for example. The method reduces the problem to an estimate for the number of solutions of the simultaneous equations $\sum _ { i = 1 } ^ { k } m _ { i } ^ { h } = \sum _ { i = 1 } ^ { k } n _ { i } ^ { h }$ for $1 \leq h \leq H$ with positive integer variables $m _ { i } , n _ { i } \leq P$. This is provided by Vinogradov's mean value theorem (cf. also Vinogradov method).

References

[a1] S.W. Graham, G. Kolesnik, "Van der Corput's method for exponential sums" , London Math. Soc. Lecture Notes , 126 , Cambridge Univ. Press (1991)
[a2] M.N. Huxley, "Area, lattice points and exponential sums" , London Math. Soc. Monographs , 13 , Clarendon Press (1996)
[a3] A. Ivić, "The Riemann zeta-function" , Wiley (1985)
[a4] W.M. Schmidt, "Equations over finite fields. An elementary approach" , Lecture Notes in Mathematics , 536 , Springer (1976)
[a5] R.C. Vaughan, "The Hardy–Littlewood method" , Tracts in Math. , 80 , Cambridge Univ. Press (1981)
[a6] N.M. Korobov, "Exponential sums and their applications" , Kluwer Acad. Publ. (1992)
How to Cite This Entry:
Exponential sum estimates. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Exponential_sum_estimates&oldid=17839
This article was adapted from an original article by D.R. Heath-Brown (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article