Formalpedia

Let $k\ge2$ and $\varepsilon>0$. There is a constant $C=C(k,\varepsilon)>0$ such that for every modulus $q\ge1$ and every integer $a$ with $(a,q)=1$,

(...)

This is the classical bound for complete exponential sums, Theorem 4.2 of Vaughan's The Hardy-Littlewood Method. It is sharper than the exponent $1-2^{1-k}+\varepsilon$ obtainable by applying Weyl's inequality at $N=q$: the two agree at $k=2$, and for every $k\ge3$ one has $1-\tfrac1k<1-2^{1-k}$, a saving that grows with $k$.

Structure of the proof. By the Chinese remainder theorem $q\mapsto S(q,a)$ is multiplicative in a twisted sense, $S(q_{1}q_{2},a)=S(q_{1},aq_{2}^{k-1})S(q_{2},aq_{1}^{k-1})$ for $(q_1,q_2)=1$, so everything reduces to prime powers, where $|S(p^{h},a)|\le k^{3}(p^{h})^{1-1/k}$. Multiplying these local estimates over the prime factorization gives

(...)

and the accumulated constant is absorbed by the divisor bound: choosing $J$ with $k^{3}\le2^{J}$ one has $(k^{3})^{\omega(q)}\le d(q)^{J}\ll_{\varepsilon}q^{\varepsilon}$. The $\varepsilon$ in the statement is exactly the price of this last step; the exponent $1-1/k$ itself is attained without loss.

Why it matters. In Waring's problem the local factors $A(q,n)$ are built from $S(q,a)$, and the absolute convergence of the singular series depends on how fast $|S(q,a)|$ decays below the trivial $q$. The exponent $1-1/k$ is what makes the singular series converge for $s>2k$ rather than only for $s$ exponentially large in $k$.

Let $k\ge2$, let $p$ be a prime, let $h\ge1$, and let $a$ be an integer with $p\nmid a$. Then

(...)

This is the local half of Vaughan's Theorem 4.2: the estimate $|S(q,a)|\ll q^{1-1/k+\varepsilon}$ restricted to prime-power moduli, with an explicit constant depending only on $k$.

The proof is an induction on $h$ in which three regimes appear. For $h=1$ one needs genuine cancellation, supplied by the Gauss-sum bound $|S(p,a)|\le(k-1)\sqrt p$ together with $\tfrac12\le1-\tfrac1k$. For $h$ below $2(v_{p}(k)+1)$ the trivial bound $|S|\le p^{h}$ already suffices, because $p^{v_p(k)}\mid k$ forces $p$ and $h$ to be bounded in terms of $k$ alone — this is where the constant $k^{3}$ comes from. Above that threshold the recursion $S(p^{h},a)=p^{k-1}S(p^{h-k},a)$ applies, and it is exponent-neutral: $p^{k-1}\cdot p^{(h-k)(1-1/k)}=p^{h(1-1/k)}$, so the induction closes with the same constant. When $h\le k$ the recursion instead terminates at the exact value $p^{h-1}$, which already satisfies the bound.

Combined with multiplicativity of $q\mapsto S(q,a)$ and the divisor bound, this yields the global estimate for arbitrary moduli.

Let $p$ be a prime, $k\ge1$, and $a$ an integer with $p\nmid a$. Then the complete exponential sum over a prime modulus satisfies the square-root cancellation bound

(...)

Context. Write $d=\gcd(k,p-1)$. The $k$-th powers modulo $p$ coincide with the $d$-th powers, and for $y\not\equiv0$ the number of solutions of $x^{k}\equiv y$ is $\sum_{\chi^{d}=\chi_{0}}\chi(y)$, the sum running over the $d$ multiplicative characters of order dividing $d$. Substituting and separating the principal character (whose contribution cancels the $m\equiv0$ term) expresses $S(p,a)$ as a sum of $d-1$ Gauss sums,

(...)

each of modulus exactly $\sqrt{p}$. Since $d\le k$, the bound follows.

Role. This is the one place in the proof of Vaughan's Theorem 4.2 where the trivial bound is not enough: for $h=1$ the estimate $|S(p^{h},a)|\le p^{h}$ gives $p^{1/k}$ too much, and no elementary substitution recovers it. Every higher prime power reduces to this case by the recursion $S(p^{h},a)=p^{k-1}S(p^{h-k},a)$. Note that $\tfrac12\le 1-\tfrac1k$ for $k\ge2$, so square-root cancellation is comfortably stronger than the $p^{1-1/k}$ ultimately needed.

Degenerate cases. When $\gcd(k,p-1)=1$ the map $x\mapsto x^{k}$ permutes the residues, so $S(p,a)=0$; the stated bound is then an equality only if $k=1$. The right-hand side is $\ge0$ because $k\ge1$.

Let $p$ be a prime and $a$ an integer with $p\nmid a$. In the range $h\le k$ the complete exponential sum at the prime power $p^{h}$ takes the exact value

(...)

