Hello, the Green-Tao theorem says infinitely many k-term Arithmetic Progressions exist for any integer k.

My question is: can we actually partition the primes into 3-term APs only (or is there a simple reason why it cannot be expected) ? And if it were possible, then what would it mean for the set of primes ?

For example fix a large integer (say M=10,000) then take the primes (except 2): 3, 5, 7, 11, 13... and remove the longest possible AP with common difference less than M as you go along. It provides the partition: 3 5 7 -- 11 17 23 29 -- 13 37 61 -- 19 31 43 -- 41 47 53 59 -- 67 73 79 -- 71 89 107 -- 83 131 179 227 -- 97 103 109 -- 101 137 173 -- ... Numerical data for the first 10,000 primes with that M shows that the average length of APs so defined is 3.2 (which is thus quite close to 3, so at least numerically there exists partitions where 3-terms APs cover a large fraction of the primes, hence the question).


1 Answer 1


Using the greedy algorithm, this would follow if for any fixed prime q, there exist infinitely prime "pairs" of the form p and 2p-q. This follows from standard (difficult) conjectures if q is odd (for example, the case q = -1 corresponds to "Sophie Germaine Primes"). On the other hand, it would be an implication of such a partition that for each odd prime q, there either:

(i) exists at least one prime pair (p,2p-q), (ii) 2q is the sum of two primes, (iii) exists at least one prime pair (p,q-2p).

Almost all proofs showing that there exist primes of a certain form also prove that there are infinitely many such primes. Thus, I suspect, one could not prove this result without also proving the difficult conjectures alluded to above.

  • $\begingroup$ Ok, very clear, thanks for answering. $\endgroup$ Oct 24, 2009 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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