ExampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)audited 2026-10-08

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The complete S3 multiplication table in both normalizations

Example

Let $S = {s, t}$ with $m (s, t) = 3$ , so that $W = ⟨ s, t ∣ s^{2} = t^{2} = (s t)^{3} = 1 ⟩ ≅ S_{3}$ with elements $1, s, t, s t, t s, w_{0} : = s t s = t s t$ of lengths $0, 1, 1, 2, 2, 3$ (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups; the identification with $S_{3}$ is the type- $A$ clause of Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification). The odd-edge graph is connected, so $R = Z [v^{\pm 1}]$ , $v_{s} = v_{t} = v$ , and $H$ is free with basis ${T_{w}}$ (The standard basis of the generic Hecke algebra and base change).

Normalized table. With $u : = v - v^{- 1}$ and the columns indexed by $1, s, t, s t, t s, w_{0}$ , the complete $6 \times 6$ left-multiplication table of $H$ is $\begin{array}{ccccccc} T_{x} \ T_{y} & T_{1} & T_{s} & T_{t} & T_{s t} & T_{t s} & T_{w_{0}} \\ T_{1} & T_{1} & T_{s} & T_{t} & T_{s t} & T_{t s} & T_{w_{0}} \\ T_{s} & T_{s} & u T_{s} + T_{1} & T_{s t} & T_{t} + u T_{s t} & T_{w_{0}} & T_{t s} + u T_{w_{0}} \\ T_{t} & T_{t} & T_{t s} & u T_{t} + T_{1} & T_{w_{0}} & T_{s} + u T_{t s} & T_{s t} + u T_{w_{0}} \\ T_{s t} & T_{s t} & T_{w_{0}} & T_{s} + u T_{s t} & T_{t s} + u T_{w_{0}} & T_{1} + u T_{s} + u T_{w_{0}} & T_{t} + u T_{s t} + u T_{t s} + u^{2} T_{w_{0}} \\ T_{t s} & T_{t s} & T_{t} + u T_{t s} & T_{w_{0}} & T_{1} + u T_{t} + u T_{w_{0}} & T_{s t} + u T_{w_{0}} & T_{s} + u T_{t s} + u T_{s t} + u^{2} T_{w_{0}} \\ T_{w_{0}} & T_{w_{0}} & T_{s t} + u T_{w_{0}} & T_{t s} + u T_{w_{0}} & T_{s} + u T_{s t} + u T_{t s} + u^{2} T_{w_{0}} & T_{t} + u T_{t s} + u T_{s t} + u^{2} T_{w_{0}} & T_{1} + u (T_{s} + T_{t}) + u^{2} (T_{s t} + T_{t s}) + (u^{3} + u) T_{w_{0}} \end{array}$ In particular $T_{s} T_{t} = T_{s t}$ , $T_{t} T_{s} = T_{t s}$ , the braid identity $T_{s} T_{t} T_{s} = T_{w_{0}} = T_{t} T_{s} T_{t}$ holds, and $T_{s}^{2} = u T_{s} + T_{1}$ , $T_{t}^{2} = u T_{t} + T_{1}$ (Reduced-word independence of T_w and the length-multiplication rules; the table is a finite computation from those rules).
Multiplicative table. Put $Q : = v^{2}$ , $S_{s} : = v T_{s}$ , $S_{t} : = v T_{t}$ and $S_{w} : = S_{s_{1}} \dots S_{s_{k}} = v^{ℓ (w)} T_{w}$ for a reduced expression $w = s_{1} \dots s_{k}$ (well defined, since the $S$ 's satisfy the braid relations). Then $S_{s} S_{w} = {\begin{cases} S_{s w}, & ℓ (s w) = ℓ (w) + 1, \\ Q S_{s w} + (Q - 1) S_{w}, & ℓ (s w) = ℓ (w) - 1, \end{cases}$ and the same rule holds with $S_{t}$ . With $a : = Q - 1$ , the complete multiplicative table is $\begin{array}{ccccccc} S_{x} \ S_{y} & S_{1} & S_{s} & S_{t} & S_{s t} & S_{t s} & S_{w_{0}} \\ S_{1} & S_{1} & S_{s} & S_{t} & S_{s t} & S_{t s} & S_{w_{0}} \\ S_{s} & S_{s} & Q S_{1} + a S_{s} & S_{s t} & Q S_{t} + a S_{s t} & S_{w_{0}} & Q S_{t s} + a S_{w_{0}} \\ S_{t} & S_{t} & S_{t s} & Q S_{1} + a S_{t} & S_{w_{0}} & Q S_{s} + a S_{t s} & Q S_{s t} + a S_{w_{0}} \\ S_{s t} & S_{s t} & S_{w_{0}} & Q S_{s} + a S_{s t} & Q S_{t s} + a S_{w_{0}} & Q^{2} S_{1} + Q a S_{s} + a S_{w_{0}} & Q^{2} S_{t} + Q a (S_{s t} + S_{t s}) + a^{2} S_{w_{0}} \\ S_{t s} & S_{t s} & Q S_{t} + a S_{t s} & S_{w_{0}} & Q^{2} S_{1} + Q a S_{t} + a S_{w_{0}} & Q S_{s t} + a S_{w_{0}} & Q^{2} S_{s} + Q a (S_{t s} + S_{s t}) + a^{2} S_{w_{0}} \\ S_{w_{0}} & S_{w_{0}} & Q S_{s t} + a S_{w_{0}} & Q S_{t s} + a S_{w_{0}} & Q^{2} S_{s} + Q a (S_{s t} + S_{t s}) + a^{2} S_{w_{0}} & Q^{2} S_{t} + Q a (S_{t s} + S_{s t}) + a^{2} S_{w_{0}} & Q^{3} S_{1} + Q^{2} a (S_{s} + S_{t}) + Q a^{2} (S_{s t} + S_{t s}) + (a^{3} + Q a) S_{w_{0}} \end{array}$ The rows for $S_{s t}$ , $S_{t s}$ and $S_{w_{0}}$ are obtained by composing the generator rows; in expanded $Q$ -notation, $S_{w_{0}} S_{w_{0}} = Q^{3} S_{1} + (Q^{3} - Q^{2}) (S_{s} + S_{t}) + (Q^{3} - 2 Q^{2} + Q) (S_{s t} + S_{t s}) + (Q^{3} - 2 Q^{2} + 2 Q - 1) S_{w_{0}}$ (The reversal anti-involution, generator invertibility, the bar operator and the multiplicative normalization, part 4). The conversion between the two tables is $T_{w} = v^{- ℓ (w)} S_{w}$ ; it maps the normalized table above to the multiplicative one.
Sanity checks. Both tables satisfy the braid identity and are associative, because they are the tables of the associative algebras $H$ and its rescaling; the substitution $v = 1$ (so $Q = 1$ ) turns them into the multiplication table of the group ring $Z [S_{3}]$ (Specialization of the generic Hecke algebra to the group ring).

Facts & Assumptions

Given: The generators $s, t$ with $m (s, t) = 3$ , the group $W ≅ S_{3}$ with its six elements and lengths, the ring $R = Z [v^{\pm 1}]$ and the algebra $H$ with standard basis ${T_{w}}$ .

[F1]

$R = Λ_{Z, 1}$ , $H$ is the quotient of the free associative $R$ -algebra on $T_{s}, T_{t}$ by the quadratic relations and the single braid relation $T_{s} T_{t} T_{s} = T_{t} T_{s} T_{t}$ , and $v$ is a unit. (Universal parameters, the generic Coxeter Hecke algebra and generator conjugacy)

[F2]

For every reduced expression $w = s_{1} \dots s_{k}$ the element $T_{w} = T_{s_{1}} \dots T_{s_{k}}$ is well defined, and $T_{s} T_{w} = T_{s w}$ if $ℓ (s w) = ℓ (w) + 1$ while $T_{s} T_{w} = T_{s w} + (v - v^{- 1}) T_{w}$ if $ℓ (s w) = ℓ (w) - 1$ ; the analogous right-multiplication rule holds. (Reduced-word independence of T_w and the length-multiplication rules)

[F3]

${T_{w} : w \in W}$ is an $R$ -basis of $H$ . (The standard basis of the generic Hecke algebra and base change)

[F4]

$T_{s}$ is a unit with $T_{s}^{- 1} = T_{s} - (v - v^{- 1})$ ; for $Q_{s} = v^{2}$ and $S_{s} = v T_{s}$ one has $T_{s} = v^{- 1} S_{s}$ , $S_{s}$ is a unit, and $(S_{s} - Q_{s}) (S_{s} + 1) = 0$ . (The reversal anti-involution, generator invertibility, the bar operator and the multiplicative normalization)

[F5]

$W ≅ S_{3}$ via $s \mapsto (12)$ , $t \mapsto (23)$ ; its six elements $1, s, t, s t, t s, w_{0} = s t s = t s t$ have lengths $0, 1, 1, 2, 2, 3$ , and $ℓ$ agrees with the inversion number of the corresponding permutation. (Coxeter matrices, the presented Coxeter group, reduced words, length, and standard parabolic subgroups, Support, intrinsic parabolic presentations, minimal coset representatives and length additivity, with the type-A identification)

Verification

technique · direct

1.1F1F3F5

The six elements of $W$ and their lengths are those recorded in [F5], and the odd-edge graph on $S = {s, t}$ (the single edge ${s, t}$ , since $m (s, t) = 3$ is odd) is connected, so $c = 1$ , $R = Z [v^{\pm 1}]$ and $v_{s} = v_{t} = v$ by the parameter rule of [F1]. By [F3] the family ${T_{w} : w \in W}$ is an $R$ -basis of $H$ , so all tables below record well-defined elements.

1.2F2F3algebra

Expansion from the rules of [F2] gives the normalized table of part 1. For example $T_{s} T_{s t}$ : $s \cdot (s t) = t$ has length $1 < 2$ , so the entry is $T_{t} + u T_{s t}$ ; $T_{s} T_{t s}$ : $s \cdot (t s) = w_{0}$ has length $3 > 2$ , so the entry is $T_{w_{0}}$ ; $T_{w_{0}} T_{s}$ : $w_{0} s = s t$ has length $2 < 3$ , so the entry is $T_{s t} + u T_{w_{0}}$ ; $T_{s t} T_{w_{0}}$ : $(s t) w_{0} = t$ has length $1 < 2$ , so $T_{s t} T_{w_{0}} = T_{s} (T_{t} T_{w_{0}}) = T_{s} (T_{s t} + u T_{w_{0}}) = T_{s} T_{s t} + u T_{s} T_{w_{0}} = (T_{t} + u T_{s t}) + u (T_{t s} + u T_{w_{0}}) = T_{t} + u T_{s t} + u T_{t s} + u^{2} T_{w_{0}}$ ; and $T_{w_{0}} T_{w_{0}} = (T_{w_{0}} T_{s t}) T_{s} = (T_{s} + u T_{s t} + u T_{t s} + u^{2} T_{w_{0}}) T_{s} = T_{1} + u (T_{s} + T_{t}) + u^{2} (T_{s t} + T_{t s}) + (u^{3} + u) T_{w_{0}}$ , using $T_{s t} T_{s} = T_{w_{0}}$ , $T_{t s} T_{s} = T_{t} + u T_{t s}$ , $T_{w_{0}} T_{s} = T_{s t} + u T_{w_{0}}$ and $T_{s}^{2} = T_{1} + u T_{s}$ . The remaining entries are computed in the same way by left multiplication by a reduced expression of the row element; the displayed table records all $36$ products.

2.1F2F4step 1.1step 1.2algebra

Multiplying the rules of 1.2 by $v^{ℓ (w) + 1}$ gives the multiplicative rule $S_{s} S_{w} = S_{s w}$ when $ℓ (s w) = ℓ (w) + 1$ and $S_{s} S_{w} = Q S_{s w} + (Q - 1) S_{w}$ when $ℓ (s w) = ℓ (w) - 1$ , and similarly for $S_{t}$ : for instance $S_{s} S_{s} = v^{2} T_{s}^{2} = v^{2} (u T_{s} + T_{1}) = v^{2} u v^{- 1} S_{s} + Q S_{1} = (Q - 1) S_{s} + Q S_{1}$ because $v u = v^{2} - 1 = Q - 1$ ; and $S_{s} S_{w_{0}} = v^{4} T_{s} T_{w_{0}} = v^{4} (T_{t s} + u T_{w_{0}}) = Q S_{t s} + (Q - 1) S_{w_{0}}$ . The $S_{s}$ - and $S_{t}$ -rows are the translations of the corresponding rows of the normalized table; since $S_{s t} = S_{s} S_{t}$ , $S_{t s} = S_{t} S_{s}$ and $S_{w_{0}} = S_{s} S_{t s}$ (each $S_{w}$ is the product of the $S$ 's along a reduced expression), associativity of $H$ composes the generator rows into the other displayed rows, with $a = Q - 1$ ; and converting the entry $T_{w_{0}} T_{w_{0}} = T_{1} + u (T_{s} + T_{t}) + u^{2} (T_{s t} + T_{t s}) + (u^{3} + u) T_{w_{0}}$ with $S_{w} = v^{ℓ (w)} T_{w}$ gives the stated $S_{w_{0}} S_{w_{0}}$ .

3.1F1F4step 1.2step 2.1∎

The two tables are converted into one another by $T_{w} = v^{- ℓ (w)} S_{w}$ , which is $T_{s} = v^{- 1} S_{s}$ on generators and extends to products; it maps each entry of the normalized table to the corresponding entry of the multiplicative table by the computation of 2.1. Both tables satisfy the braid identity $T_{s} T_{t} T_{s} = T_{w_{0}} = T_{t} T_{s} T_{t}$ because it is the defining braid relation of $H$ ([F1]), and both are associative because $H$ is a quotient of an associative algebra; the substitution $v = 1$ (so $u = 0$ and $Q = 1$ ) turns the normalized table into the group-ring table of $Z [S_{3}]$ , as recorded in Specialization of the generic Hecke algebra to the group ring, and the multiplicative table into the same table since $S_{w} = T_{w}$ and $Q = 1$ there. All computations are over $Z [v^{\pm 1}]$ and use no choice.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

44 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

George Lusztig, Lectures on Hecke Algebras with Unequal Parameters (MIT Fall 1999 lecture notes, arXiv:math/0108172v1) (standard reference, not scraped)
Meinolf Geck, Modular Representations of Hecke Algebras (EPFL course notes, arXiv:math/0511548v2) (standard reference, not scraped)
Anders Bjorner and Francesco Brenti, Combinatorics of Coxeter Groups, Springer GTM 231 (2005), complete book PDF (standard reference, not scraped)