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

See also Hall word; Hall set.

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)