Values of the length function for nonassociative algebras

Abstract

We study realizable values of the length function for unital possibly nonassociative algebras of a given dimension. To do this we apply the method of characteristic sequences and establish sufficient conditions of realizability for a given value of length. The proposed conditions are based on binary decompositions of the value and algebraic constructions that allow to modify length function of an algebra. Additionally we provide a description of unital algebras of maximal possible length in terms of their bases.

Keywords:

• Length function
• nonassociative algebra

2020 Mathematics Subject Classification:

• 15A03
• 17A99
• 15A78

1 Introduction

Let $\mathbb{F}$ be an arbitrary field. In this paper $\mathcal{A}$ denotes a finite dimensional unital not necessarily associative $\mathbb{F}$-algebra with the multiplication $(·)$ usually denoted by the concatenation. Let $\mathcal{S}=\{a_1,\dots ,a_k\}$ be a finite generating set of $\mathcal{A}$. Any product of a finite number of elements from $\mathcal{S}$ is a word in $\mathcal{S}$. The length of the word w, denoted l(w), equals to the number of letters in the corresponding product. We consider 1 as a word in $\mathcal{S}$ with the length 0.

The set of all words in $\mathcal{S}$ of lengths less than or equal to i is denoted by ${\mathcal{S}}^i$, here $i\ge 0$.

Note that similarly to the associative case, m < n implies that ${\mathcal{S}}^m\subseteq {\mathcal{S}}^n$.

The set ${\mathcal{L}}_i(\mathcal{S})=〈{\mathcal{S}}^i〉$ is the linear span of the set ${\mathcal{S}}^i$ (the set of all finite linear combinations with coefficients belonging to $\mathbb{F}$). We write ${\mathcal{L}}_i$ instead of ${\mathcal{L}}_i(\mathcal{S})$ if $\mathcal{S}$ is clear from the context. It should be noted that for unital algebras ${\mathcal{L}}_0(\mathcal{S})=〈1〉=\mathbb{F}$ for any $\mathcal{S}$, and for non-unital algebras ${\mathcal{L}}_0=\left\{0\right\}$. We denote $\mathcal{L}(\mathcal{S})={\cup }_{i=0}^{\infty }{\mathcal{L}}_i(\mathcal{S})$.

Since the set $\mathcal{S}$ is generating for $\mathcal{A}$, the equality $\mathcal{A}=\mathcal{L}(\mathcal{S})$ holds.

Definition 1.1.

The length of a generating set $\mathcal{S}$ of a finite-dimensional algebra $\mathcal{A}$ is defined as follows: $l(\mathcal{S})=\min \{k\in {\mathbb{Z}}_{+}:{\mathcal{L}}_k(\mathcal{S})=\mathcal{A}\}.$

Definition 1.2.

The length of an algebra $\mathcal{A}$ is $l(\mathcal{A})=\max \{l(\mathcal{S}):\mathcal{L}(\mathcal{S})=\mathcal{A}\}$.

The problem of the associative algebra length computation was first discussed in [19, 20] for the algebra of 3 × 3 matrices in the context of the mechanics of isotropic continua.

It is straightforward to see that the length of a unital associative algebra is strictly less than its dimension, and this bound is sharp. Namely, one-generated unital associative algebra of the dimension d has length d–1. The first nontrivial result in this direction is going back to Paz [18]. More results on the length of abstract associative algebras can be found, for example, in [13, 17] and their bibliography.

In general most of the known results on the length function are just bounds that are not sharp. Even the sharp upper bound for the length of the matrix algebra is not known, though such bounds are important in the number of applications, see [13] and references therein. In particular, the knowledge of the universal upper bound for the length provides the maximal size of products in generators that we need to consider to verify a certain property, for example, unitary similarity, [1]. Moreover, a great deal of work has been done investigating the related notion of length for given generating sets of matrices as in Definition 1.1, see [5, 9–11, 16] and references therein. Finally, the questions of determining realizable values of the length and describing algebras of maximal or minimal length were previously solved for certain important classes of matrix sets and algebras, see, e.g., [7, 8] for the realizability and [6, 12] for the description of commutative algebras of maximal length and general matrix algebras of minimal length.

The results on the lengths of nonassociative algebras were obtained in the works [2–4, 15]. The common tool to work without associativity is the method of characteristic sequences which are defined as follows.

Definition 1.3.

[4, Definition 3.1] Consider a unital finite-dimensional $\mathbb{F}$-algebra $\mathcal{A}$ and its generating set $\mathcal{S}$. By the characteristic sequence of $\mathcal{S}$ in $\mathcal{A}$ we understand a monotonically non-decreasing sequence of non-negative integers $(m_0,m_1,\dots ,m_N)$, constructed by the following rules:

1. $m_0=0$.

2. Denoting $s_1=\text{dim} {\mathcal{L}}_1(\mathcal{S})-1$, we define $m_1=\cdots =m_{s_1}=1$.

3. Let for some r > 0, k > 1 the elements $m_1,\dots ,m_r$ be already defined and the sets ${\mathcal{L}}_1(\mathcal{S}),\dots ,{\mathcal{L}}_{k-1}(\mathcal{S})$ are considered. Then we inductively continue the process in the following way. Denote $s_k=\text{dim} {\mathcal{L}}_k(\mathcal{S})-\text{dim} {\mathcal{L}}_{k-1}(\mathcal{S})$ and define $m_{r+1}=\cdots =m_{r+s_k}=k$.

Such sequences are directly connected to the dimension of algebra and the length of the respective generating set.

Lemma 1.4.

[4, Lemma 3.5] Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n>2$, and $\mathcal{S}$ be a generating set for $\mathcal{A}$. Then the characteristic sequence of $\mathcal{S}$ contains n terms, i.e., $N=n-1$. Moreover, $m_N=l(\mathcal{S})$.

Combinatorial properties of these sequences, in turn, allow us to establish various facts about lengths. In particular, using characteristic sequences it is possible to provide a strict upper bound on length of a general nonassociative unital algebra.

Theorem 1.5.

[4, Theorem 2.7] Let $\mathcal{A}$ be a unital $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n\ge 2$. Then $l(\mathcal{A})\le 2^{n-2}$.

The above bound is strict, see [4, Example 2.8].

The following questions, generalizing the previous investigations of associative case, appear naturally.

• What values of length between 1 and $2^{n-2}$ can be obtained as lengths of general nonassociative algebras of dimension n?

• How general are the algebras of arbitrary given length?

As it was shown in [2], the nonassociative situation is quite different and a gap in the set of values of length was discovered. In particular, already for the value $l=2^{n-2}-1$ there are no algebras of length l and dimension n for $n\ge 5$.

In the present paper we investigate the set of realizable values for the length function on nonassociative algebras. Our main purpose is to provide an answer to the first of the above questions. As another application of the proposed method we characterize all algebras of the maximal length in terms of their bases.

Instead of the previously known combinatorial criteria based on characteristic sequences, which was nontrivial to check, see [2, Theorem 3.19], we provide an efficient numerical sufficient condition for feasibility of length values. Our condition is stated in terms of the binary decomposition of an integer under consideration and is easy to check.

In particular, we show that for algebras of dimension 2, 3, 4 all values of length are realizable, and for any dimension $n\ge 5$ there are gaps of non-realizable values. If the value is bigger than a half of the maximal length value, then all the gaps are completely determined. Namely, we prove that only realizable values for $k>2^{n-3}$ are of the form $2^{n-3}+2^q$, and moreover, all integers of the type $2^h$ and $2^p+2^q$ with $h\le n-2,q\le p\le n-3$, are realizable. If $k>\lceil \frac{n}{2}\rceil$ then all values in the interval $[2^{n-k-1},2^{n-k}-1]$ are realizable. As a corollary a lower bound for the first non-realizable value is obtained. Namely, it is proved that all values between 1 and $2^{\lceil \frac{n}{2}\rceil }$ are realizable for $n\ge 6$. We also compute the total number of realizable values in each interval of the form $[2^{n-k-1},2^{n-k}-1]$.

Sufficient condition is provided for a given integer to be realizable as a value of length. Namely, if $l<2^{n-k}$ for some k such that the binary decomposition of l contains less than or equal to k entries 1, then l is realizable. An example is given that this condition is not necessary. A lower bound for the number of realizable values is obtained and several new gaps in the set of values of the length function are found.

