Open MathsAll courses

Square-root bounds and collision stability

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

Under the standing assumption of Lesson 1, every large prime is a sum \(a+b\) with \(a\in A\), \(b\in B\), so \(A(Y)B(Y)\gg Y/\log Y\). This lesson proves the matching upper bounds: both counting functions lie within powers of \(\log Y\) of \(\sqrt Y\) (Theorem 3.1, due to Elsholtz). Two sieves are played against each other. The large sieve says that a set avoiding many residue classes is small; the larger sieve, which counts congruent pairs, says that a set occupying few residue classes is small. Exclusion makes the large elements of \(A\) avoid the classes occupied by \(-B\), so the two sieves bound each other.

The same congruent-pair count gives the main tool of the course, collision stability (Lemma 4.1). On a weighted average over primes, the reductions modulo \(p\) of the large elements of \(A\) are nearly uniform on the support \(S_p\) of Lesson 1, those of \(D=-B\) are nearly uniform on \(S_p^c\), and \(|S_p|\) is close to \(p/2\).

Prerequisites. The inverse Goldbach problem, Sections 2, 5 and 6; Counting primes by elementary means: Chebyshev and Mertens, Theorems 2.1 and 3.1; The prime number theorem, Theorem 3.1.

1. Conventions on finite fields

Write \(e(x)=e^{2\pi ix}\) and \(e_m(x)=e(x/m)\). An expectation over a finite set is its uniform average unless another probability measure is named. For a function \(f\) on \(\mathbb F_p\) the Fourier transform is \[ \begin{gathered} \widehat f(a)=\frac1p\sum_{x\in\mathbb F_p}f(x)\,e_p(-ax),\\ f(x)=\sum_{a\in\mathbb F_p}\widehat f(a)\,e_p(ax), \end{gathered} \] and Parseval's identity reads \(\mathbb E_x|f(x)|^2=\sum_a|\widehat f(a)|^2\). Norms of functions on \(\mathbb F_p\) use the probability measure unless stated otherwise. For the mass function \(\mu\) of a probability measure on \(\mathbb F_p\), however, the counting norm \[ \|\mu\|_2^2=\sum_{x\in\mathbb F_p}\mu(x)^2 \] is used; it is the probability that two independent samples of \(\mu\) coincide. For a nonempty finite set \(E\), \(U_E\) denotes the uniform probability measure on \(E\). For a probability measure \(\mu\) on \(\mathbb Z\), \(\mu_p\) denotes its image modulo \(p\).

Lemma 1.1 (energy of a measure avoiding classes). Let \(\mu\) be a probability measure on \(\mathbb F_p\) supported on a set of \(p-\nu\) residues, with \(0\le\nu<p\). Then \[ \sum_{h\in\mathbb F_p^\times}\Bigl|\sum_{x}\mu(x)\,e_p(hx)\Bigr|^2\ge\frac{\nu}{p-\nu}. \]

Proof. Expanding the square and summing over all \(h\in\mathbb F_p\) gives \(p\sum_x\mu(x)^2\), by orthogonality. By Cauchy–Schwarz on the support, \(1=(\sum_x\mu(x))^2\le(p-\nu)\sum_x\mu(x)^2\). So the sum over all \(h\) is at least \(p/(p-\nu)\); the term \(h=0\) equals \(1\), and \(p/(p-\nu)-1=\nu/(p-\nu)\). \(\square\)

2. Counting congruent pairs

