use std::collections::{BTreeMap, HashMap};
use crate::character::character_in;
use crate::coeff::{QAlgebra, Ring};
use crate::fasthash::Map;
use crate::interrupt;
use crate::kostka::kostka;
use crate::memo::{inverse_kostka_row_cached, jt_row_cached, lex_parts_cached, partitions_cached};
use crate::partition::Partition;
use crate::sym::{
Elementary, Forgotten, Homogeneous, Monomial, PowerSum, Schur, SymAlgebra, SymFn,
};
pub trait ToSchur<C: Ring> {
fn to_schur(&self) -> Schur<C>;
}
pub trait FromSchur<C: Ring>: Sized {
fn from_schur(s: &Schur<C>) -> Self;
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
let _ = (src, terms);
None
}
}
pub fn convert<C, A, B>(a: &A) -> B
where
C: Ring,
A: SymFn<C> + ToSchur<C>,
B: FromSchur<C>,
{
match B::from_basis(A::SYMBOL, a.terms()) {
Some(b) => b,
None => B::from_schur(&a.to_schur()),
}
}
impl<C: Ring> ToSchur<C> for Schur<C> {
fn to_schur(&self) -> Schur<C> {
self.clone()
}
}
impl<C: Ring> FromSchur<C> for Schur<C> {
fn from_schur(s: &Schur<C>) -> Self {
s.clone()
}
}
fn jt_terms(c: &[u32]) -> Vec<(Partition, i64)> {
if c.is_empty() {
return vec![(Partition::default(), 1)];
}
let mut acc: HashMap<Partition, i64> = HashMap::new();
let mut used = vec![false; c.len()];
let mut idx: Vec<u32> = Vec::with_capacity(c.len());
jt_rec(c, c.len(), &mut used, &mut idx, 1, &mut acc);
acc.into_iter().filter(|(_, s)| *s != 0).collect()
}
pub(crate) fn jt_compositions(c: &[u32], visit: &mut impl FnMut(&[u32], i64)) {
if c.is_empty() {
visit(&[], 1);
return;
}
let mut used = vec![false; c.len()];
let mut alpha = vec![0u32; c.len()];
jtc_rec(c, c.len(), &mut used, &mut alpha, 1, visit);
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn jtc_rec(
c: &[u32],
i: usize,
used: &mut [bool],
alpha: &mut [u32],
sign: i64,
visit: &mut impl FnMut(&[u32], i64),
) {
if i == 0 {
visit(alpha, sign);
return;
}
let row = i - 1;
let mut below = 0i64;
let lo = (row as i64 - c[row] as i64).max(0) as usize;
for &u in used.iter().take(lo) {
if u {
below += 1;
}
}
for j in lo..c.len() {
if used[j] {
below += 1;
continue;
}
used[j] = true;
alpha[j] = (c[row] as i64 - row as i64 + j as i64) as u32;
let s = if below % 2 == 0 { sign } else { -sign };
jtc_rec(c, row, used, alpha, s, visit);
used[j] = false;
}
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn jt_rec(
c: &[u32],
i: usize,
used: &mut [bool],
idx: &mut Vec<u32>,
sign: i64,
acc: &mut HashMap<Partition, i64>,
) {
if i == 0 {
*acc.entry(Partition::new(idx.iter().copied())).or_insert(0) += sign;
return;
}
let row = i - 1;
let mut below = 0i64;
let lo = (row as i64 - c[row] as i64).max(0) as usize;
for &u in used.iter().take(lo) {
if u {
below += 1;
}
}
for j in lo..c.len() {
if used[j] {
below += 1;
continue;
}
let k = c[row] as i64 - row as i64 + j as i64;
used[j] = true;
idx.push(k as u32);
let s = if below % 2 == 0 { sign } else { -sign };
jt_rec(c, row, used, idx, s, acc);
idx.pop();
used[j] = false;
}
}
fn jt_row(index: &Partition) -> std::sync::Arc<Vec<(Partition, i64)>> {
jt_row_cached(index, || jt_terms(index.parts()))
}
impl<C: Ring> ToSchur<C> for Homogeneous<C> {
fn to_schur(&self) -> Schur<C> {
expand_multiplicative(self, false)
}
}
impl<C: Ring> FromSchur<C> for Homogeneous<C> {
fn from_schur(s: &Schur<C>) -> Self {
contract_multiplicative(s, false)
}
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
match src {
"p" => Some(multiplicative_route(terms, |n| {
power_generator::<C, Self>(n, false)
})),
"e" => Some(multiplicative_route(terms, flip_generator::<C, Self>)),
_ => None,
}
}
}
impl<C: Ring> ToSchur<C> for Elementary<C> {
fn to_schur(&self) -> Schur<C> {
expand_multiplicative(self, true)
}
}
fn expand_multiplicative<C: Ring, S: SymFn<C>>(x: &S, vertical: bool) -> Schur<C> {
let mut out = Schur::zero();
let mut by_degree: BTreeMap<u32, Vec<(&Partition, &C)>> = BTreeMap::new();
for (lambda, c) in x.terms() {
by_degree
.entry(lambda.size())
.or_default()
.push((lambda, c));
}
for (n, items) in by_degree {
let l = n as usize;
if l == 0 {
for (_, c) in &items {
out.add_term(Partition::default(), (*c).clone());
}
} else if l > MASK_LIMIT {
expand_shared(&items, 0, &Schur::unit(), vertical, &mut out);
} else {
pieri_trie(
&items,
0,
&unit_mask_layer(l),
vertical,
&mut |_, c, layer| {
for (&mask, &v) in layer {
out.add_term(mask_to_partition(mask, l), C::from_i128(v).mul(*c));
}
},
);
}
}
out
}
pub(crate) fn unit_mask_layer(l: usize) -> Map<u64, i128> {
let mut root: Map<u64, i128> = Map::default();
root.insert((1u64 << l) - 1, 1);
root
}
pub(crate) fn beta_mask(lambda: &Partition, l: usize) -> u64 {
let mut mask = 0u64;
for i in 0..l {
mask |= 1 << (lambda.part(i) as usize + (l - 1 - i));
}
mask
}
pub(crate) fn pieri_trie<X>(
items: &[(&Partition, X)],
depth: usize,
layer: &Map<u64, i128>,
vertical: bool,
emit: &mut impl FnMut(&Partition, &X, &Map<u64, i128>),
) {
let mut i = 0;
while i < items.len() && items[i].0.len() == depth {
emit(items[i].0, &items[i].1, layer);
i += 1;
}
while i < items.len() {
let k = items[i].0.part(depth);
let start = i;
while i < items.len() && items[i].0.part(depth) == k {
i += 1;
}
let next = pieri_masks(layer, k, vertical);
pieri_trie(&items[start..i], depth + 1, &next, vertical, emit);
}
}
fn pieri_masks(cur: &Map<u64, i128>, k: u32, vertical: bool) -> Map<u64, i128> {
let mut next: Map<u64, i128> = Map::with_capacity_and_hasher(cur.len() * 2, Default::default());
let mut shapes = Vec::new();
for (&mask, &c) in cur {
shapes.clear();
strip_masks(mask, k, vertical, &mut shapes);
for &m in &shapes {
*next.entry(m).or_insert(0) += c;
}
}
next
}
fn strip_masks(mask: u64, k: u32, vertical: bool, out: &mut Vec<u64>) {
let mut bits: Vec<u32> = Vec::with_capacity(mask.count_ones() as usize);
let mut rest = mask;
while rest != 0 {
let b = 63 - rest.leading_zeros();
bits.push(b);
rest &= !(1u64 << b);
}
let mut cap = vec![0u32; bits.len() + 1];
for i in (1..bits.len()).rev() {
let room = if vertical {
1
} else {
bits[i - 1] - 1 - bits[i]
};
cap[i] = cap[i + 1].saturating_add(room);
}
cap[0] = u32::MAX;
fn rec(
bits: &[u32],
cap: &[u32],
i: usize,
left: u32,
vertical: bool,
acc: u64,
out: &mut Vec<u64>,
) {
if i == bits.len() {
if left == 0 {
out.push(acc);
}
return;
}
if left > cap[i] {
return;
}
let b = bits[i];
let hi = if vertical {
b + 1
} else if i == 0 {
b + left
} else {
(bits[i - 1] - 1).min(b + left)
};
for nb in b..=hi {
let used = nb - b;
if used > left {
break;
}
if vertical && used > 0 && acc >> nb & 1 == 1 {
continue;
}
rec(
bits,
cap,
i + 1,
left - used,
vertical,
acc | (1u64 << nb),
out,
);
}
}
rec(&bits, &cap, 0, k, vertical, 0, out);
}
fn expand_shared<C: Ring>(
items: &[(&Partition, &C)],
depth: usize,
layer: &Schur<C>,
vertical: bool,
out: &mut Schur<C>,
) {
let mut i = 0;
while i < items.len() && items[i].0.len() == depth {
for (lambda, v) in layer.terms() {
out.add_term(lambda.clone(), v.mul(items[i].1));
}
i += 1;
}
while i < items.len() {
let k = items[i].0.part(depth);
let start = i;
while i < items.len() && items[i].0.part(depth) == k {
i += 1;
}
let next = pieri_step(layer, k, vertical);
expand_shared(&items[start..i], depth + 1, &next, vertical, out);
}
}
fn pieri_step<C: Ring>(cur: &Schur<C>, k: u32, vertical: bool) -> Schur<C> {
let mut next = Schur::zero();
let mut shapes = Vec::new();
for (lambda, c) in cur.terms() {
shapes.clear();
if vertical {
vertical_strips(lambda.parts(), k, &mut shapes);
} else {
horizontal_strips(lambda.parts(), k, &mut shapes);
}
for mu in shapes.drain(..) {
next.add_term(mu, c.clone());
}
}
next
}
fn horizontal_strips(lambda: &[u32], k: u32, out: &mut Vec<Partition>) {
fn rec(i: usize, left: u32, lambda: &[u32], cur: &mut Vec<u32>, out: &mut Vec<Partition>) {
if i == lambda.len() + 1 {
if left == 0 {
out.push(Partition::new(cur.iter().copied()));
}
return;
}
let lam_i = lambda.get(i).copied().unwrap_or(0);
let upper = if i == 0 {
lam_i + left
} else {
lambda[i - 1].min(lam_i + left)
};
for v in lam_i..=upper {
cur.push(v);
rec(i + 1, left - (v - lam_i), lambda, cur, out);
cur.pop();
}
}
let mut cur = Vec::with_capacity(lambda.len() + 1);
rec(0, k, lambda, &mut cur, out);
}
fn vertical_strips(lambda: &[u32], k: u32, out: &mut Vec<Partition>) {
fn rec(
i: usize,
rows: usize,
left: u32,
prev: u32,
lambda: &[u32],
cur: &mut Vec<u32>,
out: &mut Vec<Partition>,
) {
if left == 0 {
let mut done = cur.clone();
done.extend_from_slice(&lambda[i.min(lambda.len())..]);
out.push(Partition::new(done));
return;
}
if i == rows || left as usize > rows - i {
return;
}
let lam_i = lambda.get(i).copied().unwrap_or(0);
if lam_i <= prev {
cur.push(lam_i);
rec(i + 1, rows, left, lam_i, lambda, cur, out);
cur.pop();
}
if lam_i < prev {
cur.push(lam_i + 1);
rec(i + 1, rows, left - 1, lam_i + 1, lambda, cur, out);
cur.pop();
}
}
let rows = lambda.len() + k as usize;
let mut cur = Vec::with_capacity(rows);
rec(0, rows, k, u32::MAX, lambda, &mut cur, out);
}
impl<C: Ring> FromSchur<C> for Elementary<C> {
fn from_schur(s: &Schur<C>) -> Self {
contract_multiplicative(s, true)
}
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
match src {
"p" => Some(multiplicative_route(terms, |n| {
power_generator::<C, Self>(n, true)
})),
"h" => Some(multiplicative_route(terms, flip_generator::<C, Self>)),
_ => None,
}
}
}
fn flip_generator<C: Ring, S: SymAlgebra<C>>(n: u32) -> S {
let row = flip_row(n);
let mut x = S::zero();
for (mu, c) in row.iter() {
x.add_term(mu.clone(), C::from_i64(*c));
}
x
}
#[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
fn flip_row(n: u32) -> std::sync::Arc<Vec<(Partition, i64)>> {
crate::memo::flip_row_cached(n, || {
if n == 0 {
return vec![(Partition::default(), 1)];
}
let mut acc: HashMap<Partition, i64> = HashMap::new();
for k in 1..=n {
let sign = if k % 2 == 1 { 1i64 } else { -1 };
for (mu, c) in flip_row(n - k).iter() {
let mut parts = mu.parts().to_vec();
parts.push(k);
*acc.entry(Partition::new(parts)).or_insert(0) += sign * c;
}
}
acc.into_iter().filter(|(_, c)| *c != 0).collect()
})
}
pub trait Dual<C: Ring>: SymAlgebra<C> {
type Other: SymAlgebra<C> + Dual<C, Other = Self>;
}
impl<C: Ring> Dual<C> for Homogeneous<C> {
type Other = Elementary<C>;
}
impl<C: Ring> Dual<C> for Elementary<C> {
type Other = Homogeneous<C>;
}
fn flip_basis<C: Ring, A: SymFn<C>, B: SymAlgebra<C>>(x: &A) -> B {
multiplicative_route(x.terms(), flip_generator::<C, B>)
}
fn multiplicative_route<C: Ring, B: SymAlgebra<C>>(
terms: &BTreeMap<Partition, C>,
generator: impl Fn(u32) -> B,
) -> B {
let mut gens: BTreeMap<u32, B> = BTreeMap::new();
for mu in terms.keys() {
for &part in mu.parts() {
gens.entry(part).or_insert_with(|| generator(part));
}
}
let mut out = B::zero();
for (mu, c) in terms {
match mu.parts() {
[] => out.add_term(Partition::default(), c.clone()),
[first, rest @ ..] => {
let mut prod: Option<B> = None;
for part in rest {
let p = prod.as_ref().unwrap_or(&gens[first]);
prod = Some(p.times(&gens[part]));
}
for (nu, v) in prod.as_ref().unwrap_or(&gens[first]).terms() {
out.add_term(nu.clone(), v.mul(c));
}
}
}
}
out
}
fn power_in_h_row(n: u32) -> std::sync::Arc<Vec<(Partition, i128)>> {
crate::memo::power_in_h_row_cached(n, || {
if n == 0 {
return vec![(Partition::default(), 1)];
}
let mut acc: HashMap<Partition, i128> = HashMap::new();
acc.insert(Partition::new([n]), i128::from(n));
for i in 1..n {
for (mu, c) in power_in_h_row(i).iter() {
let mut parts = mu.parts().to_vec();
parts.push(n - i);
*acc.entry(Partition::new(parts)).or_insert(0) -= c;
}
}
acc.into_iter().filter(|(_, c)| *c != 0).collect()
})
}
fn power_generator<C: Ring, S: SymAlgebra<C>>(n: u32, dual: bool) -> S {
let flip = dual && n.is_multiple_of(2) && n > 0;
let row = power_in_h_row(n);
let mut x = S::zero();
for (mu, c) in row.iter() {
x.add_term(mu.clone(), C::from_i128(if flip { -c } else { *c }));
}
x
}
fn multiplicative_in_power<C: QAlgebra>(n: u32, dual: bool) -> PowerSum<C> {
let mut x = PowerSum::zero();
for mu in partitions_cached(n).iter() {
let sign: i64 = if dual && (n as usize - mu.len()) % 2 == 1 {
-1
} else {
1
};
let c = if n <= 33 {
C::from_ratio(
sign.into(),
i128::try_from(mu.z()).expect("z_mu <= 33! fits i128"),
)
} else {
None
}
.unwrap_or_else(|| mu.div_by_z(&C::from_i64(sign)));
x.add_term(mu.clone(), c);
}
x
}
const JT_LIMIT: usize = 14;
const FLIP_MIN: usize = 14;
fn contract_multiplicative<C: Ring, S: Dual<C>>(s: &Schur<C>, dual: bool) -> S {
let mut out = S::zero();
let mut swept: BTreeMap<u32, Vec<(Partition, C)>> = BTreeMap::new();
let mut crossed: Schur<C> = Schur::zero();
for (lambda, c) in s.terms() {
let index = if dual {
lambda.conjugate()
} else {
lambda.clone()
};
let other = index.conjugate();
if index.len().min(other.len()) > JT_LIMIT {
swept
.entry(index.size())
.or_default()
.push((index, c.clone()));
} else if index.len() >= FLIP_MIN && other.len() < index.len() {
crossed.add_term(lambda.clone(), c.clone());
} else {
for (mu, v) in jt_row(&index).iter() {
out.add_term(mu.clone(), C::from_i64(*v).mul(c));
}
}
}
if !crossed.is_zero() {
let mirror: S::Other = contract_multiplicative(&crossed, !dual);
out = out.add(&flip_basis::<C, _, S>(&mirror));
}
for (n, targets) in swept {
match muir_column(&targets, n) {
Some(terms) => {
for (mu, v) in terms {
out.add_term(mu, v);
}
}
None => {
for (index, c) in &targets {
for (mu, v) in jt_row(index).iter() {
out.add_term(mu.clone(), C::from_i64(*v).mul(c));
}
}
}
}
}
out
}
fn muir_column<C: Ring>(targets: &[(Partition, C)], n: u32) -> Option<Vec<(Partition, C)>> {
let want: HashMap<&Partition, &C> = targets.iter().map(|(p, c)| (p, c)).collect();
let mut out = Vec::new();
for mu in partitions_cached(n).iter() {
let mut acc = C::zero();
for (lambda, v) in muir_expand(mu)? {
if let Some(c) = want.get(&lambda) {
acc.add_assign(&C::from_i128(v).mul(c));
}
}
if !acc.is_zero() {
out.push((mu.clone(), acc));
}
}
Some(out)
}
impl<C: Ring> ToSchur<C> for PowerSum<C> {
fn to_schur(&self) -> Schur<C> {
let mut out = Schur::zero();
let mut by_degree: HashMap<u32, Vec<(&Partition, &C)>> = HashMap::new();
for (mu, c) in self.terms() {
let n = mu.size();
if n as usize <= WIDE_MASK_LIMIT {
by_degree.entry(n).or_default().push((mu, c));
} else {
for lambda in partitions_cached(n).iter() {
interrupt::poll();
let chi = character_in::<C>(lambda, mu);
if !chi.is_zero() {
out.add_term(lambda.clone(), chi.mul(c));
}
}
}
}
let mut degrees: Vec<u32> = by_degree.keys().copied().collect();
degrees.sort_unstable();
for n in degrees {
let Some(mut items) = by_degree.remove(&n) else {
continue;
};
items.sort_by(|a, b| a.0.parts().cmp(b.0.parts()));
let l = n as usize;
if l == 0 {
for (_, c) in &items {
out.add_term(Partition::default(), (*c).clone());
}
continue;
}
if l <= MASK_LIMIT {
sweep_degree::<u64, C>(&items, l, &mut out);
} else {
sweep_degree::<u128, C>(&items, l, &mut out);
}
}
out
}
}
fn sweep_degree<M: Beta, C: Ring>(items: &[(&Partition, &C)], l: usize, out: &mut Schur<C>) {
let mut root: Map<M, i128> = Map::default();
root.insert(M::low_ones(l), 1);
if integral_sweep(items, l, &root, out) {
return;
}
let mut acc: Map<M, C> = Map::default();
p_expand_shared(items, 0, &root, &mut |c: &&C, mask, chi: &i128| {
let term = C::from_i128(*chi).mul(c);
acc.entry(mask).or_insert_with(C::zero).add_assign(&term);
});
for (mask, c) in acc {
if !c.is_zero() {
out.add_term(mask_to_partition(mask, l), c);
}
}
}
pub(crate) fn p_expand_shared<M: Beta, C: Ring, T, F>(
items: &[(&Partition, T)],
depth: usize,
layer: &Map<M, C>,
emit: &mut F,
) where
F: FnMut(&T, M, &C),
{
let mut i = 0;
while i < items.len() && items[i].0.len() == depth {
interrupt::poll();
for (&mask, chi) in layer {
if !chi.is_zero() {
emit(&items[i].1, mask, chi);
}
}
i += 1;
}
while i < items.len() {
let k = items[i].0.part(depth);
let start = i;
while i < items.len() && items[i].0.part(depth) == k {
i += 1;
}
let next = p_step(layer, k);
p_expand_shared(&items[start..i], depth + 1, &next, emit);
}
}
fn integral_sweep<M: Beta, C: Ring>(
items: &[(&Partition, &C)],
l: usize,
root: &Map<M, i128>,
out: &mut Schur<C>,
) -> bool {
let mut den: i128 = 1;
let mut ratios = Vec::with_capacity(items.len());
for (_, c) in items {
let (n, d) = match c.as_ratio() {
Some(r) => r,
None => return false, };
ratios.push((n, d));
let g = gcd_i128(den, d);
den = match den.checked_mul(d / g) {
Some(v) => v,
None => return false,
};
}
let mut scaled = Vec::with_capacity(items.len());
for &(n, d) in &ratios {
match n.checked_mul(den / d) {
Some(v) => scaled.push(v),
None => return false,
}
}
let paired: Vec<(&Partition, i128)> = items
.iter()
.zip(&scaled)
.map(|((mu, _), &s)| (*mu, s))
.collect();
let mut acc: Map<M, i128> = Map::default();
let mut overflow = false;
p_expand_shared(&paired, 0, root, &mut |&s: &i128, mask, chi: &i128| {
if overflow {
return;
}
let slot = acc.entry(mask).or_insert(0);
match s.checked_mul(*chi).and_then(|t| slot.checked_add(t)) {
Some(v) => *slot = v,
None => overflow = true,
}
});
if overflow {
return false;
}
let mut built = Vec::with_capacity(acc.len());
for (&mask, &v) in &acc {
if v == 0 {
continue;
}
match C::from_ratio(v, den) {
Some(c) => built.push((mask, c)),
None => return false,
}
}
for (mask, c) in built {
out.add_term(mask_to_partition(mask, l), c);
}
true
}
#[allow(clippy::cast_possible_wrap)]
fn gcd_i128(a: i128, b: i128) -> i128 {
crate::coeff::gcd_u128(a.unsigned_abs(), b.unsigned_abs()) as i128
}
#[cfg(test)]
fn p_expand(mu: &Partition) -> Option<Vec<(Partition, i128)>> {
let l = mu.size() as usize;
if l == 0 {
return Some(vec![(Partition::default(), 1)]);
}
if l > MASK_LIMIT {
return None;
}
let mut cur: Map<u64, i128> = Map::default();
cur.insert((1u64 << l) - 1, 1);
for &k in mu.parts() {
cur = p_step(&cur, k);
}
Some(
cur.into_iter()
.filter(|&(_, c)| c != 0)
.map(|(mask, c)| (mask_to_partition(mask, l), c))
.collect(),
)
}
pub(crate) const MASK_LIMIT: usize = 32;
pub(crate) const WIDE_MASK_LIMIT: usize = 55;
pub(crate) trait Beta: Copy + Eq + std::hash::Hash + 'static {
const BITS: u32;
fn low_ones(n: usize) -> Self;
fn canonical(self) -> Self;
fn is_zero(self) -> bool;
fn test(self, n: u32) -> bool;
fn with_bit(self, n: u32) -> Self;
fn without_bit(self, n: u32) -> Self;
fn between(self, lo: u32, hi: u32) -> Self;
fn trailing_zeros(self) -> u32;
fn count_ones(self) -> u32;
fn clear_lowest(self) -> Self;
fn highest(self) -> usize;
}
macro_rules! impl_beta {
($t:ty) => {
impl Beta for $t {
const BITS: u32 = <$t>::BITS;
#[inline]
fn low_ones(n: usize) -> Self {
(1 as $t << n) - 1
}
#[inline]
fn canonical(self) -> Self {
self >> (!self).trailing_zeros()
}
#[inline]
fn is_zero(self) -> bool {
self == 0
}
#[inline]
fn test(self, n: u32) -> bool {
self >> n & 1 == 1
}
#[inline]
fn with_bit(self, n: u32) -> Self {
self | (1 as $t) << n
}
#[inline]
fn without_bit(self, n: u32) -> Self {
self & !((1 as $t) << n)
}
#[inline]
fn between(self, lo: u32, hi: u32) -> Self {
self & ((((1 as $t) << hi) - 1) ^ (((1 as $t) << lo) - 1))
}
#[inline]
fn trailing_zeros(self) -> u32 {
<$t>::trailing_zeros(self)
}
#[inline]
fn count_ones(self) -> u32 {
<$t>::count_ones(self)
}
#[inline]
fn clear_lowest(self) -> Self {
self & (self - 1)
}
#[inline]
fn highest(self) -> usize {
(<$t>::BITS - 1 - <$t>::leading_zeros(self)) as usize
}
}
};
}
impl_beta!(u64);
impl_beta!(u128);
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
pub(crate) fn p_step<M: Beta, C: Ring>(cur: &Map<M, C>, k: u32) -> Map<M, C> {
let mut next: Map<M, C> = Map::with_capacity_and_hasher(cur.len() * 2, Default::default());
for (&mask, c) in cur {
interrupt::poll();
let mut rest = mask;
while !rest.is_zero() {
let b = rest.trailing_zeros();
rest = rest.clear_lowest();
let nb = b + k;
if mask.test(nb) {
continue; }
let between = mask.between(b + 1, nb);
let m = mask.without_bit(b).with_bit(nb);
let slot = next.entry(m).or_insert_with(C::zero);
if between.count_ones().is_multiple_of(2) {
slot.add_assign(c);
} else {
slot.sub_assign(c);
}
}
}
next
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn mask_to_partition<M: Beta>(mask: M, l: usize) -> Partition {
let mut parts = Vec::with_capacity(l);
let mut rest = mask;
let mut i = 0usize;
while !rest.is_zero() {
let b = rest.highest();
rest = rest.without_bit(b as u32);
let part = b - (l - 1 - i);
if part > 0 {
parts.push(part as u32);
}
i += 1;
}
Partition::from_sorted(parts)
}
impl<C: QAlgebra> FromSchur<C> for PowerSum<C> {
fn from_schur(s: &Schur<C>) -> Self {
let mut out = PowerSum::zero();
for (lambda, c) in s.terms() {
let row = crate::character::character_row(lambda);
let mut wide: Option<HashMap<(Partition, Partition), C>> = None;
for (mu, chi) in partitions_cached(lambda.size()).iter().zip(row) {
let chi = match chi {
Some(v) => C::from_i128(v),
None => crate::character::character_generic(
lambda,
mu,
wide.get_or_insert_with(HashMap::new),
),
};
if !chi.is_zero() {
out.add_term(mu.clone(), mu.div_by_z(&c.mul(&chi)));
}
}
}
out
}
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
match src {
"h" => Some(multiplicative_route(terms, |n| {
multiplicative_in_power::<C>(n, false)
})),
"e" => Some(multiplicative_route(terms, |n| {
multiplicative_in_power::<C>(n, true)
})),
_ => None,
}
}
}
impl<C: Ring> FromSchur<C> for Monomial<C> {
fn from_schur(s: &Schur<C>) -> Self {
let mut out = Monomial::zero();
let mut by_degree: BTreeMap<u32, Vec<(&Partition, &C)>> = BTreeMap::new();
for (lambda, c) in s.terms() {
by_degree
.entry(lambda.size())
.or_default()
.push((lambda, c));
}
for (n, items) in by_degree {
if kostka_batched_wins(n, items.len()) {
kostka_batched(&items, n, &mut out);
} else {
for (lambda, c) in items {
for mu in partitions_cached(n).iter() {
let k = kostka(lambda, mu);
if k != 0 {
out.add_term(mu.clone(), C::from_u128(k).mul(c));
}
}
}
}
}
out
}
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
match src {
"h" => multiplicative_to_monomial(terms, false),
"e" => multiplicative_to_monomial(terms, true),
_ => None,
}
}
}
fn kostka_batched_wins(n: u32, terms: usize) -> bool {
n > 0 && n as usize <= MASK_LIMIT && terms >= 2 && terms >= (3 * n as usize).saturating_sub(30)
}
fn kostka_batched<C: Ring>(items: &[(&Partition, &C)], n: u32, out: &mut Monomial<C>) {
let l = n as usize;
let coeff: Map<u64, &C> = items
.iter()
.map(|&(lam, c)| (beta_mask(lam, l), c))
.collect();
let mus = partitions_cached(n);
let leaves: Vec<(&Partition, ())> = mus.iter().map(|mu| (mu, ())).collect();
pieri_trie(
&leaves,
0,
&unit_mask_layer(l),
false,
&mut |mu, (), layer| {
interrupt::poll();
let mut acc = C::zero();
if layer.len() <= coeff.len() {
for (mask, &v) in layer {
if let Some(c) = coeff.get(mask) {
acc.add_assign(&C::from_i128(v).mul(c));
}
}
} else {
for (mask, c) in &coeff {
if let Some(&v) = layer.get(mask) {
acc.add_assign(&C::from_i128(v).mul(c));
}
}
}
out.add_term(mu.clone(), acc);
},
);
}
const MATRIX_ROUTE_LIMIT: u32 = 120;
fn binomial(a: usize, b: usize) -> u128 {
let b = b.min(a - b);
let mut out: u128 = 1;
for i in 0..b {
out = out * (a - i) as u128 / (i + 1) as u128;
}
out
}
fn multiplicative_to_monomial<C: Ring>(
terms: &BTreeMap<Partition, C>,
vertical: bool,
) -> Option<Monomial<C>> {
if terms.keys().any(|mu| mu.size() > MATRIX_ROUTE_LIMIT) {
return None;
}
let items: Vec<(&Partition, &C)> = terms.iter().collect();
let mut root = BTreeMap::new();
root.insert(Partition::default(), C::one());
let mut out = Monomial::zero();
monomial_route_shared(&items, 0, &root, vertical, &mut out);
Some(out)
}
fn monomial_route_shared<C: Ring>(
items: &[(&Partition, &C)],
depth: usize,
layer: &BTreeMap<Partition, C>,
vertical: bool,
out: &mut Monomial<C>,
) {
let mut i = 0;
while i < items.len() && items[i].0.len() == depth {
for (nu, v) in layer {
out.add_term(nu.clone(), v.mul(items[i].1));
}
i += 1;
}
while i < items.len() {
let k = items[i].0.part(depth);
let start = i;
while i < items.len() && items[i].0.part(depth) == k {
i += 1;
}
let next = generator_step(layer, k, vertical);
monomial_route_shared(&items[start..i], depth + 1, &next, vertical, out);
}
}
fn generator_step<C: Ring>(
cur: &BTreeMap<Partition, C>,
k: u32,
vertical: bool,
) -> BTreeMap<Partition, C> {
let mut next: BTreeMap<Partition, C> = BTreeMap::new();
for (nu, c) in cur {
interrupt::poll();
let mut push = |rho: Partition, w: C| {
next.entry(rho)
.or_insert_with(C::zero)
.add_assign(&w.mul(c));
};
if vertical {
e_times_monomial(nu.parts(), k, &mut push);
} else {
h_times_monomial(nu.parts(), k, &mut push);
}
}
next
}
fn h_times_monomial<C: Ring>(nu: &[u32], k: u32, emit: &mut impl FnMut(Partition, C)) {
fn rec<C: Ring>(
nu: &[u32],
i: usize,
left: u32,
prev: u32,
cur: &mut Vec<u32>,
emit: &mut impl FnMut(Partition, C),
) {
if left == 0 {
let len = cur.len();
cur.extend_from_slice(&nu[i.min(nu.len())..]);
let w = arrangements_under(nu, cur);
emit(Partition::from_sorted(cur.clone()), w);
cur.truncate(len);
return;
}
let base = nu.get(i).copied().unwrap_or(0);
let (lo, hi) = if i < nu.len() {
(base, prev.min(base + left))
} else {
(1, prev.min(left))
};
for v in lo..=hi {
cur.push(v);
rec(nu, i + 1, left - (v - base), v, cur, emit);
cur.pop();
}
}
let mut cur = Vec::with_capacity(nu.len() + k as usize);
rec(nu, 0, k, u32::MAX, &mut cur, emit);
}
fn arrangements_under<C: Ring>(nu: &[u32], rho: &[u32]) -> C {
let mut w = C::one();
let mut placed = 0usize;
let mut j = 0usize;
let mut i = 0usize;
while i < nu.len() {
let v = nu[i];
let mut m = 0usize;
while i < nu.len() && nu[i] == v {
m += 1;
i += 1;
}
while j < rho.len() && rho[j] >= v {
j += 1;
}
let b = binomial(j - placed, m);
if b != 1 {
w = w.mul(&C::from_u128(b));
}
placed += m;
}
w
}
fn e_times_monomial<C: Ring>(nu: &[u32], k: u32, emit: &mut impl FnMut(Partition, C)) {
let mut vals: Vec<(u32, u32)> = Vec::new();
for &v in nu {
match vals.last_mut() {
Some((u, m)) if *u == v => *m += 1,
_ => vals.push((v, 1)),
}
}
#[allow(clippy::too_many_arguments)]
fn rec<C: Ring>(
vals: &[(u32, u32)],
i: usize,
left: u32,
prev_val: u32,
prev_kept: u32,
cur: &mut Vec<u32>,
w: &C,
emit: &mut impl FnMut(Partition, C),
) {
if i == vals.len() {
let kept = if prev_val == 1 { prev_kept } else { 0 };
let b = binomial((kept + left) as usize, left as usize);
let w = if b == 1 {
w.clone()
} else {
w.mul(&C::from_u128(b))
};
let len = cur.len();
cur.extend(std::iter::repeat_n(1u32, left as usize));
emit(Partition::from_sorted(cur.clone()), w);
cur.truncate(len);
return;
}
let (v, m) = vals[i];
let kept_above = if prev_val == v + 1 { prev_kept } else { 0 };
for t in 0..=m.min(left) {
let b = binomial((kept_above + t) as usize, t as usize);
let w2 = if b == 1 {
w.clone()
} else {
w.mul(&C::from_u128(b))
};
let len = cur.len();
cur.extend(std::iter::repeat_n(v + 1, t as usize));
cur.extend(std::iter::repeat_n(v, (m - t) as usize));
rec(vals, i + 1, left - t, v, m - t, cur, &w2, emit);
cur.truncate(len);
}
}
let mut cur = Vec::with_capacity(nu.len() + k as usize);
rec(&vals, 0, k, u32::MAX, 0, &mut cur, &C::one(), emit);
}
impl<C: Ring> ToSchur<C> for Monomial<C> {
fn to_schur(&self) -> Schur<C> {
let mut out = Schur::zero();
for (mu, c) in self.terms() {
match muir_expand(mu) {
Some(terms) => {
for (lambda, v) in terms {
out.add_term(lambda, C::from_i128(v).mul(c));
}
}
None => {
let parts = lex_parts_cached(mu.size());
let row = inverse_kostka_row_cached(mu, || inverse_kostka_row(&parts, mu));
for (i, lambda) in parts.iter().enumerate() {
if row[i] != 0 {
out.add_term(lambda.clone(), C::from_i128(row[i]).mul(c));
}
}
}
}
}
out
}
}
impl<C: Ring> ToSchur<C> for Forgotten<C> {
fn to_schur(&self) -> Schur<C> {
Monomial::from_terms(self.terms().clone())
.to_schur()
.omega()
}
}
impl<C: Ring> FromSchur<C> for Forgotten<C> {
fn from_schur(s: &Schur<C>) -> Self {
let m: Monomial<C> = Monomial::from_schur(&s.omega());
Forgotten::from_terms(m.terms().clone())
}
fn from_basis(src: &'static str, terms: &BTreeMap<Partition, C>) -> Option<Self> {
let m = match src {
"h" => multiplicative_to_monomial(terms, true),
"e" => multiplicative_to_monomial(terms, false),
_ => None,
}?;
Some(Forgotten::from_terms(m.terms().clone()))
}
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn muir_expand(mu: &Partition) -> Option<Vec<(Partition, i128)>> {
let l = mu.size() as usize;
if l == 0 {
return Some(vec![(Partition::default(), 1)]);
}
if l > 32 {
return None;
}
let mut avail: Vec<(u32, u32)> = Vec::new();
for &k in mu.parts() {
match avail.last_mut() {
Some((v, n)) if *v == k => *n += 1,
_ => avail.push((k, 1)),
}
}
let mut acc: Map<u64, i128> = Map::default();
muir_rec(
l as i32 - 1,
(1u64 << l) - 1,
&mut avail,
mu.len(),
1,
&mut acc,
);
Some(
acc.into_iter()
.filter(|&(_, v)| v != 0)
.map(|(mask, v)| (mask_to_partition(mask, l), v))
.collect(),
)
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn muir_rec(
v: i32,
mask: u64,
avail: &mut [(u32, u32)],
left: usize,
sign: i128,
acc: &mut Map<u64, i128>,
) {
if v < 0 {
if left == 0 {
*acc.entry(mask).or_insert(0) += sign;
}
return;
}
if left > v as usize + 1 {
return;
}
muir_rec(v - 1, mask, avail, left, sign, acc);
if left == 0 {
return;
}
for i in 0..avail.len() {
if avail[i].1 == 0 {
continue;
}
let nb = v as u32 + avail[i].0;
if mask >> nb & 1 == 1 {
continue; }
let between = mask & (((1u64 << nb) - 1) ^ ((1u64 << (v + 1)) - 1));
let s = if between.count_ones().is_multiple_of(2) {
sign
} else {
-sign
};
avail[i].1 -= 1;
muir_rec(
v - 1,
(mask & !(1 << v)) | (1 << nb),
avail,
left - 1,
s,
acc,
);
avail[i].1 += 1;
}
}
fn inverse_kostka_row(parts: &[Partition], mu: &Partition) -> Vec<i128> {
let size = parts.len();
let j = parts
.iter()
.position(|p| p == mu)
.expect("μ ∈ partitions(|μ|)");
let mut w = vec![0i128; size];
w[j] = 1;
for jj in (j + 1)..size {
let mut acc = 0i128;
for m in j..jj {
if w[m] == 0 {
continue;
}
let k = i128::try_from(kostka(&parts[m], &parts[jj])).unwrap_or_else(|_| {
panic!(
"K_{{{},{}}} does not fit i128; this row solve is \
fixed-width whatever the coefficient ring",
parts[m], parts[jj]
)
});
acc += w[m] * k;
}
w[jj] = -acc;
}
w
}
impl<C: Ring> Monomial<C> {
pub fn mul_via_schur(&self, other: &Self) -> Self {
let prod = self.to_schur().mul(&other.to_schur());
Monomial::from_schur(&prod)
}
}
fn convert_named_dst<C, A>(a: &A, dst: &str) -> Option<BTreeMap<Partition, C>>
where
C: Ring,
A: SymFn<C> + ToSchur<C>,
{
Some(match dst {
"s" => convert::<C, A, Schur<C>>(a).terms().clone(),
"h" => convert::<C, A, Homogeneous<C>>(a).terms().clone(),
"e" => convert::<C, A, Elementary<C>>(a).terms().clone(),
"m" => convert::<C, A, Monomial<C>>(a).terms().clone(),
"f" => convert::<C, A, Forgotten<C>>(a).terms().clone(),
_ => return None,
})
}
pub fn convert_named<C: Ring>(
terms: &BTreeMap<Partition, C>,
src: &str,
dst: &str,
) -> Option<BTreeMap<Partition, C>> {
match src {
"s" => convert_named_dst(&Schur::from_terms(terms.clone()), dst),
"h" => convert_named_dst(&Homogeneous::from_terms(terms.clone()), dst),
"e" => convert_named_dst(&Elementary::from_terms(terms.clone()), dst),
"m" => convert_named_dst(&Monomial::from_terms(terms.clone()), dst),
"f" => convert_named_dst(&Forgotten::from_terms(terms.clone()), dst),
"p" => convert_named_dst(&PowerSum::from_terms(terms.clone()), dst),
_ => None,
}
}
pub fn convert_named_to_power<C: QAlgebra>(
terms: &BTreeMap<Partition, C>,
src: &str,
) -> Option<BTreeMap<Partition, C>> {
fn go<C: QAlgebra, A: SymFn<C> + ToSchur<C>>(a: &A) -> BTreeMap<Partition, C> {
convert::<C, A, PowerSum<C>>(a).terms().clone()
}
Some(match src {
"s" => go(&Schur::from_terms(terms.clone())),
"h" => go(&Homogeneous::from_terms(terms.clone())),
"e" => go(&Elementary::from_terms(terms.clone())),
"m" => go(&Monomial::from_terms(terms.clone())),
"f" => go(&Forgotten::from_terms(terms.clone())),
"p" => terms.clone(),
_ => return None,
})
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::QtPoly;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
const NAMED: [&str; 5] = ["s", "h", "e", "m", "f"];
#[test]
fn convert_named_scales_with_the_coefficient_ring() {
let mut plain: BTreeMap<Partition, i64> = BTreeMap::new();
plain.insert(part(&[2, 1]), 1);
plain.insert(part(&[1, 1, 1]), 2);
plain.insert(part(&[2]), -3);
let scaled: BTreeMap<Partition, QtPoly<i64>> = plain
.iter()
.map(|(la, c)| (la.clone(), QtPoly::term(2, 1, *c)))
.collect();
for src in NAMED {
for dst in NAMED {
let a = convert_named(&plain, src, dst).unwrap();
let b = convert_named(&scaled, src, dst).unwrap();
assert_eq!(a.len(), b.len(), "{src} -> {dst}: term counts differ");
for (la, c) in &a {
assert_eq!(
b.get(la),
Some(&QtPoly::term(2, 1, *c)),
"{src} -> {dst}: coefficient of {la}"
);
}
}
}
}
#[test]
fn convert_named_round_trips_every_ordered_pair() {
let mut f: BTreeMap<Partition, QtPoly<i64>> = BTreeMap::new();
f.insert(part(&[2, 1]), QtPoly::term(0, 1, 1));
f.insert(part(&[1, 1, 1]), QtPoly::term(1, 0, -2));
for src in NAMED {
for dst in NAMED {
let there = convert_named(&f, src, dst).unwrap();
let back = convert_named(&there, dst, src).unwrap();
assert_eq!(back, f, "{src} -> {dst} -> {src}");
}
}
}
#[test]
fn convert_named_declines_power_sum_and_unknown_codes() {
let mut f: BTreeMap<Partition, QtPoly<i64>> = BTreeMap::new();
f.insert(part(&[2]), QtPoly::term(0, 1, 1));
assert!(convert_named(&f, "m", "p").is_none(), "m -> p declines");
assert!(
convert_named(&f, "Schur", "s").is_none(),
"long name declines"
);
assert!(
convert_named(&f, "m", "z").is_none(),
"unknown dst declines"
);
assert!(convert_named(&f, "p", "s").is_some(), "p -> s converts");
}
#[test]
fn convert_named_matches_the_typed_call() {
let mut f: BTreeMap<Partition, Rational> = BTreeMap::new();
f.insert(part(&[2, 1]), Rational::new(3, 2));
let p = PowerSum::from_terms(f.clone());
let h: Homogeneous<Rational> = convert(&p);
assert_eq!(
convert_named(&f, "p", "h").unwrap(),
*h.terms(),
"p -> h, the direct rule"
);
let m = Monomial::from_terms(f.clone());
let fg: Forgotten<Rational> = convert(&m);
assert_eq!(
convert_named(&f, "m", "f").unwrap(),
*fg.terms(),
"m -> f, through the hub"
);
}
#[test]
fn matrix_route_matches_the_schur_hub() {
for n in 0..=9u32 {
for mu in partitions_cached(n).iter() {
let h: Homogeneous<i64> = Homogeneous::monomial(mu.clone(), 1);
let e: Elementary<i64> = Elementary::monomial(mu.clone(), 1);
let hm: Monomial<i64> = convert(&h);
assert_eq!(hm, Monomial::from_schur(&h.to_schur()), "h_{mu} -> m");
let em: Monomial<i64> = convert(&e);
assert_eq!(em, Monomial::from_schur(&e.to_schur()), "e_{mu} -> m");
let hf: Forgotten<i64> = convert(&h);
assert_eq!(hf, Forgotten::from_schur(&h.to_schur()), "h_{mu} -> f");
let ef: Forgotten<i64> = convert(&e);
assert_eq!(ef, Forgotten::from_schur(&e.to_schur()), "e_{mu} -> f");
}
}
let mut h: Homogeneous<i64> = Homogeneous::zero();
for n in 0..=8u32 {
for (i, mu) in partitions_cached(n).iter().enumerate() {
h.add_term(mu.clone(), if i % 2 == 0 { 2 } else { -1 });
}
}
let got: Monomial<i64> = convert(&h);
assert_eq!(
got,
Monomial::from_schur(&h.to_schur()),
"mixed degrees 0..=8, signed"
);
}
#[test]
fn nonneg_and_zero_one_counts_are_not_the_same_rule() {
let terms = BTreeMap::from([(part(&[2, 1]), 1i64)]);
let hm = <Monomial<i64> as FromSchur<i64>>::from_basis("h", &terms).unwrap();
assert_eq!(hm.coeff(&part(&[3])), 1);
assert_eq!(hm.coeff(&part(&[2, 1])), 2);
assert_eq!(hm.coeff(&part(&[1, 1, 1])), 3);
assert_eq!(hm.terms().len(), 3);
let em = <Monomial<i64> as FromSchur<i64>>::from_basis("e", &terms).unwrap();
assert_eq!(em.coeff(&part(&[3])), 0);
assert_eq!(em.coeff(&part(&[2, 1])), 1);
assert_eq!(em.coeff(&part(&[1, 1, 1])), 3);
assert_eq!(em.terms().len(), 2);
}
#[test]
fn matrix_route_declines_past_its_limit() {
let terms = BTreeMap::from([(part(&[MATRIX_ROUTE_LIMIT + 1]), 1i64)]);
assert!(<Monomial<i64> as FromSchur<i64>>::from_basis("h", &terms).is_none());
assert!(<Forgotten<i64> as FromSchur<i64>>::from_basis("e", &terms).is_none());
}
#[test]
fn forgotten_endpoints_match_hand_computation() {
for n in 1..=6u32 {
let row: Forgotten<i64> = Forgotten::monomial(part(&[n]), 1);
let want = if (n - 1) % 2 == 0 { 1 } else { -1 };
let got: PowerSum<Rational> = PowerSum::from_schur(&to_rat(&row.to_schur()));
assert_eq!(got.terms().len(), 1, "f_({n}) should be a single p term");
assert_eq!(got.coeff(&part(&[n])), Rational::from_int(want));
let col: Forgotten<i64> = Forgotten::monomial(part(&vec![1; n as usize]), 1);
let h: Homogeneous<i64> = Homogeneous::from_schur(&col.to_schur());
assert_eq!(h.coeff(&part(&[n])), 1);
assert_eq!(h.terms().len(), 1, "f_(1^{n}) should be exactly h_{n}");
}
}
#[test]
fn forgotten_is_dual_to_elementary() {
for n in 0..=7u32 {
let parts = partitions_cached(n);
for lambda in parts.iter() {
let f: Forgotten<i64> = Forgotten::monomial(lambda.clone(), 1);
for mu in parts.iter() {
let e: Elementary<i64> = Elementary::monomial(mu.clone(), 1);
let want = i64::from(lambda == mu);
assert_eq!(
crate::ops::hall::<i64, _, _>(&f, &e),
want,
"<f_{lambda}, e_{mu}>"
);
}
}
}
}
#[test]
fn forgotten_round_trips_through_every_basis() {
for n in 0..=7u32 {
for lambda in partitions_cached(n).iter() {
let f: Forgotten<i64> = Forgotten::monomial(lambda.clone(), 1);
let s = f.to_schur();
assert_eq!(Forgotten::from_schur(&s), f, "f -> s -> f");
let m: Monomial<i64> = Monomial::from_schur(&s);
assert_eq!(Forgotten::from_schur(&m.to_schur()), f, "via m");
let e: Elementary<i64> = Elementary::from_schur(&s);
assert_eq!(Forgotten::from_schur(&e.to_schur()), f, "via e");
let h: Homogeneous<i64> = Homogeneous::from_schur(&s);
assert_eq!(Forgotten::from_schur(&h.to_schur()), f, "via h");
}
}
}
fn to_rat(s: &Schur<i64>) -> Schur<Rational> {
let mut out = Schur::zero();
for (p, c) in s.terms() {
out.add_term(p.clone(), Rational::from_int(*c as i128));
}
out
}
#[test]
fn h_and_e_expand_into_schur() {
let h11: Homogeneous<i64> = Homogeneous::monomial(part(&[1, 1]), 1);
let s = h11.to_schur();
assert_eq!(s.coeff(&part(&[2])), 1);
assert_eq!(s.coeff(&part(&[1, 1])), 1);
let e2: Elementary<i64> = Elementary::monomial(part(&[2]), 1);
let se = e2.to_schur();
assert_eq!(se.coeff(&part(&[1, 1])), 1);
assert_eq!(se.terms().len(), 1);
}
#[test]
fn the_direct_multiplicative_routes_agree_with_the_hub() {
for n in 0..=9u32 {
for lambda in partitions_cached(n).iter() {
let h: Homogeneous<i64> = Homogeneous::monomial(lambda.clone(), 1);
let e: Elementary<i64> = Elementary::monomial(lambda.clone(), 1);
let p: PowerSum<i64> = PowerSum::monomial(lambda.clone(), 1);
assert_eq!(
convert::<i64, _, Elementary<i64>>(&h),
Elementary::from_schur(&h.to_schur()),
"h_{lambda} -> e"
);
assert_eq!(
convert::<i64, _, Homogeneous<i64>>(&e),
Homogeneous::from_schur(&e.to_schur()),
"e_{lambda} -> h"
);
assert_eq!(
convert::<i64, _, Homogeneous<i64>>(&p),
Homogeneous::from_schur(&p.to_schur()),
"p_{lambda} -> h"
);
assert_eq!(
convert::<i64, _, Elementary<i64>>(&p),
Elementary::from_schur(&p.to_schur()),
"p_{lambda} -> e"
);
let hq: Homogeneous<Rational> =
Homogeneous::monomial(lambda.clone(), Rational::one());
let eq: Elementary<Rational> =
Elementary::monomial(lambda.clone(), Rational::one());
assert_eq!(
convert::<Rational, _, PowerSum<Rational>>(&hq),
PowerSum::from_schur(&hq.to_schur()),
"h_{lambda} -> p"
);
assert_eq!(
convert::<Rational, _, PowerSum<Rational>>(&eq),
PowerSum::from_schur(&eq.to_schur()),
"e_{lambda} -> p"
);
}
}
}
#[test]
fn jacobi_trudi_inverts_expansion() {
let s11: Schur<i64> = Schur::monomial(part(&[1, 1]), 1);
let h = Homogeneous::from_schur(&s11);
assert_eq!(h.coeff(&part(&[1, 1])), 1);
assert_eq!(h.coeff(&part(&[2])), -1);
}
#[test]
fn batched_p_expansion_matches_per_term() {
for n in 0..=10u32 {
let mus = partitions_cached(n);
let mut elt: PowerSum<i128> = PowerSum::zero();
for (i, mu) in mus.iter().enumerate() {
elt.add_term(mu.clone(), (i as i128) + 1);
}
let got: Schur<i128> = elt.to_schur();
let mut want: Schur<i128> = Schur::zero();
for (i, mu) in mus.iter().enumerate() {
for (lambda, chi) in p_expand(mu).expect("small degree") {
want.add_term(lambda, chi * ((i as i128) + 1));
}
}
assert_eq!(got, want, "batched p → s at degree {n}");
}
}
#[test]
fn the_two_mask_widths_agree_where_both_apply() {
for n in 1..=14u32 {
let mus = partitions_cached(n);
let items: Vec<(&Partition, &i128)> = mus.iter().map(|mu| (mu, &1i128)).collect();
let mut narrow: Schur<i128> = Schur::zero();
sweep_degree::<u64, i128>(&items, n as usize, &mut narrow);
let mut wide: Schur<i128> = Schur::zero();
sweep_degree::<u128, i128>(&items, n as usize, &mut wide);
assert_eq!(narrow, wide, "u64 and u128 sweeps disagree at degree {n}");
}
}
#[test]
fn the_wide_mask_expands_a_power_sum_to_its_hooks() {
for n in [33u32, 40, WIDE_MASK_LIMIT as u32] {
let p: PowerSum<i128> = PowerSum::monomial(Partition::new([n]), 1);
let mut want: Schur<i128> = Schur::zero();
for r in 0..n {
let mut parts = vec![n - r];
parts.extend(std::iter::repeat_n(1, r as usize));
want.add_term(
Partition::from_sorted(parts),
if r % 2 == 0 { 1 } else { -1 },
);
}
assert_eq!(p.to_schur(), want, "p_{n} → s is not the hook sum");
}
}
#[test]
fn integral_sweep_matches_rational_arithmetic() {
for n in 0..=10u32 {
let mus = partitions_cached(n);
let mut elt: PowerSum<Rational> = PowerSum::zero();
for mu in mus.iter() {
elt.add_term(mu.clone(), Rational::new(1, mu.z() as i128));
}
let got: Schur<Rational> = elt.to_schur();
let mut want: Schur<Rational> = Schur::zero();
for mu in mus.iter() {
let c = Rational::new(1, mu.z() as i128);
for (lambda, chi) in p_expand(mu).expect("small degree") {
want.add_term(lambda, Rational::from_i128(chi).mul(&c));
}
}
assert_eq!(got, want, "integral p → s at degree {n}");
}
}
#[test]
fn rings_that_decline_as_ratio_fall_back_cleanly() {
for n in 0..=8u32 {
let mus = partitions_cached(n);
let mut elt: PowerSum<i128> = PowerSum::zero();
for (i, mu) in mus.iter().enumerate() {
elt.add_term(mu.clone(), (i as i128) - 3);
}
assert!(i128::from_ratio(1, 2).is_none(), "i128 should decline");
let got: Schur<i128> = elt.to_schur();
let mut want: Schur<i128> = Schur::zero();
for (i, mu) in mus.iter().enumerate() {
for (lambda, chi) in p_expand(mu).expect("small degree") {
want.add_term(lambda, chi * ((i as i128) - 3));
}
}
assert_eq!(got, want, "fallback p → s at degree {n}");
}
}
#[test]
fn muir_agrees_with_the_inverse_kostka_solve() {
for n in 0..=12u32 {
let parts = lex_parts_cached(n);
for mu in parts.iter() {
let row = inverse_kostka_row(&parts, mu);
let mut want: Vec<(Partition, i128)> = parts
.iter()
.zip(&row)
.filter(|(_, &v)| v != 0)
.map(|(l, &v)| (l.clone(), v))
.collect();
let mut got = muir_expand(mu).expect("degree 12 is inside the mask");
want.sort();
got.sort();
assert_eq!(got, want, "m_{mu} in the Schur basis");
}
}
}
#[test]
fn batched_kostka_sweep_matches_per_pair() {
fn per_pair(items: &[(&Partition, &i128)], n: u32) -> Monomial<i128> {
let mut want = Monomial::zero();
for &(lambda, c) in items {
for mu in partitions_cached(n).iter() {
want.add_term(mu.clone(), i128::from_u128(kostka(lambda, mu)) * c);
}
}
want
}
let mut mixed: Schur<i128> = Schur::zero();
for n in 1..=12u32 {
let parts = partitions_cached(n);
let coeffs: Vec<i128> = (0..parts.len())
.map(|i| [3, -1, 2, -5, 1][i % 5] * (i as i128 % 7 - 3))
.collect();
let full: Vec<(&Partition, &i128)> = parts.iter().zip(&coeffs).collect();
let thin: Vec<(&Partition, &i128)> = full.iter().copied().step_by(9).collect();
for (name, items) in [("full", &full), ("thin", &thin)] {
let mut got = Monomial::zero();
kostka_batched(items, n, &mut got);
assert_eq!(got, per_pair(items, n), "degree {n}, {name} support");
}
for &(lambda, c) in &full {
mixed.add_term(lambda.clone(), *c);
}
}
let got: Monomial<i128> = Monomial::from_schur(&mixed);
let mut want = Monomial::zero();
for (lambda, c) in mixed.terms() {
for mu in partitions_cached(lambda.size()).iter() {
want.add_term(mu.clone(), i128::from_u128(kostka(lambda, mu)) * c);
}
}
assert_eq!(got, want, "mixed degrees 1..=12 through from_schur");
}
#[test]
fn muir_matches_hand_computation() {
let got = muir_expand(&part(&[2, 1])).unwrap();
let mut got: Vec<_> = got.iter().map(|(l, c)| (l.parts().to_vec(), *c)).collect();
got.sort();
assert_eq!(got, vec![(vec![1, 1, 1], -2), (vec![2, 1], 1)]);
let got = muir_expand(&part(&[5])).unwrap();
let mut got: Vec<_> = got.iter().map(|(l, c)| (l.parts().to_vec(), *c)).collect();
got.sort_by_key(|(l, _)| l.len());
let want = vec![
(vec![5], 1),
(vec![4, 1], -1),
(vec![3, 1, 1], 1),
(vec![2, 1, 1, 1], -1),
(vec![1, 1, 1, 1, 1], 1),
];
assert_eq!(got, want);
}
fn strips_via_masks(lambda: &Partition, k: u32, vertical: bool) -> Vec<Partition> {
let l = lambda.size() as usize + k as usize;
let mut masks = Vec::new();
strip_masks(beta_mask(lambda, l), k, vertical, &mut masks);
let mut out: Vec<Partition> = masks.into_iter().map(|m| mask_to_partition(m, l)).collect();
out.sort();
out
}
#[test]
fn beta_mask_strips_agree_with_the_partition_enumeration() {
for n in 0..=10u32 {
for lambda in partitions_cached(n).iter() {
for k in 0..=6u32 {
let mut want = Vec::new();
horizontal_strips(lambda.parts(), k, &mut want);
want.sort();
assert_eq!(
strips_via_masks(lambda, k, false),
want,
"horizontal {k}-strips on {lambda}"
);
let mut want = Vec::new();
vertical_strips(lambda.parts(), k, &mut want);
want.sort();
assert_eq!(
strips_via_masks(lambda, k, true),
want,
"vertical {k}-strips on {lambda}"
);
}
}
}
}
#[test]
fn horizontal_and_vertical_strips_are_not_the_same_rule() {
let lambda = part(&[2, 1]);
let h = strips_via_masks(&lambda, 2, false);
let v = strips_via_masks(&lambda, 2, true);
assert!(h.contains(&part(&[4, 1])), "horizontal: two cells in row 0");
assert!(!v.contains(&part(&[4, 1])), "vertical: never two in a row");
assert!(
v.contains(&part(&[2, 1, 1, 1])),
"vertical: two cells in column 0"
);
assert!(
!h.contains(&part(&[2, 1, 1, 1])),
"horizontal: never two in a column"
);
assert!(
h.contains(&part(&[3, 2])) && v.contains(&part(&[3, 2])),
"both rules accept (3,2)"
);
}
#[test]
fn pieri_steps_agree_with_the_lr_product() {
for n in 0..=7u32 {
for lambda in partitions_cached(n).iter() {
for k in 1..=4u32 {
let s: Schur<i128> = Schur::monomial(lambda.clone(), 1);
for vertical in [false, true] {
let gen = if vertical {
Partition::new(std::iter::repeat_n(1, k as usize))
} else {
Partition::new([k])
};
let want = s.mul(&Schur::monomial(gen, 1));
let mut got: Schur<i128> = Schur::zero();
for mu in strips_via_masks(lambda, k, vertical) {
got.add_term(mu, 1);
}
assert_eq!(
got,
want,
"s_{lambda} * {}_{k}",
if vertical { "e" } else { "h" }
);
}
}
}
}
}
#[test]
fn round_trips_are_identity() {
for parts in [&[2, 1][..], &[3, 1], &[2, 2], &[3, 2, 1]] {
let s: Schur<i64> = Schur::monomial(part(parts), 1);
let back_h: Schur<i64> = convert(&Homogeneous::from_schur(&s));
let back_e: Schur<i64> = convert(&Elementary::from_schur(&s));
let back_m: Schur<i64> = convert(&Monomial::from_schur(&s));
assert_eq!(back_h, s, "s→h→s at {:?}", parts);
assert_eq!(back_e, s, "s→e→s at {:?}", parts);
assert_eq!(back_m, s, "s→m→s at {:?}", parts);
}
}
#[test]
fn power_sum_round_trip_over_rationals() {
for parts in [&[2, 1][..], &[3], &[2, 2], &[3, 1]] {
let s: Schur<Rational> = Schur::monomial(part(parts), Rational::one());
let p: PowerSum<Rational> = PowerSum::from_schur(&s);
let back: Schur<Rational> = p.to_schur();
assert_eq!(back, s, "s→p→s at {:?}", parts);
}
}
#[test]
fn power_sum_two_is_s2_minus_s11() {
let p2: PowerSum<i64> = PowerSum::monomial(part(&[2]), 1);
let s = p2.to_schur();
assert_eq!(s.coeff(&part(&[2])), 1);
assert_eq!(s.coeff(&part(&[1, 1])), -1);
}
#[test]
fn monomial_multiplication_via_schur() {
let m1: Monomial<i64> = Monomial::monomial(part(&[1]), 1);
let prod = m1.mul(&m1);
assert_eq!(prod.coeff(&part(&[1, 1])), 2);
assert_eq!(prod.coeff(&part(&[2])), 1);
assert_eq!(prod.terms().len(), 2);
}
}