# 254A, Notes 4: Some sieve theory What's new

Many problems in non-multiplicative prime number theory can be recast as sieving problems. Consider for instance the problem of counting the number \$latex {N(x)}&fg=000000\$ of pairs of twin primes \$latex {p,p+2}&fg=000000\$ contained in \$latex {[x/2,x]}&fg=000000\$ for some large \$latex {x}&fg=000000\$; note that the claim that \$latex {N(x) > 0}&fg=000000\$ for arbitrarily large \$latex {x}&fg=000000\$ is equivalent to the twin prime conjecture. One can obtain this count by any of the following variants of the sieve of Eratosthenes:

1. Let \$latex {A}&fg=000000\$ be the set of natural numbers in \$latex {[x/2,x-2]}&fg=000000\$. For each prime \$latex {p leq sqrt{x}}&fg=000000\$, let \$latex {E_p}&fg=000000\$ be the union of the residue classes \$latex {0 (p)}&fg=000000\$ and \$latex {-2 (p)}&fg=000000\$. Then \$latex {N(x)}&fg=000000\$ is the cardinality of the sifted set \$latex {A backslash bigcup_{p leq sqrt{x}} E_p}&fg=000000\$.
2. Let \$latex {A}&fg=000000\$ be the set of primes in \$latex {[x/2,x-2]}&fg=000000\$. For each prime \$latex {p leq sqrt{x}}&fg=000000\$, let…

View original post 18,216 more words

Advertisements