An Upper Bound on the Length of an Algebra and Its Application to the Group Algebra of the Dihedral Group

Reflexivity. $u-\alpha u\in{\cal L}_{i-1}(\SS)$ with $\alpha=1.$

Symmetry. Let $u-\alpha v\in{\cal L}_{i-1}(\SS)$. Then, by multiplying the element $u-\alpha v$ by $-\alpha^{-1}$, we get $v-\alpha^{-1}u\in{\cal L}_{i-1}(\SS).$

Transitivity. Let $u-\alpha_{1}v\in{\cal L}_{i-1}(\SS)$, $v-\alpha_{2}w\in{\cal L}_{i-1}(\SS)$. Then, by adding the second element multiplied by $\alpha_{1}$ to the first one, we obtain $u-\alpha_{1}\alpha_{2}w\in{\cal L}_{i-1}(\SS).$

∎

Straightforward.

∎

Straightforward.

∎

By condition, $u-\alpha v\in{\cal L}_{j-1}(\SS)$, $w=w_{1}uw_{2}$, for some words $w_{1}$, $w_{2}$. Then, by multiplying the expression $u-\alpha v$ on the left by $w_{1}$ and on the right by $w_{2}$, we get $w-\alpha w^{\prime}\in{\cal L}_{i-1}(\SS).$ ∎

Let $l({\cal A})\geq m({\cal A})$ (otherwise the statement is proven). Let $\SS$ be a generating set of length $l({\cal A})$ of the algebra ${\cal A}$ (in the case of other generating sets the length of the algebra will be no greater). Consider an irreducible word $a_{1}a_{2}\cdots a_{l({\cal A})}$ of length $l({\cal A})$ in the alphabet $\SS$ (such exists by definition of the length of the algebra). We will prove that $\forall k\in[1,l({\cal A})-1]$ it holds that $\dim{\cal L}_{k}(\SS)-\dim{\cal L}_{k-1}(\SS)\geq 2.$

We will reason by contradiction. Suppose $\exists k\in[1,l({\cal A})-1]$ such that $\dim{\cal L}_{k}(\SS)-\dim{\cal L}_{k-1}(\SS)=1$ (this difference cannot be zero by definition of the length of the algebra). We will break the reasoning into steps and lead it to a contradiction.

First step. The word $a_{1}a_{2}\cdots a_{l({\cal A})}$ is irreducible. Therefore, its subword $a_{1}a_{2}\cdots a_{k}$ is irreducible by Lemma 3.3. By assumption $a_{2}a_{3}\cdots a_{k+1}\sim a_{1}a_{2}\cdots a_{k}$ (here we use the fact that $k$ is no greater than $l({\cal A})-1$). Indeed, if this were not the case, we would get $\dim{\cal L}_{k}(\SS)-\dim{\cal L}_{k-1}(\SS)\geq 2$, since the dimension would increase by at least 2 due to these two words. Thus, $a_{1}a_{2}\cdots a_{l({\cal A})}\sim a_{2}a_{3}\cdots a_{k}a_{k+1}a_{k+1}a_{k+2}\cdots a_{l({\cal A})}$ by Lemma 3.4. Therefore, the word $a_{2}a_{3}\cdots a_{k}a_{k+1}a_{k+1}a_{k+2}\cdots a_{l({\cal A})}$ is irreducible.

Second step. Now consider the irreducible word $a_{2}a_{3}\cdots a_{k}a_{k+1}a_{k+1}a_{k+2}\cdots a_{l({\cal A})}$ of length $l({\cal A})$ obtained in the previous step. By reasoning similarly (considering subwords of length $k$ starting from the first and second letters), we will get rid of the letter $a_{2}$ similarly to how we got rid of the letter $a_{1}$ in the first step. We obtain that the word $a_{3}a_{4}\cdots a_{k}a_{k+1}a_{k+1}a_{k+1}a_{k+2}\cdots a_{l({\cal A})}$ is irreducible.

After conducting $k$ steps of this reasoning, we obtain that the word $a_{k+1}\cdots a_{k+1}a_{k+2}\cdots a_{l({\cal A})}$ of length $l({\cal A})$ is irreducible. Now we can proceed to the last step and obtain a contradiction.

$(k+1)$-st step. The word $a_{k+1}^{k+1}a_{k+2}\cdots a_{l({\cal A})}$ is irreducible. Therefore, its subword $a_{k+1}^{k}$ is irreducible. By assumption, all words of length $k$ are expressed through the word $a_{k+1}^{k}$ and words of shorter length. Thus, $a_{1}a_{2}\cdots a_{l({\cal A})}\sim a_{k+1}^{l({\cal A})}$. Therefore, the word $a_{k+1}^{l({\cal A})}$ is irreducible and $l({\cal A})<m({\cal A})$. Contradiction.

