Solution of the minimum modulus problem for covering systems. (English) Zbl 1344.11015
A covering system (CS) of congruences is a finite collection of residue classes \(a_i\pmod{n_i}\), \(i=1,\dots,k\), such that every integer belong to at least one of them. If all the moduli are distinct the covering system is called distinct (author denotes them also simply as covering systems without warning). Immediately after introducing this notion by P. Erdős in the thirties of the last century Erdős formulated several striking problems connected with this notion (see the reviewer’s booklet [“Results and problems on covering systems of residue classes.” Mitt. Math. Semin. Gießen 150 (1981; Zbl 0479.10032)] for more details). Two of them were: (1) minimum modulus problem asking whether there exists a distinct CS the least modulus of which exceeds a given integer; (2 with J. L.Selfridge) odd moduli problem asking if there exists a distinct CS with all moduli odd.
The author of the paper under review proves that the first problem has a negative answer: The least modulus of a distinct CS is at most \(10^{16}\). The most exciting ingredient of this proof is the Lovász local lemma. (The best known example supporting an affirmative answer to Erdős’ original question is due to P. P. Nielsen [J. Number Theory 129, No. 3, 640–666 (2009; Zbl 1234.11011)] giving an example of a distinct CS with the least modulus 40).
In connection with the second Erdős problem the author notes that his result “immediately implies that any (distinct) CS contains a modulus divisible by one of an initial segment of primes”. In this connection note that M. Billik and H. M. Edgar [Math. Mag. 46, 265–270 (1973; Zbl 0275.10004)] proved that a negative answer to problem (1) implies that any distinct CS with the maximal modulus has an even modulus.
The author of the paper under review proves that the first problem has a negative answer: The least modulus of a distinct CS is at most \(10^{16}\). The most exciting ingredient of this proof is the Lovász local lemma. (The best known example supporting an affirmative answer to Erdős’ original question is due to P. P. Nielsen [J. Number Theory 129, No. 3, 640–666 (2009; Zbl 1234.11011)] giving an example of a distinct CS with the least modulus 40).
In connection with the second Erdős problem the author notes that his result “immediately implies that any (distinct) CS contains a modulus divisible by one of an initial segment of primes”. In this connection note that M. Billik and H. M. Edgar [Math. Mag. 46, 265–270 (1973; Zbl 0275.10004)] proved that a negative answer to problem (1) implies that any distinct CS with the maximal modulus has an even modulus.
Reviewer: Štefan Porubský (Praha)
MSC:
| 11B25 | Arithmetic progressions |
| 05B40 | Combinatorial aspects of packing and covering |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 11A07 | Congruences; primitive roots; residue systems |
Keywords:
covering system of congruences; Lovász local lemma; probabilistic method; odd moduli; distinct moduli; minimum modulus problemSoftware:
PARI/GPReferences:
| [1] | N. Alon and J. H. Spencer, The Probabilistic Method, New York: John Wiley & Sons, 1992. · Zbl 0767.05001 |
| [2] | S. L. G. Choi, ”Covering the set of integers by congruence classes of distinct moduli,” Math. Comp., vol. 25, pp. 885-895, 1971. · Zbl 0231.10004 · doi:10.2307/2004353 |
| [3] | R. F. Churchhouse, ”Covering sets and systems of congruences,” in Computers in Mathematical Research, Amsterdam: North-Holland, 1968, pp. 20-36. · Zbl 0212.39703 |
| [4] | P. Erdös, ”On integers of the form \(2^k+p\) and some related problems,” Summa Brasil. Math., vol. 2, pp. 113-123, 1950. · Zbl 0041.36808 |
| [5] | P. ErdHos, ”Some unsolved problems,” Michigan Math. J., vol. 4, pp. 291-300, 1957. · Zbl 0081.00102 · doi:10.1307/mmj/1028997963 |
| [6] | 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. · Zbl 0117.02901 |
| [7] | 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. · Zbl 0217.03101 |
| [8] | 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. · Zbl 0319.10002 |
| [9] | P. ErdHos and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, Geneva: Université de Genève, 1980, vol. 28. · Zbl 0434.10001 |
| [10] | L. Faber and H. Kadiri, New bounds for \(\psi(x)\). · Zbl 1310.11085 |
| [11] | 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. · Zbl 1210.11020 · doi:10.1090/S0894-0347-06-00549-2 |
| [12] | D. J. Gibson, ”A covering system with least modulus 25,” Math. Comp., vol. 78, iss. 266, pp. 1127-1146, 2009. · Zbl 1208.11019 · doi:10.1090/S0025-5718-08-02154-6 |
| [13] | R. K. Guy, Unsolved Problems in Number Theory, Second ed., New York: Springer-Verlag, 1994. · Zbl 0805.11001 · doi:10.1007/978-1-4899-3585-4 |
| [14] | C. E. Kruckenberg, Covering sets of the integers, 1971. |
| [15] | R. Morikawa, ”Some examples of covering sets,” Bull. Fac. Liberal Arts Nagasaki Univ., vol. 21, iss. 2, pp. 1-4, 1981. · Zbl 0462.10003 |
| [16] | P. P. Nielsen, ”A covering system whose smallest modulus is 40,” J. Number Theory, vol. 129, iss. 3, pp. 640-666, 2009. · Zbl 1234.11011 · doi:10.1016/j.jnt.2008.09.016 |
| [17] | relax The PARI Group, Pari/GP, version 2.5.5, 2013. |
| [18] | 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. · Zbl 0295.10036 · doi:10.2307/2005479 |
| [19] | T. Tao and V. Vu, Additive Combinatorics, Cambridge: Cambridge Univ. Press, 2006. · Zbl 1127.11002 · doi:10.1017/CBO9780511755149 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
