Proof of Unitary Laws: Adjoints, the Bound One, and Reduction to Cyclically Reduced Words

Each result cited below is universally quantified over the data in its own statement.

Write $W=W_{2d}$. Words are compared as maps: two words of the same length $k$ are equal when their components agree on $[k]$. Lengths are handled as follows: by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, if $u,v$ have lengths $k,l$ then $uv$ has length $k+l$, so $|uv|=|u|+|v|$ by claim 4 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field; this also holds if $u$ or $v$ is $\varnothing$, since $\varnothing u=u\varnothing=u$ and $|\varnothing|=0$ (Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §length). Every length is nonnegative, being $0$ or the image of a natural number, positive by claim 3 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field. Natural-number arithmetic uses Properties of the Order on the Natural Numbers and Arithmetic of Addition on the Natural Numbers.

Step W1 (inverse letters are involutive). For every $l\in[2d]$, $(l^{-1})^{-1}=l$. Indeed, by Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §letters: if $l\le d$, then $l^{-1}=d+l$, and $d<d+l$ by claim 6 of Properties of the Order on the Natural Numbers, so $d+l$ falls under the second case of the definition, with $j=l$ the unique $j$ such that $d+l=d+j$; hence $(d+l)^{-1}=l$. If $d<l$, then $l=d+j$ with $j\in[d]$ and $l^{-1}=j$; since $j\le d$, the first case gives $j^{-1}=d+j=l$.

Step W2 (adjoints). For $w\in W$ let $w^{\iota}\in W$ be given by $\varnothing^{\iota}=\varnothing$ and, if $w$ has length $k$, $(w^{\iota})_{i}=(w_{i})^{-1}$ for $i\in[k]$, a word of length $k$. By Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §adjoint, $w^{*}=(w^{\mathrm{rev}})^{\iota}$ for every $w$ (both sides are $\varnothing$ when $w=\varnothing$). We record:

(a) $(uv)^{\iota}=u^{\iota}v^{\iota}$ for all $u,v\in W$. If $u=\varnothing$ or $v=\varnothing$ this follows from $\varnothing^{\iota}=\varnothing$ and Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid. Otherwise, with lengths $k,l$, both sides have length $k+l$, and by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation, for $i\in[k]$ both have $i$-th component $(u_{i})^{-1}$, and for $i\in[l]$ both have $(k+i)$-th component $(v_{i})^{-1}$; these indices exhaust $[k+l]$ by that clause.

(b) $(w^{\iota})^{\iota}=w$, componentwise by W1.

(c) $(w^{\mathrm{rev}})^{\iota}=(w^{\iota})^{\mathrm{rev}}$: for $w$ of length $k$ and $i\in[k]$, with $j\in[k]$ such that $i+j=k+1$, both $i$-th components equal $(w_{j})^{-1}$ by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §reversal; for $w=\varnothing$ both sides are $\varnothing$.

Consequently, for all $u,v,w\in W$ and every letter $l\in[2d]$:

$$(uv)^{*}=v^{*}u^{*},\qquad (w^{*})^{*}=w,\qquad (l)^{*}=(l^{-1}),\qquad |w^{*}|=|w| .\tag{W2}$$

Indeed, $(uv)^{*}=((uv)^{\mathrm{rev}})^{\iota}=(v^{\mathrm{rev}}u^{\mathrm{rev}})^{\iota}=(v^{\mathrm{rev}})^{\iota}(u^{\mathrm{rev}})^{\iota}=v^{*}u^{*}$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal and (a); $(w^{*})^{*}=\bigl(((w^{\mathrm{rev}})^{\iota})^{\mathrm{rev}}\bigr)^{\iota}=\bigl(((w^{\mathrm{rev}})^{\mathrm{rev}})^{\iota}\bigr)^{\iota}=w$ by (c) applied to $w^{\mathrm{rev}}$, Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal and (b); $(l)^{*}=((l)^{\mathrm{rev}})^{\iota}=(l)^{\iota}=(l^{-1})$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §reversal; and $w^{*}$ has the length of $w$ by Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §adjoint.

