Namespaces
Variants
Actions

Difference between revisions of "Shirshov basis"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
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''
 
''Š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 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101001.png" />, that is, elements chosen from a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101002.png" /> called an [[Alphabet|alphabet]]. A word is usually written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101003.png" />, or abbreviated by a single symbol: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101004.png" />. The length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101005.png" /> is equal to the number of letters in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101006.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101007.png" />. One may concatenate words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101008.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s1101009.png" /> and this operation is concisely written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010010.png" />. The set of all words over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010011.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010012.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010013.png" /> be a set totally ordered by a relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010014.png" /> (cf. [[Totally ordered set|Totally ordered set]]). Extend the order to all words by setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010016.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010018.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010019.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010020.png" /> be the set of words <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010021.png" /> strictly greater, with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010022.png" />, than any of their circular shifts <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010023.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010024.png" />). Shirshov's lemma [[#References|[a1]]] shows that any word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010025.png" /> is a non-decreasing product of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010026.png" />: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010027.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010029.png" />. As for Lyndon words (cf. [[Lyndon word|Lyndon word]]), words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010030.png" /> lead to a basis of the free Lie algebra (over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010031.png" />; cf. [[Lie algebra, free|Lie algebra, free]]). Indeed, only a bracketing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010032.png" /> of words in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010033.png" /> is needed. This is done inductively as follows. Set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010034.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010035.png" />. Otherwise, a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010036.png" /> may be written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010037.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010038.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010039.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010040.png" />. Then one defines
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010041.png" /></td> </tr></table>
+
$$
 +
\pi ( w ) = [ \pi ( f _ {1} ) , [ \pi ( f _ {2} ) , \dots [ \pi ( f _ {n} ) , a ] ] ] .
 +
$$
  
The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010042.png" /> is the Shirshov basis for the free Lie algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/s/s110/s110100/s11010043.png" />.
+
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]].
 
See also [[Hall word|Hall word]]; [[Hall set|Hall set]].

Revision as of 08:13, 6 June 2020


Š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)
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