A covering system with least modulus 25

Gibson, Donald

doi:10.1090/S0025-5718-08-02154-6

A covering system with least modulus 25
HTML articles powered by AMS MathViewer

by Donald Jason Gibson PDF

Math. Comp. 78 (2009), 1127-1146 Request permission

Abstract:

A collection of congruences with distinct moduli, each greater than $1$, such that each integer satisfies at least one of the congruences, is said to be a covering system. A famous conjecture of Erdös from 1950 states that the least modulus of a covering system can be arbitrarily large. This conjecture remains open and, in its full strength, appears at present to be unattackable. Most of the effort in this direction has been aimed at explicitly constructing covering systems with large least modulus. Improving upon previous results of Churchhouse, Krukenberg, Choi, and Morikawa, we construct a covering system with least modulus $25$. The construction involves a large-scale computer search, in conjunction with two general results that considerably reduce the complexity of the search.

References

Marc A. Berger, Alexander Felzenbaum, and Aviezri S. Fraenkel, Necessary condition for the existence of an incongruent covering system with odd moduli. II, Acta Arith. 48 (1987), no. 1, 73–79. MR 893463, DOI 10.4064/aa-48-1-73-79
S. L. G. Choi, Covering the set of integers by congruence classes of distinct moduli, Math. Comp. 25 (1971), 885–895. MR 297692, DOI 10.1090/S0025-5718-1971-0297692-7
R. F. Churchhouse, Covering sets and systems of congruences, Computers in Mathematical Research, North-Holland, Amsterdam, 1968, pp. 20–36. MR 0240045
P. Erdös, On integers of the form $2^k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113–123. MR 44558
P. Erdős, On some of my problems in number theory I would most like to see solved, Number theory (Ootacamund, 1984) Lecture Notes in Math., vol. 1122, Springer, Berlin, 1985, pp. 74–84. MR 797781, DOI 10.1007/BFb0075752
P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève, L’Enseignement Mathématique, Geneva, 1980. MR 592420
Michael Filaseta, Coverings of the integers associated with an irreducibility theorem of A. Schinzel, Number theory for the millennium, II (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 1–24. MR 1956242
Michael Filaseta, Kevin Ford, Sergei Konyagin, Carl Pomerance, and Gang Yu, Sieving by large integers and covering systems of congruences, J. Amer. Math. Soc. 20 (2007), no. 2, 495–517. MR 2276778, DOI 10.1090/S0894-0347-06-00549-2
Donald Jason Gibson, Covering systems, Ph.D. thesis, University of Illinois, Urbana-Champaign, 2006.
Song Guo and Zhi-Wei Sun, On odd covering systems with distinct moduli, Adv. in Appl. Math. 35 (2005), no. 2, 182–187. MR 2152886, DOI 10.1016/j.aam.2005.01.004
Richard K. Guy, Unsolved problems in number theory, 3rd ed., Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335, DOI 10.1007/978-0-387-26677-0
Ivan Korec and Štefan Znám, On disjoint covering of groups by their cosets, Math. Slovaca 27 (1977), no. 1, 3–7 (English, with Russian summary). MR 485421
C. E. Krukenberg, Covering sets of the integers, Ph.D. thesis, University of Illinois, Urbana-Champaign, 1971.
Ryozo Morikawa, On a method to construct covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 22 (1981), no. 1, 1–11. MR 639636
Ryozo Morikawa, Some examples of covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 21 (1981), no. 2, 1–4. MR 639635
Pace Nielsen, A covering system whose smallest modulus is large, preprint.
Š. Porubský and J. Schönheim, Covering systems of Paul Erdős. Past, present and future, Paul Erdős and his mathematics, I (Budapest, 1999) Bolyai Soc. Math. Stud., vol. 11, János Bolyai Math. Soc., Budapest, 2002, pp. 581–627. MR 1954716
N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), no. 1, 668–678 (German). MR 1512916, DOI 10.1007/BF01449161
A. Schinzel, Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967/68), 91–101. MR 219515, DOI 10.4064/aa-13-1-91-101
J. Schönheim, Covering congruences related to modular arithmetic and error correcting codes, Ars Combin. 16 (1983), no. B, 21–25. MR 737106
W. Sierpiński, Sur un problème concernant les nombres $k\cdot 2^{n}+1$, Elem. Math. 15 (1960), 73–74 (French). MR 117201
R. J. Simpson and Doron Zeilberger, Necessary conditions for distinct covering systems with square-free moduli, Acta Arith. 59 (1991), no. 1, 59–70. MR 1133237, DOI 10.4064/aa-59-1-59-70
L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential time: preliminary report, Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), Assoc. Comput. Mach., New York, 1973, pp. 1–9. MR 0418518
J. D. Swift, Sets of covering congruences, Bull. Amer. Math. Soc. 60 (1954), 390.
Štefan Znám, A survey of covering systems of congruences, Acta Math. Univ. Comenian. 40/41 (1982), 59–79 (English, with Russian and Slovak summaries). MR 686961