#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use std::sync::Arc;
use crate::coeff::{QAlgebra, Rational, Ring};
use crate::convert::{FromSchur, ToSchur};
use crate::guard::{guarded, overflow_count, GuardedRat};
use crate::kostka::kostka;
use crate::memo::{
bold_p_peek, bold_p_store, ht_to_st_cached, reduced_kronecker_cached, schur_to_st_cached,
st_to_ht_cached, st_to_schur_cached,
};
use crate::partition::Partition;
use crate::sym::{impl_product_ops, Ht, PowerSum, Schur, St, SymAlgebra, SymFn};
fn divisors(n: u32) -> Vec<u32> {
(1..=n).filter(|d| n.is_multiple_of(*d)).collect()
}
fn mobius(n: u32) -> i128 {
let mut n = n;
let mut primes = 0;
let mut d = 2;
while d * d <= n {
if n.is_multiple_of(d) {
n /= d;
if n.is_multiple_of(d) {
return 0; }
primes += 1;
}
d += 1;
}
if n > 1 {
primes += 1;
}
if primes % 2 == 0 {
1
} else {
-1
}
}
fn multiplicities(gamma: &Partition) -> Vec<(u32, usize)> {
let mut out: Vec<(u32, usize)> = Vec::new();
for &part in gamma.parts().iter().rev() {
match out.last_mut() {
Some((p, m)) if *p == part => *m += 1,
_ => out.push((part, 1)),
}
}
out
}
fn bold_uni(i: u32, r: usize) -> Vec<i128> {
let mut falls: Vec<Vec<i128>> = vec![vec![1]];
for k in 1..=r {
let prev = &falls[k - 1];
let mut next = vec![0i128; k + 1];
for (m, &c) in prev.iter().enumerate() {
next[m + 1] += c; next[m] -= c * (k as i128 - 1); }
falls.push(next);
}
let mut out = vec![0i128; r + 1];
let mut binom = 1i128; for k in 0..=r {
let sign = if (r - k).is_multiple_of(2) { 1 } else { -1 };
let scale = sign * (i as i128).pow(k as u32) * binom;
for (m, &c) in falls[k].iter().enumerate() {
out[m] += scale * c;
}
binom = binom * (r as i128 - k as i128) / (k as i128 + 1);
}
out
}
trait RatLike: QAlgebra {
type Int: IntLike;
fn as_integer(&self) -> Option<i128>;
fn numerator(&self) -> Self::Int;
fn denominator(&self) -> Self::Int;
}
impl RatLike for Rational {
type Int = i128;
fn as_integer(&self) -> Option<i128> {
(self.denom() == 1).then(|| self.numer())
}
fn numerator(&self) -> i128 {
self.numer()
}
fn denominator(&self) -> i128 {
self.denom()
}
}
impl RatLike for GuardedRat {
type Int = i128;
fn as_integer(&self) -> Option<i128> {
(self.denom() == 1).then(|| self.numer())
}
fn numerator(&self) -> i128 {
self.numer()
}
fn denominator(&self) -> i128 {
self.denom()
}
}
#[cfg(feature = "bignum")]
impl RatLike for num_rational::BigRational {
type Int = num_bigint::BigInt;
fn as_integer(&self) -> Option<i128> {
use num_traits::ToPrimitive;
self.is_integer()
.then(|| self.to_integer().to_i128())
.flatten()
}
fn numerator(&self) -> num_bigint::BigInt {
self.numer().clone()
}
fn denominator(&self) -> num_bigint::BigInt {
self.denom().clone()
}
}
trait IntLike: Clone + PartialEq {
fn zero() -> Self;
fn one() -> Self;
fn is_zero(&self) -> bool;
fn checked_mul(&self, o: &Self) -> Option<Self>;
fn checked_add(&self, o: &Self) -> Option<Self>;
fn checked_lcm(&self, o: &Self) -> Option<Self>;
fn div_exact(&self, o: &Self) -> Self;
fn checked_div_exact(&self, o: &Self) -> Option<Self>;
fn character(lambda: &Partition, mu: &Partition) -> Option<Self>;
fn as_i128(&self) -> Option<i128>;
}
impl IntLike for i128 {
fn zero() -> Self {
0
}
fn one() -> Self {
1
}
fn is_zero(&self) -> bool {
*self == 0
}
fn checked_mul(&self, o: &Self) -> Option<Self> {
i128::checked_mul(*self, *o)
}
fn checked_add(&self, o: &Self) -> Option<Self> {
i128::checked_add(*self, *o)
}
fn checked_lcm(&self, o: &Self) -> Option<Self> {
let g = crate::modular::gcd128(self.unsigned_abs(), o.unsigned_abs());
(self / i128::try_from(g).ok()?).checked_mul(*o)
}
fn div_exact(&self, o: &Self) -> Self {
debug_assert_eq!(self % o, 0);
self / o
}
fn checked_div_exact(&self, o: &Self) -> Option<Self> {
(self % o == 0).then(|| self / o)
}
fn character(lambda: &Partition, mu: &Partition) -> Option<Self> {
crate::character::try_character(lambda, mu)
}
fn as_i128(&self) -> Option<i128> {
Some(*self)
}
}
#[cfg(feature = "bignum")]
impl IntLike for num_bigint::BigInt {
fn zero() -> Self {
<num_bigint::BigInt as num_traits::Zero>::zero()
}
fn one() -> Self {
<num_bigint::BigInt as num_traits::One>::one()
}
fn is_zero(&self) -> bool {
num_traits::Zero::is_zero(self)
}
fn checked_mul(&self, o: &Self) -> Option<Self> {
Some(self * o)
}
fn checked_add(&self, o: &Self) -> Option<Self> {
Some(self + o)
}
fn checked_lcm(&self, o: &Self) -> Option<Self> {
let (mut a, mut b) = (self.clone(), o.clone());
while !num_traits::Zero::is_zero(&b) {
let t = &a % &b;
a = b;
b = t;
}
Some(self / &a * o)
}
fn div_exact(&self, o: &Self) -> Self {
self / o
}
fn checked_div_exact(&self, o: &Self) -> Option<Self> {
num_traits::Zero::is_zero(&(self % o)).then(|| self / o)
}
fn character(lambda: &Partition, mu: &Partition) -> Option<Self> {
Some(crate::character::character_in(lambda, mu))
}
fn as_i128(&self) -> Option<i128> {
num_traits::ToPrimitive::to_i128(self)
}
}
fn bold_uni_inverse<R: RatLike>(i: u32, m: usize) -> Vec<R> {
let rows: Vec<Vec<i128>> = (0..=m).map(|r| bold_uni(i, r)).collect();
let mut coeffs = vec![R::zero(); m + 1];
let mut rem = vec![R::zero(); m + 1];
rem[m] = R::one();
for r in (0..=m).rev() {
if rem[r].is_zero() {
continue;
}
let c = rem[r].div_u128((i as u128).pow(r as u32));
coeffs[r] = c.clone();
for (j, &b) in rows[r].iter().enumerate().take(r + 1) {
let term = c.mul(&R::from_i128(b));
rem[j].sub_assign(&term);
}
}
coeffs
}
fn p_variable<R: RatLike>(i: u32) -> PowerSum<R> {
let mut out = PowerSum::zero();
for d in divisors(i) {
let m = mobius(i / d);
if m != 0 {
out.add_term(Partition::new([d]), R::from_i128(m).div_u128(i as u128));
}
}
out
}
fn bold_p_in<R: RatLike>(gamma: &Partition) -> PowerSum<R> {
let mut acc: PowerSum<R> = PowerSum::unit();
for (i, r) in multiplicities(gamma) {
let coeffs = bold_uni(i, r);
let pi = p_variable::<R>(i);
let mut power: PowerSum<R> = PowerSum::unit();
let mut factor = PowerSum::zero();
for (m, &c) in coeffs.iter().enumerate() {
if m > 0 {
power = power.mul(&pi);
}
if c != 0 {
factor = factor.add(&power.scale(&R::from_i128(c)));
}
}
acc = acc.mul(&factor);
}
acc
}
fn bold_guarded(gamma: &Partition) -> PowerSum<GuardedRat> {
if let Some(v) = bold_p_peek(gamma) {
return (*v).clone();
}
let before = overflow_count();
let value = bold_p_in::<GuardedRat>(gamma);
if overflow_count() == before {
bold_p_store(gamma, value.clone());
}
value
}
fn gamma<R: RatLike>(f: &PowerSum<R>, bold: fn(&Partition) -> PowerSum<R>) -> PowerSum<R> {
let mut out = PowerSum::zero();
for (g, c) in f.terms() {
crate::interrupt::poll();
for (idx, v) in bold(g).terms() {
out.add_term(idx.clone(), v.mul(c));
}
}
out
}
fn gamma_inverse<R: RatLike>(f: &PowerSum<R>) -> PowerSum<R> {
let mut monomials: BTreeMap<Partition, R> = BTreeMap::new();
for (g, c) in f.terms() {
crate::interrupt::poll();
let mut acc: BTreeMap<Vec<u32>, R> = BTreeMap::new();
acc.insert(Vec::new(), c.clone());
for &part in g.parts() {
let mut next: BTreeMap<Vec<u32>, R> = BTreeMap::new();
for (mono, cc) in &acc {
for d in divisors(part) {
let mut key = mono.clone();
key.push(d);
key.sort_unstable_by(|a, b| b.cmp(a));
let v = cc.mul(&R::from_i128(d as i128));
next.entry(key)
.and_modify(|e| e.add_assign(&v))
.or_insert(v);
}
}
acc = next;
}
for (mono, v) in acc {
if v.is_zero() {
continue;
}
let key = Partition::new(mono);
monomials
.entry(key)
.and_modify(|e| e.add_assign(&v))
.or_insert(v);
}
}
let mut out = PowerSum::zero();
for (mono, c) in monomials {
crate::interrupt::poll();
if c.is_zero() {
continue;
}
let mut acc: BTreeMap<Vec<u32>, R> = BTreeMap::new();
acc.insert(Vec::new(), c);
for (i, m) in multiplicities(&mono) {
let inv = bold_uni_inverse::<R>(i, m);
let mut next: BTreeMap<Vec<u32>, R> = BTreeMap::new();
for (idx, cc) in &acc {
for (r, n) in inv.iter().enumerate() {
if n.is_zero() {
continue;
}
let mut key = idx.clone();
key.extend(std::iter::repeat_n(i, r));
key.sort_unstable_by(|a, b| b.cmp(a));
let v = cc.mul(n);
next.entry(key)
.and_modify(|e| e.add_assign(&v))
.or_insert(v);
}
}
acc = next;
}
for (idx, v) in acc {
out.add_term(Partition::new(idx), v);
}
}
out
}
fn integral_row<R: RatLike>(f: &Schur<R>) -> Option<Vec<(Partition, i128)>> {
f.terms()
.iter()
.map(|(p, c)| c.as_integer().map(|n| (p.clone(), n)))
.collect()
}
fn st_in_power_sum<R: RatLike>(
lambda: &Partition,
bold: fn(&Partition) -> PowerSum<R>,
) -> PowerSum<R> {
let s: Schur<R> = Schur::monomial(lambda.clone(), R::one());
gamma(&PowerSum::from_schur(&s), bold)
}
fn escalating<T>(
what: &str,
fast: impl FnOnce() -> Option<T>,
exact: impl FnOnce() -> Option<T>,
) -> T {
if let Some(Some(v)) = guarded(fast) {
return v;
}
#[cfg(feature = "bignum")]
{
let _ = what;
exact().unwrap_or_else(|| {
panic!(
"{what}: a coefficient is not an integer over BigRational, which is a bug \
rather than an overflow"
)
})
}
#[cfg(not(feature = "bignum"))]
{
let _ = exact;
panic!(
"{what}: an intermediate coefficient left i128. The answers are almost \
certainly small — the wall is the z_γ-sized denominators this route \
divides by or clears, not the coefficients it returns. Rebuild with \
--features bignum."
)
}
}
fn st_to_schur_row(lambda: &Partition) -> Arc<Vec<(Partition, i128)>> {
st_to_schur_cached(lambda, || {
let n = lambda.size();
let rows = escalating(
&format!("s̃ → s at degree {n}"),
|| st_to_schur_degree::<GuardedRat>(n, bold_guarded),
|| {
#[cfg(feature = "bignum")]
{
st_to_schur_degree::<num_rational::BigRational>(n, bold_p_in)
}
#[cfg(not(feature = "bignum"))]
None
},
);
let mut mine = None;
for (v, row) in crate::memo::partitions_cached(n).iter().zip(rows) {
if v == lambda {
mine = Some(row);
} else {
st_to_schur_cached(v, || row);
}
}
mine.expect("partitions_cached(|λ|) lists every partition of |λ|")
})
}
fn st_to_schur_degree<R: RatLike>(
n: u32,
bold: fn(&Partition) -> PowerSum<R>,
) -> Option<Vec<Vec<(Partition, i128)>>> {
degree_rows(n, |g| {
let mut pg: PowerSum<R> = PowerSum::zero();
pg.add_term(g.clone(), g.div_by_z(&R::one()));
gamma(&pg, bold)
})
}
fn schur_to_st_degree<R: RatLike>(n: u32) -> Option<Vec<Vec<(Partition, i128)>>> {
degree_rows(n, |g| {
let mut pg: PowerSum<R> = PowerSum::zero();
pg.add_term(g.clone(), g.div_by_z(&R::one()));
gamma_inverse(&pg)
})
}
fn degree_rows<R: RatLike>(
n: u32,
per_gamma: impl Fn(&Partition) -> PowerSum<R>,
) -> Option<Vec<Vec<(Partition, i128)>>> {
let parts = crate::memo::partitions_cached(n);
let by_degree: Vec<_> = (0..=n).map(crate::memo::partitions_cached).collect();
let offsets: Vec<usize> = by_degree
.iter()
.scan(0usize, |acc, p| {
let o = *acc;
*acc += p.len();
Some(o)
})
.collect();
let total = offsets[n as usize] + parts.len();
struct Cleared<I> {
denom: I,
terms: Vec<(u32, I)>,
}
let mut shared: Vec<Cleared<R::Int>> = Vec::with_capacity(parts.len());
for g in parts.iter() {
crate::interrupt::poll();
let v = per_gamma(g);
let mut denom = R::Int::one();
for c in v.terms().values() {
denom = denom.checked_lcm(&c.denominator())?;
}
let mut dense: Vec<R::Int> = vec![R::Int::zero(); total];
for (delta, c) in v.terms() {
let u = c
.numerator()
.checked_mul(&denom.div_exact(&c.denominator()))?;
let d = delta.size() as usize;
for (i, lam) in by_degree[d].iter().enumerate() {
let chi = R::Int::character(lam, delta)?;
if chi.is_zero() {
continue;
}
let slot = &mut dense[offsets[d] + i];
*slot = slot.checked_add(&u.checked_mul(&chi)?)?;
}
}
let terms = dense
.into_iter()
.enumerate()
.filter(|(_, v)| !v.is_zero())
.map(|(i, v)| (i as u32, v))
.collect();
shared.push(Cleared { denom, terms });
}
let mut l = R::Int::one();
for c in &shared {
l = l.checked_lcm(&c.denom)?;
}
let flat_partition = |idx: usize| {
let d = offsets.partition_point(|&o| o <= idx) - 1;
&by_degree[d][idx - offsets[d]]
};
let mut out = Vec::with_capacity(parts.len());
for lam in parts.iter() {
crate::interrupt::poll();
let mut acc: Vec<R::Int> = vec![R::Int::zero(); total];
for (g, cl) in parts.iter().zip(shared.iter()) {
let chi = R::Int::character(lam, g)?;
if chi.is_zero() {
continue;
}
let scale = chi.checked_mul(&l.div_exact(&cl.denom))?;
for (idx, x) in &cl.terms {
let slot = &mut acc[*idx as usize];
*slot = slot.checked_add(&scale.checked_mul(x)?)?;
}
}
let mut row = Vec::new();
for (idx, v) in acc.iter().enumerate() {
if v.is_zero() {
continue;
}
let r = v.checked_div_exact(&l)?.as_i128()?;
row.push((flat_partition(idx).clone(), r));
}
out.push(row);
}
Some(out)
}
fn schur_to_st_row(nu: &Partition) -> Arc<Vec<(Partition, i128)>> {
schur_to_st_cached(nu, || {
let n = nu.size();
let rows = escalating(
&format!("s → s̃ at degree {n}"),
|| schur_to_st_degree::<GuardedRat>(n),
|| {
#[cfg(feature = "bignum")]
{
schur_to_st_degree::<num_rational::BigRational>(n)
}
#[cfg(not(feature = "bignum"))]
None
},
);
let mut mine = None;
for (v, row) in crate::memo::partitions_cached(n).iter().zip(rows) {
if v == nu {
mine = Some(row);
} else {
schur_to_st_cached(v, || row);
}
}
mine.expect("partitions_cached(|ν|) lists every partition of |ν|")
})
}
fn reduced_kronecker_row(lambda: &Partition, mu: &Partition) -> Arc<Vec<(Partition, i128)>> {
reduced_kronecker_cached(lambda, mu, || {
fn run<R: RatLike>(
lambda: &Partition,
mu: &Partition,
bold: fn(&Partition) -> PowerSum<R>,
) -> Option<Vec<(Partition, i128)>> {
let prod = st_in_power_sum(lambda, bold).mul(&st_in_power_sum(mu, bold));
integral_row(&gamma_inverse(&prod).to_schur())
}
escalating(
&format!("s̃_{lambda} · s̃_{mu}"),
|| run(lambda, mu, bold_guarded),
|| {
#[cfg(feature = "bignum")]
{
run::<num_rational::BigRational>(lambda, mu, bold_p_in)
}
#[cfg(not(feature = "bignum"))]
None
},
)
})
}
impl<C: Ring> ToSchur<C> for St<C> {
fn to_schur(&self) -> Schur<C> {
let mut out = Schur::zero();
for (lambda, c) in self.terms() {
for (nu, k) in st_to_schur_row(lambda).iter() {
out.add_term(nu.clone(), C::from_i128(*k).mul(c));
}
}
out
}
}
impl<C: Ring> FromSchur<C> for St<C> {
fn from_schur(s: &Schur<C>) -> Self {
let mut out = St::zero();
for (nu, c) in s.terms() {
for (lambda, k) in schur_to_st_row(nu).iter() {
out.add_term(lambda.clone(), C::from_i128(*k).mul(c));
}
}
out
}
}
impl<C: Ring> St<C> {
pub fn mul(&self, other: &Self) -> Self {
let mut out = Self::zero();
for (lambda, cl) in self.terms() {
for (mu, cm) in other.terms() {
let scale = cl.mul(cm);
for (nu, k) in reduced_kronecker_row(lambda, mu).iter() {
out.add_term(nu.clone(), C::from_i128(*k).mul(&scale));
}
}
}
out
}
}
impl_product_ops!(St);
impl<C: Ring> SymAlgebra<C> for St<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
pub fn reduced_kronecker_product<C: Ring>(lambda: &Partition, mu: &Partition) -> St<C> {
let mut out = St::zero();
for (nu, k) in reduced_kronecker_row(lambda, mu).iter() {
out.add_term(nu.clone(), C::from_i128(*k));
}
out
}
pub fn reduced_kronecker<C: Ring>(lambda: &Partition, mu: &Partition, nu: &Partition) -> C {
reduced_kronecker_row(lambda, mu)
.iter()
.find(|(p, _)| p == nu)
.map(|(_, k)| C::from_i128(*k))
.unwrap_or_else(C::zero)
}
fn horizontal_strips(lambda: &Partition, k: u32) -> Vec<Partition> {
let l = lambda.parts();
let mut out = Vec::new();
let mut current: Vec<u32> = Vec::with_capacity(l.len() + 1);
fn rec(i: usize, left: u32, l: &[u32], current: &mut Vec<u32>, out: &mut Vec<Partition>) {
if i == l.len() + 1 {
if left == 0 {
out.push(Partition::new(current.clone()));
}
return;
}
let lo = if i < l.len() { l[i] } else { 0 };
let hi = if i == 0 {
lo + left
} else {
l[i - 1].min(lo + left)
};
for v in lo..=hi {
current.push(v);
rec(i + 1, left - (v - lo), l, current, out);
current.pop();
}
}
rec(0, k, l, &mut current, &mut out);
out
}
fn ht_to_st_coeff(lambda: &Partition, mu: &Partition) -> u128 {
if lambda.size() > mu.size() {
return 0;
}
horizontal_strips(lambda, mu.size() - lambda.size())
.iter()
.map(|g| kostka(g, mu))
.sum()
}
fn ht_to_st_row(mu: &Partition) -> Arc<Vec<(Partition, i128)>> {
ht_to_st_cached(mu, || {
let mut out = Vec::new();
for size in 0..=mu.size() {
for lambda in crate::memo::partitions_cached(size).iter() {
let c = ht_to_st_coeff(lambda, mu);
if c != 0 {
let c = i128::try_from(c).unwrap_or_else(|_| {
panic!("the h̃ → s̃ coefficient at ({lambda}, {mu}) does not fit i128")
});
out.push((lambda.clone(), c));
}
}
}
out
})
}
fn triangular_key(p: &Partition) -> (u32, std::cmp::Reverse<Vec<u32>>) {
(p.size(), std::cmp::Reverse(p.parts().to_vec()))
}
fn st_to_ht_row(lambda: &Partition) -> Arc<Vec<(Partition, i128)>> {
st_to_ht_cached(lambda, || {
let mut rem: BTreeMap<Partition, i128> = BTreeMap::new();
rem.insert(lambda.clone(), 1);
let mut out: Vec<(Partition, i128)> = Vec::new();
while let Some((pivot, c)) = rem
.iter()
.max_by_key(|(p, _)| triangular_key(p))
.map(|(p, &c)| (p.clone(), c))
{
rem.remove(&pivot);
if c == 0 {
continue;
}
out.push((pivot.clone(), c));
for (nu, k) in ht_to_st_row(&pivot).iter() {
if *nu == pivot {
continue; }
*rem.entry(nu.clone()).or_insert(0) -= c * k;
}
rem.retain(|_, v| *v != 0);
}
out
})
}
impl<C: Ring> ToSchur<C> for Ht<C> {
fn to_schur(&self) -> Schur<C> {
let mut st: St<C> = St::zero();
for (mu, c) in self.terms() {
for (lambda, k) in ht_to_st_row(mu).iter() {
st.add_term(lambda.clone(), C::from_i128(*k).mul(c));
}
}
st.to_schur()
}
}
impl<C: Ring> FromSchur<C> for Ht<C> {
fn from_schur(s: &Schur<C>) -> Self {
let st: St<C> = St::from_schur(s);
let mut out = Ht::zero();
for (lambda, c) in st.terms() {
for (mu, k) in st_to_ht_row(lambda).iter() {
out.add_term(mu.clone(), C::from_i128(*k).mul(c));
}
}
out
}
}
const HT_PRODUCT_BUDGET: u64 = 4_000_000;
pub fn ht_product_terms(lambda: &Partition, mu: &Partition) -> Option<Vec<(Partition, u128)>> {
let rows = lambda.parts();
let cols = mu.parts();
let mut acc: BTreeMap<Partition, u128> = BTreeMap::new();
let mut cap: Vec<u32> = cols.to_vec();
let mut entries: Vec<u32> = Vec::new();
let mut scratch: Vec<u32> = Vec::new();
let mut budget = HT_PRODUCT_BUDGET;
#[allow(clippy::too_many_arguments)]
fn row(
i: usize,
j: usize,
left: u32,
rows: &[u32],
cap: &mut Vec<u32>,
entries: &mut Vec<u32>,
scratch: &mut Vec<u32>,
acc: &mut BTreeMap<Partition, u128>,
budget: &mut u64,
) -> bool {
if *budget == 0 {
return false;
}
if j == cap.len() {
entries.push(left); let ok = block(i + 1, rows, cap, entries, scratch, acc, budget);
entries.pop();
return ok;
}
for v in 0..=left.min(cap[j]) {
cap[j] -= v;
entries.push(v);
let ok = row(i, j + 1, left - v, rows, cap, entries, scratch, acc, budget);
entries.pop();
cap[j] += v;
if !ok {
return false;
}
}
true
}
fn block(
i: usize,
rows: &[u32],
cap: &mut Vec<u32>,
entries: &mut Vec<u32>,
scratch: &mut Vec<u32>,
acc: &mut BTreeMap<Partition, u128>,
budget: &mut u64,
) -> bool {
if i == rows.len() {
if *budget == 0 {
return false;
}
*budget -= 1;
scratch.clear();
scratch.extend_from_slice(entries);
scratch.extend_from_slice(cap);
scratch.retain(|&x| x != 0);
scratch.sort_unstable_by(|a, b| b.cmp(a));
*acc.entry(Partition::from_sorted(scratch.clone()))
.or_insert(0) += 1;
return true;
}
row(i, 0, rows[i], rows, cap, entries, scratch, acc, budget)
}
if !block(
0,
rows,
&mut cap,
&mut entries,
&mut scratch,
&mut acc,
&mut budget,
) {
return None;
}
Some(acc.into_iter().collect())
}
impl<C: Ring> Ht<C> {
pub fn mul(&self, other: &Self) -> Self {
let mut out = Self::zero();
for (lambda, cl) in self.terms() {
for (mu, cm) in other.terms() {
let scale = cl.mul(cm);
let terms = ht_product_terms(lambda, mu)
.expect("ht product enumeration exceeded its budget");
for (nu, k) in terms {
out.add_term(nu, C::from_u128(k).mul(&scale));
}
}
}
out
}
}
impl_product_ops!(Ht);
impl<C: Ring> SymAlgebra<C> for Ht<C> {
fn times(&self, o: &Self) -> Self {
self.mul(o)
}
}
pub fn reduced_kronecker_via_ht<C: Ring>(lambda: &Partition, mu: &Partition) -> Option<St<C>> {
let mut acc: BTreeMap<Partition, i128> = BTreeMap::new();
for (a, ca) in st_to_ht_row(lambda).iter() {
for (b, cb) in st_to_ht_row(mu).iter() {
for (nu, k) in ht_product_terms(a, b)? {
let k = i128::try_from(k).unwrap_or_else(|_| {
panic!("the h̃ product multiplicity at {nu} does not fit i128")
});
*acc.entry(nu).or_insert(0) += ca * cb * k;
}
}
}
let mut out = St::zero();
for (nu, c) in acc {
if c == 0 {
continue;
}
for (lam, k) in ht_to_st_row(&nu).iter() {
out.add_term(lam.clone(), C::from_i128(c * k));
}
}
Some(out)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::sym::{Elementary, Homogeneous};
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn st(v: &[u32]) -> St<i128> {
St::monomial(part(v), 1)
}
#[cfg(feature = "bignum")]
#[test]
fn the_wide_degree_passes_agree_with_the_fixed_ones() {
for n in 0..=6u32 {
let fixed = guarded(|| schur_to_st_degree::<GuardedRat>(n))
.flatten()
.expect("degree 6 is far inside the fixed width");
let wide = schur_to_st_degree::<num_rational::BigRational>(n)
.expect("BigRational cannot leave its width");
assert_eq!(fixed, wide, "s → s̃ at degree {n}");
let fixed = guarded(|| st_to_schur_degree::<GuardedRat>(n, bold_guarded))
.flatten()
.expect("degree 6 is far inside the fixed width");
let wide = st_to_schur_degree::<num_rational::BigRational>(n, bold_p_in)
.expect("BigRational cannot leave its width");
assert_eq!(fixed, wide, "s̃ → s at degree {n}");
}
}
#[test]
fn column_shapes_are_alternating_sums_of_elementaries() {
for r in 1..=6u32 {
let col = st(&vec![1; r as usize]);
let e: Elementary<i128> = Elementary::from_schur(&col.to_schur());
for i in 0..=r {
let want = if i % 2 == 0 { 1 } else { -1 };
assert_eq!(e.coeff(&part(&[r - i])), want, "e_{} in s̃_(1^{r})", r - i);
}
assert_eq!(e.terms().len(), r as usize + 1);
}
}
#[test]
fn first_character_is_the_defect_of_the_trivial_one() {
let s = st(&[1]).to_schur();
assert_eq!(s.coeff(&part(&[1])), 1);
assert_eq!(s.coeff(&Partition::default()), -1);
assert_eq!(s.terms().len(), 2);
}
#[test]
fn published_expansion_of_h_21() {
let h: Homogeneous<i128> = Homogeneous::monomial(part(&[2, 1]), 1);
let got: St<i128> = St::from_schur(&h.to_schur());
for (p, want) in [
(vec![3], 1),
(vec![2, 1], 1),
(vec![2], 4),
(vec![1, 1], 3),
(vec![1], 7),
(vec![], 4),
] {
assert_eq!(got.coeff(&part(&p)), want, "coefficient of s̃_{p:?}");
}
assert_eq!(got.terms().len(), 6);
}
#[test]
fn published_expansion_of_h_1111() {
let h: Homogeneous<i128> = Homogeneous::monomial(part(&[1, 1, 1, 1]), 1);
let got: St<i128> = St::from_schur(&h.to_schur());
for (p, want) in [
(vec![], 15),
(vec![1], 37),
(vec![1, 1], 31),
(vec![1, 1, 1], 10),
(vec![1, 1, 1, 1], 1),
(vec![2], 31),
(vec![2, 1], 20),
(vec![2, 1, 1], 3),
(vec![2, 2], 2),
(vec![3], 10),
(vec![3, 1], 3),
(vec![4], 1),
] {
assert_eq!(got.coeff(&part(&p)), want, "coefficient of s̃_{p:?}");
}
assert_eq!(got.terms().len(), 12);
}
#[test]
fn st_and_schur_round_trip() {
for n in 0..=8u32 {
for lambda in crate::partition::partitions_of(n) {
let x = St::<i128>::monomial(lambda.clone(), 1);
let back: St<i128> = St::from_schur(&x.to_schur());
assert_eq!(back, x, "round trip at {lambda}");
}
}
}
#[test]
fn ht_and_schur_round_trip() {
for n in 0..=6u32 {
for lambda in crate::partition::partitions_of(n) {
let x = Ht::<i128>::monomial(lambda.clone(), 1);
let back: Ht<i128> = Ht::from_schur(&x.to_schur());
assert_eq!(back, x, "round trip at {lambda}");
}
}
}
#[test]
fn top_degree_is_littlewood_richardson() {
for lambda in crate::partition::partitions_of(4) {
for mu in crate::partition::partitions_of(3) {
let red: St<i128> = reduced_kronecker_product(&lambda, &mu);
let sl: Schur<i128> = Schur::monomial(lambda.clone(), 1);
let sm: Schur<i128> = Schur::monomial(mu.clone(), 1);
let lr = sl.mul(&sm);
for (nu, c) in lr.terms() {
assert_eq!(
red.coeff(nu),
*c,
"top degree of s̃_{lambda} · s̃_{mu} at {nu}"
);
}
}
}
}
#[test]
fn two_product_routes_agree() {
for lambda in crate::partition::partitions_of(3) {
for mu in crate::partition::partitions_of(3) {
let a: St<i128> = reduced_kronecker_product(&lambda, &mu);
let b: St<i128> =
reduced_kronecker_via_ht(&lambda, &mu).expect("small enough to enumerate");
assert_eq!(a, b, "routes disagree on s̃_{lambda} · s̃_{mu}");
}
}
}
#[test]
fn product_has_a_unit_and_commutes() {
let a = st(&[2, 1]);
let b = st(&[2]).add(&st(&[1, 1]));
assert_eq!(a.mul(&St::unit()), a);
assert_eq!(a.mul(&b), b.mul(&a));
}
#[test]
fn product_is_associative() {
let a = st(&[2]);
let b = st(&[1, 1]);
let c = st(&[2, 1]);
assert_eq!(a.mul(&b).mul(&c), a.mul(&b.mul(&c)));
}
#[test]
fn product_agrees_with_the_schur_route() {
for lambda in crate::partition::partitions_of(3) {
for mu in crate::partition::partitions_of(2) {
let fast: St<i128> = reduced_kronecker_product(&lambda, &mu);
let a: St<i128> = St::monomial(lambda.clone(), 1);
let b: St<i128> = St::monomial(mu.clone(), 1);
let slow: St<i128> = St::from_schur(&a.to_schur().mul(&b.to_schur()));
assert_eq!(fast, slow, "s̃_{lambda} · s̃_{mu}");
}
}
}
#[test]
fn agrees_with_the_ordinary_kronecker_once_stable() {
use crate::coeff::Rational;
let lambda = part(&[2]);
let mu = part(&[1, 1]);
let red: St<i128> = reduced_kronecker_product(&lambda, &mu);
let n = 9u32; let big = |p: &Partition| {
let mut v = vec![n - p.size()];
v.extend_from_slice(p.parts());
Partition::new(v)
};
for nu in crate::partition::partitions_of(3) {
let g: Rational = crate::ops::kronecker(&big(&lambda), &big(&mu), &big(&nu));
assert_eq!(Rational::from_int(red.coeff(&nu)), g, "ḡ vs g at ν = {nu}");
}
}
}