Every 33-length subsequence of $1,2,\dotsc,122$ contains a three term arithmetic progression

Question

Is it possible to prove that every 33-length subsequence of the sequence $1,2,3,\dotsc,122$ contains a three term arithmetic progression?

Maybe I should post it on mathoverflow

Answer 1

Let me add some comments to Alexander Walker's nice answer:

The problem is first studied in the paper

Paul Erdős, and Paul Turán. On some sequences of integers, J. London Math. Soc., 11 (4), (1936), 261--264. MR1574918, Zentralblatt JFM 62.1126.01.

There $r(n)$ is defined as the length of the largest sequence of elements from $\{1,\dots,n\}$ with no three terms in arithmetic progression. A conjecture by Szekeres is mentioned that $$r\left(\frac12(3^k+1)\right)=2^k.$$ This can be verified more or less directly for $k\le 4$. Note that for $k=5$ it gives the result you asked for. The paper mentions that $\displaystyle r\left(\frac12(3^k+1)\right)\ge 2^k$ is easy to see: Given $k$, let $A$ be the set of integers of the form $u+1$ with $\displaystyle 0\le u\le \frac12(3^k-1)$ and such that the ternary expansion of $u$ has no twos. We then see that $A$ has size $2^k$ and no three terms are in arithmetic progression. For $k=5$, so $N=122$, the resulting set $A$ has size $32$ and equals $$\begin{array}{c}\{1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41,82,83,85,86,91,92,94,95,109,110,\\ 112,113,118,119,121,122\}.\end{array} $$ This means that $33$ cannot be replaced with a smaller number.

The paper (also mentioned in the comments)

Janusz Dybizbański. Sequences Containing No 3-Term Arithmetic Progressions, Electron. J. Combin., 19 (2), (2012), paper 15, 5 pp. MR2928630,

establishes a result that for the first time verifies that Szekeres conjecture holds for $k=5$. The argument uses a computer search, and no computer-free combinatorial approach seems known at the moment.

As Walker pointed out in a comment, it should be remarked that Szekeres's conjecture is actually false. The point is that we now have a good understanding for the asymptotic behavior of the function $r$, that clashes with what the conjecture predicts. Specifically, we know that for any $\epsilon>0$, there are constants $c,C>0$ such that for $N$ large enough, we have $$ cN^{1-\epsilon}<r(N)<CN^{1-\epsilon}. $$ For example, in

Tom Sanders. On Roth's theorem on progressions, Ann. of Math. (2), 174 (1), (2011), 619-636. MR2811612 (2012f:11019),

it is shown that for some $C$, $$r(N)<C\frac{(\log\log N)^5}{\log N}N,$$ while (more relevant for our current discussion), in

Felix Adalbert Behrend. On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U. S. A., 32, (1946), 331–332. MR0018694 (8,317d),

it is shown that for some $c$, $$ r(N)>N^{1-\frac{c}{\sqrt{\log N}}}. $$ For $N$ large, this inequality clashes with the value predicted by Szekeres conjecture, that gives that $r(N)\le C'N^{\log_32}$ for $N$ of the form $\displaystyle\frac12(3^k+1)$.

(Actually, the first disproof of Szekeres's conjecture is much older than the above suggests: In

Raphaël Salem, and Donald C. Spencer. On sets of integers which contain no three terms in arithmetical progression, Proc. Nat. Acad. Sci. U.S.A., 28 (12), (1942), 561–563. MR0007405 (4,131e),

it is shown that for any $\epsilon>0$, $$ r(n)\ge n^{1-\frac{1+\epsilon}{\log\log n}}$$ for all $n$ large enough.)

As Walker further points out in the comments, Jaroslaw Wroblewski has organized a search for sets without $3$-term arithmetic progressions, which in particular has found an example of length $128$ in $\{1,2,\dots,1092\}$, hence refuting Szekeres conjecture for $k=7$. This, and the other results of their search, can be seen on this page (search for $a(128)$). It appears that whether the conjecture holds for $k=6$ is still open.

For a nice survey of the known results on sets without three term arithmetic progressions, see

William Gasarch, James Glenn, and Clyde P. Kruskal. Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey. II, 2010, preprint.

Answer 2

This is hardly an answer, but I'd like to direct you to OEIS A065825.

This sequence, beginning

$$S_3=\{1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, 121, 122, 137, 145, 150, 157, 163, 165, 169, 174, 194\}$$ gives for its $n$th term the minimum $k$ such that $[1,k]$ that has an $n$-term subset that avoids $3$-term arithmetic progressions (typically called a $3$-free set). Since the $32$ term of this sequence is $122$ and the $33$rd is $137$, it follows that no $33$ term sequence in $[1,122]$ is $3$-free. Not much is known about the growth of this sequence, and I would not be surprised if the sequence above had been found by brute force calculations.

It was at one point conjectured that the sequence $G_3=\{1,2,4,5,10,\ldots\}$ (i.e. the sequence obtained by always appending the smallest element that retains $3$-freeness) would yield competitive bounds to $S_3$ infinitely often. This was been disproved by work of F. Behrend in 1946, who crafted examples of $3$-free sets of length $n$ that fit in the interval $n^{1+\epsilon}$ (for fixed $\epsilon >0$ and sufficiently large $n$). In contrast, we can prove that the "greedy" version of this packing requires space like $$n^{\log_2 3},$$ by recognizing it as the set of integers whose base $3$ representation omits the digit $2$, increased by $1$.