# Shirshov basis

Širšov basis

A particular basis for free Lie algebras introduced in [a1]. It is identical, up to symmetries, to the Lyndon basis (cf Lyndon word; Lie algebra, free).

A word is a sequence of letters $( a _ {1} \dots a _ {n} )$, that is, elements chosen from a set $A$ called an alphabet. A word is usually written as $a _ {1} \dots a _ {n}$, or abbreviated by a single symbol: $u = a _ {1} \dots a _ {n}$. The length of $w$ is equal to the number of letters in $w$, i.e. $n$. One may concatenate words $u = a _ {1} \dots a _ {n}$, $v = b _ {1} \dots b _ {m}$ and this operation is concisely written as $u v = a _ {1} \dots a _ {n} b _ {1} \dots b _ {m}$. The set of all words over $A$ is denoted by $A ^ {*}$.

Shirshov's original description, as given in [a2], is as follows. Let $A$ be a set totally ordered by a relation $\leq$( cf. Totally ordered set). Extend the order to all words by setting $uxv < uyw$ and $u > uv$ for all $u, v, w \in A ^ {*}$ and $x, y \in A$ such that $x < y$.

Let $F ^ \prime$ be the set of words $w = a _ {1} \dots a _ {n}$ strictly greater, with respect to $\leq$, than any of their circular shifts $a _ {i + 1 } \dots a _ {n} a _ {1} \dots a _ {i}$( $i = 1 \dots n - 1$). Shirshov's lemma [a1] shows that any word $w$ is a non-decreasing product of words in $F ^ \prime$: $w = f _ {1} \dots f _ {n}$ with $f _ {1} \dots f _ {n} \in F ^ \prime$ and $f _ {1} \leq \dots \leq f _ {n}$. As for Lyndon words (cf. Lyndon word), words in $F ^ \prime$ lead to a basis of the free Lie algebra (over $A$; cf. Lie algebra, free). Indeed, only a bracketing $\pi$ of words in $F ^ \prime$ is needed. This is done inductively as follows. Set $\pi ( a ) = a$ for $a \in A$. Otherwise, a $w \in F ^ \prime \setminus A$ may be written as $w = f _ {1} \dots f _ {n} a$ with $a \in A$, $f _ {1} \dots f _ {n} \in F ^ \prime$ and $f _ {1} \leq \dots \leq f _ {n}$. Then one defines

$$\pi ( w ) = [ \pi ( f _ {1} ) , [ \pi ( f _ {2} ) , \dots [ \pi ( f _ {n} ) , a ] ] ] .$$

The set $\{ {\pi ( f ) } : {f \in F ^ \prime } \}$ is the Shirshov basis for the free Lie algebra over $A$.