Erdős Problem #336 — 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 or…

Erdős and Graham posed the question in 1980: determine whether the limit of $h(r)/r^2$ exists and, if so, find its value. The problem remains unresolved.

Known results

• Grekos, 1988: $\frac{1}{3}\leq\liminf_{r\to\infty}h(r)/r^2$.
• Nash, 1993: $\limsup_{r\to\infty}h(r)/r^2\leq\frac{1}{2}$.
• Plagne, 2004: improved lower-order terms.
• Exact values include $h(2)=4$, $h(3)=7$, and $10\leq h(4)\leq11$; $h(4)$ is unknown.

2009 related asymptotic analysis

A study of the closely related function $X(h)$ established explicit quadratic upper and lower bounds and identified the asymptotic gap as a major open problem. It offers no resolution of Erdős Problem $\#336$ and records only a conjectural preference for the lower bound.

Current status (as of March 2026): the limit remains open, with $\frac{1}{3}\leq\liminf_{r\to\infty}h(r)/r^2\leq\limsup_{r\to\infty}h(r)/r^2\leq\frac{1}{2}$ and no public proof of existence or value.