Solution of the minimum modulus problem for covering systems

Year of Award: 2017

Award: Robbins

Publication Information: Annals of Mathematics, 181, no. 1 (2015), 361-382.

Summary:

(Adapted from the JMM 2017 Prizes and Awards booklet) Paul Erdős introduced the concept of a system of covering congruences ( SCC) in the 1930’s in response to a number theory question of Romanoff. An SCC is simply a finite set of arithmetic progressions {m_in + a_i : n = 0, 1, 2, . . . , } for 1 ≤ i ≤ r with 1 < m₁ < m₂ < . . . < m_r such that every positive integer belongs to at least one of the progressions. For example, it is easily checked that the progressions {2n}, {3n}, {4n + 1}, {6n + 1} and {12n + 11} form an SCC. Erdős raised the question as to whether there were SCC’s with minimum modulus m₁ ≥ M for arbitrary M . Over the past 50 years, the value of M increased, with the current record being held by Nielsen with M = 40. This latter system has more than 10⁵⁰ progressions! Everyone naturally assumed that the value of M could be made arbitrarily large by taking sufficiently many (carefully chosen) progressions. Thus, it was a complete shock to the community that this is not the case. Bob Hough stunned the field by showing that for any system of covering sequences, the minimum modulus must be less that 10¹⁶! The proof involves a very clever application of the so-called Lovász Local Lemma, a power combinatorial tool for handling dependent probability in the case where the dependence is local, together with some insightful ideas from elementary number theory. While the proof is not simple, it is completely self-contained, only employing ideas and techniques accessible to undergraduates. Of course, people now believe that the bound of 10¹⁶ can be lowered to something much smaller, perhaps as small as 100. This still leaves open the old problem as to whether there is an SCC with all the moduli odd. This beautiful paper will certainly stimulate further research on this topic.

About the Author: (From the JMM 2017 Prizes and Awards booklet)

Robert Hough was born in Midland, MI in 1985 and completed three degrees from Stanford University, including a PhD in mathematics in 2012 under the supervision of Soundararajan. He spent roughly a year and a half each at Cambridge and Oxford as a post-doc working with Ben Green and was a postdoctoral member of the Institute for Advanced Study, Princeton. He is currently an assistant professor at the State University of New York, Stony Brook. His research interests include quantitative questions in probability, combinatorics and analytic number theory.