#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::coeff::Ring;
use crate::partition::Partition;
use crate::permutation::Perm;
use crate::sym::{impl_linear_ops, impl_product_ops, InPlaceArith, Schur};
use std::collections::{BTreeMap, HashMap};
pub type Expo = Vec<u32>;
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct Schubert<C: Ring> {
terms: BTreeMap<Perm, C>,
}
impl<C: Ring> Default for Schubert<C> {
fn default() -> Self {
Schubert::zero()
}
}
fn strip(mut e: Expo) -> Expo {
while e.last() == Some(&0) {
e.pop();
}
e
}
impl<C: Ring> Schubert<C> {
pub fn zero() -> Self {
Schubert {
terms: BTreeMap::new(),
}
}
pub fn monomial(w: Perm, c: C) -> Self {
let mut t = BTreeMap::new();
if !c.is_zero() {
t.insert(w, c);
}
Schubert { terms: t }
}
pub fn one() -> Self {
Schubert::monomial(Perm::identity(), C::one())
}
pub fn terms(&self) -> &BTreeMap<Perm, C> {
&self.terms
}
pub fn is_zero(&self) -> bool {
self.terms.is_empty()
}
pub fn coeff(&self, w: &Perm) -> C {
self.terms.get(w).cloned().unwrap_or_else(C::zero)
}
pub fn add_term(&mut self, w: Perm, c: &C) {
if c.is_zero() {
return;
}
match self.terms.get_mut(&w) {
Some(slot) => {
slot.add_assign(c);
if slot.is_zero() {
self.terms.remove(&w);
}
}
None => {
self.terms.insert(w, c.clone());
}
}
}
pub fn add(&self, other: &Self) -> Self {
let mut out = self.clone();
out.add_assign(other);
out
}
pub fn add_assign(&mut self, other: &Self) {
for (w, c) in &other.terms {
self.add_term(*w, c);
}
}
pub fn sub(&self, other: &Self) -> Self {
let mut out = self.clone();
for (w, c) in &other.terms {
out.add_term(*w, &c.neg());
}
out
}
pub fn scale(&self, c: &C) -> Self {
let mut out = Schubert::zero();
for (w, a) in &self.terms {
out.add_term(*w, &a.mul(c));
}
out
}
}
impl<C: Ring> InPlaceArith<C> for Schubert<C> {
fn add_from(&mut self, other: &Self) {
self.add_assign(other);
}
fn add_owned(&mut self, mut other: Self) {
if self.terms.len() < other.terms.len() {
std::mem::swap(self, &mut other);
}
for (w, c) in std::mem::take(&mut other.terms) {
self.add_term(w, &c);
}
}
fn sub_from(&mut self, other: &Self) {
for (w, c) in &other.terms {
self.add_term(*w, &c.neg());
}
}
fn negate(&mut self) {
for c in self.terms.values_mut() {
*c = c.neg();
}
}
fn scale_by(&mut self, c: &C) {
if c.is_zero() {
self.terms.clear();
return;
}
for v in self.terms.values_mut() {
*v = v.mul(c);
}
self.terms.retain(|_, v| !v.is_zero());
}
}
impl_linear_ops!(Schubert);
impl_product_ops!(Schubert);
impl<C: Ring> Schubert<C> {
pub fn grassmannian(lambda: &Partition, k: u32) -> Option<Self> {
if lambda.len() as u32 > k {
return None;
}
Some(Schubert::monomial(grassmannian_perm(lambda, k)?, C::one()))
}
pub fn mul_variable(&self, i: u32) -> Self {
assert!(i >= 1, "variable indices are 1-based");
let mut out = Schubert::zero();
for (w, c) in &self.terms {
for (_, u) in w.covers_right(i) {
out.add_term(u, c);
}
let neg = c.neg();
for (_, u) in w.covers_left(i) {
out.add_term(u, &neg);
}
}
out
}
pub fn divided_difference(&self, i: u32) -> Self {
assert!(i >= 1, "variable indices are 1-based");
let mut out = Schubert::zero();
for (w, c) in &self.terms {
if w.at(i) > w.at(i + 1) {
out.add_term(w.transpose(i, i + 1), c);
}
}
out
}
pub fn divided_difference_perm(&self, w: &Perm) -> Self {
let mut out = self.clone();
for i in w.reduced_word() {
out = out.divided_difference(i);
if out.is_zero() {
break;
}
}
out
}
pub fn expand(&self) -> Vec<(Expo, C)> {
let mut acc: BTreeMap<Expo, C> = BTreeMap::new();
let mut memo = PeelMemo::default();
for (w, c) in &self.terms {
for (e, k) in memo.peel_perm(w) {
let term = c.mul(&C::from_u128(k));
match acc.get_mut(&e) {
Some(slot) => {
slot.add_assign(&term);
if slot.is_zero() {
acc.remove(&e);
}
}
None => {
if !term.is_zero() {
acc.insert(e, term);
}
}
}
}
}
acc.into_iter().collect()
}
pub fn from_polynomial(terms: &[(Expo, C)]) -> Self {
let mut rem: BTreeMap<Expo, C> = BTreeMap::new();
for (e, c) in terms {
if c.is_zero() {
continue;
}
let e = strip(e.clone());
match rem.get_mut(&e) {
Some(slot) => {
slot.add_assign(c);
if slot.is_zero() {
rem.remove(&e);
}
}
None => {
rem.insert(e, c.clone());
}
}
}
let mut out = Schubert::zero();
let mut memo = PeelMemo::default();
while let Some((alpha, c)) = rem.iter().next().map(|(a, c)| (a.clone(), c.clone())) {
let w = Perm::from_code(&alpha);
out.add_term(w, &c);
for (e, k) in memo.peel_perm(&w) {
let sub = c.mul(&C::from_u128(k)).neg();
match rem.get_mut(&e) {
Some(slot) => {
slot.add_assign(&sub);
if slot.is_zero() {
rem.remove(&e);
}
}
None => {
if !sub.is_zero() {
rem.insert(e, sub);
}
}
}
}
debug_assert!(
!rem.contains_key(&alpha),
"peel failed to clear its own lex-minimal monomial — triangularity violated"
);
}
out
}
pub fn mul_naive(&self, other: &Self) -> Self {
if self.is_zero() || other.is_zero() {
return Schubert::zero();
}
let (expand_side, keep_side) = if total_dimension(self) <= total_dimension(other) {
(self, other)
} else {
(other, self)
};
let mut out = Schubert::zero();
for (alpha, c) in expand_side.expand() {
let mut t = keep_side.clone();
for (j, &e) in alpha.iter().enumerate() {
for _ in 0..e {
t = t.mul_variable((j + 1) as u32);
}
}
for (w, a) in &t.terms {
out.add_term(*w, &a.mul(&c));
}
}
out
}
pub fn mul(&self, other: &Self) -> Self {
self.mul_e2(other)
}
pub fn mul_e3(&self, other: &Self) -> Self {
if self.is_zero() || other.is_zero() {
return Schubert::zero();
}
let (peel_side, keep_side) = if total_states(self) <= total_states(other) {
(self, other)
} else {
(other, self)
};
let mut out = Schubert::zero();
for (w, c) in peel_side.terms() {
let part = E3 {
keep: keep_side,
memo: HashMap::new(),
}
.eval_perm(w);
for (v, a) in &part.terms {
out.add_term(*v, &a.mul(c));
}
}
out
}
pub fn mul_e2(&self, other: &Self) -> Self {
self.mul_e2_depth(other, 4096).0
}
pub fn mul_e2_depth(&self, other: &Self, cap: u32) -> (Self, u64, u64) {
if self.is_zero() || other.is_zero() {
return (Schubert::zero(), 0, 0);
}
let mut out = Schubert::zero();
let (mut nodes, mut passes) = (0u64, 0u64);
for (w, c) in other.terms() {
let mut refs = HashMap::new();
count_transition_parents(w, &mut refs);
let mut e2 = E2 {
keep: self,
target: None,
memo: HashMap::new(),
refs,
cap,
passes: 0,
nodes: 0,
peak_live: 0,
};
let part = e2.eval(w, 0);
nodes += e2.nodes;
passes += e2.passes;
for (v, a) in &part.terms {
out.add_term(*v, &a.mul(c));
}
}
(out, nodes, passes)
}
pub fn pairing(&self, other: &Self, n: u32) -> C {
let w0 = Perm::new((1..=n).rev())
.expect("the reversal of 1..=n is a permutation unless n > MAX_SUPPORT");
self.mul(other).coeff(&w0)
}
pub fn scalar_product(&self, other: &Self, n: u32) -> Self {
let w0 = Perm::new((1..=n).rev())
.expect("the reversal of 1..=n is a permutation unless n > MAX_SUPPORT");
self.mul(other).divided_difference_perm(&w0)
}
}
pub fn grassmannian_perm(lambda: &Partition, k: u32) -> Option<Perm> {
if lambda.len() as u32 > k {
return None;
}
let k = k as usize;
let mut head: Vec<u32> = Vec::with_capacity(k);
for i in 1..=k {
head.push(lambda.part(k - i) + i as u32);
}
let n = head.iter().copied().max().unwrap_or(0);
let used: std::collections::BTreeSet<u32> = head.iter().copied().collect();
let mut v = head;
v.extend((1..=n).filter(|x| !used.contains(x)));
Perm::new(v).ok()
}
fn shift_up(w: &Perm) -> Perm {
let m = w.support_len();
let mut v = Vec::with_capacity(m as usize + 1);
v.push(1);
for i in 1..=m {
v.push(w.at(i) + 1);
}
Perm::new(v).expect("the shift 1 x w is a permutation unless it exceeds MAX_SUPPORT")
}
pub fn stanley<C: Ring>(w: &Perm) -> Schur<C> {
use crate::sym::SymFn;
let mut out: Schur<C> = Schur::zero();
let mut stack = vec![*w];
let mut steps = 0u64;
while let Some(p) = stack.pop() {
crate::interrupt::poll();
steps += 1;
assert!(
steps < 1 << 24,
"stanley: transition tree failed to terminate"
);
let Some(r) = p.last_descent() else {
let lambda = Partition::default();
let c = out.coeff(&lambda);
let mut c = c;
c.add_assign(&C::one());
out.terms_mut().insert(lambda, c);
continue;
};
if p.is_grassmannian().is_some() {
let lambda = Partition::new(p.code());
let c = out.coeff(&lambda);
let mut c = c;
c.add_assign(&C::one());
out.terms_mut().insert(lambda, c);
continue;
}
let wr = p.at(r);
let s = (r + 1..=p.support_len())
.rfind(|&s| p.at(s) < wr)
.expect("a descent has something smaller to its right");
let v = p.transpose(r, s);
let before = stack.len();
v.for_each_cover_left(r, |_, u| stack.push(u));
if stack.len() == before {
stack.push(shift_up(&p));
}
}
out
}
pub fn schubert_monomial_mass_of(u: &Perm, v: &Perm) -> u128 {
let count = |w: &Perm| dimension(w).unwrap_or(u128::MAX);
count(u).saturating_mul(count(v))
}
pub fn schubert_coeff<C: Ring>(u: &Perm, v: &Perm, w: &Perm) -> C {
if w.length() != u.length() + v.length() || !u.bruhat_le(w) || !v.bruhat_le(w) {
return C::zero();
}
let (recurse, keep_perm) = if transition_tree(v).0 <= transition_tree(u).0 {
(v, u)
} else {
(u, v)
};
let keep: Schubert<C> = Schubert::monomial(*keep_perm, C::one());
let mut refs = HashMap::new();
count_transition_parents(recurse, &mut refs);
let mut e2 = E2 {
keep: &keep,
target: Some(*w),
memo: HashMap::new(),
refs,
cap: 4096,
passes: 0,
nodes: 0,
peak_live: 0,
};
let out = e2.eval(recurse, 0);
out.coeff(w)
}
pub fn dimension(w: &Perm) -> Option<u128> {
PeelMemo::default().count(w)
}
pub fn peel_states(w: &Perm) -> u64 {
let m = w.support_len();
if m == 0 {
return 1;
}
let n = m;
let mut seen = std::collections::HashSet::new();
let mut stack = vec![(w.padded(m), m.saturating_sub(1))];
while let Some((p, stufe)) = stack.pop() {
crate::interrupt::poll();
let len = p.len() as u32;
if !seen.insert((p.clone(), n - len + 1, stufe)) {
continue;
}
if len <= 2 {
continue;
}
if p[0] == len {
stack.push((p[1..].to_vec(), len.saturating_sub(2)));
} else {
for q in covers_at_1(&p) {
stack.push((q, stufe.saturating_sub(1)));
}
}
}
seen.len() as u64
}
fn total_states<C: Ring>(f: &Schubert<C>) -> u64 {
f.terms()
.keys()
.map(peel_states)
.fold(0u64, |a, b| a.saturating_add(b))
}
struct E2<'a, C: Ring> {
keep: &'a Schubert<C>,
target: Option<Perm>,
memo: HashMap<Perm, std::rc::Rc<Schubert<C>>>,
refs: HashMap<Perm, u32>,
cap: u32,
passes: u64,
nodes: u64,
peak_live: usize,
}
pub fn transition_tree(w: &Perm) -> (u64, u64) {
let mut refs = HashMap::new();
count_transition_parents(w, &mut refs);
let nodes = refs.len() as u64;
let edges: u64 = refs.values().map(|&n| n as u64).sum();
(nodes, edges)
}
fn count_transition_parents(root: &Perm, refs: &mut HashMap<Perm, u32>) {
let mut stack = vec![*root];
let mut expanded = std::collections::HashSet::new();
while let Some(p) = stack.pop() {
crate::interrupt::poll();
*refs.entry(p).or_insert(0) += 1;
if !expanded.insert(p) || p.is_dominant() {
continue;
}
let (_, vp, ups) = p.transition().expect("non-dominant implies a descent");
stack.push(vp);
stack.extend(ups);
}
}
impl<C: Ring> E2<'_, C> {
fn release(&mut self, child: &Perm) {
if let Some(n) = self.refs.get_mut(child) {
*n = n.saturating_sub(1);
if *n == 0 {
self.memo.remove(child);
}
}
}
fn eval(&mut self, v: &Perm, depth: u32) -> std::rc::Rc<Schubert<C>> {
if let Some(r) = self.memo.get(v) {
return std::rc::Rc::clone(r);
}
assert!(
depth < self.cap,
"E2 recursion exceeded depth {} at {v} — the transition tree was \
supposed to be finite",
self.cap
);
let out = if v.is_dominant() {
let mut acc = self.keep.clone();
for (i, &e) in v.code().iter().enumerate() {
for _ in 0..e {
acc = acc.mul_variable(i as u32 + 1);
self.passes += 1;
}
}
acc
} else {
let (r, vp, ups) = v.transition().expect("non-dominant implies a descent");
let child = self.eval(&vp, depth + 1);
let mut acc = child.mul_variable(r);
self.passes += 1;
drop(child);
self.release(&vp);
for u in &ups {
let part = self.eval(u, depth + 1);
acc.add_assign(&part);
drop(part);
self.release(u);
}
acc
};
self.nodes += 1;
let mut out = out;
if let Some(t) = &self.target {
out.terms.retain(|z, _| z.bruhat_le(t));
}
let out = std::rc::Rc::new(out);
self.memo.insert(*v, std::rc::Rc::clone(&out));
self.peak_live = self.peak_live.max(self.memo.len());
out
}
}
struct E3<'a, C: Ring> {
keep: &'a Schubert<C>,
memo: HashMap<(Vec<u32>, u32, u32), std::rc::Rc<Schubert<C>>>,
}
impl<C: Ring> E3<'_, C> {
fn eval_perm(mut self, w: &Perm) -> Schubert<C> {
let m = w.support_len();
if m == 0 {
return self.keep.clone();
}
let v = w.padded(m);
let r = self.eval(&v, m, m.saturating_sub(1));
std::rc::Rc::try_unwrap(r).unwrap_or_else(|rc| (*rc).clone())
}
fn eval(&mut self, p: &[u32], n: u32, stufe: u32) -> std::rc::Rc<Schubert<C>> {
let m = p.len() as u32;
let level = n - m + 1;
let key = (p.to_vec(), level, stufe);
if let Some(v) = self.memo.get(&key) {
return std::rc::Rc::clone(v);
}
let out = if m <= 2 {
if m == 2 && p[0] == 2 {
self.keep.mul_variable(level)
} else {
self.keep.clone()
}
} else if p[0] == m {
let child = self.eval(&p[1..], n, m.saturating_sub(2));
if stufe == 0 {
(*child).clone()
} else {
let mut acc = child.mul_variable(level);
for _ in 1..stufe {
acc = acc.mul_variable(level);
}
acc
}
} else {
let mut acc = Schubert::zero();
for q in covers_at_1(p) {
let part = self.eval(&q, n, stufe.saturating_sub(1));
acc.add_assign(&part);
}
acc
};
let out = std::rc::Rc::new(out);
self.memo.insert(key, std::rc::Rc::clone(&out));
out
}
}
fn total_dimension<C: Ring>(f: &Schubert<C>) -> u128 {
f.terms()
.keys()
.map(|w| dimension(w).unwrap_or(u128::MAX))
.fold(0u128, |a, b| a.saturating_add(b))
}
#[derive(Default)]
struct PeelMemo {
poly: HashMap<(Vec<u32>, u32, u32), Vec<(Expo, u128)>>,
count: HashMap<Vec<u32>, u128>,
}
impl PeelMemo {
fn peel_perm(&mut self, w: &Perm) -> Vec<(Expo, u128)> {
let m = w.support_len();
if m == 0 {
return vec![(Vec::new(), 1)];
}
let v = w.padded(m);
let n = v.len() as u32;
self.peel(&v, n, m.saturating_sub(1))
}
fn peel(&mut self, p: &[u32], n: u32, stufe: u32) -> Vec<(Expo, u128)> {
let m = p.len() as u32;
let level = n - m + 1;
let key = (p.to_vec(), level, stufe);
if let Some(v) = self.poly.get(&key) {
return v.clone();
}
let out: Vec<(Expo, u128)> = if m <= 2 {
let mut e = Vec::new();
if m == 2 && p[0] == 2 {
e = vec![0; level as usize];
e[(level - 1) as usize] = 1;
}
vec![(strip(e), 1)]
} else if p[0] == m {
let sub = self.peel(&p[1..], n, m.saturating_sub(2));
let mut acc: BTreeMap<Expo, u128> = BTreeMap::new();
for (e, k) in sub {
let mut e2 = e;
if stufe > 0 {
if e2.len() < level as usize {
e2.resize(level as usize, 0);
}
e2[(level - 1) as usize] += stufe;
}
*acc.entry(strip(e2)).or_insert(0) += k;
}
acc.into_iter().collect()
} else {
let mut acc: BTreeMap<Expo, u128> = BTreeMap::new();
for q in covers_at_1(p) {
for (e, k) in self.peel(&q, n, stufe.saturating_sub(1)) {
*acc.entry(e).or_insert(0) += k;
}
}
acc.into_iter().collect()
};
self.poly.insert(key, out.clone());
out
}
fn count(&mut self, w: &Perm) -> Option<u128> {
let m = w.support_len();
if m == 0 {
return Some(1);
}
let v = w.padded(m);
self.count_rec(&v)
}
fn count_rec(&mut self, p: &[u32]) -> Option<u128> {
if let Some(&v) = self.count.get(p) {
return Some(v);
}
let m = p.len() as u32;
let out = if m <= 2 {
1
} else if p[0] == m {
self.count_rec(&p[1..])?
} else {
covers_at_1(p)
.into_iter()
.try_fold(0u128, |a, q| a.checked_add(self.count_rec(&q)?))?
};
self.count.insert(p.to_vec(), out);
Some(out)
}
}
fn covers_at_1(p: &[u32]) -> Vec<Vec<u32>> {
let mut out = Vec::new();
let mut running_min = u32::MAX;
for i in 1..p.len() {
if p[i] > p[0] && p[i] < running_min {
running_min = p[i];
let mut q = p.to_vec();
q.swap(0, i);
out.push(q);
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
fn p(v: &[u32]) -> Perm {
Perm::new(v.iter().copied()).unwrap()
}
fn sch(v: &[u32]) -> Schubert<i64> {
Schubert::monomial(p(v), 1)
}
fn expo(e: &[u32]) -> Expo {
strip(e.to_vec())
}
#[test]
fn hand_values() {
assert_eq!(
sch(&[1, 3, 2]).expand(),
vec![(expo(&[0, 1]), 1), (expo(&[1]), 1)]
);
assert_eq!(sch(&[3, 2, 1]).expand(), vec![(expo(&[2, 1]), 1)]);
assert_eq!(
sch(&[1, 4, 2, 3]).expand(),
vec![(expo(&[0, 2]), 1), (expo(&[1, 1]), 1), (expo(&[2]), 1)]
);
assert_eq!(Schubert::<i64>::one().expand(), vec![(expo(&[]), 1)]);
}
#[test]
fn dominant_is_a_single_monomial() {
for n in 0..=6u32 {
for w in crate::permutation::tests::all_perms(n) {
if w.is_dominant() {
let e = sch(&w.padded(n)).expand();
assert_eq!(e.len().max(1), 1, "{w} expanded to {e:?}");
assert_eq!(e[0].0, strip(w.code()), "{w}");
assert_eq!(dimension(&w), Some(1), "{w}");
}
}
}
}
#[test]
fn grassmannian_matches_schur_in_k_variables() {
let w = grassmannian_perm(&Partition::new([1]), 2).unwrap();
assert_eq!(w, p(&[1, 3, 2]));
let w = grassmannian_perm(&Partition::new([2, 1]), 2).unwrap();
assert_eq!(w, p(&[2, 4, 1, 3]));
assert_eq!(w.is_grassmannian(), Some(2));
assert_eq!(
sch(&[2, 4, 1, 3]).expand(),
vec![(expo(&[1, 2]), 1), (expo(&[2, 1]), 1)]
);
assert!(grassmannian_perm(&Partition::new([1, 1, 1]), 2).is_none());
}
#[test]
fn degree_equals_length() {
for n in 0..=6u32 {
for w in crate::permutation::tests::all_perms(n) {
for (e, _) in sch(&w.padded(n)).expand() {
assert_eq!(e.iter().sum::<u32>(), w.length(), "{w} term {e:?}");
}
}
}
}
#[test]
fn divided_difference_is_nilpotent_and_braided() {
for n in 2..=5u32 {
for w in crate::permutation::tests::all_perms(n) {
let f = sch(&w.padded(n));
for i in 1..n {
assert!(
f.divided_difference(i).divided_difference(i).is_zero(),
"{w} {i}"
);
for j in (i + 2)..n {
let a = f.divided_difference(i).divided_difference(j);
let b = f.divided_difference(j).divided_difference(i);
assert_eq!(a, b, "{w} commute {i},{j}");
}
if i + 1 < n {
let j = i + 1;
let a = f
.divided_difference(i)
.divided_difference(j)
.divided_difference(i);
let b = f
.divided_difference(j)
.divided_difference(i)
.divided_difference(j);
assert_eq!(a, b, "{w} braid {i},{j}");
}
}
}
}
}
#[test]
fn divided_difference_agrees_with_exact_division() {
for n in 2..=5u32 {
for w in crate::permutation::tests::all_perms(n) {
let f = sch(&w.padded(n));
for i in 1..=(n + 1) {
let via_basis = f.divided_difference(i).expand();
let via_poly = poly_divided_difference(&f.expand(), i);
assert_eq!(via_basis, via_poly, "{w} at i={i}");
}
}
}
}
fn poly_divided_difference(terms: &[(Expo, i64)], i: u32) -> Vec<(Expo, i64)> {
let i = (i - 1) as usize;
let mut num: BTreeMap<Expo, i64> = BTreeMap::new();
for (e, c) in terms {
let mut a = e.clone();
if a.len() <= i + 1 {
a.resize(i + 2, 0);
}
*num.entry(strip(a.clone())).or_insert(0) += c;
a.swap(i, i + 1);
*num.entry(strip(a)).or_insert(0) -= c;
}
num.retain(|_, c| *c != 0);
let mut quot: BTreeMap<Expo, i64> = BTreeMap::new();
while let Some((lead, c)) = num.iter().next_back().map(|(e, c)| (e.clone(), *c)) {
let mut q = lead.clone();
if q.len() <= i {
q.resize(i + 1, 0);
}
assert!(q[i] >= 1, "not divisible by (x_i - x_{{i+1}})");
q[i] -= 1;
let q = strip(q);
*quot.entry(q.clone()).or_insert(0) += c;
for (slot, sign) in [(i, 1i64), (i + 1, -1i64)] {
let mut t = q.clone();
if t.len() <= slot {
t.resize(slot + 1, 0);
}
t[slot] += 1;
let t = strip(t);
*num.entry(t.clone()).or_insert(0) -= c * sign;
if num[&t] == 0 {
num.remove(&t);
}
}
}
quot.retain(|_, c| *c != 0);
quot.into_iter().collect()
}
#[test]
fn divided_difference_perm_lands_where_it_should() {
for n in 2..=5u32 {
for w in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let got = sch(&v.padded(n)).divided_difference_perm(&w);
let mut vw = v.padded(n);
let wp = w.padded(n);
let composed: Vec<u32> =
(0..n as usize).map(|i| vw[(wp[i] - 1) as usize]).collect();
vw = composed;
let vw = Perm::new(vw).unwrap();
let want = if vw.length() + w.length() == v.length() {
sch(&vw.padded(n))
} else {
Schubert::zero()
};
assert_eq!(got, want, "d_{w} on S_{v}");
}
}
}
}
#[test]
fn defining_recursion_reproduces_expand() {
for n in 2..=5u32 {
let w0: Vec<u32> = (1..=n).rev().collect();
let top = sch(&w0);
let delta: Expo = strip((1..=n).rev().map(|x| x - 1).collect::<Vec<u32>>());
assert_eq!(top.expand(), vec![(delta, 1)], "w0 in S_{n}");
for w in crate::permutation::tests::all_perms(n) {
let u = compose(&Perm::new(w0.iter().copied()).unwrap(), &w, n);
let got = top.divided_difference_perm(&u);
assert_eq!(got, sch(&w.padded(n)), "reaching {w} in S_{n}");
}
}
}
fn compose(w0: &Perm, w: &Perm, n: u32) -> Perm {
let a = w0.inverse().padded(n);
let b = w.padded(n);
let v: Vec<u32> = (0..n as usize).map(|i| a[(b[i] - 1) as usize]).collect();
Perm::new(v).unwrap()
}
#[test]
fn from_polynomial_inverts_expand() {
for n in 0..=6u32 {
for w in crate::permutation::tests::all_perms(n) {
let f = sch(&w.padded(n));
assert_eq!(Schubert::from_polynomial(&f.expand()), f, "{w}");
}
}
}
#[test]
fn from_polynomial_on_sums() {
let f = sch(&[1, 3, 2])
.add(&sch(&[3, 2, 1]))
.add(&sch(&[1, 4, 2, 3]).scale(&3));
assert_eq!(Schubert::from_polynomial(&f.expand()), f);
}
#[test]
fn dimension_is_the_expansion_size() {
for n in 0..=6u32 {
for w in crate::permutation::tests::all_perms(n) {
let total: i64 = sch(&w.padded(n)).expand().iter().map(|(_, c)| c).sum();
assert_eq!(dimension(&w).map(|d| d as i64), Some(total), "{w}");
}
}
}
#[test]
fn monk_matches_expanded_multiplication() {
for n in 0..=5u32 {
for w in crate::permutation::tests::all_perms(n) {
let f = sch(&w.padded(n));
for i in 1..=(n + 1) {
let via_monk = f.mul_variable(i).expand();
let mut want: BTreeMap<Expo, i64> = BTreeMap::new();
for (e, c) in f.expand() {
let mut e2 = e;
if e2.len() < i as usize {
e2.resize(i as usize, 0);
}
e2[(i - 1) as usize] += 1;
*want.entry(strip(e2)).or_insert(0) += c;
}
let want: Vec<(Expo, i64)> = want.into_iter().collect();
assert_eq!(via_monk, want, "x_{i} · S_{w}");
}
}
}
}
#[test]
fn product_is_multiplication_of_polynomials() {
for n in 0..=4u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let a = sch(&u.padded(n));
let b = sch(&v.padded(n));
let got = a.mul(&b).expand();
let want = poly_mul(&a.expand(), &b.expand());
assert_eq!(got, want, "S_{u} · S_{v}");
}
}
}
}
fn poly_mul(a: &[(Expo, i64)], b: &[(Expo, i64)]) -> Vec<(Expo, i64)> {
let mut acc: BTreeMap<Expo, i64> = BTreeMap::new();
for (e, c) in a {
for (f, d) in b {
let n = e.len().max(f.len());
let mut g = vec![0u32; n];
for (i, slot) in g.iter_mut().enumerate() {
*slot = e.get(i).copied().unwrap_or(0) + f.get(i).copied().unwrap_or(0);
}
*acc.entry(strip(g)).or_insert(0) += c * d;
}
}
acc.retain(|_, c| *c != 0);
acc.into_iter().collect()
}
#[test]
fn e1_and_e3_agree_exhaustively() {
for n in 0..=5u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let a = sch(&u.padded(n));
let b = sch(&v.padded(n));
assert_eq!(a.mul_e3(&b), a.mul_naive(&b), "S_{u} · S_{v}");
}
}
}
}
#[test]
fn stanley_hand_values() {
use crate::sym::SymFn;
let f: Schur<i64> = stanley(&p(&[2, 1, 4, 3]));
assert_eq!(f.coeff(&Partition::new([2])), 1);
assert_eq!(f.coeff(&Partition::new([1, 1])), 1);
assert_eq!(f.terms().len(), 2);
assert_ne!(sch(&[2, 1, 4, 3]).expand().len(), 1);
let e: Schur<i64> = stanley(&Perm::identity());
assert_eq!(e.coeff(&Partition::new([] as [u32; 0])), 1);
}
#[test]
fn stanley_of_grassmannian_is_one_schur() {
use crate::sym::SymFn;
for k in 1..=4u32 {
for size in 0..=7u32 {
for lam in crate::partition::partitions_of(size) {
if lam.len() as u32 > k {
continue;
}
let w = grassmannian_perm(&lam, k).unwrap();
let f: Schur<i64> = stanley(&w);
assert_eq!(f.terms().len().max(1), 1, "{w} -> {f:?}");
assert_eq!(f.coeff(&lam), 1, "{w} shape {lam:?}");
}
}
}
}
#[test]
fn stanley_is_positive_and_shift_invariant() {
use crate::sym::SymFn;
for n in 0..=6u32 {
for w in crate::permutation::tests::all_perms(n) {
let f: Schur<i64> = stanley(&w);
for (lam, c) in f.terms() {
assert!(*c > 0, "{w}: negative coefficient at {lam:?}");
assert_eq!(lam.size(), w.length(), "{w}: wrong degree");
}
let g: Schur<i64> = stanley(&shift_up(&w));
assert_eq!(f, g, "shift invariance at {w}");
}
}
}
#[test]
fn schubert_coeff_agrees_with_the_full_product() {
for n in 0..=4u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let full = sch(&u.padded(n)).mul_naive(&sch(&v.padded(n)));
for w in crate::permutation::tests::all_perms(n + 2) {
let got: i64 = schubert_coeff(&u, &v, &w);
assert_eq!(got, full.coeff(&w), "c^{w}_{{{u},{v}}}");
}
}
}
}
}
#[test]
fn product_support_lies_above_both_factors() {
for n in 0..=5u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
for w in sch(&u.padded(n))
.mul_naive(&sch(&v.padded(n)))
.terms()
.keys()
{
assert!(u.bruhat_le(w), "{u} !<= {w} in S_{u}·S_{v}");
assert!(v.bruhat_le(w), "{v} !<= {w} in S_{u}·S_{v}");
}
}
}
}
}
#[test]
fn monk_covers_move_up_the_bruhat_order() {
for n in 0..=5u32 {
for w in crate::permutation::tests::all_perms(n) {
for i in 1..=(n + 1) {
for (_, u) in w.covers_right(i) {
assert!(w.bruhat_le(&u), "{w} !<= {u}");
}
for (_, u) in w.covers_left(i) {
assert!(w.bruhat_le(&u), "{w} !<= {u} (left)");
}
}
}
}
}
#[test]
fn bruhat_is_a_partial_order_with_known_bounds() {
for n in 0..=5u32 {
let w0 = p(&(1..=n).rev().collect::<Vec<u32>>());
for a in crate::permutation::tests::all_perms(n) {
assert!(a.bruhat_le(&a), "reflexive {a}");
assert!(Perm::identity().bruhat_le(&a), "id <= {a}");
assert!(a.bruhat_le(&w0), "{a} <= w0");
for b in crate::permutation::tests::all_perms(n) {
if a.bruhat_le(&b) && b.bruhat_le(&a) {
assert_eq!(a, b, "antisymmetry {a} {b}");
}
if a.bruhat_le(&b) {
assert!(a.length() <= b.length(), "{a} <= {b} but longer");
}
}
}
}
}
#[test]
fn e2_agrees_with_e1_exhaustively() {
for n in 0..=5u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let a = sch(&u.padded(n));
let b = sch(&v.padded(n));
assert_eq!(a.mul_e2(&b), a.mul_naive(&b), "S_{u} · S_{v}");
}
}
}
}
#[test]
fn e2_is_order_independent() {
for n in 2..=5u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let a = sch(&u.padded(n));
let b = sch(&v.padded(n));
assert_eq!(a.mul_e2(&b), b.mul_e2(&a), "S_{u} · S_{v}");
}
}
}
}
#[test]
fn e2_agrees_on_staircases() {
for k in 2..=4u32 {
let w: Vec<u32> = (1..=k)
.map(|i| 2 * i)
.chain((1..=k).map(|i| 2 * i - 1))
.collect();
let a = sch(&w);
assert_eq!(a.mul_e2(&a), a.mul_naive(&a), "stair{k}^2");
}
}
#[test]
fn e1_and_e3_agree_on_sums() {
let f = sch(&[1, 3, 2])
.add(&sch(&[3, 2, 1]))
.add(&sch(&[1, 4, 2, 3]).scale(&3));
let g = sch(&[2, 4, 1, 3]).add(&sch(&[2, 1]).scale(&2));
assert_eq!(f.mul_e3(&g), f.mul_naive(&g));
assert_eq!(g.mul_e3(&f), f.mul_naive(&g));
}
#[test]
fn e1_and_e3_agree_on_staircases() {
for k in 2..=4u32 {
let w: Vec<u32> = (1..=k)
.map(|i| 2 * i)
.chain((1..=k).map(|i| 2 * i - 1))
.collect();
let a = sch(&w);
assert_eq!(a.mul_e3(&a), a.mul_naive(&a), "stair{k}^2");
}
}
#[test]
fn peel_states_counts_the_dag() {
let stair4: Vec<u32> = vec![2, 4, 6, 8, 1, 3, 5, 7];
assert_eq!(peel_states(&p(&stair4)), 158);
let stair3: Vec<u32> = vec![2, 4, 6, 1, 3, 5];
assert_eq!(peel_states(&p(&stair3)), 38);
assert_eq!(dimension(&p(&stair4)), Some(64));
assert_eq!(dimension(&p(&stair3)), Some(8));
}
#[test]
fn product_is_commutative_and_unital() {
for n in 0..=4u32 {
for u in crate::permutation::tests::all_perms(n) {
let a = sch(&u.padded(n));
assert_eq!(a.mul(&Schubert::one()), a, "{u} · 1");
for v in crate::permutation::tests::all_perms(n) {
let b = sch(&v.padded(n));
assert_eq!(a.mul(&b), b.mul(&a), "{u} · {v}");
}
}
}
}
#[test]
fn structure_constants_are_non_negative() {
for n in 0..=5u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
for (w, c) in sch(&u.padded(n)).mul(&sch(&v.padded(n))).terms() {
assert!(*c > 0, "c^{w}_{{{u},{v}}} = {c}");
}
}
}
}
}
#[test]
fn pairing_is_the_top_coefficient() {
let n = 3u32;
let w0 = p(&[3, 2, 1]);
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let got = sch(&u.padded(n)).pairing(&sch(&v.padded(n)), n);
let w0u: Vec<u32> = (0..n as usize)
.map(|i| w0.padded(n)[(u.padded(n)[i] - 1) as usize])
.collect();
let want = i64::from(v == Perm::new(w0u).unwrap());
assert_eq!(got, want, "<S_{u}, S_{v}>");
}
}
}
fn reverse_descending_prefix(w: &Perm, n: u32) -> Option<Perm> {
let m = w.support_len().max(n);
let mut v = w.padded(m);
let n = n as usize;
if v[..n].windows(2).any(|pair| pair[0] < pair[1]) {
return None;
}
v[..n].reverse();
Some(Perm::new(v).unwrap())
}
#[test]
fn scalar_product_agrees_with_the_prefix_reversal_rule() {
for m in 0..=4u32 {
for u in crate::permutation::tests::all_perms(m) {
for v in crate::permutation::tests::all_perms(m) {
let (a, b) = (sch(&u.padded(m)), sch(&v.padded(m)));
let naive = a.mul_naive(&b);
for n in 0..=4u32 {
let mut want = Schubert::zero();
for (w, c) in naive.terms() {
if let Some(z) = reverse_descending_prefix(w, n) {
want.add_term(z, c);
}
}
assert_eq!(
a.scalar_product(&b, n),
want,
"scalar product of S_{u} and S_{v} at n={n}"
);
}
}
}
}
}
#[test]
fn scalar_product_recovers_the_pairing_at_the_identity() {
for n in 0..=4u32 {
for u in crate::permutation::tests::all_perms(n) {
for v in crate::permutation::tests::all_perms(n) {
let (a, b) = (sch(&u.padded(n)), sch(&v.padded(n)));
assert_eq!(
a.scalar_product(&b, n).coeff(&Perm::identity()),
a.pairing(&b, n),
"constant term at n={n} for S_{u}, S_{v}"
);
}
}
}
}
#[test]
fn scalar_product_matches_sages_doctest_values() {
let a = sch(&[3, 2, 4, 1]);
let b = sch(&[4, 3, 2, 1]);
assert!(a.scalar_product(&a, 4).is_zero());
assert_eq!(b.scalar_product(&a, 4), sch(&[1, 3, 4, 6, 2, 5]));
}
#[test]
fn scalar_product_below_rank_two_is_the_product() {
for m in 0..=3u32 {
for u in crate::permutation::tests::all_perms(m) {
for v in crate::permutation::tests::all_perms(m) {
let (a, b) = (sch(&u.padded(m)), sch(&v.padded(m)));
for n in 0..=1u32 {
assert_eq!(
a.scalar_product(&b, n),
a.mul(&b),
"S_{u} times S_{v} at n={n}"
);
}
}
}
}
}
#[test]
fn stability_under_padding() {
let a = sch(&[3, 1, 4, 2]);
let b = sch(&[3, 1, 4, 2, 5, 6]);
assert_eq!(a, b);
assert_eq!(a.expand(), b.expand());
assert_eq!(a.mul(&a), b.mul(&b));
}
}