The following count is the larger sieve of Gallagher in the form used by Green and Harper [GH]. Let \(\mu\) be a probability measure on integers in an interval of length at most \(X\), and let \(n,n'\) be independent samples of \(\mu\). For a prime \(p\), \(\|\mu_p\|_2^2=\Pr(n\equiv n'\pmod p)\). For any set \(\mathcal P\) of primes at most \(Q\), \[ \begin{aligned} &\sum_{p\in\mathcal P}(\log p)\,\|\mu_p\|_2^2\\ &\quad =\mathbb E\sum_{\substack{p\in\mathcal P\\p\mid n-n'}}\log p \le\log X\\ &\qquad +\Pr(n=n')\\ &\qquad \sum_{p\le Q}\log p.\quad(2.1) \end{aligned} \] Indeed, if \(n\ne n'\) the primes dividing \(n-n'\) have product at most \(|n-n'|\le X\); if \(n=n'\), every prime divides \(0\). Chebyshev's bound \(\sum_{p\le Q}\log p\ll Q\) (Counting primes by elementary means: Chebyshev and Mertens, Theorem 2.1) and \(\Pr(n=n')=\sum_n\mu(n)^2\le\max_n\mu(n)\) give \[ \begin{aligned} &\sum_{p\in\mathcal P}(\log p)\,\|\mu_p\|_2^2\\ &\quad \le\log X+O\bigl(Q\max_n\mu(n)\bigr).\quad(2.2) \end{aligned} \] If \(\mu_p\) is supported on \(\nu\) residues, Cauchy–Schwarz gives \(\|\mu_p\|_2^2\ge1/\nu\). So a measure occupying few classes modulo many primes has a large left side in (2.2), and (2.2) bounds it.

3. Square-root bounds

Theorem 3.1 (Elsholtz [Els06, Theorem 1.9]; [OpenAI-013, Lemma 2.4]). Under the standing assumption, for \(Y\ge3\), \[ \begin{aligned} \frac{\sqrt Y}{(\log Y)^3}&\ll A(Y),\,B(Y)\\ &\ll\sqrt Y(\log Y)^2.\quad(3.1) \end{aligned} \]

Proof. Step 1: the product bound and polylogarithmic bounds. Every prime \(p\in(N,Y]\) is \(a+b\) with \(a\in A\cap[0,Y]\) and \(b\in B\cap[0,Y]\), so Chebyshev's lower bound gives \[ \begin{aligned} &A(Y)\,B(Y)\ge\pi(Y)-\pi(N)\\ &\quad \gg\frac{Y}{\log Y}.\quad(3.2) \end{aligned} \] By Exercise 8.2 of Lesson 1, for every fixed \(j\ge1\), \[ \begin{gathered} A(Y),B(Y)\ll_j\frac{Y}{(\log Y)^j},\\ A(Y),B(Y)\gg_j(\log Y)^{j}.\quad(3.3) \end{gathered} \]

Step 2: a large-sieve lower bound for a collision sum. Let \(x\) be large, put \(m=A(x)\), and suppose \(m\ge3\sqrt x\). The set \(U=A\cap(\sqrt x+N_*,x]\) has at least \(m-\sqrt x-N_*-1\ge m/2\) elements. For a prime \(p\) let \(\nu_p\) be the number of residue classes modulo \(p\) that meet \(B\).

