Skip to content

Erdős Problem #1192

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics, additive basis.

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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1192 is OPEN FOR ALL r in the source as of 15 October 2026.

Fix integer \(r\ge2\) and \(A\subseteq\mathbb N\). Let \(f_r(n)\) count ordered solutions \(n=a_1+\cdots+a_r\), each \(a_i\in A\); if the source means unordered solutions, its moment changes and must be normalized. A basis of order \(r\) requires \(f_r(n)>0\) for every sufficiently large integer \(n\), not just positive density of representable integers. The question is whether for each \(r\) there exists such a basis with

\[ \sum_{n\le x}f_r(n)^2=O_r(x) \]

for every large \(x\). One bounded-moment set whose counting function is large enough is not necessarily a basis.

A small example

For the finite set \(A=\{1,2,4,8\}\), exactly 16 ordered pairs exist. Its complete sum histogram has \(\sum_n f_2(n)^2=28\), reproduced by the phase23 fixture. But \(A\) is finite and therefore is not a basis: its representations vanish for every sufficiently large \(n\). This explicitly separates a small second moment from the essential eventual-positive-representation requirement.

What is known

Erdős 1980 [Er80,p.99], https://www.erdosproblems.com/1192, marks the general problem OPEN. Erdős–Rényi probabilistically constructed \(A\) with \(\sum_{n\le x}f_r(n)^2\ll x\) and \(|A\cap[1,x]|\gg x^{1/r}\), but this does not guarantee every large integer is represented. Ruzsa [Ru90] solved the basis case \(r=2\), not all \(r\ge3\). The site has a formalized-statement badge but no certification from the underlying Lean kernel or a claimed proof of all orders.

GCL's current state

Authenticated original issue-bound research source return. The exact bounded example was independently replayed through ci/erdos_compendium_007_phase23_checks.py; general mathematical results here remain explicitly attributed to primary/external proofs, not independently certified by GCL. This manuscript is a local UNACCEPTED editorial draft.

What remains

Read the original Erdős–Rényi and Ruzsa 1990 proofs to check ordered vs unordered counts and the \(r=2\) basis property. Investigate whether a random thickening scheme can preserve bounded second moment and fill every missing integer for \(r\ge3\), with exact second-moment cost and independent mathematical review.

Any critical sample approval, theorem source fidelity, public site rollout and protected V2 admission are separate uncompleted steps.

Sources and claim boundaries

https://www.erdosproblems.com/1192 ; [Er80,p.99],[Ru90], Erdős–Rényi probabilistic additive constructions.

Finite evidence: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE23.json. Frozen original source issue identity retained; independent mathematical source approval PENDING.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2463 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction