#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::{QAlgebra, Ring};
use crate::convert::{FromSchur, ToSchur};
use crate::frac::Frac;
use crate::partition::Partition;
use crate::qt::QtPoly;
use crate::sym::{add_at, by_degree, Monomial, PowerSum, Schur, SymFn};
pub fn qt_kostka<C: Ring>(lambda: &Partition, mu: &Partition) -> QtPoly<C> {
if lambda.size() != mu.size() {
return QtPoly::zero();
}
qt_kostka_column::<C>(mu)
.into_iter()
.find(|(l, _)| l == lambda)
.map(|(_, k)| k)
.unwrap_or_else(QtPoly::zero)
}
pub fn qt_kostka_column<C: Ring>(mu: &Partition) -> Vec<(Partition, QtPoly<C>)> {
let parts = crate::memo::partitions_cached(mu.size());
let j = parts
.iter()
.position(|p| p == mu)
.expect("mu must be a partition of its own size");
let table = qt_kostka_table::<C>(mu.size());
parts
.iter()
.enumerate()
.map(|(i, lambda)| (lambda.clone(), table[i][j].clone()))
.collect()
}
pub fn qt_kostka_table<C: Ring>(n: u32) -> Vec<Vec<QtPoly<C>>> {
qt_kostka_table_via_bh(n)
}
pub fn schur_in_j_table<C: QAlgebra + Send + Sync + 'static>(n: u32) -> Vec<Vec<Frac<C>>> {
(*cached_table::<C>(n)).clone()
}
fn cached_table<C: QAlgebra + Send + Sync + 'static>(n: u32) -> std::sync::Arc<Vec<Vec<Frac<C>>>> {
crate::memo::schur_in_j_cached(n, || schur_in_j_table_uncached::<C>(n))
}
fn schur_in_j_table_uncached<C: QAlgebra>(n: u32) -> Vec<Vec<Frac<C>>> {
let parts = crate::memo::partitions_cached(n);
let index: std::collections::HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let k = qt_kostka_table::<C>(n);
let mut table = vec![vec![<Frac<C> as Ring>::zero(); parts.len()]; parts.len()];
for (j, mu) in parts.iter().enumerate() {
crate::interrupt::poll();
let mut h: Schur<QtPoly<C>> = Schur::zero();
for (i, lambda) in parts.iter().enumerate() {
if !k[i][j].is_zero() {
h.add_term(lambda.clone(), k[i][j].clone());
}
}
let p: PowerSum<QtPoly<C>> = PowerSum::from_schur(&h);
let mut scaled: PowerSum<QtPoly<C>> = PowerSum::zero();
for (nu, c) in p.terms() {
let mut v = c.clone();
for &part in nu.parts() {
v = v.mul_binomial(part, 0);
}
scaled.add_term(nu.clone(), v);
}
let mut den: BTreeMap<(u32, u32), i32> = BTreeMap::new();
for (e, m) in crate::macdonald::c_factors(mu.parts()) {
*den.entry(e).or_insert(0) -= m;
}
for (e, m) in crate::macdonald::c_prime_factors(mu.parts()) {
*den.entry(e).or_insert(0) -= m as i32;
}
let g: Schur<QtPoly<C>> = scaled.to_schur();
for (lambda, c) in g.terms() {
let mut w = Frac::from_poly(c.clone()).mul_factors(&den);
w.reduce();
let i = index[lambda];
table[i][j] = w;
}
}
table
}
pub fn schur_to_macdonald_j<C: QAlgebra + Send + Sync + 'static>(
f: &Schur<QtPoly<C>>,
) -> BTreeMap<Partition, Frac<C>> {
let mut out: BTreeMap<Partition, Frac<C>> = BTreeMap::new();
for (n, terms) in by_degree(f) {
let parts = crate::memo::partitions_cached(n);
let index: std::collections::HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let w = cached_table::<C>(n);
for (lambda, c) in terms {
crate::interrupt::poll();
let scale = Frac::from_poly(c.clone());
let row = &w[index[lambda]];
for (mu, entry) in parts.iter().zip(row) {
if !entry.is_zero() {
add_at(&mut out, mu, entry.mul(&scale));
}
}
}
}
for v in out.values_mut() {
v.reduce();
}
out
}
pub fn qt_kostka_table_via_branching<C: QAlgebra>(n: u32) -> Vec<Vec<QtPoly<C>>> {
let parts = crate::memo::partitions_cached(n);
let mut table = vec![vec![QtPoly::zero(); parts.len()]; parts.len()];
for (j, mu) in parts.iter().enumerate() {
crate::interrupt::poll();
for (lambda, k) in column_expansion::<C>(mu).terms() {
let i = parts
.iter()
.position(|p| p == lambda)
.expect("K_{λμ} is supported on partitions of |μ|");
table[i][j] = k.clone();
}
}
table
}
pub fn macdonald_ht<C: Ring>(mu: &Partition) -> Schur<QtPoly<C>> {
crate::bh::htilde_table::<C>(mu.size())
.into_iter()
.find(|(m, _)| m == mu)
.map(|(_, s)| s)
.expect("mu must be a partition of its own size")
}
pub fn modified_qt_kostka<C: Ring>(lambda: &Partition, mu: &Partition) -> QtPoly<C> {
if lambda.size() != mu.size() {
return QtPoly::zero();
}
macdonald_ht::<C>(mu).coeff(lambda)
}
pub fn qt_kostka_table_via_bh<C: Ring>(n: u32) -> Vec<Vec<QtPoly<C>>> {
let parts = crate::memo::partitions_cached(n);
let index: std::collections::HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let mut table = vec![vec![QtPoly::zero(); parts.len()]; parts.len()];
for (j, (mu, s)) in crate::bh::htilde_table::<C>(n).into_iter().enumerate() {
crate::interrupt::poll();
let n_mu: u32 = mu
.parts()
.iter()
.enumerate()
.map(|(i, &p)| i as u32 * p)
.sum();
debug_assert_eq!(&mu, &parts[j], "htilde_table must share the order");
for (lambda, kt) in s.terms() {
let mut k = QtPoly::zero();
for (&(a, b), c) in kt.terms() {
assert!(
b <= n_mu,
"K~_{{{lambda},{mu}}} has t-degree {b} > n(mu) = {n_mu}"
);
k.add_term(a, n_mu - b, c.clone());
}
table[index[lambda]][j] = k;
}
}
table
}
#[allow(dead_code)]
fn column_via_operator<C: QAlgebra>(mu: &Partition) -> Schur<QtPoly<C>> {
let (b, v) = crate::macop::eigenvector::<C>(mu);
kostka_from_eigenvector(mu, &b, &v)
}
pub fn qt_kostka_table_via_operator<C: QAlgebra>(n: u32) -> Vec<Vec<QtPoly<C>>> {
let parts = crate::memo::partitions_cached(n);
let index: std::collections::HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let mut table = vec![vec![QtPoly::zero(); parts.len()]; parts.len()];
for (j, (mu, b, v)) in crate::macop::eigenvectors::<C>(n).into_iter().enumerate() {
crate::interrupt::poll();
for (lambda, k) in kostka_from_eigenvector(&mu, &b, &v).terms() {
table[index[lambda]][j] = k.clone();
}
}
table
}
fn kostka_from_eigenvector<C: QAlgebra>(
mu: &Partition,
b: &[QtPoly<C>],
v: &QtPoly<C>,
) -> Schur<QtPoly<C>> {
let parts = crate::memo::partitions_cached(mu.size());
let mut formal: Schur<Frac<C>> = Schur::zero();
for (k, kappa) in parts.iter().enumerate() {
crate::interrupt::poll();
if !b[k].is_empty() {
formal.add_term(kappa.clone(), Frac::from_poly(b[k].clone()));
}
}
let p: PowerSum<Frac<C>> = PowerSum::from_schur(&formal);
let mut scaled = PowerSum::zero();
for (rho, c) in p.terms() {
let mut factors: BTreeMap<(u32, u32), i32> = BTreeMap::new();
for &k in rho.parts() {
*factors.entry((k, 0)).or_insert(0) -= 1;
}
let mut w = c.mul_factors(&factors);
w.reduce();
scaled.add_term(rho.clone(), w);
}
let expanded: Schur<Frac<C>> = scaled.to_schur();
let cprime: BTreeMap<(u32, u32), i32> = crate::macdonald::c_prime_factors(mu.parts())
.into_iter()
.map(|(k, m)| (k, m as i32))
.collect();
let mut out = Schur::zero();
for (lambda, c) in expanded.terms() {
let scaled = c.mul_factors(&cprime);
let num = scaled.clone().into_poly().unwrap_or_else(|| {
panic!("K_{{{lambda},{mu}}} is not a polynomial after normalizing: {scaled}")
});
let k = num
.divide_exact(v)
.unwrap_or_else(|| panic!("v must divide the normalized K_{{{lambda},{mu}}}"));
out.add_term(lambda.clone(), k);
}
out
}
fn column_expansion<C: QAlgebra>(mu: &Partition) -> Schur<QtPoly<C>> {
let j: Monomial<Frac<C>> = crate::macdonald_j(mu);
let p: PowerSum<Frac<C>> = PowerSum::from_schur(&j.to_schur());
let expanded: Schur<Frac<C>> = invert_s_basis(&p).to_schur();
let mut out = Schur::zero();
for (lambda, c) in expanded.terms() {
let k = c.clone().into_poly().unwrap_or_else(|| {
panic!("K_{{{lambda},{mu}}} is not a polynomial: {c}");
});
out.add_term(lambda.clone(), k);
}
out
}
fn invert_s_basis<C: QAlgebra>(p: &PowerSum<Frac<C>>) -> PowerSum<Frac<C>> {
let mut out = PowerSum::zero();
for (nu, c) in p.terms() {
let mut factors: BTreeMap<(u32, u32), i32> = BTreeMap::new();
for &part in nu.parts() {
*factors.entry((0, part)).or_insert(0) -= 1;
}
let mut v = c.mul_factors(&factors);
v.reduce();
out.add_term(nu.clone(), v);
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::{Rational, Ring};
type Q = QtPoly<Rational>;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn k(lambda: &[u32], mu: &[u32]) -> Q {
qt_kostka(&part(lambda), &part(mu))
}
#[test]
fn degree_two_is_the_hand_computation() {
assert_eq!(k(&[2], &[2]), <Q as Ring>::one());
assert_eq!(k(&[1, 1], &[2]), QtPoly::term(1, 0, Rational::from_int(1)));
assert_eq!(k(&[2], &[1, 1]), QtPoly::term(0, 1, Rational::from_int(1)));
assert_eq!(k(&[1, 1], &[1, 1]), <Q as Ring>::one());
}
#[test]
fn at_q_zero_it_is_kostka_foulkes() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
for (lambda, kqt) in qt_kostka_column::<Rational>(&mu) {
let want: QtPoly<Rational> = crate::kostka_foulkes(&lambda, &mu);
let got = set_q_to_zero(&kqt);
assert_eq!(got, want, "K_{{{lambda},{mu}}} at q = 0");
}
}
}
}
#[test]
fn conjugating_both_shapes_swaps_q_and_t() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
let conj = qt_kostka_column::<Rational>(&mu.conjugate());
for (lambda, kqt) in qt_kostka_column::<Rational>(&mu) {
let other = conj
.iter()
.find(|(l, _)| l == &lambda.conjugate())
.map(|(_, k)| swap_variables(k))
.unwrap_or_else(QtPoly::zero);
assert_eq!(kqt, other, "K_{{{lambda},{mu}}} under conjugation");
}
}
}
}
#[test]
fn coefficients_are_non_negative_integers() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
for (lambda, kqt) in qt_kostka_column::<Rational>(&mu) {
for (_, c) in kqt.terms() {
assert_eq!(c.denom(), 1, "K_{{{lambda},{mu}}} has {c:?} in it");
assert!(c.numer() > 0, "K_{{{lambda},{mu}}} has {c:?} in it");
}
}
}
}
}
#[test]
fn at_q_and_t_one_it_counts_standard_tableaux() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
let column = qt_kostka_column::<Rational>(&mu);
assert_eq!(
column.len(),
crate::partitions_of(n).len(),
"the column of {mu} should be dense"
);
for (lambda, kqt) in column {
let got: i128 = kqt.terms().map(|(_, c)| c.numer()).sum();
let want = crate::dimension(&lambda).unwrap() as i128;
assert_eq!(got, want, "K_{{{lambda},{mu}}} at q = t = 1");
}
}
}
}
#[test]
fn the_table_agrees_with_the_columns() {
for n in 0..=5u32 {
let parts = crate::partitions_of(n);
let table = qt_kostka_table_via_branching::<Rational>(n);
for (j, mu) in parts.iter().enumerate() {
for (i, lambda) in parts.iter().enumerate() {
assert_eq!(table[i][j], qt_kostka(lambda, mu), "[{i}][{j}]");
}
}
}
let t = qt_kostka_table::<Rational>(3);
assert!(
(0..t.len()).any(|i| (0..t.len()).any(|j| t[i][j] != t[j][i])),
"a symmetric table would make the orientation untestable"
);
}
#[test]
fn the_modified_form_is_symmetric_in_q_and_t() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
let conj = macdonald_ht::<Rational>(&mu.conjugate());
for (lambda, kt) in macdonald_ht::<Rational>(&mu).terms() {
assert_eq!(
kt,
&swap_variables(&conj.coeff(lambda)),
"K~_{{{lambda},{mu}}}"
);
}
}
}
}
#[test]
fn h_tilde_of_degree_two_is_the_known_pair() {
let one = Rational::from_int(1);
let ht = macdonald_ht::<Rational>(&part(&[2]));
assert_eq!(ht.coeff(&part(&[2])), <Q as Ring>::one());
assert_eq!(ht.coeff(&part(&[1, 1])), QtPoly::term(1, 0, one));
let ht = macdonald_ht::<Rational>(&part(&[1, 1]));
assert_eq!(ht.coeff(&part(&[2])), <Q as Ring>::one());
assert_eq!(ht.coeff(&part(&[1, 1])), QtPoly::term(0, 1, one));
}
#[test]
fn the_operator_route_agrees_with_the_branching_route() {
for n in 0..=6u32 {
for mu in crate::partitions_of(n) {
let want = column_expansion::<Rational>(&mu);
let got = column_via_operator::<Rational>(&mu);
for lambda in crate::partitions_of(n) {
assert_eq!(
got.coeff(&lambda),
want.coeff(&lambda),
"K_{{{lambda},{mu}}}"
);
}
}
}
}
#[test]
fn the_schur_table_inverts_the_j_expansion() {
for n in 0..=5u32 {
let parts = crate::partitions_of(n);
let w = schur_in_j_table::<Rational>(n);
let b: Vec<Schur<Frac<Rational>>> = parts
.iter()
.map(|mu| crate::macdonald_j::<Rational>(mu).to_schur())
.collect();
for (i, lambda) in parts.iter().enumerate() {
for (l, nu) in parts.iter().enumerate() {
let mut sum = <Frac<Rational> as Ring>::zero();
for j in 0..parts.len() {
sum.add_assign(&w[i][j].mul(&b[j].coeff(nu)));
}
let want = if i == l {
<Frac<Rational> as Ring>::one()
} else {
<Frac<Rational> as Ring>::zero()
};
assert_eq!(sum, want, "row {lambda} against J of {nu}");
}
}
}
}
#[test]
fn the_diagonal_is_one_over_c_lambda() {
for n in 0..=5u32 {
let parts = crate::partitions_of(n);
let w = schur_in_j_table::<Rational>(n);
for (i, lambda) in parts.iter().enumerate() {
let inv: BTreeMap<(u32, u32), i32> = crate::macdonald::c_factors(lambda.parts())
.into_iter()
.map(|(e, m)| (e, -m))
.collect();
assert_eq!(w[i][i], Frac::from_factors(&inv), "the {lambda} diagonal");
}
}
}
fn set_q_to_zero(p: &QtPoly<Rational>) -> QtPoly<Rational> {
let mut out = QtPoly::zero();
for (&(a, b), c) in p.terms() {
if a == 0 {
out.add_term(0, b, *c);
}
}
out
}
fn swap_variables(p: &QtPoly<Rational>) -> QtPoly<Rational> {
let mut out = QtPoly::zero();
for (&(a, b), c) in p.terms() {
out.add_term(b, a, *c);
}
out
}
fn s_in_j(lambda: &[u32]) -> BTreeMap<Partition, Frac<Rational>> {
let one = QtPoly::term(0, 0, Rational::from_int(1));
schur_to_macdonald_j(&Schur::monomial(part(lambda), one))
}
fn over(factors: &[((u32, u32), i32)]) -> Frac<Rational> {
Frac::from_factors(&factors.iter().map(|&(e, m)| (e, -m)).collect())
}
#[test]
fn s2_and_s11_in_j_are_the_hand_values() {
let mut t_minus_q: Q = QtPoly::term(0, 1, Rational::from_int(1));
t_minus_q.add_term(1, 0, Rational::from_int(-1));
let in_j = s_in_j(&[2]);
assert_eq!(in_j.len(), 2, "s_2 reaches both shapes");
assert_eq!(
in_j[&part(&[2])],
over(&[((0, 1), 1), ((1, 1), 1)]),
"s_2 at J_2"
);
assert_eq!(
in_j[&part(&[1, 1])],
over(&[((0, 1), 1), ((0, 2), 1), ((1, 1), 1)]).mul(&Frac::from_poly(t_minus_q)),
"s_2 at J_11"
);
let in_j = s_in_j(&[1, 1]);
assert_eq!(in_j.len(), 1, "s_11 reaches J_11 alone");
assert_eq!(
in_j[&part(&[1, 1])],
over(&[((0, 1), 1), ((0, 2), 1)]),
"s_11 at J_11"
);
}
#[test]
fn the_cached_table_is_the_computed_table_for_each_ring() {
use crate::guard::GuardedRat;
for n in 0..=4u32 {
let want = schur_in_j_table_uncached::<Rational>(n);
crate::clear_caches();
assert_eq!(schur_in_j_table::<Rational>(n), want, "cold at degree {n}");
assert_eq!(schur_in_j_table::<Rational>(n), want, "warm at degree {n}");
let wide = schur_in_j_table_uncached::<GuardedRat>(n);
assert_eq!(
schur_in_j_table::<GuardedRat>(n),
wide,
"a second ring read the first ring's entry at degree {n}"
);
}
crate::clear_caches();
}
#[test]
fn the_j_expansion_is_the_table_read_by_rows() {
for n in 0..=5u32 {
let parts = crate::partitions_of(n);
let w = schur_in_j_table::<Rational>(n);
for (i, lambda) in parts.iter().enumerate() {
let got = s_in_j(lambda.parts());
for (j, mu) in parts.iter().enumerate() {
let want = &w[i][j];
if want.is_zero() {
assert!(!got.contains_key(mu), "an explicit zero at {lambda}, {mu}");
} else {
assert_eq!(got[mu], *want, "{lambda} at {mu}");
}
}
}
}
}
#[test]
fn the_j_expansion_is_linear_and_takes_mixed_degrees() {
let mut f: Schur<Q> = Schur::monomial(part(&[2]), <Q as Ring>::one());
f.add_term(part(&[2, 1]), QtPoly::term(0, 0, Rational::from_int(3)));
let got = schur_to_macdonald_j(&f);
let low = s_in_j(&[2]);
let high = s_in_j(&[2, 1]);
let three = Frac::from_poly(QtPoly::term(0, 0, Rational::from_int(3)));
assert_eq!(
got.len(),
low.len() + high.len(),
"degrees 2 and 3 collided"
);
for (mu, c) in &low {
assert_eq!(&got[mu], c, "degree 2 changed at {mu}");
}
for (mu, c) in &high {
assert_eq!(got[mu], c.mul(&three), "degree 3 is not 3x at {mu}");
}
assert!(schur_to_macdonald_j(&Schur::<Q>::zero()).is_empty());
}
}