W-trick

From Polymath1Wiki

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 ${\mathcal P} := \{2,3,5,7,\ldots\}$ of primes, one instead looks at the set ${\mathcal P}_{W,b} := \{ n: Wn+b \in {\mathcal P} \}$ , where $W := \prod_{p \leq w} p$ 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 ${\mathcal P}_{W,b}$ 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 ${\mathcal P}_{W,b}$ has density about $\frac{W}{\phi(W)} \frac{1}{\log N} \approx \frac{\log w}{\log N}$ ; 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 ${\mathcal P}_{W,b}$ 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.

W-trick

From Polymath1Wiki

Views

Personal tools

Navigation

Search

Toolbox