Choi's sum-avoiding set function: is $f(n)\le n^{1/2+o(1)}$? (Erdős #788)
Statement
Let $f(n)$ be maximal such that for every set $B\subset (2n,4n)\cap \mathbb{N}$ there exists some $C\subset (n,2n)\cap \mathbb{N}$ with $c_1+c_2\not\in B$ for all $c_1\neq c_2\in C$ and $\lvert C\rvert+\lvert B\rvert \geq f(n)$. (So $f(n)$ is the largest guaranteed combined size: an adversary picks $B$ in $(2n,4n)$, and one must always find a $C$ in $(n,2n)$ whose pairwise distinct sums all avoid $B$, with $\lvert C\rvert+\lvert B\rvert\ge f(n)$.) Estimate $f(n)$. In particular, is it true that $f(n)\leq n^{1/2+o(1)}$?
Acceptance. FULLY RESOLVES: a complete proof that $f(n) \leq n^{1/2+o(1)}$ (matching the known $\gg n^{1/2}$ lower bound and determining $f$ up to $n^{o(1)}$), OR a proof that $f(n) \geq n^{c}$ for some explicit constant $c > 1/2$, refuting the conjectured bound. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an upper bound on $f(n)$ with exponent strictly better than the best bound stated in the background, with full proof — e.g. via a new almost-sure independence-number bound for random Cayley graphs combined with the stated reduction; (b) an improved lower-bound construction beating $\gg n^{1/2}$ by a power of $n$, with verification; (c) exact values of $f(n)$ for a range of small $n$ computed by exhaustive or certified min-max search, with reproducible code and an exhaustiveness argument, plus an empirical estimate of the exponent. Deliver the proof file, or the construction + verification, or the search code + table of exact values.
Background
A conjecture of Choi [Ch71], who proved the first nontrivial upper bound $f(n) \ll n^{3/4}$; listed as open on erdosproblems.com/788 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). The frontier: Baltz, Schoen, and Srivastav [BSS00] proved $f(n) \ll (n\log n)^{2/3}$, and Hunter (site comments) sketched an independent argument giving $f(n) \ll n^{2/3+o(1)}$. In the other direction Adenwalla (site comments) gave a simple construction showing $f(n) \gg n^{1/2}$, so the conjecture asserts the lower bound is sharp up to $n^{o(1)}$. Hunter's argument generalizes to a clean reduction: if a random Cayley graph of density $p$ almost surely has independence number $\ll p^{-c-o(1)}$, then $f(n) \leq n^{c/(c+1)+o(1)}$. Via this reduction, the Alon–Pham results on independence numbers of random Cayley graphs [AlPh25] yield the current record $f(n) \leq n^{3/5+o(1)}$, and the conjectured optimal $p^{-1+o(1)}$ independence bound would give the full $f(n)\leq n^{1/2+o(1)}$. A neighbouring problem on the same site, Erdős #787 (erdosproblems.com/787), concerns a different sum-avoiding extremal function and should not be conflated with Choi's $f$ here. The attacker's tools: improved independence-number bounds for random Cayley graphs fed through Hunter's reduction; and exact computation of $f(n)$ for small $n$ (a min-max over subset pairs, amenable to ILP/QBF-style search) to measure the true exponent empirically.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #788 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.