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.

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

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

3. Hennecart constructed an order-\(2\) basis of restricted order \(4\).

4. Squares have orders \((4,5)\), ordinary/restricted, while triangular

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

5. 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.

6. 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:

| residue | ordinary pattern | terms |

|---:|:---|---:|

| 0 | \(0\) | 1 |

| 1 | \(3+4+4\) | 3 |

| 2 | \(0+6+6\) | 3 |

| 3 | \(3\) | 1 |

| 4 | \(0+4\) | 2 |

| 5 | \(3+6+6\) | 3 |

| 6 | \(0+6\) | 2 |

| 7 | \(3+4\) | 2 |

| 8 | \(0+4+4\) | 3 |

| 9 | \(3+6\) | 2 |

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:

| residue | restricted pattern | terms |

|---:|:---|---:|

| 0 | \(0\) | 1 |

| 1 | \(3+3+3+3+3+6\) | 6 |

| 2 | \(3+3+6\) | 3 |

| 3 | \(3\) | 1 |

| 4 | \(0+4\) | 2 |

| 5 | \(3+3+3+6\) | 4 |

| 6 | \(0+6\) | 2 |

| 7 | \(3+4\) | 2 |

| 8 | \(3+3+3+3+6\) | 5 |

| 9 | \(3+6\) | 2 |

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:

| exception choice | least \(a\) | least \(a+c\) |

|:---|---:|---:|

| none | 7 | 7 |

| \(4\) | 9 | 10 |

| \(6\) | 5 | 6 |

| \(4+6\) | 7 | 9 |

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\).

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

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

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

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

4. 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.

| \(m\) | maximum restricted order, grouped by ordinary order \(h\) |

|---:|:---|

| 2 | \(1\mapsto1,\ 2\mapsto2\) |

| 3 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto3\) |

| 4 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto3,\ 4\mapsto4\) |

| 5 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto4,\ 4\mapsto4,\ 5\mapsto5\) |

| 6 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto4,\ 4\mapsto5,\ 5\mapsto5,\ 6\mapsto6\) |

| 7 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto5,\ 4\mapsto6,\ 6\mapsto6,\ 7\mapsto7\) |

| 8 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto5,\ 4\mapsto6,\ 5\mapsto7,\ 7\mapsto7,\ 8\mapsto8\) |

| 9 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto5,\ 4\mapsto7,\ 5\mapsto8,\ 8\mapsto8,\ 9\mapsto9\) |

| 10 | \(1\mapsto1,\ 2\mapsto2,\ 3\mapsto6,\ 4\mapsto8,\ 5\mapsto8,\ 6\mapsto9,\ 9\mapsto9,\ 10\mapsto10\) |

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:

| residue | ordinary | restricted |

|---:|---:|---:|

| 0 | 1 | 1 |

| 1 | 3 | 6 |

| 2 | 3 | 3 |

| 3 | 1 | 1 |

| 4 | 2 | 2 |

| 5 | 3 | 4 |

| 6 | 2 | 2 |

| 7 | 2 | 2 |

| 8 | 3 | 5 |

| 9 | 2 | 2 |

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.