Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Definitions for Affine and degenerate affine BMW algebras: The center

Definition
QAlgorithms_Papers_Independent_Intakenext100_P34

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

prove2quantum

The objects the formalized statements of Affine and degenerate affine BMW algebras: The center (arXiv:1105.4207) are stated in. Each was checked against the paper by a blind read-back and a moderator.

  • Adj: Valid adjacent-generator positions; this is empty at level one.
  • adjacentLeft: Left endpoint of a valid adjacent pair, in zero-based coordinates.
  • adjacentRight: Right endpoint of a valid adjacent pair.
  • trans: The source's adjacent transposition.
  • DLetter: Letters of (2.1); false/true label kappa_0/kappa_1.
  • DFree: Free algebra before imposing (2.2)--(2.5).
  • dt: Permutation letter in the free algebra.
  • dk: Kappa letter in the free algebra.
  • dy: Commuting-variable letter before the quotient.
  • dg: Adjacent gamma as defined in (2.5).
  • DRel: Exactly (2.2)--(2.5); the permutation identity represents the algebra unit.
  • DBraid: The unspecialized degenerate affine braid algebra of Section 2.1.
  • dbMap: Its canonical quotient homomorphism.
  • GIndex: Indices 0,...,k, with none representing 0 and some j representing j+1.
  • GLetter: Letters of the alternative presentation (2.8), with distinct gamma endpoints.
  • GFree: Free algebra for the alternate presentation.
  • gt: Permutation generator in the alternate presentation.
  • gk: Kappa generator in the alternate presentation.
  • gg: Gamma generator; the diagonal value is unused in every relation.
  • gAction: Permutations fix index zero.
  • GRel: Precisely the relations (2.9)--(2.11).
  • GBraid: The algebra defined by the second presentation, with no scalar kappa specialization.
  • gbMap: Its canonical quotient map.
  • gY: The generator change y_j=kappa_j/2+sum_(0≤l<j) gamma_(l,j), (2.16).
  • de: The source's e_i, defined by (2.21), before the BMW quotient.
  • DParams: Parameter data, including the implicit invertibility of 2. No admissibility assumed.
  • DWRel: All BMW relations (2.23)--(2.24), optionally specializing the two kappas.
  • DW: The actual degenerate affine BMW algebra, including the chosen scalar specialization.
  • dwMap: Canonical map into the presented algebra.
  • ps: Constant series in a possibly noncommutative coefficient algebra.
  • geometric: Geometric series (1-a u⁻¹)⁻¹, with its coefficients specified directly.
  • infinityResolvent: The formal resolvent (u-a)⁻¹.
  • halfResolvent: The formal series (2u-a)⁻¹ when h represents 1/2.
  • DAdmissible: The admissibility identity (4.5), multiplied by u⁻² and written in X=u⁻¹.
  • DCancel: Formal substitution for the additive cancellation test, with no test at level one.
  • dEval: Canonical evaluation in the commuting y-generators, ordered by variable index.
  • DCenterDescription: Equality of the center with the canonically evaluated cancellation ring.
  • dRatio: The rational factor in (3.8), expanded at infinity using its unit constant denominator.
  • dRatioProduct: Ordered product of the (3.8) factors for a finite family of commuting variables.
  • seriesTail: Removing the constant coefficient shifts Xⁿ⁺¹ to Xⁿ, hence multiplies by u.
  • dMomentPolynomial: Constructive compression representatives: coefficients of (z_0(u)+epsilonu-1/2) product R(y_j,u)-epsilonu+1/2. The cancelled principal part is implemented by seriesTail(product-1). These are polynomials, not arbitrary representatives of a compression equation.
  • dMomentAt: Canonical representative evaluated in a larger level by the initial-variable inclusion.
  • dMomentSeries: The positive or sign-reversed representative generating series at a specified level.
  • AParams: Unit parameters and all integer-indexed moments from Section 2.4. The zeroth moment is supplied as parameter data, even when E_1 vanishes.
  • ALetter: Group generators and their inverse letters; false/true means generator/inverse.
  • AFree: Free algebra used to present the affine braid group algebra and its BMW quotient.
  • aCrossing: A crossing or inverse crossing.
  • ax: The flagpole group generator or its inverse.
  • affineYWord: Y_j and Y_j⁻¹ from (2.38)--(2.39), constructed without any arbitrary inverse.
  • affineContractionWord: E_i=1-(T_i-T_i⁻¹)/Q, (2.45).
  • signedPow: Integer powers represented using an element and its specified inverse.
  • AWRel: Exactly the group presentation (2.33)--(2.36) and quotient (2.42)--(2.43). All signs and both sides of each two-sided relation are retained.
  • AW: The unrestricted affine BMW algebra; there is no cyclotomic polynomial relation.
  • awMap: The canonical quotient map.
  • multiplicativeResolvent: Y/(u-Y), expanded at infinity.
  • pairResolvent: Y_i Y_(i+1)/(u²-Y_i Y_(i+1)), expanded at infinity.
  • AAdmissible: The scalar admissibility condition (4.20); u²/(u²-1)=1+g.
  • Laurent: Laurent polynomials with integer exponent vectors and finite support.
  • aEval: Canonical Laurent evaluation using the actual Y_j and their constructed inverses.
  • laurentVariable: A Laurent variable, or its inverse, as a finite exponent-vector monomial.
  • aRatio: The factor of (3.27) after division by its leading u⁴ coefficient.
  • aScalarFraction: The normalized numerator (u²-q²)(u²-q⁻²)/(u²-1)² in (3.26).
  • aShiftedPositive: The shifted positive series Z_n^++z⁻¹/Q-u²/(u²-1), constructed by (3.28).
  • aMomentPolynomial: Explicit integer-moment representatives as Laurent polynomials. At n=0 the supplied bilateral scalar sequence is retained. At higher n, positive moments come from (3.28) and negative ones from (3.26), using the unit constant z/Q of its positive factor. No E_i is cancelled.
  • aMomentAt: Canonical evaluation of the n-variable representative at a larger level.
  • aMomentSeries: The two series both use u⁻ˡ as degree; only the moment index changes sign.
  • ACancel: Permutation invariance of Laurent coefficients and the formal reciprocal-pair test. The substitutions send (d_1,d_2,...) to (d_1-d_2,0,...) or (0,0,...).
  • ACenterDescription: Center equality in the actual affine quotient via its canonical Laurent embedding.
  • leftMultiples: Principal left ideal as the actual set of left multiples.
  • CyclotomicIntegers: The actual ring Z[zeta] inside the complex numbers.
  • CyclotomicField: The actual field Q(zeta) inside the complex numbers.
  • integralRoot: The distinguished root as an element of its integer coefficient ring.
  • Wheel: The r-variable root-of-unity wheel condition, as a formal polynomial identity.
  • coefficientPowerSum: The integral power sum from the frozen library, extended along the canonical integer map.
Definition code
import Mathlib
import Definitions.Def_QAlgorithms_Papers_Independent_Support21_P08
import Definitions.Def_QAlgorithms_Papers_Independent_Support21_P12

/-!
Statements from Daugherty--Ram--Virk, arXiv:1105.4207v2.
Indices in Fin k are the source's indices 1,...,k shifted down by one.
All presentations below are actual quotients of free algebras. No basis,
centrality, admissibility, or tower injectivity is included in a presentation.
The formal variable X in PowerSeries is u⁻¹, never a numerical specialization.
-/

namespace QAlgorithms.Papers.Independent.Intakenext100.P34

open QAlgorithms.Papers.Independent.Support21.P08 (Central)

noncomputable section

universe u

variable (C : Type u) [CommRing C]

/-- Valid adjacent-generator positions; this is empty at level one. -/
abbrev Adj (k : ℕ) := Fin (k - 1)

/-- Left endpoint of a valid adjacent pair, in zero-based coordinates. -/
def adjacentLeft {k : ℕ} (i : Adj k) : Fin k := ⟨i.val, by have := i.isLt; omega⟩

/-- Right endpoint of a valid adjacent pair. -/
def adjacentRight {k : ℕ} (i : Adj k) : Fin k := ⟨i.val + 1, by have := i.isLt; omega⟩

/-- The source's adjacent transposition. -/
def trans {k : ℕ} (i : Adj k) : Equiv.Perm (Fin k) := Equiv.swap (adjacentLeft i) (adjacentRight i)

/-- Letters of (2.1); false/true label kappa_0/kappa_1. -/
inductive DLetter (k : ℕ)
| perm : Equiv.Perm (Fin k) → DLetter k
| kappa : Bool → DLetter k
| y : Fin k → DLetter k

/-- Free algebra before imposing (2.2)--(2.5). -/
abbrev DFree (k : ℕ) := FreeAlgebra C (DLetter k)

/-- Permutation letter in the free algebra. -/
def dt {k : ℕ} (w : Equiv.Perm (Fin k)) : DFree C k := FreeAlgebra.ι C (.perm w)

/-- Kappa letter in the free algebra. -/
def dk {k : ℕ} (b : Bool) : DFree C k := FreeAlgebra.ι C (.kappa b)

/-- Commuting-variable letter before the quotient. -/
def dy {k : ℕ} (j : Fin k) : DFree C k := FreeAlgebra.ι C (.y j)

/-- Adjacent gamma as defined in (2.5). -/
def dg {k : ℕ} (i : Adj k) : DFree C k :=
  dy C (adjacentRight i) - dt C (trans i) * dy C (adjacentLeft i) * dt C (trans i)

/-- Exactly (2.2)--(2.5); the permutation identity represents the algebra unit. -/
inductive DRel (k : ℕ) : DFree C k → DFree C k → Prop
| identity : DRel k (dt C (1 : Equiv.Perm (Fin k))) 1
| perm (w v) : DRel k (dt C w * dt C v) (dt C (w * v))
| yy (i j) : DRel k (dy C i * dy C j) (dy C j * dy C i)
| kappas : DRel k (dk C false * dk C true) (dk C true * dk C false)
| kappay (b j) : DRel k (dk C b * dy C j) (dy C j * dk C b)
| kappa0t (i : Adj k) :
    DRel k (dk C false * dt C (trans i)) (dt C (trans i) * dk C false)
| kappa1first (i : Adj k) (h : i.val = 0) :
    DRel k (dk C true * dt C (trans i) * dk C true * dt C (trans i))
      (dt C (trans i) * dk C true * dt C (trans i) * dk C true)
| kappa1other (i : Adj k) (h : i.val ≠ 0) :
    DRel k (dk C true * dt C (trans i)) (dt C (trans i) * dk C true)
| sum (i : Adj k) :
    DRel k (dt C (trans i) * (dy C (adjacentLeft i) + dy C (adjacentRight i)))
      ((dy C (adjacentLeft i) + dy C (adjacentRight i)) * dt C (trans i))
| distant (i : Adj k) (j : Fin k) (h1 : j ≠ adjacentLeft i) (h2 : j ≠ adjacentRight i) :
    DRel k (dy C j * dt C (trans i)) (dt C (trans i) * dy C j)
| gamma (i j : Adj k) (h : j.val = i.val + 1) :
    DRel k (dt C (trans i) * dt C (trans j) * dg C i * dt C (trans j) * dt C (trans i))
      (dg C j)

/-- The unspecialized degenerate affine braid algebra of Section 2.1. -/
abbrev DBraid (k : ℕ) := RingQuot (DRel C k)

/-- Its canonical quotient homomorphism. -/
def dbMap (k : ℕ) : DFree C k →ₐ[C] DBraid C k := RingQuot.mkAlgHom C (DRel C k)

/-- Indices 0,...,k, with none representing 0 and some j representing j+1. -/
abbrev GIndex (k : ℕ) := Option (Fin k)