Additionally, we expand upon connection of characteristic sequence to respective generating set. This is achieved by constructing a special basis $W=\{e_0,\dots ,e_{n-1}\}$ of words corresponding to the characteristic sequence $M=\{m_0,\dots ,m_{n-1}\}$ such that the multiplication low of the elements of W is defined by the addition in M. As an application of this technique we characterize nonassociative algebras of maximal length in terms of their bases.

Our paper is organized as follows. In Section 2 we provide previously established results and notions, relevant for further proofs. In Section 3 we introduce basic numerical results for possible length values examining proto-characteristic sequences. Section 4 covers the application of binary decomposition of a given value in checking its feasibility as a length of an algebra. Throughout Sections 2 and 5 we provide description for algebras of maximal length in terms of their bases.

2 Basic results and notions

To formulate our results let us start by introducing basic notions and tools in the nonassociative situation.

Definition 2.1.

[2, Definition 3.1] We call the sequence $M=(m_0,\dots ,m_{n-1})$ proto-characteristic if it satisfies the following properties:

1. $m_0=0$.

2. There exists $k_1,1\le k_1\le n-1,$ such that $m_1=\cdots =m_{k_1}=1$ and if $k_1<n-1$ it holds that $m_{k_1+1}>1$.

3. The sequence $(m_0,\dots ,m_{n-1})$ is non-decreasing.

4. If $k_1<n-1$ then there exist two functions, $t_1(k)$ and $t_2(k)$, mapping the set $\{k_1+1,\dots ,n-1\}$ to $\{1,\dots ,n-1\}$, and satisfying two additional properties:

   1. For k such that $k_1<k<n$ the equality $m_{t_1(k)}+m_{t_2(k)}=m_k$ and inequalities $t_1(k),t_2(k)<k$ hold.

   2. For all h₁, h₂ such that $k_1<h_1<h_2<n$ at least one of the following two inequalities holds: $t_1(h_1)<t_1(h_2)$ or $t_2(h_1)<t_2(h_2)$.

Proposition 2.2.

[2, Proposition 3.2] Characteristic sequence of any generating set of any finite-dimensional unital algebra is proto-characteristic.

Theorem 2.3.

[2, Theorem 3.19] Let $M=(m_0,\dots ,m_{n-1})$, where $n\ge 2$, be a proto-characteristic sequence. Then there exists a unital algebra $\mathcal{A}$ over a field $\mathbb{F}$ with a generating set $\mathcal{S}$, such that the following conditions hold:

1. $\text{dim} \mathcal{A}=n$.

2. Characteristic sequence of $\mathcal{S}$ coincides with $(m_0,\dots ,m_{n-1})$.

3. $l(\mathcal{A})=m_{n-1}$.

Definition 2.4.

A word w in generators from the set $\mathcal{S}$ of an algebra $\mathcal{A}$ is irreducible, if for each integer $m,0\le m<l(w),$ it holds that $w\notin {\mathcal{L}}_m(\mathcal{S})$.

Lemma 2.5.

[4, Lemma 2.14] An irreducible word of the length greater than 1 is a product of two irreducible words of non-zero lengths.

Lemma 2.6.

[4, Lemma 3.4]

Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\mathit{dim}\mathcal{A}=n>2$, and $\mathcal{S}$ be a generating set for $\mathcal{A}$. Then

1. Positive integer k appears in the characteristic sequence as many times as many there are linearly independent irreducible words of length k.

2. For any term m_h of the characteristic sequence of $\mathcal{S}$ there is an irreducible word in $\mathcal{S}$ of length m_h.

3. If there is an irreducible word in $\mathcal{S}$ of length k, then k is included into the characteristic sequence of $\mathcal{S}$.

Lemma 2.7.

[4, Lemma 2.11] If $\mathcal{A}$ is an algebra and ${\mathcal{S}}_0$ and ${\mathcal{S}}_1$ are its finite subsets such that ${\mathcal{L}}_1({\mathcal{S}}_0)={\mathcal{L}}_1({\mathcal{S}}_1)$, then ${\mathcal{L}}_k({\mathcal{S}}_0)={\mathcal{L}}_k({\mathcal{S}}_1)$ for every positive integer k.

Proposition 2.8.

[4, Proposition 3.7] Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n>2$. Assume that $\mathcal{S}$ is a generating set for $\mathcal{A}$ and $(m_0,m_1,\dots ,m_{n-1})$ is the characteristic sequence of $\mathcal{S}$. Then for each h satisfying $m_h\ge 2$ it holds that there are indices $0<t_1\le t_2<h$ such that $m_h=m_{t_1}+m_{t_2}$.

Proposition 2.9.

[4, Theorem 3.8] Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n$, n > 2. Let also $\mathcal{S}$ be a generating set for $\mathcal{A},(m_0,m_1,\dots ,m_{n-1})$ be the characteristic sequence of $\mathcal{S}$. Then for each positive integer $h\le n-1$ it holds that $m_h\le 2^{h-1}$.

3 General observations

As it was already mentioned in the introduction, the length of a unital associative algebra is strictly less than its dimension and the corresponding bound is sharp. Moreover, we note that there are unital associative algebras of a given dimension n and any length between 1 and $(n-1)$ as the following example shows.

Example 3.1.

