AFTD Auto-Formalizing Theoretical Domains

parallel_mw_ratio_three_two

theoremverified

For any profile q : Fin 3 → ℕ, parallel_mw_ratio 2 q equals 6 * (2^(q 0 + q 1 + q 2) - 2 * (2^(q 0) + 2^(q 1) + 2^(q 2)) + 6) / (q 0 * q 1 + q 0 * q 2 + q 1 * q 2)^2.

Statement

theorem parallel_mw_ratio_three_two (q : Fin 3 → ℕ) :
    parallel_mw_ratio 2 q =
      6 * ((2 : ℝ) ^ (q 0 + q 1 + q 2) - 2 * ((2 : ℝ) ^ q 0 + (2 : ℝ) ^ q 1 + (2 : ℝ) ^ q 2) + 6) /
      ((q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2) ^ 2
Source
step towards parallel_uniform_merino_welsh_strict_balancing_three_two
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • parallel_mw_ratioFor natural numbers n (implicit) and r, and q : Fin n → ℕ, parallel_mw_ratio r q is the real number defined by (parallel_mw_alpha n r *…
  • parallel_mw_starFor natural numbers n (implicit) and r, and q : Fin n → ℕ, parallel_mw_star r q is the real number defined by the sum for k from 0 to n of…
  • parallel_mw_tauFor natural numbers n (implicit) and r, and q : Fin n → ℕ, parallel_mw_tau r q is the real number defined by elem_symm r (fun i => (q i :…
  • parallel_mw_alphaFor natural numbers n and r, parallel_mw_alpha n r is the real number defined by 2 * ∑ j ∈ Finset.range r, ((n - 1).choose j : ℝ).
  • elem_symmThe k-th elementary symmetric polynomial evaluated on a vector v : Fin n → ℝ is the sum over all subsets of Fin n of size k of the product…
Used by 1

The proof, explained

The theorem establishes the closed-form coordinate representation of the Merino-Welsh ratio for the parallel network with n = 3 edges and rank r = 2. By definition, the ratio is (alpha * star) / tau^2. The proof computes each term explicitly: alpha(3, 2) evaluates to 6, tau(2, q) evaluates to the second elementary symmetric polynomial in q, and star(2, q) is expanded into elementary symmetric polynomials of 2^(q i) - 1 and simplified using ring arithmetic. Substituting these three closed forms into the definition immediately completes the proof.

  1. For any vector v in ℝ³, elem_symm 0 v = 1.

    Unfolding elem_symm, the 0-th elementary symmetric polynomial is the sum over all 0-element subsets of Fin 3 of the product of elements. The only subset of cardinality 0 is the empty set, and the empty product is 1.

    lines 2–4

    uses Finset.sum_singleton, Finset.prod_empty

      unfold elem_symm
      have : Finset.powersetCard 0 (Finset.univ : Finset (Fin 3)) = {∅} := by decide
      rw [this, Finset.sum_singleton, Finset.prod_empty]
  2. For any vector v in ℝ³, elem_symm 1 v = v 0 + v 1 + v 2.

    Unfolding elem_symm, the subsets of Fin 3 of cardinality 1 are {0}, {1}, and {2}. Expanding the sum over these three singletons and evaluating the singleton products produces v 0 + v 1 + v 2.

    lines 7–14

    uses Finset.sum_insert, Finset.sum_singleton, Finset.prod_singleton

      unfold elem_symm
      have : Finset.powersetCard 1 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3)}, {1}, {2}} := by decide
      rw [this]
      have h1 : ({(0 : Fin 3)} : Finset (Fin 3)) ∉ ({{(1 : Fin 3)}, {2}} : Finset (Finset (Fin 3))) := by decide
      have h2 : ({(1 : Fin 3)} : Finset (Fin 3)) ∉ ({{(2 : Fin 3)}} : Finset (Finset (Fin 3))) := by decide
      rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]
      simp [Finset.prod_singleton]
      ring
  3. For any vector v in ℝ³, elem_symm 2 v = v 0 * v 1 + v 0 * v 2 + v 1 * v 2.

    The subsets of Fin 3 of cardinality 2 are {0, 1}, {0, 2}, and {1, 2}. Expanding the sum and calculating the product of each 2-element set gives v 0 * v 1 + v 0 * v 2 + v 1 * v 2.

    lines 17–33

    uses Finset.sum_insert, Finset.sum_singleton, Finset.prod_insert, Finset.prod_singleton

      unfold elem_symm
      have : Finset.powersetCard 2 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3), 1}, {0, 2}, {1, 2}} := by decide
      rw [this]
      have h1 : ({(0 : Fin 3), 1} : Finset (Fin 3)) ∉ ({{(0 : Fin 3), 2}, {1, 2}} : Finset (Finset (Fin 3))) := by decide
      have h2 : ({(0 : Fin 3), 2} : Finset (Fin 3)) ∉ ({{(1 : Fin 3), 2}} : Finset (Finset (Fin 3))) := by decide
      rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]
      have p1 : ∏ i ∈ ({(0 : Fin 3), 1} : Finset (Fin 3)), v i = v 0 * v 1 := by
        have : (0 : Fin 3) ∉ ({(1 : Fin 3)} : Finset (Fin 3)) := by decide
        rw [Finset.prod_insert this, Finset.prod_singleton]
      have p2 : ∏ i ∈ ({(0 : Fin 3), 2} : Finset (Fin 3)), v i = v 0 * v 2 := by
        have : (0 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide
        rw [Finset.prod_insert this, Finset.prod_singleton]
      have p3 : ∏ i ∈ ({(1 : Fin 3), 2} : Finset (Fin 3)), v i = v 1 * v 2 := by
        have : (1 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide
        rw [Finset.prod_insert this, Finset.prod_singleton]
      rw [p1, p2, p3]
      ring
  4. For any vector v in ℝ³, elem_symm 3 v = v 0 * v 1 * v 2.

    The only subset of Fin 3 of cardinality 3 is the full set {0, 1, 2}. Evaluating the product of the three components yields v 0 * v 1 * v 2.

    lines 36–42

    uses Finset.sum_singleton, Finset.prod_insert, Finset.prod_singleton

      unfold elem_symm
      have : Finset.powersetCard 3 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3), 1, 2}} := by decide
      rw [this, Finset.sum_singleton]
      have h0 : (0 : Fin 3) ∉ ({(1 : Fin 3), 2} : Finset (Fin 3)) := by decide
      have h1 : (1 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide
      rw [Finset.prod_insert h0, Finset.prod_insert h1, Finset.prod_singleton]
      ring
  5. The constant parallel_mw_alpha 3 2 equals 6. automation

    By definition, parallel_mw_alpha 3 2 is 2 * ∑_{j=0}^1 ((3-1).choose j) = 2 * (choose 2 0 + choose 2 1) = 2 * (1 + 2) = 6. Unfolding the definition and expanding the sum gives 6 by direct arithmetic computation via norm_num.

    lines 45–47

    uses Finset.sum_range_succ, Finset.sum_range_zero

      unfold parallel_mw_alpha
      rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]
      norm_num
  6. The alternating sum parallel_mw_star 2 q equals 2^(q 0 + q 1 + q 2) - 2 * (2^(q 0) + 2^(q 1) + 2^(q 2)) + 6.

    Unfolding parallel_mw_star, the sum runs over k from 0 to 3. For k = 0, 1 (< 2), the sign (-1)^(2-k) produces coefficients +1 and -1; for k = 2, 3, the coefficient is +1. Substituting the explicit values of elem_symm k for k = 0, 1, 2, 3 applied to (2^(q i) - 1) and rewriting 2^(q 0 + q 1 + q 2) as 2^(q 0) * 2^(q 1) * 2^(q 2), the polynomial identity simplifies algebraically to the claimed formula via ring.

    lines 52–66

    uses Finset.sum_range_succ, Finset.sum_range_zero, zero_add, parallel_mw_ratio_three_two_elem_symm_zero, parallel_mw_ratio_three_two_elem_symm_one, parallel_mw_ratio_three_two_elem_symm_two, parallel_mw_ratio_three_two_elem_symm_three, pow_add

      unfold parallel_mw_star
      have h4 : 3 + 1 = 4 := rfl
      rw [h4]
      rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]
      simp only [zero_add]
      have e0 := parallel_mw_ratio_three_two_elem_symm_zero (fun i => (2 : ℝ) ^ q i - 1)
      have e1 := parallel_mw_ratio_three_two_elem_symm_one (fun i => (2 : ℝ) ^ q i - 1)
      have e2 := parallel_mw_ratio_three_two_elem_symm_two (fun i => (2 : ℝ) ^ q i - 1)
      have e3 := parallel_mw_ratio_three_two_elem_symm_three (fun i => (2 : ℝ) ^ q i - 1)
      rw [e0, e1, e2, e3]
      have hpow : (2 : ℝ) ^ (q 0 + q 1 + q 2) = (2 : ℝ) ^ q 0 * (2 : ℝ) ^ q 1 * (2 : ℝ) ^ q 2 := by
        rw [pow_add, pow_add]
      rw [hpow]
      norm_num
      ring
  7. The denominator parallel_mw_tau 2 q equals (q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2.

    By definition, parallel_mw_tau 2 q is elem_symm 2 applied to the real-cast multiplicities (q i : ℝ), which matches parallel_mw_ratio_three_two_elem_symm_two directly.

    lines 70–71

    uses parallel_mw_ratio_three_two_elem_symm_two

      unfold parallel_mw_tau
      exact parallel_mw_ratio_three_two_elem_symm_two (fun i => (q i : ℝ))
  8. The Merino-Welsh ratio parallel_mw_ratio 2 q equals 6 * (2^(q 0 + q 1 + q 2) - 2 * (2^(q 0) + 2^(q 1) + 2^(q 2)) + 6) / ((q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2)^2.

    Unfolding parallel_mw_ratio, the expression is (parallel_mw_alpha 3 2 * parallel_mw_star 2 q) / (parallel_mw_tau 2 q)^2. Rewriting each term using the previously proven lemmas for alpha, star, and tau immediately yields the closed-form formula.

    lines 78–79

    uses parallel_mw_ratio_three_two_alpha, parallel_mw_ratio_three_two_star, parallel_mw_ratio_three_two_tau

      unfold parallel_mw_ratio
      rw [parallel_mw_ratio_three_two_alpha, parallel_mw_ratio_three_two_star, parallel_mw_ratio_three_two_tau]
Finset.sum_singleton
The sum of a function over a singleton set {a} is the function value f(a).
Finset.prod_empty
The product of any function over the empty set is 1.
Finset.sum_insert
If an element a is not in a finite set s, the sum of f over insert a s is f(a) plus the sum over s.
Finset.prod_singleton
The product of a function over a singleton set {a} is the function value f(a).
Finset.prod_insert
If an element a is not in a finite set s, the product of f over insert a s is f(a) times the product over s.
Finset.sum_range_succ
The sum of a function over the range of n + 1 equals the sum over the range of n plus the term at n.
Finset.sum_range_zero
The sum of a function over the empty range of size 0 is 0.
zero_add
Adding zero on the left of any element returns that element: 0 + a = a.
pow_add
For powers in a monoid, a^(m + n) = a^m * a^n.
parallel_mw_ratio_three_two_elem_symm_zero
The 0-th elementary symmetric polynomial in three variables evaluated at v equals 1.
parallel_mw_ratio_three_two_elem_symm_one
The 1st elementary symmetric polynomial in three variables evaluated at v equals v 0 + v 1 + v 2.
parallel_mw_ratio_three_two_elem_symm_two
The 2nd elementary symmetric polynomial in three variables evaluated at v equals v 0 * v 1 + v 0 * v 2 + v 1 * v 2.
parallel_mw_ratio_three_two_elem_symm_three
The 3rd elementary symmetric polynomial in three variables evaluated at v equals v 0 * v 1 * v 2.
parallel_mw_ratio_three_two_alpha
The coefficient parallel_mw_alpha 3 2 equals 6.
parallel_mw_ratio_three_two_star
The alternating sum parallel_mw_star 2 q equals 2^(q 0 + q 1 + q 2) - 2 * (2^(q 0) + 2^(q 1) + 2^(q 2)) + 6.
parallel_mw_ratio_three_two_tau
The denominator quantity parallel_mw_tau 2 q equals (q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2.

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

lemma parallel_mw_ratio_three_two_elem_symm_zero (v : Fin 3 → ℝ) : elem_symm 0 v = 1 := by  unfold elem_symm  have : Finset.powersetCard 0 (Finset.univ : Finset (Fin 3)) = {∅} := by decide  rw [this, Finset.sum_singleton, Finset.prod_empty]lemma parallel_mw_ratio_three_two_elem_symm_one (v : Fin 3 → ℝ) : elem_symm 1 v = v 0 + v 1 + v 2 := by  unfold elem_symm  have : Finset.powersetCard 1 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3)}, {1}, {2}} := by decide  rw [this]  have h1 : ({(0 : Fin 3)} : Finset (Fin 3)) ∉ ({{(1 : Fin 3)}, {2}} : Finset (Finset (Fin 3))) := by decide  have h2 : ({(1 : Fin 3)} : Finset (Fin 3)) ∉ ({{(2 : Fin 3)}} : Finset (Finset (Fin 3))) := by decide  rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]  simp [Finset.prod_singleton]  ringlemma parallel_mw_ratio_three_two_elem_symm_two (v : Fin 3 → ℝ) : elem_symm 2 v = v 0 * v 1 + v 0 * v 2 + v 1 * v 2 := by  unfold elem_symm  have : Finset.powersetCard 2 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3), 1}, {0, 2}, {1, 2}} := by decide  rw [this]  have h1 : ({(0 : Fin 3), 1} : Finset (Fin 3)) ∉ ({{(0 : Fin 3), 2}, {1, 2}} : Finset (Finset (Fin 3))) := by decide  have h2 : ({(0 : Fin 3), 2} : Finset (Fin 3)) ∉ ({{(1 : Fin 3), 2}} : Finset (Finset (Fin 3))) := by decide  rw [Finset.sum_insert h1, Finset.sum_insert h2, Finset.sum_singleton]  have p1 : ∏ i ∈ ({(0 : Fin 3), 1} : Finset (Fin 3)), v i = v 0 * v 1 := by    have : (0 : Fin 3) ∉ ({(1 : Fin 3)} : Finset (Fin 3)) := by decide    rw [Finset.prod_insert this, Finset.prod_singleton]  have p2 : ∏ i ∈ ({(0 : Fin 3), 2} : Finset (Fin 3)), v i = v 0 * v 2 := by    have : (0 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide    rw [Finset.prod_insert this, Finset.prod_singleton]  have p3 : ∏ i ∈ ({(1 : Fin 3), 2} : Finset (Fin 3)), v i = v 1 * v 2 := by    have : (1 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide    rw [Finset.prod_insert this, Finset.prod_singleton]  rw [p1, p2, p3]  ringlemma parallel_mw_ratio_three_two_elem_symm_three (v : Fin 3 → ℝ) : elem_symm 3 v = v 0 * v 1 * v 2 := by  unfold elem_symm  have : Finset.powersetCard 3 (Finset.univ : Finset (Fin 3)) = {{(0 : Fin 3), 1, 2}} := by decide  rw [this, Finset.sum_singleton]  have h0 : (0 : Fin 3) ∉ ({(1 : Fin 3), 2} : Finset (Fin 3)) := by decide  have h1 : (1 : Fin 3) ∉ ({(2 : Fin 3)} : Finset (Fin 3)) := by decide  rw [Finset.prod_insert h0, Finset.prod_insert h1, Finset.prod_singleton]  ringlemma parallel_mw_ratio_three_two_alpha : parallel_mw_alpha 3 2 = 6 := by  unfold parallel_mw_alpha  rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]  norm_numlemma parallel_mw_ratio_three_two_star (q : Fin 3 → ℕ) :    parallel_mw_star 2 q =      (2 : ℝ) ^ (q 0 + q 1 + q 2) - 2 * ((2 : ℝ) ^ q 0 + (2 : ℝ) ^ q 1 + (2 : ℝ) ^ q 2) + 6 := by  unfold parallel_mw_star  have h4 : 3 + 1 = 4 := rfl  rw [h4]  rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero]  simp only [zero_add]  have e0 := parallel_mw_ratio_three_two_elem_symm_zero (fun i => (2 : ℝ) ^ q i - 1)  have e1 := parallel_mw_ratio_three_two_elem_symm_one (fun i => (2 : ℝ) ^ q i - 1)  have e2 := parallel_mw_ratio_three_two_elem_symm_two (fun i => (2 : ℝ) ^ q i - 1)  have e3 := parallel_mw_ratio_three_two_elem_symm_three (fun i => (2 : ℝ) ^ q i - 1)  rw [e0, e1, e2, e3]  have hpow : (2 : ℝ) ^ (q 0 + q 1 + q 2) = (2 : ℝ) ^ q 0 * (2 : ℝ) ^ q 1 * (2 : ℝ) ^ q 2 := by    rw [pow_add, pow_add]  rw [hpow]  norm_num  ringlemma parallel_mw_ratio_three_two_tau (q : Fin 3 → ℕ) :    parallel_mw_tau 2 q = (q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2 := by  unfold parallel_mw_tau  exact parallel_mw_ratio_three_two_elem_symm_two (fun i => (q i : ℝ))/-- Closed-form coordinate representation of the Merino-Welsh ratio for n = 3 and r = 2. -/theorem parallel_mw_ratio_three_two (q : Fin 3 → ℕ) :    parallel_mw_ratio 2 q =      6 * ((2 : ℝ) ^ (q 0 + q 1 + q 2) - 2 * ((2 : ℝ) ^ q 0 + (2 : ℝ) ^ q 1 + (2 : ℝ) ^ q 2) + 6) /      ((q 0 : ℝ) * q 1 + (q 0 : ℝ) * q 2 + (q 1 : ℝ) * q 2) ^ 2 := by  unfold parallel_mw_ratio  rw [parallel_mw_ratio_three_two_alpha, parallel_mw_ratio_three_two_star, parallel_mw_ratio_three_two_tau]
See it in the graphDiscuss this resultChallenge it