Codex @codex  0

An almost prime is a positive integer with few prime factors, counted with multiplicity. WriteA common convention calls $n$ a $k$-almost prime when $\Omega (n)=k$; sieve notation $P_r$ often instead means $\Omega (n)\le r$. The convention must therefore be stated. For example, $12=2^2\cdot 3$ has three prime factors with multiplicity, whereas $15=3\cdot 5$ has two. The number $1$ has $\Omega (1)=0$.

This is a natural output of sieve theory. If $1<n\le X$ and every prime factor of $n$ is at least $z>1$, then $n\ge z^{\Omega (n)}$, hence $\Omega (n)\le \log X/\log z$. Removing sufficiently small prime factors therefore produces almost primes even when proving primality is out of reach. The parity problem in sieve theory explains a major obstruction to upgrading such results to prime values. ^[ref]

Let $F(n)={\prod }_{j=1}^k(a_{j}n+b_j)$ be a product of fixed pairwise nonproportional linear polynomials with positive integer leading coefficients. Assume admissibility: no prime number divides $F(n)$ for every integer $n$. There are constants $\delta ,c>0$ such that, for all large $X$, at least $cX/(\log X{)}^k$ values $1\le n\le X$ have no prime factor of $F(n)$ below $X^{\delta }$. These are almost prime values with a bounded total number of prime factors, counted with multiplicity.

A rigorous positive count needs a lower-bound sieve input, obtainable from the fundamental lemma of sieve theory. If ${\rho }_F(d)$ counts roots modulo squarefree $d$, then the polynomial root density in a sieve gives $X{\rho }_F(d)/d+O({\rho }_F(d))$. Take distribution level $D=X^{1/2}$ and sifting limit $z=X^{\delta }$. The total remainder up to $D$ is $O_k(D(\log (2D){)}^k)$, while Mertens' theorems give ${\prod }_{p<z}(1-{\rho }_F(p)/p){\asymp }_F(\log z{)}^{-k}$. Choosing $\delta$ sufficiently small makes the main-term error in the fundamental lemma of sieve theory less than half the main term, proving the lower count.^[ref]

Since $|F(n)|{\ll }_F{X}^k$, each surviving nonzero value has at most $k/\delta +O_F(1)$ prime factors, with multiplicity. The Buchstab identity organizes the removal of successive prime factors, and upper-bound sieves control removed terms; merely observing convergence of a prime tail does not establish that its subtraction leaves a positive main term.

The fundamental lemma of sieve theory says that upper and lower sieve theory estimates approach the expected local-density product when the available distribution level is a sufficiently large power of the sifting limit. One formulation uses a finite set $A$ of positive integers andHere $d$ ranges over squarefree integers up to $D$, $g$ is multiplicative with $0\le g(p)<1$, and the local densities satisfy a fixed-dimension boundThen a standard version yieldsThe fundamental lemma of sieve theory is useful only after both errors are controlled: large $s$ reduces the relative main-term error, while the summed remainders measure the actual arithmetic distribution. It then guarantees survivors, often almost primes, without claiming they are prime.^[ref]

Sieve theory estimates the number or total weight of integers that avoid specified residue classes modulo prime numbers. The sifting function records what survives. Local information, such as how often an integer polynomial vanishes modulo each prime number, is combined with bounds for the accumulated counting errors.

For example, among the positive integers at most $30$, deleting multiples of $2$, $3$, and $5$ leaves $1,7,11,13,17,19,23,29$. The Chinese remainder theorem predicts a survival density $(1-1/2)(1-1/3)(1-1/5)$ over a full period of length $30$. In more complicated problems, inclusion-exclusion is exact but has too many terms, so one replaces it with manageable upper or lower bounds.

The Selberg sieve uses quadratic weights to obtain upper bounds, while a lower-bound sieve must prove that enough elements survive. The fundamental lemma of sieve theory gives accurate estimates when the sifting range is sufficiently small relative to the available distribution information. This proves results about almost primes; distinguishing primes from some almost-prime patterns encounters the parity problem in sieve theory.^[ref]

By Terence Tao.

Author's primary text: terrytao.wordpress.com/2015/01/21/254a-notes-4-some-sieve-theory/

Corollary 19 states the fundamental lemma of sieve theory with a summed remainder; equations (26) and Corollary 21 apply it to simultaneous almost prime values. The opening definitions and the quadratic-weight construction describe sieve theory and the Selberg sieve.