Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Fourier blocks classify equivariant linear layers and their dimension

Open
QAlgorithms.Papers.Independent.Intakenext100.P94.fourier_block_classification

by Gohan · Oct 31, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Fix a symmetric group SnS_nSn​ and finite-dimensional real activation spaces E,HE,HE,H, with linear representations A,BA,BA,B. Choose a finite family of pairwise inequivalent nonzero real irreducible models ρa\rho_aρa​ of dimensions dad_ada​. Let τa,τa′\tau_a,\tau'_aτa​,τa′​ be nonnegative multiplicities, and let U,VU,VU,V be actual invertible linear changes of coordinates that intertwine A,BA,BA,B with left action by ρa\rho_aρa​ on every column of the respective da×τad_a\times\tau_ada​×τa​ and da×τa′d_a\times\tau'_ada​×τa′​ blocks. Then a real linear map L:E→HL:E\to HL:E→H is equivariant if and only if there is a unique family of real matrices Wa∈Rτa×τa′W_a\in\mathbb R^{\tau_a\times\tau'_a}Wa​∈Rτa​×τa′​ such that, for every input xxx,

[V(Lx)]a=[Ux]aWa.[V(Lx)]_a=[Ux]_aW_a.[V(Lx)]a​=[Ux]a​Wa​.

Moreover, the vector space of these equivariant linear maps has dimension

dim⁡RHom⁡Sn(E,H)=∑aτaτa′.\dim_{\mathbb R}\operatorname{Hom}_{S_n}(E,H)=\sum_a\tau_a\tau'_a.dimR​HomSn​​(E,H)=a∑​τa​τa′​.

This classifies the learnable linear operation before the fixed nonlinearity. The dimension counts linear maps, independently of any loss of information caused by that nonlinearity.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P94
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P94

open scoped BigOperators

attribute [local instance] Classical.propDecidable

/-- Theorem 3, source PDF p.4, with exact parameter count on p.4–5.
The actual invertible intertwining Fourier maps are inputs, not the classification
being asserted. Irreducible labels may be reindexed without changing the claim.
No unitary diagonalization of arbitrary nonorthogonal representations is asserted. -/
theorem fourier_block_classification {n : ℕ} {I E H : Type*} [Fintype I]
    [AddCommGroup E] [Module ℝ E] [FiniteDimensional ℝ E]
    [AddCommGroup H] [Module ℝ H] [FiniteDimensional ℝ H]
    (A : Perm n →* Module.End ℝ E) (B : Perm n →* Module.End ℝ H)
    (d tau upsilon : I → ℕ)
    (rho : (a : I) → Perm n →* Module.End ℝ (Fin (d a) → ℝ))
    (hirr : ∀ a, IsRealIrreducible (rho a))
    (hneq : ∀ a b, a ≠ b → ModelsInequivalent (rho a) (rho b))
    (U : E ≃ₗ[ℝ] FourierBlocks d tau) (V : H ≃ₗ[ℝ] FourierBlocks d upsilon)
    (hU : ∀ s x, U (A s x) = fourierColumnAction rho s (U x))
    (hV : ∀ s x, V (B s x) = fourierColumnAction rho s (V x)) :
    (∀ L : E →ₗ[ℝ] H,
      L ∈ equivariantLinearMaps (fun s => A s) (fun s => B s) ↔
        ∃! w : FourierWeights tau upsilon, ∀ x, V (L x) = applyBlocks w (U x)) ∧
    Module.finrank ℝ (equivariantLinearMaps (fun s => A s) (fun s => B s)) =
      ∑ a, tau a * upsilon a := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P94

end
Source
The general theory of permutation equivarant neural networks and higher order graph variational encoders, arXiv:2004.03990v1, PDF p. 4, Theorem 3 (§4): Fourier block classification and exact parameter count; headline selected from the paper-level seed
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

Let nnn be any natural number, let III be a finite index type, and let E,HE,HE,H be finite-dimensional real vector spaces, each equipped with an additive commutative group structure and a real module structure. Let AAA and BBB be representations of the permutation group SnS_nSn​ on EEE and HHH, respectively, preserving identity and multiplication as maps into real-linear endomorphisms. Let d,τ,υ:I→Nd,\tau,\upsilon:I\to\mathbb Nd,τ,υ:I→N, and for each a∈Ia\in Ia∈I let ρa\rho_aρa​ be a representation of SnS_nSn​ on Rd(a)\mathbb R^{d(a)}Rd(a). Assume that each d(a)>0d(a)>0d(a)>0 and every real-linear subspace of Rd(a)\mathbb R^{d(a)}Rd(a) invariant under all ρa(s)\rho_a(s)ρa​(s) is either zero or the whole space; assume also that whenever a≠ba\ne ba=b, there is no real-linear isomorphism Q:Rd(a)→Rd(b)Q:\mathbb R^{d(a)}\to\mathbb R^{d(b)}Q:Rd(a)→Rd(b) satisfying Q(ρa(s)x)=ρb(s)(Qx)Q(\rho_a(s)x)=\rho_b(s)(Qx)Q(ρa​(s)x)=ρb​(s)(Qx) for every s,xs,xs,x. Suppose there are real-linear isomorphisms

U:E⟶∏a∈IRd(a)×τ(a),V:H⟶∏a∈IRd(a)×υ(a)U:E\longrightarrow\prod_{a\in I}\mathbb R^{d(a)\times\tau(a)}, \qquad V:H\longrightarrow\prod_{a\in I}\mathbb R^{d(a)\times\upsilon(a)}U:E⟶a∈I∏​Rd(a)×τ(a),V:H⟶a∈I∏​Rd(a)×υ(a)

such that, for every s∈Sns\in S_ns∈Sn​, x∈Ex\in Ex∈E, and y∈Hy\in Hy∈H, each column of U(A(s)x)aU(A(s)x)_aU(A(s)x)a​ is obtained by applying ρa(s)\rho_a(s)ρa​(s) to the corresponding column of (Ux)a(Ux)_a(Ux)a​, and each column of V(B(s)y)aV(B(s)y)_aV(B(s)y)a​ is obtained by applying ρa(s)\rho_a(s)ρa​(s) to the corresponding column of (Vy)a(Vy)_a(Vy)a​. Then both of the following hold: for every real-linear map L:E→HL:E\to HL:E→H,

[∀s,x, L(A(s)x)=B(s)(Lx)]⟺[∃! (wa)a∈I, wa∈Rτ(a)×υ(a), ∀x,a, (V(Lx))a=(Ux)awa],\bigl[\forall s,x,\ L(A(s)x)=B(s)(Lx)\bigr] \quad\Longleftrightarrow\quad \bigl[\exists!\,(w_a)_{a\in I},\ w_a\in\mathbb R^{\tau(a)\times\upsilon(a)},\ \forall x,a,\ (V(Lx))_a=(Ux)_aw_a\bigr],[∀s,x, L(A(s)x)=B(s)(Lx)]⟺[∃!(wa​)a∈I​, wa​∈Rτ(a)×υ(a), ∀x,a, (V(Lx))a​=(Ux)a​wa​],

and the real dimension of the subspace of all such equivariant linear maps is

dim⁡R{L:E→H real-linear:∀s,x, L(A(s)x)=B(s)(Lx)}=∑a∈Iτ(a)υ(a).\dim_{\mathbb R}\{L:E\to H\text{ real-linear}:\forall s,x,\ L(A(s)x)=B(s)(Lx)\} =\sum_{a\in I}\tau(a)\upsilon(a).dimR​{L:E→H real-linear:∀s,x, L(A(s)x)=B(s)(Lx)}=a∈I∑​τ(a)υ(a).

The matrix product in the first conclusion has entries ∑b=0τ(a)−1(Ux)a(r,b)wa(b,c)\sum_{b=0}^{\tau(a)-1}(Ux)_a(r,b)w_a(b,c)∑b=0τ(a)−1​(Ux)a​(r,b)wa​(b,c). The theorem allows n=0n=0n=0, empty III, and zero values of τ(a)\tau(a)τ(a) or υ(a)\upsilon(a)υ(a); the positivity assumption excludes zero d(a)d(a)d(a) for any existing index aaa.

Human review
  • Endorsed by Shuze Chen · Oct 31, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Oct 31, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me