Step W3 (cancellation of $bb^{*}$). For every $\mu\in\mathcal{L}_{d}$ and all $u,v,b\in W$,

$$\mu(u\,b\,b^{*}\,v)=\mu(uv).\tag{W3}$$

If $b=\varnothing$ this is Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, as $\varnothing^{*}=\varnothing$. For words $b$ of a length $n\in\mathbb{N}$ we use induction on $n$ (Principle of Induction for the Natural Numbers), the statement at $n$ being that (W3) holds for all $u,v$ and all $b$ of length $n$. For $n=1$, $b$ is a letter $(l)$ by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter, $b^{*}=(l^{-1})$ by (W2), and (W3) is Laws of d-Tuples of Unitaries §cancellation. If the statement holds at $n$ and $b$ has length $S(n)$, then $b=b'(j)$ with $b'$ of length $n$ and a letter $j$ (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §last-letter), $b^{*}=(j^{-1})\,b'^{*}$ by (W2), and by associativity (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid), Laws of d-Tuples of Unitaries §cancellation and the statement at $n$,

$$\mu(u\,b\,b^{*}\,v)=\mu\bigl((ub')\,j\,j^{-1}\,(b'^{*}v)\bigr)=\mu(u\,b'\,b'^{*}\,v)=\mu(uv).$$

Clauses 1 and 2 (adjoints and the bound). Let $\lambda\in\mathcal{L}_{d}$ and $w\in W$. Complex arithmetic uses Properties of Complex Conjugation and Modulus: by its claim 1 conjugation is additive and multiplicative and fixes real numbers, so $\overline{1}=1$ and $\overline{-c}=-\overline{c}$ (as $\overline{-c}+\overline{c}=\overline{0}=0$); by its claim 3, $c\,\overline{c}=|c|^{2}$.

If $w=\varnothing$: $\lambda(\varnothing^{*})=\lambda(\varnothing)=1=\overline{1}=\overline{\lambda(\varnothing)}$ by Laws of d-Tuples of Unitaries §normalised, and $|\lambda(\varnothing)|=|1|=1\le1$ by claim 8 of Properties of Complex Conjugation and Modulus.

Let $w\ne\varnothing$ and put $c=\lambda(w)$. By claims 1 and 2 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set, $\{\varnothing\}$ is nonempty and finite, and, since $w\notin\{\varnothing\}$, $F=\{\varnothing\}\cup\{w\}$ is nonempty and finite. By Laws of d-Tuples of Unitaries §positive, $K(v,v')=\lambda(v^{*}v')$ is a positive semidefinite kernel on $F$ (Positive Semidefinite Kernel on a Finite Set §kernel). Its values are, by Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid, $\varnothing^{*}=\varnothing$, Laws of d-Tuples of Unitaries §normalised, and (W3) with $u=v=\varnothing$ and $b=w^{*}$ together with $(w^{*})^{*}=w$ from (W2):

$$K(\varnothing,\varnothing)=\lambda(\varnothing)=1,\quad K(\varnothing,w)=\lambda(w)=c,\quad K(w,\varnothing)=\lambda(w^{*}),\quad K(w,w)=\lambda\bigl(w^{*}(w^{*})^{*}\bigr)=\lambda(\varnothing)=1 .$$

Clause 1. The symmetry condition of Positive Semidefinite Kernel on a Finite Set §kernel gives $K(w,\varnothing)=\overline{K(\varnothing,w)}$, that is, $\lambda(w^{*})=\overline{\lambda(w)}=\overline{c}$.

Clause 2. Let $z:F\to\mathbb{C}$ be given by $z(\varnothing)=-c$ and $z(w)=1$, and put $f(u,v)=\overline{z(u)}\,z(v)\,K(u,v)$ for $(u,v)\in F\times F$. The set $F\times F$ is the set of ordered pairs $(u,v)$ with $u\in F$ and $v\in F$, so Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §pairs (with $A=F$ and $B(u)=F$) and then claims 1 and 2 of Peeling, Splitting, and Interchange for Sums over a Finite Index Set, applied to each inner sum and to the outer sum over $F=\{\varnothing\}\cup\{w\}$, give

