Open-problem statements, with their sources attached.

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.

Is $h(n) = \Theta(\sqrt{n})$?

By the solved variant erdos_789.variants.isBigO_sq, in order to prove erdos_789.variants.sq it suffices to show $\sqrt{n}=O(h(n))$.

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.

Is $h(n) = \Theta((n\log(n)))^{1/3})$?

By the solved variant erdos_789.variants.cube_root_linearithmic_isBigO, in order to prove erdos_789.variants.cube_root_linarithmic it suffices to show $h(n) = O((n\log(n))^{1/3})$.

Is it true that $\frac{R(n+1)}{R(n)}\geq 1+c$ for some constant $c>0$, for all large $n$?

Is it true that $R(n+1)-R(n) \gg n^2$?

Let $k \geq 3$. Define $g_k(n)$ to be the minimal $N$ such that $\{1, ..., N\}$ contains some $A$ of size $|A| = n$ such that

contains no non-trivial $k$-term arithmetic progression. Estimate $g_k(n)$. In particular, is it true that

$F(n) / \log n \to \infty as n \to \infty$

Does there exist a $k>2$ such that the $k$-sized subsets of {1,...,2k} can be coloured with $k+1$ colours such that for every $A\subset \{1,\ldots,2k\}$ with $\lvert A\rvert=k+1$ all $k+1$ colours appear among the $k$-sized subsets of $A$?

Alternative statement of Erdős Problem 835 using the chromatic number of the Johnson graph. This is equivalent to asking whether there exists $k > 2$ such that the chromatic number of the Johnson graph $J(2k, k)$ is $k+1$.

Is the chromatic number of J(2 * k, k) always at least k + 2?

Is it true that, for all large $n$, $f(n + 1) \ge f(n)$?

Estimate m(n,k), or better give an asymptotic formula.

There exists a constant $C>0$ such that, for all large $N$, if $A\subseteq \{1,\ldots,N\}$ has size at least $\frac{5}{8}N+C$ then there are distinct $a,b,c\in A$ such that $a+b,a+c,b+c\in A$.

A problem of Erdős and Sós (also earlier considered by Choi, Erdős, and Szemerédi [CES75], but Erdős had forgotten this).

Erdős and Sós conjectured that $f_k(N)\sim \frac{1}{2}\left(1+\sum_{1\leq r\leq k-2}\frac{1}{4^r}\right) N$, where $f_k(N)$ is the minimal size of a subset of $\{1, \dots, N\}$ guaranteeing $k$ elements have all pairwise sums in the set.

Erdős Problem 872, part (i) (weak form): there exists a constant $\epsilon > 0$ such that the game length is at least $\epsilon \cdot n$ for all sufficiently large $n$.

Erdős Problem 872, part (ii) (strong form): for every $\epsilon > 0$, the game length is at least $(1-\epsilon) \cdot n / 2$ for all sufficiently large $n$.

Status note: the forum thread (April-May 2026) records Shortener strategies giving $L(n) \leq (23/48 + o(1)) \cdot n$ (described in the thread as accepted as correct, with a Lean formalization in progress) and a claimed $L(n) \leq 0.19 \cdot n$, either of which would answer this question negatively under the Prolonger-first convention. Neither is published, so the statement is recorded here as the original Erdős question.

Forum-related variant: how small can a maximal primitive subset of $\{2, \dots, n\}$ be? The set of primes in $\{2, \dots, n\}$ is a maximal primitive subset of size $\pi(n)$, and the forum thread asks whether this is the smallest possible for all $n \geq 2$. Equivalently: must every completed play of the saturation game, by both players and regardless of strategy, claim at least $\pi(n)$ elements? (Terminal positions of the game are exactly the maximal primitive subsets.)

Let A ⊂ ℕ be an additive basis of order k which is minimal in the sense that if B ⊂ A is any infinite set, then A \ B is not a basis of order k.

Must there exist an infinite B ⊂ A such that A \ B is an additive basis of order k + 1?

Does the limit $\lim_{n\to\infty} \frac{f(2n)}{f(n)}$ tend to infinity?

(Other finite limits have been ruled out by [KoLu25], see below)