View source for Shirshov basis

<!--
s1101001.png
$#A+1 = 43 n = 0
$#C+1 = 43 : ~/encyclopedia/old_files/data/S110/S.1100100 Shirshov basis,
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

''Širšov basis''

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

A [[Word|word]] is a sequence of letters  $  ( a _ {1} \dots a _ {n} ) $, 
that is, elements chosen from a set  $  A $
called an [[Alphabet|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 [[#References|[a2]]], is as follows. Let  $  A $
be a set totally ordered by a relation  $  \leq  $(
cf. [[Totally ordered set|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 [[#References|[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|Lyndon word]]), words in  $  F  ^  \prime  $
lead to a basis of the free Lie algebra (over  $  A $; 
cf. [[Lie algebra, free|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 $.

See also [[Hall word|Hall word]]; [[Hall set|Hall set]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A.I. Shirshov,   "On bases for free Lie algebras"  ''Algebra i Logika Sém.'' , '''1'''  (1962)  pp. 14–19  (In Russian)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  X. Viennot,   "Algèbres de Lie libres et monoïdes libres" , ''Lecture Notes in Mathematics'' , '''691''' , Springer  (1978)</TD></TR></table>