$$Q_{K}(z)=\sum_{u\in F}\Bigl(\sum_{v\in F}f(u,v)\Bigr)=f(\varnothing,\varnothing)+f(\varnothing,w)+f(w,\varnothing)+f(w,w).$$

Using $\overline{z(\varnothing)}=-\overline{c}$, $\overline{z(w)}=1$ and clause 1, the four terms are $(-\overline{c})(-c)\cdot1=|c|^{2}$, $(-\overline{c})\cdot1\cdot c=-|c|^{2}$, $1\cdot(-c)\,\overline{c}=-|c|^{2}$ and $1\cdot1\cdot1=1$, so $Q_{K}(z)=1-|c|^{2}$, a real number, the operations on real numbers in $\mathbb{C}$ being those of $\mathbb{R}$ (condition 1 of The Complex Numbers). By Positive Semidefinite Kernel on a Finite Set §kernel it is nonnegative, so $|c|^{2}\le1=1^{2}$ (claim 3 of Elementary Arithmetic in an Ordered Field). Since $0\le|c|$ (Modulus of a Complex Number) and $0\le1$, the weak form, claim 2 of Monotonicity of Squaring on the Nonnegative Elements of an Ordered Field, gives $|\lambda(w)|=|c|\le1$.

Clause 3 (stripping a reduced word). First, if $z$ is cyclically reduced (in particular if $z=\varnothing$, which is reduced by Reduced and Cyclically Reduced Words in Unitary Letters §reduced and has no length $k$ with $1<k$), take $b=\varnothing$ and $u=z\in W^{\circ}_{d}$: then $b\,u\,b^{*}=\varnothing z\varnothing=z$ and $2|b|+|u|=|z|$. Every reduced word of length $1$ is cyclically reduced, by Reduced and Cyclically Reduced Words in Unitary Letters §cyclically-reduced, since $1<1$ fails.

For words of a length in $\mathbb{N}$ we prove, by induction on $n\in\mathbb{N}$ (Principle of Induction for the Natural Numbers), the statement $P(n)$: every reduced $z$ of a length $m\in\mathbb{N}$ with $m\le n$ admits $b\in W$ and $u\in W^{\circ}_{d}$ with $z=b\,u\,b^{*}$ and $|z|=2|b|+|u|$. $P(1)$ holds: $m\le1$ forces $m=1$ (claims 4 and 2 of Properties of the Order on the Natural Numbers), and such $z$ is cyclically reduced. Assume $P(n)$ and let $z$ be reduced of length $m\le S(n)$. If $m\ne S(n)$, then $m\le n$ by claim 5 of Properties of the Order on the Natural Numbers and $P(n)$ applies. Let $m=S(n)$. If $z$ is cyclically reduced we are done, so assume it is not. As $z$ is reduced, Reduced and Cyclically Reduced Words in Unitary Letters §cyclically-reduced gives $1<m$ and $z_{m}=(z_{1})^{-1}$. Then $m\ne2$: otherwise, with $i=1<2=m$, Reduced and Cyclically Reduced Words in Unitary Letters §reduced would give $z_{2}\ne(z_{1})^{-1}$. By claim 7 of Properties of the Order on the Natural Numbers write $m=1+j$ with $j\in\mathbb{N}$; $j\ne1$, so $j=r+1$ for some $r\in\mathbb{N}$ by claims 6 and 1 of Arithmetic of Addition on the Natural Numbers, and $m=1+(r+1)=(1+r)+1$ by associativity (claim 3 of Arithmetic of Addition on the Natural Numbers). From $n+1=S(n)=m=(1+r)+1$, cancellation (claim 5 of Arithmetic of Addition on the Natural Numbers) gives $n=1+r$, so $r<n$ by claim 6 of Properties of the Order on the Natural Numbers (with commutativity), and $r\le n$.