/-- Letters of the alternative presentation (2.8), with distinct gamma endpoints. -/
inductive GLetter (k : ℕ)
| perm : Equiv.Perm (Fin k) → GLetter k
| kappa : GIndex k → GLetter k
| gamma : {p : GIndex k × GIndex k // p.1 ≠ p.2} → GLetter k

/-- Free algebra for the alternate presentation. -/
abbrev GFree (k : ℕ) := FreeAlgebra C (GLetter k)

/-- Permutation generator in the alternate presentation. -/
def gt {k : ℕ} (w : Equiv.Perm (Fin k)) : GFree C k := FreeAlgebra.ι C (.perm w)

/-- Kappa generator in the alternate presentation. -/
def gk {k : ℕ} (j : GIndex k) : GFree C k := FreeAlgebra.ι C (.kappa j)

/-- Gamma generator; the diagonal value is unused in every relation. -/
def gg {k : ℕ} (i j : GIndex k) : GFree C k :=
  if h : i ≠ j then FreeAlgebra.ι C (.gamma ⟨(i,j),h⟩) else 0

/-- Permutations fix index zero. -/
def gAction {k : ℕ} (w : Equiv.Perm (Fin k)) : GIndex k → GIndex k := Option.map w

/-- Precisely the relations (2.9)--(2.11). -/
inductive GRel (k : ℕ) : GFree C k → GFree C k → Prop
| identity : GRel k (gt C (1 : Equiv.Perm (Fin k))) 1
| perm (w v) : GRel k (gt C w * gt C v) (gt C (w*v))
| conjugateKappa (w) (i : GIndex k) :
    GRel k (gt C w * gk C i * gt C w⁻¹) (gk C (gAction w i))
| conjugateGamma (w) (i j : GIndex k) (h : i ≠ j) :
    GRel k (gt C w * gg C i j * gt C w⁻¹) (gg C (gAction w i) (gAction w j))
| kappas (i j : GIndex k) : GRel k (gk C i * gk C j) (gk C j * gk C i)
| kappaGamma (i l m : GIndex k) (h : l ≠ m) :
    GRel k (gk C i * gg C l m) (gg C l m * gk C i)
| symmetry (i j : GIndex k) (h : i ≠ j) : GRel k (gg C i j) (gg C j i)
| disjoint (p r l m : GIndex k) (hpr : p ≠ r) (hlm : l ≠ m)
    (hpl : p ≠ l) (hpm : p ≠ m) (hrl : r ≠ l) (hrm : r ≠ m) :
    GRel k (gg C p r * gg C l m) (gg C l m * gg C p r)
| triangle (i j r : GIndex k) (hij : i ≠ j) (hir : i ≠ r) (hjr : j ≠ r) :
    GRel k (gg C i j * (gg C i r + gg C j r))
      ((gg C i r + gg C j r) * gg C i j)

/-- The algebra defined by the second presentation, with no scalar kappa specialization. -/
abbrev GBraid (k : ℕ) := RingQuot (GRel C k)

/-- Its canonical quotient map. -/
def gbMap (k : ℕ) : GFree C k →ₐ[C] GBraid C k := RingQuot.mkAlgHom C (GRel C k)

/-- The generator change y_j=kappa_j/2+sum_(0≤l<j) gamma_(l,j), (2.16). -/
def gY (k : ℕ) (half : C) (j : Fin k) : GFree C k :=
  algebraMap C (GFree C k) half*gk C (some j) + gg C none (some j) +
    ∑ l : Fin k, if l.val < j.val then gg C (some l) (some j) else 0

example (half : C) : gY C 1 half (0 : Fin 1) =
    algebraMap C (GFree C 1) half*gk C (some 0) + gg C none (some 0) := by
  simp [gY]

/-- The source's e_i, defined by (2.21), before the BMW quotient. -/
def de {k : ℕ} (i : Adj k) : DFree C k :=
  1 + dt C (trans i) * dy C (adjacentLeft i) - dy C (adjacentRight i) * dt C (trans i)

/-- Parameter data, including the implicit invertibility of 2. No admissibility assumed. -/
structure DParams where
  two : Cˣ
  two_val : (two : C) = 2
  epsilon : C
  epsilon_sign : epsilon = 1 ∨ epsilon = -1
  moment : ℕ → C
  scalarKappa : Option (C × C)

/-- All BMW relations (2.23)--(2.24), optionally specializing the two kappas. -/
inductive DWRel (P : DParams C) (k : ℕ) : DFree C k → DFree C k → Prop
| braid {a b} (h : DRel C k a b) : DWRel P k a b
| et (i : Adj k) : DWRel P k (de C i * dt C (trans i))
    (algebraMap C (DFree C k) P.epsilon * de C i)
| te (i : Adj k) : DWRel P k (dt C (trans i) * de C i)
    (algebraMap C (DFree C k) P.epsilon * de C i)
| neighbor (i j : Adj k) (h : i.val + 1 = j.val ∨ j.val + 1 = i.val) :
    DWRel P k (de C i * dt C (trans j) * de C i)
      (algebraMap C (DFree C k) P.epsilon * de C i)
| compression (i : Adj k) (h : i.val = 0) (n : ℕ) :
    DWRel P k (de C i * dy C (adjacentLeft i) ^ n * de C i)
      (algebraMap C (DFree C k) (P.moment n) * de C i)
| killLeft (i : Adj k) : DWRel P k (de C i * (dy C (adjacentLeft i) + dy C (adjacentRight i))) 0
| killRight (i : Adj k) : DWRel P k ((dy C (adjacentLeft i) + dy C (adjacentRight i)) * de C i) 0
| scalar0 (a b : C) (h : P.scalarKappa = some (a,b)) :
    DWRel P k (dk C false) (algebraMap C (DFree C k) a)
| scalar1 (a b : C) (h : P.scalarKappa = some (a,b)) :
    DWRel P k (dk C true) (algebraMap C (DFree C k) b)

/-- The actual degenerate affine BMW algebra, including the chosen scalar specialization. -/
abbrev DW (P : DParams C) (k : ℕ) := RingQuot (DWRel C P k)

/-- Canonical map into the presented algebra. -/
def dwMap (P : DParams C) (k : ℕ) : DFree C k →ₐ[C] DW C P k :=
  RingQuot.mkAlgHom C (DWRel C P k)

/-- Constant series in a possibly noncommutative coefficient algebra. -/
abbrev ps {A : Type*} [Semiring A] (a : A) : PowerSeries A := PowerSeries.C a

/-- Geometric series (1-a u⁻¹)⁻¹, with its coefficients specified directly. -/
def geometric {A : Type*} [Semiring A] (a : A) : PowerSeries A := PowerSeries.mk (fun n => a ^ n)

/-- The formal resolvent (u-a)⁻¹. -/
def infinityResolvent {A : Type*} [Semiring A] (a : A) : PowerSeries A := PowerSeries.X * geometric a

/-- The formal series (2u-a)⁻¹ when h represents 1/2. -/
def halfResolvent {A : Type*} [Semiring A] (h a : A) : PowerSeries A :=
  ps h * PowerSeries.X * geometric (h * a)

example {A : Type*} [Semiring A] (a : A) : PowerSeries.coeff 0 (geometric a) = 1 := by
  simp [geometric]

example {A : Type*} [Semiring A] (a : A) : PowerSeries.coeff 0 (infinityResolvent a) = 0 := by
  simp [infinityResolvent]

/-- The admissibility identity (4.5), multiplied by u⁻² and written in X=u⁻¹. -/
def DAdmissible (P : DParams C) : Prop :=
  let h : C := ↑P.two⁻¹
  let z := PowerSeries.mk P.moment
  let zm := PowerSeries.mk (fun n => (-1 : C)^n * P.moment n)
  (PowerSeries.X*zm-ps h*PowerSeries.X-ps P.epsilon) *
    (PowerSeries.X*z-ps h*PowerSeries.X+ps P.epsilon) =
    (ps h*PowerSeries.X-ps P.epsilon)*(ps h*PowerSeries.X+ps P.epsilon)

/-- Formal substitution for the additive cancellation test, with no test at level one. -/
def DCancel (k : ℕ) (f : MvPolynomial (Fin k) C) : Prop :=
  MvPolynomial.IsSymmetric f ∧ ∀ h : 2 ≤ k,
    let a : Fin k := ⟨0, by omega⟩
    let b : Fin k := ⟨1, by omega⟩
    MvPolynomial.eval₂ MvPolynomial.C
      (fun j => if j = a then MvPolynomial.X a else if j = b then -MvPolynomial.X a
        else MvPolynomial.X j) f =
    MvPolynomial.eval₂ MvPolynomial.C
      (fun j => if j = a ∨ j = b then 0 else MvPolynomial.X j) f

/-- Canonical evaluation in the commuting y-generators, ordered by variable index. -/
def dEval (P : DParams C) (k : ℕ) (f : MvPolynomial (Fin k) C) : DW C P k :=
  (AddMonoidAlgebra.coeff f).sum (fun d c => algebraMap C (DW C P k) c *
    (List.ofFn (fun j : Fin k => (dwMap C P k (dy C j)) ^ d j)).prod)

/-- Equality of the center with the canonically evaluated cancellation ring. -/
def DCenterDescription (P : DParams C) (k : ℕ) : Prop :=
  Function.Injective (dEval C P k) ∧
    ∀ a : DW C P k, Central a ↔ ∃ f, DCancel C k f ∧ dEval C P k f = a

/-- The rational factor in (3.8), expanded at infinity using its unit constant denominator. -/
def dRatio {A : Type*} [Ring A] (a : A) : PowerSeries A :=
  let t : PowerSeries A := PowerSeries.X
  let plus := 1+ps a*t
  let minus := 1-ps a*t
  let numerator := (plus^2-t^2)*minus^2
  let denominator := (minus^2-t^2)*plus^2
  numerator*PowerSeries.invOfUnit denominator 1

/-- Ordered product of the (3.8) factors for a finite family of commuting variables. -/
def dRatioProduct {A : Type*} [Ring A] {n : ℕ} (y : Fin n → A) : PowerSeries A :=
  (List.ofFn (fun j => dRatio (y j))).prod

/-- Removing the constant coefficient shifts Xⁿ⁺¹ to Xⁿ, hence multiplies by u. -/
def seriesTail {A : Type*} [Semiring A] (s : PowerSeries A) : PowerSeries A :=
  PowerSeries.mk (fun n => PowerSeries.coeff (n+1) s)

/-- Constructive compression representatives: coefficients of
(z_0(u)+epsilon*u-1/2) product R(y_j,u)-epsilon*u+1/2.
The cancelled principal part is implemented by seriesTail(product-1).
These are polynomials, not arbitrary representatives of a compression equation. -/
def dMomentPolynomial (P : DParams C) (n ell : ℕ) : MvPolynomial (Fin n) C :=
  let product := dRatioProduct (fun j : Fin n => (MvPolynomial.X j : MvPolynomial (Fin n) C))
  let z := PowerSeries.mk (fun m => MvPolynomial.C (P.moment m) : ℕ → MvPolynomial (Fin n) C)
  let half := MvPolynomial.C (↑P.two⁻¹ : C)
  PowerSeries.coeff ell ((z-ps half)*product+ps half+
    ps (MvPolynomial.C P.epsilon)*seriesTail (product-1))

/-- Canonical representative evaluated in a larger level by the initial-variable inclusion. -/
def dMomentAt (P : DParams C) (n level ell : ℕ) (h : n ≤ level) : DW C P level :=
  dEval C P level (MvPolynomial.rename (Fin.castLE h) (dMomentPolynomial C P n ell))

/-- The positive or sign-reversed representative generating series at a specified level. -/
def dMomentSeries (P : DParams C) (n level : ℕ) (h : n ≤ level) (negative : Bool := false) :
    PowerSeries (DW C P level) :=
  PowerSeries.mk (fun ell => (if negative then (-1 : DW C P level)^ell else 1)*
    dMomentAt C P n level ell h)

example (P : DParams C) (ell : ℕ) :
    dMomentPolynomial C P 0 ell = MvPolynomial.C (P.moment ell) := by
  simp [dMomentPolynomial, dRatioProduct, seriesTail]

/-- Unit parameters and all integer-indexed moments from Section 2.4.
The zeroth moment is supplied as parameter data, even when E_1 vanishes. -/
structure AParams where
  q : Cˣ
  z : Cˣ
  Q : Cˣ
  Q_val : (Q : C) = (q : C) - (↑q⁻¹ : C)
  moment : ℤ → C
  moment_zero : moment 0 = 1 + ((z : C) - (↑z⁻¹ : C)) * (↑Q⁻¹ : C)

/-- Group generators and their inverse letters; false/true means generator/inverse. -/
inductive ALetter (k : ℕ)
| crossing : Adj k → Bool → ALetter k
| flag : Bool → ALetter k

/-- Free algebra used to present the affine braid group algebra and its BMW quotient. -/
abbrev AFree (k : ℕ) := FreeAlgebra C (ALetter k)

/-- A crossing or inverse crossing. -/
def aCrossing {k : ℕ} (i : Adj k) (inverse : Bool := false) : AFree C k :=
  FreeAlgebra.ι C (.crossing i inverse)

/-- The flagpole group generator or its inverse. -/
def ax {k : ℕ} (inverse : Bool := false) : AFree C k := FreeAlgebra.ι C (.flag inverse)

/-- Y_j and Y_j⁻¹ from (2.38)--(2.39), constructed without any arbitrary inverse. -/
def affineYWord (P : AParams C) {k : ℕ} (j : Fin k) (inverse : Bool := false) : AFree C k :=
  let word := List.ofFn (fun i : Fin j.val =>
    aCrossing C (⟨i.val, by have := i.isLt; have := j.isLt; omega⟩ : Adj k) inverse)
  let middle := algebraMap C (AFree C k) (if inverse then (↑P.z⁻¹ : C) else (P.z : C)) * ax C inverse
  word.reverse.prod * middle * word.prod

/-- E_i=1-(T_i-T_i⁻¹)/Q, (2.45). -/
def affineContractionWord (P : AParams C) {k : ℕ} (i : Adj k) : AFree C k :=
  1-algebraMap C (AFree C k) (↑P.Q⁻¹ : C)*(aCrossing C i false-aCrossing C i true)

/-- Integer powers represented using an element and its specified inverse. -/
def signedPow {A : Type*} [Monoid A] (a inverse : A) (n : ℤ) : A :=
  if 0 ≤ n then a ^ n.toNat else inverse ^ (-n).toNat

/-- Exactly the group presentation (2.33)--(2.36) and quotient (2.42)--(2.43).
All signs and both sides of each two-sided relation are retained. -/
inductive AWRel (P : AParams C) (k : ℕ) : AFree C k → AFree C k → Prop
| inverseT (i : Adj k) (b : Bool) : AWRel P k (aCrossing C i b * aCrossing C i (!b)) 1
| inverseX (b : Bool) : AWRel P k (ax C b * ax C (!b)) 1
| distant (i j : Adj k) (h1 : i.val+1 ≠ j.val) (h2 : j.val+1 ≠ i.val) :
    AWRel P k (aCrossing C i * aCrossing C j) (aCrossing C j * aCrossing C i)
| braid (i j : Adj k) (h : j.val = i.val+1) :
    AWRel P k (aCrossing C i * aCrossing C j * aCrossing C i) (aCrossing C j * aCrossing C i * aCrossing C j)
| flagFirst (i : Adj k) (h : i.val = 0) :
    AWRel P k (ax C * aCrossing C i * ax C * aCrossing C i) (aCrossing C i * ax C * aCrossing C i * ax C)
| flagOther (i : Adj k) (h : 0 < i.val) : AWRel P k (ax C * aCrossing C i) (aCrossing C i * ax C)
| et (i : Adj k) (b : Bool) : AWRel P k (affineContractionWord C P i * aCrossing C i b)
    (algebraMap C (AFree C k) (if b then (P.z : C) else (↑P.z⁻¹ : C)) * affineContractionWord C P i)
| te (i : Adj k) (b : Bool) : AWRel P k (aCrossing C i b * affineContractionWord C P i)
    (algebraMap C (AFree C k) (if b then (P.z : C) else (↑P.z⁻¹ : C)) * affineContractionWord C P i)
| neighbor (i j : Adj k) (h : i.val+1 = j.val ∨ j.val+1 = i.val) (b : Bool) :
    AWRel P k (affineContractionWord C P i * aCrossing C j b * affineContractionWord C P i)
      (algebraMap C (AFree C k) (if b then (↑P.z⁻¹ : C) else (P.z : C)) * affineContractionWord C P i)
| compression (i : Adj k) (h : i.val = 0) (n : ℤ) :
    AWRel P k (affineContractionWord C P i * signedPow (affineYWord C P (adjacentLeft i) false) (affineYWord C P (adjacentLeft i) true) n * affineContractionWord C P i)
      (algebraMap C (AFree C k) (P.moment n) * affineContractionWord C P i)
| killLeft (i : Adj k) : AWRel P k (affineContractionWord C P i * affineYWord C P (adjacentLeft i) * affineYWord C P (adjacentRight i)) (affineContractionWord C P i)
| killRight (i : Adj k) : AWRel P k (affineYWord C P (adjacentLeft i) * affineYWord C P (adjacentRight i) * affineContractionWord C P i) (affineContractionWord C P i)

/-- The unrestricted affine BMW algebra; there is no cyclotomic polynomial relation. -/
abbrev AW (P : AParams C) (k : ℕ) := RingQuot (AWRel C P k)

/-- The canonical quotient map. -/
def awMap (P : AParams C) (k : ℕ) : AFree C k →ₐ[C] AW C P k :=
  RingQuot.mkAlgHom C (AWRel C P k)

/-- Y/(u-Y), expanded at infinity. -/
def multiplicativeResolvent {A : Type*} [Semiring A] (a : A) : PowerSeries A :=
  ps a * infinityResolvent a

/-- Y_i Y_(i+1)/(u²-Y_i Y_(i+1)), expanded at infinity. -/
def pairResolvent {A : Type*} [Ring A] (a : A) : PowerSeries A :=
  PowerSeries.mk (fun n => if n % 2 = 0 then a ^ (n/2) else 0) - 1

example {A : Type*} [Semiring A] (a : A) :
    PowerSeries.coeff 0 (multiplicativeResolvent a) = 0 := by
  simp [multiplicativeResolvent, infinityResolvent]

example {A : Type*} [Ring A] (a : A) : PowerSeries.coeff 0 (pairResolvent a) = 0 := by
  simp [pairResolvent]

/-- The scalar admissibility condition (4.20); u²/(u²-1)=1+g. -/
def AAdmissible (P : AParams C) : Prop :=
  let zp := PowerSeries.mk (fun n => P.moment (n : ℤ))
  let zm := PowerSeries.mk (fun n => P.moment (-(n : ℤ)))
  let g : PowerSeries C := pairResolvent (1 : C)
  let qi := ps (↑P.Q⁻¹ : C)
  (zm-ps (P.z : C)*qi-(1+g))*(zp+ps (↑P.z⁻¹ : C)*qi-(1+g)) =
    -(qi^2*(1+ps (2-(P.q : C)^2-(↑P.q⁻¹ : C)^2)*(g+g^2)))

/-- Laurent polynomials with integer exponent vectors and finite support. -/
abbrev Laurent (k : ℕ) := AddMonoidAlgebra C (Fin k → ℤ)

/-- Canonical Laurent evaluation using the actual Y_j and their constructed inverses. -/
def aEval (P : AParams C) (k : ℕ) (f : Laurent C k) : AW C P k :=
  (AddMonoidAlgebra.coeff f).sum (fun d c => algebraMap C (AW C P k) c *
    (List.ofFn (fun j : Fin k => signedPow (awMap C P k (affineYWord C P j false))
      (awMap C P k (affineYWord C P j true)) (d j))).prod)

/-- A Laurent variable, or its inverse, as a finite exponent-vector monomial. -/
def laurentVariable {k : ℕ} (j : Fin k) (inverse : Bool := false) : Laurent C k :=
  AddMonoidAlgebra.single (Pi.single j (if inverse then (-1 : ℤ) else 1)) 1

/-- The factor of (3.27) after division by its leading u⁴ coefficient. -/
def aRatio {A : Type*} [Ring A] (q qi y yi : A) : PowerSeries A :=
  let t : PowerSeries A := PowerSeries.X
  let f (a : A) := 1-ps a*t
  (f y)^2*f (qi^2*yi)*f (q^2*yi)*
    PowerSeries.invOfUnit ((f yi)^2*f (q^2*y)*f (qi^2*y)) 1

/-- The normalized numerator (u²-q²)(u²-q⁻²)/(u²-1)² in (3.26). -/
def aScalarFraction {A : Type*} [Ring A] (q qi : A) : PowerSeries A :=
  let g := pairResolvent (1 : A)
  1+ps (2-q^2-qi^2)*(g+g^2)

/-- The shifted positive series Z_n^++z⁻¹/Q-u²/(u²-1), constructed by (3.28). -/
def aShiftedPositive (P : AParams C) (n : ℕ) : PowerSeries (Laurent C n) :=
  let c := algebraMap C (Laurent C n)
  let h := 1+pairResolvent (1 : Laurent C n)
  let initial := PowerSeries.mk (fun ell => c (P.moment (ell : ℤ)))+
    ps (c ((↑P.z⁻¹ : C)*(↑P.Q⁻¹ : C)))-h
  initial*(List.ofFn (fun j : Fin n => aRatio (c (P.q : C)) (c (↑P.q⁻¹ : C))
    (laurentVariable C j false) (laurentVariable C j true))).prod

/-- Explicit integer-moment representatives as Laurent polynomials.
At n=0 the supplied bilateral scalar sequence is retained. At higher n,
positive moments come from (3.28) and negative ones from (3.26), using the
unit constant z/Q of its positive factor. No E_i is cancelled. -/
def aMomentPolynomial (P : AParams C) (n : ℕ) (ell : ℤ) : Laurent C n :=
  let c := algebraMap C (Laurent C n)
  if n = 0 then c (P.moment ell) else
    let h := 1+pairResolvent (1 : Laurent C n)
    let shifted := aShiftedPositive C P n
    let positive := shifted-ps (c ((↑P.z⁻¹ : C)*(↑P.Q⁻¹ : C)))+h
    let unitConstant : (Laurent C n)ˣ := Units.map c (P.z*P.Q⁻¹)
    let negative := ps (c ((P.z : C)*(↑P.Q⁻¹ : C)))+h-
      ps (c ((↑P.Q⁻¹ : C)^2))*aScalarFraction (c (P.q : C)) (c (↑P.q⁻¹ : C))*
        PowerSeries.invOfUnit shifted unitConstant
    if 0 ≤ ell then PowerSeries.coeff ell.toNat positive
      else PowerSeries.coeff (-ell).toNat negative

/-- Canonical evaluation of the n-variable representative at a larger level. -/
def aMomentAt (P : AParams C) (n level : ℕ) (ell : ℤ) (h : n ≤ level) : AW C P level :=
  (AddMonoidAlgebra.coeff (aMomentPolynomial C P n ell)).sum (fun d c => algebraMap C (AW C P level) c *
    (List.ofFn (fun j : Fin n =>
      let a : Fin level := ⟨j.val, lt_of_lt_of_le j.isLt h⟩
      signedPow (awMap C P level (affineYWord C P a false))
        (awMap C P level (affineYWord C P a true)) (d j))).prod)

/-- The two series both use u⁻ˡ as degree; only the moment index changes sign. -/
def aMomentSeries (P : AParams C) (n level : ℕ) (h : n ≤ level) (negative : Bool := false) :
    PowerSeries (AW C P level) :=
  PowerSeries.mk (fun ell => aMomentAt C P n level
    (if negative then -(ell : ℤ) else (ell : ℤ)) h)

example (P : AParams C) (ell : ℤ) :
    aMomentPolynomial C P 0 ell = algebraMap C (Laurent C 0) (P.moment ell) := by
  simp [aMomentPolynomial]

/-- Permutation invariance of Laurent coefficients and the formal reciprocal-pair test.
The substitutions send (d_1,d_2,...) to (d_1-d_2,0,...) or (0,0,...). -/
def ACancel (k : ℕ) (f : Laurent C k) : Prop :=
  (∀ (w : Equiv.Perm (Fin k)) (d : Fin k → ℤ), AddMonoidAlgebra.coeff f (d ∘ w) = AddMonoidAlgebra.coeff f d) ∧
  ∀ h : 2 ≤ k,
    let a : Fin k := ⟨0, by omega⟩
    let b : Fin k := ⟨1, by omega⟩
    (AddMonoidAlgebra.coeff f).sum (fun d c => (AddMonoidAlgebra.single
      (fun j => if j = a then d a-d b else if j = b then 0 else d j) c : Laurent C k)) =
    (AddMonoidAlgebra.coeff f).sum (fun d c => (AddMonoidAlgebra.single
      (fun j => if j = a ∨ j = b then 0 else d j) c : Laurent C k))

/-- Center equality in the actual affine quotient via its canonical Laurent embedding. -/
def ACenterDescription (P : AParams C) (k : ℕ) : Prop :=
  Function.Injective (aEval C P k) ∧
    ∀ a : AW C P k, Central a ↔ ∃ f, ACancel C k f ∧ aEval C P k f = a

/-- Principal left ideal as the actual set of left multiples. -/
def leftMultiples {A : Type*} [Mul A] (e : A) : Set A := {a | ∃ b, a = b*e}

/-- The actual ring Z[zeta] inside the complex numbers. -/
def CyclotomicIntegers (zeta : ℂ) := Algebra.adjoin ℤ ({zeta} : Set ℂ)

/-- The actual field Q(zeta) inside the complex numbers. -/
def CyclotomicField (zeta : ℂ) := IntermediateField.adjoin ℚ ({zeta} : Set ℂ)

/-- The distinguished root as an element of its integer coefficient ring. -/
def integralRoot (zeta : ℂ) : CyclotomicIntegers zeta :=
  ⟨zeta, Algebra.subset_adjoin (by simp)⟩

/-- The r-variable root-of-unity wheel condition, as a formal polynomial identity. -/
def Wheel (k r : ℕ) (hk : 0 < k) (zeta : C) (f : MvPolynomial (Fin k) C) : Prop :=
  MvPolynomial.IsSymmetric f ∧
    MvPolynomial.eval₂ MvPolynomial.C
      (fun j => if j.val < r then MvPolynomial.C (zeta^j.val)*MvPolynomial.X (⟨0,hk⟩ : Fin k)
        else MvPolynomial.X j) f =
    MvPolynomial.eval₂ MvPolynomial.C
      (fun j => if j.val < r then 0 else MvPolynomial.X j) f

/-- The integral power sum from the frozen library, extended along the canonical integer map. -/
def coefficientPowerSum (k n : ℕ) : MvPolynomial (Fin k) C :=
  MvPolynomial.map (Int.castRingHom C)
    (QAlgorithms.Papers.Independent.Support21.P12.powerSum k n)

example (k : ℕ) : coefficientPowerSum C k 1 = ∑ j : Fin k, MvPolynomial.X j := by
  simp [coefficientPowerSum, QAlgorithms.Papers.Independent.Support21.P12.powerSum]

end

end QAlgorithms.Papers.Independent.Intakenext100.P34
Source
Affine and degenerate affine BMW algebras: The center, arXiv:1105.4207v2, https://arxiv.org/abs/1105.4207v2
Read-back

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

QAlgorithms.Papers.Independent.Intakenext100.P34.AAdmissible

Let CCC be a commutative ring, and let PPP consist of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. Define

Z+(u)=∑n≥0ωnun,Z−(u)=∑n≥0ω−nun,G(u)=∑r≥1u2r.Z_+(u)=\sum_{n\ge0}\omega_nu^n,\qquad Z_-(u)=\sum_{n\ge0}\omega_{-n}u^n,\qquad G(u)=\sum_{r\ge1}u^{2r}.Z+​(u)=n≥0∑​ωn​un,Z−​(u)=n≥0∑​ω−n​un,G(u)=r≥1∑​u2r.

The predicate AAA-admissibility of PPP means precisely the following equality in C[[u]]C[[u]]C[[u]], where coefficients such as zzz and Q−1Q^{-1}Q−1 denote constant series:

(Z−−zQ−1−(1+G))(Z++z−1Q−1−(1+G))=−Q−2(1+(2−q2−q−2)(G+G2)).\bigl(Z_--zQ^{-1}-(1+G)\bigr) \bigl(Z_++z^{-1}Q^{-1}-(1+G)\bigr) = -Q^{-2}\left(1+(2-q^2-q^{-2})(G+G^2)\right).(Z−​−zQ−1−(1+G))(Z+​+z−1Q−1−(1+G))=−Q−2(1+(2−q2−q−2)(G+G2)).

QAlgorithms.Papers.Independent.Intakenext100.P34.ACancel

For a commutative ring CCC, a natural number kkk, and a Laurent polynomial f=∑d∈ZkcdXdf=\sum_{d\in\mathbb Z^k}c_dX^df=∑d∈Zk​cd​Xd with coefficients in CCC and finite support, this predicate says that cd∘w=cdc_{d\circ w}=c_dcd∘w​=cd​ for every permutation www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} and every exponent vector d:{0,…,k−1}→Zd:\{0,\ldots,k-1\}\to\mathbb Zd:{0,…,k−1}→Z, and that, whenever 2≤k2\le k2≤k, the following equality holds in the same Laurent polynomial ring:

∑dcdX0d0−d1∏j=2k−1Xjdj=∑dcd∏j=2k−1Xjdj.\sum_d c_dX_0^{d_0-d_1}\prod_{j=2}^{k-1}X_j^{d_j} = \sum_d c_d\prod_{j=2}^{k-1}X_j^{d_j}.d∑​cd​X0d0​−d1​​j=2∏k−1​Xjdj​​=d∑​cd​j=2∏k−1​Xjdj​​.

Thus the second condition is precisely f(X0,X0−1,X2,…)=f(1,1,X2,…)f(X_0,X_0^{-1},X_2,\ldots)=f(1,1,X_2,\ldots)f(X0​,X0−1​,X2​,…)=f(1,1,X2​,…); coefficients of monomials that coincide after substitution are added. For k=0k=0k=0 or k=1k=1k=1, there is no second condition, and the permutation condition is automatic.

QAlgorithms.Papers.Independent.Intakenext100.P34.ACenterDescription

Let CCC be a commutative ring, and let PPP consist of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C×, with Q=q−q−1Q=q-q^{-1}Q=q−q−1, and a sequence μ:Z→C\mu:\mathbb Z\to Cμ:Z→C satisfying μ0=1+(z−z−1)Q−1\mu_0=1+(z-z^{-1})Q^{-1}μ0​=1+(z−z−1)Q−1. For k∈Nk\in\mathbb Nk∈N, let WWW be the unital associative CCC-algebra presented by invertible generators X,T0,…,Tk−2X,T_0,\ldots,T_{k-2}X,T0​,…,Tk−2​. Put Yj=Tj−1⋯T0(zX)T0⋯Tj−1Y_j=T_{j-1}\cdots T_0(zX)T_0\cdots T_{j-1}Yj​=Tj−1​⋯T0​(zX)T0​⋯Tj−1​, with Y0=zXY_0=zXY0​=zX, and Ei=1−Q−1(Ti−Ti−1)E_i=1-Q^{-1}(T_i-T_i^{-1})Ei​=1−Q−1(Ti​−Ti−1​). Its defining relations, for all indices for which the displayed generators exist, are

TiTj=TjTi(i+1≠j, j+1≠i),TiTi+1Ti=Ti+1TiTi+1,XT0XT0=T0XT0X,XTi=TiX(i≥1),EiTiσ=TiσEi=z−σEi(σ∈{1,−1}),EiTjσEi=zσEi(∣i−j∣=1, σ∈{1,−1}),E0Y0mE0=μmE0(m∈Z),EiYiYi+1=YiYi+1Ei=Ei.\begin{gathered} T_iT_j=T_jT_i\quad(i+1\ne j,\ j+1\ne i),\qquad T_iT_{i+1}T_i=T_{i+1}T_iT_{i+1},\\ XT_0XT_0=T_0XT_0X,\qquad XT_i=T_iX\quad(i\ge1),\\ E_iT_i^\sigma=T_i^\sigma E_i=z^{-\sigma}E_i \quad(\sigma\in\{1,-1\}),\\ E_iT_j^\sigma E_i=z^\sigma E_i \quad(|i-j|=1,\ \sigma\in\{1,-1\}),\\ E_0Y_0^mE_0=\mu_mE_0\quad(m\in\mathbb Z),\qquad E_iY_iY_{i+1}=Y_iY_{i+1}E_i=E_i. \end{gathered}Ti​Tj​=Tj​Ti​(i+1=j, j+1=i),Ti​Ti+1​Ti​=Ti+1​Ti​Ti+1​,XT0​XT0​=T0​XT0​X,XTi​=Ti​X(i≥1),Ei​Tiσ​=Tiσ​Ei​=z−σEi​(σ∈{1,−1}),Ei​Tjσ​Ei​=zσEi​(∣i−j∣=1, σ∈{1,−1}),E0​Y0m​E0​=μm​E0​(m∈Z),Ei​Yi​Yi+1​=Yi​Yi+1​Ei​=Ei​.​

The relations involving index 000 among the TiT_iTi​ or EiE_iEi​ occur only when k≥2k\ge2k≥2. Define a function from the Laurent polynomial ring by ordered evaluation,

ev⁡P ⁣(∑d∈ZkcdXd)=∑dcdY0d0⋯Yk−1dk−1,\operatorname{ev}_P\!\left(\sum_{d\in\mathbb Z^k}c_dX^d\right) =\sum_d c_dY_0^{d_0}\cdots Y_{k-1}^{d_{k-1}},evP​(d∈Zk∑​cd​Xd)=d∑​cd​Y0d0​​⋯Yk−1dk−1​​,

where coefficients act through the structure map C→WC\to WC→W. The predicate asserts that this function is injective on the entire Laurent polynomial ring and that, for every a∈Wa\in Wa∈W,

