Proof of Counting Cyclically Reduced Words: Finiteness and the Bound (2d)^k

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

Throughout, $2d$ denotes the natural number $d+d$, and also its image in $\mathbb{R}$ under the canonical map $\iota_{\mathbb{R}}$ of The Canonical Map from the Natural Numbers to a Field; the power $(2d)^{k}$ is that of this real number. Sums over finite index sets are those of Sum over a Finite Index Set.

Clause 1 (finiteness). Let $k\in\mathbb{N}$. By claim 1 of Basic Properties of Finite Sets, $[2d]$ has $2d$ elements, so it is finite by Finite Set; it is nonempty because $1\in[2d]$, as $1\le 2d$ by claim 4 of Properties of the Order on the Natural Numbers. Hence, by claim 3 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets (with $X=[2d]$ and $n=k$), the set $[2d]^{k}$ is nonempty and finite. By claim 3 of Basic Properties of Finite Sets, every subset of $[2d]^{k}$, in particular every nonempty one, is finite.

The set $W^{\circ}_{d,k}$ is a subset of $[2d]^{k}$, since by Reduced and Cyclically Reduced Words in Unitary Letters §cyclically-reduced its elements are words of length $k$, which are the elements of $[2d]^{k}$ by Words over a Finite Alphabet: the Empty Word, Concatenation and Reversal §words; so it is finite once it is nonempty. Let $o$ be the map $[k]\to[2d]$ with constant value $1$, a word of length $k$. Since $1\le d$ (claim 4 of Properties of the Order on the Natural Numbers), Words in Unitary Letters: Generators, Signs, Inverse Letters, Lengths and Adjoint Words §letters gives $1^{-1}=d+1$, and $d+1\ne1$ by claim 7 of Arithmetic of Addition on the Natural Numbers. Therefore $o_{i+1}=1\ne1^{-1}=(o_{i})^{-1}$ for every $i\in[k]$ with $i<k$, so $o$ is reduced by Reduced and Cyclically Reduced Words in Unitary Letters §reduced; and if $1<k$ then $o_{k}=1\ne1^{-1}=(o_{1})^{-1}$, so $o$ is cyclically reduced by Reduced and Cyclically Reduced Words in Unitary Letters §cyclically-reduced. Thus $o\in W^{\circ}_{d,k}$, and $W^{\circ}_{d,k}$ is nonempty and finite.

Step A (sums of ones over initial segments). For $n\in\mathbb{N}$, let $u^{n}:[n]\to\mathbb{R}$ be the map with constant value $1$. By claim 1 of Properties of a Sum over a Finite Index Set and The Canonical Map from the Natural Numbers to a Field,

$$\sum_{x\in[n]}1=\sum_{k=1}^{n}u^{n}_{k}=\iota_{\mathbb{R}}(n).\tag{A}$$

Step B (the sum of ones over $[2d]^{k}$). For $k\in\mathbb{N}$ put $N_{k}=\sum_{t\in[2d]^{k}}1$, defined because $[2d]^{k}$ is nonempty and finite by clause 1. We prove $N_{k}=(2d)^{k}$ for all $k\in\mathbb{N}$ by the principle of induction Principle of Induction for the Natural Numbers, applied to the set of $k\in\mathbb{N}$ for which it holds.

Base $k=1$. The initial segment $[1]$ is $\{1\}$: if $m\in[1]$ then $m\le1$, and $1\le m$ by claim 4 of Properties of the Order on the Natural Numbers, so $m=1$ by claim 2 of that lemma. Hence the map $\theta:[2d]\to[2d]^{1}$ sending $x$ to the $1$-tuple with component $x$ is a bijection: it is injective because the component at $1$ of $\theta(x)$ is $x$, and surjective because every $t\in[2d]^{1}$, being a map on $\{1\}$, equals $\theta(t_{1})$. By claim 2 of Properties of a Sum over a Finite Index Set (reindexing along $\theta$, with the constant map $1$ on $[2d]^{1}$) and (A),

$$N_{1}=\sum_{x\in[2d]}1=\iota_{\mathbb{R}}(2d)=(2d)^{1},$$

the last equality by claim 1 of Properties of Natural Number Powers in a Field.

Step. Suppose $N_{k}=(2d)^{k}$ for some $k\in\mathbb{N}$, and write $S$ for the successor map. By claim 2 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets (with $Y=[2d]$ and $n=k$) there is a bijection $q:[2d]^{k}\times[2d]\to[2d]^{S(k)}$. The Cartesian product $[2d]^{k}\times[2d]$ is finite by claim 1 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets, and nonempty since it contains $(t_{0},x_{0})$ for any $t_{0}\in[2d]^{k}$ and $x_{0}\in[2d]$, both sets being nonempty by clause 1. By claim 2 of Properties of a Sum over a Finite Index Set (reindexing along $q$), then by The Product of Two Sums over Finite Index Sets is a Sum over the Cartesian Product (with the constant maps $1$ on $[2d]^{k}$ and on $[2d]$, using $1\cdot1=1$), and finally by (A),

$$N_{S(k)}=\sum_{p\in[2d]^{k}\times[2d]}1=\Bigl(\sum_{t\in[2d]^{k}}1\Bigr)\Bigl(\sum_{x\in[2d]}1\Bigr)=N_{k}\cdot\iota_{\mathbb{R}}(2d)=(2d)^{k}\,(2d)=(2d)^{S(k)},$$

the last equality by claim 1 of Properties of Natural Number Powers in a Field. This completes the induction.

Clause 2 (counting bound). Let $k$, $B$, $M$ and $a$ be as in clause 2, and put $G=[2d]^{k}$. Since $B$ is nonempty, pick $w_{0}\in B$; then $0\le a(w_{0})\le M$, so $0\le M$. Define $a':G\to\mathbb{R}$ by $a'(w)=a(w)$ for $w\in B$ and $a'(w)=0$ for $w\in G\setminus B$. Then $0\le a'(w)\le M$ for every $w\in G$ (for $w\notin B$ because $0\le M$), and the restriction of $a'$ to $B$ is $a$. The sets $G$ and $B$ are nonempty and finite by clause 1. By Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §monotone (with $h=a'$ and $E=B$), then by Real Sums over a Finite Index Set: Comparison, Nonnegativity, Monotonicity, Term Bounds, Absolute Values, Counting and Limits §comparison (with $h=a'$ and $h'$ the constant map $M$), then by claim 4 of Properties of a Sum over a Finite Index Set (homogeneity, with $M=M\cdot1$), and finally by Step B,

$$\sum_{w\in B}a(w)=\sum_{w\in B}a'(w)\le\sum_{w\in G}a'(w)\le\sum_{w\in G}M=M\sum_{w\in G}1=M\,N_{k}=M\,(2d)^{k}.$$