Solution of the minimum modulus problem for covering systems (Q482915): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Normalize DOI. |
||
(6 intermediate revisions by 6 users not shown) | |||
Property / DOI | |||
Property / DOI: 10.4007/annals.2015.181.1.6 / rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: PARI/GP / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2963381034 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1307.0874 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4004078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Covering the Set of Integers by Congruence Classes of Distinct Moduli / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5614073 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5802215 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some unsolved problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5726744 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5620633 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4081303 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3872528 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New bounds for $\psi (x)$ / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sieving by large integers and covering systems of congruences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A covering system with least modulus 25 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4312862 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3912854 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A covering system whose smallest modulus is 40 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5393666 / rank | |||
Normal rank | |||
Property / DOI | |||
Property / DOI: 10.4007/ANNALS.2015.181.1.6 / rank | |||
Normal rank |
Latest revision as of 18:49, 9 December 2024
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
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