multilinear_extension_perm_invariant
If a set function f is invariant under a permutation σ of the ground set, then its multilinear extension is invariant under the corresponding permutation of the coordinates: F(σ(x)) = F(x).
Statement
theorem multilinear_extension_perm_invariant {m : ℕ} (f : Finset (Fin m) → ℝ) (σ : Equiv.Perm (Fin m)) (hinv : ∀ S : Finset (Fin m), f (S.map σ.toEmbedding) = f S) (x : Fin m → ℝ) : multilinear_extension f (fun u => x (σ⁻¹ u)) = multilinear_extension f x
- Source
- step towards matroid_symmetry_gap_lt_eight_seventeenths
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- multilinear_extensionThe multilinear extension F(x) = Σ_S f(S) ∏_{u∈S} x_u ∏_{u∉S} (1 − x_u) of a set function f on {0, …, m−1}.
The proof, explained
To show that the multilinear extension F(x) is invariant under the coordinate permutation induced by σ, the proof expands F(x ∘ σ⁻¹) into its defining sum over all subsets S ⊆ Fin m. It first establishes that the set function f is invariant under σ⁻¹ as well as σ. It then reindexes both the product over S and the complementary product over Sᶜ along the bijection u ↦ σ⁻¹(u), transforming each summand at S into the corresponding summand at σ⁻¹(S). Finally, it reindexes the outer sum over the powerset via the bijection S ↦ σ⁻¹(S), proving that F(x ∘ σ⁻¹) = F(x).
Expand the definition of the multilinear extension for the permuted vector.
Unfolding the definition of multilinear_extension rewrites both sides as sums over all subsets S ⊆ Fin m of the product of f(S), the product of coordinates in S, and the product of (1 - coordinate) for coordinates outside S. For the left-hand side, each coordinate evaluation x(u) is replaced by x(σ⁻¹(u)).
simp only [multilinear_extension]The set function f is invariant under σ⁻¹, so f(S) = f(σ⁻¹(S)) for every subset S.
Applying the invariance hypothesis f(σ(T)) = f(T) to the subset T = σ⁻¹(S) gives f(σ(σ⁻¹(S))) = f(σ⁻¹(S)). Since σ and σ⁻¹ are inverse permutations, the composition σ ∘ σ⁻¹ is the identity embedding on S (via Finset.map_map), simplifying the left side to f(S).
uses
Finset.map_maphave hf : ∀ S : Finset (Fin m), f S = f (S.map σ.symm.toEmbedding) := by intro S have h := hinv (S.map σ.symm.toEmbedding) rwa [show (S.map σ.symm.toEmbedding).map σ.toEmbedding = S from by simp [Finset.map_map]] at h
The product of x(σ⁻¹(u)) over u ∈ S equals the product of x(v) over v ∈ σ⁻¹(S).
We reindex the product using Finset.prod_bij with the map u ↦ σ⁻¹(u). This map carries elements of S into σ⁻¹(S) by Finset.mem_map.mpr, is injective because σ⁻¹ is injective, and is surjective onto σ⁻¹(S) by Finset.mem_map.mp. At each element, the factors x(σ⁻¹(u)) match definitionally.
uses
Finset.prod_bij,Finset.mem_map.mpr,Finset.mem_map.mphave hprod : ∀ S : Finset (Fin m), ∏ u ∈ S, x (σ⁻¹ u) = ∏ u ∈ S.map σ.symm.toEmbedding, x u := by intro S refine Finset.prod_bij (fun u _ => σ⁻¹ u) ?_ ?_ ?_ ?_ · intro u hu; exact Finset.mem_map.mpr ⟨u, hu, rfl⟩ · intro a _ b _ hab; exact σ.symm.injective hab · intro b hb obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hb exact ⟨a, ha, rfl⟩ · intro a _; rfl
The complementary product of 1 - x(σ⁻¹(u)) over u ∈ Sᶜ equals the product of 1 - x(v) over v ∈ (σ⁻¹(S))ᶜ.
Because permutations commute with set complements, (σ⁻¹(S))ᶜ is equal to σ⁻¹(Sᶜ). Reindexing with Finset.prod_bij along u ↦ σ⁻¹(u) from Sᶜ to σ⁻¹(Sᶜ)—using Finset.mem_map.mpr for membership, injectivity of σ⁻¹, and Finset.mem_map.mp for surjectivity—shows the products are equal.
uses
Finset.prod_bij,Finset.mem_map.mpr,Finset.mem_map.mphave hprod' : ∀ S : Finset (Fin m), ∏ u ∈ Sᶜ, (1 - x (σ⁻¹ u)) = ∏ u ∈ (S.map σ.symm.toEmbedding)ᶜ, (1 - x u) := by intro S rw [show (S.map σ.symm.toEmbedding)ᶜ = Sᶜ.map σ.symm.toEmbedding from by ext u; simp] refine Finset.prod_bij (fun u _ => σ⁻¹ u) ?_ ?_ ?_ ?_ · intro u hu; exact Finset.mem_map.mpr ⟨u, hu, rfl⟩ · intro a _ b _ hab; exact σ.symm.injective hab · intro b hb obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hb exact ⟨a, ha, rfl⟩ · intro a _; rfl
The total sum over all subsets is invariant under the coordinate permutation, completing the proof.
We reindex the outer sum over the powerset using Finset.sum_bij' with the bijection S ↦ σ⁻¹(S) and its inverse T ↦ σ(T). Both maps preserve the set of all subsets (Finset.univ), and their compositions in both directions yield the identity on subsets via Finset.map_map. Finally, rewriting with the earlier lemmas (hf, hprod, and hprod') shows that for every subset S, the summand for S at x ∘ σ⁻¹ equals the summand for σ⁻¹(S) at x.
uses
Finset.sum_bij',Finset.map_maprefine Finset.sum_bij' (fun S _ => S.map σ.symm.toEmbedding) (fun T _ => T.map σ.toEmbedding) ?_ ?_ ?_ ?_ ?_ · intro a _; simp · intro a _; simp · intro a _ show (a.map σ.symm.toEmbedding).map σ.toEmbedding = a simp [Finset.map_map] · intro a _ show (a.map σ.toEmbedding).map σ.symm.toEmbedding = a simp [Finset.map_map] · intro a _ rw [hprod a, hprod' a, hf a]
Finset.map_map- Applying an embedding f and then an embedding g to a finite set is the same as mapping it along their composition g ∘ f.
Finset.prod_bij- Two finite products are equal if there is a bijection between their index sets that preserves the value of each factor.
Finset.mem_map.mpr- If an element is the image of some element in a finite set s under f, it belongs to Finset.map f s.
Finset.mem_map.mp- If an element belongs to Finset.map f s, then it is the image of some element in s under f.
Finset.sum_bij'- Two finite sums are equal if there are mutually inverse maps between their index sets that preserve the value of each term.
- In formalizing the change of variables, the products over S and Sᶜ and the outer sum over all subsets are each reindexed individually via explicit bijection lemmas (Finset.prod_bij and Finset.sum_bij'), whereas on paper all three reindexings are typically treated simultaneously.
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.
/-- The multilinear extension of a permutation-invariant set function is invariant under the coordinate permutation. -/theorem multilinear_extension_perm_invariant {m : ℕ} (f : Finset (Fin m) → ℝ) (σ : Equiv.Perm (Fin m)) (hinv : ∀ S : Finset (Fin m), f (S.map σ.toEmbedding) = f S) (x : Fin m → ℝ) : multilinear_extension f (fun u => x (σ⁻¹ u)) = multilinear_extension f x := by simp only [multilinear_extension] -- Invariance of `f` along `σ⁻¹`, derived from the hypothesis by applying it to `S.map σ⁻¹`. have hf : ∀ S : Finset (Fin m), f S = f (S.map σ.symm.toEmbedding) := by intro S have h := hinv (S.map σ.symm.toEmbedding) rwa [show (S.map σ.symm.toEmbedding).map σ.toEmbedding = S from by simp [Finset.map_map]] at h -- The `S`-product reindexes along `σ⁻¹ : S → S.map σ⁻¹`. have hprod : ∀ S : Finset (Fin m), ∏ u ∈ S, x (σ⁻¹ u) = ∏ u ∈ S.map σ.symm.toEmbedding, x u := by intro S refine Finset.prod_bij (fun u _ => σ⁻¹ u) ?_ ?_ ?_ ?_ · intro u hu; exact Finset.mem_map.mpr ⟨u, hu, rfl⟩ · intro a _ b _ hab; exact σ.symm.injective hab · intro b hb obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hb exact ⟨a, ha, rfl⟩ · intro a _; rfl -- Same for the complementary product, using `(S.map σ⁻¹)ᶜ = Sᶜ.map σ⁻¹`. have hprod' : ∀ S : Finset (Fin m), ∏ u ∈ Sᶜ, (1 - x (σ⁻¹ u)) = ∏ u ∈ (S.map σ.symm.toEmbedding)ᶜ, (1 - x u) := by intro S rw [show (S.map σ.symm.toEmbedding)ᶜ = Sᶜ.map σ.symm.toEmbedding from by ext u; simp] refine Finset.prod_bij (fun u _ => σ⁻¹ u) ?_ ?_ ?_ ?_ · intro u hu; exact Finset.mem_map.mpr ⟨u, hu, rfl⟩ · intro a _ b _ hab; exact σ.symm.injective hab · intro b hb obtain ⟨a, ha, rfl⟩ := Finset.mem_map.mp hb exact ⟨a, ha, rfl⟩ · intro a _; rfl -- Finally reindex the whole sum over the bijection `S ↦ S.map σ⁻¹` of `Finset (Fin m)`. refine Finset.sum_bij' (fun S _ => S.map σ.symm.toEmbedding) (fun T _ => T.map σ.toEmbedding) ?_ ?_ ?_ ?_ ?_ · intro a _; simp · intro a _; simp · intro a _ show (a.map σ.symm.toEmbedding).map σ.toEmbedding = a simp [Finset.map_map] · intro a _ show (a.map σ.toEmbedding).map σ.symm.toEmbedding = a simp [Finset.map_map] · intro a _ rw [hprod a, hprod' a, hf a]