# 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$.

#### References

 [a1] A.I. Shirshov, "On bases for free Lie algebras" Algebra i Logika Sém. , 1 (1962) pp. 14–19 (In Russian) [a2] X. Viennot, "Algèbres de Lie libres et monoïdes libres" , Lecture Notes in Mathematics , 691 , Springer (1978)
How to Cite This Entry:
Shirshov basis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shirshov_basis&oldid=48686
This article was adapted from an original article by G. MelanÃ§on (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article