Let us consider an arbitrary field $\mathbb{F}$ and an associative $\mathbb{F}$-algebra ${\mathcal{A}}_l$ with the basis {$e_0=1,e_1,\dots ,e_{n-1}$} where $l\le n-1$ and the multiplication determined by the following rule: $$e_p{e}_q=\{\begin{array}{cc}{e}_p,\hfill & q=0;\hfill \\ e_q,\hfill & p=0;\hfill \\ e_{p+q},\hfill & p\ge 1,q\ge 1,p+q\le l;\hfill \\ 0,\hfill & \text{otherwise}.\hfill \end{array}$$

It is straightforward to check that ${\mathcal{A}}_l$ is associative and $\text{dim} {\mathcal{A}}_l=n$.

Consider the generating set ${\mathcal{S}}_0=\{e_1,e_{l+1},e_{l+2},\dots ,e_{n-1}\}$ of ${\mathcal{A}}_l$. Since $e_l=e_1^l$ is an irreducible word of the length l, we have $l({\mathcal{A}}_l)\ge l({\mathcal{S}}_0)=l$.

It can also be easily seen that ${\mathcal{A}}_l$ is a local commutative algebra with Jacobson radical of nilpotency index l + 1, and a general upper bound for the length is known for local algebras, see [13, Corollary 3.32], which gives us $l({\mathcal{A}}_l)\le l$. This implies $l({\mathcal{A}}_l)=l$.

It is worth noting that generally for a given n and $l\le n-1$ the known associative algebras of dimension n and length l are local commutative algebras.

Below $\mathcal{A}$ is again nonassociative algebra and we discuss some general properties of the values of its length.

Proposition 3.2.

Let $\mathcal{A}$ be a unital algebra over a field $\mathbb{F}$ such that $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=l$. Then there exists a unital algebra $\mathcal{A}\prime$ such that $\text{dim} \mathcal{A}\prime =n+1$ and $l(\mathcal{A}\prime )=l$.

Proof.

Let $\mathcal{S}$ be a generating set of $\mathcal{A}$ with maximal length, $M=(m_0,\dots ,m_{n-1})$ be its characteristic sequence. By Lemma 1.4 we have $m_{n-1}=l$.

Note that by Proposition 2.2 the sequence M is proto-characteristic with certain functions t₁ and t₂.

Consider the sequence $M\prime =(m{\prime }_0,\dots ,m{\prime }_n)=(m_0,1,m_1\dots ,m_{n-1})$. It is also proto-characteristic: Properties 1–3 of the Definition 2.1 can be straightforwardly checked, and for Property 4 we can define functions $t{\prime }_1(k)$ and $t{\prime }_2(k)$ as $t_1(k)+1$ and $t_2(k)+1$. To do this we observe that for all j satisfying $m{\prime }_j>1$ it holds that $m{\prime }_j=m_{j-1}$.

By Theorem 2.3 there exists a unital algebra of dimension n + 1 and length $m{\prime }_n=m_{n-1}=l$. □

Proposition 3.3.

Let $\mathcal{A}$ be a unital algebra over a field $\mathbb{F}$ such that $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=l$. Then there exists a unital algebra $\mathcal{A}\prime$ such that $\text{dim} \mathcal{A}\prime =n+1$ and $l(\mathcal{A}\prime )=2l$.

Proof.

Let $\mathcal{S}$ be a generating set of $\mathcal{A}$ with maximal length, $M=(m_0,\dots ,m_{n-1})$ be its characteristic sequence. By Lemma 1.4 we have $m_{n-1}=l$.

Note that by Proposition 2.2 the sequence M is proto-characteristic with certain functions t₁ and t₂.

Consider the sequence $M\prime =(m{\prime }_0,\dots ,m{\prime }_n)=(m_0,m_1\dots ,m_{n-1},2m_{n-1})$. It is also proto-characteristic: Properties 1–3 of the Definition 2.1 can be straightforwardly seen, and for Property 4 we can define functions $t{\prime }_1(k)$ and $t{\prime }_2(k)$ to be equal to $t_1(k)$ and $t_2(k)$, respectively, for k < n and $t{\prime }_1(n)=t{\prime }_2(n)=n-1$.

By Theorem 2.3 there exists a unital algebra of dimension n + 1 and length $m{\prime }_n=2m_{n-1}=2l$. □

Proposition 3.4.

Let $\mathcal{A}$ be a unital algebra over a field $\mathbb{F}$ such that $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=l$. Then there exists a unital algebra $\mathcal{A}\prime$ such that $\text{dim} \mathcal{A}\prime =n+1$ and $l(\mathcal{A}\prime )=l+1$.

Proof.

Let $\mathcal{S}$ be generating set of $\mathcal{A}$ with maximal length, $M=(m_0,\dots ,m_{n-1})$ be its characteristic sequence. By Lemma 1.4 the equation $m_{n-1}=l$ holds.

Note that by Proposition 2.2 M satisfies Properties 1–4 of Definition 2.1 with certain functions t₁ and t₂.

Consider the sequence $M\prime =(m{\prime }_0,\dots ,m{\prime }_n)=(m_0,m_1\dots ,m_{n-1},m_{n-1}+1)$. It is also proto-characteristic: Properties 1–3 of the Definition 2.1 can be seen easily, and for Property 4 we can define the functions $t{\prime }_1(k)$ and $t{\prime }_2(k)$ to be equal $t_1(k)$ and $t_2(k)$, respectively, for k < n and $t{\prime }_1(n)=1,t{\prime }_2(n)=n-1$.

By Theorem 2.3 there exists a unital algebra of dimension n + 1 and length $m{\prime }_n=2m_{n-1}=l+1$. □

An example of the algebra of the maximal possible value of length for a given dimension is given in [4, Example 2.8]. For algebras of minimal possible value of length for a given dimension, namely algebras of length 1, the work [15] provides classification of such structures. In particular, the statements [15, Theorem 3.8, Theorem 4.6] allow us to infer the following.

Proposition 3.5.

There exists a unital $\mathbb{F}$-algebra of dimension $n\ge 2$ and length 1.

Observe that there are no gaps in feasible length values for small dimensions, namely $\text{dim} \mathcal{A}\in \{1,2,3,4\}$.

Proposition 3.6.

For algebras of dimension n = 2, 3, 4 each value of length between 1 and $2^{n-2}$ is attainable.

Proof.

1. Let n = 2. Then the statement is straightforward as $2^{n-2}=1$.

2. Let n = 3. Then the statement follows from Proposition 3.5 and [4, Example 2.8].

3. In the case n = 4 the values that require justification are only 2 and 3, since 1 can be attained by Proposition 3.5 and 4 can be attained by [4, Example 2.8]. As both $(0,1,1,2)$ and $(0,1,2,3)$ fall under Theorem 2.3. □

It is shown in [4] that for each $n\ge 5$ the gaps in the set of values of the length function do exist. To investigate their structure we need the following technical statements.

Proposition 3.7.

Let $n\ge 2,h\le n-2$ be integers. Then there exists a unital $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=2^h$.

Proof.

We will prove this statement using an induction on n.

The base. For n = 2 the only possible value of h is 0 and the statement holds by Proposition 3.5.

The step. Assume the statement holds for $n=N-1,N\ge 3$, and consider n = N.

The case h = 0 holds by Proposition 3.5. For the case $1\le h\le N-2$ by the induction hypothesis there exists an algebra of dimension N–1 and length $2^{h-1}$ as h–1 is nonnegative and $h-1\le N-3$. Thus by Proposition 3.3 there exists an algebra of dimension N and length $2·2^{h-1}=2^h$. □

Lemma 3.8.

Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n>4$. Assume $\mathcal{S}$ is a generating set for $\mathcal{A}$ and $(m_0,m_1,\dots ,m_{n-1})$ is the characteristic sequence of $\mathcal{S}$. Then for all h such that $2\le h\le n-2$ it holds that $m_{h+1}\le 2m_h$.

Proof.

If m_h = 1 this follows from the fact that $m_{h-1}\ge 1$ .

If $m_h\ge 2$, we have $m_h=m_i+m_j$ for some $i,j\le h-1$ by Proposition 2.8. Since the characteristic sequence is monotonically non-decreasing, we have $m_h=m_i+m_j\le m_{h-1}+m_{h-1}=2m_{h-1}$. □

Proposition 3.9.

Let $\mathcal{A}$ be a unital $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n$, n > 4, $\mathcal{S}$ be a generating set of $\mathcal{A},(m_0,m_1,\dots ,m_{n-1})$ be the characteristic sequence of $\mathcal{S}$. Then

1. For each positive integer $h\le n-1$ it holds that either $m_h=2^{h-1}$ or $m_h\le 3·2^{h-3}.$

2. Moreover, in the case $m_h=2^{h-1}$ it holds that $m_l=2^{l-1}$ for all $l\le h$.

Proof.

Note that $m_1=1$. If (3.1) $$m_k=2m_{k-1}$$(3.1) for all $2\le k\le h$, then $m_h=2^{h-1}$ and Item 2 is straightforward.

Otherwise consider the first k, $2\le k\le h$ such that $m_k\ne 2m_{k-1}$, i.e. by Lemma 3.8 $m_k<2m_{k-1}$.

1. If m_k = 1 by Lemma 3.8 it holds $m_h\le 2m_{h-1}\le \cdots \le 2^{h-k}{m}_k=2^{h-k}<3·2^{h-3}<2^{h-1}$.

2. If $m_k\ge 2$ we have $m_h=m_i+m_j$ for some $1\le i,j\le k-1$ by Proposition 2.8. Note that i, j cannot be equal to k–1 simultaneously due to the choice of k. Thus $m_k=m_i+m_j\le m_{k-1}+m_{k-2}=2^{k-2}+2^{k-3}=3·2^{k-3}.$

By Lemma 3.8 it holds $m_h\le 2m_{h-1}\le \cdots \le 2^{h-k}{m}_k\le 2^{h-k}(3·2^{k-3})=3·2^{h-3}<2^{h-1}$. □

4 Binary decomposition

4.1 Gap bounds

In this subsection we further investigate the set of realizable values of the length function. In particular, we use here a new method to determine whether a certain value is a feasible length of an algebra of dimension n. This method is based on the binary decomposition of n.

The theorem below generalizes the results of Proposition 3.7.

Theorem 4.1.

Let n > 4 be integer. Then for each $p\in \{0,\dots ,n-3\}$ there exists a unital $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=2^{n-3}+2^p$.

Proof.

Consider the sequence $$(0,1,2,\dots ,2^{n-3},2^{n-3}+2^p).$$

It is easy to see that it is proto-characteristic with functions $t_1(k)=t_2(k)=k-1$ for $k=2,\dots ,n-2$, and $t_1(n-1)=p+1,$ $t_2(n-1)=n-2$. Thus by Theorem 2.3 there exists an $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=2^{n-3}+2^p$. □

The converse statement is also true and provides a generalization for Proposition 3.9.

Theorem 4.2.

Let $\mathcal{A}$ be a unital $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n$, n > 4, $\mathcal{S}$ be a generating set for $\mathcal{A},(m_0,m_1,\dots ,m_{n-1})$ be the characteristic sequence of $\mathcal{S}$. Let $m_h>2^{h-2}$, where $h\in \{4,\dots ,n-1\}$. Then $m_h=2^{h-2}+2^q,q\in \{0,\dots ,h-2\}$.

Proof.

We will prove the theorem by induction on h.

The base. For h = 4 according to Proposition 3.9, the value $m_4=7$ is impossible. Thus by Proposition 2.9, if $m_h>2^{4-2}=4$, then $m_h\in \{5=2^2+2^0,6=2^2+2^1,8=2^2+2^2\}$.

The step. If the statement holds for $h=4,\dots ,H-1$, let us prove it for $h=H\ge 5$. Assume the contrary, i.e. that there exists $Q\in \{0,\dots ,H-3\}$ such that $2^{H-2}+2^Q<m_H<2^{H-2}+2^{Q+1}$, or, equivalently $m_H=2^{H-2}+x,2^Q<x<2^{Q+1}$. As $(m_0,\dots ,m_{n-1})$ is proto-characteristic by Proposition 2.2, we can consider respective functions t₁ and t₂. By Property 4a of Definition 2.1, $m_H=m_{t_1(H)}+m_{t_2(H)}$. Let $T=\max \{t_1(H),t_2(H)\}$ and $t=\min \{t_1(H),t_2(H)\}$, so $m_H=m_T+m_t$. Since $(m_0,\dots ,m_{n-1})$ is monotonically non-decreasing, $m_T\ge m_t$, thus $m_T\ge \frac{m_H}{2}>2^{H-3}$. For any $p\in \{0,\dots ,H-2\}$ by Proposition 2.9 the inequality $m_p\le 2^{p-1}\le 2^{H-3}$ is satisfied. Hence $T=H-1$. By assumption, $2^{H-3}+2^{Q-1}<\frac{m_H}{2}\le m_T$, thus by the induction hypothesis $m_T=m_{H-1}=2^{H-3}+2^{Q_1}$ for some $Q_1\in \{0,\dots ,H-3\}$. There are the following two possibilities.

1. $Q_1=H-3$. Then $m_{H-1}=2^{H-2}$. It follows that $m_k=2^{k-1}$ for $p=0,\dots ,H-2$. Since $t\in \{1,\dots ,H-1\},m_H=m_T+m_t=2^{H-2}+2^{t-1}$, which contradicts the assumption.

2. $Q_1<H-3$. Then $m_t=m_H-m_T=2^{H-3}-2^{Q_1}+x\ge 2^{H-4}+x$. By Proposition 2.9 for $p\in \{0,\dots ,H-3\}$ the inequality $m_p\le 2^{H-4}$ holds. Hence $t\in \{H-1,H-2\}$. If $t=H-1$, then $m_T=m_t=\frac{m_H}{2}=2^{H-3}+\frac{x}{2}$, which is impossible if x is odd. Then x is even. By our assumption $\frac{x}{2}\ne 2^q$ for any $q\in \{0,\dots ,H-3\}$, which contradicts the induction hypothesis for T. Therefore, $t=H-2$. Then by the induction hypothesis $m_t=m_{H-2}=2^{H-3}+2^{Q_2}$ for some $Q_2\in \{0,\dots ,H-4\}$. Thus, we have the equalities: $$2^{H-2}+x=m_H=m_T+m_t=2^{H-3}+2^{Q_1}+2^{H-4}+2^{Q_2},$$

or equivalently $$2^{H-4}+x=2^{Q_1}+2^{Q_2}.$$

Again, there are several possibilities.

2.1. $Q_1=H-4$. Then we have $x=2^{Q_2}$, which contradicts the assumption.

2.2. $Q_2=H-4$. Then we have $x=2^{Q_1}$, which contradicts the assumption.

2.3. $Q_1,Q_2<H-4$. Then $2^{Q_1}+2^{Q_2}\le 2·2^{H-5}=2^{H-4}<2^{H-4}+x$, thus the equality is impossible.

These contradictions conclude the proof. □

Observe that Theorem 4.1 can be generalized even further.

Proposition 4.3.

Let n and k be integers such that $n>k>1$. Assume that l is a positive integer such that the following two conditions are satisfied

1. $l<2^{n-k}$;

2. there are no more than k elements 1 in the binary decomposition of l.

Then there exists an algebra $\mathcal{A}$ of dimension n and length l.

Proof.

We will prove this statement using a double induction on n and k.

The base for n. If n = 3 then the only possible values of k and l are 2 and 1 respectively and the statement is straightforward.

The step for n. Assume the statement holds for $n=3,\dots ,N-1$ with N > 3 and consider n = N.

The base for k. If k = 2 then there are two possibilities:

1. $l=2^h$, where $0\le h\le N-3$. It is the statement of Proposition 3.7.

2. There exist positive integers h₁, h₂ such that $h_1<h_2<N-2$ and $l=2^{h_2}+2^{h_1}$. If $h_2=N-3$, then the statement follows directly from Theorem 4.1. If $h_2<N-3$, then by Theorem 4.1 there exists an algebra of length l and dimension $h_2+3$. It follows by Proposition 3.2 that there is an algebra of length l and dimension N.

The step for k. Assume that we have proven the statement for $k=2,\dots ,K-1$ where $2<K<N$. Consider l such that $l<2^{N-K}$ and there are no more than K 1s in its binary decomposition. If there are $k_1<K$ 1s, the statement follows from the induction hypothesis for k, since $l<2^{N-K}<2^{N-k_1}$. If there are exactly K 1s (it should be noted that it means that $K<N-1$ in this case, since if $K=N-1$, then l would be equal to 1), then we have two possibilities again.

1. l is odd. Note that l–1 has K–1 elements 1 and $l-1<l<2^{N-K}=2^{(N-1)-(K-1)}$. By the induction hypothesis for n there exists an algebra of dimension N–1 and length l–1. Thus, by Proposition 3.4 there exists an algebra $\mathcal{A}$ of dimension N and length l.

2. l is even. Note that $\frac{l}{2}$ has K elements 1 and $\frac{l}{2}<\frac{2^{N-K}}{2}=2^{(N-1)-K}$. By the induction hypothesis for n there exists an algebra of dimension N–1 and length $\frac{l}{2}$. Thus, by Proposition 3.3 there exists an algebra $\mathcal{A}$ of dimension N and length l. □

The following set of realizable values is also a consequence from Theorem 4.1.

Proposition 4.4.

Let n > 4 be integer. Then for each $p\in \{2,\dots ,n-3\}$ and $q\le p$ there exists a unital $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})=2^p+2^q$.

