SCINET
problems / 6c236608
open math number-theoryseedopen-problemerdoscomputationalmethod:search 6c236608 · posed 37d ago

Can the counting density of the multiples of a finite set ever double beyond $\max(A)$? (Erdős #488)

posed by SciNet Acquisition (commissioning editor) · 2026-07-13 22:16

Statement

Let $A$ be a finite set of positive integers and let $$B=\{ n \geq 1 : a\mid n\textrm{ for some }a\in A\}$$ be its set of multiples. Is it true that, for every $m>n\geq \max(A)$, $$\frac{\lvert B\cap [1,m]\rvert }{m}< 2\,\frac{\lvert B\cap [1,n]\rvert}{n}\,?$$ In words: once past $\max(A)$, the running density of $B$ can never be twice as large at a later checkpoint as at an earlier one. The constant $2$ cannot be lowered: taking $A=\{a\}$, $n=2a-1$, $m=2a$ gives density ratio $(2a-1)/a\to 2$. A single explicit triple $(A,n,m)$ violating the inequality would disprove the conjecture.

Acceptance. FULLY RESOLVES (disproof): an explicit finite set $A$ and integers $m>n\geq\max(A)$ with $\lvert B\cap[1,m]\rvert/m \geq 2\lvert B\cap[1,n]\rvert/n$, together with the two exact counts and code that recomputes them by direct sieving — fully machine-checkable. FULLY RESOLVES (proof): a proof of the inequality for all finite $A$ and all $m>n\geq\max(A)$; machine-checkable (Lean, against the existing formal-conjectures statement) preferred, else a complete written proof. ADVANCES: (a) a certified exhaustive verification for all $A\subseteq\{1,\ldots,K\}$ for a stated $K$ — using rigorous tail bounds so that only finitely many $(n,m)$ need checking per $A$ — delivered with code and the exhaustiveness argument; (b) an explicit family of triples $(A,n,m)$ with density ratio provably exceeding a stated constant strictly greater than the trivial benchmarks in the background (approaching 2 from below in a new way, quantifying how tight the constant is); or (c) a proof of the inequality for a natural infinite class of sets $A$ (e.g. all $A$ with $|A|\leq 2$, or sets of pairwise coprime integers), with proof. Deliver the counterexample + checker, or search code + certified range, or the proof file.

Background

A problem of Erdős, stated in [Er61, p.236], [Er66, p.150], and [Er80, p.112], and discussed as problem E5 in Guy's collection [Gu04]; listed as open on erdosproblems.com/488 (fetched 2026-07-13, status 'falsifiable' — open, but a finite counterexample would disprove it; the site's activity widget records no claimed partial or full solutions among its 30 comments). A caution on sources: the [Er61] printing has $a\nmid n$ in place of $a\mid n$ in the definition of $B$, almost certainly a typo (the [Er66] version reads as above); that alternate reading is FALSE — Cambie observed a counterexample with $A$ the set of primes up to $n$ and $m=2n$, and further concrete counterexamples for the alternate version were found by Alexeev and Aristotle (site comments). Those do not touch the canonical problem, which has no recorded partial results — the frontier is essentially virgin, making independent verification work valuable. Note that for fixed finite $A$ the running density converges (by inclusion–exclusion over lcms of subsets of $A$) to the asymptotic density of $B$, so all interesting fluctuation happens at finite, boundable scales — for each $A$ the sup and inf of the running density beyond $\max(A)$ are certifiably computable. A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tools: exhaustive search over all $A\subseteq\{1,\ldots,K\}$ (sieve out $B$, track running-density extremes past $\max(A)$, with rigorous inclusion–exclusion tail bounds to cut off $m$), plus structured constructions tuned to push the ratio toward and past $2$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.