Let \(p\in(\sqrt x/2,\sqrt x]\). The set \(U\) avoids the \(\nu_p\) classes of \(-B\) modulo \(p\). If \(a\equiv-b\pmod p\) with \(a\in U\) and \(b\in B\), then \(a+b\in A+B\) is divisible by \(p\) and \(a+b\ge a>\sqrt x+N_*>\max(p,N)\); by exclusion \(a+b\) is a prime divisible by \(p\) and larger than \(p\), which is impossible. Since \(U\) is nonempty, \(\nu_p<p\), and Lemma 1.1 applied to the image of \(U_U\) modulo \(p\) gives \[ \sum_{h\in\mathbb F_p^\times}\Bigl|\mathbb E_{a\in U}e_p(ha)\Bigr|^2\ge\frac{\nu_p}{p-\nu_p}\ge\frac{\nu_p}p. \] Apply the large sieve (2.1) of Lesson 1 with \(Q=\sqrt x\) and \(a_n=\mathbf 1_U(n)/|U|\), supported on at most \(x+1\) consecutive integers, so that \(\sum|a_n|^2=1/|U|\). Retaining only the prime moduli in \((\sqrt x/2,\sqrt x]\), \[ \sum_{\sqrt x/2<p\le\sqrt x}\frac{\nu_p}p\le\frac{2x}{|U|}\le\frac{4x}m. \] Let \(\mathcal P_x\) be the set of primes in \((\sqrt x/2,\sqrt x]\); by the prime number theorem \(|\mathcal P_x|\gg\sqrt x/\log x\). By Cauchy–Schwarz, \(|\mathcal P_x|^2\le\bigl(\sum_{p}\nu_p/p\bigr)\bigl(\sum_pp/\nu_p\bigr)\), with both sums over \(\mathcal P_x\). Hence \(\sum_{p\in\mathcal P_x}p/\nu_p\gg m/(\log x)^2\), and since \(p\le\sqrt x\) and \(\log p\ge\log(\sqrt x/2)\gg\log x\) on \(\mathcal P_x\), \[ \begin{aligned} H&:=\sum_{p\in\mathcal P_x}\frac{\log p}{\nu_p}\\ &\gg\frac{\log x}{\sqrt x}\sum_{p\in\mathcal P_x}\frac p{\nu_p}\\ &\gg\frac{m}{\sqrt x\,\log x}.\quad(3.4) \end{aligned} \]

Step 3: a larger-sieve upper bound for the same sum. Let \(Y\ge2\) with \(B(Y)\ge1\), and let \(\mu\) be the uniform measure on \(B\cap[0,Y]\). Its image modulo \(p\) occupies at most \(\nu_p\) classes, so \(\|\mu_p\|_2^2\ge1/\nu_p\). By (2.1) with \(\mathcal P=\mathcal P_x\), Chebyshev's bound \(\sum_{p\le\sqrt x}\log p\ll\sqrt x\), and \(\Pr(n=n')=1/B(Y)\), \[ H\le\log Y+O\left(\frac{\sqrt x}{B(Y)}\right). \tag{3.5} \]

Step 4: exponents. Let \(\varepsilon>0\) and suppose that \(A(x)>x^{1/2+\varepsilon}\) for arbitrarily large \(x\). For such \(x\) the hypothesis \(m\ge3\sqrt x\) of Step 2 holds. Choose \(Y\) with \(\log Y=x^{\varepsilon/2}\). Then (3.4) gives \(H\gg x^{\varepsilon}/\log x\), which exceeds \(2\log Y\) for large \(x\), so (3.5) forces \(\sqrt x/B(Y)\gg H\gg x^{\varepsilon}/\log x\), that is, \[ B(Y)\ll x^{1/2-\varepsilon}\log x. \] But (3.3) with an integer \(j>1/\varepsilon\) gives \(B(Y)\gg_j(\log Y)^j=x^{j\varepsilon/2}>x^{1/2}\) for large \(x\). This contradiction shows \(A(x)\le x^{1/2+\varepsilon}\) for all large \(x\). The argument is symmetric in \(A\) and \(B\): exclusion makes the large elements of \(B\) avoid the classes of \(-A\). So \(B(x)\le x^{1/2+\varepsilon}\) as well, and (3.2) gives the lower bounds \(A(x),B(x)\ge x^{1/2-\varepsilon}\) for large \(x\). Thus \[ \begin{gathered} A(x)=x^{1/2+o(1)},\\ B(x)=x^{1/2+o(1)}.\quad(3.6) \end{gathered} \]

Step 5: the logarithmic bounds. Take \(Y=x^2\) in (3.5). By (3.6), \(B(x^2)=x^{1+o(1)}\), so \(\sqrt x/B(x^2)=o(1)\) and \(H\le2\log x+o(1)\). If \(m=A(x)\ge3\sqrt x\), (3.4) gives \(m/(\sqrt x\log x)\ll\log x\), that is \(A(x)\ll\sqrt x(\log x)^2\); if \(m<3\sqrt x\) this bound is immediate. The same holds for \(B\). Finally (3.2) gives \[ \begin{aligned} A(x)&\gg\frac{x}{\log x\cdot B(x)}\\ &\gg\frac{x}{\log x\cdot\sqrt x(\log x)^2}\\ &=\frac{\sqrt x}{(\log x)^3}, \end{aligned} \] and the same for \(B\). \(\square\)

