Erdős problem #338 — wave8t

Date: 2026-07-28 (UTC)

0. Mandatory live-page gate

I fetched https://www.erdosproblems.com/338 through the Bright Data anti-bot browser, not with datacenter curl. I also saved and visually inspected a full-page screenshot. The live page reported:

• status: OPEN;
• last edit: 14 September 2025;
• comments: 0;
• claimed proofs: 0;
• “Interested in collaborating”: None;
• “Currently working on this problem”: None;
• likes: Dogmachine, Desenyon, JJ_;
• “looks difficult”: Dogmachine;
• “looks tractable”: None;
• “results ... could be formalisable”: None;
• “working on formalising”: None.

Thus the mandatory skip condition did not fire.

The page's verbatim opening (25 words) is:

“The restricted order of a basis is the least integer \(t\) (if it exists) such that every large integer is the sum of at most”

Exact mathematical restatement of the remainder: the summands must be distinct members of \(A\); the page asks (i) for necessary and sufficient conditions for such a \(t\) to exist, (ii) whether it can be bounded in terms of the ordinary order, and (iii) for necessary and sufficient conditions for equality with the ordinary order.

The live page's listed results and subsidiary question were:

1. Bateman's example

\[ A=\{1\}\cup\{x>0:h\mid x\},\qquad h\ge3, \] has ordinary order \(h\) and no restricted order.

1. Kelly proved that an order-\(2\) basis has restricted order at most

\(4\), and at most \(3\) under positive lower density.

1. Hennecart constructed an order-\(2\) basis of restricted order \(4\).
2. Squares have orders \((4,5)\), ordinary/restricted, while triangular

numbers have \((3,3)\).

1. The page asks whether \(A\setminus F\) being a basis for every finite

\(F\) forces a restricted order, and asks the same when all those ordinary orders are equal.

1. Hegyvári--Hennecart--Plagne proved the lower bound

\[ f(k)\ge 2^{k-2}+k-1 \] for the largest possible restricted order among order-\(k\) bases (assuming the displayed extremal quantity is used).

The exact live-page body was independently extracted from the browser DOM; the superscript in item 6 was also checked visually because plain-text DOM extraction flattens superscripts.

Claim labels used below

• (a) elementary-rigorous: proved here without an external theorem.
• (b) rigorous-modulo-named-theorem: a result quoted from a named

primary source.

• (c) plausible/structural-unverified: a search conclusion or

heuristic, not a theorem.

• (d) computational-only: exhaustive for the stated finite search

space, but not promoted to an infinite theorem.

1. Primary-source literature check

The original formulation is visible on p. 206 of Erdős--Graham, On bases with an exact order:

• P. Erdős and R. L. Graham, Acta Arith. 37 (1980), author-archive

PDF.

The following sources and claims were checked:

• J. B. Kelly, Restricted Bases, Amer. J. Math. 79 (1957), 258--264,

DOI 10.2307/2372681. (b)

• F. Hennecart, *On the Restricted Order of Asymptotic Bases of Order

Two*, Ramanujan J. 9 (2005), 123--130, DOI 10.1007/s11139-005-0830-8. Its abstract states both the universal upper bound \(4\) in order \(2\) and an example attaining \(4\). (b)

• N. Hegyvári, F. Hennecart, A. Plagne, *Answer to a Question by Burr and

Erdős on Restricted Addition, and Related Results*, Combin. Probab. Comput. 16 (2007), 747--756, DOI 10.1017/S0963548306008224 and author PDF. Theorem 3 gives \(f(h)\ge2^{h-2}+h-1\). The paper also carefully distinguishes bounded gaps in one fixed restricted sumset from existence of a restricted asymptotic order. (b)

• N. Hegyvári, F. Hennecart, A. Plagne, *A proof of two Erdős'

conjectures on restricted addition and further results*, J. Reine Angew. Math. 560 (2003), 199--220, DOI 10.1515/crll.2003.055. This proves density statements for restricted sumsets; positive density is not cofiniteness and does not answer #338. (b)

• Y.-G. Chen and J.-H. Fang, *All sums of \(h\) distinct terms of a

