Partition diagrams, the diagram algebras , , , and the Schur representation
DefinitionSemisimpleQFT_DiagramDiagrams (Definitions 4.1, 4.2). A partition diagram with columns is a set partition of the vertices , encoded as an equivalence relation on Vertex n = Bool × Fin n: (false, i) is the top vertex and (true, i) is the bottom vertex . cc D is the number of blocks of ; 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 on rows and on rows (bottom row of identified with top row of ). comp D₁ D₂ is its restriction to rows and , and loops D₁ D₂ is the number of components lying entirely in the middle row, so that in . one n is the identity diagram (blocks ), op D exchanges the two rows, and join D E is , the finest partition coarsening both.
Diagram algebras. The parameter is a natural number. leftMul d D is the matrix, on the space with basis all diagrams, of left multiplication by : the column of is times the basis vector . For a set of diagrams, diagramAlgebra S d is the subalgebra of matrices generated by : the diagram algebra spanned by , realised by its left regular representation. The coefficient of the diagram in an element is the matrix entry . diag S d D is the diagram as an element of the algebra.
The diagram sets are: partitionSet n (all diagrams, ); halfSet n ( and in the same block, ); brauerSet n (every block has exactly two vertices, ); walledSet r n (Brauer diagrams in which a block lying on one side of the wall after column joins the two rows and a block crossing the wall lies in one row, ). IsStdFamily n d S says that is one of these four sets and is in the corresponding range of Theorems 4.12–4.15: for and (with for the latter), for , for .
Computational basis (Eq. (4.10)). scale d D is the real number . diagBasis S d is the scaled diagram basis : its vectors are and the coordinate of along is .
Schur representation (Eqs. (4.12)–(4.14)). schurDiagram d D is the matrix on with exactly when labelling the top row by and the bottom row by is constant on every block of . schur d x and schurInner d x y .
Properties of a Fourier basis of a diagram algebra. For a FourierData of diagramAlgebra S d:
IsOrthogonalForm F(Eq. (5.25)): for every with and every irrep .IsVanishing F size(Theorem 4.17, withsizeon labels): whenever and .schurMult F iis the multiplicity of the irrep of the index in the Schur representation, computed as .concentrationDefect F size Dis of Eq. (4.24), where for the scaled diagram of , and projects onto the states with .
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
Confirmed by the mission captain (proposal self-audit).