Logo
FAQ Tags Prizes Definitions Links
All Problems Random Solved Random Open
7 solved out of 23 shown
$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] have proved $r_4(N)\ll N/(\log N)^{c}$ for some small constant $c>0$. The best bound available for general $k$ is due to Gowers [Go01], \[r_k(N) \ll \frac{N}{(\log\log N)^{c_k}},\] where $c_k>0$ is a small constant 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 also [142].

$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$, Green and Tao [GrTa17] for $k=4$, and Gowers [Go01] for $k\geq 5$.
$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] they suggest this holds for every $k$-term arithmetic progression.
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'.
$1000
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)$.
The best known bounds are due to Kelley and Meka [KeMe23] for $k=3$, Green and Tao [GrTa17] for $k=4$, and Gowers [Go01] for $k\geq 5$. Erdős remarked this is 'probably unattackable at present'. Given that Erdős elsewhere offered \$5000 just for (essentially) showing that $r_k(N)=o_k(N/\log N)$, the value of this prize seems odd.

See also [3].

Additional thanks to: Zachary Hunter
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
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.
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$.
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}$.
Let $1\leq k<\ell$ be integers and define $F_k(N,\ell)$ 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.
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$.
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?
It is known that it must contain a 4-term arithmetic progression if $d=2$, and need not contain a 3-term arithmetic progression if $d=5$. The cases $d=3$ and $d=4$ are unknown.
Additional thanks to: Boris Alexeev and Dustin Mixon
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].
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] has shown that $k\leq 5$.
Additional thanks to: Boris Alexeev and Dustin Mixon
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.
Additional thanks to: Boris Alexeev and Dustin Mixon
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
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].
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).
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$.
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?\]
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 G_k(N)$.
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.
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.
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.

Additional thanks to: Zachary Hunter