Erdős Problem #40
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, 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.
The question in plain language
For a set \(A\) of positive integers, write \(r_A(t)\) for the number of ordered pairs \((a,b)\in A\times A\) with \(a+b=t\). Erdős Problem #40 asks when a set that is fairly large compared with \(\sqrt N\) must have unbounded representation counts \(r_A(t)\). The precise source hypotheses involve a positive function \(g(N)\to\infty\) and a counting-function lower bound on the scale \(\sqrt N/g(N)\).
Ordered means that \((a,b)\) and \((b,a)\) both count when \(a\ne b\). Treating representations as unordered would change the formal statement and numerical bounds.
A small example
For \(F=\{1,2,4\}\) the possible sums \(2,3,4,5,6,8\) occur with ordered multiplicities \(1,2,1,2,2,1\), totaling 9. In general, if \(F=A\cap[1,N]\) has \(k\) elements, exactly \(k^2\) ordered pairs contribute once each:
There are \(2N-1\) possible target sums; therefore some target has at least \(\lceil k^2/(2N-1)\rceil\) representations.
What is known
The finite average bound becomes of size roughly \(1/g(N)^2\) if \(k\) is only on the scale \(\sqrt N/g(N)\), so it cannot by itself force a representation count that grows without bound. This explains why a valid elementary pigeonhole identity is not a proof of the actual density-to-unboundedness conjecture. The maintained registry continues to list the broad question as OPEN.
GCL's current state
The GCL audit #1309 checks the imported ordered-sum convention, exact convolution identity, and the relation to a separately controlled Erdős #28 question. The pinned statement remains unproved; a proof of a conditional implication in the provider does not prove its hypothesis.
What remains
A global argument must exploit more than the average number of representations in each finite prefix. In particular, it must respect the quantifier over arbitrary slowly increasing functions \(g\) and prove a genuine unbounded limsup in the ordered representation counts.
Sources and claim boundaries
- Erdős Problems #40: statement and bibliography.
- GCL source audit #1309: finite double-counting and source-semantics checks, not a proof.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1309 — 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.