Additive bases: change of domain
Volume 221 / 2025
Abstract
We consider two questions of Ruzsa on how the minimum size of an additive basis $B$ of a given set $A$ depends on the domain of $B$. To state these questions, for an abelian group $G$ and $A \subseteq D \subseteq G$ we write $\ell _D(A) := \min\left\{ |B|: B \subseteq D, \, A \subseteq B+B \right\}$. Ruzsa asked how much larger than $\ell_{\mathbb Q}(A)$ can $\ell_{\mathbb Z}(A)$ be for $A\subset \mathbb Z$, and how much larger than $\ell_{\mathbb Z}(A)$ can $\ell_{\mathbb N}(A)$ be for $A\subset \mathbb N$. For the first question we show that if $\ell_{\mathbb Q}(A) = n$ then $\ell_{\mathbb Z}(A) \le 2n$, and this is tight up to an additive error of at most $O(\sqrt {n})$. For the second question, we show that if $\ell_{\mathbb Z}(A) = n$ then $\ell_{\mathbb N}(A) \le O(n\log n)$, and this is tight up to the constant factor. We also consider these questions for higher order bases. Our proofs use some ideas that are unexpected in this context, including linear algebra and Diophantine approximation.
