The π(x) + π(y) ≥ π(x + y) Conjecture

As usually, we denote by ℤ the the integers, by ℕ the positive integers and by ℙ the prime numbers. Next, denote for each x ∈ ℕ by π(x) the number of primes which are ≤ x. In 1914 G. Hardy & J. Littlewood conjectured that

∀x, y ∈ ℕ\{1} : π(x) + π(y) ≥ π(x + y) .

In 1973 D. Hensley & I. Richards [3] showed that this conjecture contradicts another famous conjecture, the so called “n-tuple prime conjecture” also stated by Hardy & Littlewood. Call a subset S ⊂ ℤ admissible iff ∀ p ∈ ℙ ∃ r ∈ ℤ ∀ s ∈ S : s ≢ r (mod p). Then the n-tuple prime conjecture is equivalent to the statement, that for each admissible set S there exist infinite many subintervals I_{k} ⊂ ℙ which are translated copies of S — S can be regarded as an arbitrary translated n-tuple of prime numbers. Naturally, denote the length of any set S ⊂ ℤ to be 0 if S is the empty set and otherwise to be max S − min S + 1. Lastly define ∀ x ∈ ℕ ρ̄(x) = max_{S⊂[1,x]} {|S| : S is admissible }, which was introduced by A.

Schinzel & W. Sierpiński in [1].

Since the work of Hensley & Richards, it is highly probable that the π(x)−conjecture is false, which means there exists a pair (x, y) — indeed infinte many pairs (x, y) — such that π(x) + π(y) < π(x + y) for this pair (x, y). Assuming the n-tuple prime conjecture, Hensley & Richards proved the existence of infinite many pairs (x, y) for which π(x) + π(y) < π(x + y) holds. Therefore one is interested in geting such an explicit counterexample pair (x, y). Two questions arise naturally: What is the minimal x+y such that (x, y) is a counter-example of the original conjecture and what is the minimal x, call it x_{min}, such there exists a counter-example (x_{min}, y)? Transforming the inequality in question to π(x) ≥ π(x + y) − π(y), it is obviously, that a counter-example (x, y) charcterizes an interval of length x, namely [y + 1, y + x], which contains more primes than the interval [1, x].

Together with W. Stenberg, Hensley & Richards showed the existence of an admissible set of length 20000 of the integers which contains more than π(20000) numbers and must occur as a translated prime interval according to the n-tuple prime conjecture. Using their insights, in 1979 T. Vehka constructed an admissible set of length 11763 which has 1412 > 1409 = π(11763) elements[4]. In the following years the upper bound of the length x_{min} of a shortest interval was decreased down to 4911 until the year 1999. An admissible set can be described inambiguously by an empty congruence class for each prime. For the last mentioned value 4911, a subset of the interval [0, 4910] containing 656 > π(4911) = 655 elements was constructed by A. Flammenkamp and is defined by the list of the remainders for certain prime numbers in Table 1. Here for each prime p which effectively sieve out elements of the interval [0, 4910] its remainder r for the corresponding congruence class together with the number of further cancled numbers c and the current size s of the set of the interval is given:

\begin{matrix}r & p & c & s \\ 1 & 2 & 2455 & 2456 \\ 1 & 3 & 818 & 1638 \\ 3 & 5 & 328 & 1310 \\ 1 & 7 & 186 & 1124 \\ 9 & 11 & 103 & 1021 \\ 5 & 13 & 80 & 941 \\ 15 & 17 & 58 & 883 \\ 3 & 19 & 48 & 835 \\ 19 & 23 & 36 & 799 \\ 11 & 29 & 24 & 775 \\ 28 & 31 & 21 & 754 \\ 21 & 37 & 14 & 740 \\ 32 & 41 & 10 & 730 \\ 18 & 43 & 8 & 722 \end{matrix}  \begin{matrix}r & p & c & s \\ 15 & 47 & 6 & 716 \\ 43 & 53 & 3 & 713 \\ 3 & 59 & 3 & 710 \\ 57 & 61 & 3 & 707 \\ 47 & 67 & 3 & 704 \\ 70 & 71 & 3 & 701 \\ 60 & 73 & 3 & 698 \\ 78 & 79 & 3 & 695 \\ 47 & 83 & 3 & 692 \\ 1 & 89 & 3 & 689 \\ 79 & 97 & 3 & 686 \\ 53 & 101 & 3 & 683 \\ 46 & 103 & 3 & 680 \\ 44 & 107 & 3 & 677 \end{matrix}  \begin{matrix}r & p & c & s \\ 4 & 109 & 3 & 674 \\ 14 & 113 & 3 & 671 \\ 100 & 127 & 2 & 669 \\ 47 & 131 & 2 & 667 \\ 51 & 137 & 1 & 666 \\ 68 & 139 & 1 & 665 \\ 121 & 149 & 1 & 664 \\ 25 & 151 & 1 & 663 \\ 38 & 157 & 1 & 662 \\ 48 & 163 & 2 & 660 \\ 103 & 167 & 1 & 659 \\ 5 & 173 & 1 & 658 \\ 71 & 179 & 1 & 657 \\ 47 & 191 & 1 & 656 \end{matrix}

Table 1. Remainders for the sieving primes for the interval [0, 4911[.

On the other hand, a lower limit on x_{min} for any counter-example (x, y) to the conjecture in question, can be constructed without asuming the ntuple prime conjecture. This is simple done, by proving that each interval of length x having more than π(x) elements must cover all congruence classes for a certain prime, i.e. can never be a translated subinterval of the primes. Using this construction it was already shown by J. Selfridge before 1970, that x_{min} > 500 and later by R. Silverman that x_{min} > 714. Meanwhile A. Flammenkamp has shown that x_{min} > 1700 by intensive computations.

Figure 1. The function π(x) − ρ̄(x) for x < 1000.

last modified: 1999-06-01

References

[1] A. Schinzel & W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4 (1958), 185–208.

[2] A. Schinzel, Remarks on the paper “Sur certaines hypothèses concernant les nombres premiers”, Acta Arithmetica 7 (1961), 1–8.

[3] D. Hensly & I. Richards, Primes in intervals, Acta Arithmetica 25 (1974), 375–391.

[4] T. Vehka & I. Richards, Explicit construction of an admissible set for the conjecture that sometimes π(x + y) > π(y) + π(x), Notices Am. Math. Soc. 26 (1979), A-453.