AFTD Auto-Formalizing Theoretical Domains

wild_triple_partition_term_geometric_tail

theoremverified

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
Used by 1

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.

  1. 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).

    lines 7–21

    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_right

      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]
  2. 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.

    lines 25–31

    uses Nat.le_induction, pow_succ, Nat.mul_le_mul_left, wild_central_binomial_step

      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)
  3. 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.

    lines 37–46

    uses Nat.choose_pos

      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
  4. 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.

    lines 47–53

    uses wtc_choose_cube, wtc_choose_square

      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))
  5. 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.

    lines 54–58

    uses wild_central_binomial_ge_three_pow, Nat.choose_le_choose

      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
  6. 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.

    lines 59–66

    uses pow_two, mul_le_mul, div_le_one, sq_pos_of_pos, mul_le_mul_of_nonneg_right, sq_nonneg

      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
  7. ((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.

    lines 67–73

    uses pow_le_pow_left₀, mul_pow, pow_mul

      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
  8. (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.

    lines 74–80

    uses mul_le_mul_iff_of_pos_left, mul_le_mul

      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
  9. (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.

    lines 81–91

    uses mul_le_mul_of_nonneg_left

      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
  10. 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.

    lines 92–94

    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.

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

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
See it in the graphDiscuss this resultChallenge it