PROVED (LEAN) This has been solved in the affirmative and the proof verified in Lean.
Let $n_1<n_2<\cdots$ be an infinite sequence such that, for any choice of congruence classes $a_i\pmod{n_i}$, the set of integers not satisfying any of the congruences $a_i\pmod{n_i}$ has density $0$.
Is it true that for every $\epsilon>0$ there exists some $k$ such that, for every choice of congruence classes $a_i$, the density of integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is less than $\epsilon$?
The latter condition is clearly sufficient, the problem is if it's also necessary. The assumption implies $\sum \frac{1}{n_i}=\infty$. If the $n_i$ are pairwise relatively prime then it is sufficient that $\sum \frac{1}{n_i}=\infty$.
This is true - a proof is given in the comments by Somani (using ChatGPT).
An alternative elementary proof was noted by KoishiChan in the comments: let $\delta$ be the lower density of the set of integers divisible by some $n\in A$, and $\delta_k$ be the density of the set of integers divisible by at least one of $n_1,\ldots,n_k$. A theorem of Davenport and Erdős [DaEr36] states that\[\delta = \lim_{k\to \infty}\delta_k.\]In the present case $\delta=1$ and hence for every $\epsilon>0$ there exists $k$ such that $\delta_k>1-\epsilon$. In other words, the density of those integers not satisfying $a_i\equiv 0\pmod{n_i}$ for $1\leq i\leq k$ is $<\epsilon$. By a theorem of Rogers (which first appeared in print in Chapter V.3 of the book of Halberstam and Roth [HaRo66]) the density of those integers not satisfying any of the congruences $a_i\pmod{n_i}$ for $1\leq i\leq k$ is maximised when $a_i\equiv 0$, which concludes the proof.
Given that both Rogers' result and the Davenport-Erdős theorem mentioned above must have been very familiar to Erdős in 1980, it is strange that this natural argument was overlooked.
This page was last edited 18 January 2026.
| Likes this problem | Dogmachine |
| Interested in collaborating | None |
| Currently working on this problem | None |
| This problem looks difficult | None |
| This problem looks tractable | None |
Additional thanks to: Sarosh Adenwalla, KoishiChan, Neel Somani, and Terence Tao
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #281, https://www.erdosproblems.com/281, accessed 2026-01-31
Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)
-
I have made a brief blog post describing the proof of Rogers' theorem, which is simple but does not appear to be widely available online.
-
With the help of Aristotle and Gemini 3.0 Flash, Neel Somani's GPT 5.2 Pro proof has been formalized in Lean. Type-check it online!
The problem statement is expressed on lines 52 (Erdos281Hyp) and 56 (Erdos281Concl), and the main result is on line 756 (Erdos281). I would also appreciate if someone proficient in Lean could take a peek. Perhaps the proof could be more streamlined and/or reorganized in a cleaner manner.
-
I am looking at chapter V of the work "H. Halberstam and K. Roth, Sequences. Vol. 1, Clarendon Press, 1966." In this books, the authors look at a sequence $A = n_1 < n_2 < \cdots$, let $B(A)$ denote the set of integers divisible by $A$, and let $B_m(A)$ denote the set of integers divisible by the first $m$ elements of $A$. Then
1) By Roger's theorem on pp. 242, $B_m(A)$ achieves the smallest covering density of congruences classes with residue the first $m$ elements of $A$.
2) By Theroem 12 on pp. 258, the logarithmic density of $B(A)$ is equal to the limit of the natural density of $B_m(A)$.
In regard to this problem, if the smallest covering density of congruences classes with residue the first $m$ elements of $A$ is less than $(1 - \epsilon)$, then the density of $B_m(A)$ is at most $(1 - \epsilon)$, hence the logarithmic density of $B(A)$ is less than $(1 - \epsilon)$, so $B(A)$ cannot have natural density $1$. This might also solve this problem.
-
I generated this proposed solution using GPT 5.2 Pro. Sharing here for verification: https://chatgpt.com/share/696ac45b-70d8-8003-9ca4-320151e0816e
Here is a short summary:
Work in the profinite integers $\widehat{\mathbb Z}$ with Haar measure, where "avoid the first k congruences" is a clopen set whose Haar measure equals the usual asymptotic density of avoiding integers. These measures decrease with k to the Haar measure of the infinite intersection. If that limiting measure were greater than 0 for some residue choice, then translation invariance + averaging (Fatou) gives a shift x so that the shifted set corresponds to another residue choice and contains integers of positive upper density, contradicting the hypothesis that every residue choice leaves density 0 uncovered. Hence the limit is always 0, and since the finite‑k densities vary continuously over the compact space of residue choices, Dini/compactness upgrades pointwise $\to$ uniform, giving a single $k(\varepsilon)$.
If there's a gap, I suspect it's in the step $\mu(C)>0\Rightarrow\exists x$ with $(C-x)\cap\mathbb N$ having positive upper density (and in identifying that translate with an admissible residue choice).
-
I would think that for the premise to hold, there has to be an infinite subsequence of pairwise coprime $n_i$, as otherwise there should be a choice of $a_i$ such that the density is not 0, (perhaps $a_i=0$ for all $i$).
All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.