sequence*, Eur. J. Combin. 41 (2014), 289--297, DOI 10.1016/j.ejc.2014.05.002. Its striking counterexample is for \(A\subseteq\mathbb Z\), not a positive asymptotic basis of \(\mathbb N\), so it does not settle the present question. (b)

• S.-Q. Chen and W.-X. Yu, On the restricted order of two, Discrete

Math. 346 (2023), 113388, DOI 10.1016/j.disc.2023.113388. It proves restricted order \(2\) above lower density \(1/2\), shows optimality, and gives a density-\(1/2\) example of restricted order \(3\). (b)

• J.-H. Fang and Y. Cheng, On the restricted order of asymptotic bases,

Discrete Math. 348 (2025), 114260, DOI 10.1016/j.disc.2024.114260. It refines the density behavior of an order-\(2\), restricted-order-\(3\) example. (b)

• S.-Q. Chen and J.-W. Li, Asymptotic Bases with Restricted Order Two,

Bull. Malays. Math. Sci. Soc. 49 (2026), article 110, DOI 10.1007/s40840-026-02103-8. This very recent paper proves that \(n/2\le B(n)\le n/2+k\) for every \(n\) forces restricted order \(2\), with optimality statements. It does not address finite deletions or a uniform bound in arbitrary order. (b)

I searched exact-title, exact-phrase, DOI, forward-citation, and “order \(3\), restricted order \(5/6\)” combinations. I found no primary source asserting the construction below, no solution of the finite-deletion question, and no general upper bound \(f(h)\). This is a documented search miss, not a priority claim and not proof that no such source exists. (c)

2. Explicit construction: ordinary order 3, restricted order 6

Define

Theorem 1

The set (1):

1. is an asymptotic basis of ordinary order exactly \(3\);
2. has restricted order exactly \(6\);
3. has the property that \(A\setminus F\) is an asymptotic basis for

every finite \(F\).

All three assertions are (a) elementary-rigorous.

Ordinary order

Write \(0,3\) for arbitrary sufficiently large tail elements in those residue classes, and \(4,6\) for the two exceptional elements. Repetition is allowed in an ordinary representation. Every residue modulo \(10\) has the following pattern:

For every sufficiently large target \(n\), subtract the displayed exceptional constants; the remaining one tail term is positive and lies in the required class. Thus \(\operatorname{ord}(A)\le3\).

For a sufficiently large \(n\), a one- or two-term representation must contain a tail element. The possible residues are

Residues \(1,2,5,8\) are absent, so order \(2\) is impossible infinitely often. Therefore \(\operatorname{ord}(A)=3\).

Restricted upper bound

Here different tail integers with the same residue are allowed, but each of \(4,6\) may be used only once. The following patterns cover every residue:

To justify “sufficiently large” rather than just residues, suppose a pattern asks for \(\ell\) distinct \(3\bmod10\) tail terms. After removing the exceptional term, write the target as \(10Q+3\ell\). Every sufficiently large \(Q\) is a sum of \(\ell\) distinct positive integers: use \(1,2,\ldots,\ell-1\) and the remaining value. Multiplying by \(10\) and adding \(3\) to each gives the required distinct tail elements. Patterns using one \(0\bmod10\) tail term lift immediately. Hence \(\operatorname{ord}_{R}(A)\le6\).

Restricted lower bound

Take a sufficiently large \(n\equiv1\pmod {10}\). Any representation contains a tail term because the distinct exceptional elements sum to at most \(10\). Let \(a\) be the number of \(3\bmod10\) tail terms; terms congruent to \(0\) only increase the length. The exceptional offset and its cost are

Solving \(3a+e\equiv1\pmod {10}\) gives the following least possible lengths:

Thus five distinct summands can never produce a sufficiently large \(1\bmod10\) target, while the six-term pattern above does. Therefore

Stability under every finite deletion

Let \(F\) be finite. There is a \(q_0\) such that every \(10q+3\), \(q\ge q_0\), survives in \(A\setminus F\). Given a sufficiently large \(n\), choose \(k\in\{1,\ldots,10\}\) with

Use \(k-1\) copies of \(10q_0+3\); the last summand is

which, for sufficiently large \(n\), is another surviving positive \(3\bmod10\) tail element. Repetition is legal for ordinary order. Thus \(A\setminus F\) is a basis of order at most \(10\).

