W-trick: Difference between revisions
No edit summary |
|||
| Line 1: | Line 1: | ||
The W-trick is a simple trick to remove some of the structure from the set of primes, and also to increase the density of primes slightly. Basically, instead of looking at the set <math>{\mathcal P} := \{2,3,5,7,\ldots\}</math> of primes, one instead looks at the set <math>{\mathcal P}_{W,b} := \{ n: Wn+b \in {\mathcal P} \}</math>, where <math>W := \prod_{p \leq w} p</math> is the product of all primes less than some threshold w, and b is a number coprime to W (in many cases one can just take b=1). It is a result in elementary number theory that <math>W = \exp((1+o(1))w)</math>, thus W is of exponential size in w. If one seeks primes less than N, one must therefore set w no larger than <math>\log N</math> or so. | |||
The set <math>{\mathcal P}_{W,b}</math> is a little bit denser than the primes; the primes less than N have density about <math>1/\log N</math> by the prime number theorem, but <math>{\mathcal P}_{W,b}</math> has density about <math> \frac{W}{\phi(W)} \frac{1}{\log N} \approx \frac{\log w}{\log N}</math>; raising w to <math>O(\log N)</math> (which is the largest feasible value), the density of the W-tricked primes thus increases slightly from <math>1/\log N</math> to about <math>\log \log N / \log N</math>. | |||
The W-tricked primes <math>{\mathcal P}_{W,b}</math> also behave more 'pseudorandomly' than the primes themselves. For instance, the primes are of course highly biased to favour odd numbers over even numbers, but the W-tricked primes have no such bias once w is at least 2 (by the prime number theorem in arithmetic progressions). More generally, the primes do not equidistribute modulo q for any q, but the W-tricked primes do as soon as w is greater than or equal to all the prime factors of q. | |||
Latest revision as of 02:05, 5 July 2013
The W-trick is a simple trick to remove some of the structure from the set of primes, and also to increase the density of primes slightly. Basically, instead of looking at the set [math]\displaystyle{ {\mathcal P} := \{2,3,5,7,\ldots\} }[/math] of primes, one instead looks at the set [math]\displaystyle{ {\mathcal P}_{W,b} := \{ n: Wn+b \in {\mathcal P} \} }[/math], where [math]\displaystyle{ W := \prod_{p \leq w} p }[/math] is the product of all primes less than some threshold w, and b is a number coprime to W (in many cases one can just take b=1). It is a result in elementary number theory that [math]\displaystyle{ W = \exp((1+o(1))w) }[/math], thus W is of exponential size in w. If one seeks primes less than N, one must therefore set w no larger than [math]\displaystyle{ \log N }[/math] or so.
The set [math]\displaystyle{ {\mathcal P}_{W,b} }[/math] is a little bit denser than the primes; the primes less than N have density about [math]\displaystyle{ 1/\log N }[/math] by the prime number theorem, but [math]\displaystyle{ {\mathcal P}_{W,b} }[/math] has density about [math]\displaystyle{ \frac{W}{\phi(W)} \frac{1}{\log N} \approx \frac{\log w}{\log N} }[/math]; raising w to [math]\displaystyle{ O(\log N) }[/math] (which is the largest feasible value), the density of the W-tricked primes thus increases slightly from [math]\displaystyle{ 1/\log N }[/math] to about [math]\displaystyle{ \log \log N / \log N }[/math].
The W-tricked primes [math]\displaystyle{ {\mathcal P}_{W,b} }[/math] also behave more 'pseudorandomly' than the primes themselves. For instance, the primes are of course highly biased to favour odd numbers over even numbers, but the W-tricked primes have no such bias once w is at least 2 (by the prime number theorem in arithmetic progressions). More generally, the primes do not equidistribute modulo q for any q, but the W-tricked primes do as soon as w is greater than or equal to all the prime factors of q.
