Erdős problem #791 — wave 7m report

Accessed: 2026-07-27 (UTC)

Authoritative page: erdosproblems.com/791

Standalone verifier: runs/erdos791_wave7m_reverify.py

Claim-label convention

Every substantive claim below is tagged as requested:

• (a) elementary-rigorous — proved directly here;
• (b) rigorous-modulo-named-theorem — a precise translation of a cited result;
• (c) plausible/structural-unverified — not used as a theorem;
• (d) computational-only — established by the finite exhaustive run or direct browser inspection.

0. Mandatory live-page and collision check

(d) I fetched the live page through the Bright Data browser path, not datacenter

curl. I also followed the discussion link, expanded every bibliography record, and

saved full-page screenshots during the run. The page displayed:

• status OPEN;
• 0 claimed proofs;
• Currently working on this problem: None;
• Interested in collaborating: None;
• 2 comments;
• last-edited line: 24 September 2025.

Thus the mandatory stop condition did not fire.

Verbatim live statement

> Let \(g(n)\) be minimal such that there exists \(A\subseteq\{0,\ldots,n\}\) of size \(g(n)\) with \(\{0,\ldots,n\}\subseteq A+A\). Estimate \(g(n)\). In particular is it true that \(g(n)\sim 2n^{1/2}\)?

Live-page results and comments

(d) The page calls such an \(A\) a finite additive \(2\)-basis and lists

for some small \(c>0\), attributed to Rohrbach, and the current bounds

It attributes the lower bound to Yu [Yu15], the upper bound to Kohonen [Ko17],

and the disproof of \(g(n)\sim2n^{1/2}\) to Mrose [Mr79], whose construction

gives the \(7/2\) upper constant.

(d) The oldest comment, by otato at 06:44 on 24 September 2025, asks how

to prove

(d) Thomas Bloom replied at 07:25 that the comment prompted him to find the

literature and update the description with the best-known bounds and references.

Neither comment claims a proof or says that its author is working on the problem.

(d) Expanding the page's five bibliography records gave:

1. [Er73] P. Erdős, Problems and results on combinatorial number theory,

in A Survey of Combinatorial Theory (1973), 117–138, MR 0360509.

2. [Ro37] H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie,

Math. Z. (1937), 1–30, MR 1545658.

3. [Yu15] G. Yu, A new upper bound for finite additive \(h\)-bases,

J. Number Theory (2015), 95–104, MR 3360330.

4. [Ko17] J. Kohonen, An improved lower bound for finite additive 2-bases,

J. Number Theory (2017), 518–524, MR 3597407.

5. [Mr79] A. Mrose, *Untere Schranken für die Reichweiten von

Extremalbasen fester Ordnung*, Abh. Math. Sem. Univ. Hamburg (1979),

118–124, MR 537452.

1. Primary-source audit

(b) The original Erdős paper,

page 131, states the positive-integer normalization of the problem, reports

