View source for Hall polynomial

Hall polynomials are [[Lie polynomial]]s obtained from elements of a given [[Hall set]].  They furnish a basis of the [[Lie algebra, free|free Lie algebra]] 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 tree|rooted]] planar [[binary tree]]s with leaves labelled by generators $a_1,a_2,\ldots$.  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 algebra]] (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 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).

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. 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. {{Cite|a1}}); this idea is originally present in {{Cite|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. {{Cite|a3}}), whereas the Hall polynomials as defined above are usually attributed to Marshall Hall.

====References====
* {{Ref|a1}} C. Reutenauer, "Free Lie algebras", ''London Math. Soc. Monographs New Ser.'', '''7''', Oxford Univ. Press  (1993) {{ISBN|0-19-853679-8}} {{ZBL|0798.17001}}
* {{Ref|a2}} M. Hall, "A basis for free Lie rings and higher commutators in free groups", ''Proc. Amer. Math. Soc.'', '''1'''  (1950)  pp. 57–581 {{DOI|10.2307/2032282}} {{ZBL|0039.26302}}
* {{Ref|a3}} I.G. MacDonald, "Symmetric functions and Hall polynomials", 2nd edition, Clarendon Press  (1995) {{ISBN|0-19-853489-2}} {{ZBL|0824.05059}}

[[Category:TeX done]]