AFTD Auto-Formalizing Theoretical Domains

parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant

theoremverifiedoriginal

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.

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

    lines 5–10

    uses prod_one_add, powerset_card_biUnion, card_fin

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

    lines 11–17

    uses Function.onFun, disjoint_iff_ne, mem_powersetCard

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

    line 18

    uses sum_biUnion

      rw [sum_biUnion h_disj]
  4. 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.

    lines 22–24

    uses powersetCard_zero, sum_singleton, prod_empty

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

    lines 25–33

    uses parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_sum_elem_symm, prod_pow_eq_pow_sum

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

    lines 34–44

    uses sum_range_succ', Nat.not_lt_of_ge, Nat.succ_le_succ, Nat.zero_le, sum_congr

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

    lines 45–49

    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
  8. 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 : ℝ).

    lines 53–56

    uses powersetCard_one, sum_map

      unfold parallel_mw_tau elem_symm
      rw [powersetCard_one]
      rw [sum_map]
      simp
  9. 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.

    lines 61–73

    uses mem_univ, mem_erase, insert_erase, sum_insert, notMem_erase, add_assoc

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

    lines 74–88

    uses sum_congr, mem_erase

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

    lines 95–103

    uses parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_transfer_sum

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

    lines 104–112

    uses parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_star_one, parallel_uniform_merino_welsh_strict_balancing_rank_one_invariant_tau_one

      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]
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 : ℝ).

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