All Random Solved Random Open
2 solved out of 3 shown (show only solved or 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
What is the size of the largest $A\subseteq \{1,\ldots,N\}$ such that, for all $\emptyset\neq S\subseteq A$, $\sum_{n\in S}n$ is not a square?
Erdős observed that $\lvert A\rvert \gg N^{1/3}$ is possible, taking the first $\approx N^{1/3}$ multiples of some prime $p\approx N^{2/3}$.

Essentially solved by Nguyen and Vu [NgVu10], who proved that $\lvert A\rvert\ll N^{1/3}(\log N)^{O(1)}$.

See also [438].

This question was asked by Erdős to a young Terence Tao in 1985. We thank Tao for sharing this memory and a letter of Erdős describing the problem.

Additional thanks to: Terence Tao
Let $f(n)$ be maximal such that, for every $m\geq 1$, there exists some $S\subseteq \{1,\ldots,n\}$ with $\lvert S\rvert=f(n)$ such that $m\neq \sum_{a\in A}a$ for all $A\subseteq S$.

Is it true that \[f(n) = \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}?\]

A conjecture of Erdős and Graham, who proved the lower bound \[f(n)\geq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}.\] Their proof is to note that we can assume that $m< \binom{n+1}{2}$ and then, for any $m$, take $S=\{ kp : 1\leq k<\frac{n}{p}\}$ where $p$ is the least prime that does not divide $m$ (so $p<(2+o(1))\log n$).

The complementary bound \[f(n) \leq \left(\frac{1}{2}+o(1)\right)\frac{n}{\log n}\] was proved by Alon and Freiman [AlFr88], who chose $m$ as the least common multiple of $\{1,\ldots,s\}$ where $s$ is maximal such that $m\leq \frac{n^2}{20(\log n)^2}$.

Additional thanks to: Noga Alon