Consequently any uniform bound for restricted order among ordinary order-\(3\) bases must be at least \(6\). The general HHP07 lower bound listed on the page gives only \(2^{3-2}+3-1=4\) at \(h=3\). Equation (2) therefore improves that displayed numerical lower bound from \(4\) to \(6\). This comparison is (a) for the construction and (b) for the HHP07 theorem; no literature-priority claim is made.

3. Complete reduction for eventually periodic bases

This gives an affirmative answer to both finite-deletion questions on a large, natural class.

Assume that \(A\) is eventually periodic: for some \(m,N\) and \(S\subseteq G=\mathbb Z/m\mathbb Z\),

Let \(E=A\cap[1,N-1]\), retaining multiplicity when its elements are reduced modulo \(m\). Put

Theorem 2 (eventually periodic classification)

For (3):

1. \(A\) is an ordinary asymptotic basis iff

\(\langle S\cup\overline E\rangle=G\).

1. \(A\) has a restricted order iff

\[ H+\Sigma(E)=G. \tag{4} \]

1. \(A\setminus F\) is a basis for every finite \(F\) iff \(H=G\). Under

this hypothesis \(A\) has restricted order at most \(m\).

1. If every \(A\setminus F\), including \(F=\varnothing\), has the same

ordinary order \(h\), then \[ \operatorname{ord}_{R}(A)=\operatorname{ord}(A)=h. \tag{5} \]

All parts are (a) elementary-rigorous.

Proof

Any bounded-length representation of a sufficiently large integer must use a tail element: a bounded number of elements of finite \(E\) has bounded sum. Conversely, any fixed residue word containing a letter of \(S\) lifts to every sufficiently large integer in that residue by holding all but one tail term fixed and increasing the last by a multiple of \(m\). This is the ordinary residue-lifting lemma.

In a finite group, the additive semigroup generated by a nonempty set is the subgroup it generates. The residues of unrestricted words containing a tail letter therefore fill \(G\) exactly when \(\langle S\cup\overline E\rangle=G\), proving part 1.

For a restricted representation, exceptional elements contribute the sum of an actual subset \(D\subseteq E\), while the tail residues contribute an element of \(H\). This proves necessity of (4). Conversely, choose such a decomposition for each residue. Express its \(H\)-part as a nonempty word in \(S\). A prescribed word in tail residue classes can be lifted with pairwise distinct integer representatives: fix distinct representatives for all but the last term, and let the last grow. Taking a maximum over the finite group gives one restricted order. This proves part 2.

Delete all of \(E\). The remaining pure tail is a basis exactly when \(\langle S\rangle=G\); further finite deletions do not change the tail. This proves part 3's equivalence. A shortest directed path in the Cayley graph of \(G\) has length at most \(m-1\) for a nonzero residue, while a positive zero-sum word has length at most \(m\). Hence the pure tail, and therefore \(A\), has restricted order at most \(m\).

Finally let \(B=A\setminus E\) be the pure tail. Ordinary and restricted residue words for \(B\) are identical because every residue in \(S\) has infinitely many distinct integer representatives. Thus \(\operatorname{ord}_{R}(B)=\operatorname{ord}(B)=h\). Since \(B\subseteq A\), restricted order cannot increase on passing to \(A\), so \(\operatorname{ord}_{R}(A)\le h\). The hypothesis with \(F=\varnothing\) gives \(\operatorname{ord}(A)=h\), and ordinary order is always at most restricted order. This sandwiches the latter at \(h\) and proves (5).

The Bateman obstruction is transparent in (4): its tail has \(S=\{0\}\), so \(H=\{0\}\), and one exceptional residue \(1\) gives only \(H+\Sigma(E)=\{0,1\}\).

4. Exact finite computation

The standalone verifier is erdos338_wave8t_reverify.py. It uses no third-party packages.

For each \(2\le m\le10\), it exhausts all \(3^m\) assignments of each residue to:

1. absent;
2. infinite periodic tail \(S\);
3. one finite exceptional element \(E\).

It retains precisely the deletion-robust cases \(\gcd(m,S)=1\), computes ordinary repeated-residue reachability, and computes restricted reachability with 0/1 subset-sum DP for \(E\). Multiple finite exceptions in one residue cannot alter ordinary order and can only lower restricted order, so a maximizer loses nothing by using at most one exception per residue. The following maxima are therefore exact for this finite periodic search space. (d) computational-only.