under the same range hypothesis as the recursion: there is a $j\ge1$ with $p^{j}\nmid k$ and $2j\le h$.

The reason is that the part of the sum over $m$ coprime to $p$ vanishes identically, while on the remaining terms $m=pm'$ the phase $a(pm')^{k}/p^{h}=a\,p^{\,k-h}m'^{k}$ is an integer, so each of the $p^{h-1}$ surviving terms contributes $1$.

This terminates the descent $h\mapsto h-k$ in the prime-power analysis of $S(q,a)$. The value is consistent with the target estimate $|S(p^{h},a)|\le p^{h(1-1/k)}$, since $h-1\le h-h/k$ exactly when $h\le k$.

Let $p$ be a prime, $k\ge1$, and $a$ an integer with $p\nmid a$. For the complete exponential sum

(...)

the value at a prime power reduces to a smaller one:

(...)

The hypothesis controlling the range is the existence of $j\ge1$ with $p^{j}\nmid k$ and $2j\le h$; for $p\nmid k$ one may take $j=1$, so the recursion holds for all $h\ge\max(2,k)$.

The identity comes from splitting the sum by whether $p\mid m$. The part over $m$ coprime to $p$ vanishes, and the part over $m=pm'$ reindexes to $p^{k-1}S(p^{h-k},a)$.

Iterating this descent is what produces the classical bound $|S(q,a)|\ll q^{1-1/k+\varepsilon}$: the exponents match exactly, since $p^{k-1}\cdot p^{(h-k)(1-1/k)}=p^{h(1-1/k)}$, so no saving is lost at any step.

Fix $k\ge1$, a modulus $p\ge1$ and an integer $a$, and split the complete exponential sum

(...)

according to whether $p\mid m$. In the range $1\le h\le k$ the part over $m$ divisible by $p$ degenerates completely:

(...)

Indeed, writing $m=pm'$ gives $a(pm')^{k}/p^{h}=a\,p^{\,k-h}m'^{k}$, which is an integer because $h\le k$; every character value is therefore $1$, and there are exactly $p^{h-1}$ multiples of $p$ below $p^{h}$.

This is the base case of the prime-power recursion for $S(q,a)$: it terminates the descent $h\mapsto h-k$ once the exponent drops to at most $k$. The value $p^{h-1}$ is consistent with the target bound $|S(p^{h},a)|\le p^{h(1-1/k)}$, since $h-1\le h-h/k$ precisely when $h\le k$.

Formalization note. As with the recursion step, no coprimality between $a$ and $p$ is needed — the identity is an exact evaluation, not an estimate.

A finite field has a nonzero number of elements, stated for a field in an arbitrary universe. Submitted as an infrastructure probe while diagnosing a verifier issue; will be retired.

A finite field has a nonzero number of elements. Submitted as an infrastructure probe while diagnosing a verifier issue; will be retired.

Fix $k\ge1$, a modulus $p\ge1$ and an integer $a$, and consider the complete exponential sum

(...)

Split $S(p^{h},a)$ according to whether $p\mid m$. This result evaluates the part over $m$ divisible by $p$, in the range $h\ge k$:

(...)

