wild_partition_large_order_resource_bounds
Suppose n is odd, q>=10000000, 3q<=n<=3q+2, and a proper n-coloring of K_n has a bijection between colors and their unique missing vertices. For any block map whose union of h blocks has between 3h and 3h+(n-3q) vertices, the displayed canonical seal-event weight sums through every position and every vertex are each at most 1/50.
Statement
theorem wild_partition_large_order_resource_bounds {n q : ℕ} (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) : (∀ p : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50) ∧ (∀ w : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50)
- Source
- Uniform resource estimate for OP-306, extending the triple-only estimate to one or two blocks of size four. For h>=2 use two exposed binomial factors; h=1 is bounded separately at sizes 3,4,5. Experiment 7974 checks finite instances but is not used as a proof.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- wild_partition_of_resource_boundsLet n>0 and let a proper coloring of K_n use the color set Fin n. Fix a partition map b from the vertices onto q blocks, with a specified…
- wild_triple_partition_large_order_mass_boundFor odd q>=100001, both canonical seal-event resource sums for q triples of vertices in K_(3q), with weight (21/20)^d/(3q)_d, are at most…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- wild_number_complete_graph_min_proper_coloring_geLet n ≥ 3 and let ρ be a minimum proper edge colouring of K_n (a proper colouring with χ'(K_n) colours). Then wld_ρ(K_n) ≥ ⌊4⌈n/2⌉/3⌋.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 1
- wild_number_complete_graph_large_eqFor every integer n>=30000001, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge…
The proof, explained
The theorem bounds the total displayed canonical seal-event weights passing through any fixed position and any fixed vertex by 1/50. By partitioning events according to their assigned color and block set, the number of closed subsets is bounded in terms of the missing-vertex classes. The resulting event weights simplify to a ratio of binomial coefficients that is uniformly bounded by an auxiliary function for large q ≥ 10^7. Summing over all block subsets reduces the resource bound to a rapidly converging geometric series whose total sum is at most 1/50.
Definition of the canonical block map wsc_blk and its root section wsc_root.
Each vertex v < 3q is mapped to block ⌊v/3⌋, and each of the a excess vertices 3q + j is assigned to block j. The section wsc_root maps block b to 3b. Linear arithmetic verifies that all indices remain within valid bounds.
def wsc_blk (hq : 3 ≤ q) (a : Fin 3) (v : Fin (3 * q + a.val)) : Fin q := if h : v.val < 3 * q then ⟨v.val / 3, by omega⟩ else ⟨v.val - 3 * q, by have := a.isLt; have := v.isLt; omega⟩ def wsc_root (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : Fin (3 * q + a.val) := ⟨3 * b.val, by have := b.isLt; omega⟩
wsc_root is a right inverse of wsc_blk on each block b: wsc_blk(wsc_root(b)) = b.
Because b < q, 3b < 3q, so evaluating wsc_blk at 3b performs integer division (3b)/3 = b.
uses
Fin.ext_ifflemma wsc_root_blk (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : wsc_blk hq a (wsc_root hq a b) = b := by have hb := b.isLt have hlt : 3*b.val < 3*q := by omega simp [wsc_blk, wsc_root, hlt, Fin.ext_iff]
For each block b, the preimage fiber under wsc_blk has cardinality 3 + (if b < a then 1 else 0).
The preimage is explicitly {3b, 3b+1, 3b+2} if b ≥ a, and contains an additional excess vertex 3q + b if b < a. Case analysis on b < a computes the cardinality of these explicit disjoint sets.
uses
Finset.card_insert_of_notMem,Finset.card_pair,if_pos,if_neglemma wsc_blk_fibre (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : (Finset.univ.filter fun v => wsc_blk hq a v = b).card = 3 + if b.val < a.val then 1 else 0 := by have hb := b.isLt have ha := a.isLt by_cases hba : b.val < a.val · have hf : (Finset.univ.filter fun v => wsc_blk hq a v = b) = {⟨3 * b.val, by omega⟩, ⟨3 * b.val + 1, by omega⟩, ⟨3 * b.val + 2, by omega⟩, ⟨3 * q + b.val, by omega⟩} := by ext v simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton, wsc_blk, Fin.ext_iff] split_ifs <;> dsimp <;> omega rw [hf, if_pos hba] rw [Finset.card_insert_of_notMem (by simp [Fin.ext_iff]; omega), Finset.card_insert_of_notMem (by simp [Fin.ext_iff]; omega), Finset.card_pair (by simp [Fin.ext_iff]; omega)] · have hf : (Finset.univ.filter fun v => wsc_blk hq a v = b) = {⟨3 * b.val, by omega⟩, ⟨3 * b.val + 1, by omega⟩, ⟨3 * b.val + 2, by omega⟩} := by ext v simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton, wsc_blk, Fin.ext_iff] split_ifs <;> dsimp <;> omega rw [hf, if_neg hba, Finset.card_insert_of_notMem (by simp [Fin.ext_iff]), Finset.card_pair (by simp [Fin.ext_iff])]
For any block set T, |wsc_pos T| = 3|T| + |{b ∈ T : b < a}|.
By partitioning the preimage wsc_pos T into fibers over each block b ∈ T, the total size is the sum of fiber sizes 3 + (if b < a then 1 else 0), which separates into 3|T| and the count of blocks below a.
uses
Finset.card_eq_sum_card_fiberwise,wsc_blk_fibre,wsc_mem_pos,Finset.sum_add_distrib,Finset.sum_constlemma wsc_card_pos (hq : 3 ≤ q) (a : Fin 3) (T : Finset (Fin q)) : (wsc_pos (wsc_blk hq a) T).card = 3 * T.card + (T.filter fun b => b.val < a.val).card := by classical have he : (wsc_pos (wsc_blk hq a) T).card = ∑ b ∈ T, (3 + if b.val < a.val then 1 else 0) := by rw [Finset.card_eq_sum_card_fiberwise (f := wsc_blk hq a) (t := T)] · refine Finset.sum_congr rfl fun b hb => ?_ rw [← wsc_blk_fibre hq a b] congr 1 ext v simp only [Finset.mem_filter, wsc_mem_pos, Finset.mem_univ, true_and] exact and_iff_right_of_imp (fun h => h ▸ hb) · intro v hv exact wsc_mem_pos.1 hv rw [he, Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, mul_comm] congr 1 simp
For any block set T, 3|T| ≤ |wsc_pos T| ≤ 3|T| + a.
The number of blocks in T strictly less than a is at most |{0, ..., a-1}| = a, so the formula from wsc_card_pos yields the bounds immediately.
uses
Finset.card_le_card_of_injOn,Finset.card_range,wsc_card_poslemma wsc_card_pos_bounds (hq : 3 ≤ q) (a : Fin 3) (T : Finset (Fin q)) : 3 * T.card ≤ (wsc_pos (wsc_blk hq a) T).card ∧ (wsc_pos (wsc_blk hq a) T).card ≤ 3 * T.card + a.val := by have hs : (T.filter fun b => b.val < a.val).card ≤ a.val := by calc _ ≤ (Finset.range a.val).card := by refine Finset.card_le_card_of_injOn Fin.val ?_ ?_ · intro b hb exact Finset.mem_range.2 (Finset.mem_filter.1 hb).2 · intro b hb b' hb' he exact Fin.ext he _ = _ := Finset.card_range _ rw [wsc_card_pos] omega
When 3q ≤ n, 3h ≤ k, and k - 3h ≤ n - 3q, (q choose h)^3 ≤ (n choose k).
Cubing gives (q choose h)^3 ≤ (3q choose 3h). Multiplying by the non-zero factor (n - 3q choose k - 3h) ≥ 1 and applying the Vandermonde-type convolution bound yields the result.
uses
Nat.choose_pos,wtc_choose_cube,wtc_choose_mul_leset_option maxHeartbeats 1000000 set_option maxRecDepth 4000 lemma wsc_choose_cube (n q h k : ℕ) (hn : 3 * q ≤ n) (hk : 3 * h ≤ k) (hrem : k - 3 * h ≤ n - 3 * q) : q.choose h ^ 3 ≤ n.choose k := by have he : 1 ≤ (n - 3 * q).choose (k - 3 * h) := Nat.choose_pos hrem calc _ ≤ (3 * q).choose (3 * h) := wtc_choose_cube q h _ ≤ (3 * q).choose (3 * h) * (n - 3 * q).choose (k - 3 * h) := by nlinarith only [he] _ ≤ _ := by convert wtc_choose_mul_le (3 * q) (n - 3 * q) (3 * h) (k - 3 * h) using 1 <;> congr 1 <;> omega
wsc_prob n k is non-negative.
By definition, wsc_prob n k is a product and quotient of positive binomial coefficients and positive powers of 21/20.
noncomputable def wsc_prob (n k : ℕ) : ℝ := ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ) * (21 / 20 : ℝ)^k lemma wsc_prob_nonneg (n k : ℕ) : 0 ≤ wsc_prob n k := by unfold wsc_prob; positivity
k! * ((n/2) choose (k/2)) * wsc_wt n k = wsc_prob n k.
Unfolding the definition of the event weight wsc_wt n k = (21/20)^k / n.descFactorial k, the descending factorial identity n.descFactorial k = k! * (n choose k) cancels k! and converts the denominator into (n choose k), matching wsc_prob.
uses
Nat.descFactorial_eq_factorial_mul_chooselemma wsc_prob_factorial (n k : ℕ) : (k.factorial : ℝ) * ((n / 2).choose (k / 2) : ℝ) * wsc_wt n k = wsc_prob n k := by unfold wsc_wt wsc_prob rw [Nat.descFactorial_eq_factorial_mul_choose] push_cast have hf : (k.factorial : ℝ) ≠ 0 := by positivity by_cases hc : (n.choose k : ℝ) = 0 · simp [hc] · field_simp
For h = 1 and 3 ≤ k ≤ 5, (q - 1) * (q * ((n/2) choose (k/2)) / (n choose k)) ≤ 8.
For k = 3, (n choose 3) ≥ q^3 and ((n/2) choose 1) ≤ 2q, giving a product bounded by 2q^3 ≤ 8(n choose 3). For k ∈ {4, 5}, (n choose k) ≥ (q choose 2) * q^2 and ((n/2) choose (k/2)) ≤ 4q^2, yielding the same bound.
uses
Nat.cast_choose_two,wtc_choose_cube,Nat.choose_le_choose,wtc_choose_mul_lelemma wsc_small_ratio (n q k : ℕ) (hq : 10000000 ≤ q) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (hk0 : 3 ≤ k) (hk1 : k ≤ 5) : ((q : ℝ) - 1) * ((q : ℝ) * ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ)) ≤ 8 := by let B : ℝ := q.choose 2 let C : ℝ := n.choose k let D : ℝ := (n / 2).choose (k / 2) have hqR : (10000000 : ℝ) ≤ q := by exact_mod_cast hq have hqm : 0 < (q : ℝ)-1 := by linarith have hq0 : 0 < (q : ℝ) := by linarith have hc : 0 < C := by dsimp only [C]; exact_mod_cast Nat.choose_pos (by omega : k ≤ n) have hm : ((n / 2 : ℕ) : ℝ) ≤ 2 * (q : ℝ) := by exact_mod_cast (show n / 2 ≤ 2 * q by omega) have hb : B = (q : ℝ) * ((q : ℝ)-1) / 2 := by dsimp only [B] rw [Nat.cast_choose_two] have hbq : (q : ℝ) ≤ B := by rw [hb]; nlinarith change (q : ℝ) ≤ (q.choose 2 : ℝ) at hbq have hD : D ≤ 4 * (q : ℝ)^2 := by dsimp only [D] have hk2 : k / 2 = 1 ∨ k / 2 = 2 := by omega rcases hk2 with ht | ht · rw [ht, Nat.choose_one_right] nlinarith · rw [ht, Nat.cast_choose_two] have hm0 : (0 : ℝ) ≤ ((n / 2 : ℕ) : ℝ) := by positivity nlinarith have hbound : ((q : ℝ)-1) * (q : ℝ) * D ≤ 8 * C := by by_cases hk3 : k = 3 · subst k have hc3 : (q : ℝ)^3 ≤ C := by dsimp only [C] have ht : q^3 ≤ n.choose 3 := by simpa only [Nat.choose_one_right, Nat.mul_one] using (wtc_choose_cube q 1).trans (Nat.choose_le_choose 3 hn0) exact_mod_cast ht have hd : D ≤ 2 * (q : ℝ) := by dsimp only [D]; norm_num; exact hm have hmul := mul_le_mul_of_nonneg_left hd (by positivity : 0 ≤ ((q : ℝ)-1)*(q : ℝ)) calc _ ≤ ((q : ℝ)-1)*(q : ℝ)*(2*(q : ℝ)) := hmul _ ≤ 2*(q : ℝ)^3 := by nlinarith only [sq_nonneg (q : ℝ)] _ ≤ 8*C := by nlinarith only [hc3, hc.le] · have hcn : B * (q : ℝ)^2 ≤ C := by have h2 := wtc_choose_mul_le q q 1 1 have h4 := wtc_choose_mul_le q (q + q) 2 2 have h3 := wtc_choose_mul_le q q 2 1 have h5 := wtc_choose_mul_le q (q + q) 2 3 have hbN : q ≤ q.choose 2 := by exact_mod_cast hbq have hk45 : k = 4 ∨ k = 5 := by omega rcases hk45 with rfl | rfl · dsimp only [B, C] exact_mod_cast (calc q.choose 2 * q^2 ≤ (3*q).choose 4 := by have ht := (Nat.mul_le_mul_left (q.choose 2) h2).trans h4 simpa only [Nat.choose_one_right, show q+(q+q)=3*q by omega, Nat.pow_two] using ht _ ≤ _ := Nat.choose_le_choose 4 hn0) · dsimp only [B, C] have h23 : q^2 ≤ (q+q).choose 3 := by calc _ ≤ q.choose 2 * q := by nlinarith only [Nat.mul_le_mul_right q hbN] _ ≤ _ := by simpa only [Nat.choose_one_right] using h3 exact_mod_cast (calc q.choose 2 * q^2 ≤ (3*q).choose 5 := by have ht := (Nat.mul_le_mul_left (q.choose 2) h23).trans h5 simpa only [show q+(q+q)=3*q by omega] using ht _ ≤ _ := Nat.choose_le_choose 5 hn0) have hmul := mul_le_mul_of_nonneg_left hD (by positivity : 0 ≤ ((q : ℝ)-1)*(q : ℝ)) rw [hb] at hcn nlinarith only [hmul, hcn] change ((q : ℝ)-1) * ((q : ℝ)*D/C) ≤ 8 rw [← mul_div_assoc, div_le_iff₀ hc] simpa only [mul_assoc] using hbound
For 1 ≤ h ≤ q/2 and 3h ≤ k ≤ 3h + (n - 3q), 5h * (q choose h) * wsc_prob n k ≤ (1/20000) * h^2 * (5/6)^h.
For h = 1, the bound follows directly from wsc_small_ratio and (21/20)^k ≤ 2 because q ≥ 10^7. For h ≥ 2, we square both sides: the product of ratios (q choose h)^3 / (n choose k) and ((n/2) choose (k/2))^2 / (n choose k) is at most 1, while the factor q(q - 1) 2^(h-2) ≤ h(h-1)(q choose h) introduces a factor of q(q-1) ≥ 8 * 10^10 that easily absorbs the constant.
uses
wsc_small_ratio,wsc_choose_cube,wtc_choose_square,wtc_choose_lower_twolemma wsc_mass_term_bound (n q h k : ℕ) (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (h1 : 1 ≤ h) (hh : 2 * h ≤ q) (hk0 : 3 * h ≤ k) (hk1 : k ≤ 3 * h + (n - 3 * q)) : (5 * h : ℝ) * (q.choose h : ℝ) * wsc_prob n k ≤ (1 / 20000 : ℝ) * (h : ℝ)^2 * (5 / 6 : ℝ)^h := by have hqR : (10000000 : ℝ) ≤ q := by exact_mod_cast hq have hqm : 0 < (q : ℝ)-1 := by linarith have hk2 : k ≤ 3 * h + 2 := by omega by_cases heq : h = 1 · subst h have hr := wsc_small_ratio n q k hq hn0 hn1 (by omega) (by omega) have hp : (21 / 20 : ℝ)^k ≤ 2 := by calc _ ≤ (21 / 20 : ℝ)^5 := pow_le_pow_right₀ (by norm_num) (by omega) _ ≤ _ := by norm_num have hn : (0 : ℝ) ≤ (q : ℝ) * ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ) := by positivity have hh := mul_le_mul hr hp (by positivity) (by norm_num : (0 : ℝ) ≤ 8) norm_num only [Nat.choose_one_right, Nat.cast_one, mul_one, one_pow] at * apply (mul_le_mul_iff_of_pos_left hqm).mp unfold wsc_prob have hsmall : (80 : ℝ) ≤ ((q : ℝ)-1) * (1 / 24000) := by linarith calc _ = 5 * (((q : ℝ)-1)*((q : ℝ)*((n/2).choose (k/2) : ℝ)/(n.choose k : ℝ))*(21/20 : ℝ)^k) := by ring _ ≤ 80 := by nlinarith only [hh] _ ≤ _ := hsmall have h2 : 2 ≤ h := by omega let B : ℝ := q.choose h let C : ℝ := n.choose k let D : ℝ := (n / 2).choose (k / 2) have hb : 0 < B := by dsimp only [B]; exact_mod_cast Nat.choose_pos (by omega : h ≤ q) have hc : 0 < C := by dsimp only [C]; exact_mod_cast Nat.choose_pos (by omega : k ≤ n) have hd : 0 ≤ D := by positivity have hb3 : B^3 ≤ C := by dsimp only [B, C] exact_mod_cast wsc_choose_cube n q h k hn0 hk0 (by omega) have hnn : 2 * (n / 2) + 1 = n := by omega have hd2 : D^2 ≤ C := by dsimp only [D, C] exact_mod_cast (hnn ▸ wtc_choose_square (n / 2) k) have hchoose : (q : ℝ) * ((q : ℝ) - 1) * 2^(h-2) ≤ (h : ℝ) * ((h : ℝ) - 1) * B := by dsimp only [B] have ht : ((q * (q - 1) * 2 ^ (h - 2) : ℕ) : ℝ) ≤ ((h * (h - 1) * q.choose h : ℕ) : ℝ) := by exact_mod_cast wtc_choose_lower_two q h h2 hh simp only [Nat.cast_mul] at ht rw [Nat.cast_sub (by omega : 1 ≤ q), Nat.cast_sub (by omega : 1 ≤ h)] at ht simpa using ht have hhR : 2 ≤ (h : ℝ) := by exact_mod_cast h2 have hhm : 0 ≤ (h : ℝ)-1 := by linarith have hbase : (21 / 20 : ℝ)^6 ≤ 2 * (5 / 6 : ℝ)^2 := by norm_num have hpw := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21 / 20)^6) hbase h have hp0 : ((21 / 20 : ℝ)^(3*h))^2 ≤ 2^h*((5/6 : ℝ)^h)^2 := by have he1 : 3*h*2=6*h := by omega have he2 : 2*h=h*2 := by omega simpa only [mul_pow, ← pow_mul, he1, he2] using hpw have hpweq : ((21 / 20 : ℝ)^k)^2 ≤ 2 * 2^h * ((5 / 6 : ℝ)^h)^2 := by have hkpow : (21 / 20 : ℝ)^k ≤ (21/20)^(3*h+2) := pow_le_pow_right₀ (by norm_num) hk2 have hkp := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21/20)^k) hkpow 2 have he : ((21 / 20 : ℝ)^(3*h+2))^2 = (21/20)^4 * ((21/20)^(3*h))^2 := by rw [pow_add]; ring rw [he] at hkp have hp4 : (21 / 20 : ℝ)^4 ≤ 2 := by norm_num exact hkp.trans (by nlinarith only [mul_le_mul hp4 hp0 (by positivity) (by norm_num : (0 : ℝ) ≤ 2)]) have h2pow : (2 : ℝ)^h = 4 * (2 : ℝ)^(h-2) := by calc (2 : ℝ)^h = 2^(h-2+2) := by congr 1; omega _ = _ := by rw [pow_add]; norm_num; ring have hratio : B * (B * D / C)^2 ≤ 1 := by have hmul : B^3 * D^2 ≤ C^2 := by simpa only [pow_two] using mul_le_mul hb3 hd2 (by positivity : 0 ≤ D^2) (by positivity : 0 ≤ C) have he : B * (B * D / C)^2 = (B^3 * D^2) / C^2 := by ring rw [he, div_le_one (sq_pos_of_pos hc)] exact hmul have hratio' : (q : ℝ) * ((q : ℝ)-1) * 2^(h-2) * (B * D / C)^2 ≤ (h : ℝ) * ((h : ℝ)-1) := by calc _ ≤ ((h : ℝ) * ((h : ℝ)-1) * B) * (B * D / C)^2 := mul_le_mul_of_nonneg_right hchoose (sq_nonneg _) _ = (h : ℝ) * ((h : ℝ)-1) * (B * (B * D / C)^2) := by ring _ ≤ _ := by simpa using mul_le_mul_of_nonneg_left hratio (by positivity : 0 ≤ (h : ℝ)*((h : ℝ)-1)) have hs := mul_le_mul hratio' hpweq (by positivity) (by positivity : 0 ≤ (h : ℝ)*((h : ℝ)-1)) rw [h2pow] at hs have hs' : (q : ℝ)*((q : ℝ)-1)*(B*D/C)^2*((21/20 : ℝ)^k)^2 ≤ 8*(h : ℝ)*((h : ℝ)-1)*((5/6 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < 2^(h-2))).mp nlinarith only [hs] have hquot : ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 = 25*(h : ℝ)^2*(B*D/C)^2*((21/20 : ℝ)^k)^2 := by dsimp [wsc_prob, B, C, D]; push_cast; ring have hupper : (q : ℝ)*((q : ℝ)-1)*((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 ≤ 200*(h : ℝ)^4*((5/6 : ℝ)^h)^2 := by rw [hquot] have hm1 := mul_le_mul_of_nonneg_left hs' (by positivity : 0 ≤ 25*(h : ℝ)^2) have hhh : (h : ℝ)*((h : ℝ)-1) ≤ (h : ℝ)^2 := by nlinarith have hm2 := mul_le_mul_of_nonneg_left hhh (by positivity : 0 ≤ 200*(h : ℝ)^2*((5/6 : ℝ)^h)^2) nlinarith only [hm1, hm2] have hqq : (80000000000 : ℝ) ≤ (q : ℝ)*((q : ℝ)-1) := by nlinarith [sq_nonneg ((q : ℝ)-10000000)] have hsq : ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 ≤ ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < (q : ℝ)*((q : ℝ)-1))).mp calc _ ≤ 200*(h : ℝ)^4*((5/6 : ℝ)^h)^2 := hupper _ ≤ _ := by have hx := mul_le_mul_of_nonneg_right hqq (by positivity : 0 ≤ ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)^2) nlinarith only [hx] have hnon : 0 ≤ (1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by positivity nlinarith [sq_nonneg ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k + (1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)]
wsc_phi q h is non-negative.
wsc_phi q h is defined as the quotient of (1/20000) * h^2 * (5/6)^h by 5h * (q choose h), both of which are positive.
noncomputable def wsc_phi (q h : ℕ) : ℝ := ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h) / ((5*h : ℝ)*(q.choose h : ℝ)) lemma wsc_phi_nonneg (q h : ℕ) : 0 ≤ wsc_phi q h := by unfold wsc_phi; positivity
wsc_prob n k is bounded above by wsc_phi q h.
Dividing the mass term bound 5h * (q choose h) * wsc_prob n k ≤ (1/20000) * h^2 * (5/6)^h by 5h * (q choose h) yields wsc_prob n k ≤ wsc_phi q h.
uses
wsc_mass_term_boundlemma wsc_prob_le_phi (n q h k : ℕ) (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (h1 : 1 ≤ h) (hh : 2 * h ≤ q) (hk0 : 3 * h ≤ k) (hk1 : k ≤ 3 * h + (n - 3 * q)) : wsc_prob n k ≤ wsc_phi q h := by have hb : 0 < (q.choose h : ℝ) := by exact_mod_cast Nat.choose_pos (by omega : h ≤ q) unfold wsc_phi rw [le_div_iff₀ (by positivity : (0 : ℝ) < (5*h : ℝ)*(q.choose h : ℝ))] nlinarith only [wsc_mass_term_bound n q h k hq hodd hn0 hn1 h1 hh hk0 hk1]
5h * (q choose h) * wsc_phi q h = (1/20000) * h^2 * (5/6)^h.
Multiplying wsc_phi by the denominator 5h * (q choose h) in its definition directly cancels it.
uses
Nat.choose_ne_zerolemma wsc_phi_cancel (q h : ℕ) (h1 : 1 ≤ h) (hh : h ≤ q) : (5*h : ℝ) * (q.choose h : ℝ) * wsc_phi q h = (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by have hb : (q.choose h : ℝ) ≠ 0 := by exact_mod_cast Nat.choose_ne_zero hh have hhh : (h : ℝ) ≠ 0 := by exact_mod_cast (by omega : h ≠ 0) unfold wsc_phi field_simp
n * ((q - 1) choose (h - 1)) * wsc_phi q h ≤ (1/20000) * h^2 * (5/6)^h.
Using the binomial absorption identity q * ((q - 1) choose (h - 1)) = h * (q choose h) and n ≤ 3q + 2 ≤ 5q, we bound n * ((q - 1) choose (h - 1)) by 5h * (q choose h), reducing the expression to wsc_phi_cancel.
uses
Nat.add_one_mul_choose_eq,wsc_phi_cancellemma wsc_position_phi_bound (n q h : ℕ) (hq : 10000000 ≤ q) (hn : n ≤ 3*q+2) (h1 : 1 ≤ h) (hh : 2*h ≤ q) : (n : ℝ) * ((q-1).choose (h-1) : ℝ) * wsc_phi q h ≤ (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by have hi := Nat.add_one_mul_choose_eq (q-1) (h-1) rw [Nat.sub_add_cancel (by omega : 1 ≤ q), Nat.sub_add_cancel h1] at hi have hir : (q : ℝ) * ((q-1).choose (h-1) : ℝ) = (q.choose h : ℝ) * (h : ℝ) := by exact_mod_cast hi have hnr : (n : ℝ) ≤ 5*(q : ℝ) := by exact_mod_cast (show n ≤ 5*q by omega) calc _ ≤ 5*(q : ℝ) * ((q-1).choose (h-1) : ℝ) * wsc_phi q h := by exact mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_right hnr (by positivity)) (wsc_phi_nonneg _ _) _ = (5*h : ℝ)*(q.choose h : ℝ)*wsc_phi q h := by rw [mul_assoc 5, hir]; ring _ = _ := wsc_phi_cancel q h h1 (by omega)
The geometric sum over h of (1/20000) * h^2 * (5/6)^h is at most 1/50.
The total sum over h of h^2 * (5/6)^h is bounded by 330 via wtc_geometric_square_sum, and 330 / 20000 ≤ 1/50.
uses
wtc_geometric_square_sumlemma wsc_geometric_bound (q : ℕ) : ∑ h ∈ Finset.range (q+1), (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h ≤ 1/50 := by have hi := wtc_geometric_square_sum (q+1) simp only [mul_assoc] rw [← Finset.mul_sum] nlinarith
The shifted geometric sum over h of (1/20000) * (h + 1)^2 * (5/6)^(h + 1) is at most 1/50.
Reindexing the non-negative series by shifting h to h + 1 drops the h = 0 term and bounds the sum by the full geometric sum wsc_geometric_bound.
uses
wsc_geometric_boundlemma wsc_shifted_geometric_bound (q : ℕ) : ∑ h ∈ Finset.range q, (1/20000 : ℝ)*((h+1 : ℕ) : ℝ)^2*(5/6 : ℝ)^(h+1) ≤ 1/50 := by have hi := wsc_geometric_bound q rw [Finset.sum_range_succ'] at hi norm_num at hi simpa only [Nat.cast_add, Nat.cast_one] using hi set_option maxHeartbeats 1000000 set_option maxRecDepth 100000 variable {n q : ℕ}
Each missing-vertex class w279_R has cardinality n / 2.
For odd n, the color matching leaves a unique missing vertex, and the missing-vertex class R has size (n - 1)/2 = n / 2 by w279_card_R.
uses
w279_card_Rlemma wsc_R_card (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (i : Fin n) : (w279_R c m i).card = n / 2 := by have := w279_card_R c m hm i omega
The number of events with fixed color i and block set T is bounded by |wsc_pos T|! times the number of valid closed vertex subsets.
Any event is determined by its color i, block set T, and a permutation of the positions wsc_pos T. By injecting the fiber into permutations and applying w279_count_events, the bound follows.
uses
w279_count_events,Finset.card_le_card_of_injOntheorem wsc_fibre_card (b : Fin n → Fin q) (i : Fin n) (T : Finset (Fin q)) (P : Finset (Fin n) → Prop) [DecidablePred P] (Fsel : Finset (Fin n × Finset (Fin q) × (Fin n → Fin n))) (hF : ∀ t ∈ Fsel, t.1 = i → t.2.1 = T → (∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ P ((wsc_pos b t.2.1).image t.2.2)) : (Fsel.filter fun t => (t.1, t.2.1) = (i, T)).card ≤ (wsc_pos b T).card.factorial * (Finset.univ.filter fun U : Finset (Fin n) => U.card = (wsc_pos b T).card ∧ P U).card := by classical refine le_trans ?_ (w279_count_events (wsc_pos b T) P) refine Finset.card_le_card_of_injOn (fun t => t.2.2) ?_ ?_ · intro t ht simp only [Finset.coe_filter, Set.mem_setOf_eq, Prod.mk.injEq] at ht obtain ⟨ht, h1, h2⟩ := ht obtain ⟨g1, g2, g3⟩ := hF t ht h1 h2 rw [h2] at g1 g2 g3 simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_setOf_eq] exact ⟨g1, g2, g3⟩ · intro t ht t' ht' h simp only [Finset.coe_filter, Set.mem_setOf_eq, Prod.mk.injEq] at ht ht' obtain ⟨-, h1, h2⟩ := ht obtain ⟨-, h1', h2'⟩ := ht' exact Prod.ext (h1.trans h1'.symm) (Prod.ext (h2.trans h2'.symm) h)
For any position p, the sum of event weights containing p is at most 1/50.
Partition the events by color i and block set T containing b(p). Bounding the fiber by |pos|! * ((n/2) choose (|pos|/2)) converts the event weight into wsc_prob, which is at most wsc_phi q |T|. Summing over colors introduces a factor of n, while summing over all block sets T containing b(p) of size m + 1 introduces ((q - 1) choose m). The position bound and shifted geometric summation bound the total by 1/50.
uses
wsc_fibre_card,wsc_R_card,w279_count_closed,wsc_prob_factorial,wsc_prob_le_phi,Finset.sum_powerset_apply_card,wsc_position_phi_bound,wsc_shifted_geometric_boundtheorem wsc_pos_mass (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (p : Fin n) : ∑ t ∈ (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50 := by classical set Fsel := (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1) with hFdef have hFmem : ∀ t ∈ Fsel, (1 ≤ t.2.1.card ∧ t.2.1.card ≤ (q / 2) ∧ b p ∈ t.2.1) ∧ ((∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ w279_closed c t.1 ((wsc_pos b t.2.1).image t.2.2)) := by intro t ht rw [hFdef, Finset.mem_filter, wsc_mem_E ] at ht exact ⟨⟨ht.1.1, ht.1.2.1, wsc_mem_pos.1 ht.2⟩, ht.1.2.2⟩ let 𝒯 : Finset (Finset (Fin q)) := Finset.univ.filter fun T => 1 ≤ T.card ∧ T.card ≤ (q / 2) ∧ b p ∈ T let φ : ℕ → ℝ := wsc_phi q have step1 : ∑ t ∈ Fsel, wsc_wt n (wsc_pos b t.2.1).card ≤ ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, φ x.2.card := by rw [← Finset.sum_fiberwise_of_maps_to (g := fun t => (t.1, t.2.1)) (t := Finset.univ ×ˢ 𝒯)] · refine Finset.sum_le_sum fun x hx => ?_ have hw : ∀ t ∈ Fsel.filter (fun t => (t.1, t.2.1) = x), wsc_wt n (wsc_pos b t.2.1).card = wsc_wt n (wsc_pos b x.2).card := by intro t ht rw [Finset.mem_filter] at ht rw [← ht.2] rw [Finset.sum_congr rfl hw, Finset.sum_const, nsmul_eq_mul] have hc := wsc_fibre_card b x.1 x.2 (fun U => w279_closed c x.1 U) Fsel ?_ · have hc2 := w279_count_closed c m hm x.1 (wsc_pos b x.2).card rw [wsc_R_card c m hm] at hc2 have hc3 : (Fsel.filter fun t => (t.1, t.2.1) = x).card ≤ (wsc_pos b x.2).card.factorial * Nat.choose (n / 2) ((wsc_pos b x.2).card / 2) := by refine le_trans hc (Nat.mul_le_mul_left _ (le_trans (Finset.card_le_card ?_) hc2)) intro U hU simp only [Finset.mem_filter] at hU ⊢ exact hU have hT := (Finset.mem_filter.1 (Finset.mem_product.1 hx).2).2 have hb := hblock x.2 have hcR : ((Fsel.filter fun t => (t.1, t.2.1) = x).card : ℝ) ≤ (((wsc_pos b x.2).card.factorial * Nat.choose (n/2) ((wsc_pos b x.2).card/2) : ℕ) : ℝ) := by exact_mod_cast hc3 calc _ ≤ _ := mul_le_mul_of_nonneg_right hcR (wsc_wt_nonneg n _) _ = wsc_prob n (wsc_pos b x.2).card := by push_cast; exact wsc_prob_factorial n _ _ ≤ φ x.2.card := wsc_prob_le_phi n q x.2.card (wsc_pos b x.2).card hq hodd hn0 hn1 hT.1 (by omega) hb.1 (by have := hb.2; omega) · intro t ht hi _ obtain ⟨-, h1, h2, h3⟩ := hFmem t ht exact ⟨h1, h2, by rw [← hi]; exact h3⟩ · intro t ht obtain ⟨h0, -⟩ := hFmem t ht exact Finset.mem_product.2 ⟨Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _, h0⟩⟩ have step2 : ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, φ x.2.card = n * ∑ T ∈ 𝒯, φ T.card := by rw [Finset.sum_product] dsimp only rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] have step3 : ∑ T ∈ 𝒯, φ T.card = ∑ m ∈ Finset.range q, ((Nat.choose (q - 1) m : ℕ) : ℝ) * (if m + 1 ≤ (q / 2) then φ (m + 1) else 0) := by set b := b p have hcard : (Finset.univ.erase b).card = (q - 1) := by rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] have e1 : ∑ T ∈ 𝒯, φ T.card = ∑ T' ∈ (Finset.univ.erase b).powerset.filter (fun T' => T'.card + 1 ≤ (q / 2)), φ (T'.card + 1) := by refine Finset.sum_nbij' (fun T => T.erase b) (fun T' => insert b T') ?_ ?_ ?_ ?_ ?_ · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT simp only [Finset.mem_filter, Finset.mem_powerset] refine ⟨Finset.erase_subset_erase _ (Finset.subset_univ _), ?_⟩ rw [Finset.card_erase_add_one hT.2.2]; exact hT.2.1 · intro T' hT' simp only [Finset.mem_filter, Finset.mem_powerset] at hT' have hb : b ∉ T' := fun h => by simpa using hT'.1 h simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] rw [Finset.card_insert_of_notMem hb] exact ⟨by omega, hT'.2, Finset.mem_insert_self _ _⟩ · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT exact Finset.insert_erase hT.2.2 · intro T' hT' simp only [Finset.mem_filter, Finset.mem_powerset] at hT' have hb : b ∉ T' := fun h => by simpa using hT'.1 h exact Finset.erase_insert hb · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT rw [Finset.card_erase_add_one hT.2.2] rw [e1, Finset.sum_filter] have := Finset.sum_powerset_apply_card (fun m => if m + 1 ≤ (q / 2) then φ (m + 1) else 0) (x := Finset.univ.erase b) rw [hcard, Nat.sub_add_cancel (by omega : 1 ≤ q)] at this rw [this] refine Finset.sum_congr rfl fun m _ => ?_ rw [nsmul_eq_mul] calc _ ≤ _ := step1 _ = _ := by rw [step2, step3] _ ≤ ∑ h ∈ Finset.range q, (1/20000 : ℝ)*((h+1 : ℕ) : ℝ)^2*(5/6 : ℝ)^(h+1) := by rw [Finset.mul_sum] refine Finset.sum_le_sum fun h hh => ?_ by_cases hh' : h + 1 ≤ q / 2 · rw [if_pos hh'] simpa only [φ, Nat.add_sub_cancel, mul_assoc] using wsc_position_phi_bound n q (h+1) hq hn1 (by omega) (by omega) · rw [if_neg hh', mul_zero, mul_zero] positivity _ ≤ 1/50 := wsc_shifted_geometric_bound q
For any vertex w, the sum of event weights containing w is at most 1/50.
Partition events by (i, T). For m(i) = w, the number of closed subsets containing w is at most (n/2 choose |pos|/2); for m(i) ≠ w, it is at most (n/2 - 1 choose |pos|/2 - 1). Summing over all n colors uses the identity wtc_vertex_coefficient to simplify the factor to |pos| * (n/2 choose |pos|/2) ≤ 5|T| * wsc_prob ≤ 5|T| * wsc_phi. Summing over all block sets T of size h introduces (q choose h), and 5h * (q choose h) * wsc_phi cancels into the geometric series bounded by 1/50.
uses
wsc_fibre_card,w279_count_closed_mem_m,w279_count_closed_mem,wsc_R_card,wtc_vertex_coefficient,wsc_prob_factorial,wsc_prob_le_phi,Finset.sum_powerset_apply_card,wsc_phi_cancel,wsc_geometric_boundtheorem wsc_vert_mass (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (w : Fin n) : ∑ t ∈ (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50 := by classical set Fsel := (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2) with hFdef have hFmem : ∀ t ∈ Fsel, (1 ≤ t.2.1.card ∧ t.2.1.card ≤ (q / 2)) ∧ ((∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ (w279_closed c t.1 ((wsc_pos b t.2.1).image t.2.2) ∧ w ∈ (wsc_pos b t.2.1).image t.2.2)) := by intro t ht rw [hFdef, Finset.mem_filter, wsc_mem_E ] at ht exact ⟨⟨ht.1.1, ht.1.2.1⟩, ht.1.2.2.1, ht.1.2.2.2.1, ht.1.2.2.2.2, ht.2⟩ let 𝒯 : Finset (Finset (Fin q)) := Finset.univ.filter fun T => 1 ≤ T.card ∧ T.card ≤ (q / 2) let X : ℕ → ℕ := fun s => if s % 2 = 1 then Nat.choose (n / 2) (s / 2) else 0 let Y : ℕ → ℕ := fun s => Nat.choose (n / 2 - 1) (s / 2 - 1) let bnd : Fin n → ℕ → ℝ := fun i s => (s.factorial : ℝ) * (if m i = w then (X s : ℝ) else (Y s : ℝ)) have step1 : ∑ t ∈ Fsel, wsc_wt n (wsc_pos b t.2.1).card ≤ ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, bnd x.1 (wsc_pos b x.2).card * wsc_wt n (wsc_pos b x.2).card := by rw [← Finset.sum_fiberwise_of_maps_to (g := fun t => (t.1, t.2.1)) (t := Finset.univ ×ˢ 𝒯)] · refine Finset.sum_le_sum fun x hx => ?_ have hw : ∀ t ∈ Fsel.filter (fun t => (t.1, t.2.1) = x), wsc_wt n (wsc_pos b t.2.1).card = wsc_wt n (wsc_pos b x.2).card := by intro t ht rw [Finset.mem_filter] at ht rw [← ht.2] rw [Finset.sum_congr rfl hw, Finset.sum_const, nsmul_eq_mul] have hc := wsc_fibre_card b x.1 x.2 (fun U => w279_closed c x.1 U ∧ w ∈ U) Fsel ?_ · have hc2 : (Finset.univ.filter fun U : Finset (Fin n) => U.card = (wsc_pos b x.2).card ∧ (w279_closed c x.1 U ∧ w ∈ U)).card ≤ if m x.1 = w then X (wsc_pos b x.2).card else Y (wsc_pos b x.2).card := by split_ifs with hmw · have := w279_count_closed_mem_m c m hm x.1 (wsc_pos b x.2).card rw [wsc_R_card c m hm, hmw] at this exact this · have := w279_count_closed_mem c m hm x.1 (wsc_pos b x.2).card w (Ne.symm hmw) rw [wsc_R_card c m hm] at this exact this have hc3 : ((Fsel.filter fun t => (t.1, t.2.1) = x).card : ℝ) ≤ bnd x.1 (wsc_pos b x.2).card := by have h4 : (Fsel.filter fun t => (t.1, t.2.1) = x).card ≤ (wsc_pos b x.2).card.factorial * (if m x.1 = w then X (wsc_pos b x.2).card else Y (wsc_pos b x.2).card) := by refine le_trans hc (Nat.mul_le_mul_left _ (le_trans (Finset.card_le_card ?_) hc2)) intro U hU simp only [Finset.mem_filter] at hU ⊢ exact hU simp only [bnd] split_ifs at h4 ⊢ <;> exact_mod_cast h4 exact mul_le_mul_of_nonneg_right hc3 (wsc_wt_nonneg n _) · intro t ht hi _ obtain ⟨-, h1, h2, h3, h4⟩ := hFmem t ht exact ⟨h1, h2, by rw [← hi]; exact h3, h4⟩ · intro t ht obtain ⟨h0, -⟩ := hFmem t ht exact Finset.mem_product.2 ⟨Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _, h0⟩⟩ have hsumcol : ∀ s, ∑ i : Fin n, bnd i s = (((s.factorial * X s + (n - 1) * (s.factorial * Y s)) : ℕ) : ℝ) := by intro s have h1 : (Finset.univ.filter fun i : Fin n => m i = w) = {m.symm w} := by ext i; simp [Equiv.apply_eq_iff_eq_symm_apply] have h2 : (Finset.univ.filter fun i : Fin n => ¬ m i = w).card = (n - 1) := by have := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin n))) (p := fun i => m i = w) rw [h1, Finset.card_singleton, Finset.card_univ, Fintype.card_fin] at this omega simp only [bnd, mul_ite] rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, h1, h2, Finset.card_singleton] push_cast ring have step2 : ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, bnd x.1 (wsc_pos b x.2).card * wsc_wt n (wsc_pos b x.2).card = ∑ T ∈ 𝒯, (((wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n - 1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card) : ℕ) : ℝ) * wsc_wt n (wsc_pos b T).card := by rw [Finset.sum_product, Finset.sum_comm] refine Finset.sum_congr rfl fun T _ => ?_ dsimp only rw [← Finset.sum_mul, hsumcol] have step3 : ∑ T ∈ 𝒯, ((((wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n-1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card)) : ℕ) : ℝ) * wsc_wt n (wsc_pos b T).card ≤ ∑ T ∈ 𝒯, (5*T.card : ℝ)*wsc_phi q T.card := by refine Finset.sum_le_sum fun T hT => ?_ have hT' := (Finset.mem_filter.1 hT).2 have hb := hblock T have hk3 : 3 ≤ (wsc_pos b T).card := by omega have hi := wtc_vertex_coefficient n (wsc_pos b T).card hodd (by omega) hk3 have hi' : (wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n-1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card) = (wsc_pos b T).card.factorial * ((wsc_pos b T).card * (n/2).choose ((wsc_pos b T).card/2)) := by dsimp only [X, Y] nlinarith only [congrArg (fun z => (wsc_pos b T).card.factorial*z) hi] rw [hi'] push_cast have he : ((wsc_pos b T).card.factorial : ℝ) * ((wsc_pos b T).card : ℝ) * ((n/2).choose ((wsc_pos b T).card/2) : ℝ) * wsc_wt n (wsc_pos b T).card = ((wsc_pos b T).card : ℝ)*wsc_prob n (wsc_pos b T).card := by rw [← wsc_prob_factorial] ring rw [← mul_assoc, he] have hp := wsc_prob_le_phi n q T.card (wsc_pos b T).card hq hodd hn0 hn1 hT'.1 (by omega) hb.1 (by have := hb.2; omega) have hk : ((wsc_pos b T).card : ℝ) ≤ (5*T.card : ℝ) := by exact_mod_cast (show (wsc_pos b T).card ≤ 5*T.card by have := hb.2; omega) exact mul_le_mul hk hp (wsc_prob_nonneg _ _) (by positivity) have step4 : (∑ T ∈ 𝒯, (5*T.card : ℝ)*wsc_phi q T.card) = ∑ h ∈ Finset.range (q+1), (q.choose h : ℝ) * (if 1 ≤ h ∧ h ≤ q/2 then (5*h : ℝ)*wsc_phi q h else 0) := by rw [Finset.sum_filter, ← Finset.powerset_univ] have he := Finset.sum_powerset_apply_card (fun h => if 1 ≤ h ∧ h ≤ q/2 then (5*h : ℝ)*wsc_phi q h else 0) (x := (Finset.univ : Finset (Fin q))) rw [Finset.card_univ, Fintype.card_fin] at he rw [he] refine Finset.sum_congr rfl fun h hh => ?_ rw [nsmul_eq_mul] calc _ ≤ _ := step1 _ = _ := step2 _ ≤ _ := step3 _ = _ := step4 _ ≤ ∑ h ∈ Finset.range (q+1), (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by refine Finset.sum_le_sum fun h hh => ?_ by_cases hh' : 1 ≤ h ∧ h ≤ q/2 · rw [if_pos hh'] have hi := wsc_phi_cancel q h hh'.1 (by omega) nlinarith only [hi] · rw [if_neg hh', mul_zero] positivity _ ≤ 1/50 := wsc_geometric_bound q
Both the position mass and vertex mass resource bounds are at most 1/50.
The conjunction follows directly by pairing the position mass bound wsc_pos_mass and the vertex mass bound wsc_vert_mass.
uses
wsc_pos_mass,wsc_vert_masstheorem wild_partition_large_order_resource_bounds {n q : ℕ} (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) : (∀ p : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50) ∧ (∀ w : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50) := by exact ⟨wsc_pos_mass hq hodd hn0 hn1 b hblock c m hm, wsc_vert_mass hq hodd hn0 hn1 b hblock c m hm⟩
Fin.ext_iff- Two elements of Fin n are equal if and only if their underlying natural values are equal.
Finset.card_insert_of_notMem- Inserting an element not in a finite set increases its cardinality by 1.
Finset.card_pair- A set containing two distinct elements has cardinality 2.
if_pos- If a condition c holds, then (if c then t else e) equals t.
if_neg- If a condition c does not hold, then (if c then t else e) equals e.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set equals the sum over t of the cardinalities of the fibers under a map into t.
wsc_blk_fibre- The fiber of each block b has size 3 plus 1 if b < a.
wsc_mem_pos- A vertex belongs to the position set of T if and only if its assigned block belongs to T.
Finset.sum_add_distrib- The sum of a sum of functions over a finite set equals the sum of their individual sums.
Finset.sum_const- The sum of a constant value over a finite set equals the set cardinality times that value.
Finset.card_le_card_of_injOn- If a map is injective on a finite set s into t, then |s| ≤ |t|.
Finset.card_range- The cardinality of Finset.range n is n.
wsc_card_pos- The cardinality of wsc_pos for a block set T is 3|T| plus the number of blocks in T with index less than a.
Nat.choose_pos- For k ≤ n, the binomial coefficient n.choose k is strictly positive.
wtc_choose_cube- The cube of (q choose h) is at most (3q choose 3h).
wtc_choose_mul_le- The product of binomial coefficients (a choose i) * (b choose j) is at most (a + b choose i + j).
Nat.descFactorial_eq_factorial_mul_choose- The descending factorial n.descFactorial k equals k! * (n choose k).
Nat.cast_choose_two- The binomial coefficient (a choose 2) equals a * (a - 1) / 2 in a division ring.
Nat.choose_le_choose- If a ≤ b, then (a choose c) ≤ (b choose c).
wsc_small_ratio- For q ≥ 10^7 and small sizes 3 ≤ k ≤ 5, the product (q-1) * (q * ((n/2) choose (k/2)) / (n choose k)) is at most 8.
wsc_choose_cube- Whenever 3q ≤ n, 3h ≤ k, and k - 3h ≤ n - 3q, (q choose h)^3 is at most (n choose k).
wtc_choose_square- The square of (m choose (s/2)) is at most (2m + 1 choose s).
wtc_choose_lower_two- For 2 ≤ h and 2h ≤ q, q * (q - 1) * 2^(h - 2) is at most h * (h - 1) * (q choose h).
wsc_mass_term_bound- For 1 ≤ h ≤ q/2 and 3h ≤ k ≤ 3h + (n - 3q), 5h * (q choose h) * wsc_prob n k is at most (1/20000) * h^2 * (5/6)^h.
Nat.choose_ne_zero- For h ≤ q, (q choose h) is non-zero.
Nat.add_one_mul_choose_eq- The binomial identity (n + 1) * (n choose k) = (n + 1 choose k + 1) * (k + 1).
wsc_phi_cancel- Multiplying wsc_phi q h by 5h * (q choose h) cancels the denominator to yield (1/20000) * h^2 * (5/6)^h.
wtc_geometric_square_sum- The sum over h of h^2 * (5/6)^h is bounded by 330.
wsc_geometric_bound- The sum of (1/20000) * h^2 * (5/6)^h up to q is at most 1/50.
w279_card_R- The missing-vertex class w279_R has cardinality n / 2.
w279_count_events- The number of events supported on a set D satisfying predicate P is bounded by |D|! times the number of subsets U with |U| = |D| satisfying P.
wsc_fibre_card- The number of events with fixed color i and block set T is bounded by |wsc_pos b T|! times the number of valid closed vertex subsets.
wsc_R_card- The size of the missing-vertex class w279_R c m i is n / 2.
w279_count_closed- The number of closed subsets of size s for color i is at most |R(i)| choose (s / 2).
wsc_prob_factorial- Multiplying k! * ((n/2) choose (k/2)) by wsc_wt n k yields wsc_prob n k.
wsc_prob_le_phi- The probability weight wsc_prob n k is bounded by the block-size function wsc_phi q h.
Finset.sum_powerset_apply_card- The sum of a function of subset size over the powerset of x equals the sum over m of (card x choose m) times the function at m.
wsc_position_phi_bound- The position-averaged bound n * ((q-1) choose (h-1)) * wsc_phi q h is at most (1/20000) * h^2 * (5/6)^h.
wsc_shifted_geometric_bound- The shifted geometric sum of (1/20000) * (h+1)^2 * (5/6)^(h+1) is at most 1/50.
w279_count_closed_mem_m- The number of closed subsets of size s containing the missing vertex m i is at most (n/2 choose s/2) when s is odd, and 0 otherwise.
w279_count_closed_mem- The number of closed subsets of size s containing a vertex w distinct from m i is at most (n/2 - 1 choose s/2 - 1).
wtc_vertex_coefficient- For odd n, the sum of 1 occurrence of (n/2 choose s/2) and (n-1) occurrences of (n/2 - 1 choose s/2 - 1) equals s * (n/2 choose s/2).
wsc_pos_mass- The sum of seal-event weights passing through any fixed position p is at most 1/50.
wsc_vert_mass- The sum of seal-event weights passing through any fixed vertex w is at most 1/50.
- Arithmetic inequalities involving large numbers (e.g. q ≥ 10^7), polynomial terms, and geometric powers are discharged using non-linear and linear arithmetic automation (omega, linarith, nlinarith, norm_num).
- Combinatorial counting repeatedly converts fiberwise sums over tuples into sums over subsets of blocks, and then into sums over subset sizes using powerset cardinality summation principles.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
Lean’s trace was cut to the first 400 of 587 tactics.
set_option maxHeartbeats 1000000set_option maxRecDepth 4000variable {q : ℕ}def wsc_blk (hq : 3 ≤ q) (a : Fin 3) (v : Fin (3 * q + a.val)) : Fin q := if h : v.val < 3 * q then ⟨v.val / 3, by omega⟩ else ⟨v.val - 3 * q, by have := a.isLt; have := v.isLt; omega⟩def wsc_root (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : Fin (3 * q + a.val) := ⟨3 * b.val, by have := b.isLt; omega⟩lemma wsc_root_blk (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : wsc_blk hq a (wsc_root hq a b) = b := by have hb := b.isLt have hlt : 3*b.val < 3*q := by omega simp [wsc_blk, wsc_root, hlt, Fin.ext_iff]lemma wsc_blk_fibre (hq : 3 ≤ q) (a : Fin 3) (b : Fin q) : (Finset.univ.filter fun v => wsc_blk hq a v = b).card = 3 + if b.val < a.val then 1 else 0 := by have hb := b.isLt have ha := a.isLt by_cases hba : b.val < a.val · have hf : (Finset.univ.filter fun v => wsc_blk hq a v = b) = {⟨3 * b.val, by omega⟩, ⟨3 * b.val + 1, by omega⟩, ⟨3 * b.val + 2, by omega⟩, ⟨3 * q + b.val, by omega⟩} := by ext v simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton, wsc_blk, Fin.ext_iff] split_ifs <;> dsimp <;> omega rw [hf, if_pos hba] rw [Finset.card_insert_of_notMem (by simp [Fin.ext_iff]; omega), Finset.card_insert_of_notMem (by simp [Fin.ext_iff]; omega), Finset.card_pair (by simp [Fin.ext_iff]; omega)] · have hf : (Finset.univ.filter fun v => wsc_blk hq a v = b) = {⟨3 * b.val, by omega⟩, ⟨3 * b.val + 1, by omega⟩, ⟨3 * b.val + 2, by omega⟩} := by ext v simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert, Finset.mem_singleton, wsc_blk, Fin.ext_iff] split_ifs <;> dsimp <;> omega rw [hf, if_neg hba, Finset.card_insert_of_notMem (by simp [Fin.ext_iff]), Finset.card_pair (by simp [Fin.ext_iff])]lemma wsc_card_pos (hq : 3 ≤ q) (a : Fin 3) (T : Finset (Fin q)) : (wsc_pos (wsc_blk hq a) T).card = 3 * T.card + (T.filter fun b => b.val < a.val).card := by classical have he : (wsc_pos (wsc_blk hq a) T).card = ∑ b ∈ T, (3 + if b.val < a.val then 1 else 0) := by rw [Finset.card_eq_sum_card_fiberwise (f := wsc_blk hq a) (t := T)] · refine Finset.sum_congr rfl fun b hb => ?_ rw [← wsc_blk_fibre hq a b] congr 1 ext v simp only [Finset.mem_filter, wsc_mem_pos, Finset.mem_univ, true_and] exact and_iff_right_of_imp (fun h => h ▸ hb) · intro v hv exact wsc_mem_pos.1 hv rw [he, Finset.sum_add_distrib, Finset.sum_const, smul_eq_mul, mul_comm] congr 1 simplemma wsc_card_pos_bounds (hq : 3 ≤ q) (a : Fin 3) (T : Finset (Fin q)) : 3 * T.card ≤ (wsc_pos (wsc_blk hq a) T).card ∧ (wsc_pos (wsc_blk hq a) T).card ≤ 3 * T.card + a.val := by have hs : (T.filter fun b => b.val < a.val).card ≤ a.val := by calc _ ≤ (Finset.range a.val).card := by refine Finset.card_le_card_of_injOn Fin.val ?_ ?_ · intro b hb exact Finset.mem_range.2 (Finset.mem_filter.1 hb).2 · intro b hb b' hb' he exact Fin.ext he _ = _ := Finset.card_range _ rw [wsc_card_pos] omegaset_option maxHeartbeats 1000000set_option maxRecDepth 4000lemma wsc_choose_cube (n q h k : ℕ) (hn : 3 * q ≤ n) (hk : 3 * h ≤ k) (hrem : k - 3 * h ≤ n - 3 * q) : q.choose h ^ 3 ≤ n.choose k := by have he : 1 ≤ (n - 3 * q).choose (k - 3 * h) := Nat.choose_pos hrem calc _ ≤ (3 * q).choose (3 * h) := wtc_choose_cube q h _ ≤ (3 * q).choose (3 * h) * (n - 3 * q).choose (k - 3 * h) := by nlinarith only [he] _ ≤ _ := by convert wtc_choose_mul_le (3 * q) (n - 3 * q) (3 * h) (k - 3 * h) using 1 <;> congr 1 <;> omeganoncomputable def wsc_prob (n k : ℕ) : ℝ := ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ) * (21 / 20 : ℝ)^klemma wsc_prob_nonneg (n k : ℕ) : 0 ≤ wsc_prob n k := by unfold wsc_prob; positivitylemma wsc_prob_factorial (n k : ℕ) : (k.factorial : ℝ) * ((n / 2).choose (k / 2) : ℝ) * wsc_wt n k = wsc_prob n k := by unfold wsc_wt wsc_prob rw [Nat.descFactorial_eq_factorial_mul_choose] push_cast have hf : (k.factorial : ℝ) ≠ 0 := by positivity by_cases hc : (n.choose k : ℝ) = 0 · simp [hc] · field_simplemma wsc_small_ratio (n q k : ℕ) (hq : 10000000 ≤ q) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (hk0 : 3 ≤ k) (hk1 : k ≤ 5) : ((q : ℝ) - 1) * ((q : ℝ) * ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ)) ≤ 8 := by let B : ℝ := q.choose 2 let C : ℝ := n.choose k let D : ℝ := (n / 2).choose (k / 2) have hqR : (10000000 : ℝ) ≤ q := by exact_mod_cast hq have hqm : 0 < (q : ℝ)-1 := by linarith have hq0 : 0 < (q : ℝ) := by linarith have hc : 0 < C := by dsimp only [C]; exact_mod_cast Nat.choose_pos (by omega : k ≤ n) have hm : ((n / 2 : ℕ) : ℝ) ≤ 2 * (q : ℝ) := by exact_mod_cast (show n / 2 ≤ 2 * q by omega) have hb : B = (q : ℝ) * ((q : ℝ)-1) / 2 := by dsimp only [B] rw [Nat.cast_choose_two] have hbq : (q : ℝ) ≤ B := by rw [hb]; nlinarith change (q : ℝ) ≤ (q.choose 2 : ℝ) at hbq have hD : D ≤ 4 * (q : ℝ)^2 := by dsimp only [D] have hk2 : k / 2 = 1 ∨ k / 2 = 2 := by omega rcases hk2 with ht | ht · rw [ht, Nat.choose_one_right] nlinarith · rw [ht, Nat.cast_choose_two] have hm0 : (0 : ℝ) ≤ ((n / 2 : ℕ) : ℝ) := by positivity nlinarith have hbound : ((q : ℝ)-1) * (q : ℝ) * D ≤ 8 * C := by by_cases hk3 : k = 3 · subst k have hc3 : (q : ℝ)^3 ≤ C := by dsimp only [C] have ht : q^3 ≤ n.choose 3 := by simpa only [Nat.choose_one_right, Nat.mul_one] using (wtc_choose_cube q 1).trans (Nat.choose_le_choose 3 hn0) exact_mod_cast ht have hd : D ≤ 2 * (q : ℝ) := by dsimp only [D]; norm_num; exact hm have hmul := mul_le_mul_of_nonneg_left hd (by positivity : 0 ≤ ((q : ℝ)-1)*(q : ℝ)) calc _ ≤ ((q : ℝ)-1)*(q : ℝ)*(2*(q : ℝ)) := hmul _ ≤ 2*(q : ℝ)^3 := by nlinarith only [sq_nonneg (q : ℝ)] _ ≤ 8*C := by nlinarith only [hc3, hc.le] · have hcn : B * (q : ℝ)^2 ≤ C := by have h2 := wtc_choose_mul_le q q 1 1 have h4 := wtc_choose_mul_le q (q + q) 2 2 have h3 := wtc_choose_mul_le q q 2 1 have h5 := wtc_choose_mul_le q (q + q) 2 3 have hbN : q ≤ q.choose 2 := by exact_mod_cast hbq have hk45 : k = 4 ∨ k = 5 := by omega rcases hk45 with rfl | rfl · dsimp only [B, C] exact_mod_cast (calc q.choose 2 * q^2 ≤ (3*q).choose 4 := by have ht := (Nat.mul_le_mul_left (q.choose 2) h2).trans h4 simpa only [Nat.choose_one_right, show q+(q+q)=3*q by omega, Nat.pow_two] using ht _ ≤ _ := Nat.choose_le_choose 4 hn0) · dsimp only [B, C] have h23 : q^2 ≤ (q+q).choose 3 := by calc _ ≤ q.choose 2 * q := by nlinarith only [Nat.mul_le_mul_right q hbN] _ ≤ _ := by simpa only [Nat.choose_one_right] using h3 exact_mod_cast (calc q.choose 2 * q^2 ≤ (3*q).choose 5 := by have ht := (Nat.mul_le_mul_left (q.choose 2) h23).trans h5 simpa only [show q+(q+q)=3*q by omega] using ht _ ≤ _ := Nat.choose_le_choose 5 hn0) have hmul := mul_le_mul_of_nonneg_left hD (by positivity : 0 ≤ ((q : ℝ)-1)*(q : ℝ)) rw [hb] at hcn nlinarith only [hmul, hcn] change ((q : ℝ)-1) * ((q : ℝ)*D/C) ≤ 8 rw [← mul_div_assoc, div_le_iff₀ hc] simpa only [mul_assoc] using hboundlemma wsc_mass_term_bound (n q h k : ℕ) (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (h1 : 1 ≤ h) (hh : 2 * h ≤ q) (hk0 : 3 * h ≤ k) (hk1 : k ≤ 3 * h + (n - 3 * q)) : (5 * h : ℝ) * (q.choose h : ℝ) * wsc_prob n k ≤ (1 / 20000 : ℝ) * (h : ℝ)^2 * (5 / 6 : ℝ)^h := by have hqR : (10000000 : ℝ) ≤ q := by exact_mod_cast hq have hqm : 0 < (q : ℝ)-1 := by linarith have hk2 : k ≤ 3 * h + 2 := by omega by_cases heq : h = 1 · subst h have hr := wsc_small_ratio n q k hq hn0 hn1 (by omega) (by omega) have hp : (21 / 20 : ℝ)^k ≤ 2 := by calc _ ≤ (21 / 20 : ℝ)^5 := pow_le_pow_right₀ (by norm_num) (by omega) _ ≤ _ := by norm_num have hn : (0 : ℝ) ≤ (q : ℝ) * ((n / 2).choose (k / 2) : ℝ) / (n.choose k : ℝ) := by positivity have hh := mul_le_mul hr hp (by positivity) (by norm_num : (0 : ℝ) ≤ 8) norm_num only [Nat.choose_one_right, Nat.cast_one, mul_one, one_pow] at * apply (mul_le_mul_iff_of_pos_left hqm).mp unfold wsc_prob have hsmall : (80 : ℝ) ≤ ((q : ℝ)-1) * (1 / 24000) := by linarith calc _ = 5 * (((q : ℝ)-1)*((q : ℝ)*((n/2).choose (k/2) : ℝ)/(n.choose k : ℝ))*(21/20 : ℝ)^k) := by ring _ ≤ 80 := by nlinarith only [hh] _ ≤ _ := hsmall have h2 : 2 ≤ h := by omega let B : ℝ := q.choose h let C : ℝ := n.choose k let D : ℝ := (n / 2).choose (k / 2) have hb : 0 < B := by dsimp only [B]; exact_mod_cast Nat.choose_pos (by omega : h ≤ q) have hc : 0 < C := by dsimp only [C]; exact_mod_cast Nat.choose_pos (by omega : k ≤ n) have hd : 0 ≤ D := by positivity have hb3 : B^3 ≤ C := by dsimp only [B, C] exact_mod_cast wsc_choose_cube n q h k hn0 hk0 (by omega) have hnn : 2 * (n / 2) + 1 = n := by omega have hd2 : D^2 ≤ C := by dsimp only [D, C] exact_mod_cast (hnn ▸ wtc_choose_square (n / 2) k) have hchoose : (q : ℝ) * ((q : ℝ) - 1) * 2^(h-2) ≤ (h : ℝ) * ((h : ℝ) - 1) * B := by dsimp only [B] have ht : ((q * (q - 1) * 2 ^ (h - 2) : ℕ) : ℝ) ≤ ((h * (h - 1) * q.choose h : ℕ) : ℝ) := by exact_mod_cast wtc_choose_lower_two q h h2 hh simp only [Nat.cast_mul] at ht rw [Nat.cast_sub (by omega : 1 ≤ q), Nat.cast_sub (by omega : 1 ≤ h)] at ht simpa using ht have hhR : 2 ≤ (h : ℝ) := by exact_mod_cast h2 have hhm : 0 ≤ (h : ℝ)-1 := by linarith have hbase : (21 / 20 : ℝ)^6 ≤ 2 * (5 / 6 : ℝ)^2 := by norm_num have hpw := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21 / 20)^6) hbase h have hp0 : ((21 / 20 : ℝ)^(3*h))^2 ≤ 2^h*((5/6 : ℝ)^h)^2 := by have he1 : 3*h*2=6*h := by omega have he2 : 2*h=h*2 := by omega simpa only [mul_pow, ← pow_mul, he1, he2] using hpw have hpweq : ((21 / 20 : ℝ)^k)^2 ≤ 2 * 2^h * ((5 / 6 : ℝ)^h)^2 := by have hkpow : (21 / 20 : ℝ)^k ≤ (21/20)^(3*h+2) := pow_le_pow_right₀ (by norm_num) hk2 have hkp := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21/20)^k) hkpow 2 have he : ((21 / 20 : ℝ)^(3*h+2))^2 = (21/20)^4 * ((21/20)^(3*h))^2 := by rw [pow_add]; ring rw [he] at hkp have hp4 : (21 / 20 : ℝ)^4 ≤ 2 := by norm_num exact hkp.trans (by nlinarith only [mul_le_mul hp4 hp0 (by positivity) (by norm_num : (0 : ℝ) ≤ 2)]) have h2pow : (2 : ℝ)^h = 4 * (2 : ℝ)^(h-2) := by calc (2 : ℝ)^h = 2^(h-2+2) := by congr 1; omega _ = _ := by rw [pow_add]; norm_num; ring have hratio : B * (B * D / C)^2 ≤ 1 := by have hmul : B^3 * D^2 ≤ C^2 := by simpa only [pow_two] using mul_le_mul hb3 hd2 (by positivity : 0 ≤ D^2) (by positivity : 0 ≤ C) have he : B * (B * D / C)^2 = (B^3 * D^2) / C^2 := by ring rw [he, div_le_one (sq_pos_of_pos hc)] exact hmul have hratio' : (q : ℝ) * ((q : ℝ)-1) * 2^(h-2) * (B * D / C)^2 ≤ (h : ℝ) * ((h : ℝ)-1) := by calc _ ≤ ((h : ℝ) * ((h : ℝ)-1) * B) * (B * D / C)^2 := mul_le_mul_of_nonneg_right hchoose (sq_nonneg _) _ = (h : ℝ) * ((h : ℝ)-1) * (B * (B * D / C)^2) := by ring _ ≤ _ := by simpa using mul_le_mul_of_nonneg_left hratio (by positivity : 0 ≤ (h : ℝ)*((h : ℝ)-1)) have hs := mul_le_mul hratio' hpweq (by positivity) (by positivity : 0 ≤ (h : ℝ)*((h : ℝ)-1)) rw [h2pow] at hs have hs' : (q : ℝ)*((q : ℝ)-1)*(B*D/C)^2*((21/20 : ℝ)^k)^2 ≤ 8*(h : ℝ)*((h : ℝ)-1)*((5/6 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < 2^(h-2))).mp nlinarith only [hs] have hquot : ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 = 25*(h : ℝ)^2*(B*D/C)^2*((21/20 : ℝ)^k)^2 := by dsimp [wsc_prob, B, C, D]; push_cast; ring have hupper : (q : ℝ)*((q : ℝ)-1)*((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 ≤ 200*(h : ℝ)^4*((5/6 : ℝ)^h)^2 := by rw [hquot] have hm1 := mul_le_mul_of_nonneg_left hs' (by positivity : 0 ≤ 25*(h : ℝ)^2) have hhh : (h : ℝ)*((h : ℝ)-1) ≤ (h : ℝ)^2 := by nlinarith have hm2 := mul_le_mul_of_nonneg_left hhh (by positivity : 0 ≤ 200*(h : ℝ)^2*((5/6 : ℝ)^h)^2) nlinarith only [hm1, hm2] have hqq : (80000000000 : ℝ) ≤ (q : ℝ)*((q : ℝ)-1) := by nlinarith [sq_nonneg ((q : ℝ)-10000000)] have hsq : ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k)^2 ≤ ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < (q : ℝ)*((q : ℝ)-1))).mp calc _ ≤ 200*(h : ℝ)^4*((5/6 : ℝ)^h)^2 := hupper _ ≤ _ := by have hx := mul_le_mul_of_nonneg_right hqq (by positivity : 0 ≤ ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)^2) nlinarith only [hx] have hnon : 0 ≤ (1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by positivity nlinarith [sq_nonneg ((5*h : ℝ)*(q.choose h : ℝ)*wsc_prob n k + (1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h)]noncomputable def wsc_phi (q h : ℕ) : ℝ := ((1 / 20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h) / ((5*h : ℝ)*(q.choose h : ℝ))lemma wsc_phi_nonneg (q h : ℕ) : 0 ≤ wsc_phi q h := by unfold wsc_phi; positivitylemma wsc_prob_le_phi (n q h k : ℕ) (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3 * q ≤ n) (hn1 : n ≤ 3 * q + 2) (h1 : 1 ≤ h) (hh : 2 * h ≤ q) (hk0 : 3 * h ≤ k) (hk1 : k ≤ 3 * h + (n - 3 * q)) : wsc_prob n k ≤ wsc_phi q h := by have hb : 0 < (q.choose h : ℝ) := by exact_mod_cast Nat.choose_pos (by omega : h ≤ q) unfold wsc_phi rw [le_div_iff₀ (by positivity : (0 : ℝ) < (5*h : ℝ)*(q.choose h : ℝ))] nlinarith only [wsc_mass_term_bound n q h k hq hodd hn0 hn1 h1 hh hk0 hk1]lemma wsc_phi_cancel (q h : ℕ) (h1 : 1 ≤ h) (hh : h ≤ q) : (5*h : ℝ) * (q.choose h : ℝ) * wsc_phi q h = (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by have hb : (q.choose h : ℝ) ≠ 0 := by exact_mod_cast Nat.choose_ne_zero hh have hhh : (h : ℝ) ≠ 0 := by exact_mod_cast (by omega : h ≠ 0) unfold wsc_phi field_simplemma wsc_position_phi_bound (n q h : ℕ) (hq : 10000000 ≤ q) (hn : n ≤ 3*q+2) (h1 : 1 ≤ h) (hh : 2*h ≤ q) : (n : ℝ) * ((q-1).choose (h-1) : ℝ) * wsc_phi q h ≤ (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by have hi := Nat.add_one_mul_choose_eq (q-1) (h-1) rw [Nat.sub_add_cancel (by omega : 1 ≤ q), Nat.sub_add_cancel h1] at hi have hir : (q : ℝ) * ((q-1).choose (h-1) : ℝ) = (q.choose h : ℝ) * (h : ℝ) := by exact_mod_cast hi have hnr : (n : ℝ) ≤ 5*(q : ℝ) := by exact_mod_cast (show n ≤ 5*q by omega) calc _ ≤ 5*(q : ℝ) * ((q-1).choose (h-1) : ℝ) * wsc_phi q h := by exact mul_le_mul_of_nonneg_right (mul_le_mul_of_nonneg_right hnr (by positivity)) (wsc_phi_nonneg _ _) _ = (5*h : ℝ)*(q.choose h : ℝ)*wsc_phi q h := by rw [mul_assoc 5, hir]; ring _ = _ := wsc_phi_cancel q h h1 (by omega)lemma wsc_geometric_bound (q : ℕ) : ∑ h ∈ Finset.range (q+1), (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h ≤ 1/50 := by have hi := wtc_geometric_square_sum (q+1) simp only [mul_assoc] rw [← Finset.mul_sum] nlinarithlemma wsc_shifted_geometric_bound (q : ℕ) : ∑ h ∈ Finset.range q, (1/20000 : ℝ)*((h+1 : ℕ) : ℝ)^2*(5/6 : ℝ)^(h+1) ≤ 1/50 := by have hi := wsc_geometric_bound q rw [Finset.sum_range_succ'] at hi norm_num at hi simpa only [Nat.cast_add, Nat.cast_one] using hiset_option maxHeartbeats 1000000set_option maxRecDepth 100000variable {n q : ℕ}lemma wsc_R_card (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (i : Fin n) : (w279_R c m i).card = n / 2 := by have := w279_card_R c m hm i omegatheorem wsc_fibre_card (b : Fin n → Fin q) (i : Fin n) (T : Finset (Fin q)) (P : Finset (Fin n) → Prop) [DecidablePred P] (Fsel : Finset (Fin n × Finset (Fin q) × (Fin n → Fin n))) (hF : ∀ t ∈ Fsel, t.1 = i → t.2.1 = T → (∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ P ((wsc_pos b t.2.1).image t.2.2)) : (Fsel.filter fun t => (t.1, t.2.1) = (i, T)).card ≤ (wsc_pos b T).card.factorial * (Finset.univ.filter fun U : Finset (Fin n) => U.card = (wsc_pos b T).card ∧ P U).card := by classical refine le_trans ?_ (w279_count_events (wsc_pos b T) P) refine Finset.card_le_card_of_injOn (fun t => t.2.2) ?_ ?_ · intro t ht simp only [Finset.coe_filter, Set.mem_setOf_eq, Prod.mk.injEq] at ht obtain ⟨ht, h1, h2⟩ := ht obtain ⟨g1, g2, g3⟩ := hF t ht h1 h2 rw [h2] at g1 g2 g3 simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_setOf_eq] exact ⟨g1, g2, g3⟩ · intro t ht t' ht' h simp only [Finset.coe_filter, Set.mem_setOf_eq, Prod.mk.injEq] at ht ht' obtain ⟨-, h1, h2⟩ := ht obtain ⟨-, h1', h2'⟩ := ht' exact Prod.ext (h1.trans h1'.symm) (Prod.ext (h2.trans h2'.symm) h)theorem wsc_pos_mass (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (p : Fin n) : ∑ t ∈ (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50 := by classical set Fsel := (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1) with hFdef have hFmem : ∀ t ∈ Fsel, (1 ≤ t.2.1.card ∧ t.2.1.card ≤ (q / 2) ∧ b p ∈ t.2.1) ∧ ((∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ w279_closed c t.1 ((wsc_pos b t.2.1).image t.2.2)) := by intro t ht rw [hFdef, Finset.mem_filter, wsc_mem_E ] at ht exact ⟨⟨ht.1.1, ht.1.2.1, wsc_mem_pos.1 ht.2⟩, ht.1.2.2⟩ let 𝒯 : Finset (Finset (Fin q)) := Finset.univ.filter fun T => 1 ≤ T.card ∧ T.card ≤ (q / 2) ∧ b p ∈ T let φ : ℕ → ℝ := wsc_phi q have step1 : ∑ t ∈ Fsel, wsc_wt n (wsc_pos b t.2.1).card ≤ ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, φ x.2.card := by rw [← Finset.sum_fiberwise_of_maps_to (g := fun t => (t.1, t.2.1)) (t := Finset.univ ×ˢ 𝒯)] · refine Finset.sum_le_sum fun x hx => ?_ have hw : ∀ t ∈ Fsel.filter (fun t => (t.1, t.2.1) = x), wsc_wt n (wsc_pos b t.2.1).card = wsc_wt n (wsc_pos b x.2).card := by intro t ht rw [Finset.mem_filter] at ht rw [← ht.2] rw [Finset.sum_congr rfl hw, Finset.sum_const, nsmul_eq_mul] have hc := wsc_fibre_card b x.1 x.2 (fun U => w279_closed c x.1 U) Fsel ?_ · have hc2 := w279_count_closed c m hm x.1 (wsc_pos b x.2).card rw [wsc_R_card c m hm] at hc2 have hc3 : (Fsel.filter fun t => (t.1, t.2.1) = x).card ≤ (wsc_pos b x.2).card.factorial * Nat.choose (n / 2) ((wsc_pos b x.2).card / 2) := by refine le_trans hc (Nat.mul_le_mul_left _ (le_trans (Finset.card_le_card ?_) hc2)) intro U hU simp only [Finset.mem_filter] at hU ⊢ exact hU have hT := (Finset.mem_filter.1 (Finset.mem_product.1 hx).2).2 have hb := hblock x.2 have hcR : ((Fsel.filter fun t => (t.1, t.2.1) = x).card : ℝ) ≤ (((wsc_pos b x.2).card.factorial * Nat.choose (n/2) ((wsc_pos b x.2).card/2) : ℕ) : ℝ) := by exact_mod_cast hc3 calc _ ≤ _ := mul_le_mul_of_nonneg_right hcR (wsc_wt_nonneg n _) _ = wsc_prob n (wsc_pos b x.2).card := by push_cast; exact wsc_prob_factorial n _ _ ≤ φ x.2.card := wsc_prob_le_phi n q x.2.card (wsc_pos b x.2).card hq hodd hn0 hn1 hT.1 (by omega) hb.1 (by have := hb.2; omega) · intro t ht hi _ obtain ⟨-, h1, h2, h3⟩ := hFmem t ht exact ⟨h1, h2, by rw [← hi]; exact h3⟩ · intro t ht obtain ⟨h0, -⟩ := hFmem t ht exact Finset.mem_product.2 ⟨Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _, h0⟩⟩ have step2 : ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, φ x.2.card = n * ∑ T ∈ 𝒯, φ T.card := by rw [Finset.sum_product] dsimp only rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul] have step3 : ∑ T ∈ 𝒯, φ T.card = ∑ m ∈ Finset.range q, ((Nat.choose (q - 1) m : ℕ) : ℝ) * (if m + 1 ≤ (q / 2) then φ (m + 1) else 0) := by set b := b p have hcard : (Finset.univ.erase b).card = (q - 1) := by rw [Finset.card_erase_of_mem (Finset.mem_univ _), Finset.card_univ, Fintype.card_fin] have e1 : ∑ T ∈ 𝒯, φ T.card = ∑ T' ∈ (Finset.univ.erase b).powerset.filter (fun T' => T'.card + 1 ≤ (q / 2)), φ (T'.card + 1) := by refine Finset.sum_nbij' (fun T => T.erase b) (fun T' => insert b T') ?_ ?_ ?_ ?_ ?_ · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT simp only [Finset.mem_filter, Finset.mem_powerset] refine ⟨Finset.erase_subset_erase _ (Finset.subset_univ _), ?_⟩ rw [Finset.card_erase_add_one hT.2.2]; exact hT.2.1 · intro T' hT' simp only [Finset.mem_filter, Finset.mem_powerset] at hT' have hb : b ∉ T' := fun h => by simpa using hT'.1 h simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] rw [Finset.card_insert_of_notMem hb] exact ⟨by omega, hT'.2, Finset.mem_insert_self _ _⟩ · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT exact Finset.insert_erase hT.2.2 · intro T' hT' simp only [Finset.mem_filter, Finset.mem_powerset] at hT' have hb : b ∉ T' := fun h => by simpa using hT'.1 h exact Finset.erase_insert hb · intro T hT simp only [𝒯, Finset.mem_filter, Finset.mem_univ, true_and] at hT rw [Finset.card_erase_add_one hT.2.2] rw [e1, Finset.sum_filter] have := Finset.sum_powerset_apply_card (fun m => if m + 1 ≤ (q / 2) then φ (m + 1) else 0) (x := Finset.univ.erase b) rw [hcard, Nat.sub_add_cancel (by omega : 1 ≤ q)] at this rw [this] refine Finset.sum_congr rfl fun m _ => ?_ rw [nsmul_eq_mul] calc _ ≤ _ := step1 _ = _ := by rw [step2, step3] _ ≤ ∑ h ∈ Finset.range q, (1/20000 : ℝ)*((h+1 : ℕ) : ℝ)^2*(5/6 : ℝ)^(h+1) := by rw [Finset.mul_sum] refine Finset.sum_le_sum fun h hh => ?_ by_cases hh' : h + 1 ≤ q / 2 · rw [if_pos hh'] simpa only [φ, Nat.add_sub_cancel, mul_assoc] using wsc_position_phi_bound n q (h+1) hq hn1 (by omega) (by omega) · rw [if_neg hh', mul_zero, mul_zero] positivity _ ≤ 1/50 := wsc_shifted_geometric_bound qtheorem wsc_vert_mass (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) (w : Fin n) : ∑ t ∈ (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50 := by classical set Fsel := (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2) with hFdef have hFmem : ∀ t ∈ Fsel, (1 ≤ t.2.1.card ∧ t.2.1.card ≤ (q / 2)) ∧ ((∀ v ∉ wsc_pos b t.2.1, t.2.2 v = v) ∧ Set.InjOn t.2.2 ↑(wsc_pos b t.2.1) ∧ (w279_closed c t.1 ((wsc_pos b t.2.1).image t.2.2) ∧ w ∈ (wsc_pos b t.2.1).image t.2.2)) := by intro t ht rw [hFdef, Finset.mem_filter, wsc_mem_E ] at ht exact ⟨⟨ht.1.1, ht.1.2.1⟩, ht.1.2.2.1, ht.1.2.2.2.1, ht.1.2.2.2.2, ht.2⟩ let 𝒯 : Finset (Finset (Fin q)) := Finset.univ.filter fun T => 1 ≤ T.card ∧ T.card ≤ (q / 2) let X : ℕ → ℕ := fun s => if s % 2 = 1 then Nat.choose (n / 2) (s / 2) else 0 let Y : ℕ → ℕ := fun s => Nat.choose (n / 2 - 1) (s / 2 - 1) let bnd : Fin n → ℕ → ℝ := fun i s => (s.factorial : ℝ) * (if m i = w then (X s : ℝ) else (Y s : ℝ)) have step1 : ∑ t ∈ Fsel, wsc_wt n (wsc_pos b t.2.1).card ≤ ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, bnd x.1 (wsc_pos b x.2).card * wsc_wt n (wsc_pos b x.2).card := by rw [← Finset.sum_fiberwise_of_maps_to (g := fun t => (t.1, t.2.1)) (t := Finset.univ ×ˢ 𝒯)] · refine Finset.sum_le_sum fun x hx => ?_ have hw : ∀ t ∈ Fsel.filter (fun t => (t.1, t.2.1) = x), wsc_wt n (wsc_pos b t.2.1).card = wsc_wt n (wsc_pos b x.2).card := by intro t ht rw [Finset.mem_filter] at ht rw [← ht.2] rw [Finset.sum_congr rfl hw, Finset.sum_const, nsmul_eq_mul] have hc := wsc_fibre_card b x.1 x.2 (fun U => w279_closed c x.1 U ∧ w ∈ U) Fsel ?_ · have hc2 : (Finset.univ.filter fun U : Finset (Fin n) => U.card = (wsc_pos b x.2).card ∧ (w279_closed c x.1 U ∧ w ∈ U)).card ≤ if m x.1 = w then X (wsc_pos b x.2).card else Y (wsc_pos b x.2).card := by split_ifs with hmw · have := w279_count_closed_mem_m c m hm x.1 (wsc_pos b x.2).card rw [wsc_R_card c m hm, hmw] at this exact this · have := w279_count_closed_mem c m hm x.1 (wsc_pos b x.2).card w (Ne.symm hmw) rw [wsc_R_card c m hm] at this exact this have hc3 : ((Fsel.filter fun t => (t.1, t.2.1) = x).card : ℝ) ≤ bnd x.1 (wsc_pos b x.2).card := by have h4 : (Fsel.filter fun t => (t.1, t.2.1) = x).card ≤ (wsc_pos b x.2).card.factorial * (if m x.1 = w then X (wsc_pos b x.2).card else Y (wsc_pos b x.2).card) := by refine le_trans hc (Nat.mul_le_mul_left _ (le_trans (Finset.card_le_card ?_) hc2)) intro U hU simp only [Finset.mem_filter] at hU ⊢ exact hU simp only [bnd] split_ifs at h4 ⊢ <;> exact_mod_cast h4 exact mul_le_mul_of_nonneg_right hc3 (wsc_wt_nonneg n _) · intro t ht hi _ obtain ⟨-, h1, h2, h3, h4⟩ := hFmem t ht exact ⟨h1, h2, by rw [← hi]; exact h3, h4⟩ · intro t ht obtain ⟨h0, -⟩ := hFmem t ht exact Finset.mem_product.2 ⟨Finset.mem_univ _, Finset.mem_filter.2 ⟨Finset.mem_univ _, h0⟩⟩ have hsumcol : ∀ s, ∑ i : Fin n, bnd i s = (((s.factorial * X s + (n - 1) * (s.factorial * Y s)) : ℕ) : ℝ) := by intro s have h1 : (Finset.univ.filter fun i : Fin n => m i = w) = {m.symm w} := by ext i; simp [Equiv.apply_eq_iff_eq_symm_apply] have h2 : (Finset.univ.filter fun i : Fin n => ¬ m i = w).card = (n - 1) := by have := Finset.card_filter_add_card_filter_not (s := (Finset.univ : Finset (Fin n))) (p := fun i => m i = w) rw [h1, Finset.card_singleton, Finset.card_univ, Fintype.card_fin] at this omega simp only [bnd, mul_ite] rw [Finset.sum_ite, Finset.sum_const, Finset.sum_const, h1, h2, Finset.card_singleton] push_cast ring have step2 : ∑ x ∈ (Finset.univ : Finset (Fin n)) ×ˢ 𝒯, bnd x.1 (wsc_pos b x.2).card * wsc_wt n (wsc_pos b x.2).card = ∑ T ∈ 𝒯, (((wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n - 1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card) : ℕ) : ℝ) * wsc_wt n (wsc_pos b T).card := by rw [Finset.sum_product, Finset.sum_comm] refine Finset.sum_congr rfl fun T _ => ?_ dsimp only rw [← Finset.sum_mul, hsumcol] have step3 : ∑ T ∈ 𝒯, ((((wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n-1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card)) : ℕ) : ℝ) * wsc_wt n (wsc_pos b T).card ≤ ∑ T ∈ 𝒯, (5*T.card : ℝ)*wsc_phi q T.card := by refine Finset.sum_le_sum fun T hT => ?_ have hT' := (Finset.mem_filter.1 hT).2 have hb := hblock T have hk3 : 3 ≤ (wsc_pos b T).card := by omega have hi := wtc_vertex_coefficient n (wsc_pos b T).card hodd (by omega) hk3 have hi' : (wsc_pos b T).card.factorial * X (wsc_pos b T).card + (n-1) * ((wsc_pos b T).card.factorial * Y (wsc_pos b T).card) = (wsc_pos b T).card.factorial * ((wsc_pos b T).card * (n/2).choose ((wsc_pos b T).card/2)) := by dsimp only [X, Y] nlinarith only [congrArg (fun z => (wsc_pos b T).card.factorial*z) hi] rw [hi'] push_cast have he : ((wsc_pos b T).card.factorial : ℝ) * ((wsc_pos b T).card : ℝ) * ((n/2).choose ((wsc_pos b T).card/2) : ℝ) * wsc_wt n (wsc_pos b T).card = ((wsc_pos b T).card : ℝ)*wsc_prob n (wsc_pos b T).card := by rw [← wsc_prob_factorial] ring rw [← mul_assoc, he] have hp := wsc_prob_le_phi n q T.card (wsc_pos b T).card hq hodd hn0 hn1 hT'.1 (by omega) hb.1 (by have := hb.2; omega) have hk : ((wsc_pos b T).card : ℝ) ≤ (5*T.card : ℝ) := by exact_mod_cast (show (wsc_pos b T).card ≤ 5*T.card by have := hb.2; omega) exact mul_le_mul hk hp (wsc_prob_nonneg _ _) (by positivity) have step4 : (∑ T ∈ 𝒯, (5*T.card : ℝ)*wsc_phi q T.card) = ∑ h ∈ Finset.range (q+1), (q.choose h : ℝ) * (if 1 ≤ h ∧ h ≤ q/2 then (5*h : ℝ)*wsc_phi q h else 0) := by rw [Finset.sum_filter, ← Finset.powerset_univ] have he := Finset.sum_powerset_apply_card (fun h => if 1 ≤ h ∧ h ≤ q/2 then (5*h : ℝ)*wsc_phi q h else 0) (x := (Finset.univ : Finset (Fin q))) rw [Finset.card_univ, Fintype.card_fin] at he rw [he] refine Finset.sum_congr rfl fun h hh => ?_ rw [nsmul_eq_mul] calc _ ≤ _ := step1 _ = _ := step2 _ ≤ _ := step3 _ = _ := step4 _ ≤ ∑ h ∈ Finset.range (q+1), (1/20000 : ℝ)*(h : ℝ)^2*(5/6 : ℝ)^h := by refine Finset.sum_le_sum fun h hh => ?_ by_cases hh' : 1 ≤ h ∧ h ≤ q/2 · rw [if_pos hh'] have hi := wsc_phi_cancel q h hh'.1 (by omega) nlinarith only [hi] · rw [if_neg hh', mul_zero] positivity _ ≤ 1/50 := wsc_geometric_bound qtheorem wild_partition_large_order_resource_bounds {n q : ℕ} (hq : 10000000 ≤ q) (hodd : n % 2 = 1) (hn0 : 3*q ≤ n) (hn1 : n ≤ 3*q+2) (b : Fin n → Fin q) (hblock : ∀ T : Finset (Fin q), 3*T.card ≤ (wsc_pos b T).card ∧ (wsc_pos b T).card ≤ 3*T.card+(n-3*q)) (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n)) (m : Fin n ≃ Fin n) (hm : ∀ (i v : Fin n), (∀ w (hvw : v ≠ w), c ⟨s(v, w), wild_kn_mem hvw⟩ ≠ i) ↔ v = m i) : (∀ p : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => p ∈ wsc_pos b t.2.1), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50) ∧ (∀ w : Fin n, ∑ t ∈ (wsc_E b c).filter (fun t => w ∈ (wsc_pos b t.2.1).image t.2.2), wsc_wt n (wsc_pos b t.2.1).card ≤ 1/50) := by exact ⟨wsc_pos_mass hq hodd hn0 hn1 b hblock c m hm, wsc_vert_mass hq hodd hn0 hn1 b hblock c m hm⟩