8 solved out of 23 shown (show only solved or open)
OPEN - $5000 If$A\subseteq \mathbb{N}$has$\sum_{n\in A}\frac{1}{n}=\infty$then must$A$contain arbitrarily long arithmetic progressions? 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]. 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]. SOLVED -$1000
Let $r_k(N)$ be the size of the largest subset of $\{1,\ldots,N\}$ which does not contain a non-trivial $k$-term arithmetic progression. Prove that $r_k(N)=o(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$.

SOLVED - $500 Let$r_3(N)$be the size of the largest subset of$\{1,\ldots,N\}$which does not contain a non-trivial$3$-term arithmetic progression. Prove that$r_3(N)\ll N/(\log N)^C$for every$C>0$. 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]. OPEN Let$k\geq 3$. Are there$k$consecutive primes in arithmetic progression? 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'. OPEN -$10000
Let $r_k(N)$ be the largest possible size of a subset of $\{1,\ldots,N\}$ that does not contain any non-trivial $k$-term arithmetic progression. Prove an asymptotic formula for $r_k(N)$.
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]. Additional thanks to: Zach Hunter OPEN Let$h(N)$be the smallest$k$such that$\{1,\ldots,N\}$can be coloured with$k$colours so that every four-term arithmetic progression must contain at least three distinct colours. Estimate$h(N)$. 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$. Additional thanks to: Zachary Hunter OPEN Let$k\geq 3$and$f(k)$be the supremum of$\sum_{n\in A}\frac{1}{n}$as$A$ranges over all sets of positive integers which do not contain a$k$-term arithmetic progression. Estimate$f(k)$. Is $\lim_{k\to \infty}\frac{f(k)}{\log W(k)}=\infty$ where$W(k)$is the van der Waerden number? 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. OPEN Let$N(k,\ell)$be the minimal$N$such that for any$f:\{1,\ldots,N\}\to\{-1,1\}$there must exist a$k$-term arithmetic progression$P$such that $\left\lvert \sum_{n\in P}f(n)\right\rvert> \ell.$ Find good upper bounds for$N(k,\ell)$. Is it true that for any$c>0$there exists some$C>1$such that $N(k,ck)\leq C^k?$ What about $N(k,1)\leq C^k$ or $N(k,\sqrt{k})\leq C^k?$ No decent bound is known even for$N(k,1)$. Probabilistic methods imply that, for every fixed constant$c>0$, we have$N(k,ck)>C_c^k$for some$C_c>1$. OPEN Find the smallest$h(d)$such that the following holds. There exists a function$f:\mathbb{N}\to\{-1,1\}$such that, for every$d\geq 1$, $\max_{P_d}\left\lvert \sum_{n\in P_d}f(n)\right\rvert\leq h(d),$ where$P_d$ranges over all finite arithmetic progressions with common difference$d$. 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}$. SOLVED Let$1\leq k<\ell$be integers and define$F_k(N,\ell)$to be minimal such that every set$A\subset \mathbb{N}$of size$N$which contains at least$F_k(N,\ell)$many$k$-term arithmetic progressions must contain an$\ell$-term arithmetic progression. Find good upper bounds for$F_k(N,\ell)$. Is it true that $F_3(N,4)=o(N^2)?$ Is it true that for every$\ell>3$$\lim_{N\to \infty}\frac{\log F_3(N,\ell)}{\log N}=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. OPEN Let$H(k)$be the smallest$N$such that in any finite colouring of$\{1,\ldots,N\}$(into any number of colours) there is always either a monochromatic$k$-term arithmetic progression or a rainbow arithmetic progression (i.e. all elements are different colours). Estimate$H(k)$. Is it true that $H(k)^{1/k}/k \to \infty$ as$k\to\infty$? 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$. SOLVED Let$A=\{a_1,a_2,\ldots\}\subset \mathbb{R}^d$be an infinite sequence such that$a_{i+1}-a_i$is a positive unit vector (i.e. is of the form$(0,0,\ldots,1,0,\ldots,0)$). For which$d$must$A$contain a three-term arithmetic progression? 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. Additional thanks to: Boris Alexeev and Dustin Mixon SOLVED Let$k\geq 3$. Must any ordering of$\mathbb{R}$contain a monotone$k$-term arithmetic progression, that is, some$x_1<\cdots<x_k$which forms an increasing or decreasing$k$-term arithmetic progression? The answer is no, even for$k=3$, as shown by Ardal, Brown, and Jungić [ABJ11]. See also [195] and [196]. OPEN What is the smallest$k$such that in any permutation of$\mathbb{Z}$there must exist a monotone$k$-term arithmetic progression$x_1<\cdots<x_k$? Geneson [Ge19] proved that$k\leq 5$. Adenwalla [Ad22] proved that$k\leq 4$. See also [194] and [196]. Additional thanks to: Boris Alexeev and Dustin Mixon OPEN Must every permutation of$\mathbb{N}$contain a monotone 4-term arithmetic progression$x_1<x_2<x_3<x_4$? 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]. Additional thanks to: Boris Alexeev and Dustin Mixon OPEN Can$\mathbb{N}$be partitioned into two sets, each of which can be permuted to avoid monotone 3-term arithmetic progressions? If three sets are allowed then this is possible. Additional thanks to: Boris Alexeev and Dustin Mixon SOLVED If$A\subset \mathbb{N}$is a Sidon set then must the complement of$A$contain an infinite arithmetic progression? The answer is yes, as shown by Baumgartner [Ba75]. SOLVED If$A\subset \mathbb{R}$does not contain a 3-term arithmetic progression then must$\mathbb{R}\backslash A$contain an infinite arithmetic progression? The answer is no, as shown by Baumgartner [Ba75] (whose construction uses the axiom of choice). OPEN Does the longest arithmetic progression of primes in$\{1,\ldots,N\}$have length$o(\log N)$? It follows from the prime number theorem that such a progression has length$\leq(1+o(1))\log N$. OPEN Let$G_k(N)$be such that any set of$N$integers contains a subset of size at least$G_k(N)$which does not contain a$k$-term arithmetic progression. Determine the size of$G_k(N)$. How does it relate to$R_k(N)$, the size of the largest subset of$\{1,\ldots,N\}$without a$k$-term arithmetic progression? Is it true that $\lim_{N\to \infty}\frac{R_3(N)}{G_3(N)}=1?$ 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)$. Additional thanks to: Zachary Chase SOLVED Are there arbitrarily long arithmetic progressions of primes? 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. OPEN For any$n$, let$A(n)=\{0<n<\cdots\}$be the infinite sequence with$a_0=0$and$a_1=n$and$a_{k+1}$is the least integer such that there is no three-term arithmetic progression in$\{a_0,\ldots,a_{k+1}\}$. Can the$a_k$be explicitly determined? How fast do they grow? 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]. There are no conjectures for the general case. OPEN Let$N\geq 1$. What is the largest$t$such that there are$A_1,\ldots,A_t\subseteq \{1,\ldots,N\}$with$A_i\cap A_j$a non-empty arithmetic progression for all$i\neq j$? 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.