Erdős Problem #586 — Primitive covering systems
For integers and , write for an arithmetic progression. A covering system here is a finite family , , whose union is . The intended question is whether such a system can have no divisibility relation between distinct moduli; explicitly, is there a family satisfying
Erdős Problem #586 Balister et al. (2022)
The restriction excludes a degenerate literal exception: if modulus and a one-member family are allowed, the progression is itself a cover with no pair of distinct moduli to compare. With the nontrivial convention above, the answer is no. Balister et al. (2022)
Background
Erdős introduced covering systems in 1950: finite collections of arithmetic progressions that cover every integer. The divisibility question is Schinzel’s conjecture, asking whether every such system has two moduli, one dividing the other. It is closely related to the earlier Erdős–Selfridge problem of whether a covering system can have distinct odd moduli; Schinzel showed that a negative answer to that problem would have consequences for the irreducibility of certain polynomials. Balister, Bollobás, Morris, Sahasrabudhe, and Tiba developed a sieve to study the density of integers left uncovered by collections of progressions, and used it to settle Schinzel’s conjecture. Balister et al. (2022)
References
P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe, and M. Tiba, On the Erdős covering problem: the density of the uncovered set, Inventiones Mathematicae 228 (2022), 377–414.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.