Skip to content

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:

\[ \sum_{t=2}^{2N}r_F(t)=k^2. \]

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

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.

Back to catalogue · Compendium introduction