Solution of the minimum modulus problem for covering systems (Q482915): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Importer (talk | contribs)
Changed an Item
Property / review text
 
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 \textit{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 \textit{M. Billik} and \textit{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.
Property / review text: 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 \textit{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 \textit{M. Billik} and \textit{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. / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Štefan Porubský / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 11B25 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05B40 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 05C70 / rank
 
Normal rank
Property / Mathematics Subject Classification ID
 
Property / Mathematics Subject Classification ID: 11A07 / rank
 
Normal rank
Property / zbMATH DE Number
 
Property / zbMATH DE Number: 6383666 / rank
 
Normal rank
Property / zbMATH Keywords
 
covering system of congruences
Property / zbMATH Keywords: covering system of congruences / rank
 
Normal rank
Property / zbMATH Keywords
 
Lovász local lemma
Property / zbMATH Keywords: Lovász local lemma / rank
 
Normal rank
Property / zbMATH Keywords
 
probabilistic method
Property / zbMATH Keywords: probabilistic method / rank
 
Normal rank
Property / zbMATH Keywords
 
odd moduli
Property / zbMATH Keywords: odd moduli / rank
 
Normal rank
Property / zbMATH Keywords
 
distinct moduli
Property / zbMATH Keywords: distinct moduli / rank
 
Normal rank
Property / zbMATH Keywords
 
minimum modulus problem
Property / zbMATH Keywords: minimum modulus problem / rank
 
Normal rank

Revision as of 19:46, 30 June 2023

scientific article
Language Label Description Also known as
English
Solution of the minimum modulus problem for covering systems
scientific article

    Statements

    Solution of the minimum modulus problem for covering systems (English)
    0 references
    0 references
    6 January 2015
    0 references
    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 \textit{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 \textit{M. Billik} and \textit{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.
    0 references
    covering system of congruences
    0 references
    Lovász local lemma
    0 references
    probabilistic method
    0 references
    odd moduli
    0 references
    distinct moduli
    0 references
    minimum modulus problem
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references