Minimum multiplicity of the repeated modulus 9 in covering systems with odd moduli: is $t_9\le 2$, and is the residue arrangement $\{4,5,r\}\pmod 9$ realizable?

A covering system of the integers is a finite collection of residue classes whose union is all of $\mathbb{Z}$ . Erdős's odd covering problem asks whether a covering system exists whose moduli are distinct odd integers greater than 1; it remains open. Bispels, Cohen, Harrington, Lowrance, Pontes, Schaumann, and Wong (arXiv:2507.16135, published in Discrete Mathematics 349 (2026)) studied the variant in which a single odd modulus may repeat: writing $t_k$ for the least number of congruences with modulus $k$ appearing in a covering system whose remaining moduli are distinct odd integers greater than 1 and different from $k$ , they proved $t_9\le 3$ and posed the two linked questions stated here. (Q1) Is $t_9\le 2$ ? A positive answer would also give odd coverings of further combinatorial sequences, such as the Bell numbers. (Q2) Does there exist a covering system containing the congruences $4\pmod 9$ , $5\pmod 9$ , and $r\pmod 9$ for some $r\not\equiv 4,5\pmod 9$ , with all remaining moduli odd, pairwise distinct, greater than 1, and different from 9? A positive answer would imply that the set of sums of three cubes admits an odd covering. Both questions remain open.

Background

A covering system of the integers is a finite set of congruences $a_i\pmod{m_i}$ such that every integer satisfies at least one of them; the integers $m_i>1$ are called the moduli. Covering systems were introduced by Paul Erdős in 1950 (Erdős, 'On integers of the form $2^k+p$ and some related problems', Summa Brasil. Math. 2 (1950), 113–123). Much of the subsequent literature constrains the moduli. The odd covering problem asks whether there exists a covering system whose moduli are all distinct odd integers greater than 1; such a system is called an odd covering. The problem is open. The strongest general constraint, due to Balister, Bollobás, Morris, Sahasrabudhe, and Tiba ('On the Erdős covering problem: the density of the uncovered set', Invent. Math. 228 (2022), 377–414), is that if an odd covering exists, the least common multiple (lcm) of its moduli must be divisible by 9 or 15 — so the moduli 9 or 15 are unavoidable in any prospective odd covering.

One relaxation, initiated by Harrington ('Two questions concerning covering systems', Int. J. Number Theory 11 (2015), 1739–1750) and developed by Harrington, Sun, and Wong ('Covering systems with odd moduli', Discrete Math. 345 (2022), Art. 112936), allows one odd modulus to repeat. For an odd integer $k$ , let $t_k$ denote the smallest nonnegative integer $t$ such that there exists a covering system of the integers in which $k$ is the modulus of exactly $t$ congruences while all other moduli are distinct odd integers greater than 1 and different from $k$ . If an odd covering exists, then $t_k\le 1$ for every odd $k$ ; conversely, $t_k\le 1$ for even a single odd $k$ would itself furnish an odd covering, since a covering using $k$ at most once already has all moduli pairwise distinct, so lowering the $t_k$ is a graded approach to the odd covering problem. Known bounds before the source paper included $t_3\le 2$ (Harrington 2015) and $t_p\le p-5$ for all primes $p\ge 23$ (Harrington–Sun–Wong 2022), whose constructions are specified by tree diagrams — hierarchical lists in which each branch splits an uncovered residue class into classes modulo products of further primes and prime powers.

A companion direction, due to Filaseta and Harvey ('Covering subsets of the integers by congruences', Acta Arith. 182 (2018), 43–72), asks which subsets $S\subseteq\mathbb{Z}$ admit an odd covering, i.e., are covered by finitely many congruences with distinct odd moduli greater than 1; they showed the primes, the sums of two squares, and the Fibonacci numbers do.

The source paper (Bispels et al., arXiv:2507.16135) extends the $t_k$ program to composite $k$ , proving $t_9\le 3$ (with the modulus 9 used in the congruences $0,3,6\pmod 9$ ), $t_{15}\le 4$ , $t_{21}\le 5$ , $t_{25}\le 8$ , $t_{49}\le 22$ , and $t_p\le p-5$ for primes $p\ge 17$ . From the $t_9\le 3$ construction it derives (Theorem 3.1) that any set of integers having only finitely many terms in two residue classes $j+3,j-3\pmod 9$ has an odd covering, whence the union of the sums of two squares, sums of two cubes, powerful numbers (integers divisible by the square of each of their prime factors), prime powers, derangement numbers (counts of permutations with no fixed point), Fermat numbers (integers of the form $2^{2^m}+1$ ), and perfect numbers (integers equal to the sum of their proper divisors) has an odd covering.