Proof.

By Theorem 4.1 there exists an algebra $\mathcal{A}$ of dimension p + 3 and length $2^p+2^q$. If $p+3<n$, we can apply Proposition 3.2 $n-p-3$ times and get an algebra of dimension n and the same length. □

Proposition 4.5.

Let n, k be integers satisfying $1<k<n$.

1. There are at least $1+(\begin{array}{c}n-k-1\\ 1\end{array})+\cdots +(\begin{array}{c}n-k-1\\ \min (k-1,n-k-1)\end{array})$ realizable length values of algebras of dimension n in the interval $[2^{n-k-1},2^{n-k}-1]$.

2. If $k>\lceil \frac{n}{2}\rceil$, then all values in the interval $[2^{n-k-1},2^{n-k}-1]$ are realizable.

3. If k = 2, then there are exactly $1+(\begin{array}{c}n-3\\ 1\end{array})=n-2$ realizable values.

Proof.

1. Since $2^{n-k}-1-2^{n-k-1}=2^{n-k-1}-1$, there are exactly $2^{n-k-1}$ values in the interval. By Proposition 4.3 for a given h such that $0\le h\le \min (k-1,n-k-1)$ all of the values below $2^{n-k}$ with h + 1 elements 1 in binary decomposition are feasible. The number of such values in the interval $[2^{n-k-1},2^{n-k}-1]$ is equal to $(\begin{array}{c}n-k-1\\ h\end{array})$ as we have n–k digits with the leading digit equal to 1 and we can place remaining h–1 elements 1 into other $n-k-1$ digits arbitrarily. Thus, by summing all binomial coefficients for all possible h we can infer that there are at least $1+(\begin{array}{c}n-k-1\\ 1\end{array})+\dots +(\begin{array}{c}n-k-1\\ \min (k-1,n-k-1)\end{array})$ realizable length values in the interval.

2. If $k>\lceil \frac{n}{2}\rceil$, then the binomial sum is equal to $2^{n-k-1}$ which means that all of the values in the interval are feasible.

3. If k = 2, then by Theorems 4.1 and 4.2 only $1+n-3=n-2$ values in the interval are feasible. □

Observe that the converse statement to Proposition 4.3, in the same sense as Theorem 4.2 is the “converse” to Theorem 4.1, is not true. In particular, there exist algebras of length x which has k 1s in its binary decomposition, but $x\ge 2^{n-k}$, and Proposition 4.5 provides only a lower bound on the number of feasible values in the specified intervals.

Example 4.6.

Consider the sequence $(0,1,2,3,5,10,20,23)$ with the functions $t_1(k)$ and $t_2(k)$ defined as follows:

