Skip to content

Erdős Problem #26

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory, divisors.

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 Behrend sequence is a set of positive integers such that almost every integer is divisible by at least one member of the set. Erdős Problem #26 asks whether, for every infinite set \(A\) of positive integers, some fixed positive shift \(k\) makes the shifted set \(A+k\) a Behrend sequence.

The public question is disproved. However, there is an important formalization distinction: the pinned Formal Conjectures statement adds a hypothesis that \(A\) is thick, meaning its reciprocal sum diverges. A counterexample using a thin set does not by itself refute that different, restricted statement.

A small example

Consider the infinite set

\[ A=\{2^{2^j}:j\ge1\}=\{4,16,256,\ldots\}. \]

For every positive shift \(k\),

\[ \sum_{a\in A}\frac1{a+k} \le \sum_{j\ge1}2^{-2^j}<\frac13. \]

Among the integers up to \(X\), the proportion divisible by one of the numbers \(a+k\) is at most the sum of their reciprocal frequencies, up to vanishing finite-cutoff errors. Therefore those multiples cannot cover almost all integers, regardless of \(k\). This directly disproves the unrestricted assertion. It does not address the thick-set variant because the reciprocal sum of \(A\) converges.

What is known

Classical work of Davenport and Erdős shows that a Behrend sequence must have divergent reciprocal sum. Ruzsa's congruence constructions provide more informative obstructions; the maintained source also describes later counterexamples to stronger variants, including thick-sequence formulations. These deeper claims require the precise hypotheses of their original constructions, not an extrapolation from the elementary thin example.

GCL's current state

Source audit #1295 compared the maintained public wording with the pinned Formal Conjectures file, where the universal hypothesis explicitly includes a divergent reciprocal series. The frozen file has an unfilled theorem body but links to an external Lean proof. GCL has not replayed the external formal proof or certified the thick-case counterexample.

What remains

The original unrestricted question is resolved negatively. Documentary and formal work must separately verify the stronger thick-sequence counterexample and its source/axiom provenance. Failing to distinguish these versions would allow a correct elementary argument to be falsely presented as a deep theorem.

Sources and claim boundaries

Catalogue and evidence provenance

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