5
$\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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Dec 8, 2015 at 8:40

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Dec 8, 2015 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
    Commented Dec 8, 2015 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
    Commented Dec 8, 2015 at 9:54
5
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Dec 9, 2015 at 2:54
  • 1
    $\begingroup$ Of course I don't mind. $\endgroup$
    – zeb
    Commented Dec 9, 2015 at 2:57
2
$\begingroup$

Meanwhile, this question has been answered in the positive. -- See

Thomas F. Bloom, Olof Sisask: Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .