Skip to content

Erdős Problem #221

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

Can one choose a sparse subset \(A\) of the positive integers so that every sufficiently large integer is the sum of a power of two and an element of \(A\)? Specifically, Erdős asks for

\[ |A\cap[1,N]|\ll\frac{N}{\log N} \]

and representations \(m=2^k+a\) with \(k\ge0\) and \(a\in A\). The power of two is one summand, not a product or an arbitrary smooth number.

A small example

If \(A\) contains every positive integer, then any sufficiently large \(m\) has the representation \(m=1+(m-1)\), but \(|A\cap[1,N]|=N\) fails the required sparseness. A useful construction must simultaneously ensure coverage of all sufficiently large integers and retain only about one out of every \(\log N\) candidates.

For \(m\ge2\), every possible representation has \(2^k<m\) and \(a=m-2^k>0\). Checking a single power of two would be incomplete; the covering condition is existential over all nonnegative \(k\).

What is known

PROVED. Ruzsa (1972) found a set meeting the conjectured order. The maintained Erdős #221 displays an ingenious construction based on numbers \(5^t m\) selected when \(5^t\) exceeds a small constant times \(\log m\), plus two adjacent shifts. The key number-theoretic ingredient is that two is a primitive root modulo \(5^t\) for every \(t\ge1\).

Lorentz (1954) had established the weaker cardinality bound \(N\log\log N/\log N\). In a later refinement, Ruzsa (2001) constructed an exact additive complement with

\[ |A\cap[1,N]|\sim\frac{N}{\log_2 N}. \]

Here \(\log_2N\) means the base-two logarithm, so the main term is \((\log 2)N/\log N\). This sharp asymptotic cardinality is stronger than the original big-oh statement.

GCL's current state

Pinned and maintained classification: PROVED. Original issue #1490. The displayed residue construction and proof ingredients are source-attributed; neither the complete counting argument nor any third-party formalization was independently replayed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task verifies that \(2\) generates the units modulo \(5^t\) for \(t=1,2,3,4\) by exact order calculations, and checks finite coverage of sample targets for a correctly normalized Ruzsa construction. Acceptance: the shifts \(\{0,1\}\) are included, \(k=0\) is allowed, and finite coverage is not misreported as an asymptotic density result. The full source proof requires a separate audit of the sparse counting bound.

Sources and claim boundaries

No new additive-complement construction, complete independent density proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1490 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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