Mathematics of Computation

Author(s): Donald Jason Gibson.
Journal: Math. Comp. 78 (2009), 1127-1146.
MSC (2000): Primary 11B25; Secondary 11A07, 11B75
Posted: September 10, 2008
Supplement: Table supplement to this article.
Retrieve article in: PDF

Abstract: A collection of congruences with distinct moduli, each greater than

, 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

. The construction involves a large-scale computer search, in conjunction with two general results that considerably reduce the complexity of the search.

1.: 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 (88j:11002)
2.: S. L. G. Choi, Covering the set of integers by congruence classes of distinct moduli, Math. Comp. 25 (1971), 885-895. MR 0297692 (45:6744)
3.: R. F. Churchhouse, Covering sets and systems of congruences, Computers in Mathematical Research, North-Holland, Amsterdam, 1968, pp. 20-36. MR 0240045 (39:1399)
4.: P. Erdös, On integers of the form $2\sp k+p$ and some related problems, Summa Brasil. Math. 2 (1950), 113-123. MR 0044558 (13:437i)
5.: -, 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
6.: 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 (82j:10001)
7.: 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 (2003k:11015)
8.: 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 (electronic). MR 2276778
9.: Donald Jason Gibson, Covering systems, Ph.D. thesis, University of Illinois, Urbana-Champaign, 2006.
10.: 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 (2006e:11018)
11.: Richard K. Guy, Unsolved problems in number theory, Third Edition, Problem Books in Mathematics, Springer-Verlag, New York, 2004. MR 2076335 (2005h:11003)
12.: Ivan Korec and Štefan Znám, On disjoint covering of groups by their cosets, Math. Slovaca 27 (1977), no. 1, 3-7. MR 0485421 (58:5260)
13.: C. E. Krukenberg, Covering sets of the integers, Ph.D. thesis, University of Illinois, Urbana-Champaign, 1971.
14.: Ryozo Morikawa, On a method to construct covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 22 (1981), no. 1, 1-11. MR 639636 (84i:10057)
15.: -, Some examples of covering sets, Bull. Fac. Liberal Arts Nagasaki Univ. 21 (1981), no. 2, 1-4. MR 639635 (84j:10064)
16.: Pace Nielsen, A covering system whose smallest modulus is large, preprint.
17.: Š. 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 (2004d:11006)
18.: N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 109 (1934), 668-678. MR 1512916
19.: A. Schinzel, Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967/1968), 91-101. MR 0219515 (36:2596)
20.: J. Schönheim, Covering congruences related to modular arithmetic and error correcting codes, Ars Combin. 16 (1983), no. B, 21-25. MR 737106 (85d:11007)
21.: W. Sierpiński, Sur un problème concernant les nombres $k\cdot 2\sp{n}+1$ , Elem. Math. 15 (1960), 73-74. MR 0117201 (22:7983)
22.: 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 (92i:11014)
23.: 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 (54:6557)
24.: J. D. Swift, Sets of covering congruences, Bull. Amer. Math. Soc. 60 (1954), 390.
25.: Štefan Znám, A survey of covering systems of congruences, Acta Math. Univ. Comenian. 40(41) (1982), 59-79. MR 686961 (84e:10004)

Retrieve articles in Mathematics of Computation with MSC (2000): 11B25, 11A07, 11B75

Donald Jason Gibson
Affiliation: Eastern Kentucky University, 313 Wallace Building, 521 Lancaster Avenue, Richmond, Kentucky 40475-3102

DOI: 10.1090/S0025-5718-08-02154-6
PII: S 0025-5718(08)02154-6
Received by editor(s): August 27, 2007
Received by editor(s) in revised form: February 23, 2008
Posted: September 10, 2008
Copyright of article: Copyright 2008, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS