Erdős Problem #338

Erdős Problem 338: restricted additive order

Statement and scope

The restricted order of $A\subset\mathbb N$ is the least $t$ such that every sufficiently large integer is a sum of at most $t$ distinct elements. The problem asks when it exists, how it compares with ordinary order, and what robustness under finite deletions implies.

We completely characterize the family consisting of all multiples of a modulus together with finitely many exceptions, and give a density condition guaranteeing restricted order at most two. The general characterization and finite-deletion questions are unresolved here. Source: https://www.erdosproblems.com/338. This retains Bateman's valid example from the earlier GPT-5.2 attempt, but replaces its inaccurate account of the remaining questions.

An exact modular criterion

Let $q\ge2$, let $F$ be a finite set of positive integers none divisible by $q$, and put $A=q\mathbb N\cup F$. For each residue $r\bmod q$, define \[ c_r=\min\{j:r\text{ is a sum of }j\text{ residues from }F \text{ with repetition}\}, \] and \[ s_r=\min\{|E|:E\subset F,\ \sum_{e\in E}e\equiv r\pmod q\}. \] An unavailable minimum is infinite; the empty sum gives $c_0=s_0=0$. Then \[ \operatorname{ord}(A)=1+\max_r c_r,\qquad \operatorname{ord}_{\rm restricted}(A)=1+\max_r s_r, \tag{1} \] with infinity interpreted as absence of a finite order.

For the upper bounds, choose for each residue a minimizing multiset or subset from $F$. For every sufficiently large $n$ in that residue, subtract its fixed sum and use the remaining positive multiple of $q$ as one additional summand. In the restricted case that extra summand is distinct from all chosen elements because none of them is divisible by $q$.

For the lower bounds, a representation with at most $t$ summands of a sufficiently large integer must use an element of $q\mathbb N$: a sum of at most $t$ members of the fixed finite set $F$ is bounded. Removing all multiples of $q$ leaves at most $t-1$ members of $F$ with the required residue, counted with or without repetition as appropriate. This proves $1$.

In particular ordinary order is finite precisely when $\gcd(q,F)=1$. Indeed the nonnegative sums of residues of $F$ form the subgroup they generate in the finite cyclic group: an inverse of any residue is a nonnegative multiple of it. Restricted order is finite precisely when the subset sums of the actual finite set $F$ cover every residue modulo $q$.

Examples and exact comparisons

With $F=\{1\}$ and $q=h\ge3$, we have $\max c_r=h-1$, so the ordinary order is exactly $h$. The only restricted residues are zero and one, so no restricted order exists. This is Bateman's example, with its exact ordinary order verified. For $q=2$ the same set has both orders two.

For another explicit separation, take $q=7$, $F=\{1,2,3\}$. Every residue is a sum of at most two elements of $F$ with repetition, and not all are single residues, so the ordinary order is three. Subset sums cover $0,\ldots,6$; residue six needs all three elements, while the other residues need at most two. Thus the restricted order is exactly four.

A sufficient density hypothesis

Suppose $\underline d(A)>1/2$. Choose $1/2<\delta<\underline d(A)$. For all sufficiently large $n$, let $E=A\cap[1,n-1]$; then $|E|\ge\delta(n-1)$. The reflected set $n-E$ lies in the same interval and has the same size, so \[ |E\cap(n-E)|\ge2|E|-(n-1)\ge(2\delta-1)(n-1)>1. \] At most one point is $n/2$. Some other point $a$ in the intersection therefore gives $n=a+(n-a)$ with two distinct elements of $A$. Thus the restricted order is at most two. It is one exactly when $A$ contains every sufficiently large integer.

Remaining gap

The modular criterion is exact for the specified class, but that class has essential finite exceptions: deleting all of $F$ leaves only multiples of $q$. It therefore does not answer the questions where every finite deletion remains a basis, with or without a uniform order. General bases outside the density hypothesis are likewise not characterized here.

COMPLETION ESTIMATE

COMPLETION: 40%

Erdős problem #338