We return to the proof of the main statement. Represent the dimension of the algebra in the following form $\dim{\cal A}=\dim{\cal L}_{l({\cal A})}(\SS)=(\dim{\cal L}_{l({\cal A})}(\SS)-\dim{\cal L}_{l({\cal A})-1}(\SS))+(\dim{\cal L}_{l({\cal A})-1}(\SS)-\dim{\cal L}_{l({\cal A})-2}(\SS))+\cdots+(\dim{\cal L}_{1}(\SS)-\dim{\cal L}_{0}(\SS))+\dim{\cal L}_{0}(\SS)$. The first term of this sum is not less than 1, the last one equals 1, and all the others are not less than 2. Thus, $\dim{\cal A}\geq 1+2(l({\cal A})-1)+1$. Therefore, $l({\cal A})\leq\frac{\dim{\cal A}}{2}$. Thus, $l({\cal A})\leq max\{m({\cal A})-1,\frac{\dim{\cal A}}{2}\}.$

∎

The equalities are checked directly by multiplying matrices. ∎

Due to Lemma 4.2 we may consider that ${\cal C}_{n}({\mathbb{F}})={\cal C}_{n}^{\prime}({\mathbb{F}})+{\cal C}_{n}^{\prime\prime}({\mathbb{F}})$, where ${\cal C}_{n}^{\prime}({\mathbb{F}})=\langle E,A_{n},A_{n}^{2},\dots,A_{n}^{n-1}\rangle$, ${\cal C}_{n}^{\prime\prime}({\mathbb{F}})=\langle B_{n},B_{n}A_{n},B_{n}A_{n}^{2},\dots,B_{n}A_{n}^{n-1}\rangle$. Note that ${\cal C}_{n}^{\prime}({\mathbb{F}})$ is nothing else but the space of circulants, and ${\cal C}_{n}^{\prime\prime}({\mathbb{F}})$ is the space of anti-circulants, each of which has a dimension of $n$.

The basis of the intersection of the spaces ${\cal C}_{n}^{\prime}({\mathbb{F}})$ and ${\cal C}_{n}^{\prime\prime}({\mathbb{F}})$ in the odd case is the matrix in which each element equals 1, and in the even case, the basis will be the following two matrices

Thus, the statement of the lemma follows from the formula for the dimension of the sum of subspaces. ∎

Let us first prove the lower bound $l({\cal C}_{n}({\mathbb{F}}))\geq n-1.$ Consider a generating set $\SS=\{u,v\}$, where $u=B_{n},v=A_{n}B_{n}$. This is indeed a generating set, as ${\cal C}_{n}({\mathbb{F}})={\cal L}(\{A_{n},B_{n}\})={\cal L}(\{vu,u\})\subseteq{\cal L}(\{u,v\})={\cal L}(\{B_{n},A_{n}B_{n}\})\subseteq{\cal L}(\{A_{n},B_{n}\})={\cal C}_{n}({\mathbb{F}})$. At the same time, $u^{2}=v^{2}=E$, meaning that there are no more than two irreducible words of each length (of the form $uvuv\dots$ and $vuvu\dots$). Thus, $\dim{\cal L}_{n-2}(\SS)=(\dim{\cal L}_{n-2}(\SS)-\dim{\cal L}_{n-3}(\SS))+(\dim{\cal L}_{n-3}(\SS)-\dim{\cal L}_{n-4}(\SS))+\cdots+(\dim{\cal L}_{1}(\SS)-\dim{\cal L}_{0}(\SS))+\dim{\cal L}_{0}(\SS)\leq 2(n-2)+1<\dim{\cal C}_{n}({\mathbb{F}})$, from which it follows that the length of the algebra is at least $n-1$.

The upper bound $l({\cal C}_{n}({\mathbb{F}}))\leq n-1$ follows from Theorem 3.5. Indeed, by the Cayley-Hamilton theorem, $m({\cal C}_{n}({\mathbb{F}}))\leq n$. By Lemma 4.3, $\dim{\cal C}_{n}({\mathbb{F}})\leq 2n-1$. Applying Theorem 3.5, we obtain the inequality $l({\cal C}_{n}({\mathbb{F}}))\leq max\{n-1,\frac{2n-1}{2}\}$. This completes the proof.

∎

Let $a$ be the rotation by an angle $\frac{2\pi}{n}$, $b$ be the symmetry about the axis passing through the vertex $\left[\dfrac{n}{2}\right]+1$. Then ${\mathbb{F}}{\cal D}_{n}=\langle e,a,a^{2},\dots,a^{n-1},b,ba,\dots,ba^{n-1}\rangle$.

