Minimal complement count T(n) square-root growth

Conjecture 7 · arXiv:2006.00534

arXiv Conjecture low confidence— first stated 2020-12-30

Authors: Noga Alon, Noah Kravitz, Matt Larson

Status open medium confidence

No verified follow-up resolving Conjecture 7 was found. At the time of the paper, the known bounds were T(n) \geq n^{1/3}/\mathrm{polylog} (Theorem 1) and T(n) = O(n^{3/4+\varepsilon}) (Theorem 3), with the conjecture proposing the true growth rate is \widetilde{\Theta}(\sqrt{n}). Web searches returned related papers on minimal additive complements published in 2023 and 2025, but none could be verified via WebFetch to specifically address this conjecture. The conjecture appears to remain open as of May 2026.

Reviewer notes. Searches returned related papers including 'On minimal additive complements' (Ramanujan Journal, 2025, doi:10.1007/s11139-025-01281-6) and 'Sets arising as minimal additive complements in the integers' (Journal of Number Theory, 2023), but WebFetch of the Ramanujan Journal page was blocked by authentication redirect and thus these papers could not be verified to address Conjecture 7 on T(n). Noah Kravitz's arXiv author page shows no additional follow-up paper co-authored on this topic. The gap between the n^{1/3} lower bound and n^{3/4+\varepsilon} upper bound remains unresolved in the verified literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. We have that $T(n) = \widetilde{\Theta}(\sqrt{n})$. More generally, we have that $T(G) = \widetilde{\Theta}(\sqrt{|G|})$.

Context

The paper defines $\widetilde{\Theta}(g(n))$ to mean $f = \Omega(g(n)(\log n)^a)$ and $f(n) = O(g(n)(\log n)^b)$ for some integers $a,b$ (i.e., equality up to polylogarithmic factors). Theorem 1 gives a lower bound $T(n) \geq n^{1/3}/(2(\log n/\log 2)^{2/3})$ and Theorem 3 gives $T(n) = O(n^{3/4+\varepsilon})$; the conjecture proposes the true growth rate is $\widetilde{\Theta}(\sqrt{n})$.

Notes. PDF source — the tilde in $\widetilde{\Theta}$ is garbled in extraction (appears as bare 'e' or dropped); the argument of the second $\widetilde{\Theta}$ (presumably $\sqrt{|G|}$) is also lost in the PDF rendering. Statement reconstructed from context.

Source paper

Inverse problems for minimal complements and maximal supplements
Noga Alon, Noah Kravitz, Matt Larson · 2020-12-30
https://arxiv.org/abs/2006.00534 PDF source