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

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).

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer
Ok, very clear, thanks for answering. – Thomas Sauvaget Oct 24 '09 at 9:24

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.