It is easy to notice that $g\circ f(a)=A_{n}$, $g\circ f(b)=B_{n}$. Since $g\circ f$ is a homomorphism, $g\circ f(b^{i}a^{j})=B_{n}^{i}A_{n}^{j}$, from which the statement of the lemma follows. ∎

The dimension of the kernel is established using Lemmas 4.3 and 4.5. The fact that the specified elements lie in the kernel and are linearly independent (in the case of even $n$) is checked directly. ∎

Consider an arbitrary generating set $\SS=\{a_{1},\dots,a_{k}\}$ of the algebra ${\cal A}$.

Since the homomorphism $\varphi$ is surjective, we see that the set $\SS_{\mathcal{B}}=\{c_{1}=\varphi(a_{1}),\dots,c_{k}=\varphi(a_{k})\}$ is a generating set of the algebra $\mathcal{B}$. Therefore, $\dim{\cal L}_{l(\mathcal{B})}(\SS_{{\cal B}})=\dim{\cal B}$. On the other hand, ${\cal L}_{l({\cal B})}(\SS_{{\cal B}})={\cal L}_{l({\cal B})}(\varphi(\SS))=\varphi({\cal L}_{l({\cal B})}(\SS))$. Therefore, $\dim{\cal L}_{l({\cal B})}(\SS)\geq\dim\varphi({\cal L}_{l({\cal B})}(\SS))=\dim{\cal L}_{l({\cal B})}(\SS_{{\cal B}})=\dim{\cal B}$.

Since the dimensions ${\cal L}_{i}(\SS)$ must increase with $i$ until stabilization, we have $\dim{\cal L}_{l({\cal B})+\dim{\cal A}-\dim{\cal B}}(\SS)\geq\dim{\cal B}+(\dim{\cal A}-\dim{\cal B})=\dim{\cal A}$. At the same time, the minimal $i$ such that $\dim{\cal L}_{i}(\SS)=\dim{\cal A}$, by definition, is $l(\SS)$. Due to the arbitrariness of $\SS$, we obtain $l(\mathcal{A})\leq l(\mathcal{B})+\dim\mathcal{A}-\dim\cal B$.

∎

The lower bound is given by Lemma 4.7. Let us prove the upper bound.

From Theorem 4.4 it follows that $l({\cal C}_{n}({\mathbb{F}}))=n-1$. From Lemma 4.3 it follows that $\dim{\cal C}_{n}({\mathbb{F}})=2n-1$ for odd $n$, $\dim{\cal C}_{n}({\mathbb{F}})=2n-2$ for even $n$. Consider the homomorphism of algebras $g\circ f:{\mathbb{F}}\mathcal{D}_{n}\rightarrow{\cal C}_{n}({\mathbb{F}})$, described in Section 4.2. Since by Lemma 4.5 the homomorphism $g\circ f$ is surjective, we can apply Lemma 4.10 and get the upper bound $l({\mathbb{F}}\mathcal{D}_{n})\leq l({\cal C}_{n}({\mathbb{F}}))+\dim{\mathbb{F}}\mathcal{D}_{n}-\dim{\cal C}_{n}({\mathbb{F}})$. Then application of Theorem 4.4, Lemma 4.3 and the fact that $\dim{\mathbb{F}}\mathcal{D}_{n}=2n$ completes the proof.

∎

Let $\tau\in{\mathbb{F}}{\cal D}_{n}$, $g\circ f:{\mathbb{F}}\mathcal{D}_{n}\rightarrow{\cal C}_{n}({\mathbb{F}})$ be the homomorphism of algebras described in Section 4.2, $a$ be the rotation by an angle $\frac{2\pi}{n}$, $b$ be the symmetry.

Let $g\circ f(\tau)=T\in M_{n}({\mathbb{F}})$. Then by the Cayley-Hamilton theorem $m(T)=\deg\mu_{T}(x)\leq n$. Since $g\circ f(\mu_{T}(\tau))=\mu_{T}(T)=0$, we get $\mu_{T}(\tau)\in\ker g\circ f$. Next, consider two cases separately.

First case. Let $n$ be odd. Then from Lemma 4.6 it follows that $\ker g\circ f$ is one-dimensional. On the other hand, the kernel of a homomorphism of algebras is an ideal, which means $\mu_{T}(\tau)$ and $\mu_{T}(\tau)\tau$ are linearly dependent. Thus, $m({\mathbb{F}}{\cal D}_{n})\leq n+1$.

Second case. Let $n$ be even. Then from Lemma 4.6 it follows that $\ker g\circ f$ is two-dimensional. On the other hand, the kernel of a homomorphism of algebras is an ideal, which means $\mu_{T}(\tau)$, $\mu_{T}(\tau)\tau$, and $\mu_{T}(\tau)\tau^{2}$ are linearly dependent. Thus, $m({\mathbb{F}}{\cal D}_{n})\leq n+2$.

∎