Problem Statement
For $r\geq 2$ let $h(r)$ be the maximal finite $k$ such that there exists a basis $A\subseteq \mathbb{N}$ of order $r$ (so every large integer is the sum of at most $r$ integers from $A$) and exact order $k$ (so every large integer is the sum of exactly $k$ integers from $A$).
Find the value of\[\lim_r \frac{h(r)}{r^2}.\]
Find the value of\[\lim_r \frac{h(r)}{r^2}.\]
Categories:
Number Theory Additive Basis
Progress
A simple example of the order of a basis differing from the exact order is given by $A=\cup_{k\geq 0}(2^{2k},2^{2k+1}]$, which has order $2$ but exact order $3$.Erdős and Graham [ErGr80b] have shown that a basis $A$ has an exact order if and only if $a_2-a_1,a_3-a_2,a_4-a_3,\ldots$ are coprime. They also proved that\[\frac{1}{4}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{5}{4}.\]The best bounds known for the limit are\[\frac{1}{3}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{1}{2},\]the lower bound originally due to Grekos [Gr88] and the upper bound to Nash [Na93]. Improved bounds in the lower order terms were given by Plagne [Pl04].
Erdős and Graham [ErGr80b] showed $h(2)=4$. Nash [Na93] showed $h(3)=7$. The value of $h(4)$ is unknown, but it is known [Pl04] that $10\leq h(4)\leq 11$.
Source: erdosproblems.com/336 | Last verified: January 14, 2026