Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Partition diagrams, the diagram algebras Pn(d)P_n(d)Pn​(d), Pn−1/2(d)P_{n-1/2}(d)Pn−1/2​(d), Bn(d)B_n(d)Bn​(d), Br,s(d)B_{r,s}(d)Br,s​(d) and the Schur representation

Definition
SemisimpleQFT_Diagram

by Shuze Chen · Nov 19, 2026 · Mathlib 0df444a (Lean v4.33.1)

diagram-algebrasquantum-computingquantum-fourier-transformrepresentation-theory

Diagrams (Definitions 4.1, 4.2). A partition diagram with nnn columns is a set partition of the 2n2n2n vertices {1,…,n}∪{1′,…,n′}\{1,\dots,n\}\cup\{1',\dots,n'\}{1,…,n}∪{1′,…,n′}, encoded as an equivalence relation on Vertex n = Bool × Fin n: (false, i) is the top vertex i+1i+1i+1 and (true, i) is the bottom vertex (i+1)′(i+1)'(i+1)′. cc D is the number of blocks of DDD; pn D is the propagating number, the number of blocks meeting both rows.

Product (Definition 4.3). stack D₁ D₂ is the partition into connected components of the three-row picture obtained by placing D1D_1D1​ on rows 0,10,10,1 and D2D_2D2​ on rows 1,21,21,2 (bottom row of D1D_1D1​ identified with top row of D2D_2D2​). comp D₁ D₂ is its restriction to rows 000 and 222, and loops D₁ D₂ is the number ccc of components lying entirely in the middle row, so that D1D2=d c⋅comp(D1,D2)D_1D_2=d^{\,c}\cdot\mathrm{comp}(D_1,D_2)D1​D2​=dc⋅comp(D1​,D2​) in Pn(d)P_n(d)Pn​(d). one n is the identity diagram (blocks {i,i′}\{i,i'\}{i,i′}), op D exchanges the two rows, and join D E is D∨ED\vee ED∨E, the finest partition coarsening both.

Diagram algebras. The parameter ddd is a natural number. leftMul d D is the matrix, on the space with basis all diagrams, of left multiplication by DDD: the column of BBB is d loops(D,B)d^{\,\mathrm{loops}(D,B)}dloops(D,B) times the basis vector comp(D,B)\mathrm{comp}(D,B)comp(D,B). For a set SSS of diagrams, diagramAlgebra S d is the subalgebra of matrices generated by {leftMuld(D):D∈S}\{\mathrm{leftMul}_d(D):D\in S\}{leftMuld​(D):D∈S}: the diagram algebra spanned by SSS, realised by its left regular representation. The coefficient of the diagram DDD in an element xxx is the matrix entry xD,1x_{D,\mathbf 1}xD,1​. diag S d D is the diagram D∈SD\in SD∈S as an element of the algebra.

The diagram sets are: partitionSet n (all diagrams, Pn(d)P_n(d)Pn​(d)); halfSet n (nnn and n′n'n′ in the same block, Pn−1/2(d)P_{n-1/2}(d)Pn−1/2​(d)); brauerSet n (every block has exactly two vertices, Bn(d)B_n(d)Bn​(d)); walledSet r n (Brauer diagrams in which a block lying on one side of the wall after column rrr joins the two rows and a block crossing the wall lies in one row, Br,n−r(d)B_{r,n-r}(d)Br,n−r​(d)). IsStdFamily n d S says that SSS is one of these four sets and ddd is in the corresponding range of Theorems 4.12–4.15: d∉{0,…,2n−2}d\notin\{0,\dots,2n-2\}d∈/{0,…,2n−2} for Pn(d)P_n(d)Pn​(d) and Pn−1/2(d)P_{n-1/2}(d)Pn−1/2​(d) (with n≥1n\ge1n≥1 for the latter), d∉{0,…,n}d\notin\{0,\dots,n\}d∈/{0,…,n} for Bn(d)B_n(d)Bn​(d), d∉{0,…,n−2}d\notin\{0,\dots,n-2\}d∈/{0,…,n−2} for Br,s(d)B_{r,s}(d)Br,s​(d).

Computational basis (Eq. (4.10)). scale d D is the real number d(n−cc(D))/2d^{(n-\mathrm{cc}(D))/2}d(n−cc(D))/2. diagBasis S d is the scaled diagram basis B(A)={d(n−cc(D))/2D}D∈S\mathcal B(A)=\{d^{(n-\mathrm{cc}(D))/2}D\}_{D\in S}B(A)={d(n−cc(D))/2D}D∈S​: its vectors are scale(D)⋅D\mathrm{scale}(D)\cdot Dscale(D)⋅D and the coordinate of xxx along DDD is xD,1/scale(D)x_{D,\mathbf 1}/\mathrm{scale}(D)xD,1​/scale(D).

Schur representation (Eqs. (4.12)–(4.14)). schurDiagram d D is the 0/10/10/1 matrix on (Cd)⊗n(\mathbb{C}^d)^{\otimes n}(Cd)⊗n with S(D)x,y=1S(D)_{x,y}=1S(D)x,y​=1 exactly when labelling the top row by xxx and the bottom row by yyy is constant on every block of DDD. schur d x =∑DxD,1S(D)=\sum_D x_{D,\mathbf 1}S(D)=∑D​xD,1​S(D) and schurInner d x y =Tr(S(x)†S(y))=\mathrm{Tr}(S(x)^\dagger S(y))=Tr(S(x)†S(y)).

Properties of a Fourier basis of a diagram algebra. For a FourierData FFF of diagramAlgebra S d:

  • IsOrthogonalForm F (Eq. (5.25)): ρ(Dop)=ρ(D)†\rho(D^{\mathrm{op}})=\rho(D)^\daggerρ(Dop)=ρ(D)† for every D∈SD\in SD∈S with Dop∈SD^{\mathrm{op}}\in SDop∈S and every irrep ρ\rhoρ.
  • IsVanishing F size (Theorem 4.17, with size =∣⋅∣=|\cdot|=∣⋅∣ on labels): ρ(D)=0\rho(D)=0ρ(D)=0 whenever D∈SD\in SD∈S and pn(D)<∣ρ∣\mathrm{pn}(D)<|\rho|pn(D)<∣ρ∣.
  • schurMult F i is the multiplicity mρm_\rhomρ​ of the irrep ρ\rhoρ of the index iii in the Schur representation, computed as rank S(Eiiρ)\mathrm{rank}\,S(E^\rho_{ii})rankS(Eiiρ​).
  • concentrationDefect F size D is ∣⟨a~∣Πr∣a~⟩−⟨a~,a~⟩∣\big|\langle\tilde a|\Pi_r|\tilde a\rangle-\langle\tilde a,\tilde a\rangle\big|​⟨a~∣Πr​∣a~⟩−⟨a~,a~⟩​ of Eq. (4.24), where ∣a~⟩=FT~A∣a⟩|\tilde a\rangle=\widetilde{\mathrm{FT}}_A|a\rangle∣a~⟩=FTA​∣a⟩ for the scaled diagram aaa of DDD, r=pn(D)r=\mathrm{pn}(D)r=pn(D) and Πr\Pi_rΠr​ projects onto the states ∣λ,i,j⟩|\lambda,i,j\rangle∣λ,i,j⟩ with ∣λ∣=r|\lambda|=r∣λ∣=r.
Definition code
import Definitions.Def_SemisimpleQFT_Fourier

/-!
# Partition diagrams and diagram algebras

Source: B. Foxman, B. Nehoran, Y. Ding, *Efficient Quantum Fourier Transforms For Semisimple
Algebras*, Section 4 (PDF pp. 21–29).

Conventions:

* A partition diagram on `2n` vertices is a set partition of `{1,…,n} ∪ {1',…,n'}`, here an
  equivalence relation on `Vertex n = Bool × Fin n`: `(false, i)` is the top vertex `i + 1` and
  `(true, i)` is the bottom vertex `(i + 1)'`.
* The parameter `d` is a non-negative integer (PDF p. 25: "assume `d ∈ ℤ_{≥0}`").
* The partition algebra `P_n(d)` is realised through its left regular representation on the
  space with basis the diagrams: the diagram `D` is the matrix `leftMul d D` sending the basis
  vector `B` to `d^{c(D,B)} (D ∘ B)`, and a diagram algebra is the algebra generated by the
  matrices of a set of diagrams. Since `D ∘ 1 = D` with no removed component, the coefficient of
  the diagram `D` in an element `x` of the algebra is the matrix entry `x D 1`.
-/

set_option warn.classDefReducibility false

namespace SemisimpleQFT

open scoped BigOperators ComplexConjugate

/-- A vertex of a diagram with `n` columns: `(false, i)` is the top vertex `i + 1`,
`(true, i)` is the bottom vertex `(i + 1)'`. -/
abbrev Vertex (n : ℕ) := Bool × Fin n

/-- Definition 4.1 (PDF p. 22): a partition diagram, a set partition of the `2n` vertices
`{1,…,n} ∪ {1',…,n'}`, given as the equivalence relation "in the same block". -/
abbrev Diagram (n : ℕ) := Setoid (Vertex n)

instance diagramFinite (n : ℕ) : Finite (Diagram n) := by
  apply Finite.of_injective (fun D : Diagram n => D.r)
  intro D E h
  exact Setoid.ext fun a b => Iff.of_eq (congrFun (congrFun h a) b)

noncomputable instance diagramFintype (n : ℕ) : Fintype (Diagram n) := Fintype.ofFinite _

noncomputable instance diagramDecEq (n : ℕ) : DecidableEq (Diagram n) := Classical.decEq _

noncomputable instance diagramSetFintype {n : ℕ} (S : Set (Diagram n)) : Fintype S :=
  Fintype.ofFinite _

variable {n : ℕ}

/-- PDF p. 22: `cc(D)`, the number of connected components (blocks) of `D`. -/
noncomputable def cc (D : Diagram n) : ℕ := Nat.card (Quotient D)

/-- Definition 4.2 (PDF p. 22, Eq. (4.1)): the propagating number `pn(D)`, the number of blocks
of `D` that meet both the top row `{1,…,n}` and the bottom row `{1',…,n'}`. -/
noncomputable def pn (D : Diagram n) : ℕ :=
  Nat.card {c : Quotient D //
    (∃ i : Fin n, Quotient.mk D (false, i) = c) ∧ (∃ i : Fin n, Quotient.mk D (true, i) = c)}

/-- The place of a vertex of the upper diagram `D₁` in the stack of `D₁` over `D₂`
(rows `0`, `1`, `2` are the top row of `D₁`, the identified middle row, the bottom row of
`D₂`). -/
def upper (v : Vertex n) : Fin 3 × Fin n := (if v.1 then 1 else 0, v.2)

/-- The place of a vertex of the lower diagram `D₂` in the stack. -/
def lower (v : Vertex n) : Fin 3 × Fin n := (if v.1 then 2 else 1, v.2)

/-- The place in the stack of a vertex of the product diagram (top row of `D₁`, bottom row of
`D₂`). -/
def outer (v : Vertex n) : Fin 3 × Fin n := (if v.1 then 2 else 0, v.2)

/-- Two vertices of the stack are joined by a block of `D₁` (placed on rows `0`, `1`) or by a
block of `D₂` (placed on rows `1`, `2`). -/
def stackRel (D₁ D₂ : Diagram n) (a b : Fin 3 × Fin n) : Prop :=
  (∃ u v : Vertex n, upper u = a ∧ upper v = b ∧ D₁ u v) ∨
  (∃ u v : Vertex n, lower u = a ∧ lower v = b ∧ D₂ u v)

/-- Definition 4.3 (PDF p. 22): the stacked diagram of `D₁` over `D₂`, the bottom row of `D₁`
identified with the top row of `D₂`: the connected components of the three-row picture. -/
def stack (D₁ D₂ : Diagram n) : Setoid (Fin 3 × Fin n) :=
  Relation.EqvGen.setoid (stackRel D₁ D₂)

/-- Definition 4.3 (PDF p. 22): the diagram of the product `D₁ D₂`, the stack of `D₁` over `D₂`
with the middle row removed. -/
def comp (D₁ D₂ : Diagram n) : Diagram n := Setoid.comap outer (stack D₁ D₂)

/-- Definition 4.3 (PDF p. 22): the number `c` of connected components of the stack of `D₁` over
`D₂` that are removed with the middle row, i.e. that lie entirely in the middle row. The product
in `P_n(d)` is `D₁ D₂ = d^c · comp D₁ D₂`. -/
noncomputable def loops (D₁ D₂ : Diagram n) : ℕ :=
  Nat.card {c : Quotient (stack D₁ D₂) //
    ∀ a : Fin 3 × Fin n, Quotient.mk (stack D₁ D₂) a = c → a.1 = 1}

/-- The identity diagram: the blocks are the columns `{i, i'}`. -/
def one (n : ℕ) : Diagram n := Setoid.ker (fun v : Vertex n => v.2)

/-- PDF p. 27 (Section 4.5.1): the involution `op` on diagrams, exchanging the two rows. -/
def op (D : Diagram n) : Diagram n := Setoid.comap (fun v : Vertex n => (!v.1, v.2)) D

/-- Definition 4.3 (PDF p. 22): left multiplication by the diagram `D` in `P_n(d)`, as a matrix
on the space with basis the diagrams: the column of the diagram `B` is `d^{c(D,B)}` times the
basis vector `comp D B`. -/
noncomputable def leftMul (d : ℕ) (D : Diagram n) : Matrix (Diagram n) (Diagram n) ℂ :=
  Matrix.of fun C B => if comp D B = C then (d : ℂ) ^ loops D B else 0

/-- Section 4.2 (PDF pp. 22–24): the diagram algebra with parameter `d` spanned by a set `S` of
diagrams (closed under the diagram product and containing the identity diagram, as all the sets
used are), realised by its left regular representation: the subalgebra of matrices generated by
the left multiplications by the diagrams of `S`. For `S` the set of all diagrams this is the
partition algebra `P_n(d)` of Definition 4.3. -/
noncomputable def diagramAlgebra (S : Set (Diagram n)) (d : ℕ) :
    Subalgebra ℂ (Matrix (Diagram n) (Diagram n) ℂ) :=
  Algebra.adjoin ℂ (leftMul d '' S)

/-- The diagram `D ∈ S` as an element of the diagram algebra. -/
noncomputable def diag (S : Set (Diagram n)) (d : ℕ) (D : S) : diagramAlgebra S d :=
  ⟨leftMul d D.1, Algebra.subset_adjoin ⟨D.1, D.2, rfl⟩⟩

/-- PDF p. 26, Eq. (4.10): the scaling factor `d^{(n - cc(D))/2}` of the diagram `D` in the
computational basis (a real power; it is `1` when `cc(D) = n`, in particular for every Brauer
diagram). -/
noncomputable def scale (d : ℕ) (D : Diagram n) : ℝ :=
  (d : ℝ) ^ (((n : ℝ) - (cc D : ℝ)) / 2)

/-- PDF p. 26, Eq. (4.10): the computational basis `𝓑(A) = {d^{(n - cc(D))/2} D}_{D ∈ S}` of the
diagram algebra `A` spanned by `S`. The coordinate of `x` along the scaled diagram of `D` is the
coefficient `x D 1` of `D` in `x` divided by `d^{(n - cc(D))/2}`. -/
noncomputable def diagBasis (S : Set (Diagram n)) (d : ℕ) : CompBasis (diagramAlgebra S d) S where
  vec D := ((scale d D.1 : ℝ) : ℂ) • diag S d D
  coord :=
    { toFun := fun x D => x.1 D.1 (one n) / ((scale d D.1 : ℝ) : ℂ)
      map_add' := by
        intro x y
        funext D
        simp [add_div]
      map_smul' := by
        intro c x
        funext D
        simp [mul_div_assoc] }

/-- Definition 4.3 (PDF p. 22): all partition diagrams, the diagram set of `P_n(d)`. -/
def partitionSet (n : ℕ) : Set (Diagram n) := Set.univ

/-- PDF p. 23: the diagram set of the half partition algebra `P_{n-1/2}(d)`: the diagrams in
which `n` and `n'` are in the same block. -/
def halfSet (n : ℕ) : Set (Diagram n) :=
  {D | ∀ i : Fin n, i.val + 1 = n → D (false, i) (true, i)}

/-- Definition 4.7 (PDF p. 23): a Brauer diagram, a partition diagram in which every block has
size 2. -/
def IsBrauer (D : Diagram n) : Prop :=
  ∀ v : Vertex n, ∃ w : Vertex n, w ≠ v ∧ ∀ u : Vertex n, D v u ↔ (u = v ∨ u = w)

/-- Definition 4.7 (PDF p. 23): the diagram set of the Brauer algebra `B_n(d)`. -/
def brauerSet (n : ℕ) : Set (Diagram n) := {D | IsBrauer D}

/-- Definition 4.9 (PDF p. 23): a walled Brauer diagram with the wall after the first `r`
columns: a Brauer diagram in which a block with both vertices in the first `r` columns, or both
in the remaining columns, has its vertices in opposite rows, and every other block has its
vertices in the same row. -/
def IsWalled (r : ℕ) (D : Diagram n) : Prop :=
  IsBrauer D ∧ ∀ u v : Vertex n, D u v → u ≠ v →
    ((u.2.val < r ↔ v.2.val < r) ↔ u.1 ≠ v.1)

/-- Definition 4.9 (PDF p. 23): the diagram set of the walled Brauer algebra `B_{r,s}(d)` with
`r + s = n` (the wall is after the first `r` of the `n` columns). -/
def walledSet (r n : ℕ) : Set (Diagram n) := {D | IsWalled r D}

/-- "`A ∈ {P_n(d), P_{n-1/2}(d), B_n(d), B_{r,s}(d)}`" with `d` in the range where the cited
theorems give semisimplicity: `d ∉ {0,…,2n-2}` for `P_n(d)` and `P_{n-1/2}(d)` (Theorems 4.12,
4.13), `d ∉ {0,…,n}` for `B_n(d)` (Theorem 4.14), `d ∉ {0,…,n-2}` for `B_{r,s}(d)`, `r + s = n`
(Theorem 4.15). `S` is the diagram set of the algebra. -/
def IsStdFamily (n d : ℕ) (S : Set (Diagram n)) : Prop :=
  (S = partitionSet n ∧ 2 * n < d + 2) ∨
  (S = halfSet n ∧ 0 < n ∧ 2 * n < d + 2) ∨
  (S = brauerSet n ∧ n < d) ∨
  (∃ r : ℕ, r ≤ n ∧ S = walledSet r n ∧ n < d + 2)

/-- PDF p. 28: the join `D ∨ E`, the finest partition coarsening both `D` and `E`. -/
def join (D E : Diagram n) : Diagram n := D ⊔ E

open Classical in
/-- PDF p. 27, Eqs. (4.12)–(4.13): the Schur representation of a diagram on `(ℂ^d)^{⊗n}`:
`S(D)_{x,y} = 1` if the labelling of the vertices by `x` (top row) and `y` (bottom row) is
constant on every block of `D`, and `0` otherwise. -/
noncomputable def schurDiagram (d : ℕ) (D : Diagram n) :
    Matrix (Fin n → Fin d) (Fin n → Fin d) ℂ :=
  Matrix.of fun x y =>
    if ∀ u v : Vertex n, D u v →
        (if u.1 then y u.2 else x u.2) = (if v.1 then y v.2 else x v.2) then 1 else 0

/-- PDF p. 27: the Schur representation `S`, extended linearly from diagrams: the element `x`
with diagram coefficients `x D 1` is sent to `Σ_D (x D 1) S(D)`. -/
noncomputable def schur (d : ℕ) (x : Matrix (Diagram n) (Diagram n) ℂ) :
    Matrix (Fin n → Fin d) (Fin n → Fin d) ℂ :=
  ∑ D : Diagram n, x D (one n) • schurDiagram d D

/-- PDF p. 27, Eq. (4.14): the Schur inner product
`⟨a, b⟩_S^{op} = Tr(S(a)† S(b))`. -/
noncomputable def schurInner (d : ℕ) (x y : Matrix (Diagram n) (Diagram n) ℂ) : ℂ :=
  Matrix.trace ((schur d x).conjTranspose * schur d y)

section FourierOnDiagramAlgebras

variable {S : Set (Diagram n)} {d : ℕ} {Λ : Type*} {J : Type*} [Fintype J] [DecidableEq J]

/-- Section 5.4 (PDF p. 35, Eq. (5.25)): the Fourier basis `F` of the diagram algebra spanned by
`S` is in the orthogonal form: `ρ(D^{op}) = ρ(D)†` for every irrep `ρ` and every diagram
`D ∈ S` (whose flip `D^{op}` is again in `S`); as block matrices, `⊕_ρ ρ(D^{op})` is the
conjugate transpose of `⊕_ρ ρ(D)`. -/
def IsOrthogonalForm (F : FourierData (diagramAlgebra S d) Λ J) : Prop :=
  ∀ (D : S) (hD : op D.1 ∈ S),
    F.rep (diag S d ⟨op D.1, hD⟩) = (F.rep (diag S d D)).conjTranspose

/-- Theorem 4.17 (PDF p. 26) as a property of a labelling of the irreps: `size ρ` is the number
of boxes `|ρ|` of the label, and `ρ(D) = 0` for every diagram `D ∈ S` with `pn(D) < |ρ|`. -/
def IsVanishing (F : FourierData (diagramAlgebra S d) Λ J) (size : Λ → ℕ) : Prop :=
  ∀ (D : S) (i j : J), F.lab i = F.lab j → pn D.1 < size (F.lab i) →
    F.rep (diag S d D) i j = 0

/-- PDF p. 27, Lemma 4.19: the multiplicity `m_ρ` of the irrep `ρ` (the irrep of the basis index
`i`) in the Schur representation, computed as the rank of `S(E^ρ_{ii})`: the image of the
primitive idempotent `E^ρ_{ii}` in a representation is a copy of its multiplicity space. -/
noncomputable def schurMult (F : FourierData (diagramAlgebra S d) Λ J) (i : J) : ℕ :=
  (schur d (F.E i i).1).rank

/-- Theorem 4.26 (PDF p. 30, Eq. (4.24)): for the scaled diagram `a` of `D ∈ S` and
`|ã⟩ = F̃T_A |a⟩`, the quantity `|⟨ã|Π_r|ã⟩₀ - ⟨ã, ã⟩₀|` with `r = pn(D)`, where `Π_r` is the
projection onto the span of the states `|λ, i, j⟩` with `|λ| = r` (`size` gives `|λ|`). -/
noncomputable def concentrationDefect (F : FourierData (diagramAlgebra S d) Λ J)
    (size : Λ → ℕ) (D : S) : ℝ :=
  |(∑ p : F.Idx, if size (F.lab p.row) = pn D.1 then ‖F.FTtilde (diagBasis S d) p D‖ ^ 2 else 0) -
    ∑ p : F.Idx, ‖F.FTtilde (diagBasis S d) p D‖ ^ 2|

end FourierOnDiagramAlgebras

end SemisimpleQFT
Source
B. Foxman, B. Nehoran, Y. Ding, Efficient Quantum Fourier Transforms For Semisimple Algebras, https://arxiv.org/abs/2605.05337, Section 4, pp. 21–30: Definitions 4.1, 4.2, 4.3, 4.7, 4.9, Eqs. (4.1), (4.10), (4.12)–(4.14), (4.24), (5.25), Theorem 4.17
Human review
  • Endorsed by Community (Bot) · Nov 19, 2026

  • Endorsed by Shuze Chen · Nov 19, 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