This is essentially asking for good bounds on $r_k(N)$, the size of the largest subset of $\{1,\ldots,N\}$ without a non-trivial $k$-term arithmetic progression. For example, a bound like \[r_k(N) \ll_k \frac{N}{(\log N)(\log\log N)^2}\] would be sufficient.

Even the case $k=3$ is non-trivial, but was proved by Bloom and Sisask [BlSi20]. Much better bounds for $r_3(N)$ were subsequently proved by Kelley and Meka [KeMe23]. Green and Tao [GrTa17] proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. Gowers [Go01] proved \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant depending on $k$. The current best bounds for general $k$ are due to Leng, Sah, and Sawhney [LSS24], who show that \[r_k(N) \ll \frac{N}{\exp((\log\log N)^{c_k})}\] for some constant $c_k>0$ depending on $k$.

Curiously, Erdős [Er83c] thought this conjecture was the 'only way to approach' the conjecture that there are arbitrarily long arithmetic progressions of prime numbers, now a theorem due to Green and Tao [GrTa08] (see [219]).

In [Er81] Erdős makes the stronger conjecture that \[r_k(N) \ll_C\frac{N}{(\log N)^C}\] for every $C>0$ (now known for $k=3$ due to Kelley and Meka [KeMe23]) - see [140].

See also [139] and [142].

A conjecture of Erdős and Turán. Proved by Szemerédi [Sz74]. The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$ (with further slight improvements in [BlSi23]), Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$.

See also [3].

Proved by Kelley and Meka [KeMe23]. In [ErGr80] and [Er81] it is conjectured that this holds for every $k$-term arithmetic progression.

See also [3].

Green and Tao [GrTa08] have proved that there must always exist some $k$ primes in arithmetic progression, but these need not be consecutive. Erdős called this conjecture 'completely hopeless at present'.

The existence of such progressions for small $k$ has been verified for $k\leq 10$, see the Wikipedia page. It is open, even for $k=3$, whether there are infinitely many such progressions.

See also [219].

Erdős remarked this is 'probably unattackable at present'. In [Er97c] Erdős offered \$1000, but given that he elsewhere offered \$5000 just for (essentially) showing that $r_k(N)=o_k(N/\log N)$, that value seems odd. In [Er81] he offers \$10000, stating it is 'probably enormously difficult'.

The best known upper bounds for $r_k(N)$ are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Leng, Sah, and Sawhney [LSS24] for $k\geq 5$. An asymptotic formula is still far out of reach, even for $k=3$.

See also [3] and [139].

Investigated by Erdős and Freud. This has been discussed on MathOverflow, where LeechLattice shows \[h(N) \ll N^{2/3}.\] The observation of Zachary Hunter in that question coupled with the bounds of Kelley-Meka [KeMe23] imply that \[h(N) \gg \exp(c(\log N)^{1/12})\] for some $c>0$.

Gerver [Ge77] has proved \[f(k) \geq (1+o(1))k\log k.\] It is trivial that \[\frac{f(k)}{\log W(k)}\geq \frac{1}{2},\] but improving the right-hand side to any constant $>1/2$ is open.

Spencer [Sp73] has proved that if $k=2^tm$ with $m$ odd then \[N(k,1)=2^t(k-1)+1.\] Erdős and Graham write that 'no decent bound' is known even for $N(k,2)$. Probabilistic methods imply that, for every fixed constant $c>0$, we have $N(k,ck)>C_c^k$ for some $C_c>1$.

Cantor, Erdős, Schreiber, and Straus [Er66] proved that $h(d)\ll d!$ is possible. Van der Waerden's theorem implies that $h(d)\to \infty$. Beck [Be17] has shown that $h(d) \leq d^{8+\epsilon}$ is possible for every $\epsilon>0$. Roth's famous discrepancy lower bound [Ro64] implies that $h(d)\gg d^{1/2}$.

Erdős remarks the upper bound $o(N^2)$ is certainly false for $\ell >\epsilon \log N$. The answer is yes: Fox and Pohoata [FoPo20] have shown that, for all fixed $1\leq k<\ell$, \[F_k(N,\ell)=N^{2-o(1)}\] and in fact \[F_{k}(N,\ell) \leq \frac{N^2}{(\log\log N)^{C_\ell}}\] where $C_\ell>0$ is some constant. In fact, they show that, if $r_\ell(N)$ is the size of the largest subset of $\{1,\ldots,N\}$ without an $\ell$-term arithmetic progression then there exists some absolute constant $c>0$ such that \[\left(c \frac{r_\ell(N)}{N}\right)^{2(k-1)}N^2 < F_k(N,\ell) <\left(\frac{r_\ell(N)}{N}\right)^{O(1)}N^2.\] Any improved bounds for Szemerédi's theorem (see [139]) therefore yield improved bounds for $F_k(N,\ell)$. In particular, the bounds of Leng, Sah, and Sawhney [LSS24] imply \[F_k(N,\ell) \leq \frac{N^2}{\exp((\log\log N)^{c_\ell})}\] for some constant $c_\ell>0$.

