7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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? $\endgroup$
    – Stefan Geschke
    Sep 27, 2011 at 6:20
  • 15
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Sep 27, 2011 at 7:55
  • $\begingroup$ 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? $\endgroup$
    – Everett Piper
    Oct 1, 2011 at 20:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.