MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

The following result was proved by Tao and Green: For every $k$, there exist infinitely many arithmetic progressions of length $k$ contained in the sequence of prime numbers.

I think this is an interesting result from a recursion-theoretic point-of-view since it suggests that there is some linear kind of bound on the growth rate of any recursive function enumerating "big" subsets of the primes. (I'll get back to this point later.)

I have a different, though I think related, question:

Suppose we index the primes according to their natural order (i.e., $p_1 =2, p_2 =3, p_3=5$, etc.) and then consider the primes as the disjoint union of two infinite sets $A_1$ and $B_1$. $A_1$ contains only those primes that have prime index, and $B_1$ contains those primes which have composite index (including 1). For example, $A_1=\{3,5,11,17, \dots \}$ and $B_1=\{2,7,13,19,\dots\}$.

If I'm not mistaken, $B_1$ (or any finite truncation of it) has finite upper density (relative to the set of primes), hence by the Tao-Green theorem, $B_1$ contains for every $k$ infinitely many a.p.s of length $k$. (Is this correct?)

However, $A_1$ does not have positive upper density. Nevertheless, could it be the case that

$(*)$ for every $k$ there are infinitely many a.p.s of length $k$ contained in $A_1$?

What would happen if we re-indexed all the members of $A_1$ according to their order and defined the sets $A_{1,1}$ (containing those elements of $A_1$ with prime index) and $A_{1,2}$ (containing those elements with composite index incl. 1). (We could also do the same for for $B_1$...)

$(*_2)$ Does an analogue for $(*)$ hold in this 1-step iteration?

Iterating the process above n times:

$(*_{n+1})$ Does an analogue for $(*)$ hold in this $n$-step iteration?

How far can this kind of construction go?

share|cite|improve this question
Yes, the set of primes with composite index has positive density in the set of all primes. Isn't this simply because the set of primes has density zero in the integers? – Stefan Geschke Sep 27 '11 at 6:20
I'm certain $A_1$ does contain long progressions, but proving it using the Tao-Green technique might not be so easy. In fact this set has density roughly $1/\log^2 N$ in the integers, and any such set is conjectured to have arbitrarily long progressions. – Ben Green Sep 27 '11 at 7:55
Is it the case, then, that $A_k$ has density roughly $1/\log^k N$ as well? Does the conjecture you're referring to cover $k>2$? My original interest in this problem was whether there could be a $k$ such that $\Sigma_{a\in A_k} 1/a$ could converge. I later learned of the conjecture of Erd\"os and the Green-Tao result. Do either of you have any insight into my original problem? – Everett Piper Oct 1 '11 at 20:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.