# 3-term arithmetic progressions of terms as frequent as primes

Let $\ p_1\ < p_2 < \ldots\$ be the sequence of all primes $\ (2\ 3\ 5\ \ldots)$.

Let $\ x_1 < x_2 < \ldots\$ be an arbitrary increasing sequence of positive integers such that $\ x_n\le p_n\$ for every $\ n=1\ 2\ldots\,$.

QUESTION: Does sequence $\ (x_1 < x_2 < \ldots)\$ contain a 3-term arithmetic progression (of not necessary three consecutive members)? Does there exist an infinite number of such 3-term arithmetic progressions?

Acknowledgement: The simple version $\ x_n\le p_n\$ of the assumption of this conjecture was provided by @zeb in a response to my equivalent original assumption which was clumsy and harder to read.

Reference: my MO-problem is related to a famous Klaus Roth's theorem.

Now I see from the Fedor's answer that this was indeed essentially only an MO-problem, and otherwise not essentially original.

• In general, there is no absolute need to specify a measure of frequency of a class of infinite sequences--it may be more elegant to provide that class with a specific auxiliary sequence instead which serves as a standard measure of frequency. – Włodzimierz Holsztyński Dec 8 '15 at 8:40
• Perhaps I don't understand, but what is wrong with the sequence $1,2,4,5,7,8,10,11,13,14,\dots$? Isn't this an example of the sort you need that does not contain 3 consecutive members in AP? – Nick Gill Dec 8 '15 at 8:55
• @NickGill, sorry, I had a nasty typo or something. I've fixed it. Now it should be better. – Włodzimierz Holsztyński Dec 8 '15 at 9:43
• Ah, yes, now it's better. I've suffered the curse of the typo many times... – Nick Gill Dec 8 '15 at 12:00

It is open. Best current results in the quantitative version of Roth's theorem belong to Sanders and allow to find 3-term arithmetic progression between something like $O(n/\log^{1-\varepsilon} n)$ numbers not exceeding $n$, for any given $\varepsilon>0$.

UPD: already not to Sanders, but to Bloom (see quid's comment), however the estimates are still weaker than for primes.

• The terms there are not consecutive, though. (Yet then I think this condition might better be dropped from the question.) Moreover, Bloom has an improvement on the result of Sanders but the general shape rests as you state (he saves $(\log \log n)^2$) see arxiv.org/abs/1405.5800v2 – user9072 Dec 8 '15 at 9:21
• @quid "The terms there are not consecutive, though." Sorry, my brain doesn't function properly (only too often). I've already fixed my mis-formulation. – Włodzimierz Holsztyński Dec 8 '15 at 9:48
• Fedor, thank you for your answer (and for interpreting my question in the intended way rather than according to my accidental mishandling it). I am not a number theory specialist (or anything :) ), and I never saw a similar result. Thus I feel good about my question. – Włodzimierz Holsztyński Dec 8 '15 at 9:54

Your condition seems to be more easily stated as $x_n \le p_n$, where $p_n$ is the $n$th prime. By König's Lemma, your first question is equivalent to asking whether there are arbitrarily long sequences which avoid a 3-AP, and if (as one ought to suspect) there aren't, we will be able to confirm this with a finite case analysis. We can assume without loss of generality that $x_1 = 1$.

primes:
2,3,5,7,11,13,17,19,23,29,31,37,41,43
maximal sequences:
1,2,4,5,10,11,13,14,X
1,2,4,5,10,11,14,X
1,2,4,5,10,12,13,17,X
1,2,4,5,10,12,17,X
1,2,4,5,10,13,14,17,X
1,2,4,5,10,13,17,X
1,2,4,5,11,12,14,15,X
1,2,4,5,11,12,14,X
1,2,4,5,11,12,15,16,X
1,2,4,5,11,12,16,X
1,2,4,5,11,13,14,16,X
1,2,4,5,11,13,14,19,X
1,2,4,5,11,13,16,X
1,2,4,7, 8,11,16,17,19,29,X
1,2,4,7, 8,11,16,17,22,29,X
1,2,4,7, 8,11,16,19,23,26,X
1,2,4,7, 8,11,16,19,23,29,X
1,2,4,7, 8,11,17,19,22,24,28,35,38,X
1,2,4,7, 8,11,17,19,22,28,29,35,38,X
1,2,4,7, 8,11,17,19,22,29,X
1,2,4,7, 9,X
1,2,4,7,11,X
1,2,5,6,X
1,2,5,7,10,11,14,16,20,28,X
1,2,5,7,10,11,16,18,23,24,X
1,2,5,7,11,X
1,3,4,6,10,12,13,15,X
1,3,4,6,10,12,15,X
1,3,4,6,10,13,15,18,X


So in fact there are no 3-AP free sequences $x_1, ..., x_{14}$ such that for each $n$ we have $x_n \le p_n$, which answers your first question. Your second question is an open problem.

• Nice! Would you mind if I replaced my condition by your simplified (but equivalent) version? (It goes without saying that I will credit you for your simplification). – Włodzimierz Holsztyński Dec 9 '15 at 2:54
• Of course I don't mind. – zeb Dec 9 '15 at 2:57