Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Sieve Methods

Field: Analytic Number Theory

Techniques used to count or estimate the size of sets of integers.

Sequence of Expressions

Let AA be a set of integers, typically A=[1,x]∩SA = [1, x] \cap S for some set S⊂ZS \subset \mathbb{Z}. Let P={p1,p2,…,pk}P = \{p_1, p_2, \dots, p_k\} be a finite set of distinct primes. The sieve method aims to estimate the cardinality of the sifted set A(P)={a∈A:gcd⁡(a,P)=1}A(P) = \{a \in A : \gcd(a, P) = 1\}.\n\nFormally, the count is given by the inclusion-exclusion principle:\nΦ(A,P)=∑d∣P,d square-freeμ(d)∣A∩dZ∣\Phi(A, P) = \sum_{d | P, d \text{ square-free}} \mu(d) \left| A \cap d\mathbb{Z} \right|\n\nWhere μ(d)\mu(d) is the Mobius function, and ∣A∩dZ∣\left| A \cap d\mathbb{Z} \right| is the number of elements in AA divisible by dd. \n\nFor the standard case A=[1,x]A = [1, x], the count is approximated by the product formula, which forms the basis of the sieve's asymptotic estimate:\nΦ(x,P)≈x∏p∈P(1−1p)\Phi(x, P) \approx x \prod_{p \in P} \left(1 - \frac{1}{p}\right) \n\nMore generally, the sieve process is formalized by defining a multiplicative function ω(d)\omega(d) (the sifting weight) such that the count is approximated by ∑d∣Pω(d)∣A∩dZ∣\sum_{d | P} \omega(d) \left| A \cap d\mathbb{Z} \right|, where ω(1)=1\omega(1)=1 and ω(d)\omega(d) is chosen to satisfy the inclusion-exclusion structure while minimizing error terms, as seen in Selberg's sieve weights.