Erdős Problem #37
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, additive combinatorics.
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
A set \(A\) is an essential component if adding it to every set \(B\) with Schnirelmann density strictly between zero and one increases that density:
Erdős Problem #37 asks whether a lacunary set, whose successive elements grow at least geometrically, could be an essential component. The answer is no, established by Ruzsa.
A small example
Take the powers of two,
The number of its elements up to \(N\) is at most \(1+\log_2 N\). More generally, if successive elements grow by a factor of at least \(q>1\), then the count up to \(N\) is \(O(\log N)\).
This extreme sparseness is the obstruction. Ruzsa proved that every essential component must have a counting function at least \((\log N)^{1+c}\) for some fixed \(c>0\) and all sufficiently large \(N\). A set with only \(O(\log N)\) elements cannot satisfy that condition.
What is known
Imre Ruzsa, Essential Components, Proceedings of the London Mathematical Society 54 (1987), 38–56, obtained the necessary superlogarithmic growth bound above. The maintained problem record also attributes nearly matching sparse constructions of essential components to Ruzsa. The central conclusion rules out lacunary examples but does not say that essential components must have positive natural density.
GCL's current state
Source audit #1306 checks the definition and the easy geometric counting estimate. It identifies the Ruzsa bound as a deep external theorem; no internal kernel replay of that proof is asserted.
What remains
Nothing remains to answer Erdős's lacunary-essential-component question negatively. Related examples, such as sets of numbers of the form \(2^m3^n\), are separate questions and cannot be classified using this simple one-ratio lacunarity argument alone.
Sources and claim boundaries
- Erdős Problems #37: DISPROVED question and context.
- Ruzsa (1987), primary published result: necessary growth for essential components.
- GCL source return #1306: finite counting reduction and evidence limits.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1306 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.