Erdős Problem #691
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.
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
Let A be a set of positive integers and let M_A={n≥1: a divides n for at least one a∈A}, the union of their multiples. Erdős asks for a general necessary and sufficient condition on A such that M_A has natural density one. Such sets A are called Behrend sequences. The general problem is OPEN; the classical reciprocal-sum test holds in important special cases, but not for arbitrary sets with overlapping divisibility.
A small example
Take A={2p:p prime}. Then Σ_{a∈A}1/a=(1/2)Σ_p1/p diverges. Nevertheless M_A consists of every even integer ≥4, and no odd integer, so its natural density is exactly 1/2. Thus divergence of Σ_{a∈A}1/a is NOT sufficient for arbitrary A. For A={2,3}, inclusion-exclusion gives density 1/2+1/3−1/6=2/3. If 1∈A then M_A is all positive integers, so density one trivially.
What is known
For A a set of pairwise coprime integers greater than one, the CRT turns nondivisibility for finite prefixes into the product ∏{a∈A}(1−1/a), giving the familiar density-one criterion Σ{a∈A}1/a=∞; passing from finite prefixes to the infinite density requires justification, not merely a formal product. The maintained source describes lacunary block sequences and cites a theorem by Gérald Tenenbaum [Te96]: under two-sided bounds 1<C1<n_{i+1}/n_i<C2 and block widths η_i=i^(−β), the threshold is β=log 2 (strict cases β< and β>). Without that two-sided growth assumption, the claimed threshold can fail. The main necessary-and-sufficient characterization remains OPEN and the original Te96 proof was not independently inspected.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: general behrend characterization open; divergent reciprocal sum not sufficient arbitrary a. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Prove an exact density result for one new structured A by a finite-CRT limiting argument, beginning with pairwise coprime A, and specify all tail-density conditions required; verify that the A={2p} example invalidates the naive global reciprocal sum criterion. Then inspect Tenenbaum's original 1996 theorem for the block-sequence growth requirements. Stop after one quantified lemma.
Sources and claim boundaries
Maintained problem #691; https://www.erdosproblems.com/691 ; historical [Er79e,p.77], Tenenbaum [Te96] not directly inspected. GCL original issue return. Historical source pages and full theorem proofs not uniformly inspected. No novel theorem, full CI, public MathJax readback, protected merge or V2 admission.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1962 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.