Status
On this page
Status
Topics
Status
On this page
Status
Topics
Can the smallest modulus of a covering system be arbitrarily large?
Can the smallest modulus of a covering system with distinct moduli be arbitrarily large?
Source: erdosproblems.com/2
An accepted solution exists. The statement is false.
DISPROVED (LEAN), the site's label: Hough's published theorem gives an absolute upper bound for the minimum modulus. The later published BBMST bound gives , equivalently . The largest achievable minimum modulus is unidentified in the literature search. The two proofs are recorded on their claim pages, Hough and Balister, Bollobás, Morris, Sahasrabudhe and Tiba, each accepted on its refereed publication and the site's credit. Two refereed results on restricted classes are accepted partial claims: Filaseta, Ford, Konyagin, Pomerance and Yu bound the minimum modulus when the reciprocal sum of the moduli is bounded, and Cummings, Filaseta and Trifonov bound it by when every modulus is squarefree. The site's Lean badge is qualified below.
The site's wording drops the condition, assumed by the problem's sources, that the moduli are distinct; the literature uses the bare term both ways. If repeated moduli are allowed, the answer is trivially yes: for every , the residue classes modulo any single cover the integers. This trivial cover is the corpus's own observation, and no result about the site's wording is recorded. The change inserts "with distinct moduli"; nothing else changes. The evidence is the literature's statement of the problem as Erdős's. Nielsen, A covering system whose smallest modulus is 40 (J. Number Theory 129 (2009), abstract, p. 1 of the author version), a construction that settles nothing: "Paul Erdős, in 1950, asked whether for each positive integer there exists a finite set of congruence classes, with distinct moduli, covering the integers, whose smallest modulus is ." Hough [Ho15], §1, printed p. 361: "From [4], the minimum modulus problem asks whether there exist distinct covering systems for which the least modulus is arbitrarily large", where [4] is Erdős's 1950 paper and a distinct covering system is a finite collection of congruences with covering every integer. [BBMST22], abstract, printed p. 378: "Erdős asked if the moduli can be distinct and all arbitrarily large"; their §1 (printed p. 378) defines a covering system as any finite collection of arithmetic progressions that covers the integers, so in their usage the term alone does not carry distinctness. Hough and BBMST state the problem apart from their theorems' hypotheses, and the site's commentary, which credits Hough's bound , the bound and Owens's cover with minimum modulus , fits only the distinct reading. Erdős's 1950 paper also prints the distinctness: its conjecture on p. 120 concerns systems of congruences with that cover every integer (result page Erdős 1950, p. 120). Whether the site's sources [Er55c] to [Er97e] print it is not recorded here.