# Solution of Erdős Problem 1189

Throughout, “irreducible” has the strong meaning in the question: after a
proper subset of the moduli is chosen, it may choose entirely new residues.
Let `I(k)` be the number of irreducible `k`-sets, let `m(k),M(k)` be the
minimum and maximum possible largest modulus, and let `R(k)` be the maximum
reciprocal sum.  Put

\[
 \tau=\sum_{t\ge1}\left(\log\frac{t+1}{t}\right)^2,
 \qquad F(k)=\frac{k^{3/2}}{\sqrt{\log k}}.
\]

The answers are

\[
 \log I(k)=\left(\frac{4\sqrt\tau}{3}+o(1)\right)F(k),                 \tag{1}
\]
\[
 M(k)=3\,2^{k-3}\quad(k\ge5),                                      \tag{2}
\]
\[
 k+1\le m(k)\le Ck(\log k)^6,
 \quad\text{and hence }m(k)=k^{1+o(1)},                              \tag{3}
\]
and
\[
 R(k)=\Theta(\log k).                                                \tag{4}
\]
There are also infinitely many integers whose full set of divisors greater
than one is irreducible.  Verification levels are deliberately separated: the
count asymptotic uses BBMST's published PNT enumeration plus the reduction
proved below; (2)--(4) and the divisor infinitude have unconditional Lean
proofs.  The minimum result (3) is an order estimate, not an exact formula,
and (4) does not claim a leading constant.

The exact certified initial counts are

\[
 I(1)=\cdots=I(4)=0,
 \qquad (I(5),\ldots,I(11))=(1,4,15,65,318,2102,17040).
\]

## 1. The fresh-residue frame lemma

Let `X=∏_{u∈U}X_u`, with `|X_u|=q_u`.  A simple frame consists of one axis
hyperplane with support `U` and, for every `u`, exactly `q_u-1` hyperplanes
owned by `u`, each of whose support contains `u`.  Assume that all these
supports are distinct.  The usual ordered-frame choice of values covers `X`.
More importantly, no proper subfamily of its supports can cover `X`, even if
all fixed values are changed.

Indeed, let `C` be a proper support subfamily and set `V=⋃C`.  If the axis is
in `C`, then `V=U` and

\[
 |C|\le\sum_{u\in V}(q_u-1).
\]
If it is absent, put `J=U\setminus V`.  For each `u∈J`, all `q_u-1` supports
owned by `u` are absent as well, and therefore the same inequality follows.
If new values made `C` a cover, take an inclusion-minimal subcover `D`.
Simpson's geometric inequality gives

\[
 |D|\ge1+\sum_{u\in\bigcup D}(q_u-1),
\]
contradicting the preceding bound applied to `D`.  This argument, including
minimal-subcover extraction and arbitrary fresh values, is the kernel-checked
result F-032/F-033.

For `N=∏_p p^{\gamma_p}`, take one `p`-digit coordinate for every pair
`(p,e)`, `1≤e≤γ_p`.  A support is arithmetic exactly when its coordinates in
each `p`-block form an initial segment.  CRT identifies such a hyperplane
with one residue class modulo the product of the corresponding prime powers.
Thus an arithmetic simple frame with distinct supports gives an irreducible
modulus set in the strong sense above.  The complete repeated-prime CRT
transport is F-040.

## 2. Counting the sets

Balister--Bollobás--Morris--Sahasrabudhe--Tiba (BBMST), *The structure and
number of Erdős covering systems*, Theorem 1.1, prove that the number `A(k)`
of minimal displayed covering systems with `k` classes satisfies

\[
 \log A(k)=\left(\frac{4\sqrt\tau}{3}+o(1)\right)F(k).                \tag{5}
\]

### Upper bound

Choose one displayed covering system for every irreducible modulus set.  It is
minimal as a displayed system, since deleting a displayed class would make the
corresponding proper modulus subset cover.  Different modulus sets give
different displayed systems.  Hence `I(k)≤A(k)`.  This canonical-choice
injection is formalized in F-049.

### Lower bound

BBMST Proposition 5.1 and Section 5 obtain the lower bound in (5) by counting
arithmetic simple frames.  The paper explicitly records immediately after
Theorem 1.1 that this lower bound holds under the additional restriction that
the moduli are distinct.  For completeness, this restriction also follows
directly from their count. If `D_{p,e}` is the number of available predecessor
supports at layer `(p,e)`, their equation (19) gives

\[
 \log D_{p,e}=(\tau+o(1))y_{p,e}/\log y_{p,e},
\]

so `D_{p,e}/p→∞`. Choose the `p-1` layer supports injectively. Since
`(D)_{p-1}≥(D/2)^{p-1}` once `D≥2(p-1)`, the total logarithmic loss is only
`O(n(x))=o(F(n(x)))`. The finitely many early layers have at least `p-1`
binary-prefix choices, and the one possible axis collision at the last layer
is simply excluded. Supports with different owners are automatically
different. Thus the same lower exponent is attained with distinct supports.
The frame lemma in Section 1 turns every resulting modulus set into a strong
irreducible set.

Several displayed systems can have the same modulus set.  BBMST Lemma 6.2
states that prescribed moduli `d_1,…,d_k` support at most `(k!)²` minimal
displayed systems.  Consequently the number of modulus sets represented by a
lower family of size `L(k)` is at least `L(k)/(k!)²`.  Since

