Odd incongruent covering systems

 Importance: High ✭✭✭
 Author(s): Erdos, Paul Selfridge, John L.
 Subject: Number Theory » Combinatorial Number Theory
 Keywords: covering system
 Posted by: Robert Samal on: August 4th, 2007

\begin{conjecture} There is no \Def{covering system} whose moduli are odd, distinct, and greater than 1. \end{conjecture}

Let $a(n)$ denote the residue class $\{a+nt \mid t \in \Z\}$. A \emph{covering system} (defined by Paul Erdos in early 1930's) is a finite collection $\{a_1(n_1), \dots, a_k(n_k) \}$ of residue classes whose union covers all the integers. Such systems are easy to find if the moduli are allowed to repeat, or if we allow even numbers. The covering system is called \emph{incongruent} if all the moduli are distinct.

Partial results are known. Berger, Felzenbaum and Fraenkel ([BFF1], [BFF2]) show (among else) that if covering system with odd distinct moduli (greater than 1) exists, $N$ is the least common multiple of $n_1$, \dots, $n_t$, and $p_1$, \dots, $p_s$ are all distinct prime divisors of~$N$, then $$\prod_{i=1}^s \frac{p_i -1}{p_i-2} - \sum_{i=1}^s \frac {1}{p_i-2} > 2 \,.$$

Simpson and Zeilberger [SZ] proved that if in addition $n_1$, \dots , $n_k$ are square-free, then $N$ has at least 18 prime divisors.

Guo and Sun [GS] recently improved this to show that if $N$ is square-free, then it has at least 22 prime divisors.

Bibliography

[BFF1] M. A. Berger, A. Felzenbaum and A. S. Fraenkel, Necessary condition for the existence of an incongruent covering system with odd moduli, Acta. Arith. 45 (1986), 375–379

[BFF2] M. A. Berger, A. Felzenbaum and A. S. Fraenkel, Necessary condition for the existence of an incongruent covering system with odd moduli. II, Acta Arith. 48 (1987), 73–79.

[GS] Song Guo and Zhi-Wei Sun: \arxiv[On odd covering systems with distinct moduli]{math/0412217}; Adv. Appl. Math. 35(2005), 182–187

[SZ] R. J. Simpson and D. Zeilberger, Necessary conditions for distinct covering systems with square-free moduli, Acta. Arith. 59 (1991), 59–70.

* indicates original appearance(s) of problem.