4. Collision stability

The congruent-pair count also measures how far a summand is from being uniform on its residue support. Recall from Lesson 1 the partition \(\mathbb F_p=S_p\sqcup S_p^c\) and \(\sigma_p=|S_p|/p\).

Lemma 4.1 (collision stability [OpenAI-013, Lemma 2.5]). Let \(b\ge1\) be fixed and let \(X\) be large. Suppose that \(\mu\) and \(\nu\) are probability measures on \[ \begin{gathered} A\cap(\sqrt X+N_*,X]\\ \text{and}\\ D\cap[-X,-\sqrt X-N_*), \end{gathered} \] respectively, with every point mass at most \((\log X)^b/\sqrt X\). Put \(Q=\sqrt X/(\log X)^{b+1}\). Then \[ \begin{aligned} &\sum_{p\le Q}\log p\biggl(\|\mu_p-U_{S_p}\|_2^2\\ &\qquad+\|\nu_p-U_{S_p^c}\|_2^2\\ &\qquad+\frac{\sigma_p^{-1}+(1-\sigma_p)^{-1}-4}{p}\biggr)\\ &\quad\ll_b\log\log X,\quad(4.1) \end{aligned} \] and every term on the left is nonnegative.

Proof. Supports. Let \(p\le Q\). If \(a\in A\) and \(a>\sqrt X+N_*\), then \(a>p+N_*\), so \(a\bmod p\) lies in the set \(\mathcal A_p\subseteq S_p\) of Lemma 6.1 of Lesson 1. So \(\mu_p\) is supported on \(S_p\), and likewise \(\nu_p\) is supported on \(S_p^c\). For a probability measure supported on a set \(E\), \[ \begin{aligned} \|\mu_p-U_E\|_2^2&=\|\mu_p\|_2^2\\ &\quad -\frac2{|E|}\sum_{x\in E}\mu_p(x)\\ &\quad +\frac1{|E|}\\ &=\|\mu_p\|_2^2-\frac1{|E|}. \end{aligned} \] With \(|S_p|=p\sigma_p\) and \(|S_p^c|=p(1-\sigma_p)\), the bracket in (4.1) therefore equals \(\|\mu_p\|_2^2+\|\nu_p\|_2^2-4/p\).

Collision energies. Both measures live on intervals of length at most \(X\), and \(Q\max_n\mu(n)\le1/\log X\). By (2.2), \[ \begin{aligned} &\sum_{p\le Q}(\log p)\bigl(\|\mu_p\|_2^2+\|\nu_p\|_2^2\bigr)\\ &\quad \le2\log X+O(1). \end{aligned} \] Mertens' estimate gives \[ \begin{aligned} 4\sum_{p\le Q}\frac{\log p}p&=4\log Q+O(1)\\ &=2\log X\\ &\quad -4(b+1)\log\log X\\ &\quad +O(1). \end{aligned} \] Subtracting proves (4.1).

Nonnegativity. For \(0<\sigma<1\), \[ \begin{aligned} &\frac1\sigma+\frac1{1-\sigma}-4=\frac{(1-2\sigma)^2}{\sigma(1-\sigma)}\\ &\quad \ge0.\quad(4.2) \end{aligned} \] \(\square\)

By (4.2) and \(\sigma(1-\sigma)\le\frac14\), \[ \begin{aligned} &\frac1{\sigma_p}+\frac1{1-\sigma_p}-4\\ &\quad \ge16\Bigl(\sigma_p-\frac12\Bigr)^2,\quad(4.3) \end{aligned} \] and the left side is at least \(\tfrac12\) when \(\sigma_p\notin[\tfrac13,\tfrac23]\). So (4.1) bounds the \((\log p)/p\)-weight of the unbalanced primes.

