Covering systems with big moduli

Importance: Medium ✭✭
Keywords: covering system
Recomm. for undergrads: no
Posted by: Robert Samal
on: August 4th, 2007

\begin{problem} Does for every integer $N$ exist a \Def{covering system} with all moduli distinct and at least equal to~$N$? \end{problem}

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. They are known for many lower bounds $N$ on the size of moduli: e.g. $\{0(2), 0(3), 1(4), 5(6), 7(12) \}$ is such system for $N=2$. Choi proved that it is possible to give an example for N = 20.

On the other hand, recently it was shown [FFKPY] that if such systems exist for arbitrary large $N$, then $\sum_{i=1}^k \frac 1{n_i}$ is not bounded.


[FFKPY] Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance, Gang Yu: \arxiv[Sieving by large integers and covering systems of congruences]{math.NT/0507374}, J. Amer. Math. Soc. 20 (2007), 495-517.

* indicates original appearance(s) of problem.