Maximum density of integers covered by one congruence for each modulus $n_1<\cdots<n_r$ (Erdős #278)
Statement
Let $A=\{n_1<\cdots<n_r\}$ be a finite set of positive integers. Choosing one residue class $a_i\pmod{n_i}$ for each $i$, what is the maximum (natural) density of the set of integers covered by $\bigcup_i\{x : x\equiv a_i\pmod{n_i}\}$, as a function of $A$? (Erdős and Graham also asked whether the minimum density is achieved when all the $a_i$ are equal; that part is settled — see background.)
Acceptance. FULLY RESOLVES: a theorem, with proof, answering Erdős and Graham's question 'what is the maximum density': an exact formula or effective characterization of the maximum covered density as a function of $A=\{n_1<\cdots<n_r\}$ — machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES: a provably correct algorithm computing the maximum density substantially faster than brute-force enumeration over all residue tuples, with implementation and correctness proof; an exhaustive certified table of maximum densities for all modulus sets $A$ with $\mathrm{lcm}(A)$ (or $\max A$) up to an explicit bound, with reproducible code and an exhaustiveness certificate; a characterization, with proof, of the sets $A$ attaining the trivial upper bound $\min(1,\sum 1/n_i)$ (i.e., admitting pairwise disjoint choices); or nontrivial general upper/lower bounds on the maximum density strictly improving the trivial ones stated in the background, with proof. Deliver the formula/characterization with proof, or the code plus certified tables.
Background
Posed by Erdős and Graham [ErGr80, p.28]; listed as open on erdosproblems.com/278 (fetched 2026-07-13, status 'open', tagged 'number theory | covering systems'; page last edited 20 January 2026). Since the union of the chosen classes is periodic modulo $\mathrm{lcm}(n_1,\ldots,n_r)$, the covered density is a rational number computable by a finite (though potentially enormous) check for each residue choice; the problem asks for the extremal behaviour of the maximum over all choices, as a function of the modulus set $A$. The companion minimum question is resolved: Simpson [Si86] observed that the covered density is always at least $\sum_i \frac{1}{n_i}-\sum_{i<j}\frac{1}{[n_i,n_j]}+\sum_{i<j<k}\frac{1}{[n_i,n_j,n_k]}-\cdots$ (square brackets denoting least common multiples), and that this is achieved when all the $a_i$ are equal — settling the second question affirmatively. For the maximum, the trivial bound is $\min(1,\sum_i 1/n_i)$, attained exactly when the residue classes can be chosen pairwise disjoint. Cambie [arXiv:2508.18270, 2025] has recently argued that this maximum admits no clean general formula, relating it to knapsack-type hardness with non-equivalent expressions arising for different modulus structures, though the problem is still listed as open. Venue-adjacent (distinct): the covering-system problems Erdős #7 (all moduli odd) and Erdős #273 (moduli of the form $p-1$). The attacker's tools: exact optimization per modulus set — exhaustive enumeration over the $\mathrm{lcm}$-period, or ILP/SAT encodings maximizing coverage — building certified tables over all small $A$ to ground and test conjectural formulas, together with inclusion-exclusion and structural analysis of when the trivial upper bound is attained.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #278 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.