\(\sqrt{2n}

lower estimate, and records Rohrbach's \(2\sqrt n\) conjecture.

(b) The EuDML record and full text for Rohrbach

verify the 1937 paper, volume 42, pages 1–30. Its DOI is

10.1007/BF01160061.

(b) The publisher record for Yu

verifies the title, author, Journal of Number Theory 156 (2015), pages 95–104,

and DOI 10.1016/j.jnt.2015.04.007.

The publisher abstract says that the paper improves lower estimates for the

cardinality of finite \(h\)-bases. Kohonen's author manuscript explicitly

attributes to Yu the numerical theorem

(b) Kohonen's author manuscript, arXiv:1606.04770v2

and the journal record verify

The manuscript gives the explicit placement

using 42 elementary segments to cover 510 consecutive blocks. Thus its constant

is \(510/42^2=85/294\), not merely a decimal assertion.

(b) Kohonen also explicitly records Mrose's

\(\liminf R(k)/k^2\ge2/7\), which translates to the \(7/2\) constant on the

\(g\)-side. The journal bibliography verifies the 1979 Mrose citation above.

(b) A current check found two especially relevant 2026 primary sources:

• Nathanson, [Problems in additive number theory, VII,

arXiv:2605.26425v3](https://arxiv.org/abs/2605.26425), defines the dual

minimum-size function \(k_h(n)\), says that it has many open problems, cites

Erdős problem #791, and still cites Yu and Kohonen for this literature.

• Weltge–Zyhalko, [On the number of finite additive 2-bases,

arXiv:2605.19449v2](https://arxiv.org/abs/2605.19449), concerns the number of

bases, not the extremal minimum cardinality, and claims no improved constant

for \(g(n)\).

(d) Exact-title, constant, citation, and postage-stamp searches through

2026 found no later peer-reviewed paper claiming that #791 is solved or

improving the two live-page constants.

(c) One search hit must not be silently discarded: Sultan Alzahrani's

officially archived 2016 Kent State master's thesis,

The Upper Bound of Finite Additive 2-Bases,

states \(\limsup R(k)/k^2\le0.4550452314\), nominally stronger than Yu.

The final numerical step is reported as a Maple calculation. I did not validate

the thesis's full Fourier-analytic argument from scratch; it is not cited as the

record in the live 2025 page or Nathanson's 2026 survey. Therefore I classify it

as unverified and do not replace the authoritative \(0.4585\) constant with it.

(d) OEIS A066063 is exactly the sequence \(g(n)\)

and lists terms only through \(n=50\). This is not the actual exact-computation

frontier: Kohonen's 2017 paper states that the dual maximal ranges are known

through \(R(25)=212\). Accordingly, the computation below is an independent,

from-scratch verification in a concrete regime, not a claim of a new literature

record.

2. Exact dual reduction

Define

(a) Then

Indeed, this is the same feasibility condition with the two optimization

variables interchanged. Elements of \(A\) above \(n\) cannot occur in a

nonnegative sum at most \(n\), so the page's restriction \(A\subseteq[0,n]\)

loses nothing.

(a) For \(n\ge1\), every feasible \(A\) contains both 0 and 1:

representing 0 forces \(0=0+0\), and then representing 1 forces \(1=0+1\).

(a) The reciprocal translations of the literature constants are

and

The last strict inequality is precisely why Mrose's construction rules out

\(g(n)\sim2\sqrt n\), which would force \(g(n)^2/n\to4\). These arithmetic

translations are recomputed with exact Fraction objects by the verifier.

3. Exact finite result

Result

(d) The standard-library-only exhaustive computation proves

Equivalently,

Explicit lower-bound witnesses for \(R(k)\)

(a) Direct addition verifies each row below: its set has \(k\) elements,

covers every integer from 0 through the displayed \(R(k)\), and misses

\(R(k)+1\).

| \(k\) | \(R(k)\) | witness \(A\) |

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

| 1 | 0 | \(\{0\}\) |

| 2 | 2 | \(\{0,1\}\) |

| 3 | 4 | \(\{0,1,3\}\) |

| 4 | 8 | \(\{0,1,3,4\}\) |

| 5 | 12 | \(\{0,1,3,5,6\}\) |

| 6 | 16 | \(\{0,1,3,5,7,8\}\) |

| 7 | 20 | \(\{0,1,3,5,6,13,14\}\) |

| 8 | 26 | \(\{0,1,3,5,7,8,17,18\}\) |

| 9 | 32 | \(\{0,1,3,5,7,9,10,21,22\}\) |

| 10 | 40 | \(\{0,1,3,4,9,11,16,17,19,20\}\) |

| 11 | 46 | \(\{0,1,2,3,7,11,15,19,21,22,24\}\) |

| 12 | 54 | \(\{0,1,3,5,6,13,14,21,22,24,26,27\}\) |

| 13 | 64 | \(\{0,1,3,4,9,11,16,21,23,28,29,31,32\}\) |

(a) Appending 65 to the last set covers 65 as \(0+65\), so it gives the

14-element witness for \(g(65)\le14\).

Exhaustive upper-bound proof for \(R(k)\)

(a) The search is complete for the following reason. At a state with

selected set \(S\), choose an uncovered target \(s\). Any successful extension

must contain an unordered pair \(\{a,b\}\) with \(a+b=s\). The program branches

over every such pair that fits in the remaining cardinality budget and adds its

missing member or members. A diagonal pair \(a=a\) correctly consumes one new

element. Thus every possible successful extension occurs below some branch.

(a) There is one additional safe prune. If \(c=|S|\) and at most \(r\)

elements remain, the new elements create at most

unordered pairs involving a new element. Each pair covers at most one previously

uncovered sum. A node with more uncovered targets than this is impossible.

Memoizing a failed selected-set mask is safe because its sumset is determined

only by that mask.

(d) The exhaustive runs at the first forbidden target \(R(k)+1\) returned:

| \(k\) | forbidden target | DFS nodes | failed states | seconds |

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

| 1 | 1 | 1 | 1 | 0.000 |

| 2 | 3 | 1 | 1 | 0.000 |

| 3 | 5 | 3 | 3 | 0.000 |

| 4 | 9 | 6 | 6 | 0.000 |

| 5 | 13 | 21 | 20 | 0.000 |

| 6 | 17 | 81 | 74 | 0.001 |

| 7 | 21 | 405 | 365 | 0.004 |

| 8 | 27 | 1,645 | 1,466 | 0.029 |

| 9 | 33 | 7,621 | 6,690 | 0.099 |

| 10 | 41 | 25,066 | 21,139 | 0.382 |

| 11 | 47 | 183,390 | 155,187 | 3.057 |

| 12 | 55 | 919,989 | 763,376 | 17.476 |

| 13 | 65 | 3,335,360 | 2,706,135 | 75.034 |

(d) The full final run used 96.16 user CPU seconds, 96.53 wall seconds, and

336,508 KiB peak resident memory on this VM. It exited 0 with

VERIFIED: exact g(n) for every 0<=n<=65.

4. Reproduction and code

Run from the repository root:

python runs/erdos791_wave7m_reverify.py

For a faster partial rerun:

python runs/erdos791_wave7m_reverify.py --max-k 12
python runs/erdos791_wave7m_reverify.py --witnesses-only

(d) The checked standalone source has 294 lines and SHA-256

f972bc610737dd3aab37b12bf75f13293f22261b3d8a00b9c2183188a88660de.

It imports only Python's standard library. The complete executable code is in

runs/erdos791_wave7m_reverify.py; the mathematically essential recursion is:

def dfs(mask: int, covered: int) -> int | None:
    nonlocal nodes
    nodes += 1
    if covered == full:
        return mask
    if mask in failed:
        return None

    c = mask.bit_count()
    r = k - c
    if (full ^ covered).bit_count() > c * r + r * (r + 1) // 2:
        failed.add(mask)
        return None

    # Choose the uncovered sum with the fewest feasible representations.
    best_key = None
    branch_pairs = None
    for s in range(1, n + 1):
        if (covered >> s) & 1:
            continue
        feasible = []
        for a, b in pairs_by_sum[s]:
            missing = int(not ((mask >> a) & 1))
            if b != a:
                missing += int(not ((mask >> b) & 1))
            if missing <= r:
                feasible.append((a, b))
        if not feasible:
            failed.add(mask)
            return None
        key = (len(feasible), -s)
        if best_key is None or key < best_key:
            best_key = key
            branch_pairs = tuple(feasible)

    options = []
    seen_children = set()
    for a, b in branch_pairs:
        child_mask, child_covered = add_pair_coverage(mask, covered, a, b, n)
        if child_mask not in seen_children:
            seen_children.add(child_mask)
            gain = (child_covered & ~covered).bit_count()
            options.append((gain, child_mask, child_covered))

    for _gain, child_mask, child_covered in sorted(options, reverse=True):
        answer = dfs(child_mask, child_covered)
        if answer is not None:
            return answer

    failed.add(mask)
    return None

5. What this does and does not resolve

(a) The duality above isolates the asymptotic problem exactly: determine the

quadratic growth of \(R(k)\), then invert it. The present exact finite table does

not imply convergence of \(R(k)/k^2\), nor any improvement to a limsup or liminf.

(b) On the universal-bound side, an improvement needs a uniform theorem

for some \(\delta>0\). In the Fourier approach described by Yu and Habsieger,

the missing ingredient is a sharper uniform inequality for the representation

function/Fourier coefficients, not more small-\(k\) data.

(b) On the construction side, an improvement needs bases with

Within Kohonen's generalized-Mrose framework this becomes the finite placement

problem of finding \(\ell\) elementary segments that cover \(m\) consecutive

blocks with \(m/\ell^2>85/294\). Kohonen reports that a simple search through

\(\ell\le17\) found no ratio above \(2/7\); the successful \(85/294\) placement

uses \((\ell,m)=(42,510)\). Failure in a bounded placement search would not rule

out larger placements or different constructions.

(c) The measured node sequence shows why the transparent DFS is a checker,

not an asymptotic tool. Extending it by a few \(k\)-values is plausible with

engineering, but extrapolating those finite values to a constant would be

mathematically invalid. Reaching the known exact frontier \(R(25)=212\), let

alone moving it, calls for the specialized meet-in-the-middle/pruning algorithms

in the postage-stamp literature rather than this verifier.

(a) Consequently no uniformity or finiteness step closing #791 has been

claimed here. The verified contribution is the exact, independently reproducible

finite regime \(0\le n\le65\), together with a precise inverse reduction and a

clear statement of the two missing asymptotic advances.

PARTIAL: independently verified the exact table g(n) for every 0<=n<=65; #791 remains open between the Yu and Kohonen asymptotic constants.