Define $z'\in[2d]^{r}$ by $z'_{i}=z_{1+i}$ for $i\in[r]$; here $1+i\le1+r<m$ by claim 6 of Properties of the Order on the Natural Numbers, so $1+i\in[m]$ and $1+i<m$. The word $z'$ is reduced: for $i\in[r]$ with $i<r$, $z'_{i+1}=z_{1+(i+1)}=z_{(1+i)+1}\ne(z_{1+i})^{-1}=(z'_{i})^{-1}$ by associativity (claim 3 of Arithmetic of Addition on the Natural Numbers) and Reduced and Cyclically Reduced Words in Unitary Letters §reduced applied to $z$ at the index $1+i<m$. Moreover

$$z=(z_{1})\,z'\,(z_{m})=(z_{1})\,z'\,(z_{1})^{*},$$

the first equality because, by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation, the word $\bigl((z_{1})z'\bigr)(z_{m})$ has length $(1+r)+1=m$, its component at $1$ is $z_{1}$, at $1+i$ ($i\in[r]$) is $z'_{i}=z_{1+i}$, and at $(1+r)+1=m$ is $z_{m}$, these indices exhausting $[m]$; the second because $(z_{m})=((z_{1})^{-1})=(z_{1})^{*}$ by (W2). By $P(n)$, applied to $z'$ (of length $r\le n$), there are $b'\in W$ and $u\in W^{\circ}_{d}$ with $z'=b'\,u\,b'^{*}$ and $|z'|=2|b'|+|u|$. Put $b=(z_{1})\,b'$. By (W2), $b^{*}=b'^{*}(z_{1})^{*}$, so by associativity (Basic Properties of Words: Associativity, Reversal, Finitely Many Factorisations, and Countability §monoid) $z=(z_{1})\,b'\,u\,b'^{*}\,(z_{1})^{*}=b\,u\,b^{*}$. Finally $|b|=1+|b'|$ and $|z|=(\text{image of }r)+2=|z'|+2$ by the length rule recalled at the start and claims 1 and 4 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, so $2|b|+|u|=2|b'|+|u|+2=|z'|+2=|z|$. This proves $P(S(n))$ and hence clause 3, every reduced word being $\varnothing$ or of some length $m\le m$.

Clause 4 (conjugation invariance). Let $b,u\in W$ and $\mu\in\mathcal{L}_{d}$. By Laws of d-Tuples of Unitaries §cyclic with the factorisation $b\,(u\,b^{*})$, then by (W3) with $u$, $\varnothing$ and $b^{*}$ in the roles of $u$, $v$ and $b$, using $(b^{*})^{*}=b$ from (W2),

$$\mu(b\,u\,b^{*})=\mu(u\,b^{*}\,b)=\mu\bigl(u\,b^{*}(b^{*})^{*}\varnothing\bigr)=\mu(u\varnothing)=\mu(u).$$

The second sentence of clause 4 is the special case in which $z=b\,u\,b^{*}$.

Clause 5 (reduction). If $w=\varnothing$, take $u=\varnothing\in W^{\circ}_{d}$. For words of a length in $\mathbb{N}$ we prove by induction on $n\in\mathbb{N}$ the statement $R(n)$: for every $w$ of a length $m\le n$ there is $u\in W^{\circ}_{d}$ with $|u|\le|w|$ and $\mu(w)=\mu(u)$ for every $\mu\in\mathcal{L}_{d}$. We treat a word $w$ of length $m$ under the induction hypothesis that the conclusion of clause 5 holds for every word of a length $m'\in\mathbb{N}$ with $m'<m$ (as well as for $\varnothing$, done above). This yields $R(1)$, since no $m'\in\mathbb{N}$ satisfies $m'<1$ (claims 4 and 2 of Properties of the Order on the Natural Numbers), and the step from $R(n)$ to $R(S(n))$: a word of length $m\le S(n)$ has $m\le n$, covered by $R(n)$, unless $m=S(n)$ (claim 5 of that lemma), in which case every $m'<m=S(n)$ satisfies $m'\le n$ (claim 5 again), so $R(n)$ supplies the induction hypothesis. By Principle of Induction for the Natural Numbers, $R(n)$ then holds for every $n$, and each word of length $m$ is covered by $R(m)$.

Case 1: $w$ is reduced. By clause 3 there are $b\in W$ and $u\in W^{\circ}_{d}$ with $w=b\,u\,b^{*}$ and $|w|=2|b|+|u|$. Since $0\le|b|$, $|u|=|w|-2|b|\le|w|$, and $\mu(w)=\mu(u)$ for every $\mu\in\mathcal{L}_{d}$ by clause 4.

Case 2: $w$ is not reduced. By Reduced and Cyclically Reduced Words in Unitary Letters §reduced there is $i\in[m]$ with $i<m$ and $w_{i+1}=(w_{i})^{-1}$; write $l=w_{i}$. By claim 7 of Properties of the Order on the Natural Numbers write $m=i+t$ with $t\in\mathbb{N}$. Let $x=\varnothing$ if $i=1$, and otherwise, writing $i=i'+1$ (claims 6 and 1 of Arithmetic of Addition on the Natural Numbers), let $x$ be the restriction of $w$ to $[i']$, a word of length $i'$. Let $y=\varnothing$ if $t=1$, and otherwise, writing $t=1+t'$, let $y\in[2d]^{t'}$ be given by $y_{j}=w_{(i+1)+j}$ for $j\in[t']$ (here $(i+1)+j\le(i+1)+t'$ by claim 6 of Properties of the Order on the Natural Numbers, and $(i+1)+t'=i+(1+t')=i+t=m$ by associativity, claim 3 of Arithmetic of Addition on the Natural Numbers). By Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §concatenation, the word $x\,(l)\,(l^{-1})\,y$ has length $m$ and the same components as $w$ (at indices before $i$ those of $x$, at $i$ and $i+1$ the letters $l=w_{i}$ and $l^{-1}=w_{i+1}$, after $i+1$ those of $y$), so $w=x\,l\,l^{-1}\,y$. By Laws of d-Tuples of Unitaries §cancellation, $\mu(w)=\mu(xy)$ for every $\mu\in\mathcal{L}_{d}$. By the length rule, $|w|=|x|+2+|y|=|xy|+2$, so $|xy|\le|w|$ and $xy$ is $\varnothing$ or has a length less than $m$ (claim 6 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field read contrapositively, with claim 3 of Properties of the Order on the Natural Numbers). By the induction hypothesis there is $u\in W^{\circ}_{d}$ with $|u|\le|xy|\le|w|$ and $\mu(xy)=\mu(u)$, hence $\mu(w)=\mu(u)$, for every $\mu\in\mathcal{L}_{d}$.

Clause 6 (determination). Let $w\in W$ and take $u$ as in clause 5; it works for $\mu$ and $\nu$ simultaneously, so $\mu(w)=\mu(u)=\nu(u)=\nu(w)$. Thus $\mu=\nu$ as maps on $W$.

Clause 7 (nonemptiness). Let $\mathbf{1}:W\to\mathbb{C}$ be the constant map $1$. Conditions Laws of d-Tuples of Unitaries §normalised, Laws of d-Tuples of Unitaries §cancellation and Laws of d-Tuples of Unitaries §cyclic hold since both sides equal $1$. For Laws of d-Tuples of Unitaries §positive, let $F\subseteq W$ be nonempty and finite; the kernel is $K(v,v')=1$. Symmetry holds as $\overline{1}=1$ (claim 1 of Properties of Complex Conjugation and Modulus). For $z:F\to\mathbb{C}$, put $\Sigma=\sum_{v\in F}z(v)$. By The Product of Two Sums over Finite Index Sets is a Sum over the Cartesian Product (with $a(u)=\overline{z(u)}$ and $b(v)=z(v)$), Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus §conjugate and claim 3 of Properties of Complex Conjugation and Modulus,

$$Q_{K}(z)=\sum_{(u,v)\in F\times F}\overline{z(u)}\,z(v)=\Bigl(\sum_{u\in F}\overline{z(u)}\Bigr)\Bigl(\sum_{v\in F}z(v)\Bigr)=\overline{\Sigma}\,\Sigma=|\Sigma|^{2},$$

which is real and nonnegative, being the product of the nonnegative real number $|\Sigma|$ with itself (claim 5 of Elementary Arithmetic in an Ordered Field). Hence $\mathbf{1}\in\mathcal{L}_{d}$, and $\mathcal{L}_{d}$ is nonempty.