Exact order versus order of additive bases: evaluate $\lim_r h(r)/r^2$, and determine $h(4)$ (Erdős #336)
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$ (meaning every sufficiently large integer is the sum of at most $r$ integers from $A$) whose exact order is $k$ (meaning every sufficiently large integer is the sum of exactly $k$ integers from $A$). Find the value of $$\lim_{r\to\infty} \frac{h(r)}{r^2}.$$ A simple example separating the two notions: $A=\bigcup_{k\geq 0}(2^{2k},2^{2k+1}]$ has order $2$ but exact order $3$.
Acceptance. FULLY RESOLVES: the exact value of $\lim_r h(r)/r^2$ (including a proof that the limit exists, if not already established en route): a family of constructions attaining the value asymptotically, with complete proofs of both the order and the exact order of each basis, together with a matching asymptotic upper bound. ADVANCES: (a) a proven improvement of either the lower bound $1/3$ or the upper bound $1/2$ stated in the background; (b) determination of $h(4)$: either a basis of order $4$ with exact order $11$ (explicit construction plus complete proofs of both properties) or a proof that every order-$4$ basis with an exact order has exact order at most $10$; (c) new exact values $h(5), h(6), \ldots$ with proofs; (d) a reproducible computer search over structured (finite-pattern / eventually periodic) bases that certifies a new lower bound for a specific $h(r)$, with code and the proof completing the certification. Deliver the proofs; for construction-based claims, the explicit basis description plus its certification; for search-based claims, the code + certificate.
Background
Raised by Erdős and Graham [ErGr80, p.51]; listed as open on erdosproblems.com/336 (fetched 2026-07-13, status 'open'). Erdős and Graham [ErGr80b] proved that a basis $A=\{a_1<a_2<\cdots\}$ possesses an exact order at all if and only if the consecutive differences $a_2-a_1, a_3-a_2, a_4-a_3,\ldots$ are coprime (gcd $1$), and they established $1/4\leq \lim_r h(r)/r^2\leq 5/4$. The current record bounds are $$\frac{1}{3}\leq \lim_r \frac{h(r)}{r^2}\leq \frac{1}{2},$$ with the lower bound due to Grekos [Gr88] and the upper bound to Nash [Na93]; Plagne [Pl04] improved the lower-order terms. Small cases: $h(2)=4$ (Erdős–Graham [ErGr80b]), $h(3)=7$ (Nash [Na93]), and $10\leq h(4)\leq 11$ (Plagne [Pl04]) — determining $h(4)$ is the first unresolved exact value and the most concrete open milestone. No Lean formalisation exists yet (Bloom's page marks related OEIS sequences as 'possible' but lists none). The attacker's tools: extremal constructions of bases built from unions of intervals and arithmetic-progression-like pieces — searchable by computer over structured families and then certified by proof — combined with the combinatorial upper-bound arguments of Nash and Plagne; settling $h(4)$ or computing $h(5)$ looks like the tractable entry point.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #336 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.