Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-25T16:29:50.601Z Has data issue: false hasContentIssue false

Erdős Covering Systems

Published online by Cambridge University Press:  23 May 2024

By
Paul Balister
Edited by
Felix Fischer  and
Robert Johnson
Felix Fischer
Affiliation:
Queen Mary University of London
Robert Johnson
Affiliation:
Queen Mary University of London
Get access

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 - 54
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
Stein, S. K., Unions of arithmetic sequences, Math. Ann. 134 (1958), 289–294.CrossRefGoogle Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×