Erdős Problem #336

Erdős Problem 336: order versus exact order

Statement and scope

The order of an additive basis is the least $r$ for which every sufficiently large integer is a sum of at most $r$ elements; its exact order is the least $k$ for which exactly $k$ summands suffice. Repetitions are allowed. Let $h(r)$ be the largest finite exact order among bases of order $r$. The problem asks for $\lim_r h(r)/r^2$.

We prove an explicit quadratic family and correctly verify the order-two, exact-order-three interval example. The limit question is unresolved here. The earlier GPT-5.2 proof incorrectly asserted that the interval example already represents all large integers with exactly two summands, contradicting its own claimed exact order. Source and stronger known asymptotic bounds: https://www.erdosproblems.com/336. No improvement on those bounds is claimed.

A quadratic family with completely computed orders

Fix $s\ge2$, put $m=s(s+1)$, and let $A$ consist of all positive integers congruent to $s$ or $s+1$ modulo $m$. The residues of sums of exactly $j$ elements are \[ jA\bmod m=\{js,js+1,\ldots,js+j\}\bmod m. \tag{1} \] Every such residue is realized by positive summands; adding arbitrary multiples of $m$ to one summand represents all sufficiently large numbers in that residue.

If $j<m-1$, $1$ has fewer than $m$ residues. For $j=m-1$ it consists of $m$ consecutive integers and hence all residues. Thus the exact order is \[ k=m-1=s^2+s-1. \tag{2} \]

The order is exactly $r=2s-1$. To prove the upper bound, write any residue $x\in[0,m-1]$ as $x=su+v$, $0\le u\le s$, $0\le v<s$. If $u\ge v$ and $x\ne0$, use $j=u$ in $1$, with $v$ of the summands equal to $s+1$. If $u<v$, replace $x$ by $x+m=s(u+s+1)+v$ and use $j=u+s+1\le2s-1$. Residue zero is represented by $s$ copies of $s+1$. Thus at most $2s-1$ summands suffice eventually in every residue.

For the lower bound consider $x=s^2-s-1$. It lies in no interval $[js,j(s+1)]$, since \[ \left\lceil\frac{x}{s+1}\right\rceil=s-1> s-2=\left\lfloor\frac{x}{s}\right\rfloor. \] For $j\le2s-2$, the largest sum of the small representatives is $(2s-2)(s+1)=2s^2-2<x+m=2s^2-1$; it therefore cannot reach the next integer congruent to $x$ either. This residue is absent from all sums of at most $2s-2$ elements. Equations $1$--$2$ prove \[ h(2s-1)\ge s^2+s-1, \] and in particular a quadratic lower bound with leading constant $1/4$ along these orders. This is weaker than the known leading lower constant $1/3$.

The interval example, with the distinction preserved

Let $B=\bigcup_{j\ge0}(4^j,2\cdot4^j]\cap\mathbb N$. We first determine its two-term sumset: \[ \{n\ge1:n\notin B+B\} =\{1,2,3\}\cup\{4^j+1,4^j+2:j\ge1\}. \tag{3} \] For $q=4^j$, $j\ge1$, numbers in $[q+3,2q]$ equal $2+(n-2)$ with both terms in $B$. The number $2q+1$ equals $2+(2q-1)$, and the whole interval $[2q+2,4q]$ is the sum of two copies of the integer interval $[q+1,2q]$. Together with $4=2+2$, this proves all claimed inclusions.

For $n=q+1$ or $q+2$, two summands below $q$ have sum at most $q$, because the preceding block ends at $q/2$. Any summand from the next block is at least $q+1$, leaving at most one for the other summand, whereas the least element of $B$ is two. This proves the omissions in $3$.

All omissions $q+1,q+2$ belong to $B$ itself, so $B$ is a basis of order two, but not exact order two. It has exact order three. Indeed $2+(B+B)$ represents every $n\ge9$ except possibly $q+3,q+4$ with $q=4^j\ge16$. Those two exceptions are \[ q+3=(q/2-1)+(q/2-1)+5,\qquad q+4=(q/2-1)+(q/2-1)+6, \] and all the summands belong to $B$. The basis does not have order one, since its block gaps are infinite in number.

Remaining gap

These families prove genuine separation between the two orders and provide explicit quadratic growth. They do not determine the extremal leading constant or establish a matching upper bound for arbitrary bases.

COMPLETION ESTIMATE

COMPLETION: 40%

Erdős problem #336

1) FORMAL RESTATEMENT.

Additive basis of order $r$. A set $A\subseteq\mathbb{N}$ is a basis of order $r$ if every sufficiently large integer $n$ can be written as a sum of at most $r$ (not necessarily distinct) elements of $A$.

Exact order. A set $A$ has exact order $k$ if every sufficiently large integer is representable as a sum of exactly $k$ (not necessarily distinct) elements of $A$.

