Namespaces
Variants
Actions

Difference between revisions of "Vaughan identity"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (texed)
 
Line 1: Line 1:
In 1937, I.M. Vinogradov [[#References|[a9]]] proved the odd case of the Goldbach conjecture (cf. also [[Goldbach problem|Goldbach problem]]); i.e., he proved that every sufficiently large odd number can be written as a sum of three prime numbers (cf. also [[Vinogradov method|Vinogradov method]]). The essential new element of his proof was a non-trivial estimate for an exponential sum involving prime numbers (cf. also [[Exponential sum estimates|Exponential sum estimates]]). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300301.png" /> denote <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300302.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300303.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300304.png" /> runs over the prime numbers. By simply observing that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300305.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300306.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300307.png" /> and using the prime number theorem (cf. [[De la Vallée-Poussin theorem|de la Vallée-Poussin theorem]]), one immediately sees that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300308.png" />. Vinogradov was able to improve on this estimate on the  "minor arcs" ; in other words, he obtained a better estimate for those values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v1300309.png" /> that could not be well approximated by a rational number with a small denominator. Vinogradov's estimate used the sieve of Eratosthenes (cf. also [[Eratosthenes, sieve of|Eratosthenes, sieve of]]; [[Sieve method|Sieve method]]) to decompose the sum <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003010.png" /> into subsums of 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/v/v130/v130030/v13003011.png" /></td> </tr></table>
+
In 1937, I.M. Vinogradov [[#References|[a9]]] proved the odd case of the Goldbach conjecture (cf. also [[Goldbach problem|Goldbach problem]]); i.e., he proved that every sufficiently large odd number can be written as a sum of three prime numbers (cf. also [[Vinogradov method|Vinogradov method]]). The essential new element of his proof was a non-trivial estimate for an exponential sum involving prime numbers (cf. also [[Exponential sum estimates|Exponential sum estimates]]). Let $e(\alpha)$ denote $e^{2\pi\alpha}$ and let $S(\alpha, N) = \sum_{p\le N} e(p\alpha)$, where $p$ runs over the prime numbers. By simply observing that $|e(p\alpha)| \le 1$ for all $p$, $\alpha$ and using the prime number theorem (cf. [[De la Vallée-Poussin theorem|de la Vallée-Poussin theorem]]), one immediately sees that $S(\alpha, N) = O(N/\log N)$. Vinogradov was able to improve on this estimate on the  "minor arcs" ; in other words, he obtained a better estimate for those values of $\alpha$ that could not be well approximated by a rational number with a small denominator. Vinogradov's estimate used the sieve of Eratosthenes (cf. also [[Eratosthenes, sieve of|Eratosthenes, sieve of]]; [[Sieve method|Sieve method]]) to decompose the sum $S(\alpha, N)$ into subsums of the form
 +
 
 +
$$
 +
\sum_{n\le u} \alpha(n) \sum_{m \le N/n} e(\alpha m)
 +
$$
  
 
and of the form
 
and of 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/v/v130/v130030/v13003012.png" /></td> </tr></table>
+
$$
 +
\sum_{m\le u}
 +
\sum_{n\le v}
 +
\sum_{r\le N/mn}
 +
a(m) b(n) e(rmn \alpha).
 +
$$
  
 
The sums have become known as sums of type I and type II, respectively.
 
The sums have become known as sums of type I and type II, respectively.
  
Vinogradov's method is quite powerful and can be adapted to general sums of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003013.png" />. However, the technical details of his method are formidable and, consequently, the method was neither widely used nor widely understood. In 1977, R.C. Vaughan [[#References|[a6]]] found a much simpler approach to sums over prime numbers.
+
Vinogradov's method is quite powerful and can be adapted to general sums of the form $\sum_{p\le N} f(p)$. However, the technical details of his method are formidable and, consequently, the method was neither widely used nor widely understood. In 1977, R.C. Vaughan [[#References|[a6]]] found a much simpler approach to sums over prime numbers.
  
 
Vaughan's identity is most easily understood in the context of [[Dirichlet series|Dirichlet series]]. Suppose that
 
Vaughan's identity is most easily understood in the context of [[Dirichlet series|Dirichlet series]]. Suppose that
  
<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/v130/v130030/v13003014.png" /></td> </tr></table>
+
$$
 +
F(s) = \sum_{n=1}^\infty f(n) n^{-s}
 +
\quad \text{and} \quad
 +
G(s) = \sum_{n=1}^\infty g(n) n^{-s}
 +
$$
  
are both absolutely convergent in the half-plane <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003015.png" />. Then
+
are both absolutely convergent in the half-plane $\Re s > a$. 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/v130/v130030/v13003016.png" /></td> </tr></table>
+
$$
 +
F(s) G(s) = \sum_{n=1}^\infty \left(
 +
\sum_{de = n} f(d) g(e)
 +
\right) n^{-s}
 +
$$
  
in this same half-plane. One of the simplest and most useful Dirichlet series is the Riemann zeta-function (cf. also [[Zeta-function|Zeta-function]]), which is defined as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003017.png" /> for complex numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003018.png" /> with real part exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003019.png" />. The Euler product formula states that
+
in this same half-plane. One of the simplest and most useful Dirichlet series is the Riemann zeta-function (cf. also [[Zeta-function|Zeta-function]]), which is defined as $\zeta(s) = \sum_{n=1}^\infty n^{-s}$ for complex numbers $s$ with real part exceeding $1$. The Euler product formula states that
  
<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/v130/v130030/v13003020.png" /></td> </tr></table>
+
$$
 +
\zeta(s) = \prod_p (1-p^{-s})^{-1},
 +
$$
  
where the product is over all prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003021.png" />. Taking the reciprocal of the Euler product, one sees that
+
where the product is over all prime numbers $p$. Taking the reciprocal of the Euler product, one sees that
  
<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/v130/v130030/v13003022.png" /></td> </tr></table>
+
$$
 +
\frac{1}{\zeta(s)} = \sum_{n=1}^\infty \mu(n) n^{-s},
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003023.png" /> is the Möbius function defined by
+
where $\mu(n)$ is the Möbius function defined by
  
<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/v130/v130030/v13003024.png" /></td> </tr></table>
+
$$
 +
\mu(n) = \begin{cases}
 +
(-1)^k & \text{if $n = p_1\dots p_k$ for distinct prime numbers $p_1, \ldots, p_k$}, \\
 +
0 & \text{if $n$ is divisible by the square of some prime number}.
 +
\end{cases}
 +
$$
  
By looking at the coefficients of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003025.png" />, one obtains the useful identity
+
By looking at the coefficients of $\zeta(s) . \zeta(s)^{-1}$, one obtains the useful identity
  
<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/v130/v130030/v13003026.png" /></td> </tr></table>
+
$$
 +
\sum_{d|n} \mu(n) = \begin{cases}
 +
1 & \text{if $n=1$}, \\
 +
0 & \text{otherwise}.
 +
\end{cases}
 +
$$
  
 
By taking the logarithmic derivative of the Euler product formula, one sees that
 
By taking the logarithmic derivative of the Euler product formula, one sees that
  
<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/v130/v130030/v13003027.png" /></td> </tr></table>
+
$$
 +
- \frac{\zeta'}{\zeta}(s) = \sum_{n=1}^\infty \Lambda(n) n^{-s},
 +
$$
  
where the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003028.png" /> are defined as
+
where the coefficients $\Lambda(n)$ are defined as
  
<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/v130/v130030/v13003029.png" /></td> </tr></table>
+
$$
 +
\Lambda(n) = \begin{cases}
 +
\log p & \text{if $n=p^a$ for some prime number $p$}, \\
 +
0 & \text{otherwise}.
 +
\end{cases}
 +
$$
  
 
This is the [[Mangoldt function|Mangoldt function]]. By computing the product
 
This is the [[Mangoldt function|Mangoldt function]]. By computing the product
  
<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/v130/v130030/v13003030.png" /></td> </tr></table>
+
$$
 +
\zeta(s) . \frac{-\zeta'}{\zeta}(s)
 +
$$
  
 
in two different ways, one sees that
 
in two different ways, one sees that
  
<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/v130/v130030/v13003031.png" /></td> </tr></table>
+
$$
 +
\sum_{d|n} \Lambda(d) = \log n.
 +
$$
  
For technical reasons, it is often simpler to work with sums of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003032.png" /> than with sums of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003033.png" />, and estimates for the latter sum can usually be easily derived from estimates for the former.
+
For technical reasons, it is often simpler to work with sums of the form $\sum_{n\le N}\Lambda(n) f(n)$ than with sums of the form $\sum_{p\le N} f(p)$, and estimates for the latter sum can usually be easily derived from estimates for the former.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003035.png" /> be arbitrary real numbers, both exceeding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003036.png" />, and define
+
Let $u,v$ be arbitrary real numbers, both exceeding $1$, and define
  
<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/v130/v130030/v13003037.png" /></td> </tr></table>
+
$$
 +
M(s) = \sum_{d\le u} \mu(d) d^{-s}, \quad F(s) = \sum_{e \le v} \Lambda(e) e^{-s}.
 +
$$
  
Thus, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003039.png" /> are partial sums of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003041.png" /> respectively. In particular,
+
Thus, $M$ and $F$ are partial sums of $1/\zeta$ and $-\zeta'/\zeta$ respectively. In particular,
  
<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/v130/v130030/v13003042.png" /></td> </tr></table>
+
$$
 
+
\zeta(s) M(s) = \sum_{n=1} \left( \sum_{\substack{d|n \\ d\le u}} \mu(d)\right) n^{-s}
<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/v130/v130030/v13003043.png" /></td> </tr></table>
+
= 1 + \sum_{n > u} \left( \sum_{\substack{d|n \\ d\le u}} \mu(d) \right) n^{-s}.
 +
$$
  
 
Now consider the Dirichlet series identity
 
Now consider the Dirichlet series identity
  
<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/v130/v130030/v13003044.png" /></td> </tr></table>
+
$$
 +
\frac{\zeta'}{\zeta} + F
 +
= \zeta' M + FM\zeta + \left( \frac{\zeta'}{\zeta} + F \right)(1-\zeta M).
 +
$$
  
Comparing coefficients of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003045.png" /> on both sides of the equation, one sees that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003046.png" />, then
+
Comparing coefficients of $n^{-s}$ on both sides of the equation, one sees that if $n > v$, 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/v130/v130030/v13003047.png" /></td> </tr></table>
+
$$
 +
\Lambda(n) =  
 +
\sum_{\substack{dr = n \\ d \le u}} \mu(d) \log r -
 +
\sum_{\substack{kr = n \\ k \le uv}} a(k) -
 +
\sum_{\substack{ek = n \\ e > v \\ k > u}} \Lambda(e) b(k),
 +
$$
  
 
where
 
where
  
<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/v130/v130030/v13003048.png" /></td> </tr></table>
+
$$
 +
a(k) = \sum_{\substack{d \le u \\ e \le v \\ de = k}} \Lambda(d) \mu(e)
 +
\quad \text{and} \quad
 +
b(k) = \sum_{\substack{d | k \\ d \le u}} \mu(d)
 +
$$
  
If one multiplies this equation by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003049.png" /> and sums over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003050.png" />, one obtains the Vaughan identity:
 
  
<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/v130/v130030/v13003051.png" /></td> </tr></table>
+
If one multiplies this equation by $f(n)$ and sums over $v < n \le N$, one obtains the Vaughan identity:
  
<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/v130/v130030/v13003052.png" /></td> </tr></table>
+
$$
 +
\begin{aligned}
 +
\sum_{v < n \le N} \Lambda(n) f(n)
 +
&= \sum_{d \le u} \mu(d) \sum_{v/d \le r \le N/d} (\log r) f(rd)
 +
- \sum_{k \le uv} a(k) \sum_{v/k \le r \le N/k} f(rk) \\
 +
&\quad - \sum_{v < e \le N/u} \sum_{u < k \le N/e} \Lambda(e) b(k) f(dk).
 +
\end{aligned}
 +
$$
  
<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/v130/v130030/v13003053.png" /></td> </tr></table>
+
In general, the first and second sums can be treated as type-I sums, and the third sum can be treated as a type-II sum. The logarithm factor in the first sum is easily finessed with partial summation. In some applications, it is useful to divide the second sum into subsums with $k \le K$ and $K \le k \le uv$, where the first subsum is treated as type-I and the second subsum as type-II.
 
 
<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/v130/v130030/v13003054.png" /></td> </tr></table>
 
 
 
In general, the first and second sums can be treated as type-I sums, and the third sum can be treated as a type-II sum. The logarithm factor in the first sum is easily finessed with partial summation. In some applications, it is useful to divide the second sum into subsums with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003055.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003056.png" />, where the first subsum is treated as type-I and the second subsum as type-II.
 
  
 
For a brief and very accessible account of how Vaughan's identity is applied, see Vaughan's original article [[#References|[a6]]]. There, he proves that
 
For a brief and very accessible account of how Vaughan's identity is applied, see Vaughan's original article [[#References|[a6]]]. There, he proves that
  
<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/v130/v130030/v13003057.png" /></td> </tr></table>
+
$$
 
+
\sum_{n \le N} \Lambda(n) e(\alpha n) = O\left( (N q^{-1/2} + N^{4/5} + N^{1/2} q^{1/2}) \log^4 N\right)
<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/v130/v130030/v13003058.png" /></td> </tr></table>
+
$$
  
whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003059.png" />. Another self-contained account of this can be found in [[#References|[a1]]].
+
whenever $|\alpha - a/q| \le 1/q^2$. Another self-contained account of this can be found in [[#References|[a1]]].
  
There are many applications of Vaughan's identity in the literature. Vaughan [[#References|[a7]]] used it to obtain new estimates on the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003060.png" />, and he also used it to give an elegant proof of the Bombieri–Vinogradov theorem on prime numbers in arithmetic progressions [[#References|[a8]]]. H.L. Montgomery and Vaughan [[#References|[a5]]] obtained a new estimate for the error term in the formula for the number of square-free integers up to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003061.png" />, conditional on the Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]). This requires a slightly different form of Vaughan's identity. In this case, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003062.png" /> be as before, but take
+
There are many applications of Vaughan's identity in the literature. Vaughan [[#References|[a7]]] used it to obtain new estimates on the distribution of $\alpha p \pmod{1}$, and he also used it to give an elegant proof of the Bombieri–Vinogradov theorem on prime numbers in arithmetic progressions [[#References|[a8]]]. H.L. Montgomery and Vaughan [[#References|[a5]]] obtained a new estimate for the error term in the formula for the number of square-free integers up to $x$, conditional on the Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]). This requires a slightly different form of Vaughan's identity. In this case, let $M(s)$ be as before, but take
  
<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/v130/v130030/v13003063.png" /></td> </tr></table>
+
$$
 +
F(s) = \sum_{n\le v} \mu(n) n^{-s}.
 +
$$
  
 
From the equation
 
From the 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/v/v130/v130030/v13003064.png" /></td> </tr></table>
+
$$
 +
\left( \frac{1}{\zeta} + M \right) (1-\zeta M) = \frac{1}{\zeta} + F - M - FM\zeta
 +
$$
  
one can obtain an identity for sums of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003065.png" />. D.R. Heath-Brown and S.J. Patterson [[#References|[a3]]] used Vaughan's identity to prove a long-standing conjecture of E. Kummer about distribution of cubic Gauss sums (cf. also [[Kummer hypothesis|Kummer hypothesis]]; [[Gauss sum|Gauss sum]]). Heath-Brown [[#References|[a2]]] developed a more general and more flexible version of Vaughan's identity, and G. Harman [[#References|[a4]]] has developed an alternative treatment that returns to Vinogradov's original idea of using the sieve of Eratosthenes (cf. also [[Eratosthenes, sieve of|Eratosthenes, sieve of]]).
+
one can obtain an identity for sums of the form $\sum_{n\le N} \mu(n) f(n)$. D.R. Heath-Brown and S.J. Patterson [[#References|[a3]]] used Vaughan's identity to prove a long-standing conjecture of E. Kummer about distribution of cubic Gauss sums (cf. also [[Kummer hypothesis|Kummer hypothesis]]; [[Gauss sum|Gauss sum]]). Heath-Brown [[#References|[a2]]] developed a more general and more flexible version of Vaughan's identity, and G. Harman [[#References|[a4]]] has developed an alternative treatment that returns to Vinogradov's original idea of using the sieve of Eratosthenes (cf. also [[Eratosthenes, sieve of|Eratosthenes, sieve of]]).
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)  (Edition: Second)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Heath-Brown,  "Prime numbers in short intervals and a generalized Vaughan identity"  ''Canad. J. Math.'' , '''34'''  (1982)  pp. 1365–1377</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  D.R. Heath-Brown,  S.J. Patterson,  "The distribution of Kummer sums at prime arguments"  ''J. Reine Angew. Math.'' , '''310'''  (1979)  pp. 110–130</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  G. Harman,  "Eratosthenes, Legendre, Vinogradov, and beyond"  G.R.H. Greaves (ed.)  G. Harman (ed.)  M.N. Huxley (ed.) , ''Sieve Methods, Exponential Sums, and their Applications in Number Theory'' , ''London Math. Soc. Lecture Notes'' , '''237''' , Cambridge Univ. Press  (1996)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H.L. Montgomery,  R.C. Vaughan,  "On the distribution of square-free numbers"  H. Halberstam (ed.)  C. Hooley (ed.) , ''Recent Progress in Analytic Number Theory'' , '''1'''  (1981)  pp. 247–256</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  R.C. Vaughan,  "Sommes trigonométriques sur les nombres premiers"  ''C.R. Acad. Sci. Paris Sér. A'' , '''285'''  (1977)  pp. 981–983</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  R.C. Vaughan,  "On the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/v/v130/v130030/v13003066.png" /> modulo one"  ''Mathematika'' , '''24'''  (1977)  pp. 135–141</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  R.C. Vaughan,  "An elementary method in prime number theory"  ''Acta Arith.'' , '''37'''  (1980)  pp. 111–115</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  I.M. Vinogradov,  "A new estimation of a certain sum containing primes"  ''Mat. Sb.'' , '''44'''  (1937)  pp. 783–791  (In Russian)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Wiley/Interscience  (1954)  (In Russian)</TD></TR></table>
+
<table>
 +
  <TR><TD valign="top">[a1]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)  (Edition: Second)</TD></TR>
 +
  <TR><TD valign="top">[a2]</TD> <TD valign="top">  D.R. Heath-Brown,  "Prime numbers in short intervals and a generalized Vaughan identity"  ''Canad. J. Math.'' , '''34'''  (1982)  pp. 1365–1377</TD></TR>
 +
  <TR><TD valign="top">[a3]</TD> <TD valign="top">  D.R. Heath-Brown,  S.J. Patterson,  "The distribution of Kummer sums at prime arguments"  ''J. Reine Angew. Math.'' , '''310'''  (1979)  pp. 110–130</TD></TR>
 +
  <TR><TD valign="top">[a4]</TD> <TD valign="top">  G. Harman,  "Eratosthenes, Legendre, Vinogradov, and beyond"  G.R.H. Greaves (ed.)  G. Harman (ed.)  M.N. Huxley (ed.) , ''Sieve Methods, Exponential Sums, and their Applications in Number Theory'' , ''London Math. Soc. Lecture Notes'' , '''237''' , Cambridge Univ. Press  (1996)</TD></TR>
 +
  <TR><TD valign="top">[a5]</TD> <TD valign="top">  H.L. Montgomery,  R.C. Vaughan,  "On the distribution of square-free numbers"  H. Halberstam (ed.)  C. Hooley (ed.) , ''Recent Progress in Analytic Number Theory'' , '''1'''  (1981)  pp. 247–256</TD></TR>
 +
  <TR><TD valign="top">[a6]</TD> <TD valign="top">  R.C. Vaughan,  "Sommes trigonométriques sur les nombres premiers"  ''C.R. Acad. Sci. Paris Sér. A'' , '''285'''  (1977)  pp. 981–983</TD></TR>
 +
  <TR><TD valign="top">[a7]</TD> <TD valign="top">  R.C. Vaughan,  "On the distribution of $\alpha p$ modulo one"  ''Mathematika'' , '''24'''  (1977)  pp. 135–141</TD></TR>
 +
  <TR><TD valign="top">[a8]</TD> <TD valign="top">  R.C. Vaughan,  "An elementary method in prime number theory"  ''Acta Arith.'' , '''37'''  (1980)  pp. 111–115</TD></TR>
 +
  <TR><TD valign="top">[a9]</TD> <TD valign="top">  I.M. Vinogradov,  "A new estimation of a certain sum containing primes"  ''Mat. Sb.'' , '''44'''  (1937)  pp. 783–791  (In Russian)</TD></TR>
 +
  <TR><TD valign="top">[a10]</TD> <TD valign="top">  I.M. Vinogradov,  "The method of trigonometric sums in the theory of numbers" , Wiley/Interscience  (1954)  (In Russian)</TD></TR>
 +
</table>

Latest revision as of 12:01, 13 February 2024

In 1937, I.M. Vinogradov [a9] proved the odd case of the Goldbach conjecture (cf. also Goldbach problem); i.e., he proved that every sufficiently large odd number can be written as a sum of three prime numbers (cf. also Vinogradov method). The essential new element of his proof was a non-trivial estimate for an exponential sum involving prime numbers (cf. also Exponential sum estimates). Let $e(\alpha)$ denote $e^{2\pi\alpha}$ and let $S(\alpha, N) = \sum_{p\le N} e(p\alpha)$, where $p$ runs over the prime numbers. By simply observing that $|e(p\alpha)| \le 1$ for all $p$, $\alpha$ and using the prime number theorem (cf. de la Vallée-Poussin theorem), one immediately sees that $S(\alpha, N) = O(N/\log N)$. Vinogradov was able to improve on this estimate on the "minor arcs" ; in other words, he obtained a better estimate for those values of $\alpha$ that could not be well approximated by a rational number with a small denominator. Vinogradov's estimate used the sieve of Eratosthenes (cf. also Eratosthenes, sieve of; Sieve method) to decompose the sum $S(\alpha, N)$ into subsums of the form

$$ \sum_{n\le u} \alpha(n) \sum_{m \le N/n} e(\alpha m) $$

and of the form

$$ \sum_{m\le u} \sum_{n\le v} \sum_{r\le N/mn} a(m) b(n) e(rmn \alpha). $$

The sums have become known as sums of type I and type II, respectively.

Vinogradov's method is quite powerful and can be adapted to general sums of the form $\sum_{p\le N} f(p)$. However, the technical details of his method are formidable and, consequently, the method was neither widely used nor widely understood. In 1977, R.C. Vaughan [a6] found a much simpler approach to sums over prime numbers.

Vaughan's identity is most easily understood in the context of Dirichlet series. Suppose that

$$ F(s) = \sum_{n=1}^\infty f(n) n^{-s} \quad \text{and} \quad G(s) = \sum_{n=1}^\infty g(n) n^{-s} $$

are both absolutely convergent in the half-plane $\Re s > a$. Then

$$ F(s) G(s) = \sum_{n=1}^\infty \left( \sum_{de = n} f(d) g(e) \right) n^{-s} $$

in this same half-plane. One of the simplest and most useful Dirichlet series is the Riemann zeta-function (cf. also Zeta-function), which is defined as $\zeta(s) = \sum_{n=1}^\infty n^{-s}$ for complex numbers $s$ with real part exceeding $1$. The Euler product formula states that

$$ \zeta(s) = \prod_p (1-p^{-s})^{-1}, $$

where the product is over all prime numbers $p$. Taking the reciprocal of the Euler product, one sees that

$$ \frac{1}{\zeta(s)} = \sum_{n=1}^\infty \mu(n) n^{-s}, $$

where $\mu(n)$ is the Möbius function defined by

$$ \mu(n) = \begin{cases} (-1)^k & \text{if $n = p_1\dots p_k$ for distinct prime numbers $p_1, \ldots, p_k$}, \\ 0 & \text{if $n$ is divisible by the square of some prime number}. \end{cases} $$

By looking at the coefficients of $\zeta(s) . \zeta(s)^{-1}$, one obtains the useful identity

$$ \sum_{d|n} \mu(n) = \begin{cases} 1 & \text{if $n=1$}, \\ 0 & \text{otherwise}. \end{cases} $$

By taking the logarithmic derivative of the Euler product formula, one sees that

$$ - \frac{\zeta'}{\zeta}(s) = \sum_{n=1}^\infty \Lambda(n) n^{-s}, $$

where the coefficients $\Lambda(n)$ are defined as

$$ \Lambda(n) = \begin{cases} \log p & \text{if $n=p^a$ for some prime number $p$}, \\ 0 & \text{otherwise}. \end{cases} $$

This is the Mangoldt function. By computing the product

$$ \zeta(s) . \frac{-\zeta'}{\zeta}(s) $$

in two different ways, one sees that

$$ \sum_{d|n} \Lambda(d) = \log n. $$

For technical reasons, it is often simpler to work with sums of the form $\sum_{n\le N}\Lambda(n) f(n)$ than with sums of the form $\sum_{p\le N} f(p)$, and estimates for the latter sum can usually be easily derived from estimates for the former.

Let $u,v$ be arbitrary real numbers, both exceeding $1$, and define

$$ M(s) = \sum_{d\le u} \mu(d) d^{-s}, \quad F(s) = \sum_{e \le v} \Lambda(e) e^{-s}. $$

Thus, $M$ and $F$ are partial sums of $1/\zeta$ and $-\zeta'/\zeta$ respectively. In particular,

$$ \zeta(s) M(s) = \sum_{n=1} \left( \sum_{\substack{d|n \\ d\le u}} \mu(d)\right) n^{-s} = 1 + \sum_{n > u} \left( \sum_{\substack{d|n \\ d\le u}} \mu(d) \right) n^{-s}. $$

Now consider the Dirichlet series identity

$$ \frac{\zeta'}{\zeta} + F = \zeta' M + FM\zeta + \left( \frac{\zeta'}{\zeta} + F \right)(1-\zeta M). $$

Comparing coefficients of $n^{-s}$ on both sides of the equation, one sees that if $n > v$, then

$$ \Lambda(n) = \sum_{\substack{dr = n \\ d \le u}} \mu(d) \log r - \sum_{\substack{kr = n \\ k \le uv}} a(k) - \sum_{\substack{ek = n \\ e > v \\ k > u}} \Lambda(e) b(k), $$

where

$$ a(k) = \sum_{\substack{d \le u \\ e \le v \\ de = k}} \Lambda(d) \mu(e) \quad \text{and} \quad b(k) = \sum_{\substack{d | k \\ d \le u}} \mu(d) $$


If one multiplies this equation by $f(n)$ and sums over $v < n \le N$, one obtains the Vaughan identity:

$$ \begin{aligned} \sum_{v < n \le N} \Lambda(n) f(n) &= \sum_{d \le u} \mu(d) \sum_{v/d \le r \le N/d} (\log r) f(rd) - \sum_{k \le uv} a(k) \sum_{v/k \le r \le N/k} f(rk) \\ &\quad - \sum_{v < e \le N/u} \sum_{u < k \le N/e} \Lambda(e) b(k) f(dk). \end{aligned} $$

In general, the first and second sums can be treated as type-I sums, and the third sum can be treated as a type-II sum. The logarithm factor in the first sum is easily finessed with partial summation. In some applications, it is useful to divide the second sum into subsums with $k \le K$ and $K \le k \le uv$, where the first subsum is treated as type-I and the second subsum as type-II.

For a brief and very accessible account of how Vaughan's identity is applied, see Vaughan's original article [a6]. There, he proves that

$$ \sum_{n \le N} \Lambda(n) e(\alpha n) = O\left( (N q^{-1/2} + N^{4/5} + N^{1/2} q^{1/2}) \log^4 N\right) $$

whenever $|\alpha - a/q| \le 1/q^2$. Another self-contained account of this can be found in [a1].

There are many applications of Vaughan's identity in the literature. Vaughan [a7] used it to obtain new estimates on the distribution of $\alpha p \pmod{1}$, and he also used it to give an elegant proof of the Bombieri–Vinogradov theorem on prime numbers in arithmetic progressions [a8]. H.L. Montgomery and Vaughan [a5] obtained a new estimate for the error term in the formula for the number of square-free integers up to $x$, conditional on the Riemann hypothesis (cf. Riemann hypotheses). This requires a slightly different form of Vaughan's identity. In this case, let $M(s)$ be as before, but take

$$ F(s) = \sum_{n\le v} \mu(n) n^{-s}. $$

From the equation

$$ \left( \frac{1}{\zeta} + M \right) (1-\zeta M) = \frac{1}{\zeta} + F - M - FM\zeta $$

one can obtain an identity for sums of the form $\sum_{n\le N} \mu(n) f(n)$. D.R. Heath-Brown and S.J. Patterson [a3] used Vaughan's identity to prove a long-standing conjecture of E. Kummer about distribution of cubic Gauss sums (cf. also Kummer hypothesis; Gauss sum). Heath-Brown [a2] developed a more general and more flexible version of Vaughan's identity, and G. Harman [a4] has developed an alternative treatment that returns to Vinogradov's original idea of using the sieve of Eratosthenes (cf. also Eratosthenes, sieve of).

References

[a1] H. Davenport, "Multiplicative number theory" , Springer (1980) (Edition: Second)
[a2] D.R. Heath-Brown, "Prime numbers in short intervals and a generalized Vaughan identity" Canad. J. Math. , 34 (1982) pp. 1365–1377
[a3] D.R. Heath-Brown, S.J. Patterson, "The distribution of Kummer sums at prime arguments" J. Reine Angew. Math. , 310 (1979) pp. 110–130
[a4] G. Harman, "Eratosthenes, Legendre, Vinogradov, and beyond" G.R.H. Greaves (ed.) G. Harman (ed.) M.N. Huxley (ed.) , Sieve Methods, Exponential Sums, and their Applications in Number Theory , London Math. Soc. Lecture Notes , 237 , Cambridge Univ. Press (1996)
[a5] H.L. Montgomery, R.C. Vaughan, "On the distribution of square-free numbers" H. Halberstam (ed.) C. Hooley (ed.) , Recent Progress in Analytic Number Theory , 1 (1981) pp. 247–256
[a6] R.C. Vaughan, "Sommes trigonométriques sur les nombres premiers" C.R. Acad. Sci. Paris Sér. A , 285 (1977) pp. 981–983
[a7] R.C. Vaughan, "On the distribution of $\alpha p$ modulo one" Mathematika , 24 (1977) pp. 135–141
[a8] R.C. Vaughan, "An elementary method in prime number theory" Acta Arith. , 37 (1980) pp. 111–115
[a9] I.M. Vinogradov, "A new estimation of a certain sum containing primes" Mat. Sb. , 44 (1937) pp. 783–791 (In Russian)
[a10] I.M. Vinogradov, "The method of trigonometric sums in the theory of numbers" , Wiley/Interscience (1954) (In Russian)
How to Cite This Entry:
Vaughan identity. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Vaughan_identity&oldid=17846
This article was adapted from an original article by S.W. Graham (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article