Table

k	$t_1(k)$	$t_2(k)$
2	1	1
3	1	2
4	2	3
5	4	4
6	5	5
7	3	6

On the one hand, it is proto-characteristic, and by Theorem 2.3 there exists an algebra of dimension 8 and length 23. On the other hand, $23={10111}_2$. So, there are four elements 1 in the binary decomposition, however $23>16=2^{8-4}$.

We conclude this subsection by the list of all realizable values in the top half of the possible length values. They appear to be rather rare and more or less isolated. Namely, the corollary below demonstrates that all realizable values of length that are bigger than the half of the maximal value have the form $2^{n-3}+2^p$, where $1\le p\le n-3$. This implies that the all the intervals $[2^{n-3}+2^p+1,2^{n-3}+2^{p+1}-1],1\le p\le n-3$, are gaps in the set of values of the length function.

Corollary 4.7.

Let n > 4 be integer. Then for each unital $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n$ and $l(\mathcal{A})>2^{n-3}$ we have $l(\mathcal{A})=2^{n-3}+2^p$ for $p\in \{0,\dots ,n-3\}$ .

Proof.

Consider a generating set $\mathcal{S}$ of $\mathcal{A}$ such that $l(\mathcal{A})=l(\mathcal{S})$ and its characteristic sequence $(m_0,m_1,\dots ,m_{n-1})$. Since $m_{n-1}=l(\mathcal{A})>2^{n-3}$, by Theorem 4.2 we have $m_{n-1}=2^{n-3}+2^p,p\in \{0,\dots ,n-3\}$. □

4.2 Bounds for the subsequent values of the length function

Now we may investigate the upper bound for the sequence of consequent values of lengths for algebras of a given dimension, which is the same as the lower bound for the first non-feasible value.

Definition 4.8.

Let $n\ge 2$ be a natural number. By B(n) we understand the maximal integer l > 0 such that there exist algebras of dimension n and lengths $1,\dots ,l$.

Proposition 4.9.

We have $B(2)=1,B(3)=2,B(4)=4,B(5)=6$.

Proof.

The first three values follow from Proposition 3.6, since these are the maximal possible values of length for $n\in \{2,3,4\}$. For n = 5 note that 7 is not a feasible length value by Corollary 4.7 as $7=2^{5-3}+3\ne 2^{5-3}+2^p$. Also the values from 1 till 4 are feasible by Proposition 3.2 as they are feasible for n = 4. The value 5 is feasible by Proposition 3.4 as 4 is a feasible length value for dimension 4. The value 6 is feasible by Theorem 4.1 as $6=2^{5-3}+2^1$. □

Proposition 4.10.

Let $n\ge 2$ be integer. Then $B(n+2)\ge 2·B(n)+1$.

Proof.

By Propositions 3.3 and 3.4 there exist algebras of dimension n + 2 and lengths $2·1,\dots ,2·B(n+1)$ (the first proposition) and $2·1+1,2·2+1,\dots ,2·B(n)+1$ (both propositions combined). By Proposition 3.2, B(h) is monotonically non-decreasing, hence $B(n+1)\ge B(n)$ and algebras of dimension n + 2 with lengths $1,2,\dots ,2·B(n)+1$ exist, which means $B(n+2)\ge 2·B(n)+1$. □

Proposition 4.11.

Let $n\ge 2$ be integer. Then $B(n)\ge 2^{\lceil \frac{n}{2}\rceil }$ for $n\ge 6$.

Proof.

1. Let n be even, i.e. $n=2h$ for some integer $h\ge 3$. Then by Proposition 4.5, Item 2, every length value $l_0\in [1,\dots ,2^h-1]$ is attainable for algebras of dimension n, since l₀ can be placed into an interval $[2^{2h-k-1},2^{2h-k}-1]$ with $k\ge h$. Thus, $B(2h)\ge 2^h$.

2. Consider the case n is odd, i.e. $n=2h-1$ for some integer $h\ge 4$. By Proposition 4.5, Item 2, each integer value $l_0\in [1,2^h-1]$ is realizable as a length of an algebra of dimension n, since $l_0\in [2^{n-k-1},2^{n-k}-1]$ for some $k\ge h-1$. By Proposition 4.3 all integer values $l_1\in [2^{h-1},2^h-2]$ are also realizable since 1) $l_1<2^h=2^{2h-1-(h-1)}$ and 2) $l_2=2^h-1$ is the only integer with more than h–1 elements 1 in its binary decomposition satisfying $l_2<2^h$. To show that l₂ is a feasible length value we use the induction on h.

The base. For h = 4, $2^4-1=15$. Consider the sequence $(0,1,2,3,5,10,15)$ with t₁ and t₂ defined as follows:

Table

k	$t_1(k)$	$t_2(k)$
2	1	1
3	1	2
4	2	3
5	4	4
6	4	5

It is proto-characteristic, and by Theorem 2.3 there is an algebra of dimension 7 and length 15.

The step. Assume the statement holds for $h=H-1$ with H > 4. Then for h = H we need to prove that there exists an algebra of length $2^H-1$ and dimension $2H-1$. By the induction hypothesis, there exists an algebra $\mathcal{A}$ with $l(\mathcal{A})=2^{H-1}-1$ and $\text{dim} \mathcal{A}=2H-3$. Then by Proposition 3.3 there exists an algebra ${\mathcal{A}}_1$ such that $l({\mathcal{A}}_1)=(2^{H-1}-1)·2=2^H-2$ and $\text{dim} {\mathcal{A}}_1=2H-2$. Hence by Proposition 3.4 there exists an algebra ${\mathcal{A}}_2$ with $l({\mathcal{A}}_2)=2^H-2+1=2^H-1$ and $\text{dim} {\mathcal{A}}_2=2H-1$. This concludes the induction.

Finally, $2^h$ is a feasible value by Proposition 3.7. Thus, $B(2h-1)\ge 2^h$. □

5 Characteristic sequence and basis

In the next section we characterize the algebras of maximal length. To achieve this goal in the current section we construct a special basis $W=\{e_0,\dots ,e_{n-1}\}$ of an algebra $\mathcal{A}$ corresponding well to a characteristic sequence $M=(m_0,\dots ,m_{n-1})$ of a given generating set $\mathcal{S}$ of this algebra. We will approach this goal gradually.

Definition 5.1.

Consider an $\mathbb{F}$-algebra $\mathcal{A}$, its generating set $\mathcal{S}$ and a characteristic sequence $M=(m_0,\dots ,m_{n-1})$ of $\mathcal{S}$. Let k₁ be such an index that $m_1=\cdots =m_{k_1}=1$ and if $k_1<n-1$ it holds that $m_{k_1+1}>1$ and t₁, t₂ be the functions mapping $\{k_1+1,\dots ,n-1\}$ to $\{1,\dots ,n-1\}$, and satisfying the two following properties (i.e. Item 4 of Definition 2.1):

1. For k such that $k_1<k<n$ the equality $m_{t_1(k)}+m_{t_2(k)}=m_k$ and inequalities $t_1(k),t_2(k)<k$ hold.

2. For all h₁, h₂ such that $k_1<h_1<h_2<n$ at least one of the following two inequalities holds: $t_1(h_1)<t_1(h_2)$ or $t_2(h_1)<t_2(h_2)$.

We say that the basis $W=\{e_0,\dots ,e_{n-1}\}$ of $\mathcal{A}$ corresponds to the characteristic sequence M equipped with the functions t₁, t₂ if the following holds:

1. For each $i\in \{0,\dots ,n-1\}$ the element $e_i\in W$ is a word in $\mathcal{S}$ of length m_i.

2. For every k such that $k_1<k<n$ the equality $e_{t_1(k)}·e_{t_2(k)}=e_k$ is true in $\mathcal{A}$.

3. ${\mathcal{L}}_1(\mathcal{S})=〈e_0,\dots ,e_{k_1}〉$.

Remark 5.2.

For a characteristic sequence M at least one pair of such functions t₁, t₂ exists since M is proto-characteristic by Proposition 2.2, which means that Item 4 of Definition 2.1 applies to it.

Let us introduce an auxiliary definition.

Definition 5.3.

We say that the basis $W=\{e_0,\dots ,e_{n-1}\}$ of the $\mathbb{F}$-algebra $\mathcal{A}$ is graded by the generating set $\mathcal{S}$ of $\mathcal{A}$, or just $\mathcal{S}$-graded basis, if there exists a subset $\mathcal{S}\prime \subseteq \mathcal{S}$, which is also a generating set, and a sequence of sets $W_0\subseteq W_1\subseteq \cdots \subseteq W_{l(\mathcal{S})}=W$ such that:

