Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Hardy-Littlewood Conjecture for 3-term arithmetic progressions is that $$ \# \{ x,d \in \{1,\ldots,N\} \, | \, x,x+d,x+2d \text{ are all prime} \} \sim \frac{3}{2} \prod_{p > 2} \left(1+\frac{1}{(p-1)^2}\right) \frac{N^2}{(\log N)^3}. $$

In this (piece) of a paper (, Ben Green outlines a heuristic argument for the (k-term version) of the conjecture that I am trying to understand. I will repeat the most important parts here.

For large $N$, the probability that an arbitrary integer $\leq N$ is prime is $$ \mathbb{P}(x \text{ is prime} | 1 \leq x \leq N) \approx \frac{1}{\log N} $$ by the Prime Number Theorem.

Choose $x,d \in \{1,\ldots,N\}$ at random among the $N^2$ choices and write $E_j$ for the event that $x+jd$ is prime. If the events $E_0, E_1, E_2$ were independent, we would expect that $$ \mathbb{P}(x,x+d,x+2d \text{ are all prime}) = \mathbb{P}(E_0 \cap E_1 \cap E_2) \approx \frac{1}{(\log N)^3}, $$ and so $$ \# \{x,d \in \{1,\ldots,N\} \, | \, x,x+d,x+2d \text{ are all prime} \} \approx \frac{N^2}{(\log N)^3}, $$ which is the correct result up to a constant factor.

Green says that the correct constant can be obtained by discarding the incorrect assumption of independence and taking account of the fact that the primes $> q$ fall only in those residue classes $a(\text{mod }q)$ with $a$ coprime to $q$. He gives no more details.

I've been trying to figure out how to do this, but haven't been successful.

Could someone please help me out or point me to a reference where it is done?


share|cite|improve this question

Very roughly speaking, the probability for a number $x$ to be divisible by a prime $p$ is $1/p$. We can't take this literally because it stops making sense when $p$ gets close to $\sqrt x$, but it will make more and more sense for more and more primes as $x$ increases. Thus, even though we can't calculate the probability of a number being prime as $\prod_p(1-\frac1p)$ (which would be zero), we can calculate corrections to the independence assumption as if we were correcting the factor $1-\frac1p$. If the product of the corrections from primes above some limit $q$ converges to $1$ as $q\to\infty$, we can expect the correction to be asymptotically correct, since the part of it that doesn't make sense will not matter asymptotically.

Now if $E_0$, $E_1$ and $E_2$ were independent, the contribution from a prime $p$ to the probability of the triple being prime would be $(1-\frac1p)^3$. To find the correction for $p\gt2$, we can consider the two cases where $d$ is or isn't divisible by $p$. If $d$ is divisible by $p$, which happens with probability $\frac1p$, then $x$, $x+d$ and $x+2d$ all have the same residue $\bmod p$, and this is non-zero with probability $1-\frac1p$; whereas if $d$ is not divisible by $p$, which happens with probability $1-\frac1p$, then $x$, $x+d$ and $x+2d$ all have different residues $\bmod p$, and the probability of none of them being zero is $1-\frac3p$.

Thus, in total, the probability of none of the three numbers being divisible by $p$ is


Thus the correction with respect to $(1-\frac1p)^3$ is


so we should expect a minus sign where you have a plus sign, and indeed the paper you cite has a minus sign.

The case $p=2$ has to be treated separately because there aren't three different residues $\bmod2$. In this case, $(1-\frac1p)^3$ is $\frac18$, whereas the correct probability is $\frac12\cdot\frac12=\frac14$, so the correction is $2$, and indeed the paper you cite has $2$ where you have $\frac32$.

share|cite|improve this answer

There are many conjectures in Number Theory with a constant factor given as that kind of product over primes, obtained by diddling with independence conjectures. You will find some of them, with explanations, by searching for Bateman Horn, and what you find should be applicable to the arithmetic progressions problem.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.