use crate::coeff::Ring;
use crate::convert::ToSchur;
use crate::memo::partitions_cached;
use crate::partition::Partition;
use crate::sym::{
impl_linear_ops, Elementary, Forgotten, Homogeneous, InPlaceArith, Monomial, PowerSum, Schur,
SymFn,
};
use std::collections::BTreeMap;
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct SymTensor<C: Ring>(BTreeMap<(Partition, Partition), C>);
impl<C: Ring> SymTensor<C> {
pub fn zero() -> Self {
SymTensor(BTreeMap::new())
}
pub fn terms(&self) -> &BTreeMap<(Partition, Partition), C> {
&self.0
}
pub fn is_zero(&self) -> bool {
self.0.is_empty()
}
pub fn coeff(&self, mu: &Partition, nu: &Partition) -> C {
self.0
.get(&(mu.clone(), nu.clone()))
.cloned()
.unwrap_or_else(C::zero)
}
pub fn add_term(&mut self, key: (Partition, Partition), c: C) {
if c.is_zero() {
return;
}
let now_zero = {
let e = self.0.entry(key.clone()).or_insert_with(C::zero);
e.add_assign(&c);
e.is_zero()
};
if now_zero {
self.0.remove(&key);
}
}
pub fn add(&self, other: &Self) -> Self {
let mut out = self.clone();
for (k, c) in &other.0 {
out.add_term(k.clone(), c.clone());
}
out
}
}
impl<C: Ring> InPlaceArith<C> for SymTensor<C> {
fn add_from(&mut self, other: &Self) {
for (k, c) in &other.0 {
self.add_term(k.clone(), c.clone());
}
}
fn add_owned(&mut self, mut other: Self) {
if self.0.len() < other.0.len() {
std::mem::swap(self, &mut other);
}
for (k, c) in std::mem::take(&mut other.0) {
self.add_term(k, c);
}
}
fn sub_from(&mut self, other: &Self) {
for (k, c) in &other.0 {
self.add_term(k.clone(), c.neg());
}
}
fn negate(&mut self) {
for c in self.0.values_mut() {
*c = c.neg();
}
}
fn scale_by(&mut self, c: &C) {
if c.is_zero() {
self.0.clear();
return;
}
for v in self.0.values_mut() {
*v = v.mul(c);
}
self.0.retain(|_, v| !v.is_zero());
}
}
impl_linear_ops!(SymTensor);
pub fn skew_schur<C: Ring>(lambda: &Partition, mu: &Partition) -> Schur<C> {
let mut out = Schur::zero();
if !lambda.contains(mu) {
return out;
}
for (nu, c) in crate::skew_lr::expand_skew_shared(lambda, mu).iter() {
crate::interrupt::poll();
out.add_term(nu.clone(), C::from_u128(*c));
}
out
}
pub trait SkewBy<C: Ring, G> {
fn skew_by(&self, g: &G) -> Self;
}
impl<C: Ring> SkewBy<C, Schur<C>> for Schur<C> {
fn skew_by(&self, g: &Schur<C>) -> Self {
let mut out = Schur::zero();
for (lambda, c) in self.terms() {
for (mu, d) in g.terms() {
if !lambda.contains(mu) {
continue;
}
let cd = c.mul(d);
if cd.is_zero() {
continue;
}
for (nu, k) in crate::skew_lr::expand_skew_shared(lambda, mu).iter() {
out.add_term(nu.clone(), C::from_u128(*k).mul(&cd));
}
}
}
out
}
}
impl<C: Ring> SkewBy<C, Homogeneous<C>> for Schur<C> {
fn skew_by(&self, g: &Homogeneous<C>) -> Self {
let mut out = Schur::zero();
for (mu, d) in g.terms() {
let mut acc = self.clone();
for &r in mu.parts() {
acc = strip_off(&acc, r);
if acc.is_zero() {
break;
}
}
out = out.add(&acc.scale(d));
}
out
}
}
impl<C: Ring> SkewBy<C, Elementary<C>> for Schur<C> {
fn skew_by(&self, g: &Elementary<C>) -> Self {
let as_h = Homogeneous::from_terms(g.terms().clone());
SkewBy::skew_by(&self.omega(), &as_h).omega()
}
}
impl<C: Ring> SkewBy<C, PowerSum<C>> for Schur<C> {
fn skew_by(&self, g: &PowerSum<C>) -> Self {
let mut out = Schur::zero();
for (mu, d) in g.terms() {
let mut acc = self.clone();
for &r in mu.parts() {
let mut next = Schur::zero();
for (lambda, c) in acc.terms() {
for (nu, height) in crate::character::border_strips(lambda, r) {
next.add_term(nu, if height % 2 == 1 { c.neg() } else { c.clone() });
}
}
acc = next;
if acc.is_zero() {
break;
}
}
out = out.add(&acc.scale(d));
}
out
}
}
impl<C: Ring> SkewBy<C, Monomial<C>> for Schur<C> {
fn skew_by(&self, g: &Monomial<C>) -> Self {
SkewBy::skew_by(self, &g.to_schur())
}
}
impl<C: Ring> SkewBy<C, Forgotten<C>> for Schur<C> {
fn skew_by(&self, g: &Forgotten<C>) -> Self {
SkewBy::skew_by(self, &g.to_schur())
}
}
pub(crate) fn strip_off<C: Ring>(f: &Schur<C>, r: u32) -> Schur<C> {
let mut out = Schur::zero();
let mut found: Vec<Partition> = Vec::new();
for (lambda, c) in f.terms() {
crate::interrupt::poll();
found.clear();
let mut cur = lambda.parts().to_vec();
remove_horizontal(lambda.parts(), 0, r, &mut cur, &mut |nu| {
found.push(Partition::from_sorted(
nu.iter().copied().filter(|&v| v > 0).collect(),
));
});
for nu in found.drain(..) {
out.add_term(nu, c.clone());
}
}
out
}
fn remove_horizontal(
lam: &[u32],
i: usize,
left: u32,
cur: &mut Vec<u32>,
emit: &mut impl FnMut(&[u32]),
) {
if i == lam.len() {
if left == 0 {
emit(cur);
}
return;
}
if left > lam[i] {
return; }
let floor = if i + 1 < lam.len() { lam[i + 1] } else { 0 };
let lo = floor.max(lam[i] - left);
for v in lo..=lam[i] {
cur[i] = v;
remove_horizontal(lam, i + 1, left - (lam[i] - v), cur, emit);
}
cur[i] = lam[i];
}
pub fn coproduct<C: Ring>(f: &Schur<C>) -> SymTensor<C> {
let mut out = SymTensor::zero();
for (lambda, c) in f.terms() {
crate::interrupt::poll();
for k in 0..=lambda.size() {
for mu in partitions_cached(k).iter() {
if !lambda.contains(mu) {
continue;
}
for (nu, coeff) in crate::skew_lr::expand_skew_shared(lambda, mu).iter() {
out.add_term((mu.clone(), nu.clone()), C::from_u128(*coeff).mul(c));
}
}
}
}
out
}
pub fn counit<C: Ring>(f: &Schur<C>) -> C {
f.coeff(&Partition::default())
}
pub fn antipode<C: Ring>(f: &Schur<C>) -> Schur<C> {
let mut out = Schur::zero();
for (lambda, c) in f.terms() {
crate::interrupt::poll();
let coeff = if lambda.size() % 2 == 1 {
c.neg()
} else {
c.clone()
};
out.add_term(lambda.conjugate(), coeff);
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn s(v: &[u32]) -> Schur<i64> {
Schur::monomial(part(v), 1)
}
#[test]
fn skew_schur_known_value() {
let sk: Schur<i64> = skew_schur(&part(&[2, 1]), &part(&[1]));
assert_eq!(sk.coeff(&part(&[2])), 1);
assert_eq!(sk.coeff(&part(&[1, 1])), 1);
assert_eq!(sk.terms().len(), 2);
}
#[test]
fn skewing_is_adjoint_to_multiplication() {
for df in 0..=6u32 {
for dg in 0..=df {
for lambda in partitions_cached(df).iter() {
let f: Schur<i64> = Schur::monomial(lambda.clone(), 1);
for mu in partitions_cached(dg).iter() {
let g: Schur<i64> = Schur::monomial(mu.clone(), 1);
let skewed = SkewBy::skew_by(&f, &g);
for nu in partitions_cached(df - dg).iter() {
let h: Schur<i64> = Schur::monomial(nu.clone(), 1);
let lhs = crate::ops::hall::<i64, _, _>(&skewed, &h);
let rhs = crate::ops::hall::<i64, _, _>(&f, &g.mul(&h));
assert_eq!(lhs, rhs, "<{mu}^perp s_{lambda}, s_{nu}>");
}
}
}
}
}
}
#[test]
fn native_skew_rules_match_the_lr_route() {
for df in 0..=6u32 {
for dg in 0..=df {
for lambda in partitions_cached(df).iter() {
let f: Schur<Rational> = Schur::monomial(lambda.clone(), Rational::from_int(1));
for mu in partitions_cached(dg).iter() {
let one = Rational::from_int(1);
let gh: Homogeneous<Rational> = Homogeneous::monomial(mu.clone(), one);
assert_eq!(
SkewBy::skew_by(&f, &gh),
SkewBy::skew_by(&f, &gh.to_schur()),
"h_{mu}^perp s_{lambda}"
);
let ge: Elementary<Rational> = Elementary::monomial(mu.clone(), one);
assert_eq!(
SkewBy::skew_by(&f, &ge),
SkewBy::skew_by(&f, &ge.to_schur()),
"e_{mu}^perp s_{lambda}"
);
let gp: PowerSum<Rational> = PowerSum::monomial(mu.clone(), one);
assert_eq!(
SkewBy::skew_by(&f, &gp),
SkewBy::skew_by(&f, &gp.to_schur()),
"p_{mu}^perp s_{lambda}"
);
let gm: Monomial<Rational> = Monomial::monomial(mu.clone(), one);
assert_eq!(
SkewBy::skew_by(&f, &gm),
SkewBy::skew_by(&f, &gm.to_schur()),
"m_{mu}^perp s_{lambda}"
);
}
}
}
}
}
#[test]
fn skewing_by_power_sums_stays_integral() {
for df in 1..=6u32 {
for dg in 1..=df {
for lambda in partitions_cached(df).iter() {
for mu in partitions_cached(dg).iter() {
let f: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let g: PowerSum<i64> = PowerSum::monomial(mu.clone(), 1);
let got = SkewBy::skew_by(&f, &g);
let fr: Schur<Rational> =
Schur::monomial(lambda.clone(), Rational::from_int(1));
let gr: PowerSum<Rational> =
PowerSum::monomial(mu.clone(), Rational::from_int(1));
let want = SkewBy::skew_by(&fr, &gr.to_schur());
assert_eq!(got.terms().len(), want.terms().len(), "{mu} on {lambda}");
for (nu, c) in got.terms() {
assert_eq!(
Rational::from_int((*c).into()),
want.coeff(nu),
"p_{mu}^perp s_{lambda} at {nu}"
);
}
}
}
}
}
}
#[test]
fn skew_by_reproduces_the_classical_special_cases() {
let lam = part(&[3, 2, 1]);
let f: Schur<i64> = Schur::monomial(lam.clone(), 1);
for mu in partitions_cached(2).iter() {
let g: Schur<i64> = Schur::monomial(mu.clone(), 1);
assert_eq!(SkewBy::skew_by(&f, &g), skew_schur(&lam, mu), "s_{mu}^perp");
}
let h1: Homogeneous<i64> = Homogeneous::monomial(part(&[1]), 1);
let one_off = SkewBy::skew_by(&f, &h1);
assert_eq!(one_off.coeff(&part(&[2, 2, 1])), 1);
assert_eq!(one_off.coeff(&part(&[3, 1, 1])), 1);
assert_eq!(one_off.coeff(&part(&[3, 2])), 1);
assert_eq!(one_off.terms().len(), 3);
}
#[test]
fn skewing_is_degree_lowering() {
let f: Schur<i64> = Schur::monomial(part(&[2, 1]), 1);
let big: Homogeneous<i64> = Homogeneous::monomial(part(&[4]), 1);
assert!(SkewBy::skew_by(&f, &big).is_zero());
let exact: Homogeneous<i64> = Homogeneous::monomial(part(&[2, 1]), 1);
let r = SkewBy::skew_by(&f, &exact);
assert_eq!(r.degree(), Some(0));
}
#[test]
fn coproduct_known_values() {
let d1 = coproduct(&s(&[1]));
assert_eq!(d1.coeff(&part(&[]), &part(&[1])), 1);
assert_eq!(d1.coeff(&part(&[1]), &part(&[])), 1);
assert_eq!(d1.terms().len(), 2);
let d2 = coproduct(&s(&[2]));
assert_eq!(d2.coeff(&part(&[]), &part(&[2])), 1);
assert_eq!(d2.coeff(&part(&[1]), &part(&[1])), 1);
assert_eq!(d2.coeff(&part(&[2]), &part(&[])), 1);
assert_eq!(d2.terms().len(), 3);
}
#[test]
fn antipode_and_counit() {
assert_eq!(antipode(&s(&[2])).coeff(&part(&[1, 1])), 1); assert_eq!(antipode(&s(&[1])).coeff(&part(&[1])), -1); assert_eq!(counit(&s(&[])), 1);
assert_eq!(counit(&s(&[2])), 0);
}
fn antipode_axiom(f: &Schur<i64>) -> Schur<i64> {
let d = coproduct(f);
let mut acc = Schur::zero();
for ((mu, nu), c) in d.terms() {
let left = antipode(&Schur::monomial(mu.clone(), 1));
let prod = left.mul(&Schur::monomial(nu.clone(), 1)).scale(c);
acc = acc.add(&prod);
}
acc
}
#[test]
fn hopf_antipode_axiom_holds() {
for parts in [&[1][..], &[2], &[2, 1], &[3, 1]] {
assert!(antipode_axiom(&s(parts)).is_zero(), "axiom at {:?}", parts);
}
let unit = antipode_axiom(&s(&[]));
assert_eq!(unit.coeff(&part(&[])), 1);
assert_eq!(unit.terms().len(), 1);
}
}