Bratteli diagrams, subalgebra adapted bases and the orthogonal form for the chains of , ,
DefinitionSemisimpleQFT_ChainsYoung diagrams. Shape N is the set of Young diagrams with at most rows of length at most , given by their weakly decreasing row lengths ; it contains every Young diagram with at most boxes. size is , and AddBox μ ν says ( for all and ). pairSize (λ, μ) .
Bratteli diagrams and paths (pp. 34). A Bratteli V has a set vert t of vertices at each level and edges edge t μ ν between a level- vertex and a level- vertex . Path t is the set of paths with at level and consecutive entries joined; last is , trunc drops the last entry (Eq. (5.22)), and Vtx t is the set of level- vertices.
Subalgebra adapted systems (Sections 5.2–5.3). For subalgebras (alg t) of an algebra and a Bratteli diagram , a GTSystem m alg B consists of, for every , a Fourier isomorphism of (a FourierData) whose irreps are the level- vertices and whose basis indices are the Bratteli paths of length , the irrep of a path being its endpoint; and it satisfies Eqs. (5.7)–(5.8): for , and paths of length with the same endpoint , if the truncations end at the same vertex , and otherwise. top is the Fourier isomorphism of .
For a chain of diagram algebras, IsStandard G size says that the Fourier basis of the top algebra is in the orthogonal form (, Eq. (5.25)) and that its labelling satisfies Theorem 4.17 ( when ).
The three chains (Eqs. (5.23), (5.24)). All algebras of a chain are spanned by diagrams with columns; an algebra on fewer columns is embedded by adding vertical strands (HasStrand j D: is a block).
partitionLevel n t, : level is (strands in columns ), level is (in addition and are in the same block).partitionBratteli n: the vertices at level are the with ; from an even level to the next the shape stays or loses a box, from an odd level to the next it stays or gains a box (Eqs. (4.5), (4.6), (5.2), (5.3)).brauerLevel n t, : , Brauer diagrams with strands in columns .brauerBratteli n: vertices with , ; edges add or remove one box (Eqs. (4.7), (5.4)).walledLevel r n t, (for ): withwalledSizes r tfor and afterwards — the chain — realised by the walled Brauer diagrams with strands in the left columns and the right columns .walledBratteli r n: vertices with , ; when a left column is added, at the lower level is joined to iff or ; when a right column is added, iff or (Eqs. (4.8), (5.5), (5.6)).
import Definitions.Def_SemisimpleQFT_Diagram
/-!
# Bratteli diagrams, subalgebra adapted bases and the orthogonal form for diagram algebras
Source: B. Foxman, B. Nehoran, Y. Ding, *Efficient Quantum Fourier Transforms For Semisimple
Algebras*, Sections 4.3 and 5 (PDF pp. 24–25, 30–35).
Conventions:
* A Young diagram with at most `N` boxes is stored by its row lengths
`λ_1 ≥ λ_2 ≥ … ≥ λ_N ≥ 0`, each at most `N` (`Shape N`).
* A chain `ℂ = A_0 ⊆ A_1 ⊆ … ⊆ A_m = A` (Eq. (5.20)) of diagram algebras is given by the
diagram sets `level t` of its members, all inside the diagrams with `n` columns: a smaller
algebra on fewer columns is embedded by adding vertical strands `{j, j'}` in the remaining
columns.
* A Bratteli diagram (PDF p. 34) is given by its vertices at each level (the irrep labels of
`A_t`) and its edges between consecutive levels (the branching rule of Theorem 5.2). The basis
of the irrep space `V^ρ` of `A_t` is indexed by the Bratteli paths from the root to `ρ`
(Eq. (5.21)).
-/
set_option warn.classDefReducibility false
namespace SemisimpleQFT
open scoped BigOperators ComplexConjugate
/-- PDF p. 24: a Young diagram with at most `N` rows, each of length at most `N`, given by its
weakly decreasing row lengths `λ_1 ≥ … ≥ λ_N` (`λ.1 i` is the length of row `i + 1`). Every
Young diagram with at most `N` boxes is of this form. -/
abbrev Shape (N : ℕ) := {f : Fin N → Fin (N + 1) // ∀ i j : Fin N, i ≤ j → f j ≤ f i}
/-- PDF p. 24: `|λ|`, the total number of boxes. -/
def Shape.size {N : ℕ} (s : Shape N) : ℕ := ∑ i : Fin N, (s.1 i : ℕ)
/-- Theorem 5.2 (PDF p. 31): `ν = μ + □`, i.e. `ν` is obtained from `μ` by adding one box. -/
def AddBox {N : ℕ} (μ ν : Shape N) : Prop :=
(∀ i : Fin N, μ.1 i ≤ ν.1 i) ∧ ν.size = μ.size + 1
/-- PDF p. 34: a Bratteli diagram with vertex labels in `V`: `vert t` is the set of vertices at
level `t` (the irreps of `A_t`), and `edge t μ ν` says that the level-`t` vertex `μ` is joined
to the level-`(t+1)` vertex `ν` (i.e. `μ ∈ Res(ν)`). -/
structure Bratteli (V : Type) where
/-- The vertices at each level. -/
vert : ℕ → V → Prop
/-- The edges from level `t` to level `t + 1`. -/
edge : ℕ → V → V → Prop
namespace Bratteli
variable {V : Type}
/-- PDF p. 34, Eq. (5.21): a Bratteli path `(ρ_0, ρ_1, …, ρ_t)`: `ρ_i` is a vertex at level `i`
and consecutive entries are joined by an edge. -/
def Path (B : Bratteli V) (t : ℕ) : Type :=
{p : Fin (t + 1) → V //
(∀ i : Fin (t + 1), B.vert i.val (p i)) ∧
(∀ i : Fin t, B.edge i.val (p i.castSucc) (p i.succ))}
instance (B : Bratteli V) (t : ℕ) [Finite V] : Finite (B.Path t) :=
inferInstanceAs (Finite {q : Fin (t + 1) → V //
(∀ i : Fin (t + 1), B.vert i.val (q i)) ∧
(∀ i : Fin t, B.edge i.val (q i.castSucc) (q i.succ))})
noncomputable instance (B : Bratteli V) (t : ℕ) [Finite V] : Fintype (B.Path t) :=
Fintype.ofFinite _
noncomputable instance (B : Bratteli V) (t : ℕ) : DecidableEq (B.Path t) := Classical.decEq _
/-- The entry `ρ_i = P(i)` of a path. -/
def Path.at {B : Bratteli V} {t : ℕ} (p : B.Path t) (i : Fin (t + 1)) : V := Subtype.val p i
/-- The endpoint `ρ_t` of a path, the irrep whose basis vector it indexes. -/
def Path.last {B : Bratteli V} {t : ℕ} (p : B.Path t) : V := Subtype.val p (Fin.last t)
/-- PDF p. 34, Eq. (5.22): the truncated path `P_{≤ t} = (ρ_0, …, ρ_t)` of a path of length
`t + 1`. -/
def Path.trunc {B : Bratteli V} {t : ℕ} (p : B.Path (t + 1)) : B.Path t :=
⟨fun i => Subtype.val p i.castSucc,
fun i => (Subtype.property p).1 i.castSucc,
fun i => (Subtype.property p).2 i.castSucc⟩
/-- The vertices at level `t`, as a type: the irrep labels of `A_t`. -/
def Vtx (B : Bratteli V) (t : ℕ) : Type := {v : V // B.vert t v}
end Bratteli
/-- Sections 5.2–5.3 (PDF pp. 32–34): a subalgebra adapted (Gelfand–Tsetlin) system of Fourier
bases for a chain `A_0 ⊆ A_1 ⊆ … ⊆ A_m` (`A_t = alg t`) of subalgebras of `R`, with respect to
a Bratteli diagram `B`.
* For each level `t ≤ m`, `F t` is a Fourier isomorphism of `A_t` whose irreps are labelled by
the level-`t` vertices of `B` and whose basis of the irrep space `V^ρ` is indexed by the
Bratteli paths ending at `ρ` (`lab_eq`).
* `adapted` is Eqs. (5.7)–(5.8) for the multiplicity-free branching given by the edges of `B`:
for `b ∈ A_t` and paths `P, Q` to the same irrep `ρ` of `A_{t+1}`, the entry `ρ(b)_{P,Q}` is
`σ(b)_{P_{≤t}, Q_{≤t}}` if the truncations of `P` and `Q` end at the same irrep `σ` of `A_t`,
and `0` otherwise. -/
structure GTSystem {R : Type*} [Ring R] [Algebra ℂ R] (m : ℕ) (alg : ℕ → Subalgebra ℂ R)
{V : Type} [Finite V] (B : Bratteli V) where
/-- The Fourier isomorphism of `A_t`, with basis indexed by Bratteli paths. -/
F : (t : ℕ) → t ≤ m → FourierData (alg t) (B.Vtx t) (B.Path t)
/-- The irrep of a path is its endpoint. -/
lab_eq : ∀ (t : ℕ) (ht : t ≤ m) (p : B.Path t), ((F t ht).lab p).1 = p.last
/-- Eqs. (5.7)–(5.8): the basis of `A_{t+1}` is `A_t`-adapted. -/
adapted : ∀ (t : ℕ) (ht : t + 1 ≤ m) (x : R) (hx : x ∈ alg t) (hx' : x ∈ alg (t + 1))
(p q : B.Path (t + 1)), p.last = q.last →
(p.trunc.last = q.trunc.last →
(F (t + 1) ht).rep ⟨x, hx'⟩ p q =
(F t (Nat.le_of_succ_le ht)).rep ⟨x, hx⟩ p.trunc q.trunc) ∧
(p.trunc.last ≠ q.trunc.last → (F (t + 1) ht).rep ⟨x, hx'⟩ p q = 0)
namespace GTSystem
variable {n : ℕ} {m : ℕ} {level : ℕ → Set (Diagram n)} {d : ℕ} {V : Type} [Finite V]
{B : Bratteli V}
/-- The Fourier isomorphism of the top algebra `A = A_m` of the chain. -/
def top {R : Type*} [Ring R] [Algebra ℂ R] {alg : ℕ → Subalgebra ℂ R}
(G : GTSystem m alg B) : FourierData (alg m) (B.Vtx m) (B.Path m) :=
G.F m le_rfl
/-- Sections 5.3–5.4 (PDF pp. 33–35): the subalgebra adapted system is in the orthogonal form
at the top algebra `A_m` (`ρ(D^{op}) = ρ(D)†`, Eq. (5.25)) and its labelling of the irreps of
`A_m` by Young diagrams satisfies Theorem 4.17 (`λ(D) = 0` whenever `pn(D) < |λ|`), `size`
being the number of boxes `|·|` of a label. -/
def IsStandard (G : GTSystem m (fun t => diagramAlgebra (level t) d) B) (size : V → ℕ) : Prop :=
IsOrthogonalForm (S := level m) (d := d) G.top ∧
IsVanishing (S := level m) (d := d) G.top (fun v => size v.1)
end GTSystem
variable {n : ℕ}
/-- The column `j` is a vertical strand of `D`: `{j, j'}` is a block of `D`. -/
def HasStrand (j : Fin n) (D : Diagram n) : Prop :=
∀ u : Vertex n, D (false, j) u ↔ (u = (false, j) ∨ u = (true, j))
/-- PDF p. 34, Eq. (5.23): the chain
`ℂ ≅ P_0(d) ⊆ P_{1/2}(d) ⊆ P_1(d) ⊆ … ⊆ P_{n-1/2}(d) ⊆ P_n(d)` inside the diagrams with `n`
columns. Level `t = 2k` is `P_k(d)`: the diagrams with vertical strands in the columns
`k+1, …, n`. Level `t = 2k - 1` is `P_{k-1/2}(d)`: those diagrams of `P_k(d)` in which `k` and
`k'` are in the same block. -/
def partitionLevel (n t : ℕ) : Set (Diagram n) :=
{D | (∀ j : Fin n, (t + 1) / 2 ≤ j.val → HasStrand j D) ∧
(t % 2 = 1 → ∀ j : Fin n, j.val + 1 = (t + 1) / 2 → D (false, j) (true, j))}
/-- Theorems 4.12, 4.13 and 5.2 (PDF pp. 25, 31, Eqs. (4.5), (4.6), (5.2), (5.3)): the Bratteli
diagram of the chain `partitionLevel`. The irreps of `P_k(d)` (level `2k`) are the `λ` with
`|λ| ≤ k`, those of `P_{k-1/2}(d)` (level `2k - 1`) the `λ` with `|λ| ≤ k - 1`. From an even
level to the next (`P_k ⊆ P_{k+1/2}`) the shape stays or loses a box; from an odd level to the
next (`P_{k-1/2} ⊆ P_k`) it stays or gains a box. -/
def partitionBratteli (n : ℕ) : Bratteli (Shape n) where
vert t s := s.size ≤ t / 2
edge t μ ν := if t % 2 = 0 then (ν = μ ∨ AddBox ν μ) else (ν = μ ∨ AddBox μ ν)
/-- PDF p. 34, Eq. (5.23): the chain `ℂ ≅ B_0(d) ⊆ B_1(d) ⊆ … ⊆ B_n(d)` inside the diagrams
with `n` columns: level `t` is `B_t(d)`, the Brauer diagrams with vertical strands in the
columns `t+1, …, n`. -/
def brauerLevel (n t : ℕ) : Set (Diagram n) :=
{D | IsBrauer D ∧ ∀ j : Fin n, t ≤ j.val → HasStrand j D}
/-- Theorems 4.14 and 5.2 (PDF pp. 25, 31, Eqs. (4.7), (5.4)): the Bratteli diagram of the chain
`brauerLevel`: the irreps of `B_t(d)` are the `λ` with `|λ| ≤ t` and `|λ| ≡ t mod 2`, and at
each step the shape gains or loses one box. -/
def brauerBratteli (n : ℕ) : Bratteli (Shape n) where
vert t s := s.size ≤ t ∧ s.size % 2 = t % 2
edge _ μ ν := AddBox μ ν ∨ AddBox ν μ
/-- PDF p. 35, Eq. (5.24): the member `B_{a,b}(d)` at level `t` of the chain
`B_{0,0} ⊆ B_{1,0} ⊆ B_{1,1} ⊆ … ⊆ B_{r,r} ⊆ B_{r,r+1} ⊆ … ⊆ B_{r,s}` (for `r ≤ s`):
`(a, b) = (⌈t/2⌉, ⌊t/2⌋)` for `t ≤ 2r`, and `(a, b) = (r, t - r)` afterwards. -/
def walledSizes (r t : ℕ) : ℕ × ℕ :=
if t ≤ 2 * r then ((t + 1) / 2, t / 2) else (r, t - r)
/-- PDF p. 35, Eq. (5.24): the chain of walled Brauer algebras inside the walled Brauer diagrams
with `n` columns and the wall after column `r`. Level `t` is `B_{a,b}(d)` with
`(a, b) = walledSizes r t`: the walled Brauer diagrams with vertical strands in the left columns
`a+1, …, r` and in the right columns `r+b+1, …, n`. -/
def walledLevel (r n t : ℕ) : Set (Diagram n) :=
{D | IsWalled r D ∧ ∀ j : Fin n,
(((walledSizes r t).1 ≤ j.val ∧ j.val < r) ∨ r + (walledSizes r t).2 ≤ j.val) →
HasStrand j D}
/-- Theorems 4.15 and 5.2 (PDF pp. 25, 31, Eqs. (4.8), (5.5), (5.6)): the Bratteli diagram of the
chain `walledLevel`. The irreps of `B_{a,b}(d)` are the pairs `(λ, μ)` with `|λ| = a - k`,
`|μ| = b - k` for some `0 ≤ k ≤ min(a, b)`. When a left column is added
(`B_{a-1,b} ⊆ B_{a,b}`), the smaller pair `(λ', μ')` is joined to `(λ, μ)` if
`λ' = λ - □, μ' = μ` or `λ' = λ, μ' = μ + □`; when a right column is added
(`B_{a,b-1} ⊆ B_{a,b}`), if `λ' = λ + □, μ' = μ` or `λ' = λ, μ' = μ - □`. -/
def walledBratteli (r n : ℕ) : Bratteli (Shape n × Shape n) where
vert t v := v.1.size ≤ (walledSizes r t).1 ∧ v.2.size ≤ (walledSizes r t).2 ∧
(walledSizes r t).1 - v.1.size = (walledSizes r t).2 - v.2.size
edge t v w :=
if (walledSizes r (t + 1)).1 = (walledSizes r t).1 + 1 then
(AddBox v.1 w.1 ∧ v.2 = w.2) ∨ (v.1 = w.1 ∧ AddBox w.2 v.2)
else
(AddBox w.1 v.1 ∧ v.2 = w.2) ∨ (v.1 = w.1 ∧ AddBox v.2 w.2)
/-- PDF p. 25: `|(λ, μ)| = |λ| + |μ|`. -/
def pairSize {N : ℕ} (v : Shape N × Shape N) : ℕ := v.1.size + v.2.size
end SemisimpleQFT
Confirmed by the mission captain (proposal self-audit).