The structure and number of Erdős covering systems

Abstract

Introduced by Erdős in 1950, a covering system of the integers is a finite collection of arithmetic progressions whose union is the set $\mathbb{Z}$. Many beautiful questions and conjectures about covering systems have been posed over the past several decades, but until recently little was known about their properties. Most famously, the so-called minimum modulus problem of Erdős was resolved in 2015 by Hough, who proved that in every covering system with distinct moduli, the minimum modulus is at most $10^{16}$.

In this paper we answer another question of Erdős, asked in 1952, on the number of minimal covering systems. More precisely, we show that the number of minimal covering systems with exactly $n$ elements is

$\exp \left(\right(\frac{4\sqrt{\tau }}{3}+o(1)\left)\frac{n^{3/2}}{(\log n{)}^{1/2}}\right)\text{as n→∞, where}\tau ={\sum }_{t=1}^{\infty }(\log \frac{t+1}{t}{)}^2.$

En route to this counting result, we obtain a structural description of all covering systems that are close to optimal in an appropriate sense.