#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::{Plethystic, QAlgebra, Ring};
use crate::convert::FromSchur;
use crate::partition::Partition;
use crate::qt::QtPoly;
use crate::sym::{by_degree, PowerSum, Schur, SymFn};
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
pub enum Atom {
Unit(u32, u32),
Diff(u32, u32),
}
impl Atom {
pub fn unit(a: u32, b: u32) -> Self {
assert!(a > 0 || b > 0, "1 - q^0 t^0 is zero");
Atom::Unit(a, b)
}
pub fn diff(a: u32, b: u32) -> (Self, bool) {
assert!(a > 0 || b > 0, "q^0 - t^0 is zero");
if a == 0 {
(Atom::Unit(0, b), false)
} else if b == 0 {
(Atom::Unit(a, 0), true)
} else {
(Atom::Diff(a, b), false)
}
}
pub fn poly<C: Ring>(self) -> QtPoly<C> {
match self {
Atom::Unit(a, b) => {
let mut p = <QtPoly<C> as Ring>::one();
p.add_term(a, b, C::one().neg());
p
}
Atom::Diff(a, b) => {
let mut p = QtPoly::term(a, 0, C::one());
p.add_term(0, b, C::one().neg());
p
}
}
}
fn mul_into<C: Ring>(self, n: &QtPoly<C>) -> QtPoly<C> {
match self {
Atom::Unit(a, b) => n.mul_binomial(a, b),
Atom::Diff(a, b) => n.mul_diff(a, b),
}
}
fn divide<C: Ring>(self, n: &QtPoly<C>) -> Option<QtPoly<C>> {
match self {
Atom::Unit(a, b) => crate::frac::divide_by_factor(n, a, b),
Atom::Diff(a, b) => {
if !crate::frac::diff_may_divide(n, a, b) {
return None;
}
crate::frac::divide_by_diff(n, a, b)
}
}
}
}
impl core::fmt::Display for Atom {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
Atom::Unit(a, b) => write!(f, "(1-q^{a}t^{b})"),
Atom::Diff(a, b) => write!(f, "(q^{a}-t^{b})"),
}
}
}
type Atoms = BTreeMap<Atom, u32>;
fn push(map: &mut Atoms, atom: Atom, times: u32) {
if times > 0 {
*map.entry(atom).or_insert(0) += times;
}
}
#[derive(Clone, Debug)]
pub struct Ratio<C: Ring> {
num: QtPoly<C>,
den: Atoms,
}
impl<C: Ring> Ratio<C> {
pub fn from_poly(num: QtPoly<C>) -> Self {
Ratio {
num,
den: Atoms::new(),
}
}
fn over(num: QtPoly<C>, den: Atoms) -> Self {
Ratio { num, den }
}
pub fn parts(&self) -> (&QtPoly<C>, impl Iterator<Item = (&Atom, &u32)>) {
(&self.num, self.den.iter())
}
pub fn mul_atoms(&self, atoms: &Atoms) -> Self {
let mut num = self.num.clone();
for (&a, &m) in atoms {
for _ in 0..m {
num = a.mul_into(&num);
}
}
Ratio {
num,
den: self.den.clone(),
}
}
pub fn div_atoms(&self, atoms: &Atoms) -> Self {
let mut den = self.den.clone();
for (&a, &m) in atoms {
push(&mut den, a, m);
}
Ratio {
num: self.num.clone(),
den,
}
}
fn lift(&self, target: &Atoms) -> QtPoly<C> {
let mut num = self.num.clone();
for (&a, &m) in target {
for _ in 0..(m - self.den.get(&a).copied().unwrap_or(0)) {
num = a.mul_into(&num);
}
}
num
}
fn add_mul(&mut self, other: &Self, p: &QtPoly<C>) {
if other.num.is_empty() || p.is_empty() {
return;
}
let scaled = other.num.mul(p);
if self.num.is_empty() && self.den.is_empty() {
self.num = scaled;
self.den = other.den.clone();
return;
}
if other.den != self.den {
let mut lcm = self.den.clone();
for (&a, &m) in &other.den {
let e = lcm.entry(a).or_insert(0);
*e = (*e).max(m);
}
self.num = self.lift(&lcm);
self.den = lcm;
}
let mut lifted = scaled;
for (&a, &m) in &self.den {
for _ in 0..(m - other.den.get(&a).copied().unwrap_or(0)) {
lifted = a.mul_into(&lifted);
}
}
self.num.add_assign(&lifted);
}
pub fn reduce(&mut self) {
if self.num.is_empty() {
self.den.clear();
return;
}
self.den.retain(|&a, m| {
while *m > 0 {
match a.divide(&self.num) {
Some(q) => {
self.num = q;
*m -= 1;
}
None => break,
}
}
*m > 0
});
}
pub fn into_poly(mut self) -> Option<QtPoly<C>> {
self.reduce();
self.den.is_empty().then_some(self.num)
}
}
impl<C: Ring> PartialEq for Ratio<C> {
fn eq(&self, other: &Self) -> bool {
if self.den == other.den {
return self.num == other.num;
}
let mut lcm = self.den.clone();
for (&a, &m) in &other.den {
let e = lcm.entry(a).or_insert(0);
*e = (*e).max(m);
}
self.lift(&lcm) == other.lift(&lcm)
}
}
impl<C: Ring> Eq for Ratio<C> {}
crate::coeff::impl_ring_ops!([C: Ring] Ratio<C>);
impl<C: Ring> Ring for Ratio<C> {
fn zero() -> Self {
Ratio {
num: QtPoly::zero(),
den: Atoms::new(),
}
}
fn one() -> Self {
Ratio {
num: <QtPoly<C> as Ring>::one(),
den: Atoms::new(),
}
}
fn is_zero(&self) -> bool {
self.num.is_zero()
}
fn add_assign(&mut self, other: &Self) {
let one = <QtPoly<C> as Ring>::one();
self.add_mul(other, &one);
}
fn mul(&self, other: &Self) -> Self {
if self.is_zero() || other.is_zero() {
return Self::zero();
}
let mut den = self.den.clone();
for (&a, &m) in &other.den {
push(&mut den, a, m);
}
let mut r = Ratio {
num: self.num.mul(&other.num),
den,
};
r.reduce();
r
}
fn neg(&self) -> Self {
Ratio {
num: self.num.neg(),
den: self.den.clone(),
}
}
fn from_i64(n: i64) -> Self {
Ratio::from_poly(<QtPoly<C> as Ring>::from_i64(n))
}
fn from_u128(n: u128) -> Self {
Ratio::from_poly(<QtPoly<C> as Ring>::from_u128(n))
}
fn from_i128(n: i128) -> Self {
Ratio::from_poly(<QtPoly<C> as Ring>::from_i128(n))
}
fn try_from_u128(n: u128) -> Option<Self> {
<QtPoly<C> as Ring>::try_from_u128(n).map(Ratio::from_poly)
}
fn try_from_i128(n: i128) -> Option<Self> {
<QtPoly<C> as Ring>::try_from_i128(n).map(Ratio::from_poly)
}
}
impl<C: QAlgebra> QAlgebra for Ratio<C> {
fn div_u128(&self, n: u128) -> Self {
Ratio {
num: self.num.div_u128(n),
den: self.den.clone(),
}
}
}
impl<C: Plethystic> Plethystic for Ratio<C> {
fn frobenius(&self, n: u32) -> Self {
Ratio {
num: self.num.frobenius(n),
den: self
.den
.iter()
.map(|(a, &m)| {
let raised = match *a {
Atom::Unit(x, y) => Atom::Unit(x * n, y * n),
Atom::Diff(x, y) => Atom::Diff(x * n, y * n),
};
(raised, m)
})
.collect(),
}
}
}
impl<C: Ring> core::fmt::Display for Ratio<C> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
write!(f, "({})", self.num)?;
for (a, &m) in &self.den {
write!(f, "/{a}")?;
if m > 1 {
write!(f, "^{m}")?;
}
}
Ok(())
}
}
fn coarms(mu: &Partition) -> Vec<(u32, u32)> {
let mut out = Vec::with_capacity(mu.size() as usize);
for (i, &row) in mu.parts().iter().enumerate() {
for j in 0..row {
out.push((j, i as u32));
}
}
out
}
fn b_mu<C: Ring>(cells: &[(u32, u32)]) -> QtPoly<C> {
let mut out = QtPoly::zero();
for &(a, l) in cells {
out.add_term(a, l, C::one());
}
out
}
fn t_mu<C: Ring>(cells: &[(u32, u32)]) -> QtPoly<C> {
let (mut a, mut l) = (0, 0);
for &(x, y) in cells {
a += x;
l += y;
}
QtPoly::term(a, l, C::one())
}
fn pi_atoms(cells: &[(u32, u32)]) -> Atoms {
let mut out = Atoms::new();
for &(a, l) in cells {
if (a, l) != (0, 0) {
push(&mut out, Atom::unit(a, l), 1);
}
}
out
}
fn w_atoms(mu: &Partition) -> (Atoms, bool) {
let shape = mu.parts();
let mut out = Atoms::new();
let mut negated = false;
for i in 0..shape.len() {
for j in 0..shape[i] as usize {
let a = crate::macdonald::arm(shape, i, j);
let l = crate::macdonald::leg(shape, i, j);
for (x, y) in [(a, l + 1), (a + 1, l)] {
let (atom, neg) = Atom::diff(x, y);
push(&mut out, atom, 1);
negated ^= neg;
}
negated = !negated;
}
}
(out, negated)
}
fn m_atoms() -> Atoms {
let mut out = Atoms::new();
push(&mut out, Atom::unit(1, 0), 1);
push(&mut out, Atom::unit(0, 1), 1);
out
}
fn star_against_schur<C: QAlgebra>(f: &Schur<Ratio<C>>, n: u32) -> Vec<Ratio<C>> {
let parts = crate::memo::partitions_cached(n);
let fp: PowerSum<Ratio<C>> = PowerSum::from_schur(f);
let weighted: Vec<(Partition, Ratio<C>)> = fp
.terms()
.iter()
.map(|(rho, c)| {
let mut w = Atoms::new();
for &part in rho.parts() {
push(&mut w, Atom::unit(part, 0), 1);
push(&mut w, Atom::unit(0, part), 1);
}
let mut v = c.mul_atoms(&w);
if (rho.size() - rho.len() as u32) % 2 == 1 {
v = v.neg();
}
v.reduce();
(rho.clone(), v)
})
.collect();
parts
.iter()
.map(|kappa| {
let mut acc = <Ratio<C> as Ring>::zero();
for (rho, v) in &weighted {
let chi = crate::character::character(kappa, rho);
if chi != 0 {
acc.add_mul(v, &QtPoly::term(0, 0, C::from_i128(chi)));
}
}
acc.reduce();
acc
})
.collect()
}
pub fn scalar_qt_ratio<C: QAlgebra>(f: &Schur<Ratio<C>>, g: &Schur<Ratio<C>>) -> Ratio<C> {
let fp: PowerSum<Ratio<C>> = PowerSum::from_schur(f);
let gp: PowerSum<Ratio<C>> = PowerSum::from_schur(g);
let mut out = <Ratio<C> as Ring>::zero();
for (mu, a) in fp.terms() {
let Some(b) = gp.terms().get(mu) else {
continue;
};
let mut num = Atoms::new();
let mut den = Atoms::new();
for &part in mu.parts() {
push(&mut num, Atom::unit(part, 0), 1);
push(&mut den, Atom::unit(0, part), 1);
}
let term = a.mul(b).mul(&mu.z_in::<Ratio<C>>());
out.add_assign(&term.mul_atoms(&num).div_atoms(&den));
}
out.reduce();
out
}
fn coefficients<C: QAlgebra>(
f: &Schur<Ratio<C>>,
n: u32,
htilde: &[(Partition, Schur<QtPoly<C>>)],
) -> Vec<Ratio<C>> {
let u = star_against_schur(f, n);
let parts = crate::memo::partitions_cached(n);
htilde
.iter()
.map(|(mu, ht)| {
let mut acc = <Ratio<C> as Ring>::zero();
for (k, kappa) in parts.iter().enumerate() {
let kt = ht.coeff(kappa);
if !kt.is_empty() {
acc.add_mul(&u[k], &kt);
}
}
acc.reduce();
let (w, negated) = w_atoms(mu);
let mut c = acc.div_atoms(&w);
if negated {
c = c.neg();
}
c.reduce();
c
})
.collect()
}
fn combine<C: Ring>(
coeffs: &[Ratio<C>],
n: u32,
htilde: &[(Partition, Schur<QtPoly<C>>)],
) -> Schur<Ratio<C>> {
let parts = crate::memo::partitions_cached(n);
let mut out = Schur::zero();
for lambda in parts.iter() {
crate::interrupt::poll();
let items: Vec<Ratio<C>> = coeffs
.iter()
.zip(htilde.iter())
.filter(|(c, _)| !c.is_zero())
.filter_map(|(c, (_, ht))| {
let kt = ht.coeff(lambda);
(!kt.is_empty()).then(|| {
let mut r = Ratio::over(c.num.mul(&kt), c.den.clone());
r.reduce();
r
})
})
.collect();
out.add_term(lambda.clone(), sum_tree(items));
}
out
}
fn sum_tree<C: Ring>(mut items: Vec<Ratio<C>>) -> Ratio<C> {
let one = <QtPoly<C> as Ring>::one();
while items.len() > 1 {
crate::interrupt::poll();
let mut next: Vec<Ratio<C>> = Vec::with_capacity(items.len().div_ceil(2));
let mut it = items.into_iter();
while let Some(mut a) = it.next() {
if let Some(b) = it.next() {
a.add_mul(&b, &one);
a.reduce();
}
next.push(a);
}
items = next;
}
items.pop().unwrap_or_else(<Ratio<C> as Ring>::zero)
}
fn degree_of<C: Ring, S: SymFn<C>>(f: &S, what: &str) -> Option<u32> {
let mut it = f.terms().keys().map(Partition::size);
let first = it.next()?;
assert!(
it.all(|d| d == first),
"{what} requires a homogeneous argument"
);
Some(first)
}
fn diagonal<C: QAlgebra>(
f: &Schur<Ratio<C>>,
eigen: impl Fn(&Partition, &[(u32, u32)]) -> Ratio<C>,
) -> Schur<Ratio<C>> {
let n = match degree_of(f, "a Macdonald operator") {
Some(n) => n,
None => return Schur::zero(),
};
let htilde = crate::bh::htilde_table::<C>(n);
let mut coeffs = coefficients(f, n, &htilde);
for (c, (mu, _)) in coeffs.iter_mut().zip(htilde.iter()) {
let e = eigen(mu, &coarms(mu));
*c = c.mul(&e);
}
combine(&coeffs, n, &htilde)
}
fn lift_in<C: Ring>(f: &Schur<QtPoly<C>>) -> Schur<Ratio<C>> {
Schur::from_terms(
f.terms()
.iter()
.map(|(l, c)| (l.clone(), Ratio::from_poly(c.clone())))
.collect(),
)
}
fn lift_out<C: Ring>(f: Schur<Ratio<C>>, what: &str) -> Schur<QtPoly<C>> {
let mut out = Schur::zero();
for (lambda, c) in f.terms() {
let p = c.clone().into_poly().unwrap_or_else(|| {
panic!("{what} is not a polynomial at {lambda}: {c}");
});
out.add_term(lambda.clone(), p);
}
out
}
fn plethystic_eval<C: QAlgebra>(f: &Schur<i128>, cells: &[(u32, u32)]) -> QtPoly<C> {
let lifted: Schur<C> = Schur::from_terms(
f.terms()
.iter()
.map(|(l, &c)| (l.clone(), C::from_i128(c)))
.collect(),
);
let fp: PowerSum<C> = PowerSum::from_schur(&lifted);
let mut out = QtPoly::zero();
for (rho, c) in fp.terms() {
let mut term = QtPoly::term(0, 0, c.clone());
for &k in rho.parts() {
let mut pk = QtPoly::zero();
for &(a, l) in cells {
pk.add_term(a * k, l * k, C::one());
}
term = term.mul(&pk);
}
out.add_assign(&term);
}
out
}
fn without_corner(cells: &[(u32, u32)]) -> Vec<(u32, u32)> {
cells.iter().copied().filter(|&c| c != (0, 0)).collect()
}
fn elementary_eval<C: Ring>(cells: &[(u32, u32)], k: u32) -> QtPoly<C> {
let k = k as usize;
let mut acc: Vec<QtPoly<C>> = vec![QtPoly::zero(); k + 1];
acc[0] = <QtPoly<C> as Ring>::one();
for &(a, l) in cells {
let m = QtPoly::term(a, l, C::one());
for j in (1..=k).rev() {
let add = acc[j - 1].mul(&m);
acc[j].add_assign(&add);
}
}
acc.swap_remove(k)
}
pub fn nabla<C: QAlgebra>(f: &Schur<QtPoly<C>>) -> Schur<QtPoly<C>> {
let got = diagonal(&lift_in(f), |_, cells| Ratio::from_poly(t_mu::<C>(cells)));
lift_out(got, "nabla")
}
pub fn nabla_power<C: QAlgebra>(f: &Schur<QtPoly<C>>, r: u32) -> Schur<QtPoly<C>> {
let got = diagonal(&lift_in(f), |_, cells| {
let t = t_mu::<C>(cells);
let mut acc = <QtPoly<C> as Ring>::one();
for _ in 0..r {
acc = acc.mul(&t);
}
Ratio::from_poly(acc)
});
lift_out(got, "nabla_power")
}
pub fn delta<C: QAlgebra>(f: &Schur<i128>, x: &Schur<QtPoly<C>>) -> Schur<QtPoly<C>> {
let got = diagonal(&lift_in(x), |_, cells| {
Ratio::from_poly(plethystic_eval::<C>(f, cells))
});
lift_out(got, "delta")
}
pub fn delta_prime<C: QAlgebra>(f: &Schur<i128>, x: &Schur<QtPoly<C>>) -> Schur<QtPoly<C>> {
let got = diagonal(&lift_in(x), |_, cells| {
Ratio::from_poly(plethystic_eval::<C>(f, &without_corner(cells)))
});
lift_out(got, "delta_prime")
}
pub fn big_pi<C: QAlgebra>(x: &Schur<QtPoly<C>>) -> Schur<QtPoly<C>> {
let got = diagonal(&lift_in(x), |_, cells| {
<Ratio<C> as Ring>::one().mul_atoms(&pi_atoms(cells))
});
lift_out(got, "big_pi")
}
pub fn big_pi_inverse<C: QAlgebra>(x: &Schur<QtPoly<C>>) -> Schur<Ratio<C>> {
diagonal(&lift_in(x), |_, cells| {
<Ratio<C> as Ring>::one().div_atoms(&pi_atoms(cells))
})
}
fn star_substitute<C: QAlgebra>(f: &Schur<i128>) -> Schur<Ratio<C>> {
use crate::convert::ToSchur;
let lifted: Schur<Ratio<C>> = Schur::from_terms(
f.terms()
.iter()
.map(|(l, &c)| (l.clone(), <Ratio<C> as Ring>::from_i128(c)))
.collect(),
);
let fp: PowerSum<Ratio<C>> = PowerSum::from_schur(&lifted);
let mut out: PowerSum<Ratio<C>> = PowerSum::zero();
for (rho, c) in fp.terms() {
let mut d = Atoms::new();
for &k in rho.parts() {
push(&mut d, Atom::unit(k, 0), 1);
push(&mut d, Atom::unit(0, k), 1);
}
let mut v = c.div_atoms(&d);
v.reduce();
out.add_term(rho.clone(), v);
}
out.to_schur()
}
pub fn theta<C: QAlgebra>(f: &Schur<i128>, x: &Schur<QtPoly<C>>) -> Schur<QtPoly<C>> {
let k = match degree_of(f, "theta's subscript") {
Some(k) => k,
None => return Schur::zero(),
};
let n = match degree_of(x, "theta") {
Some(n) => n,
None => return Schur::zero(),
};
if n == 0 {
return if k == 0 {
let c = x.coeff(&Partition::new([]));
let scale = QtPoly::term(0, 0, C::from_i128(f.coeff(&Partition::new([]))));
Schur::monomial(Partition::new([]), c.mul(&scale))
} else {
Schur::zero()
};
}
let inner = big_pi_inverse(x);
let product = star_substitute::<C>(f).mul(&inner);
let htilde = crate::bh::htilde_table::<C>(n + k);
let mut coeffs = coefficients(&product, n + k, &htilde);
for (c, (mu, _)) in coeffs.iter_mut().zip(htilde.iter()) {
*c = c.mul_atoms(&pi_atoms(&coarms(mu)));
c.reduce();
}
lift_out(combine(&coeffs, n + k, &htilde), "theta")
}
pub fn schur_to_macdonald_ht<C: QAlgebra>(f: &Schur<QtPoly<C>>) -> BTreeMap<Partition, Ratio<C>> {
let mut out = BTreeMap::new();
for (n, terms) in by_degree(f) {
let g: Schur<Ratio<C>> = Schur::from_terms(
terms
.into_iter()
.map(|(mu, c)| (mu.clone(), Ratio::from_poly(c.clone())))
.collect(),
);
let htilde = crate::bh::htilde_table::<C>(n);
for (c, (mu, _)) in coefficients(&g, n, &htilde).into_iter().zip(htilde.iter()) {
if !c.is_zero() {
out.insert(mu.clone(), c);
}
}
}
out
}
pub fn macdonald_ht_to_schur<C: QAlgebra>(f: &BTreeMap<Partition, Ratio<C>>) -> Schur<Ratio<C>> {
let mut by_deg: BTreeMap<u32, Vec<(&Partition, &Ratio<C>)>> = BTreeMap::new();
for (mu, c) in f {
by_deg.entry(mu.size()).or_default().push((mu, c));
}
let mut out = Schur::zero();
for (n, terms) in by_deg {
let table = crate::bh::htilde_table::<C>(n);
for (mu, c) in terms {
crate::interrupt::poll();
let row = table
.iter()
.find(|(m, _)| m == mu)
.expect("mu must be a partition of its own size");
for (lambda, v) in row.1.terms() {
out.add_term(lambda.clone(), Ratio::from_poly(v.clone()).mul(c));
}
}
}
for v in out.terms_mut().values_mut() {
v.reduce();
}
out.terms_mut().retain(|_, v| !v.is_zero());
out
}
pub fn htilde_element_add<C: Ring>(
f: &BTreeMap<Partition, Ratio<C>>,
g: &BTreeMap<Partition, Ratio<C>>,
) -> BTreeMap<Partition, Ratio<C>> {
let mut out = f.clone();
for (mu, c) in g {
crate::sym::add_at(&mut out, mu, c.clone());
}
for v in out.values_mut() {
v.reduce();
}
out.retain(|_, v| !v.is_zero());
out
}
pub fn htilde_element_scale<C: Ring>(
f: &BTreeMap<Partition, Ratio<C>>,
c: &Ratio<C>,
) -> BTreeMap<Partition, Ratio<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 e_coefficients<C: Ring>(n: u32) -> Vec<Ratio<C>> {
crate::memo::partitions_cached(n)
.iter()
.map(|mu| {
let cells = coarms(mu);
let mut num = b_mu::<C>(&cells);
for (&a, &m) in m_atoms().iter().chain(pi_atoms(&cells).iter()) {
for _ in 0..m {
num = a.mul_into(&num);
}
}
let (w, negated) = w_atoms(mu);
let mut c = Ratio::over(if negated { num.neg() } else { num }, w);
c.reduce();
c
})
.collect()
}
pub fn nabla_e<C: Ring>(n: u32) -> Schur<QtPoly<C>> {
closed_form(n, |cells| t_mu::<C>(cells))
}
pub fn delta_prime_e<C: Ring>(k: u32, n: u32) -> Schur<QtPoly<C>> {
closed_form(n, move |cells| {
elementary_eval::<C>(&without_corner(cells), k)
})
}
fn closed_form<C: Ring>(n: u32, eigen: impl Fn(&[(u32, u32)]) -> QtPoly<C>) -> Schur<QtPoly<C>> {
if n == 0 {
return Schur::monomial(Partition::new([]), <QtPoly<C> as Ring>::one());
}
let htilde = crate::bh::htilde_table::<C>(n);
let mut coeffs = e_coefficients::<C>(n);
for (c, (mu, _)) in coeffs.iter_mut().zip(htilde.iter()) {
*c = c.mul(&Ratio::from_poly(eigen(&coarms(mu))));
}
lift_out(combine(&coeffs, n, &htilde), "the closed form for e_n")
}
pub fn elementary(k: u32) -> Schur<i128> {
Schur::monomial(Partition::new(std::iter::repeat_n(1, k as usize)), 1)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
type Q = QtPoly<Rational>;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn e_schur(n: u32) -> Schur<Q> {
Schur::monomial(part(&vec![1; n as usize]), <Q as Ring>::one())
}
#[test]
fn scalar_qt_ratio_agrees_with_the_frac_form() {
for n in 1..=4u32 {
let shapes = crate::partitions_of(n);
for la in &shapes {
for mu in &shapes {
let f: Schur<Ratio<Rational>> =
Schur::monomial(la.clone(), <Ratio<Rational> as Ring>::one());
let g: Schur<Ratio<Rational>> =
Schur::monomial(mu.clone(), <Ratio<Rational> as Ring>::one());
let got = scalar_qt_ratio(&f, &g);
let (num, atoms) = got.parts();
let mut factors = std::collections::BTreeMap::new();
for (atom, &m) in atoms {
let Atom::Unit(a, b) = atom else {
panic!("⟨s_{la}, s_{mu}⟩_qt grew a Diff atom");
};
*factors.entry((*a, *b)).or_insert(0i32) -= i32::try_from(m).unwrap();
}
let lifted = crate::frac::Frac::from_poly(num.clone()).mul_factors(&factors);
let fs: Schur<crate::frac::Frac<Rational>> =
Schur::monomial(la.clone(), <crate::frac::Frac<Rational> as Ring>::one());
let gs: Schur<crate::frac::Frac<Rational>> =
Schur::monomial(mu.clone(), <crate::frac::Frac<Rational> as Ring>::one());
let want = crate::macdonald::scalar_qt(&fs, &gs);
assert_eq!(lifted, want, "⟨s_{la}, s_{mu}⟩_qt across the two types");
}
}
}
}
fn h_schur(n: u32) -> Schur<Q> {
Schur::monomial(part(&[n]), <Q as Ring>::one())
}
fn s_schur(lambda: &[u32]) -> Schur<Q> {
Schur::monomial(part(lambda), <Q as Ring>::one())
}
#[test]
fn frobenius_raises_both_atom_families() {
let unit = Ratio::<Rational>::over(<Q as Ring>::one(), {
let mut d = Atoms::new();
push(&mut d, Atom::Unit(1, 1), 1);
d
});
let diff = Ratio::<Rational>::over(<Q as Ring>::one(), {
let mut d = Atoms::new();
push(&mut d, Atom::Diff(1, 2), 1);
d
});
for (f, want) in [(&unit, Atom::Unit(3, 3)), (&diff, Atom::Diff(3, 6))] {
let raised = f.frobenius(3);
let (_, atoms) = raised.parts();
let got: Vec<_> = atoms.map(|(a, &m)| (*a, m)).collect();
assert_eq!(got, vec![(want, 1)], "raising {f}");
assert_eq!(f.frobenius(1), *f, "n = 1 is the identity on {f}");
}
for n in 1..4 {
assert_eq!(
unit.mul(&diff).frobenius(n),
unit.frobenius(n).mul(&diff.frobenius(n)),
"multiplicative at n = {n}"
);
}
}
#[test]
fn t_mu_is_the_hook_monomial() {
for n in 0..=7u32 {
for mu in crate::partitions_of(n) {
let n_mu: u32 = mu
.parts()
.iter()
.enumerate()
.map(|(i, &p)| i as u32 * p)
.sum();
let n_conj: u32 = mu
.conjugate()
.parts()
.iter()
.enumerate()
.map(|(i, &p)| i as u32 * p)
.sum();
let got: Q = t_mu(&coarms(&mu));
assert_eq!(
got,
QtPoly::term(n_conj, n_mu, Rational::from_int(1)),
"{mu}"
);
}
}
}
#[test]
fn htilde_is_star_orthogonal_with_norm_w() {
for n in 0..=6u32 {
let parts = crate::partitions_of(n);
let htilde = crate::bh::htilde_table::<Rational>(n);
for (mu, ht) in &htilde {
let lifted = lift_in(ht);
let u = star_against_schur(&lifted, n);
for (j, (nu, other)) in htilde.iter().enumerate() {
let _ = j;
let mut acc = <Ratio<Rational> as Ring>::zero();
for (k, kappa) in parts.iter().enumerate() {
let kt = other.coeff(kappa);
if !kt.is_empty() {
acc.add_mul(&u[k], &kt);
}
}
acc.reduce();
let got = acc.into_poly().expect("the pairing is a polynomial");
if mu == nu {
let (w, negated) = w_atoms(mu);
let mut want = <Q as Ring>::one();
for (&a, &m) in &w {
for _ in 0..m {
want = a.mul_into(&want);
}
}
if negated {
want = want.neg();
}
assert_eq!(got, want, "<H~_{mu},H~_{mu}>_* must be w_{mu}");
} else {
assert!(got.is_empty(), "<H~_{mu},H~_{nu}>_* must vanish");
}
}
}
}
}
#[test]
fn the_htilde_expansion_round_trips() {
for n in 0..=6u32 {
let htilde = crate::bh::htilde_table::<Rational>(n);
for lambda in crate::partitions_of(n) {
let f = s_schur(lambda.parts());
let lifted = lift_in(&f);
let coeffs = coefficients(&lifted, n, &htilde);
let back = lift_out(combine(&coeffs, n, &htilde), "round trip");
assert_eq!(back, f, "round trip at {lambda}");
}
}
}
#[test]
fn nabla_of_e_two_is_the_hand_computation() {
let got = nabla(&e_schur(2));
assert_eq!(got.coeff(&part(&[2])), <Q as Ring>::one());
let mut want: Q = QtPoly::term(1, 0, Rational::from_int(1));
want.add_term(0, 1, Rational::from_int(1));
assert_eq!(got.coeff(&part(&[1, 1])), want);
assert_eq!(got.terms().len(), 2, "{got}");
}
#[test]
fn nabla_e_counts_the_diagonal_harmonics() {
for n in 1..=7u32 {
let got = nabla_e::<Rational>(n);
let one = Rational::from_int(1);
let mut total = Rational::from_int(0);
for (lambda, c) in got.terms() {
let d = crate::dimension(lambda).expect("a partition has a dimension");
let v = c.eval(&one, &one).mul(&Rational::from_u128(d));
total.add_assign(&v);
}
let want = Rational::from_u128((n as u128 + 1).pow(n - 1));
assert_eq!(total, want, "dim DH_{n}");
}
}
#[test]
fn nabla_e_is_schur_positive() {
for n in 0..=7u32 {
for (lambda, c) in nabla_e::<Rational>(n).terms() {
for (_, v) in c.terms() {
assert_eq!(v.denom(), 1, "nabla e_{n} at {lambda} has {v:?}");
assert!(v.numer() > 0, "nabla e_{n} at {lambda} has {v:?}");
}
}
}
}
#[test]
fn the_closed_form_agrees_with_the_pairing() {
for n in 0..=6u32 {
assert_eq!(nabla_e::<Rational>(n), nabla(&e_schur(n)), "nabla e_{n}");
for k in 0..n {
assert_eq!(
delta_prime_e::<Rational>(k, n),
delta_prime(&elementary(k), &e_schur(n)),
"Delta'_e{k} e_{n}"
);
}
}
}
#[test]
fn delta_of_e_n_is_nabla() {
for n in 0..=5u32 {
for f in [e_schur(n), h_schur(n)] {
assert_eq!(delta(&elementary(n), &f), nabla(&f), "degree {n}");
}
}
}
#[test]
fn delta_prime_at_the_top_is_nabla() {
for n in 1..=6u32 {
assert_eq!(
delta_prime_e::<Rational>(n - 1, n),
nabla_e::<Rational>(n),
"Delta'_e{} e_{n}",
n - 1
);
}
}
#[test]
fn theta_composed_with_nabla_is_delta_prime() {
for n in 2..=5u32 {
for k in 1..n {
let lhs = theta(&elementary(k), &nabla_e::<Rational>(n - k));
let rhs = delta_prime_e::<Rational>(n - k - 1, n);
assert_eq!(lhs, rhs, "Theta_e{k} nabla e_{} vs Delta'", n - k);
}
}
}
#[test]
fn big_pi_and_its_inverse_are_inverse() {
for n in 0..=5u32 {
for lambda in crate::partitions_of(n) {
let f = s_schur(lambda.parts());
let back = lift_out(
diagonal(&big_pi_inverse(&f), |_, cells| {
<Ratio<Rational> as Ring>::one().mul_atoms(&pi_atoms(cells))
}),
"pi round trip",
);
assert_eq!(back, f, "Pi Pi^-1 at {lambda}");
let there = big_pi(&f);
let and_back = big_pi_inverse(&there);
assert_eq!(
lift_out(and_back, "pi round trip"),
f,
"Pi^-1 Pi at {lambda}"
);
}
}
}
#[test]
fn nabla_is_linear_and_powers_compose() {
let f = s_schur(&[3, 1]).add(&s_schur(&[2, 2]).scale(&QtPoly::term(
0,
0,
Rational::from_int(3),
)));
let a = nabla(&s_schur(&[3, 1]));
let b = nabla(&s_schur(&[2, 2]));
let want = a.add(&b.scale(&QtPoly::term(0, 0, Rational::from_int(3))));
assert_eq!(nabla(&f), want, "linearity");
let mut iterated = f.clone();
for _ in 0..3 {
iterated = nabla(&iterated);
}
assert_eq!(nabla_power(&f, 3), iterated, "nabla^3");
}
#[test]
fn nabla_of_a_monomial_is_signed_schur_positive() {
use crate::convert::ToSchur;
for n in 0..=5u32 {
for mu in crate::partitions_of(n) {
let m: crate::Monomial<Q> =
crate::Monomial::monomial(mu.clone(), <Q as Ring>::one());
let f = m.to_schur();
for r in 1..=2u32 {
let got = nabla_power(&f, r);
let sign = (mu.size() - mu.len() as u32) % 2 == 1;
for (lambda, c) in got.terms() {
for (_, v) in c.terms() {
let ok = if sign { v.numer() < 0 } else { v.numer() > 0 };
assert!(ok, "nabla^{r} m_{mu} at {lambda} has {v:?}");
}
}
}
}
}
}
#[test]
fn atoms_normalize_across_the_two_families() {
assert_eq!(Atom::diff(3, 0), (Atom::Unit(3, 0), true));
assert_eq!(Atom::diff(0, 3), (Atom::Unit(0, 3), false));
assert_eq!(Atom::diff(2, 3), (Atom::Diff(2, 3), false));
let (a, neg) = Atom::diff(3, 0);
let mut want: Q = QtPoly::term(3, 0, Rational::from_int(1));
want.add_term(0, 0, Rational::from_int(-1));
let got: Q = a.poly();
assert_eq!(if neg { got.neg() } else { got }, want);
}
#[test]
fn the_specialized_diff_division_agrees_with_the_general_one() {
let mut dense: Q = QtPoly::zero();
for a in 0..5 {
for b in 0..4 {
dense.add_term(
a,
b,
Rational::from_int(i128::from(a) - 2 * i128::from(b) + 1),
);
}
}
let mut sparse: Q = QtPoly::zero();
sparse.add_term(0, 0, Rational::from_int(1));
sparse.add_term(4, 1, Rational::from_int(-3));
sparse.add_term(1, 6, Rational::from_int(5));
sparse.add_term(3, 3, Rational::from_int(2));
for f in [dense, sparse, <Q as Ring>::one(), QtPoly::zero()] {
for (a, b) in [(1u32, 1u32), (1, 2), (2, 1), (2, 3), (3, 2), (1, 5), (4, 4)] {
let d: Q = Atom::Diff(a, b).poly();
let prod = f.mul_diff(a, b);
assert_eq!(
crate::frac::divide_by_diff(&prod, a, b),
prod.divide_exact(&d),
"(q^{a} - t^{b}) dividing its own multiple"
);
assert_eq!(
crate::frac::divide_by_diff(&prod, a, b),
Some(f.clone()),
"(q^{a} - t^{b}) must recover the cofactor"
);
assert_eq!(
crate::frac::divide_by_diff(&f, a, b),
f.divide_exact(&d),
"(q^{a} - t^{b}) against {f}"
);
}
}
}
#[test]
fn the_divisibility_filter_never_rejects_a_multiple() {
let mut f: Q = QtPoly::zero();
for a in 0..5 {
for b in 0..4 {
f.add_term(a, b, Rational::from_int(i128::from(a) + i128::from(b) + 1));
}
}
for (a, b) in [(1u32, 1u32), (2, 2), (2, 4), (4, 2), (3, 3), (2, 3), (6, 4)] {
assert!(
crate::frac::diff_may_divide(&f.mul_diff(a, b), a, b),
"the filter rejected a multiple of (q^{a} - t^{b})"
);
}
}
#[test]
fn atom_division_inverts_multiplication() {
let mut f: Q = QtPoly::zero();
for a in 0..4 {
for b in 0..3 {
f.add_term(a, b, Rational::from_int(i128::from(a) - i128::from(b) + 1));
}
}
for atom in [
Atom::Unit(1, 0),
Atom::Unit(0, 1),
Atom::Unit(2, 3),
Atom::Diff(1, 1),
Atom::Diff(3, 2),
] {
let prod = atom.mul_into(&f);
assert_eq!(atom.divide(&prod), Some(f.clone()), "{atom}");
}
}
#[test]
fn every_htilde_comes_back_as_itself() {
for n in 0..=8u32 {
for (mu, ht) in crate::bh::htilde_table::<Rational>(n) {
let got = schur_to_macdonald_ht(&ht);
assert_eq!(got.len(), 1, "H̃_{mu} did not expand to one term");
assert_eq!(
got.get(&mu),
Some(&<Ratio<Rational> as Ring>::one()),
"H̃_{mu} did not expand to itself"
);
}
}
}
#[test]
fn s2_and_s11_in_htilde_are_the_hand_values() {
let q_minus_t: Atoms = [(Atom::Diff(1, 1), 1)].into_iter().collect();
let over = |a: u32, b: u32, c: i128| {
Ratio::over(QtPoly::term(a, b, Rational::from_int(c)), q_minus_t.clone())
};
let in_ht = schur_to_macdonald_ht(&s_schur(&[2]));
assert_eq!(in_ht[&part(&[1, 1])], over(1, 0, 1), "s_2 at H̃_11");
assert_eq!(in_ht[&part(&[2])], over(0, 1, -1), "s_2 at H̃_2");
let in_ht = schur_to_macdonald_ht(&s_schur(&[1, 1]));
assert_eq!(in_ht[&part(&[1, 1])], over(0, 0, -1), "s_11 at H̃_11");
assert_eq!(in_ht[&part(&[2])], over(0, 0, 1), "s_11 at H̃_2");
}
#[test]
fn the_expansion_is_linear_and_takes_mixed_degrees() {
let mut f: Schur<Q> = s_schur(&[2]);
f.add_term(part(&[2, 1]), QtPoly::term(0, 0, Rational::from_int(3)));
let got = schur_to_macdonald_ht(&f);
let low = schur_to_macdonald_ht(&s_schur(&[2]));
let high = schur_to_macdonald_ht(&s_schur(&[2, 1]));
let three = Ratio::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_ht(&Schur::<Q>::zero()).is_empty());
}
}