The maximizing \(m=10,h=3\) witness is exactly \(S=\{0,3\}\), \(E=\{4,6\}\), which produced (1).

As a genuinely independent check, the script also constructs the actual integers of \(A\) through \(4000\) and runs:

• unbounded-knapsack DP for ordinary sums;
• descending 0/1-knapsack DP for distinct sums.

On every \(n\in[1500,4000]\), the computed minimum term counts by residue are:

This finite DP is not used to prove the asymptotic claim; it independently checks every residue calculation in the proof.

Run:

python3 runs/erdos338_wave8t_reverify.py

Observed terminal lines:

integer-DP main certificate A={4,6} union {n>6:n=0 or 3 mod 10}: PASS (orders 3 and 6)
integer-DP spot check m=5, S={1}, E={2}: PASS
ALL CHECKS PASSED

The key from-scratch residue routines are:

def cyclic_sumset(xmask, ymask, m):
    out = 0
    for x in residues(xmask, m):
        for y in residues(ymask, m):
            out |= 1 << ((x + y) % m)
    return out

def ordinary_order(smask, emask, m, cutoff=None):
    full = (1 << m) - 1
    rmask = smask | emask
    exact = covered = smask              # at least one tail term
    if covered == full:
        return 1
    for h in range(2, (cutoff or 2*m+1) + 1):
        exact = cyclic_sumset(exact, rmask, m)  # E may repeat
        covered |= exact
        if covered == full:
            return h
    return None

def exceptional_subset_sumsets(emask, m):
    es = residues(emask, m)
    out = [0] * (len(es) + 1)
    out[0] = 1
    used = 0
    for e in es:
        for j in range(used, -1, -1):     # descending = use e once
            shifted = 0
            for x in residues(out[j], m):
                shifted |= 1 << ((x + e) % m)
            out[j + 1] |= shifted
        used += 1
    return out

The linked standalone file contains the complete exhaustive enumeration, the independent integer DP, Bateman regression tests, and all assertions. The exact sweep through \(m=11\) was also run (101 seconds, one core) and still gave maximum \(6\) at ordinary order \(3\). I did not run \(m=12\): the measured factor-of-three scaling predicts roughly 5--6 CPU-minutes (\(\approx0.1\) core-hour), outside the intended lightweight sweep, and no finite modulus cutoff can settle the uniform infinite question.

5. Exact wall beyond periodicity

The eventual-periodic argument succeeds because all asymptotic thresholds collapse to finitely many residue states. For a general set, the finite-deletion hypothesis has the quantifier form

The desired distinct representation needs uniform control while the forbidden set is built from repeated summands of representations of the same \(n\).

More precisely, fix \(n,h\). If \(n\) has no representation by at most \(h\) distinct elements, then among its finitely many at-most-\(h\)-term representations choose one repeated value from each. These choices form a finite set \(F_n\) such that \(n\) has no at-most-\(h\)-term representation from \(A\setminus F_n\). This is elementary, but (6) does not contradict it: \(F_n\) moves with \(n\), and \(n\) may lie below the uncontrolled threshold \(N_{F_n}\).

Thus the exact missing lemma is a uniform deletion-threshold principle strong enough to compare \(N_F\) with the targets whose repeated summands generate \(F\). Neither the basis hypothesis nor the cited density theorems supplies such control. A finite computation cannot establish that uniformity. This is an (a) rigorous diagnosis of the logical gap, not a claim that no different method can work.

6. Verified state

• (a) Explicit deletion-robust basis with orders \((3,6)\).
• (a) Necessary-and-sufficient finite-group criterion for every

eventually periodic set.

• (a) Both finite-deletion questions answered affirmatively in that

class; the equal-order hypothesis even forces equality of the two orders.

• (d) Exact exhaustive periodic table through modulus \(10\), plus

actual-integer DP.

• (c) No claim that the general problem is solved or that the

construction is literature-new.

PARTIAL: proved a deletion-robust order-3 basis of restricted order 6, completely resolved both finite-deletion questions for eventually periodic bases, and isolated the nonuniform deletion-threshold lemma still missing in general.