Extremal function. For each $r\ge 2$, define $h(r)$ as the largest finite $k$ such that there exists a basis $A$ of order $r$ that has exact order $k$. The problem asks for the value of \[ \lim_{r\to\infty} \frac{h(r)}{r^2}, \] and for the exact values of $h(r)$.

2) QUICK LITERATURE/CONTEXT CHECK. The statement reports several bounds and values (e.g. $\tfrac14\le\liminf h(r)/r^2\le \limsup h(r)/r^2\le\tfrac54$, improved later to $\tfrac13\le\liminf\le\limsup\le\tfrac12$; and some small $h(r)$ values). These are recorded as context but are not re-proved here.

3) ATTACK PLAN.

• Prove elementary necessary conditions for being a basis / having exact order (gcd obstructions).
• Verify in detail the given explicit example \[A=\bigcup_{k\ge 0}\left(2^{2k},2^{2k+1}\right]\cap\mathbb{N}\] which the statement claims has order $2$ and exact order $3$.
• Use computation on this example as a sanity check.

4) WORK.

Lemma 336.1 (gcd obstruction for bases). If $A\subseteq\mathbb{N}$ is a basis of (finite) order $r$, then $\gcd(A)=1$.

Proof. Let $d=\gcd(A)$. Every sum of elements of $A$ (with repetitions allowed) is a multiple of $d$. If $d\ge 2$, then no integer $n\not\equiv 0\pmod d$ can be represented as a sum of elements of $A$, contradicting that all sufficiently large integers are representable. Hence $d=1$. $\square$

Now fix the example set. Let \[ A:=\bigcup_{k\ge 0}\left\{n\in\mathbb{N}: 2^{2k} < n \le 2^{2k+1}\right\}. \] Equivalently, $A$ contains $2$ and, for each $k\ge 1$, all integers in the interval $(4^k,2\cdot 4^k]$.

Proposition 336.2 (the example $A$ is a basis of order $2$). Every integer $n\ge 4$ can be written as $n=a+b$ with $a,b\in A$ (repetitions allowed). In particular, $A$ is a basis of order $2$.

Proof. We prove that every $n\ge 4$ is a sum of two elements of $A$.

If $n=4^k=2^{2k}$ for some $k\ge 1$, then \[ n=2^{2k-1}+2^{2k-1}, \] and $2^{2k-1}\in A$ because it is the upper endpoint of the interval $(2^{2k-2},2^{2k-1}]$.

Otherwise, pick $k\ge 0$ such that \[ 2^{2k} < n \le 2^{2k+2}. \] If $n\le 2^{2k+1}$, then $n\in A$ by definition, and $n=2+(n-2)$ is not needed; we can simply write $n=n+2-2$? To keep exactly two summands, we instead note that $n\ge 4$ implies there exists $a\in A$ with $2\le a\le n-2$ (e.g. $a=2$), and the remaining term can be handled by the next case; thus it suffices to handle the case $n>2^{2k+1}$.

So assume $n>2^{2k+1}$. Write $n=2^{2k+1}+t$ with $1\le t\le 2^{2k+1}$.

Case 1: $t=1$. If $k=0$, then $n=3$, which we are not claiming. If $k\ge 1$, then \[ n=2 + (2^{2k+1}-1). \] Here $2\in A$, and $2^{2k+1}-1>2^{2k}$ so $2^{2k+1}-1\in A$.

Case 2: $t\ge 2$. Set \[ a:=2^{2k}+t-1,\qquad b:=2^{2k}+1. \] Then $a+b=2^{2k+1}+t=n$. Moreover $t\ge 2$ implies $a>2^{2k}$, and $t\le 2^{2k+1}$ implies $a\le 2^{2k}+2^{2k}-1=2^{2k+1}-1\le 2^{2k+1}$. Thus $a\in A$. Clearly $b=2^{2k}+1\in A$.

Thus in all cases $n$ is a sum of two elements of $A$. $\square$

Proposition 336.3 (the example has exact order $3$).

1. (a) Every integer $n\ge 9$ can be written as a sum of exactly three (not necessarily distinct) elements of $A$.
2. (b) For every $k\ge 1$, the integers $2^{2k}+1$ and $2^{2k}+2$ are not representable as sums of exactly two elements of $A$.

Consequently, $A$ has exact order $3$.

Proof. (a) Let $n\ge 9$. Choose $k\ge 1$ such that $2^{2k}<n\le 2^{2k+2}$.