Writing $m=pm'$ with $m'<p^{h-1}$ turns the phase into $a(pm')^{k}/p^{h}=am'^{k}/p^{h-k}$, so the summand depends on $m'$ only modulo $p^{h-k}$. As $p^{h-1}=p^{k-1}\cdot p^{h-k}$, the range of $m'$ covers each residue class modulo $p^{h-k}$ exactly $p^{k-1}$ times, which produces the factor $p^{k-1}$ and the complete sum $S(p^{h-k},a)$.

Together with the vanishing of the coprime part, this is the recursion $S(p^{h},a)=p^{k-1}S(p^{h-k},a)$ that drives the classical estimate $|S(q,a)|\ll q^{1-1/k+\varepsilon}$. Note the exponents match exactly: $p^{k-1}\cdot p^{(h-k)(1-1/k)}=p^{h(1-1/k)}$, so the induction loses nothing.

Formalization note. No coprimality between $a$ and $p$ is required here; the identity is purely a reindexing. The hypothesis $p\ge1$ only rules out the empty modulus.

Let $p$ be a prime, $k\ge1$, and let $a$ be an integer with $p\nmid a$. Write

(...)

Split this complete sum according to whether $p\mid m$. The assertion is that the part running over $m$ prime to $p$ vanishes identically,

(...)

provided $h$ is large enough relative to how divisible $k$ is by $p$: precisely, whenever there is a $j\ge1$ with $p^{j}\nmid k$ and $2j\le h$.

Why it is true. Substitute $m\mapsto m+p^{h-j}t$. Since $2j\le h$ we have $2(h-j)\ge h$, so $(p^{h-j}t)^{2}\equiv0\pmod{p^{h}}$ and the binomial expansion terminates after the linear term:

(...)

The substitution permutes the residues prime to $p$, so averaging over $t$ modulo $p^{h}$ gives

(...)

The inner sum is a complete additive character sum, hence $0$ unless $p^{j}\mid a k m^{k-1}$. As $p\nmid a$ and $p\nmid m$, that would force $p^{j}\mid k$, which is excluded. So every inner sum vanishes and the whole coprime part is $0$.

This is the engine behind the prime-power estimate for $S(q,a)$: it reduces $S(p^{h},a)$ to its $p\mid m$ part, which is a scaled copy of $S(p^{h-k},a)$, and iterating that recursion yields the classical bound $|S(q,a)|\ll q^{1-1/k+\varepsilon}$ of Vaughan, Theorem 4.2.

Remark. When $p\nmid k$ one may take $j=1$, so the conclusion holds for every $h\ge2$.

Let $S(\alpha,N)=\sum_{n<N}\Lambda(n)e(\alpha n)$ be the von Mangoldt exponential sum. Then for every $n$,

(...)

This is the starting point of the three primes theorem. The quantity $R(n)$ is the von Mangoldt weighted count of representations of $n$ as an ordered sum of three prime powers below $N$; showing $R(n)>0$ for large odd $n$ is exactly what Vinogradov's theorem asserts, and the circle method attacks it by splitting the integral into major and minor arcs.

The identity itself is exact and elementary — no estimate is involved — but it is the bridge that turns an additive question about primes into an analytic question about the size of $S(\alpha,N)$ on the circle.

Let $w:\mathbb N\to\mathbb C$ be arbitrary weights and set $F(\alpha)=\sum_{a<N}w(a)e(\alpha a)$. Then for every natural number $n$,

(...)

This is the fundamental counting identity of the circle method in its ternary, weighted form: the $n$-th Fourier coefficient of $F^3$ is the weighted number of representations of $n$ as an ordered sum of three elements below $N$. Stating it for arbitrary weights rather than for a specific arithmetic function is what makes it reusable — the von Mangoldt weighting, the indicator of the primes and any smoothed variant are all instances.

For every real $m$ and all $a<b$, the function $\alpha\mapsto e(m\alpha)$ is interval integrable on $[a,b]$.

Every integrand appearing in the circle method is, after expanding the generating function, a finite linear combination of such pure phases; this lemma is what allows the integral to be exchanged with those finite sums.

The character $e(\theta)=\exp(2\pi i\theta)$ is a continuous function $\mathbb R\to\mathbb C$.

Continuity is the hypothesis behind every integrability claim in the circle method: the generating functions are finite sums of continuous functions, so all the integrals over $[0,1]$ that define Fourier coefficients exist.

Let $q\ge1$, let $b$ be coprime to $q$, and let $N\ge0$. Then

(...)

where $\tau(\chi)=\sum_{m<q}\chi(m)e(m/q)$ is the Gauss sum and $\psi(N,\chi)=\sum_{n<N}\Lambda(n)\chi(n)$ is the von Mangoldt sum twisted by $\chi$.

This is the identity that governs the major arcs in the three primes theorem. It is exact — no approximation has been made — and it converts the behaviour of the prime-side generating function at a rational point $b/q$ into a weighted average of character sums. Estimating each $\psi(N,\chi)$ by the prime number theorem in arithmetic progressions, and evaluating the Gauss sums, is what produces the main term $\varphi(q)^{-1}\mu(q)N$ together with the singular series.

For every modulus $q$, every $\alpha$ and every $N$,

(...)

On a major arc around $b/q$ only the first sum is expanded in Dirichlet characters; the second is an error term supported on the powers of the primes dividing $q$, and is negligible. Recording the split explicitly keeps the character expansion an exact identity rather than an approximation.

For a Dirichlet character $\chi$ modulo $q$,

(...)

A Dirichlet character vanishes on residues that are not units, so the twisted sum automatically discards the $n$ sharing a factor with $q$. The identity is what lets one pass freely between the twisted sum and the sum restricted to reduced residues in the major-arc expansion.

Let $q\ge1$ and let $b$ be coprime to $q$. Write

(...)

for the Gauss sum of a Dirichlet character $\chi$ modulo $q$. Then

(...)

the sum running over all $\varphi(q)$ Dirichlet characters modulo $q$ with values in $\mathbb C$.

This is the exact dual of the definition of a Gauss sum: it expresses the additive character at a reduced fraction as a linear combination of multiplicative characters. It is the identity that converts the major-arc analysis of an exponential sum over primes into a question about $L$-functions, since after substituting it the inner sum becomes a von Mangoldt sum twisted by a Dirichlet character.

For $q\ge1$ and any natural number $b$,

(...)

Replacing a numerator by its least nonnegative residue is the step that connects a sum indexed by $\{0,\dots,q-1\}$ with an arbitrary rational point $b/q$ of the circle.

Let $Q$ be squarefree and let $n$ be odd. Then

(...)

Every truncation of the three primes singular series at a squarefree modulus is nonzero — in fact positive — for odd $n$. This is the complement of the vanishing at even $n$, and it is the local input to the assertion that the main term of the three primes asymptotic does not degenerate.