#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::character::character_in;
use crate::coeff::{QAlgebra, Ring};
use crate::convert::{FromSchur, ToSchur};
#[cfg(feature = "bignum")]
use crate::guard::{guarded, GuardedRat};
use crate::partition::Partition;
use crate::sym::{PowerSum, Schur, SymFn};
impl<C: Ring> Schur<C> {
pub fn omega(&self) -> Self {
let mut out = Schur::zero();
for (lambda, c) in self.terms() {
out.add_term(lambda.conjugate(), c.clone());
}
out
}
}
impl<C: Ring> PowerSum<C> {
pub fn omega(&self) -> Self {
let mut out = PowerSum::zero();
for (lambda, c) in self.terms() {
let odd = (lambda.size() - lambda.len() as u32) % 2 == 1;
out.add_term(lambda.clone(), if odd { c.neg() } else { c.clone() });
}
out
}
}
pub fn omega<C, B>(x: &B) -> B
where
C: Ring,
B: ToSchur<C> + FromSchur<C>,
{
B::from_schur(&x.to_schur().omega())
}
pub fn hall<C, A, B>(a: &A, b: &B) -> C
where
C: Ring,
A: ToSchur<C>,
B: ToSchur<C>,
{
let sa = a.to_schur();
let sb = b.to_schur();
let mut acc = C::zero();
for (lambda, ca) in sa.terms() {
crate::interrupt::poll();
if let Some(cb) = sb.terms().get(lambda) {
acc.add_assign(&ca.mul(cb));
}
}
acc
}
pub fn internal<C: QAlgebra>(a: &Schur<C>, b: &Schur<C>) -> Schur<C> {
let pa: PowerSum<C> = PowerSum::from_schur(a);
let pb: PowerSum<C> = PowerSum::from_schur(b);
let (small, large) = if pa.terms().len() <= pb.terms().len() {
(&pa, &pb)
} else {
(&pb, &pa)
};
let mut acc = PowerSum::zero();
for (lambda, cs) in small.terms() {
crate::interrupt::poll();
let cl = match large.terms().get(lambda) {
Some(c) => c,
None => continue,
};
acc.add_term(lambda.clone(), cs.mul(cl).mul(&lambda.z_in::<C>()));
}
acc.to_schur()
}
pub fn kronecker<C: QAlgebra>(
lambda: &crate::partition::Partition,
mu: &crate::partition::Partition,
nu: &crate::partition::Partition,
) -> C {
let sl: Schur<C> = Schur::monomial(lambda.clone(), C::one());
let sm: Schur<C> = Schur::monomial(mu.clone(), C::one());
internal(&sl, &sm).coeff(nu)
}
pub fn kronecker_via_characters<C: QAlgebra>(
lambda: &Partition,
mu: &Partition,
nu: &Partition,
) -> C {
let n = lambda.size();
if mu.size() != n || nu.size() != n {
return C::zero();
}
if n == 0 {
return C::one();
}
let mut acc = C::zero();
for rho in crate::memo::partitions_cached(n).iter() {
crate::interrupt::poll();
let a: C = character_in(lambda, rho);
if a.is_zero() {
continue;
}
let b: C = character_in(mu, rho);
if b.is_zero() {
continue;
}
let c: C = character_in(nu, rho);
if c.is_zero() {
continue;
}
acc.add_assign(&rho.div_by_z(&a.mul(&b).mul(&c)));
}
acc
}
#[cfg(feature = "bignum")]
pub fn kronecker_coeff(lambda: &Partition, mu: &Partition, nu: &Partition) -> i128 {
try_kronecker_coeff(lambda, mu, nu)
.unwrap_or_else(|| panic!("g^{nu}_{{{lambda},{mu}}} does not fit i128"))
}
#[cfg(feature = "bignum")]
pub fn try_kronecker_coeff(lambda: &Partition, mu: &Partition, nu: &Partition) -> Option<i128> {
use num_traits::ToPrimitive;
let fast = || {
let v: GuardedRat = kronecker_via_characters(lambda, mu, nu);
(v.denom() == 1).then(|| v.numer())
};
if let Some(Some(v)) = guarded(fast) {
return Some(v);
}
let v: num_rational::BigRational = kronecker_via_characters(lambda, mu, nu);
assert!(
v.is_integer(),
"g^{nu}_{{{lambda},{mu}}} is not an integer over BigRational, \
which is a bug rather than an overflow"
);
v.to_integer().to_i128()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::memo::partitions_cached;
use crate::partition::Partition;
use crate::sym::{Homogeneous, Monomial};
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn q(n: i128) -> Rational {
Rational::new(n, 1)
}
fn sch(v: &[u32]) -> Schur<Rational> {
Schur::monomial(part(v), q(1))
}
#[test]
fn kronecker_matches_s3_representation_theory() {
assert_eq!(internal(&sch(&[3]), &sch(&[2, 1])), sch(&[2, 1]));
assert_eq!(internal(&sch(&[1, 1, 1]), &sch(&[1, 1, 1])), sch(&[3]));
assert_eq!(internal(&sch(&[1, 1, 1]), &sch(&[2, 1])), sch(&[2, 1]));
let r = internal(&sch(&[2, 1]), &sch(&[2, 1]));
assert_eq!(r.coeff(&part(&[3])), q(1));
assert_eq!(r.coeff(&part(&[2, 1])), q(1));
assert_eq!(r.coeff(&part(&[1, 1, 1])), q(1));
assert_eq!(r.terms().len(), 3);
}
#[test]
fn kronecker_matches_the_character_formula() {
for n in 0..=6u32 {
let parts = partitions_cached(n);
for lambda in parts.iter() {
for mu in parts.iter() {
let got = internal(
&Schur::monomial(lambda.clone(), q(1)),
&Schur::monomial(mu.clone(), q(1)),
);
for nu in parts.iter() {
let mut want = Rational::new(0, 1);
for rho in parts.iter() {
let t = crate::character::character(lambda, rho)
* crate::character::character(mu, rho)
* crate::character::character(nu, rho);
want.add_assign(&Rational::new(t, rho.z() as i128));
}
assert_eq!(got.coeff(nu), want, "g^{nu}_{{{lambda},{mu}}}");
}
}
}
}
}
#[test]
fn kronecker_via_characters_agrees_with_the_product() {
for n in 0..=7u32 {
let parts = partitions_cached(n);
for lambda in parts.iter() {
for mu in parts.iter() {
let prod = internal(
&Schur::monomial(lambda.clone(), q(1)),
&Schur::monomial(mu.clone(), q(1)),
);
for nu in parts.iter() {
let got: Rational = kronecker_via_characters(lambda, mu, nu);
assert_eq!(got, prod.coeff(nu), "g^{nu}_{{{lambda},{mu}}}");
}
}
}
}
}
#[test]
fn kronecker_via_characters_respects_the_grading() {
let z: Rational = kronecker_via_characters(&part(&[2]), &part(&[2, 1]), &part(&[2, 1]));
assert_eq!(z, q(0));
let z: Rational = kronecker_via_characters(&part(&[2, 1]), &part(&[2, 1]), &part(&[3, 1]));
assert_eq!(z, q(0));
let e: Rational = kronecker_via_characters(&part(&[]), &part(&[]), &part(&[]));
assert_eq!(e, q(1));
}
#[test]
fn factorial_ceiling_for_z_is_at_thirty_five() {
assert_eq!(
part(&[1; 34]).z(),
295_232_799_039_604_140_847_618_609_643_520_000_000
);
}
#[test]
#[cfg(feature = "bignum")]
fn kronecker_coeff_holds_identities_past_every_fixed_width_ceiling() {
let lambda = part(&[38, 2]);
let trivial = part(&[40]);
let other = part(&[37, 3]);
assert_eq!(kronecker_coeff(&lambda, &trivial, &lambda), 1);
assert_eq!(kronecker_coeff(&lambda, &trivial, &other), 0);
let (a, b, c) = (part(&[36, 3, 1]), part(&[35, 5]), part(&[37, 2, 1]));
let g = kronecker_coeff(&a, &b, &c);
assert_eq!(g, kronecker_coeff(&b, &a, &c));
assert_eq!(g, kronecker_coeff(&c, &b, &a));
assert_eq!(g, kronecker_coeff(&a, &c, &b));
}
#[test]
#[cfg(feature = "bignum")]
#[should_panic(expected = "overflow")]
fn unguarded_fixed_width_refuses_where_the_guarded_path_escalates() {
let lambda = part(&[38, 2]);
let trivial = part(&[40]);
let _: Rational = kronecker_via_characters(&lambda, &trivial, &lambda);
}
#[test]
#[cfg(feature = "bignum")]
fn guarded_path_escalates_where_fixed_width_refuses() {
let lambda = part(&[38, 2]);
let trivial = part(&[40]);
assert_eq!(kronecker_coeff(&lambda, &trivial, &lambda), 1);
}
#[test]
fn kronecker_symmetries_and_dimension_count() {
for n in 0..=6u32 {
let parts = partitions_cached(n);
let ones = Partition::new(std::iter::repeat_n(1, n as usize));
for lambda in parts.iter() {
for mu in parts.iter() {
let g = internal(
&Schur::monomial(lambda.clone(), q(1)),
&Schur::monomial(mu.clone(), q(1)),
);
let swapped = internal(
&Schur::monomial(mu.clone(), q(1)),
&Schur::monomial(lambda.clone(), q(1)),
);
assert_eq!(g, swapped, "g symmetric in λ, μ");
let conj = internal(
&Schur::monomial(lambda.conjugate(), q(1)),
&Schur::monomial(mu.clone(), q(1)),
);
for nu in parts.iter() {
assert_eq!(
g.coeff(nu),
conj.coeff(&nu.conjugate()),
"g^{{ν\'}}_{{λ\',μ}} = g^ν_{{λ,μ}}"
);
}
let dim = |p: &Partition| crate::character::character(p, &ones);
let total: i128 = parts
.iter()
.map(|nu| {
let c = g.coeff(nu);
assert_eq!(c.denom(), 1, "Kronecker coefficients are integers");
c.numer() * dim(nu)
})
.sum();
assert_eq!(total, dim(lambda) * dim(mu), "dim of the tensor product");
}
}
}
}
#[test]
fn internal_product_across_degrees_is_zero() {
let r = internal(&sch(&[2]), &sch(&[2, 1]));
assert!(r.is_zero(), "different degrees must annihilate");
}
#[test]
fn omega_on_schur_conjugates() {
let s3: Schur<i64> = Schur::monomial(part(&[3]), 1);
assert_eq!(s3.omega().coeff(&part(&[1, 1, 1])), 1);
assert_eq!(s3.omega().omega(), s3);
let s21: Schur<i64> = Schur::monomial(part(&[2, 1]), 1);
assert_eq!(s21.omega(), s21);
}
#[test]
fn omega_on_power_sums_signs() {
let p2: PowerSum<i64> = PowerSum::monomial(part(&[2]), 1);
assert_eq!(p2.omega().coeff(&part(&[2])), -1);
let p11: PowerSum<i64> = PowerSum::monomial(part(&[1, 1]), 1);
assert_eq!(p11.omega().coeff(&part(&[1, 1])), 1);
}
#[test]
fn omega_via_schur_maps_h_to_e_expression() {
let h2: Homogeneous<i64> = Homogeneous::monomial(part(&[2]), 1);
let w = omega(&h2);
assert_eq!(w.coeff(&part(&[1, 1])), 1);
assert_eq!(w.coeff(&part(&[2])), -1);
}
#[test]
fn hall_products_match_known_pairings() {
let s21: Schur<i64> = Schur::monomial(part(&[2, 1]), 1);
let s3: Schur<i64> = Schur::monomial(part(&[3]), 1);
assert_eq!(hall(&s21, &s21), 1);
assert_eq!(hall(&s21, &s3), 0);
let p2: PowerSum<i64> = PowerSum::monomial(part(&[2]), 1);
assert_eq!(hall(&p2, &p2), part(&[2]).z() as i64);
let h21: Homogeneous<i64> = Homogeneous::monomial(part(&[2, 1]), 1);
let m21: Monomial<i64> = Monomial::monomial(part(&[2, 1]), 1);
let m3: Monomial<i64> = Monomial::monomial(part(&[3]), 1);
assert_eq!(hall(&h21, &m21), 1);
assert_eq!(hall(&h21, &m3), 0);
}
}