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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s