1. $W_0=\left\{1\right\},W_1=\mathcal{S}\prime \cup \left\{1\right\}$.

2. W_k is a basis of ${\mathcal{L}}_k(\mathcal{S})$ for $k=1,\dots ,l(\mathcal{S})$

3. $W_k\setminus W_{k-1}$ consists of irreducible words of length k in $\mathcal{S}\prime$.

4. Each element of W_k, which is a word of length at least 2 in $\mathcal{S}\prime$, is a product of two non-unit elements from W_k.

Lemma 5.4.

Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n\ge 2,\mathcal{S}$ be a generating set of $\mathcal{A}$. Then there exists an $\mathcal{S}$-graded basis W of $\mathcal{A}$.

Proof.

Let $\mathcal{S}\prime =\{a_1,\dots ,a_p\}$ be a maximal subset of $\mathcal{S}$ which is linearly independent modulo $\mathbb{F}$ and define W₁ as $\mathcal{S}\prime \cup \left\{1\right\}$. It is linearly independent as $\mathcal{S}\prime$ is linearly independent modulo $\mathbb{F}$.

Note that ${\mathcal{L}}_1(\mathcal{S}\prime )$ by definition is equal to $〈W_1〉=〈\mathcal{S}\prime \cup \left\{1\right\}〉=〈\mathcal{S}\cup \left\{1\right\}〉={\mathcal{L}}_1(\mathcal{S})$. By Lemma 2.7 we have ${\mathcal{L}}_k(\mathcal{S})={\mathcal{L}}_k(\mathcal{S}\prime )$, which implies that $\mathcal{S}\prime$ is a generating set. Additionally, for the purposes of Item 2 it is enough to prove that W_k is a basis of ${\mathcal{L}}_k(\mathcal{S}\prime )$.

We construct the sequence of W_k satisfying Items 2-4 inductively.

The base for k = 1 is provided above. Indeed, W₁ is a basis of ${\mathcal{L}}_1(\mathcal{S}\prime )$ as it is linearly independent and spans ${\mathcal{L}}_1(\mathcal{S}\prime ),W_1\setminus W_0=\mathcal{S}\prime$ consists of irreducible words of length 1 in $\mathcal{S}\prime$ (as $\mathbb{F}\cap \mathcal{S}\prime =\varnothing$, words of length 1 cannot be reduced), and, since in W₁ there are no elements which are words of length at least 2 in $\mathcal{S}\prime$, Item 4 holds as well.

The step. Assume $W_1,\dots ,W_{K-1}$ are already constructed. Consider an irreducible word w of length $K\le l(\mathcal{S})$. Note that $w=w\prime ·w″$, where $w\prime$ has length j, $1\le j<K$, and $w″$ has length K–j, which is also less than K. As $w\prime \in {\mathcal{L}}_j(\mathcal{S}\prime )=〈W_j〉$ and $w″\in {\mathcal{L}}_{K-j}(\mathcal{S}\prime )=〈W_{K-j}〉$, we have $w\in 〈W_j·W_{K-j}〉$. From this it follows that all of the irreducible words of length K belong to $〈\underset{i=1,\dots ,K-1}{\cup }{W}_i{W}_{K-i}〉$. Thus we can expand $W_{K-1}$ with irreducible words belonging to $W_i{W}_{K-i}$ for some indices i to obtain the basis of ${\mathcal{L}}_K(\mathcal{S}\prime )$. We name the resulting set W_K, as it satisfies Items 2-4:

1. It is indeed a basis by construction.

2. Only irreducible words of length K in $\mathcal{S}\prime$ were added, as any word of length less than K belongs to $〈W_{K-1}〉$ already.

3. Each added element is a product of two elements from $W_{K-1}$, which, by construction, is a subset of W_K. □

Lemma 5.5.

Let $\mathcal{A}$ be an $\mathbb{F}$-algebra, $\text{dim} \mathcal{A}=n\ge 2,\mathcal{S}$ be a generating set of $\mathcal{A}$. Let $M=(m_0,\dots ,m_{n-1})$ be the characteristic sequence of $\mathcal{S}$ and W be an $\mathcal{S}$-graded basis of $\mathcal{A}$ with associated set $\mathcal{S}\prime \subseteq \mathcal{S}$ and sequence of sets $W_0\subseteq W_1\subseteq \cdots \subseteq W_{l(\mathcal{S})}=W$. Then there exists a numbering e_i, $i=0,\dots ,n-1$, of the elements from W such that

1. $e_0=1$

2. For all r such that $1\le r\le l(\mathcal{S})$ it holds that $W_r=\{e_0,\dots ,e_{s_1+\cdots +s_r}\}$, where $s_r=\text{dim} {\mathcal{L}}_r(\mathcal{S})-\text{dim} {\mathcal{L}}_{r-1}(\mathcal{S})$. Additionally, the length of e_j as a word in $\mathcal{S}\prime$ is equal to m_j for $j=0,\dots ,s_1+\cdots +s_r$.

3. Under this numbering for all r such that $1\le r\le l(\mathcal{S})$ there exist functions $t_1^{(r)}$ and $t_2^{(r)}$ from the set $\{s_1+1,\dots ,s_1+\cdots +s_r\}$ to $\{1,\dots ,s_1+\cdots +s_r\}$ for which the following two properties are satisfied.

4. For k such that $s_1<k\le s_1+\cdots +s_r$ we have $e_{t_1^{(r)}(k)}{e}_{t_2^{(r)}(k)}=e_k$.

5. For all h₁, h₂ such that $s_1<h_1<h_2\le s_1+\cdots +s_r$ at least one of the inequalities $t_1^{(r)}(h_1)<t_1^{(r)}(h_2)$ or $t_2^{(r)}(h_1)<t_2^{(r)}(h_2)$ is satisfied.

Proof.

We will construct this numbering and respective functions using induction on r.

The base. For r = 1 set $e_0=1$ and $e_1,\dots ,e_{s_1}$ to be elements of $\mathcal{S}\prime$ in an arbitrary order. This guarantees Item 1 and Items 2 and 3 for r = 1 with $t_1^{(1)}$ and $t_2^{(1)}$ having empty domain.

The step. Assume that Items 2 and 3 hold for $r=1,\dots ,R-1$, with $2\le R\le l(\mathcal{S})$. For r = R there are two possibilities.

1. If s_R = 0, then $$W_R=W_{R-1}=\{e_0,\dots ,e_{s_1+\cdots +s_{R-1}}\}=\{e_0,\dots ,e_{s_1+\cdots +s_{R-1}+s_R}\}.$$

The functions $t_1^{(R)}$ and $t_2^{(R)}$ can be defined as $t_1^{(R-1)}$ and $t_2^{(R-1)}$ with Item 3 holding by the induction hypothesis.

2. If $s_R>0$, then consider all the elements of W which are the words of length R in $\mathcal{S}\prime$ (note that all of them belong to W_R by Item 3 of Definition 5.3). Since by Item 4 of Definition 5.3 they are equal to products of two shorter, already numbered elements of W, we can establish a correspondence between them and pairs of indices: a word w of length R would correspond to (j₁, j₂), where $e_{j_1}{e}_{j_2}=w$. Since all the words in W are distinct, all the pairs in the resulting correspondence are also distinct.

By sorting these pairs in lexicographic order we can continue the numbering of elements of W. We name the one with the lexicographic minimal corresponding pair $e_{s_1+\cdots +s_{R-1}+1}$, the next $e_{s_1+\cdots +s_{R-1}+2}$ and continue in this way. Item 2 will hold for r = R as there are exactly s_R words of length R in W. Since $W_{R-1}$ is a basis of ${\mathcal{L}}_{R-1}(\mathcal{S})$, W_R is a basis of ${\mathcal{L}}_R(\mathcal{S})$ and $W_R\setminus W_{R-1}$ consists of irreducible words of length R. For Item 3 we define $t_1^{(R)}$ and $t_2^{(R)}$ as follows:

• For $k\in \{s_1+1,\dots ,s_1+\cdots +s_{R-1}\}$ we define $t_i^{(R)}(k)=t_i^{(R-1)}(k)$, i = 1, 2. This guarantees Item 3 a,b for all indices $k,h_1,h_2$ less than or equal to $s_1+\cdots +s_{R-1}$.

