Namespaces
Variants
Actions

Difference between revisions of "Shirshov basis"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
 
Line 69: Line 69:
  
 
====References====
 
====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>
+
<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) {{ZBL|0395.17003}}</TD></TR>
 +
</table>

Latest revision as of 18:39, 5 October 2023


Š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) Zbl 0395.17003
How to Cite This Entry:
Shirshov basis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Shirshov_basis&oldid=54070
This article was adapted from an original article by G. Melançon (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article