Corollary 4.2 (test functions). In the setting of Lemma 4.1, let \(f_p\colon\mathbb F_p\to\mathbb C\) be functions with \(\mathbb E_{x\in\mathbb F_p}|f_p(x)|^2\le1\), chosen separately at every prime. Then \[ \begin{aligned} &\sum_{p\le Q}\frac{\log p}p\Bigl|\mathbb E_{\mu}f_p\\ &\qquad -\mathbb E_{x\in S_p}f_p(x)\Bigr|^2\\ &\quad \ll_b\log\log X,\quad(4.4) \end{aligned} \] where \(\mathbb E_\mu f_p=\sum_n\mu(n)f_p(n\bmod p)\), and the same holds for \(\nu\) with \(S_p^c\).

Proof. By Cauchy–Schwarz, \[ \begin{aligned} &\Bigl|\sum_x\bigl(\mu_p(x)-U_{S_p}(x)\bigr)f_p(x)\Bigr|^2\\ &\quad \le\|\mu_p-U_{S_p}\|_2^2\sum_x|f_p(x)|^2\\ &\quad \le p\,\|\mu_p-U_{S_p}\|_2^2 . \end{aligned} \] Multiply by \((\log p)/p\), sum, and apply (4.1). \(\square\)

The corollary needs no pointwise bound on \(f_p\): only the probability \(L^2\) norm enters. This matters later, when the test functions are inverse Fourier transforms that can be as large as \(\sqrt p\) at single points.

5. The tails used in later lessons

For large \(X\) put \[ \begin{gathered} A_X=A\cap[X^{9/10},X],\\ D_X=D\cap[-X,-X^{9/10}].\quad(5.1) \end{gathered} \]

Lemma 5.1. For large \(X\), \(|A_X|,|D_X|\gg\sqrt X/(\log X)^3\), and the uniform measures on \(A_X\) and \(D_X\) satisfy the hypotheses of Lemma 4.1 with \(b=4\).

Proof. By Theorem 3.1, \(|A_X|\ge A(X)-A(X^{9/10})\)\(\ge c\sqrt X/(\log X)^3\)\(-CX^{9/20}(\log X)^2\gg\sqrt X/(\log X)^3\). Every point mass is \(1/|A_X|\ll(\log X)^3/\sqrt X\)\(\le(\log X)^4/\sqrt X\) for large \(X\), and \(X^{9/10}>\sqrt X+N_*\). The same holds for \(D_X\), using \(B\). \(\square\)

With \(b=4\), Lemma 4.1 and Corollary 4.2 apply to all primes \(p\le\sqrt X/(\log X)^5\). In particular, for any functions \(\phi_p\) with \(|\phi_p|\le1\), \[ \begin{aligned} &\sum_{p\le\sqrt X/(\log X)^5}\frac{\log p}p \Bigl|\mathbb E_{x\in A_X}\phi_p(x)\\ &\qquad -\mathbb E_{x\in S_p}\phi_p(x)\Bigr|^2\ll\log\log X,\quad(5.2) \end{aligned} \] and the same with \(D_X\) and \(S_p^c\). In words: for any choice of bounded test functions, one at each prime, the empirical mean over the tail \(A_X\) and the uniform mean over \(S_p\) agree up to an error whose square has \((\log p)/p\)-weighted sum \(O(\log\log X)\). Since \(\sum_{p\le y}(\log p)/p\sim\log y\), the two means agree for all primes outside a set of \((\log p)/p\)-weight \(O_\delta(\log\log X)\), up to any fixed tolerance \(\delta\).

6. Exercises