• For $k\in \{s_1+\cdots +s_{R-1}+1,\dots ,s_1+\cdots +s_{R-1}+s_R\}$ we define $t_i^{(R)}(k)$ using the aforementioned correspondence between elements of lengths R and pairs of indices, with $t_1^{(R)}(k)$ being the first and $t_2^{(R)}(k)$ being the second index respectively. Item 3a holds by construction.

Item 3b requires us to check that $t_1^{(R)}(h_1)\le t_1^{(R)}(h_2)$ or $t_2^{(R)}(h_1)\le t_2^{(R)}(h_2)$ for h₁, h₂ such that $s_1<h_1<h_2\le s_1+\cdots +s_R$ with $h_2\ge s_1+\cdots +s_{R-1}+1$ (as lower h₂ are covered by the induction hypothesis). The proof of this property splits into two cases:

1. If $h_1\le s_1+\cdots +s_{R-1}$, then $m_{h_1}<R=m_{h_2}$. By reducing $e_{h_1}=e_{t_1^{(R)}(h_1)}·e_{t_2^{(R)}(h_1)}$ and $e_{h_2}=e_{t_1^{(R)}(h_2)}·e_{t_2^{(R)}(h_2)}$ to an equation on lengths we get $m_{h_1}=m_{t_1^{(R)}(h_1)}+m_{t_2^{(R)}(h_1)}$ and $m_{h_2}=m_{t_1^{(R)}(h_2)}+m_{t_2^{(R)}(h_2)}$. Since $x_1+y_1<x_2+y_2$ means that $x_1<x_2$ or $y_1<y_2$, we can infer that $m_{t_1^{(R)}(h_1)}<m_{t_1^{(R)}(h_2)}$ or $m_{t_2^{(R)}(h_1)}<m_{t_2^{(R)}(h_2)}$. This provides the inequalities on indices due to M being non-decreasing.

2. If $h_1\ge s_1+\cdots +s_{R-1}+1$ the inequalities hold due to the lexicographic sorting of the elements corresponding to pairs.□

Proposition 5.6.

Consider an algebra $\mathcal{A}$ of dimension $n\ge 2$ over a field $\mathbb{F}$ and its generating set $\mathcal{S}$ such that $l(\mathcal{S})\ge 2$. Let $M=(m_0,\dots ,m_{n-1})$ be the characteristic sequence of $\mathcal{S}$. There exists a basis $\{e_0,\dots ,e_{n-1}\}$ of the algebra $\mathcal{A}$ and functions t₁, t₂ from the set $\{k_1+1,\dots ,n-1\}$ to $\{1,\dots ,n-1\}$, here $k_1$ is defined by $m_{k_1}=1,m_{k_1+1}>1$, which satisfy the following properties:

1. for all $i\in \{0,\dots ,n-1\}$ the element e_i is a word in $\mathcal{S}$ of length m_i.

2. For t₁ and t₂ it holds that

3. For k such that $k_1<k<n$ the equality $m_{t_1(k)}+m_{t_2(k)}=m_k$ and inequalities $t_1(k),t_2(k)<k$ hold.

4. For all h₁, h₂ such that $k_1<h_1<h_2<n$ at least one of the following two inequalities holds: $t_1(h_1)<t_1(h_2)$ or $t_2(h_1)<t_2(h_2)$.

5. For any k, $k_1<k<n$, it holds that $e_{t_1(k)}{e}_{t_2(k)}=e_k$.

6. ${\mathcal{L}}_1(\mathcal{S})=〈e_0,\dots ,e_{k_1}〉$.

Particularly, this means that $\{e_0,\dots ,e_{n-1}\}$ corresponds to the characteristic sequence M equipped with the functions t₁, t₂.

Proof.

Consider an $\mathcal{S}$-graded basis W, constructed in Lemma 5.4 and numbered in Lemma 5.5 with $t_1=t_1^{(l(\mathcal{S}))}$ and $t_2=t_2^{(l(\mathcal{S}))}$ provided by Lemma 5.5. We will demonstrate that it satisfies Items 1–4.

• W₁, which is a basis of ${\mathcal{L}}_1(\mathcal{S})$, coincides with $\{e_0,\dots ,e_{s_1}\}$. As $e_0=1$ and s₁ = k₁, this implies Item 4 and Item 1 for $i=0,\dots ,s_1$.

• For any $j\in \{s_1+1,\dots ,n-1\}$ there exists R such that $s_1+\cdots +s_{R-1}<j\le s_1+\cdots +s_R$. We have m_j = R and by Item 2 of Lemma 5.5 e_j has length m_j, which demonstrates the desired property 1 for all remaining j.

• Items 2 and 3 of Lemma 5.5 for $r=l(\mathcal{S})$ guarantee Items 2 and 3 of the proposition.□

6 Algebras of maximal length

With the results of the previous section we are ready to characterize algebras of maximal length for a given dimension using their basis.

Proposition 6.1.

Consider a unital algebra $\mathcal{A}$ over a field $\mathbb{F}$ of dimension n > 2 and maximal possible length. There exists a generating set $\mathcal{S}$ of $\mathcal{A}$ such that its characteristic sequence is $(0,1,2,4,\dots ,2^{n-2})$.

Proof.

By Theorem 1.5 the maximal possible length of a unital algebra with dimension n is $2^{n-2}$. Consider a generating set $\mathcal{S}$ of such an algebra which has exactly this length. The last element of its characteristic sequence $M=(m_0,\dots ,m_{n-1})$ is equal to $l(\mathcal{S})=2^{n-2}$. By Proposition 3.9 Item 2 this means that all previous m_h for h > 0 are equal to $2^{h-1}$. Finally, m₀ is always equal to zero. □

Definition 6.2.

A basis $\{e_0,e_1,\dots ,e_{n-1}\}$ of an algebra $\mathcal{A}$ is called long, if $e_0=1$ and $e_i^2=e_{i+1}$ for $i=1,\dots ,n-2$.

Proposition 6.3.

A unital $\mathbb{F}$-algebra $\mathcal{A}$ of dimension n > 2 which has a long basis $E=\{e_0,e_1,\dots ,e_{n-1}\}$ such that $e_p{e}_q\in 〈e_0,\dots ,e_{\max (p,q)}〉$ for $p\ne q$ also has length $l(\mathcal{A})=2^{n-2}$.

Proof.

Consider the generating set $\left\{e_1\right\}$ of $\mathcal{A}$.

We demonstrate using induction on j that for each $j\in \{1,\dots ,n-1\}$ the following two statements hold:

• There are no irreducible words in $\left\{e_1\right\}$ of lengths $2^{j-2}+1,\dots ,2^{j-1}-1$ for j > 2;

• For the generating set $\left\{e_1\right\}$ there exists a single irreducible word w_j of length $2^{j-1}$, which is equal to e_j as an element of $\mathcal{A}$ and to $w_{j-1}^2$ as a word, with w₁ being e₁.

The base. For j = 1 the statement holds as w₁ = e₁ is an irreducible word of length 1 in $\left\{e_1\right\}$ with no other possible words of length 1. For j = 2 the statement holds as $w_2=w_1^2=e_1^2=e_2$ is an irreducible word of length 2 in $\left\{e_1\right\}$ with no other possible words of length 2 and the set $\{2^{j-2}+1,\dots ,2^{j-1}-1\}$ is empty for j = 2.

The step. Assume the statement holds for $j=1,\dots ,J-1$ with $3\le J\le n-1$.

Assume that v is an irreducible word of length $l\in \{2^{J-2}+1,\dots ,2^{J-1}\}$. Since $J\ge 3,l\ge 2$. This means that $v=v\prime ·v″$, where $v\prime$ and $v″$ are irreducible words of lesser positive lengths, $l\prime$ and $l″$. As $l\prime +l″=l$, the larger one of them is greater than or equal to $l/2$.

1. $l\prime \ge l″$. Since $l/2\le l\prime <l$, this means that $l\prime$ belongs to $\{2^{J-3}+1,\dots ,2^{J-2}\}$. Since $v\prime$ is irreducible, by the induction hypothesis this means that $v\prime =w_{J-1}=e_{J-1}$ and $l\prime =2^{J-2}$.

1.1. If $l″<2^{J-2}$, then by the induction hypothesis $v″$ must be equal to w_r with $r\in \{1,\dots ,J-2\}$. However, this would mean $v=w_{J-1}{w}_r=e_{J-1}{e}_r\in 〈e_1,\dots ,e_{J-1}〉={\mathcal{L}}_{2^{J-2}}(\{e_1\})$, with $l>2^{J-2}$. This contradicts the irreducibility of v. Thus, there are no irreducible words of lengths between $2^{J-2}+1$ and $2^{J-1}-1$. From this follows ${\mathcal{L}}_{2^{J-1}-1}(\{e_1\})={\mathcal{L}}_{2^{J-2}}(\{e_1\})$.

