n^{1/4} tight bound for non-averaging sets
Informal Conjecture on h(n) · arXiv:2311.01416
Status solved high confidence
The conjecture that h(n) = \Theta(n^{1/4}) (i.e., that Bosznay's 1990 lower bound is tight) was resolved in October 2024 by Pham and Zakharov, who proved that the largest non-averaging subset of \{1,\ldots,n\} has size n^{1/4+o(1)}, matching the lower bound up to sub-polynomial factors. Their paper explicitly describes this as solving the Erdős–Straus problem on non-averaging sets. The journal version appeared in Geometric and Functional Analysis in 2025.
Cited literature (1)
-
Proves h(n) = n^{1/4+o(1)}, establishing that the Bosznay lower bound \Omega(n^{1/4}) is tight and thus confirming the conjecture h(n) = \Theta(n^{1/4}).
Reviewer notes. Pham and Zakharov's paper 2410.14624 (submitted October 18, 2024; published in GAFA 2025) directly resolves the conjecture. The result h(n) = n^{1/4+o(1)} means the upper bound matches the Bosznay construction up to a sub-polynomial factor, confirming the n^{1/4} exponent is correct.
Context
The bounds $\Omega(n^{1/4}) \leq h(n) \leq n^{1/2+o(1)}$ were both known by 1990, with the lower bound due to Bosznay [6] and the upper bound to Erdős and Sárközy [10]. The lower bound follows from a simple construction: fixing integer $q$, the set $\{n_i = iq^3 + i(i+1)/2 : i = 1,\ldots,q-1\}$ is a non-averaging subset of $[n]$ with $n = q^4$. The authors state 'which we suspect to be tight' immediately after citing this bound.
Notes. Stated as running prose: 'The current best lower bound, h(n) = Ω(n^{1/4}), which we suspect to be tight'. No labelled conjecture environment.
Source paper
Homogeneous structures in subset sums and non-averaging sets
David Conlon, Jacob Fox, Huy Tuan Pham · 2023-11-02
https://arxiv.org/abs/2311.01416
PDF source