Solution of the minimum modulus problem for covering systems

Abstract

We answer a question of Erdős by showing that the least modulus of a distinct covering system is at most $ 10^{16}$.

  • [ASE92] N. Alon and J. H. Spencer, The Probabilistic Method, New York: John Wiley & Sons, 1992.
    @book{ASE92, mrkey = {1140703},
      author = {Alon, Noga and Spencer, Joel H.},
      title = {The Probabilistic Method},
      series = {Wiley-Intersci. Ser. Discrete Math. Optim.},
      publisher = {John Wiley \& Sons},
      address = {New York},
      year = {1992},
      pages = {xvi+254},
      isbn = {0-471-53588-5},
      mrclass = {60-02 (05C80 11K99 60C05)},
      mrnumber = {1140703},
      mrreviewer = {Bert Fristedt},
      zblnumber = {0767.05001},
      }
  • [C71] Go to document S. L. G. Choi, "Covering the set of integers by congruence classes of distinct moduli," Math. Comp., vol. 25, pp. 885-895, 1971.
    @article{C71, mrkey = {0297692},
      author = {Choi, S. L. G.},
      title = {Covering the set of integers by congruence classes of distinct moduli},
      journal = {Math. Comp.},
      fjournal = {Mathematics of Computation},
      volume = {25},
      year = {1971},
      pages = {885--895},
      issn = {0025-5718},
      mrclass = {10A10},
      mrnumber = {0297692},
      mrreviewer = {H. Gupta},
      doi = {10.2307/2004353},
      zblnumber = {0231.10004},
      }
  • [C68] R. F. Churchhouse, "Covering sets and systems of congruences," in Computers in Mathematical Research, Amsterdam: North-Holland, 1968, pp. 20-36.
    @incollection{C68, mrkey = {0240045},
      author = {Churchhouse, R. F.},
      title = {Covering sets and systems of congruences},
      booktitle = {Computers in {M}athematical {R}esearch},
      pages = {20--36},
      publisher = {North-Holland},
      address = {Amsterdam},
      year = {1968},
      mrclass = {10.06},
      mrnumber = {0240045},
      mrreviewer = {D. H. Lehmer},
      zblnumber = {0212.39703},
      }
  • [E50] P. Erdös, "On integers of the form $2^k+p$ and some related problems," Summa Brasil. Math., vol. 2, pp. 113-123, 1950.
    @article{E50, mrkey = {0044558},
      author = {Erd{ö}s, P.},
      title = {On integers of the form {$2\sp k+p$} and some related problems},
      journal = {Summa Brasil. Math.},
      volume = {2},
      year = {1950},
      pages = {113--123},
      mrclass = {10.0X},
      mrnumber = {0044558},
      mrreviewer = {P. Scherk},
      zblnumber = {0041.36808},
      }
  • [E57] Go to document P. ErdHos, "Some unsolved problems," Michigan Math. J., vol. 4, pp. 291-300, 1957.
    @article{E57, mrkey = {0098702},
      author = {Erd{ő}s, Paul},
      title = {Some unsolved problems},
      journal = {Michigan Math. J.},
      fjournal = {The Michigan Mathematical Journal},
      volume = {4},
      year = {1957},
      pages = {291--300},
      issn = {0026-2285},
      mrclass = {10.00 (41.00)},
      mrnumber = {0098702},
      mrreviewer = {S. Chowla},
      zblnumber = {0081.00102},
      doi = {10.1307/mmj/1028997963},
      }
  • [E63] P. ErdHos, "Quelques problèmes de théorie des nombres," in Monographies de L’Enseignement Mathématique, No. 6, Geneva: Université de Genève, 1963, pp. 81-135.
    @incollection{E63, mrkey = {0158847},
      author = {Erd{ő}s, Paul},
      title = {Quelques problèmes de théorie des nombres},
      booktitle = {Monographies de {L}'{E}nseignement {M}athématique, {N}o. 6},
      pages = {81--135},
      publisher = {Université de Genève},
      address = {Geneva},
      year = {1963},
      mrclass = {10.05},
      mrnumber = {0158847},
      mrreviewer = {W. J. LeVeque},
      zblnumber = {0117.02901},
      }
  • [E69] P. ErdHos, "Some problems in number theory," in Computers in Number Theory, Atkin, A. O. L. and Birch, B. J., Eds., New York: Academic Press, 1971, p. 405.
    @incollection{E69,
      author = {Erd{ő}s, Paul},
      title = {Some problems in number theory},
      booktitle = {Computers in Number Theory},
      editor = {A. O. L. Atkin and B. J. Birch},
      publisher = {Academic Press},
      address = {New York},
      venue = {Proc. Science Research Council Atlas Sympos. No. 2, Oxford (August 18–23, 1969)},
      year = {1971},
      pages = {405–414},
      mrnumber = {0314733},
      zblnumber = {0217.03101},
      }
  • [E73] P. ErdHos, "Résultats et problèmes en théorie des nombres," in Séminaire Delange-Pisot-Poitou (14e année: 1972/73), Théorie des nombres, Fasc. 2, Exp. No. 24, Paris: Secrétariat Mathématique, 1973, p. 7.
    @incollection{E73, mrkey = {0396376},
      author = {Erd{ő}s, Paul},
      title = {Résultats et problèmes en théorie des nombres},
      booktitle = {Séminaire {D}elange-{P}isot-{P}oitou (14e année: 1972/73), {T}héorie des nombres, {F}asc. 2, {E}xp. {N}o. 24},
      pages = {7},
      publisher = {Secrétariat Mathématique},
      address = {Paris},
      year = {1973},
      mrclass = {10-02},
      mrnumber = {0396376},
      mrreviewer = {R. L. Graham},
      zblnumber = {0319.10002},
      }
  • [EG80] P. ErdHos and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Geneva: Université de Genève, 1980, vol. 28.
    @book{EG80,
      author = {Erd{ő}s, Paul and Graham, R. L.},
      title = {Old and New Problems and Results in Combinatorial Number Theory},
      series = {Mongr. Enseign. Math.},
      publisher = {Université de Genève},
      address = {Geneva},
      volume = {28},
      year = {1980},
      mrnumber = {0592420},
      zblnumber = {0434.10001},
      }
  • [FK13] L. Faber and H. Kadiri, New bounds for $\psi(x)$.
    @misc{FK13,
      author = {Faber, L. and Kadiri, H.},
      title = {New bounds for $\psi(x)$},
      note = {to appear in \emph{Math. Comp.}},
      arxiv = {1310.6374v1},
      }
  • [FFKPY07] Go to document M. Filaseta, K. Ford, S. Konyagin, C. Pomerance, and G. Yu, "Sieving by large integers and covering systems of congruences," J. Amer. Math. Soc., vol. 20, iss. 2, pp. 495-517, 2007.
    @article{FFKPY07, mrkey = {2276778},
      author = {Filaseta, Michael and Ford, Kevin and Konyagin, Sergei and Pomerance, Carl and Yu, Gang},
      title = {Sieving by large integers and covering systems of congruences},
      journal = {J. Amer. Math. Soc.},
      fjournal = {Journal of the American Mathematical Society},
      volume = {20},
      year = {2007},
      number = {2},
      pages = {495--517},
      issn = {0894-0347},
      mrclass = {11B25 (11A07 11B05 11N36)},
      mrnumber = {2276778},
      mrreviewer = {Zhi-Wei Sun},
      doi = {10.1090/S0894-0347-06-00549-2},
      zblnumber = {1210.11020},
      }
  • [G09] Go to document D. J. Gibson, "A covering system with least modulus 25," Math. Comp., vol. 78, iss. 266, pp. 1127-1146, 2009.
    @article{G09, mrkey = {2476575},
      author = {Gibson, Donald Jason},
      title = {A covering system with least modulus 25},
      journal = {Math. Comp.},
      fjournal = {Mathematics of Computation},
      volume = {78},
      year = {2009},
      number = {266},
      pages = {1127--1146},
      issn = {0025-5718},
      coden = {MCMPAF},
      mrclass = {11B25 (11A07)},
      mrnumber = {2476575},
      mrreviewer = {Min Tang},
      doi = {10.1090/S0025-5718-08-02154-6},
      zblnumber = {1208.11019},
      }
  • [G94] Go to document R. K. Guy, Unsolved Problems in Number Theory, Second ed., New York: Springer-Verlag, 1994.
    @book{G94, mrkey = {1299330},
      author = {Guy, Richard K.},
      title = {Unsolved Problems in Number Theory},
      series = {Problem Books in Mathematics},
      edition = {Second},
      publisher = {Springer-Verlag},
      year = {1994},
      pages = {xvi+285},
      isbn = {0-387-94289-0},
      mrclass = {11-01 (00A07 11-02)},
      mrnumber = {1299330},
      mrreviewer = {B. M. M. de Weger},
      doi = {10.1007/978-1-4899-3585-4},
      address = {New York},
      zblnumber = {0805.11001},
      }
  • [K71] C. E. Kruckenberg, Covering sets of the integers, 1971.
    @misc{K71,
      author = {Kruckenberg, C. E.},
      title = {Covering sets of the integers},
      note = {Ph.D. thesis, Univ. Illinois at Urbana-Champaigne},
      year = {1971},
      }
  • [M84] R. Morikawa, "Some examples of covering sets," Bull. Fac. Liberal Arts Nagasaki Univ., vol. 21, iss. 2, pp. 1-4, 1981.
    @article{M84, mrkey = {0639635},
      author = {Morikawa, Ryozo},
      title = {Some examples of covering sets},
      journal = {Bull. Fac. Liberal Arts Nagasaki Univ.},
      fjournal = {Bulletin of the Faculty of Liberal Arts. Nagasaki Univesity. Natural Science},
      volume = {21},
      year = {1981},
      number = {2},
      pages = {1--4},
      issn = {0287-1319},
      mrclass = {10L10 (05B40 10A10)},
      mrnumber = {0639635},
      mrreviewer = {Author's review},
      zblnumber = {0462.10003},
      }
  • [N09] Go to document P. P. Nielsen, "A covering system whose smallest modulus is 40," J. Number Theory, vol. 129, iss. 3, pp. 640-666, 2009.
    @article{N09, mrkey = {2488595},
      author = {Nielsen, Pace P.},
      title = {A covering system whose smallest modulus is 40},
      journal = {J. Number Theory},
      fjournal = {Journal of Number Theory},
      volume = {129},
      year = {2009},
      number = {3},
      pages = {640--666},
      issn = {0022-314X},
      coden = {JNUTA9},
      mrclass = {11B25 (11A07)},
      mrnumber = {2488595},
      mrreviewer = {V. Siva Rama Prasad},
      doi = {10.1016/j.jnt.2008.09.016},
      zblnumber = {1234.11011},
      }
  • [PariGP] Go to document relax The PARI Group, Pari/GP, version 2.5.5, 2013.
    @misc{PariGP,
      author = {{\relax The PARI Group}},
      title = {Pari/GP, version 2.5.5},
      note = {Bordeaux},
      year = {2013},
      url = {http://pari.math.u-bordeaux.fr},
      }
  • [RS75] Go to document B. J. Rosser and L. Schoenfeld, "Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$," Math. Comp., vol. 29, pp. 243-269, 1975.
    @article{RS75, mrkey = {0457373},
      author = {Rosser, J. Barkley and Schoenfeld, Lowell},
      title = {Sharper bounds for the {C}hebyshev functions {$\theta (x)$} and {$\psi (x)$}},
      journal = {Math. Comp.},
      fjournal = {Mathematics of Computation},
      volume = {29},
      year = {1975},
      pages = {243--269},
      issn = {0025-5718},
      mrclass = {10H05},
      mrnumber = {0457373},
      mrreviewer = {R. P. Brent},
      doi = {10.2307/2005479},
      zblnumber = {0295.10036},
      }
  • [TV06] Go to document T. Tao and V. Vu, Additive Combinatorics, Cambridge: Cambridge Univ. Press, 2006.
    @book{TV06, mrkey = {2289012},
      author = {Tao, Terence and Vu, Van},
      title = {Additive Combinatorics},
      series = {Cambridge Stud. Adv. Math.},
      number = {105},
      publisher = {Cambridge Univ. Press},
      address = {Cambridge},
      year = {2006},
      pages = {xviii+512},
      isbn = {978-0-521-85386-6; 0-521-85386-9},
      mrclass = {11-02 (05-02 05D10 11B13 11P70 11P82 28D05 37A45)},
      mrnumber = {2289012},
      mrreviewer = {Serge{\u\i} V. Konyagin},
      doi = {10.1017/CBO9780511755149},
      zblnumber = {1127.11002},
      }

Authors

Bob Hough

Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom