MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

in 1923 Hardy and Littlewood proposed the conjecture $\pi (m+n) \leq \pi (m) + \pi (n)$. Is there any progress towards solving this conjecture?

share|cite|improve this question
It's known that this contradicts the general prime $k$-tuple conjecture and many number theorists find the $k$-tuple conjecture the more plausible. – Robin Chapman Jul 5 '10 at 7:08
You mean Littlewood not Wright (who was born 1906): see… – Charles Matthews Jul 5 '10 at 11:11
charles:thank you for this comment – Hashem sazegar Jul 5 '10 at 12:49
T, about 30 years ago I went to a philosophy of math talk, where the speaker was interested in what it says about mathematics, that our instincts are so good. He pointed to our uncanny ability to make conjectures that turn out to be true. I told him about the Hensley-Richards work showing that the $\pi(m+n)$ conjecture and the prime $k$-tuple conjecture couldn't both be true. His immediate reply was that the $\pi(m+n)$ conjecture must be correct! But he doesn't count as an answer to your question, as he was a philosopher of math, not a number theorist. – Gerry Myerson Jul 6 '10 at 1:43
Is it plausible that there are only finitely many counterexamples with $n\ge m\ge cn$ and for any constant $c>0$? – Brendan McKay Aug 5 '13 at 16:50

As Robin Chapman points out, this conjecture is probably false. Nonetheless, similar results have been obtained, usually using sieve theory. Montgomery and Vaughan have proven $$\pi(x+y)\leq\pi(x)+\frac{2y}{\log y}.$$

Combined with a standard Chebyshev estimate, this gives $$\pi(x+y)\leq\pi(x)+16\pi(y),$$ say (for all $x,y\geq2$). Erdos conjectured that $$\pi(x+y)\leq\pi(x)+(1+o_{y\to\infty}(1))\frac{y}{\log y}$$ which, combined with the prime number theorem, would give $$\pi(x+y)\leq\pi(x)+(1+o_{y\to\infty}(1))\pi(y).$$

This may be as close as possible, and some (possibly including Selberg, see comments) believe even this to be false, and the constant 2 in the first result mentioned is the best possible.

share|cite|improve this answer
Where does Selberg state his belief that the last inequality is false? – Mark Lewko Aug 5 '13 at 19:37
Good question. Searching my memory, I think I got that impression, and indeed the content of this answer (including the Erdos conjecture), from 'Lectures on sieves' by Heath-Brown ( The relevant quote is "Erdos apparently believed that the constant may be taken as 1, while Selberg is reputed to have suggested that no constant below is admissible.", without references. – Thomas Bloom Aug 5 '13 at 20:14

The historical highlights for this conjecture are:

1923 : Hardy and Littlewood's classic paper, Partitio Numerorum III, elevates an obvious question to a conjecture. More precisely, H & L note that $\pi(x+y) \leq \pi(x) + \pi(y)$ (for large enough $y$) is "forcibly suggested" by the data for $x,y \leq 200$; prove some upper and lower bounds on the (lim sup) densest packing of primes in an interval of length $x$; calculate the densest packing for $x=35, 59$ and $97$; and finish with the remark that "beyond $x=97$ it would seem that [the densest packing] falls further below $\pi(x)$, at least within any range in which calculation is practicable". These speculative comments from the paper become known as a conjecture.

1973 : Ian Richards and his doctoral student Douglas Hensley explode the conjecture by showing that it contradicts the (much more plausible) prime k-tuplets conjecture

2004 to today: Green-Tao theorem and later developments lead to proofs of statements similar to the k-tuplets conjecture, giving hope that "moral certainty that H-L 1923 is false" can be replaced by "a proof that k-tuplets conjecture is true (and HL1923 is therefore false)".

The $\pi(x+y)$ conjecture never had much evidence for it. Hensley and Richards set out to disprove it by a computer calculation. They ended up proving the existence of subsets $D$ of {1,2,...,$n$} denser than the first $n$ primes ($|D| > \pi(n)$) and with no congruence obstruction to $x + D$ being a set of primes for infinitely many $x$ (for no prime $p$ do the elements of $D$ fill all congruence classes modulo $p$). Sets free of congruence obstructions are called "admissible prime constellations" and the other more credible conjecture of Hardy and Littlewood is that for any admissible constellation, infinitely many copies exist in the primes. For $D$ this implies that for infinitely many $x$,

$\pi(x+|D|) - \pi(x) \geq |D| > \pi (D)$.

The optimal example (according to ) is with $n = 3159, |D| = 447 > \pi(n) = 446$, so conjecturally,

$\pi(x+3159) > \pi(x) + \pi(3159)$ infinitely often, with the number of examples less than $N$ being of order $cN/(\log N)^{447}$

Hensley and Richards' technique for constructing dense constellations of primes is to take all the primes and their negatives in a symmetrical interval $[-K,K]$, and delete enough of the first few primes to prevent congruence obstructions. They proved that this construction is, infinitely often, denser than $\pi(2K+1)$.

share|cite|improve this answer
Does language like "elevate ... obvious" and "explode" indicate some hostility to Hardy or Littlewood? – Charles Stewart Jul 6 '10 at 8:19
I added more on Hardy and Littlewood's contribution. The question is correctly described as being obvious and lacking evidence, it was elevated (intentionally or not) to conjecture status as a result of Hardy and Littlewood's paper, and any plausibility of that conjecture was shattered by the Hensley and Richards results. "Exploded" is a better descriptor than "refuted" or "resolved", since they did not fully disprove the conjecture, but reduced its falsity to a well-accepted family of hypotheses on the distribution of primes. – T.. Jul 6 '10 at 20:00

As has already been pointed out, Montgomery and Vaughn have proven that $$\pi(x+y) \leq \pi(x)+ 2 \frac{y}{\log(y)} $$ from which, with some care, one can derive that: $\pi(x+y) \leq \pi(x)+ 2\pi(y)$ (this is worked out in the original paper of Montgomery and Vaughn).

The natural question is thus to further refine the constant $2$. There seems to be no unrestricted result on this problem, however Friedlander and Iwaniec (in their recent book on sieve theory) have shown that

$$\pi(x+y) \leq \pi(x) + (2-\delta) \frac{y} {\log(y)} $$

holds for $x^{\theta} < y < x$ where $\delta:= \delta(\theta)$ is a function of $\theta$. In other words, one can improve the constant $2$ as long as $y$ isn't too small compared to $x$.

Recently Bourgain and Garaev have refined this result to give the quantitative relationship of $\delta \sim \theta^2$.

share|cite|improve this answer

Some partial results, as well as the proof of the claim mentioned by Chapman are given in the book The Little Book of Bigger Primes by Ribenboim.

share|cite|improve this answer

Zhang's work on bounded gaps between primes connects with this conjecture and there is a candidate counterexample. See

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.