Namespaces
Variants
Actions

Difference between revisions of "Hall polynomial"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
Line 1: Line 1:
Hall polynomials are Lie polynomials obtained from elements of a given Hall set (cf. [[Lie polynomial|Lie polynomial]]; [[Hall set|Hall set]]). They furnish a basis of the free Lie algebra (cf. [[Lie algebra, free|Lie algebra, free]]) over a (finite or infinite) set of generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100301.png" />. Elements of a Hall set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100302.png" /> may be seen as completely bracketed words (or rooted planar binary trees with leaves labelled by generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100303.png" />; cf. also [[Binary tree|Binary tree]]). These are defined recursively as brackets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100304.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100305.png" /> are bracketed words of lower weight; bracketed words of weight one correspond to the generators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100306.png" />. The Hall polynomial associated with the Hall element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100307.png" /> is then computed in the free associative ring (i.e. the ring of polynomials with non-commuting indeterminates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h1100308.png" />) following the rule:
+
Hall polynomials are Lie polynomials obtained from elements of a given Hall set (cf. [[Lie polynomial|Lie polynomial]]; [[Hall set|Hall set]]). They furnish a basis of the free Lie algebra (cf. [[Lie algebra, free|Lie algebra, free]]) over a (finite or infinite) set of generators $\{a_1,a_2,\ldots\}$. Elements of a Hall set $H$ may be seen as completely bracketed words (or rooted planar binary trees with leaves labelled by generators $a_1,a_2,\ldots$; cf. also [[Binary tree]]). These are defined recursively as brackets $t = [t',t'']$, where$t',t''$ are bracketed words of lower weight; bracketed words of weight one correspond to the generators $a_1,a_2,\ldots$. The Hall polynomial associated with the Hall element $t \in H$ is then computed in the free associative ring (i.e. the ring of polynomials with non-commuting indeterminates $\{a_1,a_2,\ldots\}$) following the rule:
 +
$$
 +
P_t = \begin{cases} t & \text{if}\, t = a_i \,\text{is a generator}\\ P_{t'}P_{t''} - P_{t''}P_{t'} &\text{if}\,t=[t',t'']\,\text{is a bracketed word of weight}\ge 2.\end{cases}
 +
$$
  
<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/h/h110/h110030/h1100309.png" /></td> </tr></table>
+
This basis of the free Lie algebra (cf. [[Lie algebra, free]]) is called the Hall basis (corresponding to the given Hall set). Sometimes this terminology is reserved for the basis arising from the basic commutator Hall set (or its left or right versions); cf. [[Hall set]; [[Basic commutator]].
  
This basis of the free Lie algebra (cf. [[Lie algebra, free|Lie algebra, free]]) is called the Hall basis (corresponding to the given Hall set). Sometimes this terminology is reserved for the basis arising from the basic commutator Hall set (or its left or right versions); cf. [[Hall set|Hall set]]; [[Basic commutator|Basic commutator]].
+
A Hall set $H$ is totally ordered, thus inducing a total order on the set of polynomials $\left\lbrace P_t : t \in H \right\rbrace$. One can show that any non-commutative polynomial is a sum of non-increasing products $P_{t_1}\cdots P_{t_n}$ of Hall polynomials. This result is the well-known Poincaré–Birkhoff–Witt theorem for free Lie algebras (cf. also [[Lie algebra, free]]). One can prove this result combinatorially by first showing that any non-commutative [[polynomial]] is a sum of non-increasing products $P_{t_1}\cdots P_{t_n}$ (with non-negative integer coefficients). This is accomplished using rewriting techniques (cf. [[#References|[a1]]]); this idea is originally present in [[#References|[a2]]]. A theorem stating that any word is a unique non-increasing product of Hall words then implies that these non-increasing products of Hall polynomials form a basis of the free associative algebra. It then follows that the set of Hall polynomials is linearly independent. In order to show that the set of Hall polynomials generate the free Lie algebra, one shows that the bracket $\left[ P_s,P_t \right] = P_s P_t - P_t P_s$ of any two Hall polynomials $P_s, P_t$ is a sum of Hall polynomials $P_u$ with $u = [u',u'']$ and $u'' < \sup(s,t)$. This result is known as the Schützenberger lemma. Consequently, the set $\left\lbrace P_t : t \in H \right\rbrace$ is a linear basis for the free Lie algebra over $\{a_1,a_2,\ldots\}$.
  
A Hall set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003010.png" /> is totally ordered, thus inducing a total order on the set of polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003011.png" />. One can show that any non-commutative polynomial is a sum of non-increasing products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003012.png" /> of Hall polynomials. This result is the well-known Poincaré–Birkhoff–Witt theorem for free Lie algebras (cf. also [[Lie algebra, free|Lie algebra, free]]). One can prove this result combinatorially by first showing that any non-commutative [[Polynomial|polynomial]] is a sum of non-increasing products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003013.png" /> (with non-negative integer coefficients). This is accomplished using rewriting techniques (cf. [[#References|[a1]]]); this idea is originally present in [[#References|[a2]]]. A theorem stating that any word is a unique non-increasing product of Hall words then implies that these non-increasing products of Hall polynomials form a basis of the free associative algebra. It then follows that the set of Hall polynomials is linearly independent. In order to show that the set of Hall polynomials generate the free Lie algebra, one shows that the bracket <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003014.png" /> of any two Hall polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003015.png" /> is a sum of Hall polynomials <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003016.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003018.png" />. This result is known as the Schützenberger lemma. Consequently, the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003019.png" /> is a linear basis for the free Lie algebra over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/h/h110/h110030/h11003020.png" />.
+
See also: [[Hall set]]; [[Hall word]]; [[Lie algebra, free]]; [[Lie polynomial]].
 
 
See also: [[Hall set|Hall set]]; [[Hall word|Hall word]]; [[Lie algebra, free|Lie algebra, free]]; [[Lie polynomial|Lie polynomial]].
 
  
 
There is a second notion of Hall polynomial, introduced by Philip Hall for studying the structure of finite modules over a commutative discrete valuation ring (cf. [[#References|[a3]]]), whereas the Hall polynomials as defined above are usually attributed to Marshall Hall.
 
There is a second notion of Hall polynomial, introduced by Philip Hall for studying the structure of finite modules over a commutative discrete valuation ring (cf. [[#References|[a3]]]), whereas the Hall polynomials as defined above are usually attributed to Marshall Hall.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Reutenauer,  "Free Lie algebras" , ''London Math. Soc. Monographs New Ser.'' , '''7''' , Oxford Univ. Press  (1993)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Hall,  "A basis for free Lie rings and higher commutators in free groups"  ''Proc. Amer. Math. Soc.'' , '''1'''  (1950)  pp. 57–581</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  I.G. MacDonald,  "Symmetric functions and Hall polynomials" , Clarendon Press  (1995)  (Edition: Second)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  C. Reutenauer,  "Free Lie algebras" , ''London Math. Soc. Monographs New Ser.'' , '''7''' , Oxford Univ. Press  (1993)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Hall,  "A basis for free Lie rings and higher commutators in free groups"  ''Proc. Amer. Math. Soc.'' , '''1'''  (1950)  pp. 57–581</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  I.G. MacDonald,  "Symmetric functions and Hall polynomials" , Clarendon Press  (1995)  (Edition: Second)</TD></TR>
 +
</table>
 +
 
 +
[[Category:TeX done]]

Revision as of 19:45, 5 December 2015

Hall polynomials are Lie polynomials obtained from elements of a given Hall set (cf. Lie polynomial; Hall set). They furnish a basis of the free Lie algebra (cf. Lie algebra, free) over a (finite or infinite) set of generators $\{a_1,a_2,\ldots\}$. Elements of a Hall set $H$ may be seen as completely bracketed words (or rooted planar binary trees with leaves labelled by generators $a_1,a_2,\ldots$; cf. also Binary tree). These are defined recursively as brackets $t = [t',t'']$, where$t',t''$ are bracketed words of lower weight; bracketed words of weight one correspond to the generators $a_1,a_2,\ldots$. The Hall polynomial associated with the Hall element $t \in H$ is then computed in the free associative ring (i.e. the ring of polynomials with non-commuting indeterminates $\{a_1,a_2,\ldots\}$) following the rule: $$ P_t = \begin{cases} t & \text{if}\, t = a_i \,\text{is a generator}\\ P_{t'}P_{t''} - P_{t''}P_{t'} &\text{if}\,t=[t',t'']\,\text{is a bracketed word of weight}\ge 2.\end{cases} $$

This basis of the free Lie algebra (cf. Lie algebra, free) is called the Hall basis (corresponding to the given Hall set). Sometimes this terminology is reserved for the basis arising from the basic commutator Hall set (or its left or right versions); cf. [[Hall set]; Basic commutator.

A Hall set $H$ is totally ordered, thus inducing a total order on the set of polynomials $\left\lbrace P_t : t \in H \right\rbrace$. One can show that any non-commutative polynomial is a sum of non-increasing products $P_{t_1}\cdots P_{t_n}$ of Hall polynomials. This result is the well-known Poincaré–Birkhoff–Witt theorem for free Lie algebras (cf. also Lie algebra, free). One can prove this result combinatorially by first showing that any non-commutative polynomial is a sum of non-increasing products $P_{t_1}\cdots P_{t_n}$ (with non-negative integer coefficients). This is accomplished using rewriting techniques (cf. [a1]); this idea is originally present in [a2]. A theorem stating that any word is a unique non-increasing product of Hall words then implies that these non-increasing products of Hall polynomials form a basis of the free associative algebra. It then follows that the set of Hall polynomials is linearly independent. In order to show that the set of Hall polynomials generate the free Lie algebra, one shows that the bracket $\left[ P_s,P_t \right] = P_s P_t - P_t P_s$ of any two Hall polynomials $P_s, P_t$ is a sum of Hall polynomials $P_u$ with $u = [u',u'']$ and $u'' < \sup(s,t)$. This result is known as the Schützenberger lemma. Consequently, the set $\left\lbrace P_t : t \in H \right\rbrace$ is a linear basis for the free Lie algebra over $\{a_1,a_2,\ldots\}$.

See also: Hall set; Hall word; Lie algebra, free; Lie polynomial.

There is a second notion of Hall polynomial, introduced by Philip Hall for studying the structure of finite modules over a commutative discrete valuation ring (cf. [a3]), whereas the Hall polynomials as defined above are usually attributed to Marshall Hall.

References

[a1] C. Reutenauer, "Free Lie algebras" , London Math. Soc. Monographs New Ser. , 7 , Oxford Univ. Press (1993)
[a2] M. Hall, "A basis for free Lie rings and higher commutators in free groups" Proc. Amer. Math. Soc. , 1 (1950) pp. 57–581
[a3] I.G. MacDonald, "Symmetric functions and Hall polynomials" , Clarendon Press (1995) (Edition: Second)
How to Cite This Entry:
Hall polynomial. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Hall_polynomial&oldid=13673
This article was adapted from an original article by G. Melançon (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article