# W-trick

### From Polymath1Wiki

Current revision (10:05, 5 July 2013) (view source) |
|||

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. | |

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + | ||

- | + |

## Current revision

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 of primes, one instead looks at the set , where 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 *W* = exp((1 + *o*(1))*w*), thus W is of exponential size in w. If one seeks primes less than N, one must therefore set w no larger than log*N* or so.

The set is a little bit denser than the primes; the primes less than N have density about 1 / log*N* by the prime number theorem, but has density about ; raising w to *O*(log*N*) (which is the largest feasible value), the density of the W-tricked primes thus increases slightly from 1 / log*N* to about loglog*N* / log*N*.

The W-tricked primes 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.