6.1. Show that (4.1) and (4.3) give, for \(2\le y\le\sqrt X/(\log X)^{b+1}\) and fixed \(\delta>0\), \[ \sum_{\substack{p\le y\\|\sigma_p-1/2|>\delta}}\frac{\log p}p\ll_{b}\delta^{-2}\log\log X. \]

6.2 (Gallagher's larger sieve). Let \(\mathcal A\) be a finite set of integers in an interval of length \(X\ge2\), and let \(\mathcal P\) be a finite set of primes such that \(\mathcal A\) meets at most \(\nu_p\) classes modulo \(p\) for each \(p\in\mathcal P\). Show that \[ |\mathcal A|\le\frac{\sum_{p\in\mathcal P}\log p-\log X}{\sum_{p\in\mathcal P}(\log p)/\nu_p-\log X} \] whenever the denominator is positive.

6.3. In Lemma 1.1, show that equality holds exactly when \(\mu\) is uniform on a set of \(p-\nu\) residues.

6.4. Let \(0<\alpha<\tfrac12\). Suppose that a set \(\mathcal A\subseteq[1,X]\) meets at most \(\alpha p+1\) classes modulo every prime \(p\le X\). Use Exercise 6.2 with the primes up to \(X^{\alpha+\varepsilon}\) to show \(|\mathcal A|\ll_{\alpha,\varepsilon}X^{\alpha+\varepsilon}\) for every \(\varepsilon>0\).

7. Solutions

6.1. By (4.3), each prime with \(|\sigma_p-\tfrac12|>\delta\) has \(\sigma_p^{-1}+(1-\sigma_p)^{-1}-4>16\delta^2\). All terms of (4.1) are nonnegative, so the \((\log p)/p\)-weight of these primes up to \(y\le Q\) is at most \((16\delta^2)^{-1}\) times the left side of (4.1).

6.2. Let \(\mu\) be the uniform measure on \(\mathcal A\). The equality in (2.1) and the bound \(\|\mu_p\|_2^2\ge1/\nu_p\) give \[ \begin{aligned} \sum_{p\in\mathcal P}\frac{\log p}{\nu_p}&\le\Bigl(1-\frac1{|\mathcal A|}\Bigr)\log X\\ &\quad +\frac1{|\mathcal A|}\sum_{p\in\mathcal P}\log p, \end{aligned} \] because \(\Pr(n=n')=1/|\mathcal A|\) and the bound \(\log X\) applies only when \(n\ne n'\). Multiplying by \(|\mathcal A|\) and rearranging gives \(|\mathcal A|\bigl(\sum_p(\log p)/\nu_p-\log X\bigr)\)\(\le\sum_p\log p-\log X\).

6.3. Equality in Lemma 1.1 means equality in \(1\le(p-\nu)\sum_x\mu(x)^2\), which is Cauchy–Schwarz for the vectors \((\mu(x))\) and \((1)\) on the support; it holds exactly when \(\mu\) is constant on its support.

6.4. Let \(\mathcal P\) be the primes up to \(Q=X^{\alpha+\varepsilon}\), so \(\nu_p\le\alpha p+1\). The numerator in Exercise 6.2 is at most \(\sum_{p\le Q}\log p\ll Q\). For the denominator, \((\log p)/\nu_p\ge(\log p)/(\alpha p+1)\)\(\ge(\log p)/(\alpha p)-(\log p)/(\alpha^2p^2)\), and Mertens' estimate gives \[ \begin{aligned} \sum_{p\le Q}\frac{\log p}{\nu_p}&\ge\frac{\log Q}{\alpha}-O_\alpha(1)\\ &=\Bigl(1+\frac\varepsilon\alpha\Bigr)\log X-O_\alpha(1). \end{aligned} \] So the denominator is at least \((\varepsilon/\alpha)\log X-O_\alpha(1)\gg_{\alpha,\varepsilon}\log X\) for large \(X\), and \(|\mathcal A|\ll Q/\log X\le X^{\alpha+\varepsilon}\).

Sources