1.2. If $l″=2^{J-2}$, then $v″=w_{J-1}$ as well and $v=w_{J-1}^2=:w_J$. This word is indeed irreducible as $w_J=e_J\notin {\mathcal{L}}_{2^{J-1}-1}(\{e_1\})={\mathcal{L}}_{2^{J-2}}(\{e_1\})=〈e_0,\dots ,e_{J-1}〉$.

2. A similar argument works in the case $l″\ge l\prime$.

From this statement for $j=n-1$ it follows that there exists an irreducible word in $\left\{e_1\right\}$ of length $2^{n-2}$, which means $2^{n-2}\le l(\{e_1\})\le l(\mathcal{A})$. However, by Theorem 1.5, $l(\mathcal{A})\le 2^{n-2}$, which allows us to conclude that $l(\mathcal{A})=2^{n-2}$. □

Proposition 6.4.

A unital $\mathbb{F}$-algebra $\mathcal{A}$ of dimension n > 2 which has maximal length $2^{n-2}$ also has a long basis $E=\{e_0,e_1,\dots ,e_{n-1}\}$ such that $e_p{e}_q\in 〈e_0,\dots ,e_{\max (p,q)}〉$ for $p\ne q$.

Proof.

Consider a generating set $\overline{\mathcal{S}}$ of $\mathcal{A}$ such that $l(\overline{\mathcal{S}})=l(\mathcal{A})$. By Proposition 6.1, its characteristic sequence is $(0,1,2,4,\dots ,2^{n-2})$. Since there is only one element in the characteristic sequence equal to 1, we have $\text{dim} {\mathcal{L}}_1(\overline{\mathcal{S}})-\text{dim} {\mathcal{L}}_0(\overline{\mathcal{S}})=1$. This means that we can find a subset $\mathcal{S}\subset \overline{\mathcal{S}}$ such that $\left|\mathcal{S}\right|=1$ and $〈\mathcal{S}\cup \left\{1\right\}〉=〈\overline{\mathcal{S}}\cup \left\{1\right\}〉$. By Lemma 2.7 $\mathcal{S}$ is also a generating set of $\mathcal{A}$ of the same length and with the same characteristic sequence, since ${\mathcal{L}}_k(\mathcal{S})={\mathcal{L}}_k(\overline{\mathcal{S}})$ for all natural k.

Note that there is only one way for $(m_0,\dots ,m_{n-1})=(0,\dots ,2^{n-2})$ to define functions t₁, t₂ from the set $\{2,\dots ,n-1\}$ to $\{1,\dots ,n-1\}$ so they would satisfy

1. For k such that $1<k<n$ the equality $m_{t_1(k)}+m_{t_2(k)}=m_k$ and inequalities $t_1(k),t_2(k)<k$ hold.

2. For all h₁, h₂ such that $1<h_1<h_2<n$ at least one of the following two inequalities holds: $t_1(h_1)<t_1(h_2)$ or $t_2(h_1)<t_2(h_2)$.

Namely, we must set $t_1(h)=t_2(h)=h-1$, as otherwise $m_{t_1(h)}+m_{t_2(h)}=2^{t_1(h)-1}+2^{t_2(h)-1}$ is strictly less than $m_h=2^{h-1}$.

This means that by Proposition 5.6 applied to the generating set $\mathcal{S}$ there is a basis $\{e_0,\dots ,e_{n-1}\}$ such that $e_0=1,\mathcal{S}=\left\{e_1\right\}$ (as e₁ is a word of length 1 in singleton $\mathcal{S}$), e_i is a word of length $m_i=2^{i-1}$ for $i=1,\dots ,n-1$ in $\mathcal{S}$ and $e_j^2=e_{j+1}$ for $j=1,\dots ,n-2$ as $t_1(j+1)=t_2(j+1)=j$. In particular, this basis is long.

Additionally, e_i is an irreducible word. For i = 0, 1 this is evident. To prove this for $i\ge 2$, note that the dimension of ${\mathcal{L}}_{2^{i-2}}(\mathcal{S})$ is equal to the number of elements of the characteristic sequence less than or equal to $2^{i-2}$, i.e. i, which means that i linearly independent words $e_0,\dots ,e_{i-1}$ which belong to ${\mathcal{L}}_{2^{i-2}}(\mathcal{S})$ form its basis. Also by Lemma 2.6 there are no irreducible words of lengths $2^{i-2}+1,\dots ,2^{i-1}-1$ as there are no such elements in the characteristic sequence of $\mathcal{S}$. This allows us to conclude that ${\mathcal{L}}_{2^{i-2}}(\mathcal{S})={\mathcal{L}}_{2^{i-1}-1}(\mathcal{S})=〈e_0,\dots ,e_{i-1}〉$, from which follows $e_i\notin {\mathcal{L}}_{2^{i-1}-1}(\mathcal{S})$.

To demonstrate that $e_p{e}_q\in 〈e_0,\dots ,e_{\max (p,q)}〉$ for $p\ne q$, assume the opposite. Let there be p, q with $p\ne q$ such that $e_p{e}_q=f_r{e}_r+\cdots +f_0{e}_0$, where $f_r\ne 0$ and $r>\max (p,q)$. The word e_r of length $2^{r-1}$ is irreducible. However we can represent $e_r=c{e}_p{e}_q+s$, where $c=\frac{1}{f_r}$ and $s\in 〈e_0,\dots ,e_{r-1}〉$. This implies that $e_r\in {\mathcal{L}}_{\max (2^{r-2},2^{p-1}+2^{q-1})}(\{e_1\})$. Since $2^{r-2}<2^{r-1}$ and $2^{p-1}+2^{q-1}<2^{r-1}$, the word e_r is reducible. This is a contradiction, which means that the initial assumption is incorrect. □

The following is immediate from the two propositions above.

Theorem 6.5.

A unital $\mathbb{F}$-algebra $\mathcal{A}$ of dimension n > 2 has maximal length $2^{n-2}$ if and only if it has a long basis $E=\{e_0,e_1,\dots ,e_{n-1}\}$ such that $e_p{e}_q\in 〈e_0,\dots ,e_{\max (p,q)}〉$ for $p\ne q$.

Corollary 6.6.

For every unital $\mathbb{F}$-algebra $\mathcal{A}$ with $\text{dim} \mathcal{A}=n>2$ and $l(\mathcal{A})=2^{n-2}$ there exist elements $f_{p,q}^{(j)}$ and $f^{(0)},\dots ,f^{(n-1)}$ in $\mathbb{F},p,q\in \{1,\dots ,n-1\},$ $p\ne q,j=0,\dots ,\max (p,q)$ such that $\mathcal{A}$ is isomorphic to an algebra defined by generators $x_0,\dots ,x_{n-1}$ and relations $$\begin{array}{c}{x}_0=1,x_i^2=x_{i+1},i=1,\dots ,n-2,\\ x_p{x}_q=\sum _{j=0}^{\max (p,q)}{f}_{p,q}^{(j)}{x}_j,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{x}_{n-1}^2=\sum _{i=0}^{n-1}{f}^{(i)}{x}_i.\end{array}$$

Proof.

By the theorem above, $\mathcal{A}$ has a long basis $E=\{e_0,e_1,\dots ,e_{n-1}\}$ such that $e_p{e}_q\in 〈e_0,\dots ,e_{\max (p,q)}〉$ for $p\ne q$. Using this basis as well as the fact that $e_{n-1}^2\in \mathcal{A}$ we can find the elements $f_{p,q}^{(j)}$ and $f^{(0)},\dots ,f^{(n-1)}\in \mathbb{F}$ such that $$e_p{e}_q=\sum _{j=0}^{\max (p,q)}{f}_{p,q}^{(j)}{e}_j,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{e}_{n-1}^2=\sum _{i=0}^{n-1}{f}^{(i)}{e}_i.$$

This allows to construct the desired isomorphism simply by mapping e_i onto x_i. □

A possible further avenue of investigation is to attempt to find an algorithm checking whether the given algebra has maximal length. A related algorithmic question for lengths of matrix algebras has been recently investigated in [14].

Acknowledgments

The authors are very grateful to the referee for the helpful comments.