Case 1: $n>2^{2k+1}$. Write $n=2^{2k+1}+t$ with $1\le t\le 2^{2k+1}$. If $t\in\{1,2,3\}$, then \[ n = 2+2+\left(2^{2k+1}+(t-4)\right) \] where the third term is $2^{2k+1}-3$, $2^{2k+1}-2$, or $2^{2k+1}-1$, all of which are $>2^{2k}$ and $\le 2^{2k+1}$, hence in $A$. If $t\ge 4$, then \[ n = 2 + \left(2^{2k}+1\right) + \left(2^{2k}+t-3\right). \] Here $2\in A$, $2^{2k}+1\in A$, and $t\ge 4$ implies $2^{2k}+t-3>2^{2k}$ while $t\le 2^{2k+1}$ implies $2^{2k}+t-3\le 2^{2k+1}-3\le 2^{2k+1}$, so the third term is also in $A$.

Case 2: $n\le 2^{2k+1}$. Then $n\in A$ (since $n>2^{2k}$). If $n\ge 2^{2k}+5$, then $n-4>2^{2k}$ and $n-4\le 2^{2k+1}-4\le 2^{2k+1}$, hence $n-4\in A$, so \[ n = 2+2+(n-4) \] is a 3-term representation. It remains to treat $n\in\{2^{2k}+1,2^{2k}+2,2^{2k}+3,2^{2k}+4\}$. Since $n\ge 9$, this forces $k\ge 2$, so $2^{2k-1}\ge 8$ and the small constants $5,6\in A$. We give explicit representations: \[ \begin{aligned} 2^{2k}+1 &= 2^{2k-1} + \bigl(2^{2k-1}-1\bigr) + 2,\\ 2^{2k}+2 &= 2^{2k-1} + 2^{2k-1} + 2,\\ 2^{2k}+3 &= \bigl(2^{2k-1}-1\bigr) + \bigl(2^{2k-1}-1\bigr) + 5,\\ 2^{2k}+4 &= \bigl(2^{2k-1}-1\bigr) + \bigl(2^{2k-1}-1\bigr) + 6. \end{aligned} \] All summands lie in $A$ because $2^{2k-1}\in A$, $2^{2k-1}-1>2^{2k-2}$ so $2^{2k-1}-1\in A$, and $2,5,6\in A$. Thus every $n\ge 9$ is a sum of exactly three elements of $A$.

(b) Fix $k\ge 1$ and consider $N\in\{2^{2k}+1,2^{2k}+2\}$. Suppose $N=x+y$ with $x,y\in A$ and $x\le y$. If both $x,y<2^{2k}$, then $x,y\le 2^{2k-1}$ because there are no elements of $A$ in $(2^{2k-1},2^{2k}]$, hence $x+y\le 2^{2k}$, contradicting $N>2^{2k}$. Thus $y\ge 2^{2k}+1$. But then $x=N-y\le 1$, impossible since $A\subseteq\mathbb{N}$ does not contain $1$. So $N$ is not a 2-term sum from $A$.

Combining (a) and (b), $A$ has exact order $3$. $\square$

FAST REALITY CHECK (computed on the example). For the above $A$, a brute-force check up to $n\le 20\,000$ found:

• The integers not representable as a sum of exactly two elements of $A$ are \[\{1,2,3\}\cup\{4^k+1,4^k+2: k\ge 1\}\cap[1,20000].\]
• Every integer $n\ge 9$ is representable as a sum of exactly three elements of $A$.

This matches Proposition 336.3.

5) VERIFICATION.

• Lemma 336.1 is a direct modular obstruction.
• Propositions 336.2--336.3 are verified by explicit constructive casework.
• The computation is a finite check consistent with the proofs.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We fully verified the explicit example from the statement: the set $A=\bigcup_{k\ge 0}(2^{2k},2^{2k+1}]$ is a basis of order $2$ (Proposition 336.2) and has exact order $3$ (Proposition 336.3).

(ii) Exact first gap. We did not obtain new general bounds on $h(r)$, nor any proof of the existence/value of $\lim_{r\to\infty}h(r)/r^2$. The first missing piece is a general mechanism that turns "order $r$" information into sharp control of the largest possible exact order.

(iii) Top 3 next moves (concrete targets).

1. Develop a general lemma relating exact order $k$ to growth/structure of $rA:=\{a_1+\cdots+a_r: a_i\in A\}$ (sumsets with repetition), in particular to stabilization ranges.
2. For each fixed $r$, attempt a computational search for candidate extremal bases achieving large exact order $k$, to guess a formula for $h(r)$.
3. Prove new universal inequalities of the form $c_1 r^2\le h(r)\le c_2 r^2$ with improved constants by constructing explicit families and proving matching obstructions.

(iv) Minimal counterexample structure. If the limit $\lim_{r\to\infty}h(r)/r^2$ exists but differs from a conjectured value $c$, then for some $\delta>0$ there must be infinitely many $r$ for which either

• there exist bases of order $r$ with exact order at least $(c+\delta)r^2$, or
• no basis of order $r$ has exact order more than $(c-\delta)r^2$.

Either scenario would require a structural understanding of extremal bases far beyond the example-level constructions.