parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant
For any natural number n ≥ 3, any function q : Fin n → ℕ with 0 < q k for all k : Fin n, and any indices i, j : Fin n with q i + 2 ≤ q j, parallel_mw_ratio 1 (parallel_mw_transfer q i j) = parallel_mw_ratio 1 q.
Statement
theorem parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant
(n : ℕ) (hn : 3 ≤ n) (q : Fin n → ℕ) (hq : ∀ k, 0 < q k)
(i j : Fin n) (hij : q i + 2 ≤ q j) :
parallel_mw_ratio 1 (parallel_mw_transfer q i j) = parallel_mw_ratio 1 q- Related work
- OP-670; Experiment 9588
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_transferFor a natural number n, a function q : Fin n → ℕ, and indices i, j : Fin n, parallel_mw_transfer q i j is the function Fin n → ℕ defined…
- 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…
- 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_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 : ℝ).
- 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 :…
Read back from the Lean
For every natural number $n$ with $n \ge 3$, every sequence $q : \text{Fin } n \to \mathbb{N}$ of strictly positive natural numbers (i.e., $q(k) > 0$ for all $k \in \text{Fin } n$), and every pair of indices $i, j \in \text{Fin } n$ satisfying $q(i) + 2 \le q(j)$, the rank-1 parallel Merino–Welsh ratio parallel_mw_ratio 1 evaluated at the transferred sequence parallel_mw_transfer q i j is equal to the rank-1 parallel Merino–Welsh ratio evaluated at $q$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
At rank r = 1, the Merino-Welsh ratio is defined in terms of two quantities, parallel_mw_star and parallel_mw_tau. Using the generating-function identity for elementary symmetric polynomials, parallel_mw_star 1 q simplifies to 2^(∑ q_i) - 2, while parallel_mw_tau 1 q simplifies to the sum ∑ q_i. A transfer between parallel classes decrements q_j and increments q_i, leaving the total sum ∑ q_i unchanged; consequently, both numerator and denominator remain invariant, proving that the ratio itself is invariant under the transfer.
The product ∏ i, (1 + v i) expands to the sum over all subsets, which partitions into subsets of fixed cardinality k ∈ {0, ..., n}.
By definition, the k-th elementary symmetric polynomial is the sum of products over subsets of size k. Expanding ∏ i, (1 + v i) over the universal set of indices gives the sum over its entire powerset, which is decomposed as the union over k ∈ {0, ..., n} of subsets of cardinality k.
uses
prod_one_add,powerset_card_biUnion,card_finunfold elem_symm rw [prod_one_add univ] have h_biUnion := powerset_card_biUnion (univ : Finset (Fin n)) have hc : (univ : Finset (Fin n)).card = n := card_fin n rw [hc] at h_biUnion rw [h_biUnion]
Subsets of distinct cardinalities are pairwise disjoint.
If two subsets x and y of the index set have cardinalities a and b respectively and x = y, then their cardinalities must coincide (a = b). Thus, families of subsets of different sizes share no elements.
uses
Function.onFun,disjoint_iff_ne,mem_powersetCardhave h_disj : (↑(range (n + 1)) : Set ℕ).PairwiseDisjoint (fun i => powersetCard i (univ : Finset (Fin n))) := by intro a _ b _ hab rw [Function.onFun, disjoint_iff_ne] intro x hx y hy hxy rw [mem_powersetCard] at hx hy apply hab rw [← hx.2, ← hy.2, hxy]
The sum of all elementary symmetric polynomials ∑ k ∈ range (n + 1), elem_symm k v equals ∏ i, (1 + v i).
Since the subsets of fixed cardinalities partition the powerset into pairwise disjoint collections, summing over the union is equivalent to summing over each size class k from 0 to n and then summing the products over each subset of size k.
uses
sum_biUnionrw [sum_biUnion h_disj]For v i = 2^(q i) - 1, the 0-th elementary symmetric polynomial elem_symm 0 v equals 1.
The only subset of size 0 is the empty set, and the product of any function over the empty set is 1 by definition.
uses
powersetCard_zero,sum_singleton,prod_emptyhave elem_symm_zero : elem_symm 0 (fun i => (2 : ℝ) ^ q i - 1) = 1 := by unfold elem_symm rw [powersetCard_zero, sum_singleton, prod_empty]
The total sum of elementary symmetric polynomials ∑ k ∈ range (n + 1), elem_symm k (2^(q i) - 1) equals 2^(∑ i, q i).
Applying the sum-product identity to v i = 2^(q i) - 1, the sum becomes ∏ i, (1 + (2^(q i) - 1)) = ∏ i, 2^(q i). Converting the product of powers with base 2 into a single power whose exponent is the sum ∑ i, q i gives 2^(∑ i, q i).
uses
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm,prod_pow_eq_pow_sumhave h_sum : (∑ k ∈ range (n + 1), elem_symm k (fun i => (2 : ℝ) ^ q i - 1)) = (2 : ℝ) ^ (∑ i : Fin n, q i) := by have h_prod := parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm (fun i => (2 : ℝ) ^ q i - 1) rw [h_prod] have h_simp : (fun i : Fin n => 1 + ((2 : ℝ) ^ q i - 1)) = fun i => (2 : ℝ) ^ q i := by ext i ring rw [h_simp] exact prod_pow_eq_pow_sum univ q 2
The sum defining parallel_mw_star 1 q unfolds to (∑ k ∈ range n, elem_symm (k + 1) v) - 1.
Unfolding parallel_mw_star for r = 1, the k = 0 term has coefficient (-1)^(1 - 0) = -1, while all terms with k ≥ 1 have coefficient 1 because k + 1 < 1 is false. Separating the k = 0 term gives -elem_symm 0 v = -1 plus the sum of elem_symm (k + 1) v over k ∈ range n.
uses
sum_range_succ',Nat.not_lt_of_ge,Nat.succ_le_succ,Nat.zero_le,sum_congrunfold parallel_mw_star rw [sum_range_succ'] have h_zero : (if 0 < 1 then (-1 : ℝ) ^ (1 - 0) else 1) * elem_symm 0 (fun i => (2 : ℝ) ^ q i - 1) = -1 := by simp [elem_symm_zero] have h_succ : ∀ k ∈ range n, (if k + 1 < 1 then (-1 : ℝ) ^ (1 - (k + 1)) else 1) * elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1) = elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1) := by intro k _ have : ¬ (k + 1 < 1) := Nat.not_lt_of_ge (Nat.succ_le_succ (Nat.zero_le k)) simp [this] rw [sum_congr rfl h_succ] rw [h_zero]
parallel_mw_star 1 q = 2^(∑ i, q i) - 2.
The total sum over all k from 0 to n splits into the sum over k ≥ 1 plus elem_symm 0 v = 1. Since the total sum is 2^(∑ i, q i), the sum over k ≥ 1 equals 2^(∑ i, q i) - 1, and subtracting 1 yields 2^(∑ i, q i) - 2.
uses
sum_range_succ'have h_split : (∑ k ∈ range (n + 1), elem_symm k (fun i => (2 : ℝ) ^ q i - 1)) = (∑ k ∈ range n, elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1)) + 1 := by rw [sum_range_succ'] simp [elem_symm_zero] linarith
parallel_mw_tau 1 q = ∑ i, (q i : ℝ).
By definition, parallel_mw_tau 1 q is the degree-1 elementary symmetric polynomial, which sums q i over all 1-element subsets. Mapping singletons over the universal set reduces this to the ordinary sum ∑ i, (q i : ℝ).
uses
powersetCard_one,sum_mapunfold parallel_mw_tau elem_symm rw [powersetCard_one] rw [sum_map] simp
For any function f on Fin n and indices i ≠ j, the total sum decomposes as f j + f i + ∑ k ∉ {i, j}, f k.
Isolating j from the universal set and then isolating i from the remaining indices decomposes the sum over all elements into the contribution at j, the contribution at i, and the sum over the remaining indices.
uses
mem_univ,mem_erase,insert_erase,sum_insert,notMem_erase,add_assochave hj_mem : j ∈ (univ : Finset (Fin n)) := mem_univ j have hi_mem : i ∈ (univ.erase j) := by rw [mem_erase] exact ⟨hij, mem_univ i⟩ have h_split (f : Fin n → ℕ) : (∑ k : Fin n, f k) = f j + f i + ∑ k ∈ (univ.erase j).erase i, f k := by have h1 : (∑ k : Fin n, f k) = f j + ∑ k ∈ univ.erase j, f k := by conv_lhs => rw [← insert_erase hj_mem] rw [sum_insert (notMem_erase j univ)] have h2 : (∑ k ∈ univ.erase j, f k) = f i + ∑ k ∈ (univ.erase j).erase i, f k := by conv_lhs => rw [← insert_erase hi_mem] rw [sum_insert (notMem_erase i (univ.erase j))] rw [h1, h2, add_assoc]
Transferring one unit from j to i preserves the total sum of q: ∑ k, parallel_mw_transfer q i j k = ∑ k, q k.
Decomposing both sums with the three-part splitting, the transfer modifies only the coordinates at j (to q j - 1) and at i (to q i + 1), while leaving all other coordinates unchanged. The net change is (q j - 1) + (q i + 1) - (q j + q i) = 0.
uses
sum_congr,mem_eraserw [h_split (parallel_mw_transfer q i j)] rw [h_split q] unfold parallel_mw_transfer have h_j : Function.update (Function.update q i (q i + 1)) j (q j - 1) j = q j - 1 := by simp have h_i : Function.update (Function.update q i (q i + 1)) j (q j - 1) i = q i + 1 := by simp [hij] have h_rest : (∑ k ∈ (univ.erase j).erase i, Function.update (Function.update q i (q i + 1)) j (q j - 1) k) = ∑ k ∈ (univ.erase j).erase i, q k := by refine sum_congr rfl (fun k hk => ?_) rw [mem_erase, mem_erase] at hk simp [hk.1, hk.2.1] rw [h_j, h_i, h_rest] omega
The transfer indices i and j are distinct, q j ≥ 1, and the transfer preserves the sum: ∑ k, parallel_mw_transfer q i j k = ∑ k, q k.
The hypothesis q i + 2 ≤ q j implies i ≠ j. Since q k > 0 for all k, we have q j ≥ 1. These conditions permit applying the transfer sum lemma, showing the total sum of components is preserved under the transfer.
uses
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sumhave _ := hn have hne : i ≠ j := by rintro rfl omega have hj : 1 ≤ q j := by have := hq j omega have hsum : ∑ k : Fin n, parallel_mw_transfer q i j k = ∑ k : Fin n, q k := parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sum q i j hne hj
parallel_mw_ratio 1 (parallel_mw_transfer q i j) = parallel_mw_ratio 1 q.
At rank 1, parallel_mw_star 1 depends only on the total sum ∑ k, q k, and parallel_mw_tau 1 equals this total sum. Because the transfer operation preserves the total sum, both terms evaluate to identical values before and after transfer, leaving the ratio invariant.
uses
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one,parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_oneunfold parallel_mw_ratio have hstar : parallel_mw_star 1 (parallel_mw_transfer q i j) = parallel_mw_star 1 q := by rw [parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one n (parallel_mw_transfer q i j), parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one n q, hsum] have htau : parallel_mw_tau 1 (parallel_mw_transfer q i j) = parallel_mw_tau 1 q := by rw [parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one n (parallel_mw_transfer q i j), parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one n q] exact_mod_cast hsum rw [hstar, htau]
prod_one_add- For a finite set s and function f, the product of 1 + f(i) over s equals the sum over all subsets t ⊆ s of the product of f(i) over t.
powerset_card_biUnion- The powerset of a finite set s decomposes as the disjoint union over k ∈ {0, ..., |s|} of the collections of subsets of s with cardinality k.
card_fin- The cardinality of Fin n (as the universal Finset) is n.
Function.onFun- Combines a binary relation with a function applied to both arguments: (x, y) ↦ R (f x) (f y).
disjoint_iff_ne- Two finsets are disjoint if and only if no element of the first equals an element of the second.
mem_powersetCard- A finset s belongs to powersetCard n t if and only if s ⊆ t and |s| = n.
sum_biUnion- The sum over a pairwise disjoint union of finite sets equals the iterated sum over the index set and each component set.
powersetCard_zero- The only subset of cardinality 0 of any finite set is the empty set.
sum_singleton- The sum of a function over a singleton set {a} equals f(a).
prod_empty- The product of a function over the empty set equals 1.
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm- For any vector v ∈ ℝⁿ, the sum of its elementary symmetric polynomials e_k(v) for k from 0 to n equals the product of 1 + v_i for all i.
prod_pow_eq_pow_sum- The product of a constant base raised to powers f(i) equals the base raised to the sum of the exponents f(i).
sum_range_succ'- Splits a sum over {0, ..., n} into the sum over {1, ..., n} shifted by 1, plus the k = 0 term.
Nat.not_lt_of_ge- For natural numbers, b ≥ a implies that b < a is false.
Nat.succ_le_succ- If n ≤ m for natural numbers, then n + 1 ≤ m + 1.
Nat.zero_le- For every natural number n, 0 ≤ n.
sum_congr- If two index sets are identical and the summands agree on every element, then their sums are equal.
powersetCard_one- The collection of 1-element subsets of a set s is the image of s under the singleton map.
sum_map- Summing a function over the image of an embedding Finset.map e s equals summing the composed function over s.
mem_univ- Every element of a finite type belongs to its universal Finset univ.
mem_erase- An element a belongs to s.erase b if and only if a ≠ b and a ∈ s.
insert_erase- For an element a ∈ s, inserting a into s.erase a reconstructs s.
sum_insert- If a ∉ s, the sum over insert a s equals f(a) plus the sum over s.
notMem_erase- An element a is not an element of s.erase a.
add_assoc- Addition in an additive semigroup is associative: (a + b) + c = a + (b + c).
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sum- If i ≠ j and q j ≥ 1, transferring one unit from j to i preserves the sum of all components: ∑ k, parallel_mw_transfer q i j k = ∑ k, q k.
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one- At rank r = 1, parallel_mw_star 1 q simplifies to 2^(∑ i, q i) - 2.
parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one- At rank r = 1, parallel_mw_tau 1 q simplifies to ∑ i, (q i : ℝ).
- The overall proof relies on four auxiliary lemmas proved earlier in the file: the generating-function identity for elementary symmetric polynomials, the evaluations of parallel_mw_star and parallel_mw_tau at rank 1, and the conservation of the sum of components under transfers.
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 Finsetlemma parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm {n : ℕ} (v : Fin n → ℝ) : (∑ k ∈ range (n + 1), elem_symm k v) = ∏ i : Fin n, (1 + v i) := by unfold elem_symm rw [prod_one_add univ] have h_biUnion := powerset_card_biUnion (univ : Finset (Fin n)) have hc : (univ : Finset (Fin n)).card = n := card_fin n rw [hc] at h_biUnion rw [h_biUnion] have h_disj : (↑(range (n + 1)) : Set ℕ).PairwiseDisjoint (fun i => powersetCard i (univ : Finset (Fin n))) := by intro a _ b _ hab rw [Function.onFun, disjoint_iff_ne] intro x hx y hy hxy rw [mem_powersetCard] at hx hy apply hab rw [← hx.2, ← hy.2, hxy] rw [sum_biUnion h_disj]lemma parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one (n : ℕ) (q : Fin n → ℕ) : parallel_mw_star 1 q = (2 : ℝ) ^ (∑ i : Fin n, q i) - 2 := by have elem_symm_zero : elem_symm 0 (fun i => (2 : ℝ) ^ q i - 1) = 1 := by unfold elem_symm rw [powersetCard_zero, sum_singleton, prod_empty] have h_sum : (∑ k ∈ range (n + 1), elem_symm k (fun i => (2 : ℝ) ^ q i - 1)) = (2 : ℝ) ^ (∑ i : Fin n, q i) := by have h_prod := parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm (fun i => (2 : ℝ) ^ q i - 1) rw [h_prod] have h_simp : (fun i : Fin n => 1 + ((2 : ℝ) ^ q i - 1)) = fun i => (2 : ℝ) ^ q i := by ext i ring rw [h_simp] exact prod_pow_eq_pow_sum univ q 2 unfold parallel_mw_star rw [sum_range_succ'] have h_zero : (if 0 < 1 then (-1 : ℝ) ^ (1 - 0) else 1) * elem_symm 0 (fun i => (2 : ℝ) ^ q i - 1) = -1 := by simp [elem_symm_zero] have h_succ : ∀ k ∈ range n, (if k + 1 < 1 then (-1 : ℝ) ^ (1 - (k + 1)) else 1) * elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1) = elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1) := by intro k _ have : ¬ (k + 1 < 1) := Nat.not_lt_of_ge (Nat.succ_le_succ (Nat.zero_le k)) simp [this] rw [sum_congr rfl h_succ] rw [h_zero] have h_split : (∑ k ∈ range (n + 1), elem_symm k (fun i => (2 : ℝ) ^ q i - 1)) = (∑ k ∈ range n, elem_symm (k + 1) (fun i => (2 : ℝ) ^ q i - 1)) + 1 := by rw [sum_range_succ'] simp [elem_symm_zero] linarithlemma parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one (n : ℕ) (q : Fin n → ℕ) : parallel_mw_tau 1 q = ∑ i : Fin n, (q i : ℝ) := by unfold parallel_mw_tau elem_symm rw [powersetCard_one] rw [sum_map] simplemma parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sum {n : ℕ} (q : Fin n → ℕ) (i j : Fin n) (hij : i ≠ j) (hj : 1 ≤ q j) : ∑ k : Fin n, parallel_mw_transfer q i j k = ∑ k : Fin n, q k := by have hj_mem : j ∈ (univ : Finset (Fin n)) := mem_univ j have hi_mem : i ∈ (univ.erase j) := by rw [mem_erase] exact ⟨hij, mem_univ i⟩ have h_split (f : Fin n → ℕ) : (∑ k : Fin n, f k) = f j + f i + ∑ k ∈ (univ.erase j).erase i, f k := by have h1 : (∑ k : Fin n, f k) = f j + ∑ k ∈ univ.erase j, f k := by conv_lhs => rw [← insert_erase hj_mem] rw [sum_insert (notMem_erase j univ)] have h2 : (∑ k ∈ univ.erase j, f k) = f i + ∑ k ∈ (univ.erase j).erase i, f k := by conv_lhs => rw [← insert_erase hi_mem] rw [sum_insert (notMem_erase i (univ.erase j))] rw [h1, h2, add_assoc] rw [h_split (parallel_mw_transfer q i j)] rw [h_split q] unfold parallel_mw_transfer have h_j : Function.update (Function.update q i (q i + 1)) j (q j - 1) j = q j - 1 := by simp have h_i : Function.update (Function.update q i (q i + 1)) j (q j - 1) i = q i + 1 := by simp [hij] have h_rest : (∑ k ∈ (univ.erase j).erase i, Function.update (Function.update q i (q i + 1)) j (q j - 1) k) = ∑ k ∈ (univ.erase j).erase i, q k := by refine sum_congr rfl (fun k hk => ?_) rw [mem_erase, mem_erase] at hk simp [hk.1, hk.2.1] rw [h_j, h_i, h_rest] omega/-- At rank r = 1, the Merino-Welsh ratio is invariant under parallel-class transfers. -/theorem parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant (n : ℕ) (hn : 3 ≤ n) (q : Fin n → ℕ) (hq : ∀ k, 0 < q k) (i j : Fin n) (hij : q i + 2 ≤ q j) : parallel_mw_ratio 1 (parallel_mw_transfer q i j) = parallel_mw_ratio 1 q := by have _ := hn have hne : i ≠ j := by rintro rfl omega have hj : 1 ≤ q j := by have := hq j omega have hsum : ∑ k : Fin n, parallel_mw_transfer q i j k = ∑ k : Fin n, q k := parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sum q i j hne hj unfold parallel_mw_ratio have hstar : parallel_mw_star 1 (parallel_mw_transfer q i j) = parallel_mw_star 1 q := by rw [parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one n (parallel_mw_transfer q i j), parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one n q, hsum] have htau : parallel_mw_tau 1 (parallel_mw_transfer q i j) = parallel_mw_tau 1 q := by rw [parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one n (parallel_mw_transfer q i j), parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one n q] exact_mod_cast hsum rw [hstar, htau]