MathLabs
TheoremProved

Legendre's sieve (inclusion–exclusion count)

Statement

For A={1,2,…,x}A=\{1,2,\ldots,x\} and P\mathcal P the set of primes p<zp<z, the count of a∈Aa \in A coprime to P(z)=∏p<zpP(z)=\prod_{p<z}p is S(A,P,z)=∑d∣P(z)μ(d)⌊xd⌋\displaystyle S(A,\mathcal P,z)=\sum_{d \mid P(z)} \mu(d)\Big\lfloor \dfrac{x}{d} \Big\rfloor, where μ\mu is the Möbius function; taking z=x+1z=\sqrt x+1 gives π(x)−π(x)+1=S(A,P,x)=∑d∣P(x)μ(d) ⌊x/d⌋\pi(x)-\pi(\sqrt{x})+1 = S(A,\mathcal{P},\sqrt{x}) = \sum_{d \mid P(\sqrt{x})} \mu(d)\, \lfloor x/d \rfloor.

Why is it true?

This is the precise, quantitative version of "cross off multiples": instead of physically marking a grid, it counts survivors directly by inclusion–exclusion over which small primes divide them. It is the ancestor of every modern sieve (Brun, Selberg, the large sieve, GPY) used to attack twin primes and bounded gaps — all of them are, at bottom, smarter ways of controlling the error terms that this exact formula produces.

Proof sketch

Every integer a∈Aa\in A is coprime to P(z)P(z) iff it is divisible by none of the primes p<zp<z. For each divisor d∣P(z)d\mid P(z) (a squarefree product of some subset of these primes), the count of multiples of dd in A={1,…,x}A=\{1,\ldots,x\} is exactly ⌊x/d⌋\lfloor x/d\rfloor.

By inclusion–exclusion over the events "p∣ap\mid a" for p<zp<z: the count of a∈Aa\in A divisible by at least one prime in P\mathcal P is ∑p<z⌊x/p⌋−∑p<q⌊x/(pq)⌋+∑p<q<r⌊x/(pqr)⌋−⋯\sum_{p<z}\lfloor x/p\rfloor - \sum_{p<q}\lfloor x/(pq)\rfloor + \sum_{p<q<r}\lfloor x/(pqr)\rfloor - \cdots, alternating with the number of primes multiplied together. Each such alternating sign is exactly the Möbius function μ(d)\mu(d) of the corresponding squarefree d∣P(z)d\mid P(z): μ(1)=1\mu(1)=1, μ(d)=(−1)k\mu(d)=(-1)^k for dd a product of kk distinct primes.

So the count divisible by at least one prime in P\mathcal P is −∑d∣P(z), d>1μ(d)⌊x/d⌋-\sum_{d\mid P(z),\,d>1}\mu(d)\lfloor x/d\rfloor. Subtracting this from ∣A∣=⌊x⌋=x|A|=\lfloor x\rfloor=x (the d=1d=1 term, μ(1)⌊x/1⌋=x\mu(1)\lfloor x/1\rfloor=x) gives the count coprime to P(z)P(z): S(A,P,z)=x−∑d∣P(z),d>1μ(d)⌊x/d⌋=∑d∣P(z)μ(d)⌊x/d⌋S(A,\mathcal P,z)=x-\sum_{d\mid P(z),d>1}\mu(d)\lfloor x/d\rfloor=\sum_{d\mid P(z)}\mu(d)\lfloor x/d\rfloor.

Finally, taking z=x+1z=\sqrt x+1 so that P\mathcal P is exactly the primes ≤x\le\sqrt x: any a∈[2,x]a\in[2,x] coprime to all of them is either 11 or a prime >x>\sqrt x (by the theorem above, since it has no prime factor ≤x\le\sqrt x), so S(A,P,x+1)=1+(π(x)−π(x))S(A,\mathcal P,\sqrt x+1)=1+\big(\pi(x)-\pi(\sqrt x)\big), giving the stated identity.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.

References

  1. Alina Carmen Cojocaru, M. Ram Murty (2005). An Introduction to Sieve Methods and Their Applications
  2. Yitang Zhang (2014). Bounded gaps between primes · DOI:10.4007/annals.2014.179.3.7
  3. James Maynard (2015). Small gaps between primes · DOI:10.4007/annals.2015.181.1.7