Question

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

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.