Vaughan identity

From Encyclopedia of Mathematics
Jump to: navigation, search

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), $$


$$ 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).


[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:
This article was adapted from an original article by S.W. Graham (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article