\[
 2\log(k!)=O(k\log k)=o(F(k)),
\]
this division does not change the leading term.

The first frame sizes in their proof are `n(x)`, where

\[
 n(x)=(\tau+o(1))\frac{x^2}{2\log x}.
\]
If `n(x)≤k<n(x^+)`, then `k-n(x)<x=o(n(x))`.  Apply the injective operation

\[
 \delta(S)=\{2\}\cup\{2n:n\in S\}
\]
exactly `k-n(x)` times.  It preserves strong irreducibility (F-027) and is
injective, so it fills every size gap without losing any sets.  Also
`F(n(x))/F(k)→1`.  The finite-fiber and arbitrary-gap reductions are
machine-checked in F-048.  Combining both sides proves (1).

## 3. Largest modulus

Full arithmetic Simpson gives, for every irreducible `k`-set `S`,

\[
 1+\sum_p \max_{n\in S}v_p(n)(p-1)\le k.                             \tag{6}
\]

A covering set of distinct moduli cannot use powers of two only: if the
largest exponent is `a`, only `a` nontrivial powers are available while (6)
requires at least `a+1` classes.  Thus an odd-prime block occurs.  Applying
`p^a≤2^{a(p-1)}` to all prime-power blocks, with the sharpened estimate on one
odd block, gives

\[
 n\le 3\,2^{k-3}\qquad(n\in S).
\]
Starting from `{2,3,4,6,12}` and iterating `δ` produces a size-`k` irreducible
set with largest member `12·2^{k-5}=3·2^{k-3}`.  This proves (2); the complete
kernel proof is F-029.

For the minimum, `k` distinct integers in `[2,m(k)]` force `m(k)≥k+1`
(F-031).  The upper construction is an explicit prime-power boundary frame.
Here is its quantitative outline.

Set

\[
 L=\lfloor\log_2(k+1)\rfloor+1,\quad n=2(\lfloor\sqrt k\rfloor+1),
 \quad X=16(n+1)(\lfloor\log_2(n+1)\rfloor+1),
\]
\[
 h=2(\lfloor\sqrt X\rfloor+1),\qquad
 Y=16(h+1)(\lfloor\log_2(h+1)\rfloor+1).
\]
The eventual nth-prime bound `p_j≤16(j+1)(⌊log₂(j+1)⌋+1)` puts all payload
primes below `X` and all seed primes below `Y`.  Force the seed prime-power
digits through their `Y`-adic caps.  Complete the remaining exact cardinality
with distinct odd-prime half-weights `(p-1)/2`; a one- or two-digit binary tail
fixes parity.  There are `choose(h,2)≥X` seed pairs, enough to tag all ordinary
payload layers.  One layer over each coordinate instead receives the full
prefix of its predecessor, and the final binary prefix is the anchor.  The
boundary-frame lemma then gives strong irreducibility, while the weight
identity gives exactly `k` moduli.

Every coordinate prefix is at most `Y²`.  Integer tags have product at most
`Y³`, pair tags at most `Y⁴`, and predecessor-chain tags at most `4Y⁴`; the
anchor is smaller.  Moreover

\[
 X\le64\sqrt k\,L,
 \qquad Y\le80\sqrt X\,L.
\]
Thus every modulus is at most

\[
 4Y^4\le (4\cdot80^4\cdot64^2)\,kL^6.
\]
The forced seed weight is eventually below `k-3` because any fixed multiple
of `L^5` is `o(\sqrt k)`.  Hence the construction works for every sufficiently
large `k`.  This entire construction and the explicit constant
`671088640000` are kernel-checked in F-051--F-053, proving (3).

## 4. Reciprocal sums

For any `k` distinct integers greater than one,

\[
 \sum_{n\in S}\frac1n\le\sum_{j=2}^{k+1}\frac1j=O(\log k).            \tag{7}
\]

For the reverse order, F-047 constructs one fixed `D>0` such that every
`k≥D` has an irreducible `k`-set satisfying

\[
 \sum_{n\in S}\frac1n\ge \frac18\,\operatorname{Nat.log}_{64}(k/D).
                                                                            \tag{8}
\]
The construction uses every integer tag `d=1,…,q-1` on the first digit of
each prime `q` in a growing initial block, so those classes have exact moduli
`qd` and contribute `H_{q-1}/q`; a binary boundary tail fills every remaining
cardinality.  Chebyshev's theta lower bound gives a fixed gain at every
base-64 scale.  Since the right side of (8) is `Ω(log k)`, (7)--(8) prove
(4).  F-030 and F-047 are sorry-free Lean proofs.

## 5. Full divisor sets

For every odd prime `p`, all nontrivial divisors of

\[
 N_p=2^{p-1}p
\]
form an irreducible covering set.  In digit coordinates, the `p-1` pure powers
of two detect the first nonzero binary digit, and the `p` mixed divisors cover
the all-zero binary fibre.

For strong irreducibility, a subset not using `p` consists only of powers of
two and cannot cover.  If `p` occurs and the largest binary exponent is
`a≤p-2`, there are at most `2a+1` eligible divisors, whereas (6) requires at
least `a+p>2a+1`.  If `a=p-1`, (6) requires all `2p-1` nontrivial divisors.
Thus no proper divisor subset covers, regardless of fresh residues.  F-009
formalizes the cover, the divisor identification, the integer congruences, and
infinitude.  Since there are infinitely many odd primes, the answer to the
last question is yes.
