The Number of Minimal Covering Systems With Distinct Moduli

Let $F(x)$ be the number of minimal covering systems of the integers whose moduli are distinct and lie in $[1,x]$. Estimating $F(x)$ is a problem of Erd{o}s, known as Erd{o}s Problem~#1188. We determine the order of magnitude of log F(x):\[ (c_1+o(1))\,xlog x\;≤\;log F(x)\;≤\;(1-log 2)\,xlog x+1.5\,x,\]where c₁=0.0672. Thus F(x)=xΘ(x). The upper bound holds for all x≥2. It rests on a local lemma: in a minimal covering system, for every prime p, the classes whose moduli are divisible by p project onto all residues modulo the largest power of p dividing a modulus. Hence every modulus of a minimal covering system with distinct moduli at most x is √x-smooth. The lower bound comes from a split construction. The integers are organised by the least prime power that does not divide them, and many of the resulting classes are split further, along splitting trees, according to their residues modulo auxiliary primes. The construction shows that a minimal distinct covering system with moduli at most x can use a positive proportion of all integers up to x as moduli: the largest possible number $k(x)$ of classes satisfies 0.2128\,x≤ k(x)≤(1-log2+o(1))\,x for large x. In fact, for every 0<h<12 the construction uses almost all integers n≤ x with exactly two prime factors in (xʰ,√ x] and no larger prime factor, and the constants are explicit double integrals of Dickman's function. Splitting only once, by primes from (x1/5,x1/4], gives the closed forms (1-λ)λ(λ-3/20) and (1-λ)λ², with λ=log54, in place of c₁ and $0.2128$, and the systems without splitting give the explicit bound log F(x)≥ x/2-3x/log x for all x≥40. The exact values of the constants remain open. Call a modulus balanced if none of its prime-power components exceeds its square root. At most (1+o(1))\,x/log x classes of such a system are unbalanced. An anchor lemma, which strengthens the local lemma, shows that the systems with at most b≥1 balanced classes number exp(x/2+O(xloglog x/log x+blog x)). Consequently almost all minimal distinct covering systems with moduli at most x have at least $c\,x$ classes, for any fixed c<145. We also compute $F(x)$ exactly for x≤ 24 and the largest possible number of classes for several x≤48.