4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Włodzimierz Holsztyński Dec 8 '15 at 8:40
  • 4
    $\begingroup$ 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? $\endgroup$ – Nick Gill Dec 8 '15 at 8:55
  • $\begingroup$ @NickGill, sorry, I had a nasty typo or something. I've fixed it. Now it should be better. $\endgroup$ – Włodzimierz Holsztyński Dec 8 '15 at 9:43
  • 1
    $\begingroup$ Ah, yes, now it's better. I've suffered the curse of the typo many times... $\endgroup$ – Nick Gill Dec 8 '15 at 12:00
4
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ 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 $\endgroup$ – user9072 Dec 8 '15 at 9:21
  • $\begingroup$ @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. $\endgroup$ – Włodzimierz Holsztyński Dec 8 '15 at 9:48
  • $\begingroup$ 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. $\endgroup$ – Włodzimierz Holsztyński Dec 8 '15 at 9:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Włodzimierz Holsztyński Dec 9 '15 at 2:54
  • 1
    $\begingroup$ Of course I don't mind. $\endgroup$ – zeb Dec 9 '15 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.