Hall polynomial

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) ISBN 0-19-853679-8 Zbl 0798.17001
[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
[a3]	I.G. MacDonald, "Symmetric functions and Hall polynomials" , 2nd edition, Clarendon Press (1995) ISBN 0-19-853489-2 Zbl 0824.05059