Two residues stay out of reach of that construction, and they are exactly the arithmetically special ones. A cube is congruent to $0,1,$ or $8\pmod 9$ , so a sum of three cubes is never congruent to $4$ or $5\pmod 9$ ; consequently, a covering system containing $4\pmod 9$ , $5\pmod 9$ , and one further congruence $r\pmod 9$ (all other moduli distinct odd, greater than 1, and different from 9) would yield an odd covering of the set of sums of three cubes: deleting the congruences $4\pmod 9$ and $5\pmod 9$ while keeping $r\pmod 9$ leaves a collection of congruences with distinct odd moduli greater than 1 that covers every integer outside the classes $4,5\pmod 9$ , and every sum of three cubes lies outside those classes. The same paper notes that $t_9\le 2$ would give odd coverings of further combinatorial sequences, such as the Bell numbers (the numbers of set partitions), whose residues modulo 9 are constrained. The paper closes by stating that it is unknown whether any such covering system exists, and that establishing $t_9\le 2$ is an obvious direction for improvement; no lower-bound technique is known that separates multiplicity 2 from 3 (the density and abundancy arguments behind the lcm constraints do not count occurrences of a single modulus).

Problem Statement

Determine how few times the modulus 9 must repeat in a covering system with odd moduli, and which arrangements of its residue classes are realizable. Concretely, with $t_k$ defined as the smallest number of congruences with modulus $k$ in a covering system of the integers whose remaining moduli are distinct odd integers greater than 1 and different from $k$ (currently $t_9\le 3$ ):

(Q1) Is $t_9\le 2$ ? That is, exhibit a covering system of the integers in which the modulus 9 is used in at most two congruences and every other modulus is an odd integer greater than 1, with all moduli other than 9 pairwise distinct and different from 9; or prove that no such covering system exists.

(Q2) Does there exist a covering system of the integers containing the congruences $4\pmod 9$ and $5\pmod 9$ together with one further congruence $r\pmod 9$ for some $r\in\{0,1,2,3,6,7,8\}$ , in which the modulus 9 is used in exactly these three congruences and every other modulus is an odd integer greater than 1, pairwise distinct and different from 9? Exhibit such a covering system or prove that none exists for any admissible $r$ .

The two questions are jointly posed and linked: a positive answer to Q1 whose two residue classes modulo 9 are $\{4,5\}$ also answers Q2 positively, while a negative answer to Q1 ( $t_9\ge 3$ ) leaves Q2 open, and vice versa. A positive answer to Q2 would establish that the set of sums of three cubes has an odd covering; a positive answer to Q1 would establish odd coverings of further combinatorial sequences, such as the Bell numbers, as noted in the source paper. Note that $t_9\le 1$ is equivalent to the existence of a full odd covering, since a covering using the modulus 9 at most once already has all moduli pairwise distinct.

References

Chris Bispels, Matthew Cohen, Joshua Harrington, Joshua Lowrance, Kaelyn Pontes, Leif Schaumann, Tony W. H. Wong, 'A further investigation on covering systems with odd moduli', Discrete Mathematics 349 (2026), Article 115013. DOI: 10.1016/j.disc.2026.115013 (arXiv:2507.16135), https://doi.org/10.1016/j.disc.2026.115013
Joshua Harrington, Yewen Sun, Wing Hong Tony Wong, 'Covering systems with odd moduli', Discrete Mathematics 345 (2022), Article 112936. DOI: 10.1016/j.disc.2022.112936 (arXiv:2104.00602), https://doi.org/10.1016/j.disc.2022.112936
Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, Marius Tiba, 'On the Erdős covering problem: the density of the uncovered set', Inventiones mathematicae 228 (2022), 377–414. DOI: 10.1007/s00222-021-01087-5, https://doi.org/10.1007/s00222-021-01087-5
Michael Filaseta, Wilson Harvey, 'Covering subsets of the integers by congruences', Acta Arithmetica 182 (2018), 43–72. DOI: 10.4064/aa161214-4-10, https://doi.org/10.4064/aa161214-4-10
Joshua Harrington, 'Two questions concerning covering systems', International Journal of Number Theory 11 (2015), 1739–1750. DOI: 10.1142/S179304211550075X, https://doi.org/10.1142/S179304211550075X
P. Erdős, 'On integers of the form 2^k+p and some related problems', Summa Brasil. Math. 2 (1950), 113–123. zbMATH: Zbl 0041.36808, https://zbmath.org/?q=an%3A0041.36808
Ibrahim Mian, Shayaan Siddique, 'Kernel-Checked Exclusions for the Erdős-Selfridge Odd Covering Problem: Any Odd Covering of $\mathbb{Z}$ Has lcm Exceeding 10000', arXiv preprint arXiv:2607.25628 (2026). arXiv:2607.25628, https://arxiv.org/abs/2607.25628
Michael Filaseta, Alexandros Kalogirou, 'Covering systems with the sum of the reciprocals of the moduli close to 1', Transactions of the American Mathematical Society (2026). DOI: 10.1090/tran/9670 (arXiv:2407.15280), https://doi.org/10.1090/tran/9670

搜索科普文

Minimum multiplicity of the repeated modulus 9 in covering systems with odd moduli: is $t_9\le 2$ , and is the residue arrangement $\{4,5,r\}\pmod 9$ realizable?

Background

Problem Statement

References