(∀b∈W, ab=ba)⟺∃f=∑dcdXd,{cd∘w=cdfor every permutation w and every d,f(X0,X0−1,X2,…)=f(1,1,X2,…)if k≥2,ev⁡P(f)=a.(\forall b\in W,\ ab=ba) \quad\Longleftrightarrow\quad \exists f=\sum_dc_dX^d,\quad \begin{cases} c_{d\circ w}=c_d&\text{for every permutation $w$ and every $d$},\\ f(X_0,X_0^{-1},X_2,\ldots)=f(1,1,X_2,\ldots)&\text{if $k\ge2$},\\ \operatorname{ev}_P(f)=a. \end{cases}(∀b∈W, ab=ba)⟺∃f=d∑​cd​Xd,⎩⎨⎧​cd∘w​=cd​f(X0​,X0−1​,X2​,…)=f(1,1,X2​,…)evP​(f)=a.​for every permutation w and every d,if k≥2,​

No positivity of kkk, nontriviality of CCC, or admissibility identity for μ\muμ is assumed in this definition. When k=0k=0k=0, the Laurent polynomial ring is CCC, evaluation is the scalar map, and the presented algebra still has the invertible generator XXX.

QAlgorithms.Papers.Independent.Intakenext100.P34.AFree

For a commutative ring CCC and every natural number kkk, this abbreviates the free associative unital CCC-algebra on the letters consisting of a crossing letter (i,b)(i,b)(i,b) for every natural number iii with i+1<ki+1<ki+1<k and every Boolean bbb, together with a flag letter for every Boolean bbb. No relations among these generators are imposed beyond the CCC-algebra axioms. When k=0k=0k=0 or k=1k=1k=1, this is the free CCC-algebra on the two flag letters.

QAlgorithms.Papers.Independent.Intakenext100.P34.ALetter

For every natural number kkk, this defines a type of letters with two distinct constructors: a crossing letter (i,b)(i,b)(i,b) for every natural number iii satisfying i+1<ki+1<ki+1<k and every Boolean bbb, and a flag letter for every Boolean bbb. Letters from different constructors are distinct, and each constructor distinguishes its arguments. The crossing index set is Fin⁡(k−1)\operatorname{Fin}(k-1)Fin(k−1), where natural-number subtraction is truncated at zero. Thus, when k=0k=0k=0 or k=1k=1k=1, there are no crossing letters and there are exactly two flag letters. The Boolean labels carry no additional relations.

QAlgorithms.Papers.Independent.Intakenext100.P34.AParams

For a commutative ring CCC, this structure consists of three specified units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C×, an equality of their underlying ring elements

Q=q−q−1,Q=q-q^{-1},Q=q−q−1,

an integer-indexed sequence ω:Z→C\omega:\mathbb Z\to Cω:Z→C, and an equality

ω(0)=1+(z−z−1)Q−1.\omega(0)=1+(z-z^{-1})Q^{-1}.ω(0)=1+(z−z−1)Q−1.

All inverses here are inverses of the specified units. In particular, q−q−1q-q^{-1}q−q−1 is required to be a unit because it equals QQQ. The sequence includes both positive and negative integer indices, and the only condition imposed on its values by this structure is the displayed value at 000.

QAlgorithms.Papers.Independent.Intakenext100.P34.AW

For a commutative ring CCC, parameters PPP comprising units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and m:Z→Cm:\mathbb Z\to Cm:Z→C satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and m(0)=1+(z−z−1)Q−1m(0)=1+(z-z^{-1})Q^{-1}m(0)=1+(z−z−1)Q−1, and any natural number kkk, this abbreviates the ring quotient of the free associative unital CCC-algebra on generators TibT_i^bTib​ for natural iii with i+1<ki+1<ki+1<k and Boolean bbb, together with XbX^bXb, by the smallest ring congruence imposing the equations below. Identify the Boolean labels with 0,10,10,1, put bˉ=1−b\bar b=1-bbˉ=1−b, ζ0=z\zeta_0=zζ0​=z, ζ1=z−1\zeta_1=z^{-1}ζ1​=z−1, and define, with scalars embedded from CCC,

Ei=1−Q−1(Ti0−Ti1),Yjb=(Tj−1b⋯T0b)(ζbXb)(T0b⋯Tj−1b).E_i=1-Q^{-1}(T_i^0-T_i^1),\qquad Y_j^b=(T_{j-1}^b\cdots T_0^b)(\zeta_bX^b)(T_0^b\cdots T_{j-1}^b).Ei​=1−Q−1(Ti0​−Ti1​),Yjb​=(Tj−1b​⋯T0b​)(ζb​Xb)(T0b​⋯Tj−1b​).

Here 0≤j<k0\le j<k0≤j<k, empty products equal 111, and Sj(n)S_j(n)Sj​(n) means (Yj0)n(Y_j^0)^n(Yj0​)n for integers n≥0n\ge0n≥0 and (Yj1)−n(Y_j^1)^{-n}(Yj1​)−n for n<0n<0n<0. The imposed equations, for every valid crossing index and Boolean bbb, are

TibTibˉ=1,XbXbˉ=1,Ti0Tj0=Tj0Ti0if i+1≠j, j+1≠i,Ti0Tj0Ti0=Tj0Ti0Tj0if j=i+1,X0Ti0X0Ti0=Ti0X0Ti0X0if i=0,X0Ti0=Ti0X0if i>0,EiTib=ζbˉEi,TibEi=ζbˉEi,EiTjbEi=ζbEiif i+1=j or j+1=i,EiSi(n)Ei=m(n)Eiif i=0,n∈Z,EiYi0Yi+10=Ei,Yi0Yi+10Ei=Ei.\begin{aligned} T_i^bT_i^{\bar b}&=1,&X^bX^{\bar b}&=1,\\ T_i^0T_j^0&=T_j^0T_i^0 &&\text{if }i+1\ne j,\ j+1\ne i,\\ T_i^0T_j^0T_i^0&=T_j^0T_i^0T_j^0 &&\text{if }j=i+1,\\ X^0T_i^0X^0T_i^0&=T_i^0X^0T_i^0X^0 &&\text{if }i=0,\\ X^0T_i^0&=T_i^0X^0 &&\text{if }i>0,\\ E_iT_i^b&=\zeta_{\bar b}E_i, &T_i^bE_i&=\zeta_{\bar b}E_i,\\ E_iT_j^bE_i&=\zeta_bE_i &&\text{if }i+1=j\text{ or }j+1=i,\\ E_iS_i(n)E_i&=m(n)E_i &&\text{if }i=0,\quad n\in\mathbb Z,\\ E_iY_i^0Y_{i+1}^0&=E_i, &Y_i^0Y_{i+1}^0E_i&=E_i. \end{aligned}Tib​Tibˉ​Ti0​Tj0​Ti0​Tj0​Ti0​X0Ti0​X0Ti0​X0Ti0​Ei​Tib​Ei​Tjb​Ei​Ei​Si​(n)Ei​Ei​Yi0​Yi+10​​=1,=Tj0​Ti0​=Tj0​Ti0​Tj0​=Ti0​X0Ti0​X0=Ti0​X0=ζbˉ​Ei​,=ζb​Ei​=m(n)Ei​=Ei​,​XbXbˉTib​Ei​Yi0​Yi+10​Ei​​=1,if i+1=j, j+1=i,if j=i+1,if i=0,if i>0,=ζbˉ​Ei​,if i+1=j or j+1=i,if i=0,n∈Z,=Ei​.​

The distant equation includes i=ji=ji=j, and the compression equations include n=0n=0n=0. When k=0k=0k=0 or k=1k=1k=1, there are no crossing generators and the only imposed equations are XbXbˉ=1X^bX^{\bar b}=1XbXbˉ=1 for both Boolean values.

QAlgorithms.Papers.Independent.Intakenext100.P34.AWRel

Let CCC be a commutative ring, let PPP consist of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and a function m:Z→Cm:\mathbb Z\to Cm:Z→C with Q=q−q−1Q=q-q^{-1}Q=q−q−1 and m(0)=1+(z−z−1)Q−1m(0)=1+(z-z^{-1})Q^{-1}m(0)=1+(z−z−1)Q−1, and let kkk be any natural number. Put Ik={i∈N:i+1<k}I_k=\{i\in\mathbb N:i+1<k\}Ik​={i∈N:i+1<k}. In the free associative unital CCC-algebra on crossing generators TibT_i^bTib​ for i∈Iki\in I_ki∈Ik​ and Boolean bbb, and flag generators XbX^bXb, identify false and true with 000 and 111, respectively, write bˉ=1−b\bar b=1-bbˉ=1−b, and put ζ0=z\zeta_0=zζ0​=z, ζ1=z−1\zeta_1=z^{-1}ζ1​=z−1,

Ei=1−Q−1(Ti0−Ti1),Yjb=(Tj−1b⋯T0b)(ζbXb)(T0b⋯Tj−1b)(0≤j<k).E_i=1-Q^{-1}(T_i^0-T_i^1),\qquad Y_j^b=(T_{j-1}^b\cdots T_0^b)(\zeta_bX^b)(T_0^b\cdots T_{j-1}^b) \quad(0\le j<k).Ei​=1−Q−1(Ti0​−Ti1​),Yjb​=(Tj−1b​⋯T0b​)(ζb​Xb)(T0b​⋯Tj−1b​)(0≤j<k).

Scalars here are embedded from CCC, and empty products equal 111. For n∈Zn\in\mathbb Zn∈Z, put Sj(n)=(Yj0)nS_j(n)=(Y_j^0)^nSj​(n)=(Yj0​)n when n≥0n\ge0n≥0 and Sj(n)=(Yj1)−nS_j(n)=(Y_j^1)^{-n}Sj​(n)=(Yj1​)−n when n<0n<0n<0, so Sj(0)=1S_j(0)=1Sj​(0)=1. This defines a binary relation whose constructor pairs are exactly the following, with all displayed crossing indices in IkI_kIk​, every bbb Boolean, and every nnn integral:

TibTibˉ⇝1,XbXbˉ⇝1,Ti0Tj0⇝Tj0Ti0if i+1≠j, j+1≠i,Ti0Tj0Ti0⇝Tj0Ti0Tj0if j=i+1,X0Ti0X0Ti0⇝Ti0X0Ti0X0if i=0,X0Ti0⇝Ti0X0if i>0,EiTib⇝ζbˉEi,TibEi⇝ζbˉEi,EiTjbEi⇝ζbEiif i+1=j or j+1=i,EiSi(n)Ei⇝m(n)Eiif i=0,EiYi0Yi+10⇝Ei,Yi0Yi+10Ei⇝Ei.\begin{aligned} T_i^bT_i^{\bar b}&\rightsquigarrow1, &X^bX^{\bar b}&\rightsquigarrow1,\\ T_i^0T_j^0&\rightsquigarrow T_j^0T_i^0 &&\text{if }i+1\ne j,\ j+1\ne i,\\ T_i^0T_j^0T_i^0&\rightsquigarrow T_j^0T_i^0T_j^0 &&\text{if }j=i+1,\\ X^0T_i^0X^0T_i^0&\rightsquigarrow T_i^0X^0T_i^0X^0 &&\text{if }i=0,\\ X^0T_i^0&\rightsquigarrow T_i^0X^0 &&\text{if }i>0,\\ E_iT_i^b&\rightsquigarrow\zeta_{\bar b}E_i, &T_i^bE_i&\rightsquigarrow\zeta_{\bar b}E_i,\\ E_iT_j^bE_i&\rightsquigarrow\zeta_bE_i &&\text{if }i+1=j\text{ or }j+1=i,\\ E_iS_i(n)E_i&\rightsquigarrow m(n)E_i &&\text{if }i=0,\\ E_iY_i^0Y_{i+1}^0&\rightsquigarrow E_i, &Y_i^0Y_{i+1}^0E_i&\rightsquigarrow E_i. \end{aligned}Tib​Tibˉ​Ti0​Tj0​Ti0​Tj0​Ti0​X0Ti0​X0Ti0​X0Ti0​Ei​Tib​Ei​Tjb​Ei​Ei​Si​(n)Ei​Ei​Yi0​Yi+10​​⇝1,⇝Tj0​Ti0​⇝Tj0​Ti0​Tj0​⇝Ti0​X0Ti0​X0⇝Ti0​X0⇝ζbˉ​Ei​,⇝ζb​Ei​⇝m(n)Ei​⇝Ei​,​XbXbˉTib​Ei​Yi0​Yi+10​Ei​​⇝1,if i+1=j, j+1=i,if j=i+1,if i=0,if i>0,⇝ζbˉ​Ei​,if i+1=j or j+1=i,if i=0,⇝Ei​.​

The arrows denote membership in this relation, rather than equalities already holding in the free algebra; the definition does not itself close these pairs under symmetry, transitivity, addition, or multiplication. The distant rule permits i=ji=ji=j. When k=0k=0k=0 or k=1k=1k=1, only the flag inverse pairs remain.

QAlgorithms.Papers.Independent.Intakenext100.P34.Adj

For every natural number kkk, Adj⁡(k)\operatorname{Adj}(k)Adj(k) is the type of natural numbers iii satisfying 0≤i<k−10\le i<k-10≤i<k−1, where subtraction is truncated at zero. Thus Adj⁡(k)\operatorname{Adj}(k)Adj(k) is empty for k=0k=0k=0 and k=1k=1k=1; for k≥2k\ge2k≥2, its elements are 0,…,k−20,\ldots,k-20,…,k−2.

QAlgorithms.Papers.Independent.Intakenext100.P34.CyclotomicField

For any complex number ζ\zetaζ, this defines the smallest intermediate field of C/Q\mathbb C/\mathbb QC/Q containing ζ\zetaζ, namely

Q(ζ)={p(ζ)q(ζ):p,q∈Q[X], q(ζ)≠0}.\mathbb Q(\zeta) = \left\{\frac{p(\zeta)}{q(\zeta)}: p,q\in\mathbb Q[X],\ q(\zeta)\ne0\right\}.Q(ζ)={q(ζ)p(ζ)​:p,q∈Q[X], q(ζ)=0}.

No root-of-unity or algebraicity assumption is imposed on ζ\zetaζ.

QAlgorithms.Papers.Independent.Intakenext100.P34.CyclotomicIntegers

For any complex number ζ\zetaζ, this defines the smallest Z\mathbb ZZ-subalgebra of C\mathbb CC containing ζ\zetaζ, namely

Z[ζ]={p(ζ):p∈Z[X]}.\mathbb Z[\zeta]=\{p(\zeta):p\in\mathbb Z[X]\}.Z[ζ]={p(ζ):p∈Z[X]}.

There is no assumption that ζ\zetaζ is a root of unity or is algebraic or integral.

QAlgorithms.Papers.Independent.Intakenext100.P34.DAdmissible

Let CCC be the commutative coefficient ring, and let PPP consist of a specified unit uuu whose underlying element equals 222, an element ε∈C\varepsilon\in Cε∈C with ε=1\varepsilon=1ε=1 or ε=−1\varepsilon=-1ε=−1, a sequence μ:N→C\mu:\mathbb N\to Cμ:N→C, and an optional scalar pair. Put h=u−1∈Ch=u^{-1}\in Ch=u−1∈C, and form the formal power series

Z(T)=∑n=0∞μnTn,Z−(T)=∑n=0∞(−1)nμnTn.Z(T)=\sum_{n=0}^{\infty}\mu_nT^n, \qquad Z_-(T)=\sum_{n=0}^{\infty}(-1)^n\mu_nT^n.Z(T)=n=0∑∞​μn​Tn,Z−​(T)=n=0∑∞​(−1)nμn​Tn.

This definition is the proposition that the following equality holds in C[[T]]C[[T]]C[[T]], with hhh and ε\varepsilonε inserted as constant series:

(TZ−(T)−hT−ε)(TZ(T)−hT+ε)=(hT−ε)(hT+ε).\bigl(TZ_-(T)-hT-\varepsilon\bigr) \bigl(TZ(T)-hT+\varepsilon\bigr) =(hT-\varepsilon)(hT+\varepsilon).(TZ−​(T)−hT−ε)(TZ(T)−hT+ε)=(hT−ε)(hT+ε).

It is an equality of all formal coefficients, including degree zero, and requires no analytic convergence. The optional scalar pair does not occur in this proposition.

QAlgorithms.Papers.Independent.Intakenext100.P34.DBraid

For a commutative ring CCC and a natural number kkk, Dbraid(C,k)D_{\mathrm{braid}}(C,k)Dbraid​(C,k) is the quotient of the free associative unital CCC-algebra on generators TwT_wTw​ indexed by permutations of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, two generators Kfalse,KtrueK_{\mathrm{false}},K_{\mathrm{true}}Kfalse​,Ktrue​, and generators YjY_jYj​ for 0≤j<k0\le j<k0≤j<k, by the smallest ring congruence imposing the following equations. Writing sis_isi​ for the permutation exchanging iii and i+1i+1i+1, and Δi=Yi+1−TsiYiTsi\Delta_i=Y_{i+1}-T_{s_i}Y_iT_{s_i}Δi​=Yi+1​−Tsi​​Yi​Tsi​​, the equations are

Tid=1,TwTv=Twvfor all permutations w,v;YiYj=YjYifor 0≤i,j<k;KfalseKtrue=KtrueKfalse;KbYj=YjKbfor every Boolean b, 0≤j<k;KfalseTsi=TsiKfalsefor 0≤i<k−1;KtrueTsiKtrueTsi=TsiKtrueTsiKtruefor 0≤i<k−1, i=0;KtrueTsi=TsiKtruefor 0≤i<k−1, i≠0;Tsi(Yi+Yi+1)=(Yi+Yi+1)Tsifor 0≤i<k−1;YjTsi=TsiYjfor 0≤i<k−1, 0≤j<k, j≠i, j≠i+1;TsiTsjΔiTsjTsi=Δjfor 0≤i,j<k−1, j=i+1.\begin{aligned} &T_{\mathrm{id}}=1,\qquad T_wT_v=T_{wv} &&\text{for all permutations }w,v;\\ &Y_iY_j=Y_jY_i &&\text{for }0\le i,j<k;\\ &K_{\mathrm{false}}K_{\mathrm{true}} =K_{\mathrm{true}}K_{\mathrm{false}};\\ &K_bY_j=Y_jK_b &&\text{for every Boolean }b,\ 0\le j<k;\\ &K_{\mathrm{false}}T_{s_i}=T_{s_i}K_{\mathrm{false}} &&\text{for }0\le i<k-1;\\ &K_{\mathrm{true}}T_{s_i}K_{\mathrm{true}}T_{s_i} =T_{s_i}K_{\mathrm{true}}T_{s_i}K_{\mathrm{true}} &&\text{for }0\le i<k-1,\ i=0;\\ &K_{\mathrm{true}}T_{s_i}=T_{s_i}K_{\mathrm{true}} &&\text{for }0\le i<k-1,\ i\ne0;\\ &T_{s_i}(Y_i+Y_{i+1})=(Y_i+Y_{i+1})T_{s_i} &&\text{for }0\le i<k-1;\\ &Y_jT_{s_i}=T_{s_i}Y_j &&\text{for }0\le i<k-1,\ 0\le j<k,\ j\ne i,\ j\ne i+1;\\ &T_{s_i}T_{s_j}\Delta_iT_{s_j}T_{s_i}=\Delta_j &&\text{for }0\le i,j<k-1,\ j=i+1. \end{aligned}​Tid​=1,Tw​Tv​=Twv​Yi​Yj​=Yj​Yi​Kfalse​Ktrue​=Ktrue​Kfalse​;Kb​Yj​=Yj​Kb​Kfalse​Tsi​​=Tsi​​Kfalse​Ktrue​Tsi​​Ktrue​Tsi​​=Tsi​​Ktrue​Tsi​​Ktrue​Ktrue​Tsi​​=Tsi​​Ktrue​Tsi​​(Yi​+Yi+1​)=(Yi​+Yi+1​)Tsi​​Yj​Tsi​​=Tsi​​Yj​Tsi​​Tsj​​Δi​Tsj​​Tsi​​=Δj​​​for all permutations w,v;for 0≤i,j<k;for every Boolean b, 0≤j<k;for 0≤i<k−1;for 0≤i<k−1, i=0;for 0≤i<k−1, i=0;for 0≤i<k−1;for 0≤i<k−1, 0≤j<k, j=i, j=i+1;for 0≤i,j<k−1, j=i+1.​

Here wvwvwv acts by w(v(x))w(v(x))w(v(x)), and k−1k-1k−1 uses truncated natural-number subtraction. The definition includes k=0k=0k=0 and k=1k=1k=1, when there are no adjacent indices; for k=0k=0k=0 there are also no YjY_jYj​ generators.

QAlgorithms.Papers.Independent.Intakenext100.P34.DCancel

For a commutative ring CCC, a natural number kkk, and a polynomial f∈C[X0,…,Xk−1]f\in C[X_0,\ldots,X_{k-1}]f∈C[X0​,…,Xk−1​], this predicate means that fff is invariant under every permutation of its variables and, whenever k≥2k\ge2k≥2, the following equality holds as an equality of polynomials:

f(X0,−X0,X2,…,Xk−1)=f(0,0,X2,…,Xk−1).f(X_0,-X_0,X_2,\ldots,X_{k-1}) = f(0,0,X_2,\ldots,X_{k-1}).f(X0​,−X0​,X2​,…,Xk−1​)=f(0,0,X2​,…,Xk−1​).

The coefficients are unchanged by both substitutions. For k=0k=0k=0 or k=1k=1k=1, the substitution condition is vacuous, so only permutation invariance is required.

QAlgorithms.Papers.Independent.Intakenext100.P34.DCenterDescription

Let CCC be a commutative ring, k∈Nk\in\mathbb Nk∈N, and let PPP specify a unit uuu with value 222, a sign ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence ω:N→C\omega:\mathbb N\to Cω:N→C, and an optional scalar pair σ\sigmaσ. Define WkW_kWk​ as the associative unital CCC-algebra with generators TwT_wTw​ for permutations of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, κ0,κ1\kappa_0,\kappa_1κ0​,κ1​, and YjY_jYj​ for j<kj<kj<k. Write Si=T(i i+1)S_i=T_{(i\ i+1)}Si​=T(i i+1)​, Γi=Yi+1−SiYiSi\Gamma_i=Y_{i+1}-S_iY_iS_iΓi​=Yi+1​−Si​Yi​Si​, Ei=1+SiYi−Yi+1SiE_i=1+S_iY_i-Y_{i+1}S_iEi​=1+Si​Yi​−Yi+1​Si​, and [a,b]=ab−ba[a,b]=ab-ba[a,b]=ab−ba. Its relations, for existing indices, are

T1=1,TwTv=Twv,[Ya,Yb]=[κ0,κ1]=[κc,Ya]=[κ0,Si]=0(c=0,1),(κ1S0)2=(S0κ1)2(k≥2),[κ1,Si]=0(i>0),[Si,Yi+Yi+1]=0,[Si,Yj]=0(j∉{i,i+1}),SiSi+1ΓiSi+1Si=Γi+1(i+2<k),EiSi=SiEi=εEi,EiSjEi=εEi(∣i−j∣=1),E0Y0aE0=ω(a)E0(k≥2, a≥0),Ei(Yi+Yi+1)=(Yi+Yi+1)Ei=0,\begin{gathered} T_1=1,\quad T_wT_v=T_{wv},\quad [Y_a,Y_b]=[\kappa_0,\kappa_1]=[\kappa_c,Y_a]=[\kappa_0,S_i]=0 \quad(c=0,1),\\ (\kappa_1S_0)^2=(S_0\kappa_1)^2\quad(k\ge2),\quad [\kappa_1,S_i]=0\quad(i>0),\\ [S_i,Y_i+Y_{i+1}]=0,\quad [S_i,Y_j]=0\quad(j\notin\{i,i+1\}),\\ S_iS_{i+1}\Gamma_iS_{i+1}S_i=\Gamma_{i+1}\quad(i+2<k),\\ E_iS_i=S_iE_i=\varepsilon E_i,\quad E_iS_jE_i=\varepsilon E_i\quad(|i-j|=1),\\ E_0Y_0^aE_0=\omega(a)E_0\quad(k\ge2,\ a\ge0),\quad E_i(Y_i+Y_{i+1})=(Y_i+Y_{i+1})E_i=0, \end{gathered}T1​=1,Tw​Tv​=Twv​,[Ya​,Yb​]=[κ0​,κ1​]=[κc​,Ya​]=[κ0​,Si​]=0(c=0,1),(κ1​S0​)2=(S0​κ1​)2(k≥2),[κ1​,Si​]=0(i>0),[Si​,Yi​+Yi+1​]=0,[Si​,Yj​]=0(j∈/{i,i+1}),Si​Si+1​Γi​Si+1​Si​=Γi+1​(i+2<k),Ei​Si​=Si​Ei​=εEi​,Ei​Sj​Ei​=εEi​(∣i−j∣=1),E0​Y0a​E0​=ω(a)E0​(k≥2, a≥0),Ei​(Yi​+Yi+1​)=(Yi​+Yi+1​)Ei​=0,​

together with κ0=a1, κ1=b1\kappa_0=a1,\ \kappa_1=b1κ0​=a1, κ1​=b1 if σ=some⁡(a,b)\sigma=\operatorname{some}(a,b)σ=some(a,b), and no such scalar relations if σ=none⁡\sigma=\operatorname{none}σ=none. For a polynomial f=∑αcαXαf=\sum_\alpha c_\alpha X^\alphaf=∑α​cα​Xα, let

Φ(f)=∑α∈supp⁡(f)cα‾ Y0α0⋯Yk−1αk−1,\Phi(f)=\sum_{\alpha\in\operatorname{supp}(f)} \overline{c_\alpha}\,Y_0^{\alpha_0}\cdots Y_{k-1}^{\alpha_{k-1}},Φ(f)=α∈supp(f)∑​cα​​Y0α0​​⋯Yk−1αk−1​​,

with the product ordered by increasing index. The predicate asserts both that Φ\PhiΦ is injective on the entire polynomial ring C[X0,…,Xk−1]C[X_0,\ldots,X_{k-1}]C[X0​,…,Xk−1​], and that, for every a∈Wka\in W_ka∈Wk​,

(∀b∈Wk, ab=ba)⟺∃f∈C[X0,…,Xk−1], {f is invariant under every variable permutation,f(X0,−X0,X2,…)=f(0,0,X2,…) if k≥2,Φ(f)=a.(\forall b\in W_k,\ ab=ba) \quad\Longleftrightarrow\quad \exists f\in C[X_0,\ldots,X_{k-1}],\ \begin{cases} f\text{ is invariant under every variable permutation},\\ f(X_0,-X_0,X_2,\ldots)=f(0,0,X_2,\ldots)\text{ if }k\ge2,\\ \Phi(f)=a. \end{cases}(∀b∈Wk​, ab=ba)⟺∃f∈C[X0​,…,Xk−1​], ⎩⎨⎧​f is invariant under every variable permutation,f(X0​,−X0​,X2​,…)=f(0,0,X2​,…) if k≥2,Φ(f)=a.​

For k<2k<2k<2, the substitution condition is vacuous; for k=0k=0k=0, polynomial evaluation uses the empty product 111.

QAlgorithms.Papers.Independent.Intakenext100.P34.DFree

For a commutative ring CCC and every natural number kkk, Dfree(C,k)D_{\mathrm{free}}(C,k)Dfree​(C,k) is the free associative unital CCC-algebra on formal generators TwT_wTw​ indexed by permutations www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, two formal generators Kfalse,KtrueK_{\mathrm{false}},K_{\mathrm{true}}Kfalse​,Ktrue​, and formal generators YjY_jYj​ indexed by j∈{0,…,k−1}j\in\{0,\ldots,k-1\}j∈{0,…,k−1}. Its elements are finite CCC-linear combinations of words in these generators; no additional relations among these generators are imposed. In particular, TidT_{\mathrm{id}}Tid​ is a formal generator, and for k=0k=0k=0 the generating alphabet still contains TidT_{\mathrm{id}}Tid​ and the two KKK generators.

QAlgorithms.Papers.Independent.Intakenext100.P34.DLetter

For every natural number kkk, DLetter⁡(k)\operatorname{DLetter}(k)DLetter(k) is the disjoint union of three types of formal letters: a letter perm⁡(w)\operatorname{perm}(w)perm(w) for each permutation www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, a letter kappa⁡(b)\operatorname{kappa}(b)kappa(b) for each Boolean value b∈{false,true}b\in\{\mathrm{false},\mathrm{true}\}b∈{false,true}, and a letter y⁡(j)\operatorname{y}(j)y(j) for each j∈{0,…,k−1}j\in\{0,\ldots,k-1\}j∈{0,…,k−1}. Each constructor is injective, and letters from different constructors are distinct. For k=0k=0k=0, there are no y⁡\operatorname{y}y letters, while the unique permutation of the empty set still supplies a perm⁡\operatorname{perm}perm letter.

QAlgorithms.Papers.Independent.Intakenext100.P34.DParams

Over the commutative coefficient ring CCC, a value of this structure consists of a specified unit u∈C×u\in C^\timesu∈C× together with a proof that its underlying element equals 222, an element ε∈C\varepsilon\in Cε∈C together with a proof of the disjunction ε=1\varepsilon=1ε=1 or ε=−1\varepsilon=-1ε=−1, an arbitrary sequence μ:N→C\mu:\mathbb N\to Cμ:N→C, and an optional ordered pair of elements of CCC. The optional pair is either absent or has the form (a,b)∈C×C(a,b)\in C\times C(a,b)∈C×C. The structure imposes no further condition on the sequence or on this optional pair, and the two alternatives for ε\varepsilonε need not be distinct in CCC.

QAlgorithms.Papers.Independent.Intakenext100.P34.DRel

For a commutative ring CCC and a natural number kkk, work in the free associative unital CCC-algebra on generators TwT_wTw​ for permutations www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, generators KbK_bKb​ for Boolean values bbb, and generators YjY_jYj​ for 0≤j<k0\le j<k0≤j<k. Write sis_isi​ for the permutation exchanging iii and i+1i+1i+1, and put Δi=Yi+1−TsiYiTsi\Delta_i=Y_{i+1}-T_{s_i}Y_iT_{s_i}Δi​=Yi+1​−Tsi​​Yi​Tsi​​ whenever 0≤i<k−10\le i<k-10≤i<k−1, with subtraction in the index bound truncated at zero. The binary relation R=DRel⁡(C,k)\mathcal R=\operatorname{DRel}(C,k)R=DRel(C,k) is inductively generated by precisely the following ordered pairs, universally quantified over the indices and permutations indicated:

(Tid,1)∈R;(TwTv,Twv)∈Rfor all permutations w,v;(YiYj,YjYi)∈Rfor 0≤i,j<k;(KfalseKtrue,KtrueKfalse)∈R;(KbYj,YjKb)∈Rfor every Boolean b, 0≤j<k;(KfalseTsi,TsiKfalse)∈Rfor 0≤i<k−1;(KtrueTsiKtrueTsi,TsiKtrueTsiKtrue)∈Rfor 0≤i<k−1, i=0;(KtrueTsi,TsiKtrue)∈Rfor 0≤i<k−1, i≠0;(Tsi(Yi+Yi+1),(Yi+Yi+1)Tsi)∈Rfor 0≤i<k−1;(YjTsi,TsiYj)∈Rfor 0≤i<k−1, 0≤j<k, j≠i, j≠i+1;(TsiTsjΔiTsjTsi,Δj)∈Rfor 0≤i,j<k−1, j=i+1.\begin{aligned} &(T_{\mathrm{id}},1)\in\mathcal R;\\ &(T_wT_v,T_{wv})\in\mathcal R &&\text{for all permutations }w,v;\\ &(Y_iY_j,Y_jY_i)\in\mathcal R &&\text{for }0\le i,j<k;\\ &(K_{\mathrm{false}}K_{\mathrm{true}}, K_{\mathrm{true}}K_{\mathrm{false}})\in\mathcal R;\\ &(K_bY_j,Y_jK_b)\in\mathcal R &&\text{for every Boolean }b,\ 0\le j<k;\\ &(K_{\mathrm{false}}T_{s_i},T_{s_i}K_{\mathrm{false}})\in\mathcal R &&\text{for }0\le i<k-1;\\ &(K_{\mathrm{true}}T_{s_i}K_{\mathrm{true}}T_{s_i}, T_{s_i}K_{\mathrm{true}}T_{s_i}K_{\mathrm{true}})\in\mathcal R &&\text{for }0\le i<k-1,\ i=0;\\ &(K_{\mathrm{true}}T_{s_i},T_{s_i}K_{\mathrm{true}})\in\mathcal R &&\text{for }0\le i<k-1,\ i\ne0;\\ &(T_{s_i}(Y_i+Y_{i+1}),(Y_i+Y_{i+1})T_{s_i})\in\mathcal R &&\text{for }0\le i<k-1;\\ &(Y_jT_{s_i},T_{s_i}Y_j)\in\mathcal R &&\text{for }0\le i<k-1,\ 0\le j<k,\ j\ne i,\ j\ne i+1;\\ &(T_{s_i}T_{s_j}\Delta_iT_{s_j}T_{s_i},\Delta_j)\in\mathcal R &&\text{for }0\le i,j<k-1,\ j=i+1. \end{aligned}​(Tid​,1)∈R;(Tw​Tv​,Twv​)∈R(Yi​Yj​,Yj​Yi​)∈R(Kfalse​Ktrue​,Ktrue​Kfalse​)∈R;(Kb​Yj​,Yj​Kb​)∈R(Kfalse​Tsi​​,Tsi​​Kfalse​)∈R(Ktrue​Tsi​​Ktrue​Tsi​​,Tsi​​Ktrue​Tsi​​Ktrue​)∈R(Ktrue​Tsi​​,Tsi​​Ktrue​)∈R(Tsi​​(Yi​+Yi+1​),(Yi​+Yi+1​)Tsi​​)∈R(Yj​Tsi​​,Tsi​​Yj​)∈R(Tsi​​Tsj​​Δi​Tsj​​Tsi​​,Δj​)∈R​​for all permutations w,v;for 0≤i,j<k;for every Boolean b, 0≤j<k;for 0≤i<k−1;for 0≤i<k−1, i=0;for 0≤i<k−1, i=0;for 0≤i<k−1;for 0≤i<k−1, 0≤j<k, j=i, j=i+1;for 0≤i,j<k−1, j=i+1.​

Here wvwvwv is permutation composition, acting by w(v(x))w(v(x))w(v(x)). These are pairs in a relation on the free algebra; reflexive, symmetric, transitive, additive, and multiplicative closure are not additional constructors of this relation. All clauses requiring an adjacent index have no instances for k=0k=0k=0 or k=1k=1k=1, and the last clause has no instances for k<3k<3k<3.

QAlgorithms.Papers.Independent.Intakenext100.P34.DW

For the commutative coefficient ring CCC, a natural number kkk, and parameters PPP consisting of a unit representing 222, a sign ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence μ:N→C\mu:\mathbb N\to Cμ:N→C, and an optional scalar pair, this abbreviation denotes the following ring quotient. Start with the free associative unital CCC-algebra on TwT_wTw​, for all permutations of I={0,…,k−1}I=\{0,\ldots,k-1\}I={0,…,k−1}, two generators K0,K1K_0,K_1K0​,K1​, and generators YjY_jYj​, for j∈Ij\in Ij∈I. For 0≤i<k−10\le i<k-10≤i<k−1, let sis_isi​ exchange iii and i+1i+1i+1, and abbreviate

Gi=Yi+1−TsiYiTsi,Ei=1+TsiYi−Yi+1Tsi.G_i=Y_{i+1}-T_{s_i}Y_iT_{s_i}, \qquad E_i=1+T_{s_i}Y_i-Y_{i+1}T_{s_i}.Gi​=Yi+1​−Tsi​​Yi​Tsi​​,Ei​=1+Tsi​​Yi​−Yi+1​Tsi​​.

Take the quotient by the smallest ring congruence imposing

Tid=1,TwTv=Twv,YpYq=YqYp,K0K1=K1K0,KbYj=YjKb,K0Tsi=TsiK0,K1Ts0K1Ts0=Ts0K1Ts0K1,K1Tsi=TsiK1(i≠0),Tsi(Yi+Yi+1)=(Yi+Yi+1)Tsi,YjTsi=TsiYj(j∉{i,i+1}),TsiTsi+1GiTsi+1Tsi=Gi+1,EiTsi=εEi,TsiEi=εEi,EiTsjEi=εEi(i+1=j or j+1=i),E0Y0nE0=μnE0(n∈N),Ei(Yi+Yi+1)=0,(Yi+Yi+1)Ei=0.\begin{gathered} T_{\mathrm{id}}=1,\qquad T_wT_v=T_{wv},\qquad Y_pY_q=Y_qY_p,\qquad K_0K_1=K_1K_0,\qquad K_bY_j=Y_jK_b,\\ K_0T_{s_i}=T_{s_i}K_0,\qquad K_1T_{s_0}K_1T_{s_0}=T_{s_0}K_1T_{s_0}K_1,\qquad K_1T_{s_i}=T_{s_i}K_1\quad(i\ne0),\\ T_{s_i}(Y_i+Y_{i+1})=(Y_i+Y_{i+1})T_{s_i},\qquad Y_jT_{s_i}=T_{s_i}Y_j\quad(j\notin\{i,i+1\}),\\ T_{s_i}T_{s_{i+1}}G_iT_{s_{i+1}}T_{s_i}=G_{i+1},\\ E_iT_{s_i}=\varepsilon E_i,\qquad T_{s_i}E_i=\varepsilon E_i,\qquad E_iT_{s_j}E_i=\varepsilon E_i\quad(i+1=j\ \text{or}\ j+1=i),\\ E_0Y_0^nE_0=\mu_nE_0\quad(n\in\mathbb N),\qquad E_i(Y_i+Y_{i+1})=0,\qquad (Y_i+Y_{i+1})E_i=0. \end{gathered}Tid​=1,Tw​Tv​=Twv​,Yp​Yq​=Yq​Yp​,K0​K1​=K1​K0​,Kb​Yj​=Yj​Kb​,K0​Tsi​​=Tsi​​K0​,K1​Ts0​​K1​Ts0​​=Ts0​​K1​Ts0​​K1​,K1​Tsi​​=Tsi​​K1​(i=0),Tsi​​(Yi​+Yi+1​)=(Yi​+Yi+1​)Tsi​​,Yj​Tsi​​=Tsi​​Yj​(j∈/{i,i+1}),Tsi​​Tsi+1​​Gi​Tsi+1​​Tsi​​=Gi+1​,Ei​Tsi​​=εEi​,Tsi​​Ei​=εEi​,Ei​Tsj​​Ei​=εEi​(i+1=j or j+1=i),E0​Y0n​E0​=μn​E0​(n∈N),Ei​(Yi​+Yi+1​)=0,(Yi​+Yi+1​)Ei​=0.​

Here b∈{0,1}b\in\{0,1\}b∈{0,1}, coefficients are inserted through the structural map from CCC, and all indexed equations are imposed only when their indices exist. If the optional scalar pair is (a,b)(a,b)(a,b), also impose K0=aK_0=aK0​=a and K1=bK_1=bK1​=b; if it is absent, impose neither of these additional equations. The compression equation includes n=0n=0n=0. The definition allows k=0k=0k=0 and k=1k=1k=1, when every equation requiring an adjacent index is absent, and it imposes no admissibility condition on μ\muμ.

QAlgorithms.Papers.Independent.Intakenext100.P34.DWRel

Let CCC be the commutative coefficient ring, let PPP consist of a specified unit uuu with underlying element 222, an element ε\varepsilonε satisfying ε=1\varepsilon=1ε=1 or ε=−1\varepsilon=-1ε=−1, a sequence μ:N→C\mu:\mathbb N\to Cμ:N→C, and an optional scalar pair, and let k∈Nk\in\mathbb Nk∈N. Put I={0,…,k−1}I=\{0,\ldots,k-1\}I={0,…,k−1}, let sis_isi​ exchange iii and i+1i+1i+1 for 0≤i<k−10\le i<k-10≤i<k−1, and work in the free associative unital CCC-algebra on TwT_wTw​, for permutations www of III, on K0,K1K_0,K_1K0​,K1​, and on YjY_jYj​, for j∈Ij\in Ij∈I. Write [c][c][c] for the structural image of c∈Cc\in Cc∈C, and define

Gi=Yi+1−TsiYiTsi,Ei=1+TsiYi−Yi+1Tsi.G_i=Y_{i+1}-T_{s_i}Y_iT_{s_i}, \qquad E_i=1+T_{s_i}Y_i-Y_{i+1}T_{s_i}.Gi​=Yi+1​−Tsi​​Yi​Tsi​​,Ei​=1+Tsi​​Yi​−Yi+1​Tsi​​.

The declaration defines the least binary relation ⇝\rightsquigarrow⇝ on this free algebra containing the following ordered pairs:

Tid⇝1,TwTv⇝Twv,YpYq⇝YqYp,K0K1⇝K1K0,KbYj⇝YjKb,K0Tsi⇝TsiK0,K1Ts0K1Ts0⇝Ts0K1Ts0K1,K1Tsi⇝TsiK1(i≠0),Tsi(Yi+Yi+1)⇝(Yi+Yi+1)Tsi,YjTsi⇝TsiYj(j∉{i,i+1}),TsiTsi+1GiTsi+1Tsi⇝Gi+1,EiTsi⇝[ε]Ei,TsiEi⇝[ε]Ei,EiTsjEi⇝[ε]Ei(i+1=j or j+1=i),E0Y0nE0⇝[μn]E0(n∈N),Ei(Yi+Yi+1)⇝0,(Yi+Yi+1)Ei⇝0.\begin{gathered} T_{\mathrm{id}}\rightsquigarrow1,\qquad T_wT_v\rightsquigarrow T_{wv},\qquad Y_pY_q\rightsquigarrow Y_qY_p,\qquad K_0K_1\rightsquigarrow K_1K_0,\qquad K_bY_j\rightsquigarrow Y_jK_b,\\ K_0T_{s_i}\rightsquigarrow T_{s_i}K_0,\qquad K_1T_{s_0}K_1T_{s_0}\rightsquigarrow T_{s_0}K_1T_{s_0}K_1,\qquad K_1T_{s_i}\rightsquigarrow T_{s_i}K_1\quad(i\ne0),\\ T_{s_i}(Y_i+Y_{i+1})\rightsquigarrow (Y_i+Y_{i+1})T_{s_i},\qquad Y_jT_{s_i}\rightsquigarrow T_{s_i}Y_j \quad(j\notin\{i,i+1\}),\\ T_{s_i}T_{s_{i+1}}G_iT_{s_{i+1}}T_{s_i} \rightsquigarrow G_{i+1},\\ E_iT_{s_i}\rightsquigarrow[\varepsilon]E_i,\qquad T_{s_i}E_i\rightsquigarrow[\varepsilon]E_i,\\ E_iT_{s_j}E_i\rightsquigarrow[\varepsilon]E_i \quad(i+1=j\ \text{or}\ j+1=i),\\ E_0Y_0^nE_0\rightsquigarrow[\mu_n]E_0 \quad(n\in\mathbb N),\\ E_i(Y_i+Y_{i+1})\rightsquigarrow0,\qquad (Y_i+Y_{i+1})E_i\rightsquigarrow0. \end{gathered}Tid​⇝1,Tw​Tv​⇝Twv​,Yp​Yq​⇝Yq​Yp​,K0​K1​⇝K1​K0​,Kb​Yj​⇝Yj​Kb​,K0​Tsi​​⇝Tsi​​K0​,K1​Ts0​​K1​Ts0​​⇝Ts0​​K1​Ts0​​K1​,K1​Tsi​​⇝Tsi​​K1​(i=0),Tsi​​(Yi​+Yi+1​)⇝(Yi​+Yi+1​)Tsi​​,Yj​Tsi​​⇝Tsi​​Yj​(j∈/{i,i+1}),Tsi​​Tsi+1​​Gi​Tsi+1​​Tsi​​⇝Gi+1​,Ei​Tsi​​⇝[ε]Ei​,Tsi​​Ei​⇝[ε]Ei​,Ei​Tsj​​Ei​⇝[ε]Ei​(i+1=j or j+1=i),E0​Y0n​E0​⇝[μn​]E0​(n∈N),Ei​(Yi​+Yi+1​)⇝0,(Yi​+Yi+1​)Ei​⇝0.​

All indices range over their stated sets, b∈{0,1}b\in\{0,1\}b∈{0,1}, and each pair is included only when its adjacent indices exist. In addition, for every a,b∈Ca,b\in Ca,b∈C such that the optional scalar pair of PPP is exactly (a,b)(a,b)(a,b), it contains K0⇝[a]K_0\rightsquigarrow[a]K0​⇝[a] and K1⇝[b]K_1\rightsquigarrow[b]K1​⇝[b]. If that pair is absent, these last constructors supply no pairs. The compression pairs include n=0n=0n=0, yielding E02⇝[μ0]E0E_0^2\rightsquigarrow[\mu_0]E_0E02​⇝[μ0​]E0​. No reflexive, symmetric, transitive, or ring-congruence closure is part of this inductively defined relation itself. For k=0k=0k=0 or k=1k=1k=1, there are no adjacent indices and hence no pairs requiring them.

QAlgorithms.Papers.Independent.Intakenext100.P34.GBraid

For every commutative ring CCC and natural number kkk, this denotes the ring quotient of the free associative unital CCC-algebra on generators TwT_wTw​ for permutations www of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, κi\kappa_iκi​ for i∈Ik={∗}⊔{j^:j∈[k]}i\in I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}i∈Ik​={∗}⊔{j​:j∈[k]}, and Γij\Gamma_{ij}Γij​ for ordered distinct pairs in IkI_kIk​, imposing precisely the following generating equations and their consequences as ring equations. Write w⋅∗=∗w\cdot\ast=\astw⋅∗=∗ and w⋅j^=w(j)^w\cdot\widehat j=\widehat{w(j)}w⋅j​=w(j)​. For all permutations w,vw,vw,v and all indices satisfying the indicated restrictions, the equations are

Tid=1,TwTv=Twv,TwκiTw−1=κw⋅i,TwΓijTw−1=Γw⋅i,w⋅j(i≠j),κiκj=κjκi,κiΓℓm=Γℓmκi(ℓ≠m),Γij=Γji(i≠j),ΓprΓℓm=ΓℓmΓpr(p,r,ℓ,m pairwise distinct),Γij(Γir+Γjr)=(Γir+Γjr)Γij(i,j,r pairwise distinct).\begin{aligned} &T_{\mathrm{id}}=1,\qquad T_wT_v=T_{wv},\\ &T_w\kappa_iT_{w^{-1}}=\kappa_{w\cdot i},\\ &T_w\Gamma_{ij}T_{w^{-1}}=\Gamma_{w\cdot i,w\cdot j} && (i\ne j),\\ &\kappa_i\kappa_j=\kappa_j\kappa_i,\\ &\kappa_i\Gamma_{\ell m}=\Gamma_{\ell m}\kappa_i && (\ell\ne m),\\ &\Gamma_{ij}=\Gamma_{ji} && (i\ne j),\\ &\Gamma_{pr}\Gamma_{\ell m}=\Gamma_{\ell m}\Gamma_{pr} && (p,r,\ell,m\text{ pairwise distinct}),\\ &\Gamma_{ij}(\Gamma_{ir}+\Gamma_{jr}) =(\Gamma_{ir}+\Gamma_{jr})\Gamma_{ij} && (i,j,r\text{ pairwise distinct}). \end{aligned}​Tid​=1,Tw​Tv​=Twv​,Tw​κi​Tw−1​=κw⋅i​,Tw​Γij​Tw−1​=Γw⋅i,w⋅j​κi​κj​=κj​κi​,κi​Γℓm​=Γℓm​κi​Γij​=Γji​Γpr​Γℓm​=Γℓm​Γpr​Γij​(Γir​+Γjr​)=(Γir​+Γjr​)Γij​​​(i=j),(ℓ=m),(i=j),(p,r,ℓ,m pairwise distinct),(i,j,r pairwise distinct).​

The definition includes k=0k=0k=0; then there are no Γ\GammaΓ generators, and all conditions requiring distinct indices have no instances.

QAlgorithms.Papers.Independent.Intakenext100.P34.GFree

For every commutative ring CCC and natural number kkk, this denotes the free associative unital CCC-algebra whose generators are TwT_wTw​ for every permutation www of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, κi\kappa_iκi​ for every iii in Ik={∗}⊔{j^:j∈[k]}I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}Ik​={∗}⊔{j​:j∈[k]}, and Γij\Gamma_{ij}Γij​ for every ordered pair of distinct elements i,j∈Iki,j\in I_ki,j∈Ik​. No additional equations among these generators are imposed by this definition. In particular, opposite orders of a pair give separate generators. For k=0k=0k=0, the generators consist of TidT_{\mathrm{id}}Tid​ and κ∗\kappa_\astκ∗​.

QAlgorithms.Papers.Independent.Intakenext100.P34.GIndex

For every natural number kkk, this defines the index type as the disjoint union of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1} with one additional element. Write the additional element as ∗\ast∗ and the element corresponding to j∈[k]j\in[k]j∈[k] as j^\widehat jj​. Thus the index type has k+1k+1k+1 elements, and for k=0k=0k=0 it consists only of ∗\ast∗.

QAlgorithms.Papers.Independent.Intakenext100.P34.GLetter

For every natural number kkk, let Ik={∗}⊔{j^:j∈[k]}I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}Ik​={∗}⊔{j​:j∈[k]}, where [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}. This defines an alphabet with three disjoint kinds of letters: a letter indexed by each permutation of [k][k][k], a letter indexed by each element of IkI_kIk​, and a letter indexed by each ordered pair (i,j)∈Ik2(i,j)\in I_k^2(i,j)∈Ik2​ with i≠ji\ne ji=j. The two orders (i,j)(i,j)(i,j) and (j,i)(j,i)(j,i) index distinct letters. When k=0k=0k=0, there is one permutation letter, one letter of the second kind, and no letters of the third kind.

QAlgorithms.Papers.Independent.Intakenext100.P34.GRel

For every commutative ring CCC and natural number kkk, set [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1} and Ik={∗}⊔{j^:j∈[k]}I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}Ik​={∗}⊔{j​:j∈[k]}. In the free associative unital CCC-algebra with generators TwT_wTw​ for permutations www of [k][k][k], κi\kappa_iκi​ for i∈Iki\in I_ki∈Ik​, and Γij\Gamma_{ij}Γij​ for ordered distinct pairs in IkI_kIk​, extend the notation by Γii=0\Gamma_{ii}=0Γii​=0 and let w⋅∗=∗w\cdot\ast=\astw⋅∗=∗, w⋅j^=w(j)^w\cdot\widehat j=\widehat{w(j)}w⋅j​=w(j)​. This defines a binary relation consisting exactly of the following ordered pairs, for every choice of the displayed permutations and indices satisfying the stated restrictions:

(Tid,1),(TwTv,Twv),(TwκiTw−1,κw⋅i),(TwΓijTw−1,Γw⋅i,w⋅j)(i≠j),(κiκj,κjκi),(κiΓℓm,Γℓmκi)(ℓ≠m),(Γij,Γji)(i≠j),(ΓprΓℓm,ΓℓmΓpr)(p,r,ℓ,m pairwise distinct),(Γij(Γir+Γjr),(Γir+Γjr)Γij)(i,j,r pairwise distinct).\begin{aligned} &(T_{\mathrm{id}},1),\qquad (T_wT_v,T_{wv}),\\ &(T_w\kappa_iT_{w^{-1}},\kappa_{w\cdot i}),\\ &(T_w\Gamma_{ij}T_{w^{-1}},\Gamma_{w\cdot i,w\cdot j}) && (i\ne j),\\ &(\kappa_i\kappa_j,\kappa_j\kappa_i),\\ &(\kappa_i\Gamma_{\ell m},\Gamma_{\ell m}\kappa_i) && (\ell\ne m),\\ &(\Gamma_{ij},\Gamma_{ji}) && (i\ne j),\\ &(\Gamma_{pr}\Gamma_{\ell m},\Gamma_{\ell m}\Gamma_{pr}) && (p,r,\ell,m\text{ pairwise distinct}),\\ &(\Gamma_{ij}(\Gamma_{ir}+\Gamma_{jr}), (\Gamma_{ir}+\Gamma_{jr})\Gamma_{ij}) && (i,j,r\text{ pairwise distinct}). \end{aligned}​(Tid​,1),(Tw​Tv​,Twv​),(Tw​κi​Tw−1​,κw⋅i​),(Tw​Γij​Tw−1​,Γw⋅i,w⋅j​)(κi​κj​,κj​κi​),(κi​Γℓm​,Γℓm​κi​)(Γij​,Γji​)(Γpr​Γℓm​,Γℓm​Γpr​)(Γij​(Γir​+Γjr​),(Γir​+Γjr​)Γij​)​​(i=j),(ℓ=m),(i=j),(p,r,ℓ,m pairwise distinct),(i,j,r pairwise distinct).​

The definition itself supplies no additional closure rules for this relation. The parameter kkk may be zero, in which case IkI_kIk​ has only ∗\ast∗ and every clause requiring distinct indices has no instances.

QAlgorithms.Papers.Independent.Intakenext100.P34.Laurent

For a commutative ring CCC and any natural number kkk, including k=0k=0k=0, Laurent⁡(C,k)\operatorname{Laurent}(C,k)Laurent(C,k) denotes the additive monoid algebra of the group Zk\mathbb Z^kZk over CCC: its elements are finite sums

∑d∈Zkcdxd,xd=∏j=0k−1xjdj,\sum_{d\in\mathbb Z^k}c_d x^d,\qquad x^d=\prod_{j=0}^{k-1}x_j^{d_j},d∈Zk∑​cd​xd,xd=j=0∏k−1​xjdj​​,

with coefficients cd∈Cc_d\in Ccd​∈C, addition coefficientwise, and multiplication determined by xdxe=xd+ex^dx^e=x^{d+e}xdxe=xd+e. Thus it is the Laurent polynomial algebra in kkk commuting variables; for k=0k=0k=0, the exponent group has one element and this algebra is canonically CCC.

QAlgorithms.Papers.Independent.Intakenext100.P34.Wheel

For a commutative ring CCC, natural numbers k,rk,rk,r, a hypothesis 0<k0<k0<k, an arbitrary ζ∈C\zeta\in Cζ∈C, and a polynomial f∈C[X0,…,Xk−1]f\in C[X_0,\ldots,X_{k-1}]f∈C[X0​,…,Xk−1​], this predicate says that fff is invariant under every permutation of its variables and that

