#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::Ring;
use crate::partition::Partition;
use crate::qt::QtPoly;
type Atom = (u32, u32);
fn atom<C: Ring>((a, b): Atom) -> QtPoly<C> {
let mut p = QtPoly::term(a, 0, C::one());
p.add_term(0, b, C::one().neg());
p
}
fn divide_by_atom<C: Ring>(num: &QtPoly<C>, (a, b): Atom) -> Option<QtPoly<C>> {
debug_assert!(a > 0 || b > 0, "q^0 - t^0 is zero");
if a == 0 {
crate::frac::divide_by_factor(num, 0, b)
} else if b == 0 {
crate::frac::divide_by_factor(num, a, 0).map(|q| q.neg())
} else if crate::frac::diff_may_divide(num, a, b) {
crate::frac::divide_by_diff(num, a, b)
} else {
None
}
}
#[derive(Clone, Debug)]
pub struct Rat<C: Ring> {
num: QtPoly<C>,
den: BTreeMap<Atom, u32>,
}
impl<C: Ring + 'static> crate::memo::HeapSize for Rat<C> {
fn heap_bytes(&self) -> usize {
crate::memo::HeapSize::heap_bytes(&self.num) + crate::memo::HeapSize::heap_bytes(&self.den)
}
}
impl<C: Ring> Rat<C> {
fn one() -> Self {
Rat {
num: <QtPoly<C> as Ring>::one(),
den: BTreeMap::new(),
}
}
fn zero() -> Self {
Rat {
num: QtPoly::zero(),
den: BTreeMap::new(),
}
}
fn from_poly(num: QtPoly<C>) -> Self {
Rat {
num,
den: BTreeMap::new(),
}
}
fn is_zero(&self) -> bool {
self.num.is_empty()
}
fn scale_by_ratio(&mut self, up: Atom, down: Atom) {
if up == down {
return;
}
self.num = self.num.mul(&atom(up));
*self.den.entry(down).or_insert(0) += 1;
}
fn mul(&self, other: &Self) -> Self {
let mut den = self.den.clone();
for (k, &m) in &other.den {
*den.entry(*k).or_insert(0) += m;
}
Rat {
num: self.num.mul(&other.num),
den,
}
}
fn lift(&self, target: &BTreeMap<Atom, u32>) -> QtPoly<C> {
let mut num = self.num.clone();
for (&k, &m) in target {
for _ in 0..(m - self.den.get(&k).copied().unwrap_or(0)) {
num = num.mul(&atom(k));
}
}
num
}
fn add_assign(&mut self, other: &Self) {
if other.is_zero() {
return;
}
if self.is_zero() {
*self = other.clone();
return;
}
if other.den != self.den {
let mut lcm = self.den.clone();
for (&k, &m) in &other.den {
let e = lcm.entry(k).or_insert(0);
*e = (*e).max(m);
}
self.num = self.lift(&lcm);
self.den = lcm;
}
let lifted = other.lift(&self.den);
self.num.add_assign(&lifted);
}
fn reduce(&mut self) {
if self.num.is_empty() {
self.den.clear();
return;
}
self.den.retain(|&k, m| {
while *m > 0 {
match divide_by_atom(&self.num, k) {
Some(q) => {
self.num = q;
*m -= 1;
}
None => break,
}
}
*m > 0
});
}
fn into_poly(mut self) -> Option<QtPoly<C>> {
self.reduce();
self.den.is_empty().then_some(self.num)
}
}
fn bi_exponent<C: Ring>(mu: &Partition, nu: &Partition) -> QtPoly<C> {
let mut out = QtPoly::zero();
for i in 0..mu.len() {
for j in nu.part(i)..mu.part(i) {
out.add_term(j, i as u32, C::one());
}
}
out
}
fn one_box<C: Ring>(mu: &Partition, nu: &Partition) -> Rat<C> {
let (mut row, mut col) = (usize::MAX, u32::MAX);
for i in 0..mu.len() {
if mu.part(i) != nu.part(i) {
row = i;
col = nu.part(i);
break;
}
}
debug_assert!(row != usize::MAX, "nu must be mu with a box removed");
let (m, n) = (mu.parts(), nu.parts());
let mut out = Rat::one();
for j in 0..nu.part(row) as usize {
let up = (
crate::macdonald::arm(m, row, j) + 1,
crate::macdonald::leg(m, row, j),
);
let down = (
crate::macdonald::arm(n, row, j) + 1,
crate::macdonald::leg(n, row, j),
);
out.scale_by_ratio(up, down);
}
for i in 0..crate::macdonald::count_above(n, col as usize) {
let up = (
crate::macdonald::arm(m, i, col as usize),
crate::macdonald::leg(m, i, col as usize) + 1,
);
let down = (
crate::macdonald::arm(n, i, col as usize),
crate::macdonald::leg(n, i, col as usize) + 1,
);
out.scale_by_ratio(up, down);
}
out.reduce();
out
}
fn pieri(mu: &Partition, nu: &Partition) -> Rat<i128> {
if mu == nu {
return Rat::one();
}
if !mu.contains(nu) {
return Rat::zero();
}
crate::memo::bh_pieri_cached(&(mu.clone(), nu.clone()), || {
if mu.size() == nu.size() + 1 {
return one_box(mu, nu);
}
let mut acc = Rat::zero();
for alpha in covers_within(nu, mu) {
let outer = pieri(mu, &alpha);
if outer.is_zero() {
continue;
}
let mut term = outer.mul(&one_box(&alpha, nu));
term = term.mul(&Rat::from_poly(bi_exponent(&alpha, nu)));
acc.add_assign(&term);
}
let b = bi_exponent::<i128>(mu, nu);
acc.num = acc
.num
.divide_exact(&b)
.unwrap_or_else(|| panic!("B_{{mu/nu}} must divide the Pieri sum at {mu} / {nu}"));
acc.reduce();
acc
})
}
fn ell(mu: &Partition, nu: &Partition) -> Rat<i128> {
debug_assert_eq!(mu.size(), nu.size());
if nu.len() <= 1 {
return Rat::one();
}
crate::memo::bh_ell_cached(&(mu.clone(), nu.clone()), || {
let hat = Partition::new(nu.parts()[..nu.len() - 1].iter().copied());
let mut acc = Rat::zero();
for gamma in crate::partitions_of(hat.size()) {
if !mu.contains(&gamma) {
continue;
}
let c = pieri(mu, &gamma);
if c.is_zero() {
continue;
}
acc.add_assign(&c.mul(&ell(&gamma, &hat)));
}
acc.reduce();
acc
})
}
fn covers_within(nu: &Partition, mu: &Partition) -> Vec<Partition> {
let mut out = Vec::new();
for i in 0..=nu.len() {
let mut parts: Vec<u32> = nu.parts().to_vec();
if i == parts.len() {
parts.push(1);
} else {
parts[i] += 1;
}
if i > 0 && parts[i] > parts[i - 1] {
continue;
}
let alpha = Partition::new(parts);
if mu.contains(&alpha) {
out.push(alpha);
}
}
out
}
pub fn htilde_monomial_table<C: Ring>(n: u32) -> Vec<(Partition, crate::sym::Monomial<QtPoly<C>>)> {
use crate::sym::SymFn;
monomial_table_i128(n)
.into_iter()
.map(|(mu, m)| {
let mut out = crate::sym::Monomial::zero();
for (nu, p) in m.terms() {
let mut q = QtPoly::zero();
for (&(a, b), c) in p.terms() {
q.add_term(a, b, C::from_i128(*c));
}
out.add_term(nu.clone(), q);
}
(mu, out)
})
.collect()
}
fn monomial_table_i128(n: u32) -> Vec<(Partition, crate::sym::Monomial<QtPoly<i128>>)> {
use crate::sym::SymFn;
let parts = crate::memo::partitions_cached(n);
parts
.iter()
.map(|mu| {
let mut out = crate::sym::Monomial::zero();
for nu in parts.iter() {
let poly = ell(mu, nu)
.into_poly()
.unwrap_or_else(|| panic!("L_{{{mu},{nu}}} must be a polynomial"));
out.add_term(nu.clone(), poly);
}
(mu.clone(), out)
})
.collect()
}
pub fn htilde_table<C: Ring>(n: u32) -> Vec<(Partition, crate::sym::Schur<QtPoly<C>>)> {
use crate::sym::SymFn;
let cached = crate::memo::htilde_cached(n, || htilde_table_uncached::<i128>(n));
cached
.iter()
.map(|(mu, s)| {
let mut out = crate::sym::Schur::zero();
for (lambda, k) in s.terms() {
let mut p = QtPoly::zero();
for (&(a, b), c) in k.terms() {
p.add_term(a, b, C::from_i128(*c));
}
out.add_term(lambda.clone(), p);
}
(mu.clone(), out)
})
.collect()
}
fn htilde_table_uncached<C: Ring>(n: u32) -> Vec<(Partition, crate::sym::Schur<QtPoly<C>>)> {
use crate::convert::ToSchur;
htilde_monomial_table::<C>(n)
.into_iter()
.map(|(mu, m)| (mu, m.to_schur()))
.collect()
}
impl<C: Ring> PartialEq for Rat<C> {
fn eq(&self, other: &Self) -> bool {
self.num == other.num && self.den == other.den
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::sym::SymFn;
#[test]
fn the_recursion_agrees_with_the_branching_route() {
for n in 0..=6u32 {
for (mu, got) in htilde_table::<Rational>(n) {
let want = crate::macdonald_ht::<Rational>(&mu);
for lambda in crate::partitions_of(n) {
assert_eq!(
got.coeff(&lambda),
want.coeff(&lambda),
"K~_{{{lambda},{mu}}}"
);
}
}
}
}
#[test]
fn the_cache_is_transparent() {
use crate::sym::SymFn;
for n in 0..=7u32 {
crate::clear_caches();
let want_r = htilde_table_uncached::<Rational>(n);
crate::clear_caches();
let got_r = htilde_table::<Rational>(n);
assert_eq!(got_r, want_r, "Rational at degree {n}");
crate::clear_caches();
let want_n = htilde_table_uncached::<i64>(n);
crate::clear_caches();
let got_n = htilde_table::<i64>(n);
assert_eq!(got_n, want_n, "i64 at degree {n}");
for ((_, a), (_, b)) in got_n.iter().zip(got_r.iter()) {
for (lambda, k) in a.terms() {
let wide = b.coeff(lambda);
assert!(
k.terms()
.map(|(x, c)| (*x, Rational::from_int(*c as i128)))
.eq(wide.terms().map(|(x, c)| (*x, *c))),
"i64 and Rational disagree at {lambda}"
);
}
}
}
}
#[test]
fn the_coefficients_are_non_negative_integers() {
for n in 0..=6u32 {
for (mu, s) in htilde_table::<Rational>(n) {
for (lambda, k) in s.terms() {
for (_, c) in k.terms() {
assert_eq!(c.denom(), 1, "K~_{{{lambda},{mu}}} has {c:?}");
assert!(c.numer() > 0, "K~_{{{lambda},{mu}}} has {c:?}");
}
}
}
}
}
#[test]
fn the_monomial_coefficients_pair_against_the_kostka_numbers() {
for n in 0..=6u32 {
let parts = crate::partitions_of(n);
let schur = htilde_table::<Rational>(n);
for ((mu, s), (mu2, m)) in schur.iter().zip(htilde_monomial_table::<Rational>(n)) {
assert_eq!(mu, &mu2);
for nu in &parts {
let mut want = QtPoly::zero();
for lambda in &parts {
let k = crate::kostka::kostka(lambda, nu);
if k == 0 {
continue;
}
let scale = QtPoly::term(0, 0, Rational::from_int(k as i128));
want.add_assign(&s.coeff(lambda).mul(&scale));
}
assert_eq!(m.coeff(nu), want, "L_{{{mu},{nu}}}");
}
}
}
}
}