#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::coeff::Ring;
use crate::convert::ToSchur;
use crate::fasthash::Map;
use crate::partition::Partition;
use crate::sym::{Elementary, Forgotten, Homogeneous, Monomial, PowerSum, Schur, SymFn};
fn powers<C: Ring>(x: &C, upto: u32) -> Vec<C> {
let mut out = Vec::with_capacity(upto as usize + 1);
out.push(C::one());
for k in 1..=upto as usize {
crate::interrupt::poll();
out.push(out[k - 1].mul(x));
}
out
}
impl<C: Ring> PowerSum<C> {
pub fn eval(&self, xs: &[C]) -> C {
if self.is_zero() {
return C::zero();
}
let top = self.terms().keys().map(|l| l.part(0)).max().unwrap_or(0);
let pk: Vec<C> = {
let mut acc = vec![C::zero(); top as usize + 1];
for x in xs {
for (k, p) in powers(x, top).into_iter().enumerate() {
acc[k].add_assign(&p);
}
}
acc
};
let mut total = C::zero();
for (lambda, c) in self.terms() {
let mut term = c.clone();
for &part in lambda.parts() {
term = term.mul(&pk[part as usize]);
}
total.add_assign(&term);
}
total
}
}
fn elementary_of<C: Ring>(xs: &[C], upto: u32) -> Vec<C> {
let mut e = vec![C::zero(); upto as usize + 1];
e[0] = C::one();
for x in xs {
for k in (1..=upto as usize).rev() {
let add = e[k - 1].mul(x);
e[k].add_assign(&add);
}
}
e
}
fn homogeneous_of<C: Ring>(xs: &[C], upto: u32) -> Vec<C> {
let mut h = vec![C::zero(); upto as usize + 1];
h[0] = C::one();
for x in xs {
for k in 1..=upto as usize {
let add = h[k - 1].mul(x);
h[k].add_assign(&add);
}
}
h
}
fn eval_multiplicative<C: Ring, S: SymFn<C>>(f: &S, gens: &[C]) -> C {
let mut total = C::zero();
for (lambda, c) in f.terms() {
crate::interrupt::poll();
let mut term = c.clone();
for &part in lambda.parts() {
term = term.mul(&gens[part as usize]);
}
total.add_assign(&term);
}
total
}
impl<C: Ring> Elementary<C> {
pub fn eval(&self, xs: &[C]) -> C {
if self.is_zero() {
return C::zero();
}
let top = self.terms().keys().map(|l| l.part(0)).max().unwrap_or(0);
eval_multiplicative(self, &elementary_of(xs, top))
}
}
impl<C: Ring> Homogeneous<C> {
pub fn eval(&self, xs: &[C]) -> C {
if self.is_zero() {
return C::zero();
}
let top = self.terms().keys().map(|l| l.part(0)).max().unwrap_or(0);
eval_multiplicative(self, &homogeneous_of(xs, top))
}
}
impl<C: Ring> Monomial<C> {
pub fn eval(&self, xs: &[C]) -> C {
let mut total = C::zero();
for (lambda, c) in self.terms() {
if lambda.len() > xs.len() {
continue; }
let pows: Vec<Vec<C>> = xs.iter().map(|x| powers(x, lambda.part(0))).collect();
let mut avail = multiplicities(lambda);
let mut acc = C::zero();
rearrange(&pows, 0, &mut avail, lambda.len(), &C::one(), &mut acc);
total.add_assign(&c.mul(&acc));
}
total
}
}
fn rearrange<C: Ring>(
pows: &[Vec<C>],
slot: usize,
avail: &mut [(u32, u32)],
left: usize,
run: &C,
acc: &mut C,
) {
if left == 0 {
acc.add_assign(run);
return;
}
if pows.len() - slot < left {
return;
}
rearrange(pows, slot + 1, avail, left, run, acc);
for i in 0..avail.len() {
if avail[i].1 == 0 {
continue;
}
avail[i].1 -= 1;
let next = run.mul(&pows[slot][avail[i].0 as usize]);
rearrange(pows, slot + 1, avail, left - 1, &next, acc);
avail[i].1 += 1;
}
}
pub(crate) fn for_each_rearrangement(lambda: &Partition, n: usize, emit: &mut impl FnMut(&[u32])) {
if lambda.len() > n {
return;
}
let mut avail = multiplicities(lambda);
let mut slots = vec![0u32; n];
place(&mut slots, 0, &mut avail, lambda.len(), emit);
}
pub(crate) fn multiplicities(lambda: &Partition) -> Vec<(u32, u32)> {
let mut out: Vec<(u32, u32)> = Vec::new();
for &k in lambda.parts() {
match out.last_mut() {
Some((v, m)) if *v == k => *m += 1,
_ => out.push((k, 1)),
}
}
out
}
fn place(
slots: &mut [u32],
slot: usize,
avail: &mut [(u32, u32)],
left: usize,
emit: &mut impl FnMut(&[u32]),
) {
if left == 0 {
emit(slots);
return;
}
if slots.len() - slot < left {
return;
}
for i in 0..avail.len() {
if avail[i].1 == 0 {
continue;
}
avail[i].1 -= 1;
slots[slot] = avail[i].0;
place(slots, slot + 1, avail, left - 1, emit);
avail[i].1 += 1;
}
slots[slot] = 0;
place(slots, slot + 1, avail, left, emit);
}
impl<C: Ring> Monomial<C> {
pub fn expand(&self, n: usize) -> Vec<(Vec<u32>, C)> {
let mut out = Vec::new();
for (lambda, c) in self.terms() {
for_each_rearrangement(lambda, n, &mut |alpha| {
out.push((alpha.to_vec(), c.clone()))
});
}
out
}
}
impl<C: Ring> Schur<C> {
pub fn eval(&self, xs: &[C]) -> C {
let mut total = C::zero();
for (lambda, c) in self.terms() {
let v = eval_schur_at(lambda, xs);
if !v.is_zero() {
total.add_assign(&c.mul(&v));
}
}
total
}
}
fn eval_schur_at<C: Ring>(lambda: &Partition, xs: &[C]) -> C {
let l = lambda.len();
if l == 0 {
return C::one();
}
if l > xs.len() {
return C::zero();
}
let lam: Vec<u32> = lambda.parts().to_vec();
let n = xs.len();
let mut cur: Map<Vec<u32>, C> = Map::default();
cur.insert(vec![0u32; l], C::one());
let mut scratch = vec![0u32; l];
for (step, x) in xs.iter().enumerate() {
let pw = powers(x, lambda.size());
let remaining = n - step - 1;
let mut next: Map<Vec<u32>, C> = Map::default();
for (mu, c) in cur.drain() {
grow_strip(&lam, &mu, 0, u32::MAX, &mut scratch, 0, &mut |nu, added| {
if !reachable(&lam, nu, remaining) {
return;
}
let v = c.mul(&pw[added as usize]);
if v.is_zero() {
return;
}
match next.get_mut(nu) {
Some(e) => e.add_assign(&v),
None => {
next.insert(nu.to_vec(), v);
}
}
});
}
cur = next;
}
cur.remove(&lam).unwrap_or_else(C::zero)
}
fn reachable(lam: &[u32], nu: &[u32], k: usize) -> bool {
for j in 0..lam.len() {
let need = if j + k < lam.len() { lam[j + k] } else { 0 };
if nu[j] < need {
return false;
}
}
true
}
fn grow_strip(
lam: &[u32],
mu: &[u32],
i: usize,
prev: u32,
cur: &mut Vec<u32>,
added: u32,
emit: &mut impl FnMut(&[u32], u32),
) {
if i == lam.len() {
emit(cur, added);
return;
}
let hi = prev.min(lam[i]);
for v in mu[i]..=hi {
cur[i] = v;
grow_strip(lam, mu, i + 1, mu[i], cur, added + (v - mu[i]), emit);
}
}
impl<C: Ring> Forgotten<C> {
pub fn eval(&self, xs: &[C]) -> C {
self.to_schur().eval(xs)
}
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn hooks(lambda: &Partition) -> Vec<u32> {
let conj = lambda.conjugate();
let mut out = Vec::with_capacity(lambda.size() as usize);
for (i, &row) in lambda.parts().iter().enumerate() {
for j in 0..row as usize {
out.push((row - j as u32) + (conj.part(j) - i as u32) - 1);
}
}
out
}
pub fn dimension(lambda: &Partition) -> Option<u128> {
let n = lambda.size();
if n == 0 {
return Some(1);
}
let mut hs = hooks(lambda);
hs.sort_unstable_by(|a, b| b.cmp(a));
let mut acc: u128 = 1;
for k in 1..=u128::from(n) {
acc = acc.checked_mul(k)?;
for h in hs.iter_mut() {
if *h != 0 && acc.is_multiple_of(u128::from(*h)) {
acc /= u128::from(*h);
*h = 0;
}
}
}
for h in hs {
if h != 0 {
acc /= u128::from(h);
}
}
Some(acc)
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
pub fn principal_specialization(lambda: &Partition, n: u32) -> Option<u128> {
if lambda.len() as u32 > n {
return Some(0);
}
let mut hs = hooks(lambda);
hs.sort_unstable_by(|a, b| b.cmp(a));
let mut acc: u128 = 1;
for (i, &row) in lambda.parts().iter().enumerate() {
for j in 0..row as usize {
let f = u128::from(n) + j as u128 - i as u128;
acc = acc.checked_mul(f)?;
for h in hs.iter_mut() {
if *h != 0 && acc.is_multiple_of(u128::from(*h)) {
acc /= u128::from(*h);
*h = 0;
}
}
}
}
for h in hs {
if h != 0 {
acc /= u128::from(h);
}
}
Some(acc)
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
pub fn principal_specialization_q(lambda: &Partition, n: u32) -> Option<Vec<i128>> {
if lambda.len() as u32 > n {
return Some(Vec::new());
}
if lambda.is_empty() {
return Some(vec![1]);
}
let mut num = vec![1i128];
for (i, &row) in lambda.parts().iter().enumerate() {
for j in 0..row as usize {
let a = (n as i64 + j as i64 - i as i64) as usize;
num = mul_one_minus_q(&num, a)?;
}
}
let mut den = vec![1i128];
for h in hooks(lambda) {
den = mul_one_minus_q(&den, h as usize)?;
}
let qdeg = (num.len() - 1) - (den.len() - 1);
let mut q = vec![0i128; qdeg + 1];
for k in 0..=qdeg {
let mut v = *num.get(k).unwrap_or(&0);
for (j, d) in den.iter().enumerate().skip(1) {
if j > k {
break;
}
v = v.checked_sub(d.checked_mul(q[k - j])?)?;
}
q[k] = v; }
let shift: usize = lambda
.parts()
.iter()
.enumerate()
.map(|(i, &r)| i * r as usize)
.sum();
let mut out = vec![0i128; shift];
out.extend_from_slice(&q);
Some(out)
}
fn mul_one_minus_q(p: &[i128], a: usize) -> Option<Vec<i128>> {
let mut out = vec![0i128; p.len() + a];
out[..p.len()].copy_from_slice(p);
for (i, c) in p.iter().enumerate() {
out[i + a] = out[i + a].checked_sub(*c)?;
}
Some(out)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::convert::FromSchur;
use crate::memo::partitions_cached;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn ints(v: &[i64]) -> Vec<i64> {
v.to_vec()
}
#[test]
fn all_bases_agree_at_the_same_alphabet() {
let xs = ints(&[2, -1, 3, 1, -2]);
for n in 0..=6u32 {
for lambda in partitions_cached(n).iter() {
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let want = s.eval(&xs);
let m: Monomial<i64> = Monomial::from_schur(&s);
assert_eq!(m.eval(&xs), want, "m for {lambda}");
let e: Elementary<i64> = Elementary::from_schur(&s);
assert_eq!(e.eval(&xs), want, "e for {lambda}");
let h: Homogeneous<i64> = Homogeneous::from_schur(&s);
assert_eq!(h.eval(&xs), want, "h for {lambda}");
let f: Forgotten<i64> = Forgotten::from_schur(&s);
assert_eq!(f.eval(&xs), want, "f for {lambda}");
let sr: Schur<Rational> = Schur::monomial(lambda.clone(), Rational::from_int(1));
let p: PowerSum<Rational> = PowerSum::from_schur(&sr);
let xr: Vec<Rational> = xs.iter().map(|&v| Rational::from_int(v.into())).collect();
assert_eq!(
p.eval(&xr),
Rational::from_int(want.into()),
"p for {lambda}"
);
}
}
}
#[test]
fn expansion_summed_at_an_alphabet_is_evaluation() {
let xs = ints(&[2, -1, 3, 1, -2]);
for n in 0..=6u32 {
for lambda in partitions_cached(n).iter() {
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let m: Monomial<i64> = Monomial::from_schur(&s);
let mut total = 0i64;
for (alpha, c) in m.expand(xs.len()) {
let mut term = c;
for (x, &k) in xs.iter().zip(alpha.iter()) {
term *= x.pow(k);
}
total += term;
}
assert_eq!(total, s.eval(&xs), "expand vs eval for {lambda}");
}
}
}
#[test]
fn expansion_is_in_normal_form() {
for deg in 0..=6u32 {
for n in 0..=5usize {
let mut m: Monomial<i64> = Monomial::zero();
for (i, lambda) in partitions_cached(deg).iter().enumerate() {
m.add_term(lambda.clone(), i as i64 + 1);
}
let mut seen = std::collections::HashSet::new();
for (alpha, c) in m.expand(n) {
assert_eq!(alpha.len(), n, "width at degree {deg}");
assert_eq!(alpha.iter().sum::<u32>(), deg, "{alpha:?}");
assert!(!c.is_zero());
assert!(seen.insert(alpha.clone()), "{alpha:?} twice");
}
}
}
}
#[test]
fn expansion_vanishes_below_the_row_count_and_keeps_the_constant() {
let m21: Monomial<i64> = Monomial::monomial(part(&[2, 1]), 1);
assert!(m21.expand(1).is_empty());
assert_eq!(m21.expand(2), vec![(vec![2, 1], 1), (vec![1, 2], 1)]);
let one: Monomial<i64> = Monomial::monomial(part(&[]), 1);
assert_eq!(one.expand(0), vec![(vec![], 1)]);
assert_eq!(one.expand(3), vec![(vec![0, 0, 0], 1)]);
}
#[test]
fn repeated_and_zero_alphabet_entries_are_fine() {
let xs = ints(&[2, 2, 2, 0, 5]);
for n in 0..=6u32 {
for lambda in partitions_cached(n).iter() {
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let h: Homogeneous<i64> = Homogeneous::from_schur(&s);
assert_eq!(s.eval(&xs), h.eval(&xs), "{lambda}");
}
}
}
#[test]
fn vanishing_below_the_row_count() {
let xs = ints(&[3, 1, 4]);
for n in 0..=7u32 {
for lambda in partitions_cached(n).iter() {
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
if lambda.len() > xs.len() {
assert_eq!(s.eval(&xs), 0, "s_{lambda} in 3 variables");
}
}
}
let e4: Elementary<i64> = Elementary::monomial(part(&[4]), 1);
assert_eq!(e4.eval(&xs), 0);
}
#[test]
fn evaluation_at_ones_matches_the_content_formula() {
for deg in 1..=8u32 {
for lambda in partitions_cached(deg).iter() {
for n in 0..=6usize {
let ones = vec![1i64; n];
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let want = principal_specialization(lambda, n as u32).unwrap();
assert_eq!(s.eval(&ones) as u128, want, "s_{lambda}(1^{n})");
}
}
}
}
#[test]
fn q_specialization_matches_evaluation_and_collapses_at_one() {
for deg in 1..=7u32 {
for lambda in partitions_cached(deg).iter() {
for n in 0..=5usize {
let coeffs = principal_specialization_q(lambda, n as u32)
.expect("degree 7 is far below the i128 wall");
let at_one: i128 = coeffs.iter().sum();
assert_eq!(
at_one as u128,
principal_specialization(lambda, n as u32).unwrap(),
"q=1 for {lambda}, n={n}"
);
let alphabet: Vec<i64> = (0..n).map(|k| 1i64 << k).collect();
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let direct = s.eval(&alphabet) as i128;
let from_poly: i128 = coeffs.iter().enumerate().map(|(k, c)| c << k).sum();
assert_eq!(from_poly, direct, "q=2 for {lambda}, n={n}");
}
}
}
}
#[test]
fn q_specialization_coefficients_are_non_negative() {
for deg in 1..=8u32 {
for lambda in partitions_cached(deg).iter() {
for n in 0..=5u32 {
let coeffs = principal_specialization_q(lambda, n)
.expect("degree 8 is far below the i128 wall");
for (k, c) in coeffs.iter().enumerate() {
assert!(*c >= 0, "q^{k} of s_{lambda}(1,q,..q^{n}) is {c}");
}
}
}
}
}
#[test]
fn dimension_matches_the_kostka_count() {
for deg in 1..=10u32 {
for lambda in partitions_cached(deg).iter() {
let ones = Partition::new(std::iter::repeat_n(1, deg as usize));
assert_eq!(
dimension(lambda).unwrap(),
crate::kostka::kostka(lambda, &ones),
"dim {lambda}"
);
}
}
}
#[test]
fn dimensions_square_sum_to_the_factorial() {
for n in 0..=12u32 {
let total: u128 = partitions_cached(n)
.iter()
.map(|l| {
let d = dimension(l).unwrap();
d * d
})
.sum();
let factorial: u128 = (1..=u128::from(n)).product();
assert_eq!(total, factorial, "n = {n}");
}
}
#[test]
fn dimension_survives_past_the_factorial_ceiling() {
let lam = part(&[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);
assert_eq!(lam.size(), 55);
assert_eq!(
dimension(&lam),
Some(44_261_486_084_874_072_183_645_699_204_710_400)
);
}
}