f(U0,…,Uk−1)=f(V0,…,Vk−1),Uj={ζjX0,j<r,Xj,j≥r,Vj={0,j<r,Xj,j≥r.f(U_0,\ldots,U_{k-1})=f(V_0,\ldots,V_{k-1}), \qquad U_j= \begin{cases} \zeta^jX_0,&j<r,\\ X_j,&j\ge r, \end{cases} \quad V_j= \begin{cases} 0,&j<r,\\ X_j,&j\ge r. \end{cases}f(U0​,…,Uk−1​)=f(V0​,…,Vk−1​),Uj​={ζjX0​,Xj​,​j<r,j≥r,​Vj​={0,Xj​,​j<r,j≥r.​

The equality is an equality of polynomials over CCC, with coefficients left unchanged by the substitutions. There is no requirement that r≤kr\le kr≤k or that ζ\zetaζ be a unit or a root of unity. For r=0r=0r=0, both substitutions are the identity, so only symmetry is required; for r≥kr\ge kr≥k, every variable is substituted, and the condition becomes f(X0,ζX0,…,ζk−1X0)=f(0,…,0)f(X_0,\zeta X_0,\ldots,\zeta^{k-1}X_0)=f(0,\ldots,0)f(X0​,ζX0​,…,ζk−1X0​)=f(0,…,0).

QAlgorithms.Papers.Independent.Intakenext100.P34.aCrossing

For a commutative ring CCC, an implicitly quantified natural number kkk, an index i∈Fin⁡(k−1)i\in\operatorname{Fin}(k-1)i∈Fin(k−1), and a Boolean bbb whose default value is false, this defines TibT_i^bTib​ to be the canonical image of the crossing letter (i,b)(i,b)(i,b) in the free associative unital CCC-algebra generated by all crossing letters (j,c)(j,c)(j,c) with j+1<kj+1<kj+1<k and Boolean ccc, and by the two Boolean-labelled flag letters. The parameter named “inverse” is just the Boolean label: this definition imposes no inverse relation between TifalseT_i^{\mathrm{false}}Tifalse​ and TitrueT_i^{\mathrm{true}}Titrue​. There is no permissible iii when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.aEval

Let CCC be a commutative ring, and let PPP specify units q,z,Qq,z,Qq,z,Q and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, with Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. For any natural number kkk, define WkW_kWk​ as the associative CCC-algebra generated by invertible T0,…,Tk−2,XT_0,\ldots,T_{k-2},XT0​,…,Tk−2​,X. Set

Er=1−Q−1(Tr−Tr−1),Yj=zTj−1⋯T0XT0⋯Tj−1,Y‾j=z−1Tj−1−1⋯T0−1X−1T0−1⋯Tj−1−1.E_r=1-Q^{-1}(T_r-T_r^{-1}),\quad Y_j=zT_{j-1}\cdots T_0XT_0\cdots T_{j-1},\quad \overline Y_j=z^{-1}T_{j-1}^{-1}\cdots T_0^{-1}X^{-1}T_0^{-1}\cdots T_{j-1}^{-1}.Er​=1−Q−1(Tr​−Tr−1​),Yj​=zTj−1​⋯T0​XT0​⋯Tj−1​,Yj​=z−1Tj−1−1​⋯T0−1​X−1T0−1​⋯Tj−1−1​.

The quotient relations, for all valid indices, are

TrTs=TsTr (∣r−s∣≠1),TrTr+1Tr=Tr+1TrTr+1,XT0XT0=T0XT0X,XTr=TrX (r>0),ErTrδ=TrδEr=z−δEr,ErTsδEr=zδEr (∣r−s∣=1, δ=±1),E0Y0[ℓ]E0=ωℓE0 (ℓ∈Z),ErYrYr+1=Er=YrYr+1Er,\begin{gathered} T_rT_s=T_sT_r\ (|r-s|\ne1),\qquad T_rT_{r+1}T_r=T_{r+1}T_rT_{r+1},\\ XT_0XT_0=T_0XT_0X,\qquad XT_r=T_rX\ (r>0),\\ E_rT_r^\delta=T_r^\delta E_r=z^{-\delta}E_r,\qquad E_rT_s^\delta E_r=z^\delta E_r \ (|r-s|=1,\ \delta=\pm1),\\ E_0Y_0^{[\ell]}E_0=\omega_\ell E_0\ (\ell\in\mathbb Z),\qquad E_rY_rY_{r+1}=E_r=Y_rY_{r+1}E_r, \end{gathered}Tr​Ts​=Ts​Tr​ (∣r−s∣=1),Tr​Tr+1​Tr​=Tr+1​Tr​Tr+1​,XT0​XT0​=T0​XT0​X,XTr​=Tr​X (r>0),Er​Trδ​=Trδ​Er​=z−δEr​,Er​Tsδ​Er​=zδEr​ (∣r−s∣=1, δ=±1),E0​Y0[ℓ]​E0​=ωℓ​E0​ (ℓ∈Z),Er​Yr​Yr+1​=Er​=Yr​Yr+1​Er​,​

where Yj[ℓ]=YjℓY_j^{[\ell]}=Y_j^\ellYj[ℓ]​=Yjℓ​ when ℓ≥0\ell\ge0ℓ≥0, and Yj[ℓ]=Y‾j−ℓY_j^{[\ell]}=\overline Y_j^{-\ell}Yj[ℓ]​=Yj−ℓ​ when ℓ<0\ell<0ℓ<0. For a Laurent polynomial f=∑dcdxdf=\sum_d c_dx^df=∑d​cd​xd in kkk commuting variables, the function aEvalaEvalaEval is the ordered evaluation

aEval(P,k,f)=∑d: cd≠0ι(cd) Y0[d0]Y1[d1]⋯Yk−1[dk−1]∈Wk,aEval(P,k,f)=\sum_{d:\,c_d\ne0}\iota(c_d)\, Y_0^{[d_0]}Y_1^{[d_1]}\cdots Y_{k-1}^{[d_{k-1}]}\in W_k,aEval(P,k,f)=d:cd​=0∑​ι(cd​)Y0[d0​]​Y1[d1​]​⋯Yk−1[dk−1​]​∈Wk​,

where ι:C→Wk\iota:C\to W_kι:C→Wk​ is the scalar map. The sum is finite, and the factors are multiplied in increasing index order. For k=0k=0k=0, the product is empty and the function sends the constant Laurent polynomial ccc to ι(c)\iota(c)ι(c); the target W0W_0W0​ still has its invertible generator XXX.

QAlgorithms.Papers.Independent.Intakenext100.P34.aMomentAt

Let CCC be a commutative ring, and let PPP specify units q,z,Qq,z,Qq,z,Q and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, with Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. Fix natural numbers n,Nn,Nn,N, a witness h:n≤Nh:n\le Nh:n≤N, and an integer ℓ\ellℓ. The target WNW_NWN​ is the associative CCC-algebra generated by invertible T0,…,TN−2,XT_0,\ldots,T_{N-2},XT0​,…,TN−2​,X; define

Er=1−Q−1(Tr−Tr−1),Yj=zTj−1⋯T0XT0⋯Tj−1,Y‾j=z−1Tj−1−1⋯T0−1X−1T0−1⋯Tj−1−1.E_r=1-Q^{-1}(T_r-T_r^{-1}),\quad Y_j=zT_{j-1}\cdots T_0XT_0\cdots T_{j-1},\quad \overline Y_j=z^{-1}T_{j-1}^{-1}\cdots T_0^{-1}X^{-1}T_0^{-1}\cdots T_{j-1}^{-1}.Er​=1−Q−1(Tr​−Tr−1​),Yj​=zTj−1​⋯T0​XT0​⋯Tj−1​,Yj​=z−1Tj−1−1​⋯T0−1​X−1T0−1​⋯Tj−1−1​.

Its defining relations, for all valid indices, are

TrTs=TsTr (∣r−s∣≠1),TrTr+1Tr=Tr+1TrTr+1,XT0XT0=T0XT0X,XTr=TrX (r>0),ErTrδ=TrδEr=z−δEr,ErTsδEr=zδEr (∣r−s∣=1, δ=±1),E0Y0[m]E0=ωmE0 (m∈Z),ErYrYr+1=Er=YrYr+1Er,\begin{gathered} T_rT_s=T_sT_r\ (|r-s|\ne1),\quad T_rT_{r+1}T_r=T_{r+1}T_rT_{r+1},\\ XT_0XT_0=T_0XT_0X,\quad XT_r=T_rX\ (r>0),\\ E_rT_r^\delta=T_r^\delta E_r=z^{-\delta}E_r,\quad E_rT_s^\delta E_r=z^\delta E_r \ (|r-s|=1,\ \delta=\pm1),\\ E_0Y_0^{[m]}E_0=\omega_mE_0\ (m\in\mathbb Z),\quad E_rY_rY_{r+1}=E_r=Y_rY_{r+1}E_r, \end{gathered}Tr​Ts​=Ts​Tr​ (∣r−s∣=1),Tr​Tr+1​Tr​=Tr+1​Tr​Tr+1​,XT0​XT0​=T0​XT0​X,XTr​=Tr​X (r>0),Er​Trδ​=Trδ​Er​=z−δEr​,Er​Tsδ​Er​=zδEr​ (∣r−s∣=1, δ=±1),E0​Y0[m]​E0​=ωm​E0​ (m∈Z),Er​Yr​Yr+1​=Er​=Yr​Yr+1​Er​,​

where Yj[m]=YjmY_j^{[m]}=Y_j^mYj[m]​=Yjm​ for m≥0m\ge0m≥0 and Y‾j−m\overline Y_j^{-m}Yj−m​ for m<0m<0m<0. To define the Laurent polynomial to be evaluated, work first in Rn=C[x0±1,…,xn−1±1]R_n=C[x_0^{\pm1},\ldots,x_{n-1}^{\pm1}]Rn​=C[x0±1​,…,xn−1±1​], the algebra of finitely supported integer-exponent monomials, and set

G=∑r≥1u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj=(1−xju)2(1−q−2xj−1u)(1−q2xj−1u)(1−xj−1u)2(1−q2xju)(1−q−2xju),Sn=(∑m≥0ωmum+z−1Q−1−H)∏j=0n−1Rj.\begin{gathered} G=\sum_{r\ge1}u^{2r},\quad H=1+G,\quad F=1+(2-q^2-q^{-2})(G+G^2),\\ R_j= \frac{(1-x_ju)^2(1-q^{-2}x_j^{-1}u)(1-q^2x_j^{-1}u)} {(1-x_j^{-1}u)^2(1-q^2x_ju)(1-q^{-2}x_ju)},\\ S_n=\left(\sum_{m\ge0}\omega_mu^m+z^{-1}Q^{-1}-H\right) \prod_{j=0}^{n-1}R_j. \end{gathered}G=r≥1∑​u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj​=(1−xj−1​u)2(1−q2xj​u)(1−q−2xj​u)(1−xj​u)2(1−q−2xj−1​u)(1−q2xj−1​u)​,Sn​=(m≥0∑​ωm​um+z−1Q−1−H)j=0∏n−1​Rj​.​

Scalars here are mapped into RnR_nRn​; all inverses are formal series inverses, and SnS_nSn​ has unit constant coefficient zQ−1zQ^{-1}zQ−1. Define

μn,ℓ={ωℓ,n=0,[uℓ](Sn−z−1Q−1+H),n>0, ℓ≥0,[u−ℓ](zQ−1+H−Q−2FSn−1),n>0, ℓ<0.\mu_{n,\ell}= \begin{cases} \omega_\ell,&n=0,\\ [u^\ell](S_n-z^{-1}Q^{-1}+H),&n>0,\ \ell\ge0,\\ [u^{-\ell}](zQ^{-1}+H-Q^{-2}FS_n^{-1}),&n>0,\ \ell<0. \end{cases}μn,ℓ​=⎩⎨⎧​ωℓ​,[uℓ](Sn​−z−1Q−1+H),[u−ℓ](zQ−1+H−Q−2FSn−1​),​n=0,n>0, ℓ≥0,n>0, ℓ<0.​

If μn,ℓ=∑dcdxd\mu_{n,\ell}=\sum_dc_dx^dμn,ℓ​=∑d​cd​xd, then

aMomentAt(P,n,N,ℓ,h)=∑d: cd≠0ιN(cd)Y0[d0]⋯Yn−1[dn−1]∈WN,aMomentAt(P,n,N,\ell,h) =\sum_{d:\,c_d\ne0}\iota_N(c_d) Y_0^{[d_0]}\cdots Y_{n-1}^{[d_{n-1}]}\in W_N,aMomentAt(P,n,N,ℓ,h)=d:cd​=0∑​ιN​(cd​)Y0[d0​]​⋯Yn−1[dn−1​]​∈WN​,

where ιN:C→WN\iota_N:C\to W_NιN​:C→WN​ is the scalar map and the factors occur in increasing index order. The witness hhh allows each index below nnn to be used at level NNN. For n=0n=0n=0, including N=0N=0N=0, this value is simply ιN(ωℓ)\iota_N(\omega_\ell)ιN​(ωℓ​).

QAlgorithms.Papers.Independent.Intakenext100.P34.aMomentPolynomial

Let CCC be a commutative ring, and let PPP consist of units q,z,Qq,z,Qq,z,Q and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. For any natural number nnn and any integer ℓ\ellℓ, the value aMomentPolynomial(P,n,ℓ)aMomentPolynomial(P,n,\ell)aMomentPolynomial(P,n,ℓ) lies in the Laurent polynomial algebra Rn=C[x0±1,…,xn−1±1]R_n=C[x_0^{\pm1},\ldots,x_{n-1}^{\pm1}]Rn​=C[x0±1​,…,xn−1±1​], whose monomials have integer exponent vectors and whose elements have finite support. Write c:C→Rnc:C\to R_nc:C→Rn​ for the scalar map and identify scalar coefficients with their images. Define in Rn[[u]]R_n[[u]]Rn​[[u]]

G=∑r≥1u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj=(1−xju)2(1−q−2xj−1u)(1−q2xj−1u)(1−xj−1u)2(1−q2xju)(1−q−2xju),Sn=(∑m≥0c(ωm)um+z−1Q−1−H)∏j=0n−1Rj,Pn+=Sn−z−1Q−1+H,Pn−=zQ−1+H−Q−2FSn−1.\begin{gathered} G=\sum_{r\ge1}u^{2r},\qquad H=1+G,\qquad F=1+(2-q^2-q^{-2})(G+G^2),\\ R_j= \frac{(1-x_ju)^2(1-q^{-2}x_j^{-1}u)(1-q^2x_j^{-1}u)} {(1-x_j^{-1}u)^2(1-q^2x_ju)(1-q^{-2}x_ju)},\\ S_n=\left(\sum_{m\ge0}c(\omega_m)u^m+z^{-1}Q^{-1}-H\right) \prod_{j=0}^{n-1}R_j,\\ P_n^+=S_n-z^{-1}Q^{-1}+H,\qquad P_n^-=zQ^{-1}+H-Q^{-2}F S_n^{-1}. \end{gathered}G=r≥1∑​u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj​=(1−xj−1​u)2(1−q2xj​u)(1−q−2xj​u)(1−xj​u)2(1−q−2xj−1​u)(1−q2xj−1​u)​,Sn​=(m≥0∑​c(ωm​)um+z−1Q−1−H)j=0∏n−1​Rj​,Pn+​=Sn​−z−1Q−1+H,Pn−​=zQ−1+H−Q−2FSn−1​.​

All displayed scalar terms are constant series. The ratio denominators have constant coefficient 111, and SnS_nSn​ has the unit constant coefficient c(zQ−1)c(zQ^{-1})c(zQ−1); the inverse of SnS_nSn​ uses that unit. With [um][u^m][um] denoting coefficient extraction, the definition is

aMomentPolynomial(P,n,ℓ)={c(ωℓ),n=0,[uℓ]Pn+,n>0, ℓ≥0,[u−ℓ]Pn−,n>0, ℓ<0.aMomentPolynomial(P,n,\ell)= \begin{cases} c(\omega_\ell),&n=0,\\ [u^\ell]P_n^+,&n>0,\ \ell\ge0,\\ [u^{-\ell}]P_n^-,&n>0,\ \ell<0. \end{cases}aMomentPolynomial(P,n,ℓ)=⎩⎨⎧​c(ωℓ​),[uℓ]Pn+​,[u−ℓ]Pn−​,​n=0,n>0, ℓ≥0,n>0, ℓ<0.​

In particular, ℓ=0\ell=0ℓ=0 uses the positive-series branch when n>0n>0n>0.

QAlgorithms.Papers.Independent.Intakenext100.P34.aMomentSeries

Let CCC be a commutative ring, and let PPP specify units q,z,Qq,z,Qq,z,Q and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, with Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. Fix natural numbers n,Nn,Nn,N, a witness h:n≤Nh:n\le Nh:n≤N, and a Boolean bbb, defaulting to false. Let WNW_NWN​ be the associative CCC-algebra on invertible T0,…,TN−2,XT_0,\ldots,T_{N-2},XT0​,…,TN−2​,X, with

Er=1−Q−1(Tr−Tr−1),Yj=zTj−1⋯T0XT0⋯Tj−1,Y‾j=z−1Tj−1−1⋯T0−1X−1T0−1⋯Tj−1−1,E_r=1-Q^{-1}(T_r-T_r^{-1}),\quad Y_j=zT_{j-1}\cdots T_0XT_0\cdots T_{j-1},\quad \overline Y_j=z^{-1}T_{j-1}^{-1}\cdots T_0^{-1}X^{-1}T_0^{-1}\cdots T_{j-1}^{-1},Er​=1−Q−1(Tr​−Tr−1​),Yj​=zTj−1​⋯T0​XT0​⋯Tj−1​,Yj​=z−1Tj−1−1​⋯T0−1​X−1T0−1​⋯Tj−1−1​,

and relations

TrTs=TsTr (∣r−s∣≠1),TrTr+1Tr=Tr+1TrTr+1,XT0XT0=T0XT0X,XTr=TrX (r>0),ErTrδ=TrδEr=z−δEr,ErTsδEr=zδEr (∣r−s∣=1, δ=±1),E0Y0[m]E0=ωmE0 (m∈Z),ErYrYr+1=Er=YrYr+1Er,\begin{gathered} T_rT_s=T_sT_r\ (|r-s|\ne1),\quad T_rT_{r+1}T_r=T_{r+1}T_rT_{r+1},\\ XT_0XT_0=T_0XT_0X,\quad XT_r=T_rX\ (r>0),\\ E_rT_r^\delta=T_r^\delta E_r=z^{-\delta}E_r,\quad E_rT_s^\delta E_r=z^\delta E_r \ (|r-s|=1,\ \delta=\pm1),\\ E_0Y_0^{[m]}E_0=\omega_mE_0\ (m\in\mathbb Z),\quad E_rY_rY_{r+1}=E_r=Y_rY_{r+1}E_r, \end{gathered}Tr​Ts​=Ts​Tr​ (∣r−s∣=1),Tr​Tr+1​Tr​=Tr+1​Tr​Tr+1​,XT0​XT0​=T0​XT0​X,XTr​=Tr​X (r>0),Er​Trδ​=Trδ​Er​=z−δEr​,Er​Tsδ​Er​=zδEr​ (∣r−s∣=1, δ=±1),E0​Y0[m]​E0​=ωm​E0​ (m∈Z),Er​Yr​Yr+1​=Er​=Yr​Yr+1​Er​,​

for all valid indices, where Yj[m]=YjmY_j^{[m]}=Y_j^mYj[m]​=Yjm​ for m≥0m\ge0m≥0 and Y‾j−m\overline Y_j^{-m}Yj−m​ for m<0m<0m<0. Define Laurent polynomials μn,m\mu_{n,m}μn,m​ in Rn=C[x0±1,…,xn−1±1]R_n=C[x_0^{\pm1},\ldots,x_{n-1}^{\pm1}]Rn​=C[x0±1​,…,xn−1±1​], the algebra of finite sums of integer-exponent monomials, by putting

G=∑r≥1u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj=(1−xju)2(1−q−2xj−1u)(1−q2xj−1u)(1−xj−1u)2(1−q2xju)(1−q−2xju),Sn=(∑r≥0ωrur+z−1Q−1−H)∏j=0n−1Rj,μn,m={ωm,n=0,[um](Sn−z−1Q−1+H),n>0, m≥0,[u−m](zQ−1+H−Q−2FSn−1),n>0, m<0.\begin{gathered} G=\sum_{r\ge1}u^{2r},\quad H=1+G,\quad F=1+(2-q^2-q^{-2})(G+G^2),\\ R_j= \frac{(1-x_ju)^2(1-q^{-2}x_j^{-1}u)(1-q^2x_j^{-1}u)} {(1-x_j^{-1}u)^2(1-q^2x_ju)(1-q^{-2}x_ju)},\\ S_n=\left(\sum_{r\ge0}\omega_ru^r+z^{-1}Q^{-1}-H\right) \prod_{j=0}^{n-1}R_j,\qquad \mu_{n,m}= \begin{cases} \omega_m,&n=0,\\ [u^m](S_n-z^{-1}Q^{-1}+H),&n>0,\ m\ge0,\\ [u^{-m}](zQ^{-1}+H-Q^{-2}FS_n^{-1}),&n>0,\ m<0. \end{cases} \end{gathered}G=r≥1∑​u2r,H=1+G,F=1+(2−q2−q−2)(G+G2),Rj​=(1−xj−1​u)2(1−q2xj​u)(1−q−2xj​u)(1−xj​u)2(1−q−2xj−1​u)(1−q2xj−1​u)​,Sn​=(r≥0∑​ωr​ur+z−1Q−1−H)j=0∏n−1​Rj​,μn,m​=⎩⎨⎧​ωm​,[um](Sn​−z−1Q−1+H),[u−m](zQ−1+H−Q−2FSn−1​),​n=0,n>0, m≥0,n>0, m<0.​​

Scalars are mapped into RnR_nRn​, ratio denominators have constant coefficient 111, and Sn−1S_n^{-1}Sn−1​ is the formal inverse using its unit constant coefficient zQ−1zQ^{-1}zQ−1. For μn,m=∑dcdxd\mu_{n,m}=\sum_dc_dx^dμn,m​=∑d​cd​xd, let

Mn,mN=∑d: cd≠0ιN(cd)Y0[d0]⋯Yn−1[dn−1],M^N_{n,m}=\sum_{d:\,c_d\ne0}\iota_N(c_d) Y_0^{[d_0]}\cdots Y_{n-1}^{[d_{n-1}]},Mn,mN​=d:cd​=0∑​ιN​(cd​)Y0[d0​]​⋯Yn−1[dn−1​]​,

with factors in increasing order and ιN:C→WN\iota_N:C\to W_NιN​:C→WN​ the scalar map. Then the definition is

aMomentSeries(P,n,N,h,b)={∑ℓ≥0Mn,ℓNuℓ,b=false,∑ℓ≥0Mn,−ℓNuℓ,b=true.aMomentSeries(P,n,N,h,b)= \begin{cases} \displaystyle\sum_{\ell\ge0}M^N_{n,\ell}u^\ell,&b=\mathrm{false},\\[2mm] \displaystyle\sum_{\ell\ge0}M^N_{n,-\ell}u^\ell,&b=\mathrm{true}. \end{cases}aMomentSeries(P,n,N,h,b)=⎩⎨⎧​ℓ≥0∑​Mn,ℓN​uℓ,ℓ≥0∑​Mn,−ℓN​uℓ,​b=false,b=true.​

Both choices use Mn,0NM^N_{n,0}Mn,0N​ as their constant coefficient. When n=0n=0n=0, these series are respectively ∑ℓ≥0ιN(ωℓ)uℓ\sum_{\ell\ge0}\iota_N(\omega_\ell)u^\ell∑ℓ≥0​ιN​(ωℓ​)uℓ and ∑ℓ≥0ιN(ω−ℓ)uℓ\sum_{\ell\ge0}\iota_N(\omega_{-\ell})u^\ell∑ℓ≥0​ιN​(ω−ℓ​)uℓ; N=0N=0N=0 is allowed.

QAlgorithms.Papers.Independent.Intakenext100.P34.aRatio

For any ring AAA, not necessarily commutative, and any four elements q,q~,y,y~∈Aq,\widetilde q,y,\widetilde y\in Aq,q​,y,y​∈A, the series aRatio(q,q~,y,y~)∈A[[u]]aRatio(q,\widetilde q,y,\widetilde y)\in A[[u]]aRatio(q,q​,y,y​)∈A[[u]] is

(1−yu)2(1−q~ 2y~ u)(1−q2y~ u)((1−y~ u)2(1−q2yu)(1−q~ 2yu))−1.(1-yu)^2(1-\widetilde q^{\,2}\widetilde y\,u)(1-q^2\widetilde y\,u) \left((1-\widetilde y\,u)^2(1-q^2yu)(1-\widetilde q^{\,2}yu)\right)^{-1}.(1−yu)2(1−q​2y​u)(1−q2y​u)((1−y​u)2(1−q2yu)(1−q​2yu))−1.

Here uuu is the formal power series variable, elements of AAA are constant series, the inverse is the formal power series inverse with constant coefficient 111, and all products have the displayed order. The denominator has constant coefficient 111. No relation asserting that q~\widetilde qq​ or y~\widetilde yy​ is an inverse of another argument is required.

QAlgorithms.Papers.Independent.Intakenext100.P34.aScalarFraction

For any ring AAA, not necessarily commutative, and arbitrary elements q,q~∈Aq,\widetilde q\in Aq,q​∈A, define

G(u)=∑r≥11Au2r.G(u)=\sum_{r\ge1}1_Au^{2r}.G(u)=r≥1∑​1A​u2r.

Then aScalarFraction(q,q~)aScalarFraction(q,\widetilde q)aScalarFraction(q,q​) is the formal power series

1+(2−q2−q~ 2)(G+G2)∈A[[u]],1+(2-q^2-\widetilde q^{\,2})(G+G^2)\in A[[u]],1+(2−q2−q​2)(G+G2)∈A[[u]],

with 2=1A+1A2=1_A+1_A2=1A​+1A​ and the coefficient in parentheses treated as a constant series. The two arguments are arbitrary; no inverse relation between them is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P34.aShiftedPositive

Let CCC be a commutative ring, and let PPP specify units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and moments ω:Z→C\omega:\mathbb Z\to Cω:Z→C, satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and ω0=1+(z−z−1)Q−1\omega_0=1+(z-z^{-1})Q^{-1}ω0​=1+(z−z−1)Q−1. For any natural number nnn, let Rn=C[x0±1,…,xn−1±1]R_n=C[x_0^{\pm1},\ldots,x_{n-1}^{\pm1}]Rn​=C[x0±1​,…,xn−1±1​], meaning finite CCC-linear combinations of integer-exponent monomials with multiplication given by addition of exponent vectors, and let c:C→Rnc:C\to R_nc:C→Rn​ be its scalar map. In Rn[[u]]R_n[[u]]Rn​[[u]], put

H(u)=1+∑r≥1u2r=(1−u2)−1,H(u)=1+\sum_{r\ge1}u^{2r}=(1-u^2)^{-1},H(u)=1+r≥1∑​u2r=(1−u2)−1,

and, writing scalars for their images under ccc, put

Rj(u)=(1−xju)2(1−q−2xj−1u)(1−q2xj−1u)(1−xj−1u)2(1−q2xju)(1−q−2xju).R_j(u)= \frac{(1-x_ju)^2(1-q^{-2}x_j^{-1}u)(1-q^2x_j^{-1}u)} {(1-x_j^{-1}u)^2(1-q^2x_ju)(1-q^{-2}x_ju)}.Rj​(u)=(1−xj−1​u)2(1−q2xj​u)(1−q−2xj​u)(1−xj​u)2(1−q−2xj−1​u)(1−q2xj−1​u)​.

Each denominator is inverted as a formal power series with constant coefficient 111. The definition is

aShiftedPositive(P,n)=(∑ℓ≥0c(ωℓ)uℓ+c(z−1Q−1)−H(u))∏j=0n−1Rj(u),aShiftedPositive(P,n)= \left(\sum_{\ell\ge0}c(\omega_\ell)u^\ell +c(z^{-1}Q^{-1})-H(u)\right) \prod_{j=0}^{n-1}R_j(u),aShiftedPositive(P,n)=(ℓ≥0∑​c(ωℓ​)uℓ+c(z−1Q−1)−H(u))j=0∏n−1​Rj​(u),

with the product taken in increasing index order. When n=0n=0n=0, R0R_0R0​ as a coefficient algebra is canonically CCC, and the product of ratio factors is empty and equals 111.

QAlgorithms.Papers.Independent.Intakenext100.P34.adjacentLeft

For every natural number kkk and every i∈Adj⁡(k)i\in\operatorname{Adj}(k)i∈Adj(k), meaning 0≤i<k−10\le i<k-10≤i<k−1 with truncated subtraction, adjacentLeft⁡(i)\operatorname{adjacentLeft}(i)adjacentLeft(i) is the element of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} whose value is iii. There are no such inputs when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.adjacentRight

For every natural number kkk and every i∈Adj⁡(k)i\in\operatorname{Adj}(k)i∈Adj(k), meaning 0≤i<k−10\le i<k-10≤i<k−1 with truncated subtraction, adjacentRight⁡(i)\operatorname{adjacentRight}(i)adjacentRight(i) is the element of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} whose value is i+1i+1i+1. There are no such inputs when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.affineContractionWord

Let CCC be a commutative ring, and let PPP consist of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and a function m:Z→Cm:\mathbb Z\to Cm:Z→C satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and m(0)=1+(z−z−1)Q−1m(0)=1+(z-z^{-1})Q^{-1}m(0)=1+(z−z−1)Q−1. For an implicitly quantified natural number kkk and an index i∈Fin⁡(k−1)i\in\operatorname{Fin}(k-1)i∈Fin(k−1), let TifalseT_i^{\mathrm{false}}Tifalse​ and TitrueT_i^{\mathrm{true}}Titrue​ be the two canonical crossing generators in the free associative unital CCC-algebra on the crossing letters and two flag letters. This defines

Ei=1−Q−1(Tifalse−Titrue),E_i=1-Q^{-1}\bigl(T_i^{\mathrm{false}}-T_i^{\mathrm{true}}\bigr),Ei​=1−Q−1(Tifalse​−Titrue​),

with Q−1Q^{-1}Q−1 embedded through the canonical scalar map. This is a word in the free algebra; the definition itself asserts no idempotence or other relation for EiE_iEi​. There is no permissible iii when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.affineYWord

Let CCC be a commutative ring, and let PPP consist of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and a function m:Z→Cm:\mathbb Z\to Cm:Z→C satisfying Q=q−q−1Q=q-q^{-1}Q=q−q−1 and m(0)=1+(z−z−1)Q−1m(0)=1+(z-z^{-1})Q^{-1}m(0)=1+(z−z−1)Q−1. For an implicitly quantified natural number kkk, an index j∈Fin⁡kj\in\operatorname{Fin}kj∈Fink, and a Boolean bbb defaulting to false, write TibT_i^bTib​ and XbX^bXb for the canonical crossing and flag generators of the free associative unital CCC-algebra on these letters, and put ζfalse=z\zeta_{\mathrm{false}}=zζfalse​=z and ζtrue=z−1\zeta_{\mathrm{true}}=z^{-1}ζtrue​=z−1. This defines the word

Yjb=(Tj−1bTj−2b⋯T0b) (ζbXb) (T0bT1b⋯Tj−1b),Y_j^b= (T_{j-1}^bT_{j-2}^b\cdots T_0^b)\, (\zeta_bX^b)\, (T_0^bT_1^b\cdots T_{j-1}^b),Yjb​=(Tj−1b​Tj−2b​⋯T0b​)(ζb​Xb)(T0b​T1b​⋯Tj−1b​),

where scalars are embedded by the canonical map from CCC. Both crossing products are empty products equal to 111 when j=0j=0j=0, so Y0b=ζbXbY_0^b=\zeta_bX^bY0b​=ζb​Xb. There is no permissible jjj when k=0k=0k=0. The same Boolean is used in every crossing and in the flag; no inverse relations between the Boolean-labelled generators are imposed here. The fields q,Q,mq,Q,mq,Q,m and their constraints are part of PPP, although this word uses only zzz.

QAlgorithms.Papers.Independent.Intakenext100.P34.awMap

For a commutative ring CCC, parameters PPP consisting of units q,z,Q∈C×q,z,Q\in C^\timesq,z,Q∈C× and m:Z→Cm:\mathbb Z\to Cm:Z→C with Q=q−q−1Q=q-q^{-1}Q=q−q−1 and m(0)=1+(z−z−1)Q−1m(0)=1+(z-z^{-1})Q^{-1}m(0)=1+(z−z−1)Q−1, and any natural number kkk, this defines the canonical CCC-algebra homomorphism from the free associative unital CCC-algebra on crossing letters (i,b)(i,b)(i,b), where i+1<ki+1<ki+1<k and bbb is Boolean, and the two flag letters, to its ring quotient by the following relations. Denote the free generators by Tib,XbT_i^b,X^bTib​,Xb, identify Boolean labels with 0,10,10,1, put bˉ=1−b\bar b=1-bbˉ=1−b, ζ0=z\zeta_0=zζ0​=z, ζ1=z−1\zeta_1=z^{-1}ζ1​=z−1, and define

Ei=1−Q−1(Ti0−Ti1),Yjb=(Tj−1b⋯T0b)(ζbXb)(T0b⋯Tj−1b),E_i=1-Q^{-1}(T_i^0-T_i^1),\qquad Y_j^b=(T_{j-1}^b\cdots T_0^b)(\zeta_bX^b)(T_0^b\cdots T_{j-1}^b),Ei​=1−Q−1(Ti0​−Ti1​),Yjb​=(Tj−1b​⋯T0b​)(ζb​Xb)(T0b​⋯Tj−1b​),

using the canonical scalar embedding and empty products equal to 111. For n∈Zn\in\mathbb Zn∈Z, let Sj(n)=(Yj0)nS_j(n)=(Y_j^0)^nSj​(n)=(Yj0​)n if n≥0n\ge0n≥0 and Sj(n)=(Yj1)−nS_j(n)=(Y_j^1)^{-n}Sj​(n)=(Yj1​)−n otherwise. The target quotient imposes, for all valid crossing indices and Boolean bbb,

TibTibˉ=1,XbXbˉ=1,Ti0Tj0=Tj0Ti0if i+1≠j, j+1≠i,Ti0Tj0Ti0=Tj0Ti0Tj0if j=i+1,X0Ti0X0Ti0=Ti0X0Ti0X0if i=0,X0Ti0=Ti0X0if i>0,EiTib=ζbˉEi,TibEi=ζbˉEi,EiTjbEi=ζbEiif i+1=j or j+1=i,EiSi(n)Ei=m(n)Eiif i=0,n∈Z,EiYi0Yi+10=Ei,Yi0Yi+10Ei=Ei.\begin{aligned} T_i^bT_i^{\bar b}&=1,&X^bX^{\bar b}&=1,\\ T_i^0T_j^0&=T_j^0T_i^0 &&\text{if }i+1\ne j,\ j+1\ne i,\\ T_i^0T_j^0T_i^0&=T_j^0T_i^0T_j^0 &&\text{if }j=i+1,\\ X^0T_i^0X^0T_i^0&=T_i^0X^0T_i^0X^0 &&\text{if }i=0,\\ X^0T_i^0&=T_i^0X^0 &&\text{if }i>0,\\ E_iT_i^b&=\zeta_{\bar b}E_i, &T_i^bE_i&=\zeta_{\bar b}E_i,\\ E_iT_j^bE_i&=\zeta_bE_i &&\text{if }i+1=j\text{ or }j+1=i,\\ E_iS_i(n)E_i&=m(n)E_i &&\text{if }i=0,\quad n\in\mathbb Z,\\ E_iY_i^0Y_{i+1}^0&=E_i, &Y_i^0Y_{i+1}^0E_i&=E_i. \end{aligned}Tib​Tibˉ​Ti0​Tj0​Ti0​Tj0​Ti0​X0Ti0​X0Ti0​X0Ti0​Ei​Tib​Ei​Tjb​Ei​Ei​Si​(n)Ei​Ei​Yi0​Yi+10​​=1,=Tj0​Ti0​=Tj0​Ti0​Tj0​=Ti0​X0Ti0​X0=Ti0​X0=ζbˉ​Ei​,=ζb​Ei​=m(n)Ei​=Ei​,​XbXbˉTib​Ei​Yi0​Yi+10​Ei​​=1,if i+1=j, j+1=i,if j=i+1,if i=0,if i>0,=ζbˉ​Ei​,if i+1=j or j+1=i,if i=0,n∈Z,=Ei​.​

The homomorphism sends each free-algebra element to its class under the smallest ring congruence containing these equations. The distant rule allows equal indices, and compression includes exponent zero. For k=0k=0k=0 or k=1k=1k=1, the source has only the two flag generators and the quotient imposes only their two inverse equations.

QAlgorithms.Papers.Independent.Intakenext100.P34.ax

For a commutative ring CCC, an implicitly quantified natural number kkk, and a Boolean bbb whose default value is false, this defines XbX^bXb to be the canonical image of the flag letter labelled by bbb in the free associative unital CCC-algebra generated by the two flag letters and the crossing letters (i,c)(i,c)(i,c) for i+1<ki+1<ki+1<k and Boolean ccc. Both flag generators exist for every kkk, including k=0k=0k=0. The parameter named “inverse” does not impose an inverse relation between the two flag generators.

QAlgorithms.Papers.Independent.Intakenext100.P34.coefficientPowerSum

For a commutative ring CCC and natural numbers k,nk,nk,n, this defines the polynomial in kkk variables over CCC obtained by mapping the integer coefficients of the integer polynomial ∑i=0k−1Xin\sum_{i=0}^{k-1}X_i^n∑i=0k−1​Xin​ through the canonical homomorphism Z→C\mathbb Z\to CZ→C; equivalently, it is

∑i=0k−1Xin∈C[X0,…,Xk−1].\sum_{i=0}^{k-1}X_i^n\in C[X_0,\ldots,X_{k-1}].i=0∑k−1​Xin​∈C[X0​,…,Xk−1​].

For k=0k=0k=0, the empty sum is zero, including when n=0n=0n=0; for n=0n=0n=0, the polynomial is the constant k⋅1Ck\cdot1_Ck⋅1C​.

QAlgorithms.Papers.Independent.Intakenext100.P34.dEval

Let CCC be a commutative ring, and let PPP consist of a unit u∈C×u\in C^\timesu∈C× whose value is 222, an element ε∈C\varepsilon\in Cε∈C satisfying ε=1\varepsilon=1ε=1 or ε=−1\varepsilon=-1ε=−1, a sequence ω:N→C\omega:\mathbb N\to Cω:N→C, and an optional pair σ∈Option⁡(C×C)\sigma\in\operatorname{Option}(C\times C)σ∈Option(C×C). For a natural number kkk, write WkW_kWk​ for the quotient of the free associative unital CCC-algebra on generators TwT_wTw​, for permutations www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, together with κ0,κ1\kappa_0,\kappa_1κ0​,κ1​ and Y0,…,Yk−1Y_0,\ldots,Y_{k-1}Y0​,…,Yk−1​. Put Si=T(i i+1)S_i=T_{(i\ i+1)}Si​=T(i i+1)​, Γi=Yi+1−SiYiSi\Gamma_i=Y_{i+1}-S_iY_iS_iΓi​=Yi+1​−Si​Yi​Si​, and Ei=1+SiYi−Yi+1SiE_i=1+S_iY_i-Y_{i+1}S_iEi​=1+Si​Yi​−Yi+1​Si​, for i+1<ki+1<ki+1<k, and write [a,b]=ab−ba[a,b]=ab-ba[a,b]=ab−ba. The defining relations are

T1=1,TwTv=Twv,[Ya,Yb]=[κ0,κ1]=[κc,Ya]=[κ0,Si]=0(c∈{0,1}),(κ1S0)2=(S0κ1)2(k≥2),[κ1,Si]=0(i>0),[Si,Yi+Yi+1]=0,[Si,Yj]=0(j∉{i,i+1}),SiSi+1ΓiSi+1Si=Γi+1(i+2<k),EiSi=SiEi=εEi,EiSjEi=εEi(∣i−j∣=1),E0Y0aE0=ω(a)E0(k≥2, a∈N),Ei(Yi+Yi+1)=(Yi+Yi+1)Ei=0.\begin{gathered} T_1=1,\qquad T_wT_v=T_{wv},\\ [Y_a,Y_b]=[\kappa_0,\kappa_1]=[\kappa_c,Y_a]=[\kappa_0,S_i]=0 \quad(c\in\{0,1\}),\\ (\kappa_1S_0)^2=(S_0\kappa_1)^2\quad(k\ge2),\qquad [\kappa_1,S_i]=0\quad(i>0),\\ [S_i,Y_i+Y_{i+1}]=0,\qquad [S_i,Y_j]=0\quad(j\notin\{i,i+1\}),\\ S_iS_{i+1}\Gamma_iS_{i+1}S_i=\Gamma_{i+1}\quad(i+2<k),\\ E_iS_i=S_iE_i=\varepsilon E_i,\qquad E_iS_jE_i=\varepsilon E_i\quad(|i-j|=1),\\ E_0Y_0^aE_0=\omega(a)E_0\quad(k\ge2,\ a\in\mathbb N),\\ E_i(Y_i+Y_{i+1})=(Y_i+Y_{i+1})E_i=0. \end{gathered}T1​=1,Tw​Tv​=Twv​,[Ya​,Yb​]=[κ0​,κ1​]=[κc​,Ya​]=[κ0​,Si​]=0(c∈{0,1}),(κ1​S0​)2=(S0​κ1​)2(k≥2),[κ1​,Si​]=0(i>0),[Si​,Yi​+Yi+1​]=0,[Si​,Yj​]=0(j∈/{i,i+1}),Si​Si+1​Γi​Si+1​Si​=Γi+1​(i+2<k),Ei​Si​=Si​Ei​=εEi​,Ei​Sj​Ei​=εEi​(∣i−j∣=1),E0​Y0a​E0​=ω(a)E0​(k≥2, a∈N),Ei​(Yi​+Yi+1​)=(Yi​+Yi+1​)Ei​=0.​

All indices in these relations must exist; additionally, if σ=some⁡(a,b)\sigma=\operatorname{some}(a,b)σ=some(a,b), impose κ0=a1\kappa_0=a1κ0​=a1 and κ1=b1\kappa_1=b1κ1​=b1, whereas σ=none⁡\sigma=\operatorname{none}σ=none imposes neither scalar relation. For f=∑αcαXα∈C[X0,…,Xk−1]f=\sum_\alpha c_\alpha X^\alpha\in C[X_0,\ldots,X_{k-1}]f=∑α​cα​Xα∈C[X0​,…,Xk−1​], the defined element of WkW_kWk​ is

dEval⁡P,k(f)=∑α∈supp⁡(f)cα‾ Y0α0Y1α1⋯Yk−1αk−1,\operatorname{dEval}_{P,k}(f) = \sum_{\alpha\in\operatorname{supp}(f)} \overline{c_\alpha}\, Y_0^{\alpha_0}Y_1^{\alpha_1}\cdots Y_{k-1}^{\alpha_{k-1}},dEvalP,k​(f)=α∈supp(f)∑​cα​​Y0α0​​Y1α1​​⋯Yk−1αk−1​​,

where cα‾\overline{c_\alpha}cα​​ is the image of the coefficient under the structural map C→WkC\to W_kC→Wk​, and the product is taken in increasing index order. The zero polynomial gives an empty sum, hence zero; when k=0k=0k=0, the monomial product is empty and equals 111, so the definition sends a constant polynomial to its scalar image in W0W_0W0​.

QAlgorithms.Papers.Independent.Intakenext100.P34.dMomentAt

Let CCC be a commutative ring, and let PPP specify a unit uuu with value 222, a sign ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence ω:N→C\omega:\mathbb N\to Cω:N→C, and an optional pair σ\sigmaσ. Fix natural numbers n,L,ℓn,L,\elln,L,ℓ with n≤Ln\le Ln≤L. Let WLW_LWL​ be the associative unital CCC-algebra generated by TwT_wTw​, for permutations of {0,…,L−1}\{0,\ldots,L-1\}{0,…,L−1}, by κ0,κ1\kappa_0,\kappa_1κ0​,κ1​, and by YjY_jYj​ for j<Lj<Lj<L. Set Si=T(i i+1)S_i=T_{(i\ i+1)}Si​=T(i i+1)​, Γi=Yi+1−SiYiSi\Gamma_i=Y_{i+1}-S_iY_iS_iΓi​=Yi+1​−Si​Yi​Si​, Ei=1+SiYi−Yi+1SiE_i=1+S_iY_i-Y_{i+1}S_iEi​=1+Si​Yi​−Yi+1​Si​, and [a,b]=ab−ba[a,b]=ab-ba[a,b]=ab−ba. Its defining relations, for existing indices, are

T1=1,TwTv=Twv,[Ya,Yb]=[κ0,κ1]=[κc,Ya]=[κ0,Si]=0(c=0,1),(κ1S0)2=(S0κ1)2(L≥2),[κ1,Si]=0(i>0),[Si,Yi+Yi+1]=0,[Si,Yj]=0(j∉{i,i+1}),SiSi+1ΓiSi+1Si=Γi+1(i+2<L),EiSi=SiEi=εEi,EiSjEi=εEi(∣i−j∣=1),E0Y0aE0=ω(a)E0(L≥2, a≥0),Ei(Yi+Yi+1)=(Yi+Yi+1)Ei=0.\begin{gathered} T_1=1,\quad T_wT_v=T_{wv},\quad [Y_a,Y_b]=[\kappa_0,\kappa_1]=[\kappa_c,Y_a]=[\kappa_0,S_i]=0 \quad(c=0,1),\\ (\kappa_1S_0)^2=(S_0\kappa_1)^2\quad(L\ge2),\quad [\kappa_1,S_i]=0\quad(i>0),\\ [S_i,Y_i+Y_{i+1}]=0,\quad [S_i,Y_j]=0\quad(j\notin\{i,i+1\}),\\ S_iS_{i+1}\Gamma_iS_{i+1}S_i=\Gamma_{i+1}\quad(i+2<L),\\ E_iS_i=S_iE_i=\varepsilon E_i,\quad E_iS_jE_i=\varepsilon E_i\quad(|i-j|=1),\\ E_0Y_0^aE_0=\omega(a)E_0\quad(L\ge2,\ a\ge0),\quad E_i(Y_i+Y_{i+1})=(Y_i+Y_{i+1})E_i=0. \end{gathered}T1​=1,Tw​Tv​=Twv​,[Ya​,Yb​]=[κ0​,κ1​]=[κc​,Ya​]=[κ0​,Si​]=0(c=0,1),(κ1​S0​)2=(S0​κ1​)2(L≥2),[κ1​,Si​]=0(i>0),[Si​,Yi​+Yi+1​]=0,[Si​,Yj​]=0(j∈/{i,i+1}),Si​Si+1​Γi​Si+1​Si​=Γi+1​(i+2<L),Ei​Si​=Si​Ei​=εEi​,Ei​Sj​Ei​=εEi​(∣i−j∣=1),E0​Y0a​E0​=ω(a)E0​(L≥2, a≥0),Ei​(Yi​+Yi+1​)=(Yi​+Yi+1​)Ei​=0.​

If σ=some⁡(a,b)\sigma=\operatorname{some}(a,b)σ=some(a,b), also impose κ0=a1, κ1=b1\kappa_0=a1,\ \kappa_1=b1κ0​=a1, κ1​=b1; if σ=none⁡\sigma=\operatorname{none}σ=none, impose neither scalar relation. To define the element in question, put h=u−1h=u^{-1}h=u−1, and in C[X0,…,Xn−1][[t]]C[X_0,\ldots,X_{n-1}][[t]]C[X0​,…,Xn−1​][[t]] form

Ra(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,Fn(t)=∏j=0n−1RXj(t),Z(t)=∑m≥0ω(m)tm,Gn,ℓ=[tℓ]((Z−h)Fn+h+ε Tail⁡(Fn−1)),\begin{aligned} R_a(t)&=\bigl((1+at)^2-t^2\bigr)(1-at)^2 \left(\bigl((1-at)^2-t^2\bigr)(1+at)^2\right)^{-1},\\ F_n(t)&=\prod_{j=0}^{n-1}R_{X_j}(t),\qquad Z(t)=\sum_{m\ge0}\omega(m)t^m,\\ G_{n,\ell}&=[t^\ell]\Bigl((Z-h)F_n+h+ \varepsilon\,\operatorname{Tail}(F_n-1)\Bigr), \end{aligned}Ra​(t)Fn​(t)Gn,ℓ​​=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,=j=0∏n−1​RXj​​(t),Z(t)=m≥0∑​ω(m)tm,=[tℓ]((Z−h)Fn​+h+εTail(Fn​−1)),​

where scalars are constant polynomials and series, each inverse has constant coefficient 111, and Tail⁡(∑bmtm)=∑bm+1tm\operatorname{Tail}(\sum b_mt^m)=\sum b_{m+1}t^mTail(∑bm​tm)=∑bm+1​tm. If Gn,ℓ=∑αcαXαG_{n,\ell}=\sum_\alpha c_\alpha X^\alphaGn,ℓ​=∑α​cα​Xα, the defined element is

Mn,L,ℓ=∑α∈supp⁡(Gn,ℓ)cα‾ Y0α0⋯Yn−1αn−1∈WL,M_{n,L,\ell} = \sum_{\alpha\in\operatorname{supp}(G_{n,\ell})} \overline{c_\alpha}\,Y_0^{\alpha_0}\cdots Y_{n-1}^{\alpha_{n-1}} \in W_L,Mn,L,ℓ​=α∈supp(Gn,ℓ​)∑​cα​​Y0α0​​⋯Yn−1αn−1​​∈WL​,

with products in increasing index order. This is evaluation after renaming the nnn variables to the first nnn variables at level LLL. The case n=0n=0n=0 gives M0,L,ℓ=ω(ℓ)‾M_{0,L,\ell}=\overline{\omega(\ell)}M0,L,ℓ​=ω(ℓ)​; L=0L=0L=0 is also allowed, in which case necessarily n=0n=0n=0 and the target is still the presented quotient W0W_0W0​.

QAlgorithms.Papers.Independent.Intakenext100.P34.dMomentPolynomial

Let CCC be a commutative ring, and let PPP specify a unit u∈C×u\in C^\timesu∈C× with value 222, an element ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence ω:N→C\omega:\mathbb N\to Cω:N→C, and an optional pair of elements of CCC. For arbitrary n,ℓ∈Nn,\ell\in\mathbb Nn,ℓ∈N, put h=u−1∈Ch=u^{-1}\in Ch=u−1∈C, work in Bn=C[X0,…,Xn−1]B_n=C[X_0,\ldots,X_{n-1}]Bn​=C[X0​,…,Xn−1​], and regard elements of BnB_nBn​ as constant series when they occur in Bn[[t]]B_n[[t]]Bn​[[t]]. Define

Ra(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,Fn(t)=∏j=0n−1RXj(t),Z(t)=∑m≥0ω(m)tm,Tail⁡ ⁣(∑m≥0bmtm)=∑m≥0bm+1tm.\begin{aligned} R_a(t)&= \bigl((1+at)^2-t^2\bigr)(1-at)^2 \left(\bigl((1-at)^2-t^2\bigr)(1+at)^2\right)^{-1},\\ F_n(t)&=\prod_{j=0}^{n-1}R_{X_j}(t),\qquad Z(t)=\sum_{m\ge0}\omega(m)t^m,\\ \operatorname{Tail}\!\left(\sum_{m\ge0}b_mt^m\right) &=\sum_{m\ge0}b_{m+1}t^m. \end{aligned}Ra​(t)Fn​(t)Tail(m≥0∑​bm​tm)​=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,=j=0∏n−1​RXj​​(t),Z(t)=m≥0∑​ω(m)tm,=m≥0∑​bm+1​tm.​

Each inverse has a denominator with constant coefficient 111, and the product defining FnF_nFn​ is in increasing index order. The defined polynomial is

Gn,ℓ=[tℓ]((Z(t)−h)Fn(t)+h+ε Tail⁡(Fn(t)−1))∈Bn.G_{n,\ell} = [t^\ell]\Bigl((Z(t)-h)F_n(t)+h+ \varepsilon\,\operatorname{Tail}(F_n(t)-1)\Bigr) \in B_n.Gn,ℓ​=[tℓ]((Z(t)−h)Fn​(t)+h+εTail(Fn​(t)−1))∈Bn​.

The optional pair in PPP does not enter this formula. The indices nnn and ℓ\ellℓ may be zero; in particular F0=1F_0=1F0​=1, so G0,ℓG_{0,\ell}G0,ℓ​ is the constant polynomial ω(ℓ)\omega(\ell)ω(ℓ).

QAlgorithms.Papers.Independent.Intakenext100.P34.dMomentSeries

Let CCC be a commutative ring, and let PPP consist of a unit uuu with value 222, a sign ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence ω:N→C\omega:\mathbb N\to Cω:N→C, and an optional pair σ\sigmaσ. Fix natural numbers n≤Ln\le Ln≤L and a Boolean bbb, whose default value is false. Define WLW_LWL​ as the associative unital CCC-algebra generated by permutation symbols TwT_wTw​, two elements κ0,κ1\kappa_0,\kappa_1κ0​,κ1​, and YjY_jYj​ for j<Lj<Lj<L. With Si=T(i i+1)S_i=T_{(i\ i+1)}Si​=T(i i+1)​, Γi=Yi+1−SiYiSi\Gamma_i=Y_{i+1}-S_iY_iS_iΓi​=Yi+1​−Si​Yi​Si​, Ei=1+SiYi−Yi+1SiE_i=1+S_iY_i-Y_{i+1}S_iEi​=1+Si​Yi​−Yi+1​Si​, and [a,b]=ab−ba[a,b]=ab-ba[a,b]=ab−ba, its defining relations, for existing indices, are

T1=1,TwTv=Twv,[Ya,Yb]=[κ0,κ1]=[κc,Ya]=[κ0,Si]=0(c=0,1),(κ1S0)2=(S0κ1)2(L≥2),[κ1,Si]=0(i>0),[Si,Yi+Yi+1]=0,[Si,Yj]=0(j∉{i,i+1}),SiSi+1ΓiSi+1Si=Γi+1(i+2<L),EiSi=SiEi=εEi,EiSjEi=εEi(∣i−j∣=1),E0Y0aE0=ω(a)E0(L≥2, a≥0),Ei(Yi+Yi+1)=(Yi+Yi+1)Ei=0.\begin{gathered} T_1=1,\quad T_wT_v=T_{wv},\quad [Y_a,Y_b]=[\kappa_0,\kappa_1]=[\kappa_c,Y_a]=[\kappa_0,S_i]=0 \quad(c=0,1),\\ (\kappa_1S_0)^2=(S_0\kappa_1)^2\quad(L\ge2),\quad [\kappa_1,S_i]=0\quad(i>0),\\ [S_i,Y_i+Y_{i+1}]=0,\quad [S_i,Y_j]=0\quad(j\notin\{i,i+1\}),\\ S_iS_{i+1}\Gamma_iS_{i+1}S_i=\Gamma_{i+1}\quad(i+2<L),\\ E_iS_i=S_iE_i=\varepsilon E_i,\quad E_iS_jE_i=\varepsilon E_i\quad(|i-j|=1),\\ E_0Y_0^aE_0=\omega(a)E_0\quad(L\ge2,\ a\ge0),\quad E_i(Y_i+Y_{i+1})=(Y_i+Y_{i+1})E_i=0. \end{gathered}T1​=1,Tw​Tv​=Twv​,[Ya​,Yb​]=[κ0​,κ1​]=[κc​,Ya​]=[κ0​,Si​]=0(c=0,1),(κ1​S0​)2=(S0​κ1​)2(L≥2),[κ1​,Si​]=0(i>0),[Si​,Yi​+Yi+1​]=0,[Si​,Yj​]=0(j∈/{i,i+1}),Si​Si+1​Γi​Si+1​Si​=Γi+1​(i+2<L),Ei​Si​=Si​Ei​=εEi​,Ei​Sj​Ei​=εEi​(∣i−j∣=1),E0​Y0a​E0​=ω(a)E0​(L≥2, a≥0),Ei​(Yi​+Yi+1​)=(Yi​+Yi+1​)Ei​=0.​

If σ=some⁡(a,b′)\sigma=\operatorname{some}(a,b')σ=some(a,b′), additionally κ0=a1, κ1=b′1\kappa_0=a1,\ \kappa_1=b'1κ0​=a1, κ1​=b′1; if σ=none⁡\sigma=\operatorname{none}σ=none, these scalar relations are absent. Put h=u−1h=u^{-1}h=u−1, define

Ra(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,Fn(t)=∏j=0n−1RXj(t),Z(t)=∑m≥0ω(m)tm,Gn,ℓ=[tℓ]((Z−h)Fn+h+ε Tail⁡(Fn−1))∈C[X0,…,Xn−1],\begin{aligned} R_a(t)&=\bigl((1+at)^2-t^2\bigr)(1-at)^2 \left(\bigl((1-at)^2-t^2\bigr)(1+at)^2\right)^{-1},\\ F_n(t)&=\prod_{j=0}^{n-1}R_{X_j}(t),\qquad Z(t)=\sum_{m\ge0}\omega(m)t^m,\\ G_{n,\ell}&=[t^\ell]\Bigl((Z-h)F_n+h+ \varepsilon\,\operatorname{Tail}(F_n-1)\Bigr) \in C[X_0,\ldots,X_{n-1}], \end{aligned}Ra​(t)Fn​(t)Gn,ℓ​​=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1,=j=0∏n−1​RXj​​(t),Z(t)=m≥0∑​ω(m)tm,=[tℓ]((Z−h)Fn​+h+εTail(Fn​−1))∈C[X0​,…,Xn−1​],​

where Tail⁡(∑cmtm)=∑cm+1tm\operatorname{Tail}(\sum c_mt^m)=\sum c_{m+1}t^mTail(∑cm​tm)=∑cm+1​tm, scalars are constant series, and each inverse is the formal inverse with constant coefficient 111. Let Mn,L,ℓ∈WLM_{n,L,\ell}\in W_LMn,L,ℓ​∈WL​ be obtained from Gn,ℓ=∑αcαXαG_{n,\ell}=\sum_\alpha c_\alpha X^\alphaGn,ℓ​=∑α​cα​Xα by the finite sum ∑αcα‾Y0α0⋯Yn−1αn−1\sum_\alpha\overline{c_\alpha}Y_0^{\alpha_0}\cdots Y_{n-1}^{\alpha_{n-1}}∑α​cα​​Y0α0​​⋯Yn−1αn−1​​, with factors in increasing index order. The defined power series is

{∑ℓ≥0Mn,L,ℓtℓ,b=false,∑ℓ≥0(−1)ℓMn,L,ℓtℓ,b=true.\begin{cases} \displaystyle\sum_{\ell\ge0}M_{n,L,\ell}t^\ell,&b=\mathrm{false},\\[4pt] \displaystyle\sum_{\ell\ge0}(-1)^\ell M_{n,L,\ell}t^\ell,&b=\mathrm{true}. \end{cases}⎩⎨⎧​ℓ≥0∑​Mn,L,ℓ​tℓ,ℓ≥0∑​(−1)ℓMn,L,ℓ​tℓ,​b=false,b=true.​

Empty products equal 111; in particular n=0n=0n=0 gives the scalar moment series ∑ℓ≥0ω(ℓ)‾tℓ\sum_{\ell\ge0}\overline{\omega(\ell)}t^\ell∑ℓ≥0​ω(ℓ)​tℓ, with alternating signs in the true case, and n=L=0n=L=0n=L=0 is permitted.

QAlgorithms.Papers.Independent.Intakenext100.P34.dRatio

For any ring AAA, not assumed commutative, and any a∈Aa\in Aa∈A, this definition gives the formal power series

Ra(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1∈A[[t]],R_a(t) = \bigl((1+at)^2-t^2\bigr)(1-at)^2 \left(\bigl((1-at)^2-t^2\bigr)(1+at)^2\right)^{-1} \in A[[t]],Ra​(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1∈A[[t]],

where aaa denotes its constant power series and ttt is the formal power-series variable. The inverse is the formal power-series inverse with constant coefficient 111; it exists because the displayed denominator has constant coefficient 111. Multiplication occurs in exactly the displayed order, with the inverse on the right, and there is no restriction on aaa.

QAlgorithms.Papers.Independent.Intakenext100.P34.dRatioProduct

For any ring AAA, any natural number nnn, and any indexed family y0,…,yn−1∈Ay_0,\ldots,y_{n-1}\in Ay0​,…,yn−1​∈A, this definition gives the ordered product

Ry0(t)Ry1(t)⋯Ryn−1(t)∈A[[t]],R_{y_0}(t)R_{y_1}(t)\cdots R_{y_{n-1}}(t)\in A[[t]],Ry0​​(t)Ry1​​(t)⋯Ryn−1​​(t)∈A[[t]],

where, for a∈Aa\in Aa∈A,

Ra(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1.R_a(t)= \bigl((1+at)^2-t^2\bigr)(1-at)^2 \left(\bigl((1-at)^2-t^2\bigr)(1+at)^2\right)^{-1}.Ra​(t)=((1+at)2−t2)(1−at)2(((1−at)2−t2)(1+at)2)−1.

Elements of AAA in this formula are constant power series, and each inverse is the formal inverse of a series with constant coefficient 111. Neither AAA nor the family yjy_jyj​ is assumed commutative; the outer product is in increasing index order. When n=0n=0n=0, the product is empty and equals 111.

QAlgorithms.Papers.Independent.Intakenext100.P34.dbMap

For every commutative ring CCC and natural number kkk, this defines the canonical CCC-algebra homomorphism from the free associative unital CCC-algebra on symbols TwT_wTw​ for permutations www of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, symbols κ0,κ1\kappa_0,\kappa_1κ0​,κ1​, and symbols yjy_jyj​ for j∈[k]j\in[k]j∈[k], to its ring quotient imposing the following equations. For 0≤i<k−10\le i<k-10≤i<k−1, let τi\tau_iτi​ swap iii and i+1i+1i+1, and put γi=yi+1−TτiyiTτi\gamma_i=y_{i+1}-T_{\tau_i}y_iT_{\tau_i}γi​=yi+1​−Tτi​​yi​Tτi​​. The imposed equations are Tid=1T_{\mathrm{id}}=1Tid​=1, TwTv=TwvT_wT_v=T_{wv}Tw​Tv​=Twv​ for all permutations w,vw,vw,v, yiyj=yjyiy_iy_j=y_jy_iyi​yj​=yj​yi​ for all i,j∈[k]i,j\in[k]i,j∈[k], κ0κ1=κ1κ0\kappa_0\kappa_1=\kappa_1\kappa_0κ0​κ1​=κ1​κ0​, and κbyj=yjκb\kappa_by_j=y_j\kappa_bκb​yj​=yj​κb​ for both b∈{0,1}b\in\{0,1\}b∈{0,1} and every j∈[k]j\in[k]j∈[k]; also, for every adjacent index iii, κ0Tτi=Tτiκ0\kappa_0T_{\tau_i}=T_{\tau_i}\kappa_0κ0​Tτi​​=Tτi​​κ0​, κ1Tτiκ1Tτi=Tτiκ1Tτiκ1\kappa_1T_{\tau_i}\kappa_1T_{\tau_i}=T_{\tau_i}\kappa_1T_{\tau_i}\kappa_1κ1​Tτi​​κ1​Tτi​​=Tτi​​κ1​Tτi​​κ1​ if i=0i=0i=0, κ1Tτi=Tτiκ1\kappa_1T_{\tau_i}=T_{\tau_i}\kappa_1κ1​Tτi​​=Tτi​​κ1​ if i≠0i\ne0i=0, and Tτi(yi+yi+1)=(yi+yi+1)TτiT_{\tau_i}(y_i+y_{i+1})=(y_i+y_{i+1})T_{\tau_i}Tτi​​(yi​+yi+1​)=(yi​+yi+1​)Tτi​​; furthermore, yjTτi=Tτiyjy_jT_{\tau_i}=T_{\tau_i}y_jyj​Tτi​​=Tτi​​yj​ whenever j∉{i,i+1}j\notin\{i,i+1\}j∈/{i,i+1}, and TτiTτjγiTτjTτi=γjT_{\tau_i}T_{\tau_j}\gamma_iT_{\tau_j}T_{\tau_i}=\gamma_jTτi​​Tτj​​γi​Tτj​​Tτi​​=γj​ whenever i,ji,ji,j are adjacent indices with j=i+1j=i+1j=i+1. The homomorphism sends each free-algebra element to its quotient class. The parameter kkk may be zero; the adjacent-index set is empty for k=0k=0k=0 or k=1k=1k=1, and the yyy-index set is empty for k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakenext100.P34.de

For the commutative coefficient ring CCC, a natural number kkk, and an adjacent index i∈{0,…,k−2}i\in\{0,\ldots,k-2\}i∈{0,…,k−2}, let sis_isi​ be the permutation of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} exchanging iii and i+1i+1i+1. In the free associative unital CCC-algebra with generators TwT_wTw​ for all permutations www, generators K0,K1K_0,K_1K0​,K1​, and generators YjY_jYj​ for 0≤j<k0\le j<k0≤j<k, this definition assigns the element

Ei:=1+TsiYi−Yi+1Tsi.E_i:=1+T_{s_i}Y_i-Y_{i+1}T_{s_i}.Ei​:=1+Tsi​​Yi​−Yi+1​Tsi​​.

This is an element of the free algebra before any relations are imposed. The adjacent-index set has size k−1k-1k−1, with natural-number subtraction truncated at zero; thus there is no input iii when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.dg

For a commutative ring CCC, a natural number kkk, and an index iii satisfying 0≤i<k−10\le i<k-10≤i<k−1 with truncated subtraction, let sis_isi​ be the permutation exchanging iii and i+1i+1i+1, let TsiT_{s_i}Tsi​​ be its formal permutation generator, and let YjY_jYj​ be the formal generator indexed by jjj. In the free associative unital CCC-algebra on all permutation letters, two Boolean-indexed kappa⁡\operatorname{kappa}kappa letters, and the YjY_jYj​, the definition is

dg⁡C(i)=Yi+1−TsiYiTsi.\operatorname{dg}_C(i)=Y_{i+1}-T_{s_i}Y_iT_{s_i}.dgC​(i)=Yi+1​−Tsi​​Yi​Tsi​​.

There are no such inputs iii when k=0k=0k=0 or k=1k=1k=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.dk

For a commutative ring CCC, a natural number kkk, and a Boolean value bbb, dk⁡C(b)\operatorname{dk}_C(b)dkC​(b) is the canonical free generator corresponding to the formal letter kappa⁡(b)\operatorname{kappa}(b)kappa(b) in the free associative unital CCC-algebra generated by permutation letters indexed by permutations of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, the two Boolean-indexed kappa⁡\operatorname{kappa}kappa letters, and letters y⁡(j)\operatorname{y}(j)y(j) for 0≤j<k0\le j<k0≤j<k. Both Boolean choices are available for every kkk, including k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakenext100.P34.dt

For a commutative ring CCC, a natural number kkk, and a permutation www of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, dt⁡C(w)\operatorname{dt}_C(w)dtC​(w) is the canonical free generator corresponding to the formal letter perm⁡(w)\operatorname{perm}(w)perm(w) in the free associative unital CCC-algebra generated by all permutation letters, two Boolean-indexed kappa⁡\operatorname{kappa}kappa letters, and the letters y⁡(j)\operatorname{y}(j)y(j) for 0≤j<k0\le j<k0≤j<k. This definition imposes no multiplication relations on the permutation-indexed generators, including the generator indexed by the identity permutation.

QAlgorithms.Papers.Independent.Intakenext100.P34.dwMap

Let CCC be the commutative coefficient ring, k∈Nk\in\mathbb Nk∈N, and PPP consist of a unit representing 222, a sign ε∈{1,−1}\varepsilon\in\{1,-1\}ε∈{1,−1}, a sequence μ:N→C\mu:\mathbb N\to Cμ:N→C, and an optional scalar pair. Let FFF be the free associative unital CCC-algebra on TwT_wTw​, for permutations of I={0,…,k−1}I=\{0,\ldots,k-1\}I={0,…,k−1}, on K0,K1K_0,K_1K0​,K1​, and on YjY_jYj​, for j∈Ij\in Ij∈I. For each adjacent index 0≤i<k−10\le i<k-10≤i<k−1, write si=(i i+1)s_i=(i\ i+1)si​=(i i+1) and

Gi=Yi+1−TsiYiTsi,Ei=1+TsiYi−Yi+1Tsi.G_i=Y_{i+1}-T_{s_i}Y_iT_{s_i}, \qquad E_i=1+T_{s_i}Y_i-Y_{i+1}T_{s_i}.Gi​=Yi+1​−Tsi​​Yi​Tsi​​,Ei​=1+Tsi​​Yi​−Yi+1​Tsi​​.

This definition is the canonical CCC-algebra homomorphism from FFF to its ring quotient obtained by imposing

Tid=1,TwTv=Twv,YpYq=YqYp,K0K1=K1K0,KbYj=YjKb,K0Tsi=TsiK0,K1Ts0K1Ts0=Ts0K1Ts0K1,K1Tsi=TsiK1(i≠0),Tsi(Yi+Yi+1)=(Yi+Yi+1)Tsi,YjTsi=TsiYj(j∉{i,i+1}),TsiTsi+1GiTsi+1Tsi=Gi+1,EiTsi=εEi,TsiEi=εEi,EiTsjEi=εEi(i+1=j or j+1=i),E0Y0nE0=μnE0(n∈N),Ei(Yi+Yi+1)=0,(Yi+Yi+1)Ei=0,\begin{gathered} T_{\mathrm{id}}=1,\qquad T_wT_v=T_{wv},\qquad Y_pY_q=Y_qY_p,\qquad K_0K_1=K_1K_0,\qquad K_bY_j=Y_jK_b,\\ K_0T_{s_i}=T_{s_i}K_0,\qquad K_1T_{s_0}K_1T_{s_0}=T_{s_0}K_1T_{s_0}K_1,\qquad K_1T_{s_i}=T_{s_i}K_1\quad(i\ne0),\\ T_{s_i}(Y_i+Y_{i+1})=(Y_i+Y_{i+1})T_{s_i},\qquad Y_jT_{s_i}=T_{s_i}Y_j\quad(j\notin\{i,i+1\}),\\ T_{s_i}T_{s_{i+1}}G_iT_{s_{i+1}}T_{s_i}=G_{i+1},\\ E_iT_{s_i}=\varepsilon E_i,\qquad T_{s_i}E_i=\varepsilon E_i,\qquad E_iT_{s_j}E_i=\varepsilon E_i\quad(i+1=j\ \text{or}\ j+1=i),\\ E_0Y_0^nE_0=\mu_nE_0\quad(n\in\mathbb N),\qquad E_i(Y_i+Y_{i+1})=0,\qquad (Y_i+Y_{i+1})E_i=0, \end{gathered}Tid​=1,Tw​Tv​=Twv​,Yp​Yq​=Yq​Yp​,K0​K1​=K1​K0​,Kb​Yj​=Yj​Kb​,K0​Tsi​​=Tsi​​K0​,K1​Ts0​​K1​Ts0​​=Ts0​​K1​Ts0​​K1​,K1​Tsi​​=Tsi​​K1​(i=0),Tsi​​(Yi​+Yi+1​)=(Yi​+Yi+1​)Tsi​​,Yj​Tsi​​=Tsi​​Yj​(j∈/{i,i+1}),Tsi​​Tsi+1​​Gi​Tsi+1​​Tsi​​=Gi+1​,Ei​Tsi​​=εEi​,Tsi​​Ei​=εEi​,Ei​Tsj​​Ei​=εEi​(i+1=j or j+1=i),E0​Y0n​E0​=μn​E0​(n∈N),Ei​(Yi​+Yi+1​)=0,(Yi​+Yi+1​)Ei​=0,​

together with K0=aK_0=aK0​=a and K1=bK_1=bK1​=b whenever the optional scalar pair is (a,b)(a,b)(a,b). In these equations b∈{0,1}b\in\{0,1\}b∈{0,1} in KbYj=YjKbK_bY_j=Y_jK_bKb​Yj​=Yj​Kb​, all scalar elements mean their structural images, and every adjacent index must exist. The homomorphism sends each free-algebra element to its class under the smallest ring congruence generated by these equations. There is no admissibility hypothesis; compression includes exponent zero, and when k=0k=0k=0 or k=1k=1k=1, the equations requiring adjacent indices are absent.

QAlgorithms.Papers.Independent.Intakenext100.P34.dy

For a commutative ring CCC, a natural number kkk, and an index jjj satisfying 0≤j<k0\le j<k0≤j<k, dy⁡C(j)\operatorname{dy}_C(j)dyC​(j) is the canonical free generator corresponding to the formal letter y⁡(j)\operatorname{y}(j)y(j) in the free associative unital CCC-algebra generated by permutation letters indexed by permutations of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1}, two Boolean-indexed kappa⁡\operatorname{kappa}kappa letters, and the letters y⁡(j)\operatorname{y}(j)y(j). There are no such inputs jjj when k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakenext100.P34.gAction

For every natural number kkk and permutation www of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, this defines a function on Ik={∗}⊔{j^:j∈[k]}I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}Ik​={∗}⊔{j​:j∈[k]} by ∗↦∗\ast\mapsto\ast∗↦∗ and j^↦w(j)^\widehat j\mapsto\widehat{w(j)}j​↦w(j)​. When k=0k=0k=0, this is the identity function on the singleton {∗}\{\ast\}{∗}.

QAlgorithms.Papers.Independent.Intakenext100.P34.gY

For every commutative ring CCC, natural number kkk, element h∈Ch\in Ch∈C supplied as the parameter named half, and index j∈[k]={0,…,k−1}j\in[k]=\{0,\ldots,k-1\}j∈[k]={0,…,k−1}, this defines an element of the free associative unital CCC-algebra on permutation generators TwT_wTw​, generators κi\kappa_iκi​ indexed by Ik={∗}⊔{a^:a∈[k]}I_k=\{\ast\}\sqcup\{\widehat a:a\in[k]\}Ik​={∗}⊔{a:a∈[k]}, and generators Γab\Gamma_{ab}Γab​ indexed by ordered distinct pairs in IkI_kIk​, by

Yj=ιC(h)κj^+Γ∗,j^+∑ℓ∈[k]ℓ<jΓℓ^,j^,Y_j=\iota_C(h)\kappa_{\widehat j} +\Gamma_{\ast,\widehat j} +\sum_{\substack{\ell\in[k]\\ \ell<j}}\Gamma_{\widehat\ell,\widehat j},Yj​=ιC​(h)κj​​+Γ∗,j​​+ℓ∈[k]ℓ<j​∑​Γℓ,j​​,

where ιC\iota_CιC​ is the scalar homomorphism into the free algebra. There is no hypothesis that hhh is an inverse of 222 or satisfies any other equation. For j=0j=0j=0 the sum is empty and equals zero; for k=0k=0k=0 there is no possible argument jjj.

QAlgorithms.Papers.Independent.Intakenext100.P34.gbMap

For every commutative ring CCC and natural number kkk, this defines the canonical CCC-algebra homomorphism from the free associative unital CCC-algebra on generators TwT_wTw​ for permutations of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, κi\kappa_iκi​ for i∈Ik={∗}⊔{j^:j∈[k]}i\in I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}i∈Ik​={∗}⊔{j​:j∈[k]}, and Γij\Gamma_{ij}Γij​ for ordered distinct pairs in IkI_kIk​, to the ring quotient imposing the following equations. Let w⋅∗=∗w\cdot\ast=\astw⋅∗=∗ and w⋅j^=w(j)^w\cdot\widehat j=\widehat{w(j)}w⋅j​=w(j)​. For all permutations w,vw,vw,v and all applicable indices, impose Tid=1T_{\mathrm{id}}=1Tid​=1, TwTv=TwvT_wT_v=T_{wv}Tw​Tv​=Twv​, TwκiTw−1=κw⋅iT_w\kappa_iT_{w^{-1}}=\kappa_{w\cdot i}Tw​κi​Tw−1​=κw⋅i​, and TwΓijTw−1=Γw⋅i,w⋅jT_w\Gamma_{ij}T_{w^{-1}}=\Gamma_{w\cdot i,w\cdot j}Tw​Γij​Tw−1​=Γw⋅i,w⋅j​ when i≠ji\ne ji=j; impose κiκj=κjκi\kappa_i\kappa_j=\kappa_j\kappa_iκi​κj​=κj​κi​ for every i,ji,ji,j, κiΓℓm=Γℓmκi\kappa_i\Gamma_{\ell m}=\Gamma_{\ell m}\kappa_iκi​Γℓm​=Γℓm​κi​ when ℓ≠m\ell\ne mℓ=m, and Γij=Γji\Gamma_{ij}=\Gamma_{ji}Γij​=Γji​ when i≠ji\ne ji=j; finally, impose ΓprΓℓm=ΓℓmΓpr\Gamma_{pr}\Gamma_{\ell m}=\Gamma_{\ell m}\Gamma_{pr}Γpr​Γℓm​=Γℓm​Γpr​ for pairwise distinct p,r,ℓ,mp,r,\ell,mp,r,ℓ,m, and Γij(Γir+Γjr)=(Γir+Γjr)Γij\Gamma_{ij}(\Gamma_{ir}+\Gamma_{jr})=(\Gamma_{ir}+\Gamma_{jr})\Gamma_{ij}Γij​(Γir​+Γjr​)=(Γir​+Γjr​)Γij​ for pairwise distinct i,j,ri,j,ri,j,r. The homomorphism sends every free-algebra element to its quotient class. The case k=0k=0k=0 is included, with the unique permutation of the empty set, the sole index ∗\ast∗, and no Γ\GammaΓ generators.

QAlgorithms.Papers.Independent.Intakenext100.P34.geometric

For every semiring AAA and every a∈Aa\in Aa∈A, this definition denotes the formal power series

geometric⁡(a)=∑n=0∞anTn∈A[[T]].\operatorname{geometric}(a)=\sum_{n=0}^{\infty}a^nT^n\in A[[T]].geometric(a)=n=0∑∞​anTn∈A[[T]].

Thus its coefficient of degree nnn is ana^nan, including coefficient 111 in degree zero. No commutativity, invertibility, or convergence hypothesis is required.

QAlgorithms.Papers.Independent.Intakenext100.P34.gg

For every commutative ring CCC, natural number kkk, and indices i,j∈Ik={∗}⊔{a^:a∈[k]}i,j\in I_k=\{\ast\}\sqcup\{\widehat a:a\in[k]\}i,j∈Ik​={∗}⊔{a:a∈[k]}, where [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, this defines Γij\Gamma_{ij}Γij​ in the free associative unital CCC-algebra on permutation letters, index letters, and letters indexed by ordered distinct pairs in IkI_kIk​: if i≠ji\ne ji=j, its value is the canonical free generator labelled by (i,j)(i,j)(i,j); if i=ji=ji=j, its value is zero. For distinct indices, Γij\Gamma_{ij}Γij​ and Γji\Gamma_{ji}Γji​ are separate free generators. When k=0k=0k=0, every value of this function is zero.

QAlgorithms.Papers.Independent.Intakenext100.P34.gk

For every commutative ring CCC, natural number kkk, and index j∈Ik={∗}⊔{a^:a∈[k]}j\in I_k=\{\ast\}\sqcup\{\widehat a:a\in[k]\}j∈Ik​={∗}⊔{a:a∈[k]}, where [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, this defines κj\kappa_jκj​ to be the canonical free generator labelled by jjj in the free associative unital CCC-algebra on permutation letters TwT_wTw​, index letters κi\kappa_iκi​, and letters Γiℓ\Gamma_{i\ell}Γiℓ​ indexed by ordered distinct pairs in IkI_kIk​. The distinguished index ∗\ast∗ is allowed for every kkk; when k=0k=0k=0, it is the only possible value of jjj.

QAlgorithms.Papers.Independent.Intakenext100.P34.gt

For every commutative ring CCC, natural number kkk, and permutation www of [k]={0,…,k−1}[k]=\{0,\ldots,k-1\}[k]={0,…,k−1}, this defines TwT_wTw​ to be the canonical free generator labelled by www in the free associative unital CCC-algebra on permutation letters, letters κi\kappa_iκi​ indexed by Ik={∗}⊔{j^:j∈[k]}I_k=\{\ast\}\sqcup\{\widehat j:j\in[k]\}Ik​={∗}⊔{j​:j∈[k]}, and letters Γij\Gamma_{ij}Γij​ indexed by ordered distinct pairs in IkI_kIk​. This definition imposes no permutation multiplication equations; in particular, TidT_{\mathrm{id}}Tid​ is a free generator. The definition includes k=0k=0k=0, when www is the unique permutation of the empty set.

QAlgorithms.Papers.Independent.Intakenext100.P34.halfResolvent

For every semiring AAA and every ordered pair h,a∈Ah,a\in Ah,a∈A, this definition denotes the formal power series

halfResolvent⁡(h,a)=hT(∑n=0∞(ha)nTn)=∑n=0∞h(ha)nTn+1∈A[[T]],\operatorname{halfResolvent}(h,a) =hT\left(\sum_{n=0}^{\infty}(ha)^nT^n\right) =\sum_{n=0}^{\infty}h(ha)^nT^{n+1}\in A[[T]],halfResolvent(h,a)=hT(n=0∑∞​(ha)nTn)=n=0∑∞​h(ha)nTn+1∈A[[T]],

where hhh is first inserted as a constant series. Its constant coefficient is 000, and its coefficient of degree m≥1m\ge1m≥1 is h(ha)m−1h(ha)^{m-1}h(ha)m−1, in the displayed multiplication order. No assumption says that hhh represents one half, is invertible, or commutes with aaa.

QAlgorithms.Papers.Independent.Intakenext100.P34.infinityResolvent

For every semiring AAA and every a∈Aa\in Aa∈A, this definition denotes the formal power series

infinityResolvent⁡(a)=T(∑n=0∞anTn)=∑n=0∞anTn+1∈A[[T]].\operatorname{infinityResolvent}(a) =T\left(\sum_{n=0}^{\infty}a^nT^n\right) =\sum_{n=0}^{\infty}a^nT^{n+1}\in A[[T]].infinityResolvent(a)=T(n=0∑∞​anTn)=n=0∑∞​anTn+1∈A[[T]].

Its constant coefficient is 000, and its coefficient of degree m≥1m\ge1m≥1 is am−1a^{m-1}am−1. The definition requires neither commutativity nor invertibility of aaa.

QAlgorithms.Papers.Independent.Intakenext100.P34.integralRoot

For every complex number ζ\zetaζ, this defines the element of the subalgebra Z[ζ]={p(ζ):p∈Z[X]}⊆C\mathbb Z[\zeta]=\{p(\zeta):p\in\mathbb Z[X]\}\subseteq\mathbb CZ[ζ]={p(ζ):p∈Z[X]}⊆C whose underlying complex value is ζ\zetaζ, together with its membership in that subalgebra. No hypothesis that ζ\zetaζ is a root of unity or an algebraic integer is required.

QAlgorithms.Papers.Independent.Intakenext100.P34.laurentVariable

Let CCC be a commutative ring, let kkk be a natural number, let j∈{0,…,k−1}j\in\{0,\ldots,k-1\}j∈{0,…,k−1}, and let bbb be a Boolean, defaulting to false. In the Laurent polynomial algebra C[Zk]C[\mathbb Z^k]C[Zk], whose elements are finite CCC-linear combinations of monomials with integer exponent vectors, laurentVariable⁡(j,b)\operatorname{laurentVariable}(j,b)laurentVariable(j,b) is the single monomial with coefficient 111, exponent 111 at coordinate jjj when bbb is false and exponent −1-1−1 there when bbb is true, and exponent 000 at every other coordinate. Thus its value is xjx_jxj​ or xj−1x_j^{-1}xj−1​, respectively. There is no possible argument jjj when k=0k=0k=0.

QAlgorithms.Papers.Independent.Intakenext100.P34.leftMultiples

For any type AAA equipped with a binary multiplication and any e∈Ae\in Ae∈A, this defines the subset

{a∈A:∃b∈A, a=be}.\{a\in A:\exists b\in A,\ a=be\}.{a∈A:∃b∈A, a=be}.

Thus membership means being a single left multiple of eee; no addition, identity, associativity, or distributivity is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P34.multiplicativeResolvent

For every type AAA equipped with a semiring structure and every a∈Aa\in Aa∈A, this defines the formal power series

Ra(t)=a t(∑n=0∞antn)=∑n=1∞antn.R_a(t)=a\,t\left(\sum_{n=0}^{\infty}a^nt^n\right) =\sum_{n=1}^{\infty}a^nt^n.Ra​(t)=at(n=0∑∞​antn)=n=1∑∞​antn.

Here aaa in the first product means the constant power series with value aaa, and ttt is the formal power-series variable. Thus the constant coefficient is zero and the coefficient of tnt^ntn is ana^nan for every n≥1n\ge1n≥1. No commutativity of AAA or invertibility of aaa is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P34.pairResolvent

For every type AAA equipped with a ring structure and every a∈Aa\in Aa∈A, this defines the formal power series

Ga(t)=(∑n=0∞{an/2,n even,0,n oddtn)−1=∑r=1∞art2r.G_a(t)= \left(\sum_{n=0}^{\infty} \begin{cases} a^{n/2},&n\text{ even},\\ 0,&n\text{ odd} \end{cases} t^n\right)-1 =\sum_{r=1}^{\infty}a^rt^{2r}.Ga​(t)=(n=0∑∞​{an/2,0,​n even,n odd​tn)−1=r=1∑∞​art2r.

The division n/2n/2n/2 in the coefficient formula is natural-number division. The constant coefficient is zero, every odd-degree coefficient is zero, and the coefficient of t2rt^{2r}t2r is ara^rar for r≥1r\ge1r≥1. No commutativity of AAA or invertibility of aaa is assumed.

QAlgorithms.Papers.Independent.Intakenext100.P34.ps

For every semiring AAA and every a∈Aa\in Aa∈A, this abbreviation denotes the constant formal power series

ps⁡(a)=a∈A[[T]],\operatorname{ps}(a)=a\in A[[T]],ps(a)=a∈A[[T]],

whose coefficient of degree zero is aaa and whose coefficient of every positive degree is 000. Commutativity of AAA is not assumed.

QAlgorithms.Papers.Independent.Intakenext100.P34.seriesTail

For any semiring AAA and any formal power series s(t)=∑m≥0smtm∈A[[t]]s(t)=\sum_{m\ge0}s_mt^m\in A[[t]]s(t)=∑m≥0​sm​tm∈A[[t]], this definition gives

Tail⁡(s)(t)=∑m≥0sm+1tm.\operatorname{Tail}(s)(t)=\sum_{m\ge0}s_{m+1}t^m.Tail(s)(t)=m≥0∑​sm+1​tm.

Thus the constant coefficient of the result is s1s_1s1​, and its coefficient of degree mmm is the coefficient of degree m+1m+1m+1 of sss; the original constant coefficient is discarded. No commutativity or subtraction assumption on AAA is required.

QAlgorithms.Papers.Independent.Intakenext100.P34.signedPow

For every type AAA equipped with a monoid structure, every two elements a,u∈Aa,u\in Aa,u∈A, and every integer nnn, this defines

signedPow⁡(a,u,n)={an,n≥0,u−n,n<0,\operatorname{signedPow}(a,u,n)= \begin{cases} a^n,&n\ge 0,\\ u^{-n},&n<0, \end{cases}signedPow(a,u,n)={an,u−n,​n≥0,n<0,​

where each exponent in the selected branch is a natural number. In particular, the value at n=0n=0n=0 is 111. The second argument, named “inverse” in the definition, is arbitrary: no hypothesis requires au=1au=1au=1 or ua=1ua=1ua=1.

QAlgorithms.Papers.Independent.Intakenext100.P34.trans

For every natural number kkk and every iii satisfying 0≤i<k−10\le i<k-10≤i<k−1, where subtraction is truncated at zero, trans⁡(i)\operatorname{trans}(i)trans(i) is the permutation of {0,…,k−1}\{0,\ldots,k-1\}{0,…,k−1} that exchanges iii and i+1i+1i+1 and fixes every other element. There are no such inputs when k=0k=0k=0 or k=1k=1k=1.

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