Hall Polynomials¶

sage.combinat.hall_polynomial.
hall_polynomial
(nu, mu, la, q=None)¶ Return the (classical) Hall polynomial \(P^{\nu}_{\mu,\lambda}\) (where \(\nu\), \(\mu\) and \(\lambda\) are the inputs
nu
,mu
andla
).Let \(\nu,\mu,\lambda\) be partitions. The Hall polynomial \(P^{\nu}_{\mu,\lambda}(q)\) (in the indeterminate \(q\)) is defined as follows: Specialize \(q\) to a prime power, and consider the category of \(\GF{q}\)vector spaces with a distinguished nilpotent endomorphism. The morphisms in this category shall be the linear maps commuting with the distinguished endomorphisms. The type of an object in the category will be the Jordan type of the distinguished endomorphism; this is a partition. Now, if \(N\) is any fixed object of type \(\nu\) in this category, then the polynomial \(P^{\nu}_{\mu,\lambda}(q)\) specialized at the prime power \(q\) counts the number of subobjects \(L\) of \(N\) having type \(\lambda\) such that the quotient object \(N / L\) has type \(\mu\). This determines the values of the polynomial \(P^{\nu}_{\mu,\lambda}\) at infinitely many points (namely, at all prime powers), and hence \(P^{\nu}_{\mu,\lambda}\) is uniquely determined. The degree of this polynomial is at most \(n(\nu)  n(\lambda)  n(\mu)\), where \(n(\kappa) = \sum_i (i1) \kappa_i\) for every partition \(\kappa\). (If this is negative, then the polynomial is zero.)
These are the structure coefficients of the
(classical) Hall algebra
.If \(\lvert \nu \rvert \neq \lvert \mu \rvert + \lvert \lambda \rvert\), then we have \(P^{\nu}_{\mu,\lambda} = 0\). More generally, if the LittlewoodRichardson coefficient \(c^{\nu}_{\mu,\lambda}\) vanishes, then \(P^{\nu}_{\mu,\lambda} = 0\).
The Hall polynomials satisfy the symmetry property \(P^{\nu}_{\mu,\lambda} = P^{\nu}_{\lambda,\mu}\).
ALGORITHM:
If \(\lambda = (1^r)\) and \(\lvert \nu \rvert = \lvert \mu \rvert + \lvert \lambda \rvert\), then we compute \(P^{\nu}_{\mu,\lambda}\) as follows (cf. Example 2.4 in [Sch2006]):
First, write \(\nu = (1^{l_1}, 2^{l_2}, \ldots, n^{l_n})\), and define a sequence \(r = r_0 \geq r_1 \geq \cdots \geq r_n\) such that
\[\mu = \left( 1^{l_1  r_0 + 2r_1  r_2}, 2^{l_2  r_1 + 2r_2  r_3}, \ldots , (n1)^{l_{n1}  r_{n2} + 2r_{n1}  r_n}, n^{l_n  r_{n1} + r_n} \right).\]Thus if \(\mu = (1^{m_1}, \ldots, n^{m_n})\), we have the following system of equations:
\[\begin{split}\begin{aligned} m_1 & = l_1  r + 2r_1  r_2, \\ m_2 & = l_2  r_1 + 2r_2  r_3, \\ & \vdots , \\ m_{n1} & = l_{n1}  r_{n2} + 2r_{n1}  r_n, \\ m_n & = l_n  r_{n1} + r_n \end{aligned}\end{split}\]and solving for \(r_i\) and back substituting we obtain the equations:
\[\begin{split}\begin{aligned} r_n & = r_{n1} + m_n  l_n, \\ r_{n1} & = r_{n2} + m_{n1}  l_{n1} + m_n  l_n, \\ & \vdots , \\ r_1 & = r + \sum_{k=1}^n (m_k  l_k), \end{aligned}\end{split}\]or in general we have the recursive equation:
\[r_i = r_{i1} + \sum_{k=i}^n (m_k  l_k).\]This, combined with the condition that \(r_0 = r\), determines the \(r_i\) uniquely (recursively). Next we define
\[t = (r_{n2}  r_{n1})(l_n  r_{n1}) + (r_{n3}  r_{n2})(l_{n1} + l_n  r_{n2}) + \cdots + (r_0  r_1)(l_2 + \cdots + l_n  r_1),\]and with these notations we have
\[P^{\nu}_{\mu,(1^r)} = q^t \binom{l_n}{r_{n1}}_q \binom{l_{n1}}{r_{n2}  r_{n1}}_q \cdots \binom{l_1}{r_0  r_1}_q.\]To compute \(P^{\nu}_{\mu,\lambda}\) in general, we compute the product \(I_{\mu} I_{\lambda}\) in the Hall algebra and return the coefficient of \(I_{\nu}\).
EXAMPLES:
sage: from sage.combinat.hall_polynomial import hall_polynomial sage: hall_polynomial([1,1],[1],[1]) q + 1 sage: hall_polynomial([2],[1],[1]) 1 sage: hall_polynomial([2,1],[2],[1]) q sage: hall_polynomial([2,2,1],[2,1],[1,1]) q^2 + q sage: hall_polynomial([2,2,2,1],[2,2,1],[1,1]) q^4 + q^3 + q^2 sage: hall_polynomial([3,2,2,1], [3,2], [2,1]) q^6 + q^5 sage: hall_polynomial([4,2,1,1], [3,1,1], [2,1]) 2*q^3 + q^2  q  1 sage: hall_polynomial([4,2], [2,1], [2,1], 0) 1