Skip to content

Erdős Problem #33

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

An additive complement to the squares is a set \(A\) such that every sufficiently large integer can be written as \(a+m^2\) for some \(a\in A\) and integer \(m\ge0\). Erdős Problem #33 asks for the best possible constants governing the size of a very sparse such \(A\), expressed by the limsup and liminf of its counting function divided by \(\sqrt N\).

The source statement requires representation of all sufficiently large integers. The frozen Lean helper instead asks for a representation of every nonnegative integer. These properties are not equivalent for a fixed set, although finite changes to \(A\) can preserve the asymptotic optimization.

A small example

If \(A\) represents every integer \(k\ge K\) as \(a+m^2\), adjoin the finite set \(F=\{0,1,\ldots,K-1\}\) and put \(B=A\cup F\). All previously representable integers remain covered; each smaller \(k\) is represented by \(a=k\) and \(m=0\). Thus \(B\) covers every nonnegative integer.

The counting functions of \(A\) and \(B\) differ by at most \(K\), and

\[ \frac{K}{\sqrt N}\longrightarrow0. \]

So this repair does not alter either asymptotic normalized limsup or liminf. It does not mean that the original \(A\) already covered every integer.

What is known

The maintained problem page records an open optimization and attributes finite upper constructions and lower bounds to the literature, including later work by van Doorn. The GCL audit did not independently inspect the relevant primary pages, so no optimal numerical constant is asserted here.

GCL's current state

The frozen source file uses a stronger all-integers predicate than the historical eventual-cover formulation and contains unfilled research proofs. Audit #1302 proves the finite-augmentation bridge and identifies the asymptotic-normalization assumptions. It supplies no proof of the optimal constant.

What remains

Determine the optimal normalized counting-function bounds for genuine square-complement sets. Formal source comparisons must keep the fixed-set distinction intact, even though adding finitely many elements leaves the asymptotic constants unchanged.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1302 — 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