#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::{BTreeMap, HashMap};
use crate::coeff::{QAlgebra, Ring};
use crate::convert::FromSchur;
use crate::frac::Frac;
use crate::partition::Partition;
use crate::sym::{add_at, by_degree, Monomial, PowerSum, Schur, SymFn};
pub fn macdonald_p<C: Ring>(lambda: &Partition) -> Monomial<Frac<C>> {
p_with(lambda, &mut PsiCache::new())
}
pub fn macdonald_p_table<C: Ring>(n: u32) -> Vec<(Partition, Monomial<Frac<C>>)> {
let mut cache = PsiCache::new();
crate::partitions_of(n)
.into_iter()
.map(|lambda| {
let f = p_with(&lambda, &mut cache);
(lambda, f)
})
.collect()
}
type PsiCache = HashMap<(Vec<u32>, Vec<u32>), Factors>;
fn p_with<C: Ring>(lambda: &Partition, cache: &mut PsiCache) -> Monomial<Frac<C>> {
let mut out = Monomial::zero();
if lambda.is_empty() {
out.add_term(Partition::new([]), <Frac<C> as Ring>::one());
return out;
}
let target: Vec<u32> = lambda.parts().to_vec();
let mut acc: Factors = BTreeMap::new();
for mu in crate::partitions_of(lambda.size()) {
crate::interrupt::poll();
let mut total = <Frac<C> as Ring>::zero();
let mut chain: Vec<Vec<u32>> = vec![vec![0; target.len()]];
crate::charge::build(&target, mu.parts(), 0, &mut chain, &mut |ch| {
acc.clear();
for k in 1..ch.len() {
let key = (ch[k].clone(), ch[k - 1].clone());
let f = cache
.entry(key)
.or_insert_with(|| psi_factors(&ch[k], &ch[k - 1]));
for (&e, &m) in f.iter() {
*acc.entry(e).or_insert(0) += m;
}
}
acc.retain(|_, m| *m != 0);
total.add_assign(&Frac::from_factors(&acc));
});
if !total.is_zero() {
total.reduce();
out.add_term(mu, total);
}
}
out
}
pub fn macdonald_q<C: Ring>(lambda: &Partition) -> Monomial<Frac<C>> {
scale(macdonald_p(lambda), &b_factors(lambda.parts()))
}
pub fn macdonald_j<C: Ring>(lambda: &Partition) -> Monomial<Frac<C>> {
scale(macdonald_p(lambda), &c_factors(lambda.parts()))
}
pub fn monomial_to_macdonald_p<C: Ring + Send + Sync + 'static>(
f: &Monomial<Frac<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: HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let table = cached_in_p_table::<C>(n);
for (mu, c) in terms {
crate::interrupt::poll();
for (lambda, v) in &table[index[mu]] {
add_at(&mut out, lambda, v.mul(c));
}
}
}
for v in out.values_mut() {
v.reduce();
}
out
}
pub fn monomial_to_macdonald_q<C: Ring + Send + Sync + 'static>(
f: &Monomial<Frac<C>>,
) -> BTreeMap<Partition, Frac<C>> {
let mut out = monomial_to_macdonald_p(f);
for (lambda, v) in &mut out {
let mut over_b = b_factors(lambda.parts());
for m in over_b.values_mut() {
*m = -*m;
}
*v = v.mul_factors(&over_b);
v.reduce();
}
out
}
fn cached_in_p_table<C: Ring + Send + Sync + 'static>(
n: u32,
) -> std::sync::Arc<Vec<BTreeMap<Partition, Frac<C>>>> {
crate::memo::mac_p_inverse_cached(n, || monomial_in_p_table::<C>(n))
}
fn monomial_in_p_table<C: Ring>(n: u32) -> Vec<BTreeMap<Partition, Frac<C>>> {
let parts = crate::memo::partitions_cached(n);
let table = macdonald_p_table::<C>(n);
let mut out: Vec<BTreeMap<Partition, Frac<C>>> = vec![BTreeMap::new(); parts.len()];
for j in (0..parts.len()).rev() {
crate::interrupt::poll();
let mut acc = BTreeMap::new();
acc.insert(parts[j].clone(), <Frac<C> as Ring>::one());
for l in (j + 1)..parts.len() {
let c = table[j].1.coeff(&parts[l]);
if c.is_zero() {
continue;
}
for (nu, v) in &out[l] {
add_at(&mut acc, nu, c.mul(v).neg());
}
}
for v in acc.values_mut() {
v.reduce();
}
out[j] = acc;
}
out
}
pub fn macdonald_element_add<C: Ring>(
f: &BTreeMap<Partition, Frac<C>>,
g: &BTreeMap<Partition, Frac<C>>,
) -> BTreeMap<Partition, Frac<C>> {
let mut out = f.clone();
for (mu, c) in g {
add_at(&mut out, mu, c.clone());
}
for v in out.values_mut() {
v.reduce();
}
out.retain(|_, v| !v.is_zero());
out
}
pub fn macdonald_element_scale<C: Ring>(
f: &BTreeMap<Partition, Frac<C>>,
c: &Frac<C>,
) -> BTreeMap<Partition, Frac<C>> {
let mut out = BTreeMap::new();
for (mu, v) in f {
let mut w = v.mul(c);
w.reduce();
if !w.is_zero() {
out.insert(mu.clone(), w);
}
}
out
}
fn expand_mac<C: Ring>(
f: &BTreeMap<Partition, Frac<C>>,
one: fn(&Partition) -> Monomial<Frac<C>>,
) -> Monomial<Frac<C>> {
let mut acc: BTreeMap<Partition, Frac<C>> = BTreeMap::new();
for (lambda, c) in f {
crate::interrupt::poll();
for (mu, v) in one(lambda).terms() {
add_at(&mut acc, mu, v.mul(c));
}
}
let mut out = Monomial::zero();
for (mu, mut v) in acc {
v.reduce();
out.add_term(mu, v);
}
out
}
pub fn macdonald_p_to_monomial<C: Ring>(f: &BTreeMap<Partition, Frac<C>>) -> Monomial<Frac<C>> {
expand_mac(f, macdonald_p::<C>)
}
pub fn macdonald_q_to_monomial<C: Ring>(f: &BTreeMap<Partition, Frac<C>>) -> Monomial<Frac<C>> {
expand_mac(f, macdonald_q::<C>)
}
pub fn macdonald_j_to_monomial<C: Ring>(f: &BTreeMap<Partition, Frac<C>>) -> Monomial<Frac<C>> {
expand_mac(f, macdonald_j::<C>)
}
pub fn powersum_scalar_qt<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 = Factors::new();
for &part in mu.parts() {
*factors.entry((part, 0)).or_insert(0) += 1;
*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_qt<C: QAlgebra>(f: &Schur<Frac<C>>, g: &Schur<Frac<C>>) -> Frac<C> {
powersum_scalar_qt(&PowerSum::from_schur(f), &PowerSum::from_schur(g))
}
fn scale<C: Ring>(f: Monomial<Frac<C>>, by: &Factors) -> Monomial<Frac<C>> {
let mut out = Monomial::zero();
for (mu, c) in f.terms() {
crate::interrupt::poll();
let mut v = c.mul_factors(by);
v.reduce();
out.add_term(mu.clone(), v);
}
out
}
fn b_factors(lambda: &[u32]) -> Factors {
let mut f = Factors::new();
for_each_cell(lambda, &mut |a, l| {
*f.entry((a, l + 1)).or_insert(0) += 1;
*f.entry((a + 1, l)).or_insert(0) -= 1;
});
f.retain(|_, m| *m != 0);
f
}
pub(crate) fn c_factors(lambda: &[u32]) -> Factors {
let mut f = Factors::new();
for_each_cell(lambda, &mut |a, l| {
*f.entry((a, l + 1)).or_insert(0) += 1;
});
f.retain(|_, m| *m != 0);
f
}
pub(crate) fn c_prime_factors(lambda: &[u32]) -> BTreeMap<(u32, u32), u32> {
let mut f = BTreeMap::new();
for_each_cell(lambda, &mut |a, l| {
*f.entry((a + 1, l)).or_insert(0) += 1;
});
f
}
fn for_each_cell(lambda: &[u32], visit: &mut impl FnMut(u32, u32)) {
for i in 0..lambda.len() {
for j in 0..lambda[i] as usize {
visit(arm(lambda, i, j), leg(lambda, i, j));
}
}
}
type Factors = BTreeMap<(u32, u32), i32>;
fn psi_factors(lam: &[u32], mu: &[u32]) -> Factors {
let width = lam.iter().copied().max().unwrap_or(0) as usize;
let met: Vec<bool> = (0..width)
.map(|j| count_above(lam, j) > count_above(mu, j))
.collect();
let mut f = Factors::new();
for i in 0..mu.len() {
if lam[i] == mu[i] {
continue; }
for j in 0..mu[i] as usize {
if met[j] {
continue; }
let (am, lm) = (arm(mu, i, j), leg(mu, i, j));
let (al, ll) = (arm(lam, i, j), leg(lam, i, j));
*f.entry((am, lm + 1)).or_insert(0) += 1;
*f.entry((am + 1, lm)).or_insert(0) -= 1;
*f.entry((al + 1, ll)).or_insert(0) += 1;
*f.entry((al, ll + 1)).or_insert(0) -= 1;
}
}
f.retain(|_, m| *m != 0);
f
}
pub(crate) fn arm(shape: &[u32], i: usize, j: usize) -> u32 {
shape[i] - j as u32 - 1
}
pub(crate) fn leg(shape: &[u32], i: usize, j: usize) -> u32 {
count_above(shape, j) as u32 - 1 - i as u32
}
pub(crate) fn count_above(shape: &[u32], j: usize) -> usize {
shape.iter().filter(|&&v| v as usize > j).count()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::convert::ToSchur;
use crate::qt::QtPoly;
type F = Frac<Rational>;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn r(n: i128) -> Rational {
Rational::from_int(n)
}
#[test]
fn p_and_q_are_dual_under_scalar_qt() {
for n in 1..=4u32 {
for la in crate::partitions_of(n) {
let p = macdonald_p::<Rational>(&la).to_schur();
for mu in crate::partitions_of(n) {
let q = macdonald_q::<Rational>(&mu).to_schur();
let got = scalar_qt(&p, &q);
if la == mu {
assert_eq!(got, <F as Ring>::one(), "⟨P_{la}, Q_{la}⟩_qt");
} else {
assert!(got.is_zero(), "⟨P_{la}, Q_{mu}⟩_qt must vanish");
}
}
}
}
}
#[test]
fn j_norm_under_scalar_qt_is_c_times_c_prime() {
for n in 1..=4u32 {
for la in crate::partitions_of(n) {
let j = macdonald_j::<Rational>(&la).to_schur();
let mut hooks = c_factors(la.parts());
for (&(a, b), &m) in &c_prime_factors(la.parts()) {
*hooks.entry((a, b)).or_insert(0) += m as i32;
}
assert_eq!(
scalar_qt(&j, &j),
F::from_factors(&hooks),
"⟨J_{la}, J_{la}⟩_qt"
);
}
}
}
#[test]
fn p_of_two_matches_the_hand_computation() {
let p: Monomial<F> = macdonald_p(&part(&[2]));
assert_eq!(p.coeff(&part(&[2])), <F as Ring>::one(), "monic in m_λ");
let c = p.coeff(&part(&[1, 1]));
let mut one_plus_q: QtPoly<Rational> = <QtPoly<Rational> as Ring>::one();
one_plus_q.add_term(1, 0, r(1));
let want = F::factor(0, 1) .mul(&F::from_poly(one_plus_q))
.mul(&F::inv_factor(1, 1)); assert_eq!(c, want, "got {c}, want {want}");
}
#[test]
fn at_q_equals_t_it_is_the_schur_function() {
use crate::convert::FromSchur;
for n in 0..=6u32 {
for lambda in crate::partitions_of(n) {
let p: Monomial<F> = macdonald_p(&lambda);
let s: Monomial<Rational> =
Monomial::from_schur(&crate::Schur::monomial(lambda.clone(), r(1)));
for (mu, c) in p.terms() {
let got = c.eval(&r(2), &r(2)).expect("no pole at q = t = 2");
assert_eq!(got, s.coeff(mu), "P_{lambda} at q=t, term {mu}");
}
for (mu, want) in s.terms() {
if p.coeff(mu) == <F as Ring>::zero() {
assert!(want.is_zero(), "missing term {mu} of s_{lambda}");
}
}
}
}
}
#[test]
fn at_t_equals_one_it_is_the_monomial() {
for n in 0..=6u32 {
for lambda in crate::partitions_of(n) {
let p: Monomial<F> = macdonald_p(&lambda);
for (mu, c) in p.terms() {
let got = c.eval(&r(3), &r(1)).expect("no pole at q = 3, t = 1");
assert_eq!(
got,
Rational::from_int(i128::from(mu == &lambda)),
"P_{lambda} at t = 1, term {mu}"
);
}
}
}
}
#[test]
fn at_q_zero_it_is_hall_littlewood_p() {
use crate::convert::FromSchur;
use crate::qt::QtPoly;
for n in 0..=6u32 {
for lambda in crate::partitions_of(n) {
let mac: Monomial<F> = macdonald_p(&lambda);
let hl: crate::Schur<QtPoly<Rational>> = crate::hall_littlewood_p(&lambda);
let hl: Monomial<QtPoly<Rational>> = Monomial::from_schur(&hl);
for &tv in &[2i128, 3, 5] {
let t = r(tv);
for (mu, c) in mac.terms() {
let got = c.eval(&r(0), &t).expect("q = 0 is not a pole");
assert_eq!(
got,
hl.coeff(mu).eval(&Rational::from_int(0), &t),
"P_{lambda} at q=0, t={tv}, term {mu}"
);
}
for (mu, c) in hl.terms() {
if mac.coeff(mu) == <F as Ring>::zero() {
assert!(
c.eval(&Rational::from_int(0), &t).is_zero(),
"Hall–Littlewood has {mu} where Macdonald does not"
);
}
}
}
}
}
}
#[test]
fn q_and_j_are_scalar_multiples_of_p() {
for n in 0..=5u32 {
for lambda in crate::partitions_of(n) {
let p: Monomial<F> = macdonald_p(&lambda);
let q: Monomial<F> = macdonald_q(&lambda);
let j: Monomial<F> = macdonald_j(&lambda);
let b = q.coeff(&lambda);
let c = j.coeff(&lambda);
for (mu, pc) in p.terms() {
assert_eq!(q.coeff(mu), pc.mul(&b), "Q at {mu}");
assert_eq!(j.coeff(mu), pc.mul(&c), "J at {mu}");
}
for (mu, jc) in j.terms() {
let (_, den) = jc.parts();
assert_eq!(den.count(), 0, "J_{lambda} coefficient at {mu} is {jc}");
}
}
}
}
#[test]
fn every_macdonald_polynomial_comes_back_as_itself() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let unit: BTreeMap<Partition, F> =
[(lambda.clone(), <F as Ring>::one())].into_iter().collect();
let p: Monomial<F> = macdonald_p(&lambda);
assert_eq!(monomial_to_macdonald_p(&p), unit, "m -> P of P_{lambda}");
let q: Monomial<F> = macdonald_q(&lambda);
assert_eq!(monomial_to_macdonald_q(&q), unit, "m -> Q of Q_{lambda}");
}
}
}
#[test]
fn adding_and_scaling_commute_with_expanding() {
let a = part(&[2, 1]);
let b = part(&[1, 1, 1]);
let one = <F as Ring>::one();
let f: BTreeMap<Partition, F> = [(a.clone(), one.clone())].into_iter().collect();
let g: BTreeMap<Partition, F> = [(b.clone(), one.clone())].into_iter().collect();
let mut want: Monomial<F> = macdonald_p_to_monomial(&f);
for (mu, c) in macdonald_p_to_monomial(&g).terms() {
want.add_term(mu.clone(), c.clone());
}
assert_eq!(
macdonald_p_to_monomial(&macdonald_element_add(&f, &g)),
want,
"P_{a} + P_{b}"
);
let c = F::inv_factor(1, 1);
let mut scaled: Monomial<F> = Monomial::zero();
for (mu, v) in macdonald_p_to_monomial(&f).terms() {
let mut w = v.mul(&c);
w.reduce();
scaled.add_term(mu.clone(), w);
}
assert_eq!(
macdonald_p_to_monomial(&macdonald_element_scale(&f, &c)),
scaled,
"P_{a}/(1 - q t)"
);
}
#[test]
fn every_monomial_comes_back_as_itself() {
for n in 0..=7u32 {
for mu in crate::partitions_of(n) {
let f: Monomial<F> = Monomial::monomial(mu.clone(), <F as Ring>::one());
assert_eq!(
macdonald_p_to_monomial(&monomial_to_macdonald_p(&f)),
f,
"P at m_{mu}"
);
assert_eq!(
macdonald_q_to_monomial(&monomial_to_macdonald_q(&f)),
f,
"Q at m_{mu}"
);
}
}
}
#[test]
fn expanding_j_gives_a_multiple_of_p() {
for n in 0..=6u32 {
for lambda in crate::partitions_of(n) {
let unit: BTreeMap<Partition, F> =
[(lambda.clone(), <F as Ring>::one())].into_iter().collect();
let in_p = monomial_to_macdonald_p(&macdonald_j_to_monomial(&unit));
assert_eq!(in_p.len(), 1, "J_{lambda} written in P");
assert!(in_p.contains_key(&lambda), "J_{lambda} written in P");
}
}
}
#[test]
fn m2_and_m11_in_p_and_q_are_the_hand_values() {
let one = <F as Ring>::one();
let m2: Monomial<F> = Monomial::monomial(part(&[2]), one.clone());
let m11: Monomial<F> = Monomial::monomial(part(&[1, 1]), one.clone());
let mut one_plus_q: QtPoly<Rational> = <QtPoly<Rational> as Ring>::one();
one_plus_q.add_term(1, 0, r(1));
let psi = F::factor(0, 1)
.mul(&F::from_poly(one_plus_q))
.mul(&F::inv_factor(1, 1));
let in_p = monomial_to_macdonald_p(&m2);
assert_eq!(in_p[&part(&[2])], one, "m_2 is monic in P_2");
assert_eq!(in_p[&part(&[1, 1])], psi.neg(), "m_2 in P_11");
assert_eq!(
monomial_to_macdonald_p(&m11),
[(part(&[1, 1]), one.clone())].into_iter().collect(),
"m_11 = P_11"
);
let over_b = F::factor(1, 1)
.mul(&F::factor(1, 0))
.mul(&F::inv_factor(0, 2))
.mul(&F::inv_factor(0, 1));
let in_q = monomial_to_macdonald_q(&m11);
assert_eq!(in_q.len(), 1, "m_11 reaches Q_11 alone");
assert_eq!(in_q[&part(&[1, 1])], over_b, "m_11 in Q_11");
}
#[test]
fn the_cached_table_is_the_computed_table_for_each_ring() {
use crate::guard::GuardedRat;
for n in 0..=4u32 {
let want = monomial_in_p_table::<Rational>(n);
crate::clear_caches();
assert_eq!(*cached_in_p_table::<Rational>(n), want, "cold at {n}");
assert_eq!(*cached_in_p_table::<Rational>(n), want, "warm at {n}");
let wide = monomial_in_p_table::<GuardedRat>(n);
assert_eq!(
*cached_in_p_table::<GuardedRat>(n),
wide,
"a second ring read the first ring's entry at degree {n}"
);
}
crate::clear_caches();
}
#[test]
fn the_expansions_are_linear_and_take_mixed_degrees() {
let two = F::from_poly(QtPoly::term(0, 0, r(2)));
let three = F::from_poly(QtPoly::term(0, 0, r(3)));
let mut f: Monomial<F> = Monomial::zero();
f.add_term(part(&[1]), <F as Ring>::one());
f.add_term(part(&[2]), two.clone());
f.add_term(part(&[1, 1]), three.clone());
for (name, to_basis) in [
(
"m -> P",
monomial_to_macdonald_p as fn(&Monomial<F>) -> BTreeMap<Partition, F>,
),
("m -> Q", monomial_to_macdonald_q),
] {
let mut want: BTreeMap<Partition, F> = BTreeMap::new();
for (mu, scalar) in [
(part(&[1]), <F as Ring>::one()),
(part(&[2]), two.clone()),
(part(&[1, 1]), three.clone()),
] {
let piece = to_basis(&Monomial::monomial(mu, <F as Ring>::one()));
for (lambda, c) in piece {
crate::sym::add_at(&mut want, &lambda, c.mul(&scalar));
}
}
for v in want.values_mut() {
v.reduce();
}
let mut got = to_basis(&f);
for v in got.values_mut() {
v.reduce();
}
assert_eq!(got, want, "{name} is linear across three degrees");
assert!(to_basis(&Monomial::zero()).is_empty(), "{name} of 0");
}
}
#[test]
fn expansion_is_unitriangular_in_dominance() {
for n in 0..=7u32 {
for lambda in crate::partitions_of(n) {
let p: Monomial<F> = macdonald_p(&lambda);
assert_eq!(p.coeff(&lambda), <F as Ring>::one(), "monic at {lambda}");
for mu in p.terms().keys() {
assert!(
crate::kostka::kostka(&lambda, mu) > 0,
"{mu} appears in P_{lambda} but λ does not dominate it"
);
}
}
}
}
}