← All problems

Erdős Problem #586 — Primitive covering systems

46 years old · traced to

For integers aa and d>1d>1, write a+dZ={a+nd:n∈Z}a+d\mathbb{Z}=\{a+nd:n\in\mathbb{Z}\} for an arithmetic progression. A covering system here is a finite family ai+diZa_i+d_i\mathbb{Z}, 1≤i≤k1\le i\le k, whose union is Z\mathbb{Z}. The intended question is whether such a system can have no divisibility relation between distinct moduli; explicitly, is there a family satisfying

⋃i=1k(ai+diZ)=Zanddi∤dj for all distinct i,j?\bigcup_{i=1}^{k}(a_i+d_i\mathbb{Z})=\mathbb{Z} \quad\text{and}\quad d_i\nmid d_j\text{ for all distinct }i,j?

Erdős Problem #586 Balister et al. (2022)

The restriction di>1d_i>1 excludes a degenerate literal exception: if modulus 11 and a one-member family are allowed, the progression Z\mathbb{Z} 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.

Source: 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

Never refreshed

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.