Erdős Problem #791
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A finite additive two-basis generates every integer from zero through n using the sum of two members, where both members may be equal. The goal is the smallest possible basis and its growth rate.
For every n, let g(n) be smallest |A| among A subset {0,...,n} such that every integer 0,...,n belongs to A+A (repetitions allowed). This is a finite additive 2-basis. General asymptotic estimation remains OPEN, but the specific conjecture g(n)~2sqrt(n) is already disproved by better constructions.
A small example
For n=5, the set A={0,1,2,3} supplies every integer up to 5 as a sum of two selected elements. In particular 2+2=4 is legal, so the distinct-summand convention would change the problem.
Finite example n=5 and A={0,1,2,3}: its pair sums include 0,1,2,3,4,5, so g(5)<=4. Distinctness between summands is NOT required: 2+2=4. Simple counting gives at most |A|(|A|+1)/2 unordered sums so g(n)(g(n)+1)/2 >= n+1; asymptotically g(n)>=sqrt(2n)(1-o(1)), weaker than best published lower constant.
What is known
Maintained https://www.erdosproblems.com/791 OPEN, attributes (2.181...+o(1))n <=g(n)^2 <=(3.458...+o(1))n to Yu [Yu15] and Kohonen [Ko17]. Mrose [Mr79] previously gave g(n)^2<=3.5n, ruling out g(n)~2sqrt(n) since this would require g(n)^2/n->4. The older Rohrbach bound has larger upper constant 4. Source statements are catalogue-attributed; original Mrose, Yu, Kohonen full publications have not been read.
GCL's current state
The original authenticated RESULT/1 source return has historical disposition STATUS_CONFLICT. This status and the original research exceptions are preserved, not silently converted into a theorem verdict. The maintained Erdős source and source-specific mathematical definitions were reviewed, and this article is editorially reviewed as a source-exception-annotated explanation under EC-BULK-005-R10, effective only after the exact-hash protected admission merges.
Source interpretation and unresolved mathematical qualification: Known construction rules out the proposed 2sqrt(n) subquestion, but the general additive basis optimum still has an open sharp constant.
The explanation is accepted for publication of established background, examples, and explicitly attributed current claims. It does not establish or formally certify the disputed original theorem, external model-assisted proof, historical interpretation, or any unreplayed Lean kernel file. Original source-fidelity and proof-review research holds remain.
What remains
Next: exhaustive finite minimum-basis enumeration for n<=12, validate exact 0..n coverage and count pairs with repetition, source-lock Yu/Kohonen/Mrose coefficient statements, preserve OPEN_GENERAL with DISPROVED_SECONDARY_ASYMPTOTIC.
The previously completed public MathJax readback confirms rendering only; historical theorem provenance and editorial source qualifications still require adjudication.
Sources and claim boundaries
- Maintained Erdős Problem #791 and authenticated source-return record.
- Pinned teorth/erdosproblems source commit
536408716724a2402bdfa7c1d764bf83d64a8c89atdata/problems.yaml. Primary historical references are identified by their bibliography keys in the original return; any not directly inspected are explicitly unverified. - Source review: PARTIAL. Independent mathematical critical review: PENDING. Protected merge: NONE. Public browser MathJax: NOT VERIFIED. GCL theorem certification: NONE.
Qualified editorial critical review: R10 source-exception dossier. The source-semantic exception is visible and its original research hold remains. Publication classification: REVIEWED EXPLANATORY ARTICLE WITH UNRESOLVED SOURCE/PROOF QUALIFICATIONS. Independent theorem proof or Lean certification: NOT CLAIMED.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2062 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.