AFTD Auto-Formalizing Theoretical Domains

multilinear_extension_perm_invariant

theoremverified

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

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

    line 6

      simp only [multilinear_extension]
  2. 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).

    lines 8–12

    uses Finset.map_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
  3. 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.

    lines 14–23

    uses Finset.prod_bij, Finset.mem_map.mpr, Finset.mem_map.mp

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

    lines 25–35

    uses Finset.prod_bij, Finset.mem_map.mpr, Finset.mem_map.mp

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

    lines 37–48

    uses Finset.sum_bij', Finset.map_map

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

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

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