use crate::coeff::Ring;
use crate::lr::LrBackend;
use crate::partition::Partition;
use crate::strip_lr::AutoLr;
use std::collections::btree_map::Entry;
use std::collections::BTreeMap;
pub trait SymFn<C: Ring>: Sized {
const SYMBOL: &'static str;
fn terms(&self) -> &BTreeMap<Partition, C>;
fn terms_mut(&mut self) -> &mut BTreeMap<Partition, C>;
fn from_terms(terms: BTreeMap<Partition, C>) -> Self;
fn zero() -> Self {
Self::from_terms(BTreeMap::new())
}
fn monomial(p: Partition, c: C) -> Self {
let mut t = BTreeMap::new();
if !c.is_zero() {
t.insert(p, c);
}
Self::from_terms(t)
}
fn coeff(&self, p: &Partition) -> C {
self.terms().get(p).cloned().unwrap_or_else(C::zero)
}
fn is_zero(&self) -> bool {
self.terms().is_empty()
}
fn degree(&self) -> Option<u32> {
self.terms().keys().map(Partition::size).max()
}
fn add_term(&mut self, p: Partition, c: C) {
if c.is_zero() {
return;
}
match self.terms_mut().entry(p) {
Entry::Vacant(e) => {
e.insert(c);
}
Entry::Occupied(mut e) => {
e.get_mut().add_assign(&c);
if e.get().is_zero() {
e.remove();
}
}
}
}
fn add(&self, other: &Self) -> Self {
let mut out = Self::from_terms(self.terms().clone());
for (p, c) in other.terms() {
out.add_term(p.clone(), c.clone());
}
out
}
fn scale(&self, c: &C) -> Self {
let mut t = BTreeMap::new();
if !c.is_zero() {
for (p, cc) in self.terms() {
let v = cc.mul(c);
if !v.is_zero() {
t.insert(p.clone(), v);
}
}
}
Self::from_terms(t)
}
fn neg(&self) -> Self {
self.scale(&C::from_i64(-1))
}
fn sub(&self, other: &Self) -> Self {
self.add(&other.neg())
}
fn format(&self) -> String {
if self.is_zero() {
return "0".to_string();
}
let one = C::one();
let mut out = Vec::new();
for (p, c) in self.terms() {
let prefix = if *c == one {
String::new()
} else {
format!("{c:?}*")
};
out.push(format!("{prefix}{}{p}", Self::SYMBOL));
}
out.join(" + ")
}
}
pub(crate) trait InPlaceArith<C: Ring>: Sized {
fn add_from(&mut self, other: &Self);
fn add_owned(&mut self, other: Self);
fn sub_from(&mut self, other: &Self);
fn negate(&mut self);
fn scale_by(&mut self, c: &C);
}
macro_rules! impl_linear_ops {
($name:ident) => {
impl<C: $crate::coeff::Ring> core::ops::Add<&$name<C>> for $name<C> {
type Output = $name<C>;
fn add(mut self, rhs: &$name<C>) -> $name<C> {
$crate::sym::InPlaceArith::add_from(&mut self, rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Add<$name<C>> for $name<C> {
type Output = $name<C>;
fn add(mut self, rhs: $name<C>) -> $name<C> {
$crate::sym::InPlaceArith::add_owned(&mut self, rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Add<&$name<C>> for &$name<C> {
type Output = $name<C>;
fn add(self, rhs: &$name<C>) -> $name<C> {
self.clone() + rhs
}
}
impl<C: $crate::coeff::Ring> core::ops::Add<$name<C>> for &$name<C> {
type Output = $name<C>;
fn add(self, rhs: $name<C>) -> $name<C> {
rhs + self
}
}
impl<C: $crate::coeff::Ring> core::ops::Sub<&$name<C>> for $name<C> {
type Output = $name<C>;
fn sub(mut self, rhs: &$name<C>) -> $name<C> {
$crate::sym::InPlaceArith::sub_from(&mut self, rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Sub<$name<C>> for $name<C> {
type Output = $name<C>;
fn sub(mut self, mut rhs: $name<C>) -> $name<C> {
$crate::sym::InPlaceArith::negate(&mut rhs);
$crate::sym::InPlaceArith::add_owned(&mut self, rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Sub<&$name<C>> for &$name<C> {
type Output = $name<C>;
fn sub(self, rhs: &$name<C>) -> $name<C> {
self.clone() - rhs
}
}
impl<C: $crate::coeff::Ring> core::ops::Sub<$name<C>> for &$name<C> {
type Output = $name<C>;
fn sub(self, mut rhs: $name<C>) -> $name<C> {
$crate::sym::InPlaceArith::negate(&mut rhs);
$crate::sym::InPlaceArith::add_from(&mut rhs, self);
rhs
}
}
impl<C: $crate::coeff::Ring> core::ops::Neg for $name<C> {
type Output = $name<C>;
fn neg(mut self) -> $name<C> {
$crate::sym::InPlaceArith::negate(&mut self);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Neg for &$name<C> {
type Output = $name<C>;
fn neg(self) -> $name<C> {
-self.clone()
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<&C> for $name<C> {
type Output = $name<C>;
fn mul(mut self, rhs: &C) -> $name<C> {
$crate::sym::InPlaceArith::scale_by(&mut self, rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<C> for $name<C> {
type Output = $name<C>;
fn mul(mut self, rhs: C) -> $name<C> {
$crate::sym::InPlaceArith::scale_by(&mut self, &rhs);
self
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<&C> for &$name<C> {
type Output = $name<C>;
fn mul(self, rhs: &C) -> $name<C> {
self.clone() * rhs
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<C> for &$name<C> {
type Output = $name<C>;
fn mul(self, rhs: C) -> $name<C> {
self.clone() * &rhs
}
}
impl<C: $crate::coeff::Ring> core::ops::AddAssign<&$name<C>> for $name<C> {
fn add_assign(&mut self, rhs: &$name<C>) {
$crate::sym::InPlaceArith::add_from(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::AddAssign<$name<C>> for $name<C> {
fn add_assign(&mut self, rhs: $name<C>) {
$crate::sym::InPlaceArith::add_owned(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::SubAssign<&$name<C>> for $name<C> {
fn sub_assign(&mut self, rhs: &$name<C>) {
$crate::sym::InPlaceArith::sub_from(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::SubAssign<$name<C>> for $name<C> {
fn sub_assign(&mut self, mut rhs: $name<C>) {
$crate::sym::InPlaceArith::negate(&mut rhs);
$crate::sym::InPlaceArith::add_owned(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::MulAssign<&C> for $name<C> {
fn mul_assign(&mut self, rhs: &C) {
$crate::sym::InPlaceArith::scale_by(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::MulAssign<C> for $name<C> {
fn mul_assign(&mut self, rhs: C) {
$crate::sym::InPlaceArith::scale_by(self, &rhs);
}
}
};
}
macro_rules! impl_product_ops {
($name:ident) => {
impl<C: $crate::coeff::Ring> core::ops::Mul<&$name<C>> for &$name<C> {
type Output = $name<C>;
fn mul(self, rhs: &$name<C>) -> $name<C> {
<$name<C>>::mul(self, rhs)
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<$name<C>> for &$name<C> {
type Output = $name<C>;
fn mul(self, rhs: $name<C>) -> $name<C> {
<$name<C>>::mul(self, &rhs)
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<&$name<C>> for $name<C> {
type Output = $name<C>;
fn mul(self, rhs: &$name<C>) -> $name<C> {
<$name<C>>::mul(&self, rhs)
}
}
impl<C: $crate::coeff::Ring> core::ops::Mul<$name<C>> for $name<C> {
type Output = $name<C>;
fn mul(self, rhs: $name<C>) -> $name<C> {
<$name<C>>::mul(&self, &rhs)
}
}
impl<C: $crate::coeff::Ring> core::ops::MulAssign<&$name<C>> for $name<C> {
fn mul_assign(&mut self, rhs: &$name<C>) {
*self = <$name<C>>::mul(self, rhs);
}
}
impl<C: $crate::coeff::Ring> core::ops::MulAssign<$name<C>> for $name<C> {
fn mul_assign(&mut self, rhs: $name<C>) {
*self = <$name<C>>::mul(self, &rhs);
}
}
};
}
pub(crate) use impl_linear_ops;
pub(crate) use impl_product_ops;
macro_rules! basis {
($(#[$m:meta])* $name:ident, $sym:literal) => {
$(#[$m])*
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct $name<C: Ring>(BTreeMap<Partition, C>);
impl<C: Ring> SymFn<C> for $name<C> {
const SYMBOL: &'static str = $sym;
fn terms(&self) -> &BTreeMap<Partition, C> { &self.0 }
fn terms_mut(&mut self) -> &mut BTreeMap<Partition, C> { &mut self.0 }
fn from_terms(terms: BTreeMap<Partition, C>) -> Self { $name(terms) }
}
impl<C: Ring> InPlaceArith<C> for $name<C> {
fn add_from(&mut self, other: &Self) {
for (p, c) in other.terms() {
self.add_term(p.clone(), c.clone());
}
}
fn add_owned(&mut self, mut other: Self) {
if self.terms().len() < other.terms().len() {
std::mem::swap(self, &mut other);
}
for (p, c) in std::mem::take(other.terms_mut()) {
self.add_term(p, c);
}
}
fn sub_from(&mut self, other: &Self) {
for (p, c) in other.terms() {
self.add_term(p.clone(), c.neg());
}
}
fn negate(&mut self) {
for c in self.terms_mut().values_mut() {
*c = c.neg();
}
}
fn scale_by(&mut self, c: &C) {
let terms = self.terms_mut();
if c.is_zero() {
terms.clear();
return;
}
for v in terms.values_mut() {
*v = v.mul(c);
}
terms.retain(|_, v| !v.is_zero());
}
}
impl_linear_ops!($name);
impl<C: Ring> core::fmt::Display for $name<C> {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
f.write_str(&self.format())
}
}
};
}
basis!(
Schur, "s"
);
basis!(
PowerSum, "p"
);
basis!(
Monomial, "m"
);
basis!(
Elementary, "e"
);
basis!(
Homogeneous, "h"
);
basis!(
Forgotten, "f"
);
basis!(
St, "st"
);
basis!(
Ht, "ht"
);
pub(crate) fn add_at<C: Ring>(map: &mut BTreeMap<Partition, C>, p: &Partition, c: C) {
if c.is_zero() {
return;
}
if let Some(e) = map.get_mut(p) {
e.add_assign(&c);
if e.is_zero() {
map.remove(p);
}
} else {
map.insert(p.clone(), c);
}
}
pub(crate) fn by_degree<C: Ring, S: SymFn<C>>(f: &S) -> BTreeMap<u32, Vec<(&Partition, &C)>> {
let mut groups: BTreeMap<u32, Vec<(&Partition, &C)>> = BTreeMap::new();
for (mu, c) in f.terms() {
groups.entry(mu.size()).or_default().push((mu, c));
}
groups
}
fn multiplicative_product<C: Ring, S: SymFn<C>>(a: &S, b: &S) -> S {
let mut out = S::zero();
for (mu, cmu) in a.terms() {
crate::interrupt::poll();
for (nu, cnu) in b.terms() {
let mut parts = mu.parts().to_vec();
parts.extend_from_slice(nu.parts());
out.add_term(Partition::new(parts), cmu.mul(cnu));
}
}
out
}
impl<C: Ring> Schur<C> {
pub fn mul_with<B: LrBackend>(&self, other: &Self, backend: &B) -> Self {
let mut out = BTreeMap::new();
for (mu, cmu) in self.terms() {
for (nu, cnu) in other.terms() {
crate::interrupt::poll();
let cprod = cmu.mul(cnu);
let product = backend.schur_product_shared(mu, nu);
let terms = product.iter().filter_map(|(lambda, k)| {
let c = C::from_u128(*k).mul(&cprod);
(!c.is_zero()).then_some((lambda, c))
});
if out.is_empty() {
let mut sorted = Vec::with_capacity(product.len());
sorted.extend(terms.map(|(lambda, c)| (lambda.clone(), c)));
out = sorted.into_iter().collect();
} else {
for (lambda, c) in terms {
add_at(&mut out, lambda, c);
}
}
}
}
Schur(out)
}
pub fn mul(&self, other: &Self) -> Self {
self.mul_with(other, &AutoLr)
}
}
impl<C: Ring> PowerSum<C> {
pub fn mul(&self, other: &Self) -> Self {
multiplicative_product(self, other)
}
}
impl<C: Ring> Elementary<C> {
pub fn mul(&self, other: &Self) -> Self {
multiplicative_product(self, other)
}
}
impl<C: Ring> Homogeneous<C> {
pub fn mul(&self, other: &Self) -> Self {
multiplicative_product(self, other)
}
}
impl<C: Ring> Monomial<C> {
pub fn mul(&self, other: &Self) -> Self {
let mut out = Self::zero();
for (mu, cmu) in self.terms() {
for (nu, cnu) in other.terms() {
let c = cmu.mul(cnu);
if c.is_zero() {
continue;
}
overlays(mu, nu, &mut |lambda: &[u32]| {
out.add_term(Partition::new(lambda.iter().copied()), c.clone());
});
}
}
out
}
}
impl_product_ops!(Schur);
impl_product_ops!(PowerSum);
impl_product_ops!(Elementary);
impl_product_ops!(Homogeneous);
impl_product_ops!(Monomial);
fn overlays(mu: &Partition, nu: &Partition, emit: &mut impl FnMut(&[u32])) {
let n = mu.len() + nu.len();
let mut a = crate::eval::multiplicities(mu);
let mut b = crate::eval::multiplicities(nu);
let mut sum = vec![0u32; n];
walk(
&mut sum,
0,
u32::MAX,
&mut a,
&mut b,
mu.len(),
nu.len(),
emit,
);
}
#[allow(clippy::too_many_arguments)]
fn walk(
sum: &mut [u32],
slot: usize,
prev: u32,
a: &mut [(u32, u32)],
b: &mut [(u32, u32)],
left_a: usize,
left_b: usize,
emit: &mut impl FnMut(&[u32]),
) {
if left_a == 0 && left_b == 0 {
emit(&sum[..slot]);
return;
}
if sum.len() - slot < left_a.max(left_b) {
return;
}
let (na, nb) = (a.len(), b.len());
for i in 0..=na {
let va = if i == na {
0
} else if a[i].1 == 0 {
continue;
} else {
a[i].0
};
for j in 0..=nb {
let vb = if j == nb {
0
} else if b[j].1 == 0 {
continue;
} else {
b[j].0
};
if i == na && j == nb {
continue;
}
if va + vb > prev {
continue;
}
if i < na {
a[i].1 -= 1;
}
if j < nb {
b[j].1 -= 1;
}
sum[slot] = va + vb;
walk(
sum,
slot + 1,
va + vb,
a,
b,
left_a - usize::from(i < na),
left_b - usize::from(j < nb),
emit,
);
if i < na {
a[i].1 += 1;
}
if j < nb {
b[j].1 += 1;
}
}
}
sum[slot] = 0;
}
pub trait SymAlgebra<C: Ring>: SymFn<C> {
fn unit() -> Self {
Self::monomial(Partition::default(), C::one())
}
fn times(&self, other: &Self) -> Self;
}
impl<C: Ring> SymAlgebra<C> for Homogeneous<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
impl<C: Ring> SymAlgebra<C> for Elementary<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
impl<C: Ring> SymAlgebra<C> for PowerSum<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
impl<C: Ring> SymAlgebra<C> for Schur<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
impl<C: Ring> SymAlgebra<C> for Monomial<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
#[cfg(test)]
mod tests {
use super::*;
fn s(parts: &[u32], c: i64) -> Schur<i64> {
Schur::monomial(Partition::new(parts.iter().copied()), c)
}
#[test]
fn monomial_product_agrees_with_the_schur_route() {
use crate::memo::partitions_cached;
for a in 0..=4u32 {
for b in 0..=4u32 {
for mu in partitions_cached(a).iter() {
for nu in partitions_cached(b).iter() {
let x: Monomial<i64> = Monomial::monomial(mu.clone(), 1);
let y: Monomial<i64> = Monomial::monomial(nu.clone(), 1);
assert_eq!(x.mul(&y), x.mul_via_schur(&y), "m_{mu} · m_{nu}");
}
}
}
}
}
#[test]
fn monomial_product_evaluates_as_a_product() {
use crate::memo::partitions_cached;
let xs = [2i64, -1, 3, 1, -2, 4];
for a in 0..=4u32 {
for b in 0..=4u32 {
for mu in partitions_cached(a).iter() {
for nu in partitions_cached(b).iter() {
let x: Monomial<i64> = Monomial::monomial(mu.clone(), 1);
let y: Monomial<i64> = Monomial::monomial(nu.clone(), 1);
assert_eq!(
x.mul(&y).eval(&xs),
x.eval(&xs) * y.eval(&xs),
"m_{mu} · m_{nu} at the alphabet"
);
}
}
}
}
}
#[test]
fn monomial_product_is_not_a_multiset_union() {
let m1: Monomial<i64> = Monomial::monomial(Partition::new([1]), 1);
let sq = m1.mul(&m1);
assert_eq!(sq.coeff(&Partition::new([1, 1])), 2);
assert_eq!(sq.coeff(&Partition::new([2])), 1);
assert_eq!(sq.terms().len(), 2);
}
#[test]
fn schur_product_matches_known_expansion() {
let prod = s(&[2], 1).mul(&s(&[1], 1));
assert_eq!(prod.coeff(&Partition::new([3])), 1);
assert_eq!(prod.coeff(&Partition::new([2, 1])), 1);
assert_eq!(prod.terms().len(), 2);
}
#[test]
fn schur_product_is_commutative() {
let a = s(&[2, 1], 1);
let b = s(&[2], 1).add(&s(&[1, 1], 1));
assert_eq!(a.mul(&b), b.mul(&a));
}
#[test]
fn schur_multiplicity_two_survives_scaling() {
let prod = s(&[2, 1], 3).mul(&s(&[2, 1], 1));
assert_eq!(prod.coeff(&Partition::new([3, 2, 1])), 6);
}
#[test]
fn schur_product_matches_term_by_term_accumulation() {
use crate::lr::NaiveLr;
let a = s(&[2, 1], 1).add(&s(&[3], -1)).add(&s(&[1, 1, 1], 2));
let b = s(&[2], 1).add(&s(&[1, 1], -1)).add(&s(&[3, 1], 1));
let mut want: Schur<i64> = Schur::zero();
for (mu, cmu) in a.terms() {
for (nu, cnu) in b.terms() {
for (lambda, k) in NaiveLr.schur_product(mu, nu) {
want.add_term(lambda, i64::try_from(k).unwrap() * cmu * cnu);
}
}
}
assert_eq!(a.mul(&b), want);
assert_eq!(a.mul_with(&b, &NaiveLr), want);
assert!(want.terms().values().all(|c| *c != 0));
}
#[test]
fn schur_product_drops_a_term_that_cancels_across_pairs() {
let a = s(&[2], 1).add(&s(&[1, 1], -1));
let prod = a.mul(&s(&[1], 1));
assert_eq!(prod, s(&[3], 1).add(&s(&[1, 1, 1], -1)));
assert_eq!(prod.terms().len(), 2);
assert!(!prod.terms().contains_key(&Partition::new([2, 1])));
let mut f = s(&[2, 1], 4);
f.add_term(Partition::new([2, 1]), -4);
assert!(f.is_zero());
}
#[test]
fn schur_product_with_zero_is_zero() {
let a = s(&[2, 1], 1).add(&s(&[3], -1));
let zero: Schur<i64> = Schur::zero();
assert!(a.mul(&zero).is_zero());
assert!(zero.mul(&a).is_zero());
assert!(zero.mul(&zero).is_zero());
}
#[test]
fn power_sum_product_is_multiset_union() {
let a: PowerSum<i64> = PowerSum::monomial(Partition::new([2]), 1);
let b: PowerSum<i64> = PowerSum::monomial(Partition::new([3, 1]), 1);
let prod = a.mul(&b);
assert_eq!(prod.coeff(&Partition::new([3, 2, 1])), 1);
assert_eq!(prod.terms().len(), 1);
}
#[test]
fn elementary_and_homogeneous_products_are_multiplicative() {
let e: Elementary<i64> = Elementary::monomial(Partition::new([2]), 1);
let e1: Elementary<i64> = Elementary::monomial(Partition::new([1]), 1);
assert_eq!(e.mul(&e1).coeff(&Partition::new([2, 1])), 1);
let h: Homogeneous<i64> = Homogeneous::monomial(Partition::new([1, 1]), 1);
let h2: Homogeneous<i64> = Homogeneous::monomial(Partition::new([2]), 1);
let prod = h.mul(&h2);
assert_eq!(prod.coeff(&Partition::new([2, 1, 1])), 1);
assert_eq!(prod.terms().len(), 1);
}
#[test]
fn display_omits_unit_coefficient() {
let f = s(&[2], 1).add(&s(&[1, 1], 3));
assert_eq!(f.to_string(), "3*s[1,1] + s[2]");
}
}