Hall Algebras¶
AUTHORS:
- Travis Scrimshaw (2013-10-17): Initial version
-
sage.algebras.hall_algebra.
HallAlgebra
¶ The (classical) Hall algebra.
The (classical) Hall algebra over a commutative ring \(R\) with a parameter \(q \in R\) is defined to be the free \(R\)-module with basis \((I_\lambda)\), where \(\lambda\) runs over all integer partitions. The algebra structure is given by a product defined by
\[I_\mu \cdot I_\lambda = \sum_\nu P^{\nu}_{\mu, \lambda}(q) I_\nu,\]where \(P^{\nu}_{\mu, \lambda}\) is a Hall polynomial (see
hall_polynomial()
). The unity of this algebra is \(I_{\emptyset}\).The (classical) Hall algebra is also known as the Hall-Steinitz algebra.
We can define an \(R\)-algebra isomorphism \(\Phi\) from the \(R\)-algebra of symmetric functions (see
SymmetricFunctions
) to the (classical) Hall algebra by sending the \(r\)-th elementary symmetric function \(e_r\) to \(q^{r(r-1)/2} I_{(1^r)}\) for every positive integer \(r\). This isomorphism used to transport the Hopf algebra structure from the \(R\)-algebra of symmetric functions to the Hall algebra, thus making the latter a connected graded Hopf algebra. If \(\lambda\) is a partition, then the preimage of the basis element \(I_{\lambda}\) under this isomorphism is \(q^{n(\lambda)} P_{\lambda}(x; q^{-1})\), where \(P_{\lambda}\) denotes the \(\lambda\)-th Hall-Littlewood \(P\)-function, and where \(n(\lambda) = \sum_i (i - 1) \lambda_i\).See section 2.3 in [Sch2006], and sections II.2 and III.3 in [Macdonald1995] (where our \(I_{\lambda}\) is called \(u_{\lambda}\)).
EXAMPLES:
sage: R.<q> = ZZ[] sage: H = HallAlgebra(R, q) sage: H[2,1]*H[1,1] H[3, 2] + (q+1)*H[3, 1, 1] + (q^2+q)*H[2, 2, 1] + (q^4+q^3+q^2)*H[2, 1, 1, 1] sage: H[2]*H[2,1] H[4, 1] + q*H[3, 2] + (q^2-1)*H[3, 1, 1] + (q^3+q^2)*H[2, 2, 1] sage: H[3]*H[1,1] H[4, 1] + q^2*H[3, 1, 1] sage: H[3]*H[2,1] H[5, 1] + q*H[4, 2] + (q^2-1)*H[4, 1, 1] + q^3*H[3, 2, 1]
We can rewrite the Hall algebra in terms of monomials of the elements \(I_{(1^r)}\):
sage: I = H.monomial_basis() sage: H(I[2,1,1]) H[3, 1] + (q+1)*H[2, 2] + (2*q^2+2*q+1)*H[2, 1, 1] + (q^5+2*q^4+3*q^3+3*q^2+2*q+1)*H[1, 1, 1, 1] sage: I(H[2,1,1]) I[3, 1] + (-q^3-q^2-q-1)*I[4]
The isomorphism between the Hall algebra and the symmetric functions described above is implemented as a coercion:
sage: R = PolynomialRing(ZZ, 'q').fraction_field() sage: q = R.gen() sage: H = HallAlgebra(R, q) sage: e = SymmetricFunctions(R).e() sage: e(H[1,1,1]) 1/q^3*e[3]
We can also do computations with any special value of
q
, such as \(0\) or \(1\) or (most commonly) a prime power. Here is an example using a prime:sage: H = HallAlgebra(ZZ, 2) sage: H[2,1]*H[1,1] H[3, 2] + 3*H[3, 1, 1] + 6*H[2, 2, 1] + 28*H[2, 1, 1, 1] sage: H[3,1]*H[2] H[5, 1] + H[4, 2] + 6*H[3, 3] + 3*H[4, 1, 1] + 8*H[3, 2, 1] sage: H[2,1,1]*H[3,1] H[5, 2, 1] + 2*H[4, 3, 1] + 6*H[4, 2, 2] + 7*H[5, 1, 1, 1] + 19*H[4, 2, 1, 1] + 24*H[3, 3, 1, 1] + 48*H[3, 2, 2, 1] + 105*H[4, 1, 1, 1, 1] + 224*H[3, 2, 1, 1, 1] sage: I = H.monomial_basis() sage: H(I[2,1,1]) H[3, 1] + 3*H[2, 2] + 13*H[2, 1, 1] + 105*H[1, 1, 1, 1] sage: I(H[2,1,1]) I[3, 1] - 15*I[4]
If \(q\) is set to \(1\), the coercion to the symmetric functions sends \(I_{\lambda}\) to \(m_{\lambda}\):
sage: H = HallAlgebra(QQ, 1) sage: H[2,1] * H[2,1] H[4, 2] + 2*H[3, 3] + 2*H[4, 1, 1] + 2*H[3, 2, 1] + 6*H[2, 2, 2] + 4*H[2, 2, 1, 1] sage: m = SymmetricFunctions(QQ).m() sage: m[2,1] * m[2,1] 4*m[2, 2, 1, 1] + 6*m[2, 2, 2] + 2*m[3, 2, 1] + 2*m[3, 3] + 2*m[4, 1, 1] + m[4, 2] sage: m(H[3,1]) m[3, 1]
We can set \(q\) to \(0\) (but should keep in mind that we don’t get the Schur functions this way):
sage: H = HallAlgebra(QQ, 0) sage: H[2,1] * H[2,1] H[4, 2] + H[3, 3] + H[4, 1, 1] - H[3, 2, 1] - H[3, 1, 1, 1]
-
sage.algebras.hall_algebra.
HallAlgebraMonomials
¶ The classical Hall algebra given in terms of monomials in the \(I_{(1^r)}\).
We first associate a monomial \(I_{(1^{r_1})} I_{(1^{r_2})} \cdots I_{(1^{r_k})}\) with the composition \((r_1, r_2, \ldots, r_k)\). However since \(I_{(1^r)}\) commutes with \(I_{(1^s)}\), the basis is indexed by partitions.
EXAMPLES:
We use the fraction field of \(\ZZ[q]\) for our initial example:
sage: R = PolynomialRing(ZZ, 'q').fraction_field() sage: q = R.gen() sage: H = HallAlgebra(R, q) sage: I = H.monomial_basis()
We check that the basis conversions are mutually inverse:
sage: all(H(I(H[p])) == H[p] for i in range(7) for p in Partitions(i)) True sage: all(I(H(I[p])) == I[p] for i in range(7) for p in Partitions(i)) True
Since Laurent polynomials are sufficient, we run the same check with the Laurent polynomial ring \(\ZZ[q, q^{-1}]\):
sage: R.<q> = LaurentPolynomialRing(ZZ) sage: H = HallAlgebra(R, q) sage: I = H.monomial_basis() sage: all(H(I(H[p])) == H[p] for i in range(6) for p in Partitions(i)) # long time True sage: all(I(H(I[p])) == I[p] for i in range(6) for p in Partitions(i)) # long time True
We can also convert to the symmetric functions. The natural basis corresponds to the Hall-Littlewood basis (up to a renormalization and an inversion of the \(q\) parameter), and this basis corresponds to the elementary basis (up to a renormalization):
sage: Sym = SymmetricFunctions(R) sage: e = Sym.e() sage: e(I[2,1]) (q^-1)*e[2, 1] sage: e(I[4,2,2,1]) (q^-8)*e[4, 2, 2, 1] sage: HLP = Sym.hall_littlewood(q).P() sage: H(I[2,1]) H[2, 1] + (1+q+q^2)*H[1, 1, 1] sage: HLP(e[2,1]) (1+q+q^2)*HLP[1, 1, 1] + HLP[2, 1] sage: all( e(H[lam]) == q**-sum([i * x for i, x in enumerate(lam)]) ....: * e(HLP[lam]).map_coefficients(lambda p: p(q**(-1))) ....: for lam in Partitions(4) ) True
We can also do computations using a prime power:
sage: H = HallAlgebra(ZZ, 3) sage: I = H.monomial_basis() sage: i_elt = I[2,1]*I[1,1]; i_elt I[2, 1, 1, 1] sage: H(i_elt) H[4, 1] + 7*H[3, 2] + 37*H[3, 1, 1] + 136*H[2, 2, 1] + 1495*H[2, 1, 1, 1] + 62920*H[1, 1, 1, 1, 1]
-
sage.algebras.hall_algebra.
transpose_cmp
(x, y)¶ Compare partitions
x
andy
in transpose dominance order.We say partitions \(\mu\) and \(\lambda\) satisfy \(\mu \prec \lambda\) in transpose dominance order if for all \(i \geq 1\) we have:
\[l_1 + 2 l_2 + \cdots + (i-1) l_{i-1} + i(l_i + l_{i+1} + \cdots) \leq m_1 + 2 m_2 + \cdots + (i-1) m_{i-1} + i(m_i + m_{i+1} + \cdots),\]where \(l_k\) denotes the number of appearances of \(k\) in \(\lambda\), and \(m_k\) denotes the number of appearances of \(k\) in \(\mu\).
Equivalently, \(\mu \prec \lambda\) if the conjugate of the partition \(\mu\) dominates the conjugate of the partition \(\lambda\).
Since this is a partial ordering, we fallback to lex ordering \(\mu <_L \lambda\) if we cannot compare in the transpose order.
EXAMPLES:
sage: from sage.algebras.hall_algebra import transpose_cmp sage: transpose_cmp(Partition([4,3,1]), Partition([3,2,2,1])) -1 sage: transpose_cmp(Partition([2,2,1]), Partition([3,2])) 1 sage: transpose_cmp(Partition([4,1,1]), Partition([4,1,1])) 0