1) FORMAL RESTATEMENT.

A set $A\subseteq\mathbb{N}$ has restricted order $r$ if every sufficiently large integer can be expressed as a sum of at most $r$ distinct elements of $A$.

The problem asks:

If $A$ is a basis of (unrestricted) order $r$, must $A$ have a restricted order (possibly depending on $r$)? In particular, must every basis of order $2$ have a restricted order?

The statement also records a construction of Bateman for $h\ge 3$ that is a basis of order $h$ but has no restricted order.

2) QUICK LITERATURE/CONTEXT CHECK. The statement reports:

• Bateman constructed, for each $h\ge 3$, a basis of order $h$ with no restricted order.
• It also states that Kelly [Ke84] proved every basis of order $2$ has restricted order.
• It asks further questions about sets of exact order $2$ and deletions $A\setminus\{a\}$.

Only the Bateman construction is proved here.

3) ATTACK PLAN.

• Prove Bateman's example works: basis of order $h$ but no restricted order.
• Do a small modular sanity check for $h=3$.
• Record what remains open/unstudied here (notably the order-$2$ and exact-order-$2$ refinements).

4) WORK.

Fix an integer $h\ge 3$ and define \[ A:=\{1\}\cup\{x\in\mathbb{N}: h\mid x\}. \]

Proposition 338.1 ($A$ is a basis of order $h$). Every integer $n\ge 1$ can be expressed as a sum of at most $h$ (not necessarily distinct) elements of $A$.

Proof. Write $n=qh+r$ with $0\le r\le h-1$. Then $qh\in A$ (it is a multiple of $h$), and $1\in A$. Hence \[ n = (qh) + \underbrace{1+\cdots+1}_{r\text{ times}}. \] This uses $1+r\le h$ summands (or just $r$ summands if $q=0$ and we interpret $qh=0$ as absent). Thus $A$ is a basis of order $h$. $\square$

Proposition 338.2 ($A$ has no restricted order). No matter what $r\in\mathbb{N}$ is chosen, there are infinitely many integers that cannot be written as a sum of at most $r$ distinct elements of $A$.

Proof. A sum of distinct elements of $A$ uses at most one copy of $1$ (because $1$ appears only once in $A$) and any number of distinct multiples of $h$. Therefore every such sum is congruent to either $0$ or $1$ modulo $h$. In particular, no integer congruent to $2\pmod h$ can be represented in this way, and there are infinitely many such integers. Hence $A$ has no restricted order. $\square$

FAST REALITY CHECK (the case $h=3$). For $h=3$, $A=\{1,3,6,9,\dots\}$. Any sum of distinct elements is congruent to $0$ or $1$ modulo $3$, so $2,5,8,11,\dots$ are never representable. This matches Proposition 338.2.

5) VERIFICATION. Both propositions are proved by explicit modular reasoning.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We gave a complete proof that for every $h\ge 3$ there exists a basis of order $h$ with no restricted order (Propositions 338.1--338.2), answering the general question in the negative for $r\ge 3$.

(ii) Exact first gap. The remaining questions in the statement concern order $2$ and exact order $2$ (including whether $A\setminus\{a\}$ must remain a basis of order $2$). No such results are proved here.

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

1. Try to prove directly (without external literature) that every basis of order $2$ has some finite restricted order; or find an explicit counterexample if possible.
2. Analyze the stronger hypothesis "exact order $2$" and determine whether it forces robustness under deletions $A\setminus\{a\}$.
3. Search for structural invariants (e.g. local densities in residue classes) that prevent restricted representations even when unrestricted representations exist.

(iv) Minimal counterexample structure. A counterexample to "every basis of order $2$ has restricted order" would be a set $A$ such that every large $n$ is a sum of two elements of $A$ (with repetition allowed), yet for each fixed $r$ infinitely many integers cannot be represented as sums of $\le r$ distinct elements. Any such $A$ would need to force heavy reuse of certain small elements (as in Bateman's example), but without increasing the order beyond $2$.