The structure and number of Erdős covering systems

Journal article

Introduced by Erdos in 1950, a covering system of the integers is a finite collection of arithmetic progressions whose union is the set 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 Erdos was resolved in 2015 by Hough, who proved that in every covering system with distinct moduli, the minimum modulus is at most 1016. In this paper we answer another question of Erdos, 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 (( 4 √τ 3 C o(1) ) n3=2 .log n/1=2 ) as n → ∞, where τ ∞Σ 1(log 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.

Authors: Balister, P; Bollobás, B; Morris, R; Sahasrabudhe, J; Tiba, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: EMS Press
• Journal: Journal of the European Mathematical Society
• Volume: 26
• Issue: 1
• Pages: 75-109
• Publication date: 2023-06-15
• Acceptance date: 2022-11-08
• DOI: 10.4171/jems/1357
• EISSN: 1435-9863
• ISSN: 1435-9855
• Language: English
• Keywords: covering systems; arithmetic progressions; inverse theorems