Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2: center of the permutation image

Open
QAlgorithms.Papers.Independent.Intakenext100.P38.permutation_center

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

prove2quantum

Let TμT_\muTμ​ consist of permutations with exactly μ\muμ disjoint transpositions and all other points fixed, and let Lμ=∑π∈TμR(π)L_\mu=\sum_{\pi\in T_\mu}R(\pi)Lμ​=∑π∈Tμ​​R(π), where R(π)∣b⟩=∣b∘π−1⟩R(\pi)|b\rangle=|b\circ\pi^{-1}\rangleR(π)∣b⟩=∣b∘π−1⟩. Let An=span⁡C{R(π):π∈Sn}\mathcal A_n=\operatorname{span}_{\mathbb C}\{R(\pi):\pi\in S_n\}An​=spanC​{R(π):π∈Sn​} be the complex group-algebra image, and let pn={A∈An:A†=−A}\mathfrak p_n=\{A\in\mathcal A_n:A^\dagger=-A\}pn​={A∈An​:A†=−A}. For every n≥0n\ge0n≥0,

z(pn)=span⁡R{iLμ:0≤2μ≤n}.\mathfrak z(\mathfrak p_n)=\operatorname{span}_{\mathbb R}\{iL_\mu:0\le2\mu\le n\}.z(pn​)=spanR​{iLμ​:0≤2μ≤n}.

The skew part of the complex image corrects (B3): arbitrary permutation matrices need not be Hermitian. The source cites an alternative proof in Ref. [56] and notes overlap with Ref. [18].

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P38
Formal statement
noncomputable section

namespace QAlgorithms.Papers.Independent.Intakenext100.P38

open scoped BigOperators

open QAlgorithms.Papers.Independent.Support50.P30
  (QnnOperator qubitPermutationMatrix PermutationEquivariant)

attribute [local instance] LieRing.ofAssociativeRing

/-- PDF pp.12–13, Lemma 2: center of the skew part of the complex permutation
image. Corrects (B3), which incorrectly spans iR(pi) over R for arbitrary pi.
Alternative proof is cited to Ref.[56]; p.13 also credits Ref.[18]. -/
theorem permutation_center (n : ℕ) :
    algebraCenter (permutationImage n) =
      Submodule.span ℝ {A | ∃ mu : ℕ, 2 * mu ≤ n ∧
        A = Complex.I • transpositionSum n mu} := by sorry

end QAlgorithms.Papers.Independent.Intakenext100.P38

end
Source
On the universality of SnS_nSn​-equivariant kkk-body gates, arXiv:2303.00728v2, PDF p. 12, lemma2
Read-back

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

For every natural number nnn, let PπP_\piPπ​ be the complex matrix on {0,1}n\{0,1\}^n{0,1}n sending ∣z⟩|z\rangle∣z⟩ to ∣z∘π−1⟩|z\circ\pi^{-1}\rangle∣z∘π−1⟩, where π\piπ ranges over permutations of the nnn positions. Let Pn\mathcal P_nPn​ be the real linear span of all skew-Hermitian matrices belonging to the complex linear span of the matrices PπP_\piPπ​. For each natural number μ\muμ, define

Tn,μ=∑π2=id∣{j:π(j)≠j}∣=2μPπ,T_{n,\mu} =\sum_{\substack{\pi^2=\mathrm{id}\\ |\{j:\pi(j)\ne j\}|=2\mu}}P_\pi,Tn,μ​=π2=id∣{j:π(j)=j}∣=2μ​∑​Pπ​,

so the sum runs over involutions moving exactly 2μ2\mu2μ positions, equivalently products of μ\muμ disjoint transpositions. Then the real linear span of the matrices A∈PnA\in\mathcal P_nA∈Pn​ commuting with every B∈PnB\in\mathcal P_nB∈Pn​ is

span⁡R{ iTn,μ:μ∈N, 2μ≤n }.\operatorname{span}_{\mathbb R} \{\,iT_{n,\mu}:\mu\in\mathbb N,\ 2\mu\le n\,\}.spanR​{iTn,μ​:μ∈N, 2μ≤n}.

The case μ=0\mu=0μ=0 contributes Tn,0=IT_{n,0}=ITn,0​=I, and n=0n=0n=0 is included.

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