#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::{BTreeMap, HashMap};
use std::rc::Rc;
use crate::coeff::{QAlgebra, Ring};
use crate::convert::FromSchur;
use crate::frac::Frac;
use crate::partition::Partition;
use crate::qt::QtPoly;
use crate::sym::{add_at, by_degree, PowerSum, Schur, SymFn};
pub fn hall_littlewood<C: Ring>(lambda: &Partition) -> Schur<QtPoly<C>> {
let mut memo = HashMap::new();
Rc::try_unwrap(hl_suffix(lambda.parts(), &mut memo)).unwrap_or_else(|rc| (*rc).clone())
}
pub fn hall_littlewood_table<C: Ring>(n: u32) -> Vec<(Partition, Schur<QtPoly<C>>)> {
let mut memo = HashMap::new();
crate::partitions_of(n)
.into_iter()
.map(|lambda| {
let v = hl_suffix(lambda.parts(), &mut memo);
(lambda, (*v).clone())
})
.collect()
}
pub fn hall_littlewood_p_table<C: Ring>(n: u32) -> Vec<(Partition, Schur<QtPoly<C>>)> {
let parts = crate::memo::partitions_cached(n);
let k = crate::kf::kostka_foulkes_table::<C>(n);
let mut out: Vec<Schur<QtPoly<C>>> = vec![Schur::zero(); parts.len()];
for j in (0..parts.len()).rev() {
let mut acc = Schur::monomial(parts[j].clone(), <QtPoly<C> as Ring>::one());
for l in (j + 1)..parts.len() {
let coeff = &k[j][l];
if coeff.is_zero() {
continue;
}
let done = std::mem::replace(&mut out[l], Schur::zero());
for (nu, c) in done.terms() {
acc.add_term(nu.clone(), coeff.mul(c).neg());
}
out[l] = done;
}
out[j] = acc;
}
parts.iter().cloned().zip(out).collect()
}
pub fn hall_littlewood_p<C: Ring>(lambda: &Partition) -> Schur<QtPoly<C>> {
hall_littlewood_p_table(lambda.size())
.into_iter()
.find(|(mu, _)| mu == lambda)
.map(|(_, f)| f)
.expect("hall_littlewood_p_table(|λ|) lists every partition of |λ|")
}
pub fn schur_to_hall_littlewood_p<C: Ring>(f: &Schur<QtPoly<C>>) -> BTreeMap<Partition, QtPoly<C>> {
let mut out = BTreeMap::new();
for (n, terms) in by_degree(f) {
let parts = crate::memo::partitions_cached(n);
let index: HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let k = crate::kf::kostka_foulkes_table::<C>(n);
for (mu, c) in terms {
crate::interrupt::poll();
let row = &k[index[mu]];
for (lambda, entry) in parts.iter().zip(row) {
if !entry.is_zero() {
add_at(&mut out, lambda, entry.mul(c));
}
}
}
}
out
}
pub fn schur_to_hall_littlewood_qp<C: Ring>(
f: &Schur<QtPoly<C>>,
) -> BTreeMap<Partition, QtPoly<C>> {
let mut out = BTreeMap::new();
for (n, terms) in by_degree(f) {
let table = hall_littlewood_p_table::<C>(n);
for (nu, c) in terms {
crate::interrupt::poll();
for (lambda, p) in &table {
if let Some(a) = p.terms().get(nu) {
add_at(&mut out, lambda, a.mul(c));
}
}
}
}
out
}
fn expand_hl<C: Ring>(
f: &BTreeMap<Partition, QtPoly<C>>,
table_of: fn(u32) -> Vec<(Partition, Schur<QtPoly<C>>)>,
) -> Schur<QtPoly<C>> {
let mut by_deg: BTreeMap<u32, Vec<(&Partition, &QtPoly<C>)>> = BTreeMap::new();
for (lambda, c) in f {
by_deg.entry(lambda.size()).or_default().push((lambda, c));
}
let mut out = Schur::zero();
for (n, terms) in by_deg {
let table = table_of(n);
for (lambda, c) in terms {
crate::interrupt::poll();
let row = table
.iter()
.find(|(mu, _)| mu == lambda)
.expect("the table lists every partition of its degree");
for (mu, v) in row.1.terms() {
out.add_term(mu.clone(), v.mul(c));
}
}
}
out
}
pub fn hall_littlewood_p_to_schur<C: Ring>(f: &BTreeMap<Partition, QtPoly<C>>) -> Schur<QtPoly<C>> {
expand_hl(f, hall_littlewood_p_table::<C>)
}
pub fn hall_littlewood_qp_to_schur<C: Ring>(
f: &BTreeMap<Partition, QtPoly<C>>,
) -> Schur<QtPoly<C>> {
expand_hl(f, hall_littlewood_table::<C>)
}
pub fn powersum_scalar_t<C: Ring>(f: &PowerSum<Frac<C>>, g: &PowerSum<Frac<C>>) -> Frac<C> {
let mut out = <Frac<C> as Ring>::zero();
for (mu, a) in f.terms() {
let Some(b) = g.terms().get(mu) else { continue };
let mut factors: BTreeMap<(u32, u32), i32> = BTreeMap::new();
for &part in mu.parts() {
*factors.entry((0, part)).or_insert(0) -= 1;
}
let term = a.mul(b).mul(&mu.z_in::<Frac<C>>());
out.add_assign(&term.mul_factors(&factors));
}
out.reduce();
out
}
pub fn scalar_t<C: QAlgebra>(f: &Schur<Frac<C>>, g: &Schur<Frac<C>>) -> Frac<C> {
powersum_scalar_t(&PowerSum::from_schur(f), &PowerSum::from_schur(g))
}
type Memo<C> = HashMap<Vec<u32>, Rc<Schur<QtPoly<C>>>>;
fn hl_suffix<C: Ring>(parts: &[u32], memo: &mut Memo<C>) -> Rc<Schur<QtPoly<C>>> {
if parts.is_empty() {
return Rc::new(Schur::monomial(
Partition::new([]),
<QtPoly<C> as Ring>::one(),
));
}
if let Some(hit) = memo.get(parts) {
return Rc::clone(hit);
}
let first = parts[0] as i64;
let prev = hl_suffix(&parts[1..], memo);
let mut out = Schur::zero();
let mut v: Vec<i64> = Vec::with_capacity(parts.len() + 1);
let mut beta: Vec<i64> = Vec::with_capacity(parts.len() + 1);
for (nu, c) in prev.terms() {
crate::interrupt::poll();
let nu = nu.parts();
removals(nu, nu.len(), &mut v, 0, &mut |mu, i| {
beta.clear();
beta.extend_from_slice(mu);
beta.push(first + i as i64);
if let Some((negate, mu)) = straighten(&mut beta) {
out.terms_mut()
.entry(mu)
.or_insert_with(<QtPoly<C> as Ring>::zero)
.add_shifted(c, (0, i), negate);
}
});
}
out.terms_mut().retain(|_, c| !c.is_zero());
let out = Rc::new(out);
memo.insert(parts.to_vec(), Rc::clone(&out));
out
}
fn removals(
nu: &[u32],
row: usize,
cur: &mut Vec<i64>,
removed: u32,
emit: &mut impl FnMut(&mut Vec<i64>, u32),
) {
if row == 0 {
emit(cur, removed);
return;
}
let r = row - 1;
let floor = if r + 1 < nu.len() { nu[r + 1] } else { 0 };
for m in floor..=nu[r] {
cur.push(m as i64);
removals(nu, r, cur, removed + (nu[r] - m), emit);
cur.pop();
}
}
fn straighten(v: &mut [i64]) -> Option<(bool, Partition)> {
let l = v.len();
for (j, x) in v.iter_mut().enumerate() {
*x += j as i64;
}
let mut swaps = 0usize;
for i in 1..l {
let mut j = i;
while j > 0 && v[j - 1] > v[j] {
v.swap(j - 1, j);
swaps += 1;
j -= 1;
}
}
for i in 1..l {
if v[i] == v[i - 1] {
return None; }
}
if l > 0 && v[0] < 0 {
return None; }
let parts: Vec<u32> = (0..l)
.rev()
.map(|j| (v[j] - j as i64) as u32)
.filter(|&x| x > 0)
.collect();
Some((swaps % 2 == 1, Partition::from_sorted(parts)))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::convert::ToSchur;
use crate::sym::{Homogeneous, Monomial};
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
type Q = QtPoly<i64>;
type F = Frac<Rational>;
fn b_t_factors(lambda: &Partition) -> BTreeMap<(u32, u32), i32> {
let mut factors = BTreeMap::new();
for (_, mult) in lambda.part_multiplicities() {
for j in 1..=mult {
*factors.entry((0, j)).or_insert(0) += 1;
}
}
factors
}
#[test]
fn p_is_orthogonal_under_scalar_t_with_norm_one_over_b() {
for n in 1..=5u32 {
let table: Vec<(Partition, Schur<F>)> = hall_littlewood_p_table::<Rational>(n)
.into_iter()
.map(|(la, f)| {
let terms = f
.terms()
.iter()
.map(|(mu, c)| (mu.clone(), Frac::from_poly(c.clone())))
.collect();
(la, Schur::from_terms(terms))
})
.collect();
for (la, f) in &table {
for (mu, g) in &table {
let got = scalar_t(f, g);
if la == mu {
assert_eq!(
got.mul(&Frac::from_factors(&b_t_factors(la))),
<F as Ring>::one(),
"⟨P_{la}, P_{la}⟩_t · b_{la}"
);
} else {
assert!(got.is_zero(), "⟨P_{la}, P_{mu}⟩_t must vanish");
}
}
}
}
}
#[test]
fn scalar_t_hand_values() {
let s = |la: &[u32]| -> Schur<F> { Schur::monomial(part(la), <F as Ring>::one()) };
assert_eq!(scalar_t(&s(&[1]), &s(&[1])), F::inv_factor(0, 1));
let want = F::inv_factor(0, 1).mul(&F::inv_factor(0, 2));
assert_eq!(scalar_t(&s(&[2]), &s(&[2])), want);
assert!(scalar_t(&s(&[2]), &s(&[1])).is_zero());
}
#[test]
fn at_t_zero_it_is_the_schur_function() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let hl: Schur<Q> = hall_littlewood(&lambda);
for (mu, c) in hl.terms() {
let want = i64::from(*mu == lambda);
assert_eq!(c.eval(&0, &0), want, "Q'_{lambda} at t=0, term {mu}");
}
}
}
}
#[test]
fn at_t_one_it_is_the_complete_homogeneous() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let hl: Schur<Q> = hall_littlewood(&lambda);
let h: Schur<i64> = Homogeneous::monomial(lambda.clone(), 1).to_schur();
for (mu, c) in hl.terms() {
assert_eq!(c.eval(&0, &1), h.coeff(mu), "Q'_{lambda} at t=1, {mu}");
}
assert_eq!(
hl.terms().len(),
h.terms().len(),
"same support at t = 1 for {lambda}"
);
}
}
}
#[test]
fn coefficients_are_kostka_foulkes() {
for n in 0..=8u32 {
let parts = crate::partitions_of(n);
for lambda in &parts {
let hl: Schur<Q> = hall_littlewood(lambda);
for mu in &parts {
let want = crate::charge::kostka_foulkes_by_charge::<i64>(mu, lambda);
assert_eq!(hl.coeff(mu), want, "K_{mu}{lambda}(t)");
}
}
}
}
#[test]
fn expansion_is_unitriangular() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let hl: Schur<Q> = hall_littlewood(&lambda);
assert_eq!(hl.coeff(&lambda), <Q as Ring>::one(), "K_{lambda}{lambda}");
for mu in hl.terms().keys() {
assert!(
crate::kostka::kostka(mu, &lambda) > 0,
"{mu} appears in Q'_{lambda} but is outside the Kostka support"
);
}
}
}
}
#[test]
fn p_inverts_the_kostka_foulkes_matrix() {
for n in 0..=8u32 {
let parts = crate::partitions_of(n);
let table: Vec<(Partition, Schur<Q>)> = hall_littlewood_p_table(n);
for mu in &parts {
let mut acc: Schur<Q> = Schur::zero();
for (lambda, p) in &table {
let k = crate::kostka_foulkes::<i64>(mu, lambda);
if k.is_zero() {
continue;
}
for (nu, c) in p.terms() {
acc.add_term(nu.clone(), k.mul(c));
}
}
let want: Schur<Q> = Schur::monomial(mu.clone(), <Q as Ring>::one());
assert_eq!(acc, want, "s_{mu} = sum_lambda K P_lambda");
}
}
}
#[test]
fn the_inverse_expansions_undo_the_forward_ones() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let unit: BTreeMap<Partition, Q> =
[(lambda.clone(), <Q as Ring>::one())].into_iter().collect();
let p: Schur<Q> = hall_littlewood_p(&lambda);
assert_eq!(schur_to_hall_littlewood_p(&p), unit, "s -> P of P_{lambda}");
let qp: Schur<Q> = hall_littlewood(&lambda);
assert_eq!(
schur_to_hall_littlewood_qp(&qp),
unit,
"s -> Q' of Q'_{lambda}"
);
}
}
}
#[test]
fn every_schur_function_comes_back_as_itself() {
for n in 0..=8u32 {
for mu in crate::partitions_of(n) {
let f: Schur<Q> = Schur::monomial(mu.clone(), <Q as Ring>::one());
assert_eq!(
hall_littlewood_p_to_schur(&schur_to_hall_littlewood_p(&f)),
f,
"P at s_{mu}"
);
assert_eq!(
hall_littlewood_qp_to_schur(&schur_to_hall_littlewood_qp(&f)),
f,
"Q' at s_{mu}"
);
}
}
}
#[test]
fn s2_in_p_and_s11_in_qp_are_the_hand_values() {
let one = <Q as Ring>::one();
let s2: Schur<Q> = Schur::monomial(part(&[2]), one.clone());
let want_p: BTreeMap<Partition, Q> = [(part(&[1, 1]), Q::t()), (part(&[2]), one.clone())]
.into_iter()
.collect();
assert_eq!(schur_to_hall_littlewood_p(&s2), want_p, "s_2 in P");
let s11: Schur<Q> = Schur::monomial(part(&[1, 1]), one.clone());
let want_qp: BTreeMap<Partition, Q> =
[(part(&[1, 1]), one), (part(&[2]), Q::term(0, 1, -1))]
.into_iter()
.collect();
assert_eq!(schur_to_hall_littlewood_qp(&s11), want_qp, "s_11 in Q'");
}
#[test]
fn the_inverse_expansions_are_linear_across_degrees() {
let terms: [(Partition, Q); 3] = [
(part(&[2]), <Q as Ring>::one()),
(part(&[1]), Q::term(0, 1, -1)),
(part(&[2, 1]), Q::term(0, 0, 3)),
];
let mut f: Schur<Q> = Schur::zero();
for (la, c) in &terms {
f.add_term(la.clone(), c.clone());
}
for (name, convert) in [
(
"s -> P",
schur_to_hall_littlewood_p as fn(&Schur<Q>) -> BTreeMap<Partition, Q>,
),
("s -> Q'", schur_to_hall_littlewood_qp),
] {
let mut want: BTreeMap<Partition, Q> = BTreeMap::new();
for (la, c) in &terms {
let one: Schur<Q> = Schur::monomial(la.clone(), <Q as Ring>::one());
for (mu, v) in convert(&one) {
add_at(&mut want, &mu, v.mul(c));
}
}
assert_eq!(convert(&f), want, "{name} on a mixed-degree element");
}
let zero: Schur<Q> = Schur::zero();
assert!(schur_to_hall_littlewood_p(&zero).is_empty(), "s -> P of 0");
assert!(
schur_to_hall_littlewood_qp(&zero).is_empty(),
"s -> Q' of 0"
);
}
#[test]
fn p_specializes_to_schur_and_monomial() {
use crate::sym::Monomial;
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let p: Schur<Q> = hall_littlewood_p(&lambda);
for (mu, c) in p.terms() {
assert_eq!(
c.eval(&0, &0),
i64::from(*mu == lambda),
"P_{lambda} at t = 0 must be s_{lambda}, term {mu}"
);
}
let m: Schur<i64> = Monomial::monomial(lambda.clone(), 1).to_schur();
for (mu, c) in p.terms() {
assert_eq!(c.eval(&0, &1), m.coeff(mu), "P_{lambda} at t = 1, {mu}");
}
for (mu, want) in m.terms() {
assert_eq!(p.coeff(mu).eval(&0, &1), *want, "missing {mu} at t = 1");
}
}
}
}
#[test]
fn table_agrees_with_individual_calls() {
for n in 0..=9u32 {
for (lambda, got) in hall_littlewood_table::<i64>(n) {
assert_eq!(got, hall_littlewood(&lambda), "table at {lambda}");
}
}
}
#[test]
fn straightening_follows_the_beta_rules() {
assert_eq!(straighten(&mut [1, 2]), Some((false, part(&[2, 1]))));
assert_eq!(straighten(&mut [2, 1]), None);
assert_eq!(straighten(&mut [0, 3]), Some((false, part(&[3]))));
assert_eq!(straighten(&mut [3, 1]), Some((true, part(&[2, 2]))));
assert_eq!(straighten(&mut [-1, 5]), None);
assert_eq!(straighten(&mut []), Some((false, part(&[]))));
}
#[test]
fn it_is_q_prime_not_p() {
let hl: Schur<Q> = hall_littlewood(&part(&[2, 1]));
let m: Schur<i64> = Monomial::monomial(part(&[2, 1]), 1).to_schur();
let at_one: Vec<(Partition, i64)> = hl
.terms()
.iter()
.map(|(mu, c)| (mu.clone(), c.eval(&0, &1)))
.collect();
let as_m: Vec<(Partition, i64)> =
m.terms().iter().map(|(mu, c)| (mu.clone(), *c)).collect();
assert_ne!(at_one, as_m, "Q'_(2,1)(x;1) must be h_(2,1), not m_(2,1)");
}
}