parallel_mw_ratio_three_two
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
- parallel_uniform_merino_welsh_strict_balancing_three_twoFor any function q : Fin 3 → ℕ with 0 < q i for all i : Fin 3, and any indices i, j : Fin 3 with q i + 2 ≤ q j, parallel_mw_ratio 2…
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.
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.
uses
Finset.sum_singleton,Finset.prod_emptyunfold elem_symm have : Finset.powersetCard 0 (Finset.univ : Finset (Fin 3)) = {∅} := by decide rw [this, Finset.sum_singleton, Finset.prod_empty]
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.
uses
Finset.sum_insert,Finset.sum_singleton,Finset.prod_singletonunfold 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
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.
uses
Finset.sum_insert,Finset.sum_singleton,Finset.prod_insert,Finset.prod_singletonunfold 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
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.
uses
Finset.sum_singleton,Finset.prod_insert,Finset.prod_singletonunfold 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
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.
uses
Finset.sum_range_succ,Finset.sum_range_zerounfold parallel_mw_alpha rw [Finset.sum_range_succ, Finset.sum_range_succ, Finset.sum_range_zero] norm_num
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.
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_addunfold 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
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.
uses
parallel_mw_ratio_three_two_elem_symm_twounfold parallel_mw_tau exact parallel_mw_ratio_three_two_elem_symm_two (fun i => (q i : ℝ))
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.
uses
parallel_mw_ratio_three_two_alpha,parallel_mw_ratio_three_two_star,parallel_mw_ratio_three_two_tauunfold 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.
- The evaluations of elementary symmetric polynomials over Fin 3 rely on decidable finite set enumerations via the `decide` tactic to list all subsets of given cardinality.
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.
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]