Book contents
- Frontmatter
- Contents
- Preface
- Intersection Theory of Matroids: Variations on a Theme
- Erdős Covering Systems
- The Cluster Expansion in Combinatorics
- Sublinear Expanders and Their Applications
- Transversals in Latin Squares
- Finite Field Models in Arithmetic Combinatorics – Twenty Years On
- The Slice Rank Polynomial Method – A Survey a Few Years Later
- An Introduction to Transshipments Over Time
- Oriented Trees and Paths in Digraphs
- References
Erdős Covering Systems
Published online by Cambridge University Press: 23 May 2024
Book contents
- Frontmatter
- Contents
- Preface
- Intersection Theory of Matroids: Variations on a Theme
- Erdős Covering Systems
- The Cluster Expansion in Combinatorics
- Sublinear Expanders and Their Applications
- Transversals in Latin Squares
- Finite Field Models in Arithmetic Combinatorics – Twenty Years On
- The Slice Rank Polynomial Method – A Survey a Few Years Later
- An Introduction to Transshipments Over Time
- Oriented Trees and Paths in Digraphs
- References
Summary
Introduced by Erdős in 1950, a covering system of the integers is a finite collection of infinite arithmetic progressions whose union is the set of all integers. Many beautiful questions and conjectures about covering systems have been posed over the past several decades, but until the last decade 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 a fixed constant. The ideas of Hough were simplified and extended in 2018 by Balister, Bollobas, Morris, Sahasrabudhe and Tiba, to give solutions (or progress towards solutions) to a number of related questions. We give a summary of this and other progress that has been made since.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2024 , pp. 31 - 54Publisher: Cambridge University PressPrint publication year: 2024
References
Balister, P., Bollobás, B., Morris, R., Sahasrabudhe, J. and Tiba, M., Covering intervals with arithmetic progressions, Acta Math. Hungar. 161 (2020), 197–200.CrossRefGoogle Scholar
Balister, P., Bollobás, B., Morris, R., Sahasrabudhe, J. and Tiba, M., Erdős covering systems, Acta Math. Hungar. 161 (2020), 540–549.CrossRefGoogle Scholar
Balister, P., Bollobás, B., Morris, R., Sahasrabudhe, J. and Tiba, M., The Erdős–Selfridge problem with square-free moduli, Algebra Number Theory 15 (2021), 609–626.CrossRefGoogle Scholar
Balister, P., Bollobás, B., Morris, R., Sahasrabudhe, J. and Tiba, M., On the Erdős covering problem: the density of the uncovered set, Invent. Math. 228 (2022), 377–414.CrossRefGoogle Scholar
Balister, P., Bollobás, B., Morris, R., Sahasrabudhe, J. and Tiba, M., The structure and number of Erdős covering systems, J. Eur. Math. Soc., in press.Google Scholar
Choi, S. L. G., Covering the set of integers by congruence classes of distinct moduli, Math. Comp. 25 (1971), 885–895.CrossRefGoogle Scholar
Churchhouse, R. F., Covering sets and systems of congruences, In: Computers in Mathematical Research North-Holland, Amsterdam, 1968, pp. 20–36.Google Scholar
Crittenden, R. B. and Eynden, C. L. Vanden, A proof of a conjecture of Erdős, Bull. Amer. Math. Soc. 75 (1969), 1326–1329.CrossRefGoogle Scholar
Crittenden, R. B. and Eynden, C. L. Vanden, Any n arithmetic progressions covering the first 2n integers cover all integers, Proc. Amer. Math. Soc. 24 (1970), 475–481.Google Scholar
Cummings, M., Filaseta, M. and Trifonov, O., An upper bound for the minimum modulus in a covering system with squarefree moduli, ArXiv preprint arXiv:2211.08548 (2022).Google Scholar
Dusart, P., The kth prime is greater than k(log k + log log k − 1) for k ≥ 2, Math. Comp. 68 (1999), 411–415.CrossRefGoogle Scholar
Elsholtz, C. and Schlage-Puchta, J-C., On Romanov’s constant, Math. Z. 288 (2018), 713–724.CrossRefGoogle Scholar
Erdős, P., On integers of the form 2k + p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.Google Scholar
Erdős, P., On a problem concerning congruence-systems (in Hungarian), Mat. Lapok 3 (1952), 122–128.Google Scholar
Erdős, P., Remarks on number theory, IV. Extremal problems in number theory, I. (in Hungarian), Mat. Lapok 13 (1962), 228–255.Google Scholar
Erdős, P., Some recent advances and current problems in number theory, Lectures on Modern Mathematics, Vol. III, Wiley, New York, 1965, pp. 196–244.Google Scholar
Erdős, P., Extremal problems in number theory, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 181–189. Erdős Covering Systems 53CrossRefGoogle Scholar
Erdős, P., Problems and results on combinatorial number theory III, In: Number Theory Day, Lecture Notes in Math., vol. 626, Springer, Berlin, 1977, pp. 43–72.CrossRefGoogle Scholar
Erdős, P., Solution to problem 1029: Erdős and the computer, Math. Mag. 52 (1979), 180–181.Google Scholar
Erdős, P. and Graham, R. L., Old and new problems and results in combinatorial number theory, Monographies de Lénseignement Mathématique, vol. 28, Université de Genève, Lénseignement Mathématique, Geneva, 1980.Google Scholar
Fabrykowski, J., Smotzer, T., Covering Systems of Congruences, Math. Mag. 78 (2005), pp. 228–231.CrossRefGoogle Scholar
Filaseta, M., Ford, K. and Konyagin, S., On an irreducibility theorem of A. Schinzel associated with coverings of the integers, Illinois J. Math. 44 (2000), 633–643.CrossRefGoogle Scholar
Filaseta, M., Ford, K., Konyagin, S., Pomerance, C. and Yu, G., Sieving by large integers and covering systems of congruences, J. Amer. Math. Soc. 20 (2007), 495–517.CrossRefGoogle Scholar
Filaseta, M., Finch, C. and Kozek, M., On powers associated with Sierpiński numbers, Riesel numbers and Polignac’s conjecture, J. Number Theory 128 (2008), 1916–1940.CrossRefGoogle Scholar
Filaseta, M. and Juillerat, J., Consecutive primes which are widely digitally delicate, Integers 21A (2021), A12.CrossRefGoogle Scholar
Filaseta, M. and Harrington, J., A polynomial investigation inspired by work of Schinzel and Sierpiński, Acta Arith. 155 (2012), 149–161.CrossRefGoogle Scholar
Filaseta, M. and Harvey, W., Covering subsets of the integers by congruences, Acta Arith. 182 (2018), 43–72.CrossRefGoogle Scholar
Friedlander, J., On exact coverings of the integers, Israel J. Math. 12 (1972), 299–305.CrossRefGoogle Scholar
Gibson, D. J., A covering system with least modulus 25, Math. Comp. 78 (2009), 1127–1146.CrossRefGoogle Scholar
Goulden, I. P., Granville, A., B. Richmond and J. Shallit, L., Natural exact covering systems and the reversion of the M̈obius series, Ramanujan J. 50 (2019), 211–235.CrossRefGoogle Scholar
Graham, R. L., A Fibonacci-like sequence of composite numbers, Math. Mag. 37 (1964), 322–324.CrossRefGoogle Scholar
Guy, R. K., Unsolved problems in number theory, Problem Books in Mathematics, Springer-Verlag, New York, 2004.Google Scholar
Harrington, J., Two questions concerning covering systems, Int. J. Number Theory 11 (2015), 1739–1750.CrossRefGoogle Scholar
Hough, R. D., Solution of the minimum modulus problem for covering systems, Ann. Math. 181 (2015), 361–382.CrossRefGoogle Scholar
Hough, R. D. and Nielsen, P. P., Covering systems with restricted divisibility, Duke Math. J. 168 (2019), 3261–3295.CrossRefGoogle Scholar
Klein, J., Koukoulopoulos, D. and Lemieux, S., On the j-th smallest modulus of a covering system with distinct moduli, Int. J. Number Theory, in press.Google Scholar
Krukenberg, C. E., Covering sets of the integers, Ph.D. dissertation, University of Illinois, Urbana-Champaign, 1971.Google Scholar
Landau, E., Über einige neuere Fortschritte der additiven Zahlentheorie, Cambridge tracts in mathematics and mathematical physics, vol. 35, Cambridge University Press, Cambridge, 1937.Google Scholar
Nielsen, P. P., A covering system whose smallest modulus is 40, J. Number Theory 129 (2009), 640–666.CrossRefGoogle Scholar
Owens, T., A Covering System with Minimum Modulus 42, Master’s thesis, Brigham Young University, 2014, available at https://scholarsarchive.byu.edu/etd/4329.Google Scholar
Polignac, A. de, Six propositions arithmologiques déduites du crible d’Ératosthéne, Nouvelles Annales de Mathématiques 1 (1849), no. 8, 423–429.Google Scholar
Porubský, Š. and Schönheim, J., Covering systems of Paul Erdős. Past, present and future, In: Paul Erdős and his mathematics, I, János Bolyai Math. Soc., Budapest, 2002, 581–627.Google Scholar
Schinzel, A., Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967), 91–101.CrossRefGoogle Scholar
Sierpiński, W., Sur un problème concernant les nombres k · 2n + 1, Elem. Math. 15 (1960), 73–74.Google Scholar
Simpson, R. J., Regular coverings of the integers by arithmetic progressions, Acta Arith. 45 (1985), 145–152.CrossRefGoogle Scholar