This type of problem belongs to 'canonical' Ramsey theory. The existence of $H(k)$ follows from Szemerédi's theorem, and it is easy to show that $H(k)^{1/k}\to\infty$.

This is true for $d\leq 3$ and false for $d\geq 4$.

This problem is equivalent to one on 'abelian squares' (see [231]). In particular $A$ can be interpreted as an infinite string over an alphabet with $d$ letters (each letter describining which of the $d$ possible steps is taken at each point). An abelian square in a string $s$ is a pair of consecutive blocks $x$ and $y$ appearing in $s$ such that $y$ is a permutation of $x$. The connection comes from the observation that $p,q,r\in A\subset \mathbb{R}^d$ form a three-term arithmetic progression if and only if the string corresponding to the steps from $p$ to $q$ is a permutation of the string corresponding to the steps from $q$ to $r$.

This problem is therefore equivalent to asking for which $d$ there exists an infinite string over $\{1,\ldots,d\}$ with no abelian squares. It is easy to check that in fact any finite string of length $7$ over $\{1,2,3\}$ contains an abelian square.

An infinite string without abelian squares was constructed when $d=4$ by Keränen [Ke92]. We refer to a recent survey by Fici and Puzynina [FiPu23] for more background and related results, and a blog post by Renan for an entertaining and educational discussion.

The answer is no, even for $k=3$, as shown by Ardal, Brown, and Jungić [ABJ11].

See also [195] and [196].

Geneson [Ge19] proved that $k\leq 5$. Adenwalla [Ad22] proved that $k\leq 4$.

See also [194] and [196].

Davis, Entringer, Graham, and Simmons [DEGS77] have shown that there must exist a monotone 3-term arithmetic progression and need not contain a 5-term arithmetic progression.

See also [194] and [195].

If three sets are allowed then this is possible.

The answer is yes, as shown by Baumgartner [Ba75].

The answer is no, as shown by Baumgartner [Ba75] (whose construction uses the axiom of choice).

It follows from the prime number theorem that such a progression has length $\leq(1+o(1))\log N$.

First asked and investigated by Riddell [Ri69]. It is trivial that $G_k(N)\leq R_k(N)$, and it is possible that $G_k(N) <R_k(N)$ (for example with $k=3$ and $N=14$). Komlós, Sulyok, and Szemerédi [KSS75] have shown that $R_k(N) \ll_k G_k(N)$.

The answer is yes, proved by Green and Tao [GrTa08]. The stronger claim that there are arbitrarily long arithmetic progressions of consecutive primes is still open.

See also [3] and [141].

It is easy to see that $A(1)$ is the set of integers which have no 2 in their base 3 expansion. Odlyzko and Stanley have found similar characterisations are known for $A(3^k)$ and $A(2\cdot 3^k)$ for any $k\geq 0$, see [OdSt78], and conjectured in general that such a sequence always eventually either satisfies \[a_k\asymp k^{\log_23}\] or \[a_k \asymp \frac{k^2}{\log k}.\] There is no known sequence which satisfies the second growth rate, but Lindhurst [Li90] gives data which suggests that $A(4)$ has such growth ($A(4)$ is given as A005487 in the OEIS).

Moy [Mo11] has proved that, for all such sequences, for all $\epsilon>0$, $a_k\leq (\frac{1}{2}+\epsilon)k^2$ for all sufficiently large $k$.

In general, sequences which begin with some initial segment and thereafter are continued in a greedy fashion to avoid three-term arithmetic progressions are known as Stanley sequences.

Simonovits and Sós [SiSo81] have shown that $t\ll N^2$. It is possible that the maximal $t$ is achieved when we take the $A_i$ to be all arithmetic progressions in $\{1,\ldots,N\}$ containing some fixed element.

If we drop the non-empty requirement then Simonovits, Sós, and Graham [SiSoGr80] have shown that \[t\leq \binom{N}{3}+\binom{N}{2}+\binom{N}{1}+1\] and this is best possible.