Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2 (Dimension of Sn-equivariant unitaries)

Open
QAlgorithms.Papers.Independent.Support50.P30.equivariantUnitary_dimension

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let VnV_nVn​ be the full set of unitaries commuting with the qubit-permutation representation of SnS_nSn​. For 0≤m≤⌊n/2⌋0\le m\le\lfloor n/2\rfloor0≤m≤⌊n/2⌋ write dm=n−2m+1d_m=n-2m+1dm​=n−2m+1. The commuting unitary family has the product-unitary description Vn≃∏mU(dm)V_n\simeq\prod_m U(d_m)Vn​≃∏m​U(dm​), and its real tangent space at the identity consists of skew-Hermitian commuting matrices. Its real dimension is

dim⁡RVn=∑m=0⌊n/2⌋(n−2m+1)2=(n+33)=Θ(n3).\dim_{\mathbb R}V_n=\sum_{m=0}^{\lfloor n/2\rfloor}(n-2m+1)^2=\binom{n+3}{3}=\Theta(n^3).dimR​Vn​=m=0∑⌊n/2⌋​(n−2m+1)2=(3n+3​)=Θ(n3).

The asymptotic comparison uses positive constants and an eventual threshold independent of nnn. This describes all commuting unitaries, including their block phases, rather than identifying the Lie group generated by Eq. (9). The formula includes n=0n=0n=0.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P30
Formal statement
noncomputable section

open MeasureTheory

open scoped BigOperators ComplexConjugate Matrix.Norms.L2Operator NNReal ENNReal

namespace QAlgorithms.Papers.Independent.Support50.P30

/-- PDF pp.5,22, Lemma 2: full product-unitary family and real dimension;
this does not identify the Lie algebra generated by Eq.(9) with this tangent. -/
theorem equivariantUnitary_dimension :
    (∀ n : ℕ,
      Nonempty ((unitaryFamily n) ≃ₜ
        ((m : Sector n) → Matrix.unitaryGroup (Fin (blockDim n m)) ℂ)) ∧
      Module.finrank ℝ (tangentCommutant n) = (n + 3).choose 3 ∧
      (∑ m : Sector n, blockDim n m ^ 2) = (n + 3).choose 3) ∧
    ∃ a b : ℝ, 0 < a ∧ 0 < b ∧ ∃ N : ℕ, ∀ n ≥ N,
      a * (n : ℝ) ^ 3 ≤ (Module.finrank ℝ (tangentCommutant n) : ℝ) ∧
      (Module.finrank ℝ (tangentCommutant n) : ℝ) ≤ b * (n : ℝ) ^ 3 := by sorry

end QAlgorithms.Papers.Independent.Support50.P30

end
Source
Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks, arXiv:2210.09974v3, PDF p. 5, Lemma 2 (Dimension of Sn-equivariant unitaries)
Read-back

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

For each natural number nnn, let Hn=C{0,1}n\mathcal H_n=\mathbb C^{\{0,1\}^n}Hn​=C{0,1}n, let PpP_pPp​ be the permutation matrix with entry 111 at (x,y)(x,y)(x,y) precisely when xj=yp−1(j)x_j=y_{p^{-1}(j)}xj​=yp−1(j)​ for every position jjj, and define

Un={U∈U(Hn):UPp=PpU for every position permutation p},Tn=span⁡R{A:A∗=−A, APp=PpA for every p}.\mathcal U_n=\{U\in U(\mathcal H_n):UP_p=P_pU\text{ for every position permutation }p\}, \qquad T_n=\operatorname{span}_{\mathbb R}\{A:A^*=-A,\ AP_p=P_pA\text{ for every }p\}.Un​={U∈U(Hn​):UPp​=Pp​U for every position permutation p},Tn​=spanR​{A:A∗=−A, APp​=Pp​A for every p}.

For sectors m=0,…,⌊n/2⌋m=0,\ldots,\lfloor n/2\rfloorm=0,…,⌊n/2⌋, put dm=n−2m+1d_m=n-2m+1dm​=n−2m+1. The assertion is that, for every nnn, there exists a homeomorphism, with the inherited matrix topologies and the product topology,

Un≅top∏m=0⌊n/2⌋U(dm),\mathcal U_n\cong_{\mathrm{top}}\prod_{m=0}^{\lfloor n/2\rfloor}U(d_m),Un​≅top​m=0∏⌊n/2⌋​U(dm​),

and both exact equalities hold:

dim⁡RTn=(n+33),∑m=0⌊n/2⌋dm2=(n+33).\dim_{\mathbb R}T_n=\binom{n+3}{3}, \qquad \sum_{m=0}^{\lfloor n/2\rfloor}d_m^2=\binom{n+3}{3}.dimR​Tn​=(3n+3​),m=0∑⌊n/2⌋​dm2​=(3n+3​).

These statements include n=0n=0n=0. In addition, there exist real constants a,b>0a,b>0a,b>0 and a natural number NNN such that every natural number n≥Nn\ge Nn≥N satisfies

an3≤dim⁡RTn≤bn3.a n^3\le \dim_{\mathbb R}T_n\le b n^3.an3≤dimR​Tn​≤bn3.
Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 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