wild_triple_partition_term_geometric_tail
For q>=3 odd and any h>=5 with2*h<=q, the existing canonical triple-partition resource term wtc_term(q,h) is at most 3*h*(27/40)^h. The term is3*h*choose(q,h)*choose(floor(3*q/2), floor(3*h/2))/choose(3*q,3*h)*(21/20)^(3*h). This is a uniform tail estimate for the sufficient resource criterion, not a statement that the full resource sum satisfies its threshold.
Statement
theorem wild_triple_partition_term_geometric_tail
(q h : ℕ) (hq : 3 ≤ q) (hodd : q%2 = 1)
(hh : 5 ≤ h) (hhq : 2*h ≤ q) :
wtc_term q h ≤ 3*(h : ℝ)*(27/40 : ℝ)^h- Source
- IN-359 technical helper for the existing permutation resource criterion for OP-306, https://arxiv.org/html/2610.22142v1 Section6. Elementary central-binomial induction and the already proved Vandermonde estimates wtc_choose_cube and wtc_choose_square. No improved wild-number bound or research advance is asserted.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- wild_triple_partition_mass_le_of_odd_ge_179For every odd number q of triple blocks with q>=179, the existing sufficient canonical seal-event resource sum wtc_mass(q) is at most1/50.…
The proof, explained
The tail estimate for the triple-partition resource term wtc_term(q,h) is established by bounding its square, which factors as 9*h^2 * (B*D/C)^2 * (21/20)^(6*h) where B = choose(q,h), C = choose(3*q,3*h), and D = choose(floor(3*q/2), floor(3*h/2)). Binomial inequalities B^3 ≤ C and D^2 ≤ C imply B*(B*D/C)^2 ≤ 1, and since B ≥ choose(2*h,h) ≥ 3^h for h ≥ 5 (proved by induction), we obtain 3^h * (B*D/C)^2 ≤ 1. Combining this with the numerical exponential bound (21/20)^(6*h) ≤ 3^h * (27/40)^(2*h) bounds the squared term by (3*h*(27/40)^h)^2, and taking square roots yields the result.
For any h ≥ 1, 3 * (2*h).choose h ≤ (2*(h+1)).choose (h+1) (wild_central_binomial_step).
By symmetry of binomial coefficients (Nat.choose_symm_half), (2*h+1).choose h = (2*h+1).choose (h+1), so Pascal's recurrence (Nat.choose_succ_succ) gives (2*(h+1)).choose (h+1) = 2 * (2*h+1).choose (h+1). By Nat.le_of_mul_le_mul_right, it suffices to multiply both sides by h + 1 > 0. Using the identity (2*h+1) * (2*h).choose h = (2*h+1).choose (h+1) * (h+1) from Nat.add_one_mul_choose_eq together with 3*(h+1) ≤ 2*(2*h+1), we deduce 3 * (2*h).choose h * (h+1) ≤ 2 * (2*h+1) * (2*h).choose h = 2 * (2*h+1).choose (h+1) * (h+1) = (2*(h+1)).choose (h+1) * (h+1).
uses
Nat.choose_symm_half,Nat.add_one_mul_choose_eq,Nat.choose_succ_succ,Nat.le_of_mul_le_mul_right,Nat.mul_le_mul_righthave hs : (2*h+1).choose h = (2*h+1).choose (h+1) := (Nat.choose_symm_half h).symm have he := Nat.add_one_mul_choose_eq (2*h) h have hn : (2*(h+1)).choose (h+1) = 2 * (2*h+1).choose (h+1) := by rw [show 2*(h+1) = (2*h+1)+1 by omega, Nat.choose_succ_succ, hs] change (2*h+1).choose (h+1) + (2*h+1).choose (h+1) = 2 * (2*h+1).choose (h+1) ring apply Nat.le_of_mul_le_mul_right (c := h+1) (hc := by omega) calc 3 * (2*h).choose h * (h+1) = 3*(h+1)*(2*h).choose h := by ring _ ≤ (2*(2*h+1))*(2*h).choose h := Nat.mul_le_mul_right _ (by omega) _ = (2 * (2*h+1).choose (h+1))*(h+1) := by nlinarith [he] _ = _ := by rw [hn]
For any h ≥ 5, 3^h ≤ (2*h).choose h (wild_central_binomial_ge_three_pow).
We proceed by induction on h ≥ 5 using Nat.le_induction. The base case h = 5 holds by direct evaluation (decide), since 3^5 = 243 ≤ 252 = (10).choose 5. For the inductive step, 3^(h+1) = 3 * 3^h ≤ 3 * (2*h).choose h by the inductive hypothesis (Nat.mul_le_mul_left), which is at most (2*(h+1)).choose (h+1) by wild_central_binomial_step.
uses
Nat.le_induction,pow_succ,Nat.mul_le_mul_left,wild_central_binomial_stepinduction h, hh using Nat.le_induction with | base => decide | succ h hh ih => calc 3^(h+1) = 3*3^h := by rw [pow_succ]; ring _ ≤ 3*(2*h).choose h := Nat.mul_le_mul_left _ ih _ ≤ _ := wild_central_binomial_step h (by omega)
The abbreviations B = q.choose h, C = (3*q).choose (3*h), and D = (3*q/2).choose (3*h/2) satisfy B > 0, C > 0, and D ≥ 0.
Since 2*h ≤ q and h ≥ 5, we have h ≤ q and 3*h ≤ 3*q, so B and C are strictly positive by Nat.choose_pos, and D ≥ 0 holds by positivity.
uses
Nat.choose_poslet B : ℝ := q.choose h let C : ℝ := (3*q).choose (3*h) let D : ℝ := (3*q/2).choose (3*h/2) have hb : 0 < B := by dsimp [B] exact_mod_cast Nat.choose_pos (by omega : h ≤ q) have hc : 0 < C := by dsimp [C] exact_mod_cast Nat.choose_pos (by omega : 3*h ≤ 3*q) have hd : 0 ≤ D := by positivity
The binomial quantities satisfy B^3 ≤ C and D^2 ≤ C.
The bound B^3 ≤ C is an immediate cast of wtc_choose_cube q h. Since q is odd, integer division satisfies 2*(3*q/2) + 1 = 3*q (by omega), so applying wtc_choose_square (3*q/2) (3*h) gives D^2 ≤ C.
uses
wtc_choose_cube,wtc_choose_squarehave hb3 : B^3 ≤ C := by dsimp [B,C] exact_mod_cast wtc_choose_cube q h have hn : 2*(3*q/2)+1 = 3*q := by omega have hd2 : D^2 ≤ C := by dsimp [D,C] exact_mod_cast (hn ▸ wtc_choose_square (3*q/2) (3*h))
3^h ≤ B.
Since 2*h ≤ q, binomial monotonicity (Nat.choose_le_choose) gives (2*h).choose h ≤ q.choose h = B. Combining this with 3^h ≤ (2*h).choose h from wild_central_binomial_ge_three_pow yields 3^h ≤ B.
uses
wild_central_binomial_ge_three_pow,Nat.choose_le_choosehave hlow : (3 : ℝ)^h ≤ B := by have hnlow := (wild_central_binomial_ge_three_pow h hh).trans (Nat.choose_le_choose h hhq) dsimp [B] exact_mod_cast hnlow
B * (B*D/C)^2 ≤ 1 and hence 3^h * (B*D/C)^2 ≤ 1.
Multiplying B^3 ≤ C and D^2 ≤ C gives B^3 * D^2 ≤ C^2 by mul_le_mul. Rewriting the left-hand side as B * (B*D/C)^2 = (B^3 * D^2) / C^2, div_le_one implies B * (B*D/C)^2 ≤ 1. Since 3^h ≤ B and (B*D/C)^2 ≥ 0, multiplying by (B*D/C)^2 yields 3^h * (B*D/C)^2 ≤ 1.
uses
pow_two,mul_le_mul,div_le_one,sq_pos_of_pos,mul_le_mul_of_nonneg_right,sq_nonneghave 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) hc.le 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' : (3 : ℝ)^h*(B*D/C)^2 ≤ 1 := (mul_le_mul_of_nonneg_right hlow (sq_nonneg _)).trans hratio
((21/20)^(3*h))^2 ≤ 3^h * ((27/40)^h)^2.
Direct evaluation by norm_num establishes the base inequality (21/20)^6 ≤ 3 * (27/40)^2. Raising both sides to the power h via pow_le_pow_left₀ and applying monoid power laws ((a^b)^c = a^(b*c) and (a*b)^h = a^h * b^h) rewrites ((21/20)^6)^h to ((21/20)^(3*h))^2 and (3 * (27/40)^2)^h to 3^h * ((27/40)^h)^2.
uses
pow_le_pow_left₀,mul_pow,pow_mulhave hpower : ((21/20 : ℝ)^(3*h))^2 ≤ (3 : ℝ)^h*((27/40 : ℝ)^h)^2 := by have hp := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21/20)^6) (by norm_num : (21/20 : ℝ)^6 ≤ 3*(27/40 : ℝ)^2) h 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 hp
(B*D/C)^2 * ((21/20)^(3*h))^2 ≤ ((27/40)^h)^2.
Multiplying 3^h * (B*D/C)^2 ≤ 1 by ((21/20)^(3*h))^2 ≤ 3^h * ((27/40)^h)^2 gives 3^h * ((B*D/C)^2 * ((21/20)^(3*h))^2) ≤ 3^h * ((27/40)^h)^2. Since 3^h > 0, cancelling 3^h from both sides using mul_le_mul_iff_of_pos_left yields the claim.
uses
mul_le_mul_iff_of_pos_left,mul_le_mulhave hproduct : (B*D/C)^2*((21/20 : ℝ)^(3*h))^2 ≤ ((27/40 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < (3 : ℝ)^h)).mp calc _ = ((3 : ℝ)^h*(B*D/C)^2)*((21/20 : ℝ)^(3*h))^2 := by ring _ ≤ 1*((3 : ℝ)^h*((27/40 : ℝ)^h)^2) := mul_le_mul hratio' hpower (by positivity) (by positivity) _ = _ := by ring
(wtc_term q h)^2 ≤ (3 * h * (27/40)^h)^2.
Unfolding wtc_term shows that (wtc_term q h)^2 = 9 * h^2 * ((B*D/C)^2 * ((21/20)^(3*h))^2). Multiplying the product bound of the previous step by the nonnegative scalar 9 * h^2 via mul_le_mul_of_nonneg_left gives 9 * h^2 * ((27/40)^h)^2 = (3 * h * (27/40)^h)^2.
uses
mul_le_mul_of_nonneg_lefthave heq : (wtc_term q h)^2 = 9*(h : ℝ)^2*((B*D/C)^2*((21/20 : ℝ)^(3*h))^2) := by dsimp [wtc_term,B,C,D] push_cast ring have hsquare : (wtc_term q h)^2 ≤ (3*(h : ℝ)*(27/40 : ℝ)^h)^2 := by rw [heq] calc _ ≤ 9*(h : ℝ)^2*((27/40 : ℝ)^h)^2 := mul_le_mul_of_nonneg_left hproduct (by positivity) _ = _ := by ring
wtc_term q h ≤ 3 * h * (27/40)^h.
Both wtc_term q h and 3 * h * (27/40)^h are nonnegative (checked by positivity). By sq_le_sq₀, the inequality between their squares implies the inequality between the terms themselves.
uses
sq_le_sq₀have hnonneg : 0 ≤ 3*(h : ℝ)*(27/40 : ℝ)^h := by positivity have ht : 0 ≤ wtc_term q h := by unfold wtc_term; positivity exact (sq_le_sq₀ ht hnonneg).mp hsquare
Nat.choose_symm_half- For any m, the binomial coefficient (2*m+1).choose (m+1) equals (2*m+1).choose m by symmetry.
Nat.add_one_mul_choose_eq- For natural numbers n and k, (n + 1) * n.choose k = (n + 1).choose (k + 1) * (k + 1).
Nat.choose_succ_succ- Pascal's recurrence identity: (n + 1).choose (k + 1) = n.choose k + n.choose (k + 1).
Nat.le_of_mul_le_mul_right- If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
Nat.mul_le_mul_right- If n ≤ m, then n * k ≤ m * k for any natural number k.
Nat.le_induction- Mathematical induction on natural numbers starting from a base index m: to prove P(n) for all n ≥ m, it suffices to prove P(m) and P(n) → P(n+1).
pow_succ- In a monoid, a^(n+1) = a^n * a.
Nat.mul_le_mul_left- If n ≤ m, then k * n ≤ k * m for any natural number k.
wild_central_binomial_step- For any h ≥ 1, 3 * (2*h).choose h ≤ (2*(h+1)).choose (h+1).
Nat.choose_pos- If k ≤ n, the binomial coefficient n.choose k is strictly positive.
wtc_choose_cube- For natural numbers q and h, (q.choose h)^3 ≤ (3*q).choose (3*h).
wtc_choose_square- For natural numbers m and s, (m.choose (s / 2))^2 ≤ (2*m + 1).choose s.
wild_central_binomial_ge_three_pow- For h ≥ 5, 3^h ≤ (2*h).choose h.
Nat.choose_le_choose- If a ≤ b, then a.choose c ≤ b.choose c.
pow_two- In a monoid, a^2 = a * a.
mul_le_mul- If a ≤ b and c ≤ d with c ≥ 0 and b ≥ 0, then a * c ≤ b * d.
div_le_one- For b > 0, a / b ≤ 1 if and only if a ≤ b.
sq_pos_of_pos- If a > 0, then a^2 > 0.
mul_le_mul_of_nonneg_right- If b ≤ c and a ≥ 0, then b * a ≤ c * a.
sq_nonneg- In a linearly ordered semiring, the square of any element is nonnegative.
pow_le_pow_left₀- If 0 ≤ a ≤ b, then a^n ≤ b^n for all natural numbers n.
mul_pow- In a commutative monoid, (a * b)^n = a^n * b^n.
pow_mul- In a monoid, a^(m * n) = (a^m)^n.
mul_le_mul_iff_of_pos_left- For a strictly positive element a, a * b ≤ a * c if and only if b ≤ c.
mul_le_mul_of_nonneg_left- If b ≤ c and a ≥ 0, then a * b ≤ a * c.
sq_le_sq₀- For nonnegative a and b, a^2 ≤ b^2 if and only if a ≤ b.
- The base numerical inequality (21/20)^6 ≤ 3 * (27/40)^2 on line 70 is verified by Lean's arithmetic evaluator norm_num without producing an explicit paper-style calculation.
- The main inequality wtc_term(q,h) ≤ 3*h*(27/40)^h is established by first proving the bound on their squares and then deducing the original inequality via sq_le_sq₀ after establishing nonnegativity of both sides.
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.
open Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000theorem wild_central_binomial_step (h : ℕ) (hh : 1 ≤ h) : 3 * (2*h).choose h ≤ (2*(h+1)).choose (h+1) := by have hs : (2*h+1).choose h = (2*h+1).choose (h+1) := (Nat.choose_symm_half h).symm have he := Nat.add_one_mul_choose_eq (2*h) h have hn : (2*(h+1)).choose (h+1) = 2 * (2*h+1).choose (h+1) := by rw [show 2*(h+1) = (2*h+1)+1 by omega, Nat.choose_succ_succ, hs] change (2*h+1).choose (h+1) + (2*h+1).choose (h+1) = 2 * (2*h+1).choose (h+1) ring apply Nat.le_of_mul_le_mul_right (c := h+1) (hc := by omega) calc 3 * (2*h).choose h * (h+1) = 3*(h+1)*(2*h).choose h := by ring _ ≤ (2*(2*h+1))*(2*h).choose h := Nat.mul_le_mul_right _ (by omega) _ = (2 * (2*h+1).choose (h+1))*(h+1) := by nlinarith [he] _ = _ := by rw [hn]theorem wild_central_binomial_ge_three_pow (h : ℕ) (hh : 5 ≤ h) : 3^h ≤ (2*h).choose h := by induction h, hh using Nat.le_induction with | base => decide | succ h hh ih => calc 3^(h+1) = 3*3^h := by rw [pow_succ]; ring _ ≤ 3*(2*h).choose h := Nat.mul_le_mul_left _ ih _ ≤ _ := wild_central_binomial_step h (by omega)theorem wild_triple_partition_term_geometric_tail (q h : ℕ) (hq : 3 ≤ q) (hodd : q%2 = 1) (hh : 5 ≤ h) (hhq : 2*h ≤ q) : wtc_term q h ≤ 3*(h : ℝ)*(27/40 : ℝ)^h := by let B : ℝ := q.choose h let C : ℝ := (3*q).choose (3*h) let D : ℝ := (3*q/2).choose (3*h/2) have hb : 0 < B := by dsimp [B] exact_mod_cast Nat.choose_pos (by omega : h ≤ q) have hc : 0 < C := by dsimp [C] exact_mod_cast Nat.choose_pos (by omega : 3*h ≤ 3*q) have hd : 0 ≤ D := by positivity have hb3 : B^3 ≤ C := by dsimp [B,C] exact_mod_cast wtc_choose_cube q h have hn : 2*(3*q/2)+1 = 3*q := by omega have hd2 : D^2 ≤ C := by dsimp [D,C] exact_mod_cast (hn ▸ wtc_choose_square (3*q/2) (3*h)) have hlow : (3 : ℝ)^h ≤ B := by have hnlow := (wild_central_binomial_ge_three_pow h hh).trans (Nat.choose_le_choose h hhq) dsimp [B] exact_mod_cast hnlow 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) hc.le 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' : (3 : ℝ)^h*(B*D/C)^2 ≤ 1 := (mul_le_mul_of_nonneg_right hlow (sq_nonneg _)).trans hratio have hpower : ((21/20 : ℝ)^(3*h))^2 ≤ (3 : ℝ)^h*((27/40 : ℝ)^h)^2 := by have hp := pow_le_pow_left₀ (by positivity : (0 : ℝ) ≤ (21/20)^6) (by norm_num : (21/20 : ℝ)^6 ≤ 3*(27/40 : ℝ)^2) h 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 hp have hproduct : (B*D/C)^2*((21/20 : ℝ)^(3*h))^2 ≤ ((27/40 : ℝ)^h)^2 := by apply (mul_le_mul_iff_of_pos_left (by positivity : (0 : ℝ) < (3 : ℝ)^h)).mp calc _ = ((3 : ℝ)^h*(B*D/C)^2)*((21/20 : ℝ)^(3*h))^2 := by ring _ ≤ 1*((3 : ℝ)^h*((27/40 : ℝ)^h)^2) := mul_le_mul hratio' hpower (by positivity) (by positivity) _ = _ := by ring have heq : (wtc_term q h)^2 = 9*(h : ℝ)^2*((B*D/C)^2*((21/20 : ℝ)^(3*h))^2) := by dsimp [wtc_term,B,C,D] push_cast ring have hsquare : (wtc_term q h)^2 ≤ (3*(h : ℝ)*(27/40 : ℝ)^h)^2 := by rw [heq] calc _ ≤ 9*(h : ℝ)^2*((27/40 : ℝ)^h)^2 := mul_le_mul_of_nonneg_left hproduct (by positivity) _ = _ := by ring have hnonneg : 0 ≤ 3*(h : ℝ)*(27/40 : ℝ)^h := by positivity have ht : 0 ≤ wtc_term q h := by unfold wtc_term; positivity exact (sq_le_sq₀ ht hnonneg).mp hsquare