Must the surviving set of an arbitrary congruence sieve have a logarithmic density? (Erdős #25)
Statement
Let $1\le n_1<n_2<\cdots$ be an arbitrary strictly increasing sequence of moduli, and to each $n_i$ associate a residue class $a_i\pmod{n_i}$. Let $A$ be the set of integers $n$ such that for every $i$ either $n<n_i$ or $n\not\equiv a_i\pmod{n_i}$ — that is, $A$ consists of the integers that survive all of the congruence conditions that apply to them (a condition $a_i\pmod{n_i}$ only removes $n$ when $n\ge n_i$). Must the logarithmic density of $A$, namely $$\lim_{x\to\infty}\frac{1}{\log x}\sum_{\substack{n\in A\\ n\le x}}\frac1n,$$ exist for every such choice of moduli and residues?
Acceptance. FULLY RESOLVES: EITHER a complete proof that for every sequence of moduli $n_i$ and residues $a_i$ the logarithmic density of $A$ exists (a Lean/Coq-checkable proof preferred, otherwise a full written proof) — OR an explicit counterexample: a sequence $(n_i,a_i)$ together with a proof that $\frac{1}{\log x}\sum_{n\in A,\,n\le x}1/n$ has two distinct subsequential limits, so the logarithmic density does not exist. ADVANCES: prove that the logarithmic density exists under a stated structural restriction on the moduli (for example bounded moduli, or a growth/multiplicity condition), with a complete proof; OR establish the analogous existence statement for a natural weaker or stronger notion of density; OR give an explicit family of finite truncations whose survivor logarithmic-density partial sums are proved to oscillate by a quantified amount, delivered with the generating construction. Deliver the proof file, or the counterexample sequence plus the oscillation proof.
Background
Posed by Erdős [Er95]. The set $A$ is what remains after sieving $\mathbb{N}$ by an arbitrary family of congruences, with the twist that the congruence $a_i\pmod{n_i}$ is applied only from $n_i$ onward. If the congruences $\{a_i\pmod{n_i}\}$ happened to form a covering system, $A$ would be finite; in general $A$ can be infinite, and the question is whether its logarithmic density is always well-defined. Natural density can fail to exist for adversarially chosen moduli, so the logarithmic (Cesàro-type) average is the more robust notion being probed here. This is a special case of the more general Erdős #486 (erdosproblems.com/486). The problem carries no cash prize. A Lean formalisation exists in the Google DeepMind Formal Conjectures project. Listed as open on erdosproblems.com/25 (fetched 2026-07-13, status 'open', tagged 'number theory'). Attacker's tool: analytic machinery for the existence of logarithmic density of sets defined by congruences (in the spirit of Davenport–Erdős results on sets of multiples), set against explicit adversarial constructions of moduli and residues engineered to make the survivor logarithmic-density partial sums oscillate; small-scale simulation over truncated sieves can probe candidate counterexamples before a full proof.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #25 (T. F. Bloom) | website |
| REF-02 | Lean formalisation — Erdős #25 (Google DeepMind Formal Conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.