use std::collections::HashMap;
use crate::coeff::Ring;
use crate::convert::Beta;
use crate::memo::{character_cached, MaskKey};
use crate::partition::Partition;
pub fn character(lambda: &Partition, mu: &Partition) -> i128 {
try_character(lambda, mu).unwrap_or_else(|| {
panic!(
"character χ^{lambda}({mu}) overflows i128 (|λ| = {}); \
use try_character to handle this",
lambda.size()
)
})
}
pub fn try_character(lambda: &Partition, mu: &Partition) -> Option<i128> {
if lambda.is_empty() && mu.is_empty() {
return Some(1);
}
if mu.is_empty() || lambda.size() != mu.size() {
return Some(0);
}
if fits_mask::<u64>(lambda) && fits_mask::<u64>(mu) {
return character_masked::<u64>(lambda, mu);
}
if fits_mask::<u128>(lambda) && fits_mask::<u128>(mu) {
return character_masked::<u128>(lambda, mu);
}
character_cached(lambda, mu, || character_uncached(lambda, mu))
}
fn fits_mask<M: Beta>(lambda: &Partition) -> bool {
lambda.is_empty() || (lambda.part(0) as usize + lambda.len() - 1) < M::BITS as usize
}
#[allow(clippy::cast_possible_truncation)]
fn beta_mask<M: Beta>(lambda: &Partition) -> M {
let l = lambda.len();
let mut mask = M::low_ones(0);
for i in 0..l {
mask = mask.with_bit((lambda.part(i) as usize + l - 1 - i) as u32);
}
mask
}
fn character_masked<M: MaskKey>(lambda: &Partition, mu: &Partition) -> Option<i128> {
let mut ctx = MaskedRecursion::<M> {
mu: mu.parts(),
local: Default::default(),
shared: crate::memo::character_masks_read::<M>(),
};
let result = ctx.chi(beta_mask::<M>(lambda), beta_mask::<M>(mu), 0);
let MaskedRecursion { local, shared, .. } = ctx;
drop(shared);
crate::memo::character_masks_store::<M>(local);
result
}
pub(crate) fn character_row(lambda: &Partition) -> Vec<Option<i128>> {
let n = lambda.size() as usize;
let mus = crate::memo::partitions_cached(lambda.size());
if n < u64::BITS as usize {
return character_row_masked::<u64>(lambda, &mus);
}
if n < u128::BITS as usize {
return character_row_masked::<u128>(lambda, &mus);
}
mus.iter().map(|mu| try_character(lambda, mu)).collect()
}
fn character_row_masked<M: MaskKey>(lambda: &Partition, mus: &[Partition]) -> Vec<Option<i128>> {
let shared = crate::memo::character_masks_read::<M>();
let cold = mus.len() * (lambda.size() as usize / 4 + 1);
let mut ctx = MaskedRecursion::<M> {
mu: &[],
local: crate::fasthash::Map::with_capacity_and_hasher(
cold.saturating_sub(shared.len()),
Default::default(),
),
shared,
};
let lam = beta_mask::<M>(lambda);
let row = mus
.iter()
.map(|mu| {
ctx.mu = mu.parts();
ctx.chi(lam, beta_mask::<M>(mu), 0)
})
.collect();
let MaskedRecursion { local, shared, .. } = ctx;
drop(shared);
crate::memo::character_masks_store::<M>(local);
row
}
struct MaskedRecursion<'a, M: MaskKey> {
mu: &'a [u32],
local: crate::fasthash::Map<(M, M), i128>,
shared: std::sync::RwLockReadGuard<'static, crate::fasthash::Map<(M, M), i128>>,
}
impl<M: MaskKey> MaskedRecursion<'_, M> {
#[allow(clippy::cast_possible_truncation)]
fn chi(&mut self, mask: M, mu_mask: M, k: usize) -> Option<i128> {
if k == self.mu.len() {
return Some(1);
}
let key = (mask.canonical(), mu_mask);
if let Some(&v) = self.local.get(&key) {
return Some(v);
}
if let Some(&v) = self.shared.get(&key) {
return Some(v);
}
crate::interrupt::poll();
let r = self.mu[k];
let rest_mu = mu_mask.without_bit(mu_mask.highest() as u32);
let mut total: i128 = 0;
let mut rest = mask;
while !rest.is_zero() {
let b = rest.trailing_zeros();
rest = rest.clear_lowest();
if b < r {
continue;
}
let bp = b - r;
if mask.test(bp) {
continue;
}
let height = mask.between(bp + 1, b).count_ones();
let next = mask.without_bit(b).with_bit(bp);
let sub = self.chi(next, rest_mu, k + 1)?;
let term = if height.is_multiple_of(2) { sub } else { -sub };
total = total.checked_add(term)?;
}
self.local.insert(key, total);
Some(total)
}
}
pub fn character_in<C: Ring>(lambda: &Partition, mu: &Partition) -> C {
if let Some(v) = try_character(lambda, mu) {
return C::from_i128(v);
}
let mut memo = HashMap::new();
character_generic(lambda, mu, &mut memo)
}
pub(crate) fn character_generic<C: Ring>(
lambda: &Partition,
mu: &Partition,
memo: &mut HashMap<(Partition, Partition), C>,
) -> C {
if lambda.is_empty() && mu.is_empty() {
return C::one();
}
if mu.is_empty() || lambda.size() != mu.size() {
return C::zero();
}
let key = (lambda.clone(), mu.clone());
if let Some(v) = memo.get(&key) {
return v.clone();
}
let r = mu.part(0);
let rest = Partition::from_sorted(mu.parts()[1..].to_vec());
let mut total = C::zero();
for (next, height) in border_strips(lambda, r) {
crate::interrupt::poll();
let sub = character_generic(&next, &rest, memo);
if height % 2 == 0 {
total.add_assign(&sub);
} else {
total.sub_assign(&sub);
}
}
memo.insert(key, total.clone());
total
}
fn character_uncached(lambda: &Partition, mu: &Partition) -> Option<i128> {
let r = mu.part(0);
let rest = Partition::from_sorted(mu.parts()[1..].to_vec());
let mut total: i128 = 0;
for (next, height) in border_strips(lambda, r) {
crate::interrupt::poll();
let sub = try_character(&next, &rest)?;
let term = if height % 2 == 0 { sub } else { -sub };
total = total.checked_add(term)?;
}
Some(total)
}
pub fn character_table(n: u32) -> Vec<Vec<i128>> {
character_table_in(n)
}
pub fn character_table_in<C: Ring>(n: u32) -> Vec<Vec<C>> {
let parts = crate::memo::partitions_cached(n);
let mut table = vec![vec![C::zero(); parts.len()]; parts.len()];
let l = n as usize;
if l == 0 {
table[0][0] = C::one();
return table;
}
if l > crate::convert::MASK_LIMIT {
for (i, lambda) in parts.iter().enumerate() {
for (j, mu) in parts.iter().enumerate() {
crate::interrupt::poll();
table[i][j] = character_in::<C>(lambda, mu);
}
}
return table;
}
let index: crate::fasthash::Map<u64, usize> = parts
.iter()
.enumerate()
.map(|(i, p)| {
let mut mask = 0u64;
for k in 0..l {
mask |= 1u64 << (p.part(k) as usize + l - 1 - k);
}
(mask, i)
})
.collect();
let mut order: Vec<usize> = (0..parts.len()).collect();
order.sort_by(|&a, &b| parts[a].parts().cmp(parts[b].parts()));
let items: Vec<(&Partition, usize)> = order.iter().map(|&i| (&parts[i], i)).collect();
let mut root: crate::fasthash::Map<u64, C> = Default::default();
root.insert((1u64 << l) - 1, C::one());
crate::convert::p_expand_shared(&items, 0, &root, &mut |&col: &usize, mask, chi: &C| {
if let Some(&row) = index.get(&mask) {
table[row][col] = chi.clone();
}
});
table
}
pub(crate) fn border_strips(lambda: &Partition, r: u32) -> Vec<(Partition, u32)> {
let l = lambda.len();
if l == 0 {
return Vec::new();
}
if lambda.part(0) as usize + l - 1 < 64 {
return border_strips_masked(lambda, l, r);
}
border_strips_general(lambda, r)
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn border_strips_general(lambda: &Partition, r: u32) -> Vec<(Partition, u32)> {
let l = lambda.len();
if l == 0 {
return Vec::new();
}
let beta: Vec<i64> = (0..l)
.map(|i| lambda.part(i) as i64 + (l as i64 - 1 - i as i64))
.collect();
let present: std::collections::HashSet<i64> = beta.iter().copied().collect();
let mut out = Vec::new();
for &b in &beta {
let bp = b - r as i64;
if bp < 0 || present.contains(&bp) {
continue;
}
let height = beta.iter().filter(|&&x| x > bp && x < b).count() as u32;
let mut nb: Vec<i64> = beta.iter().map(|&x| if x == b { bp } else { x }).collect();
nb.sort_unstable_by(|a, c| c.cmp(a));
let mut parts = Vec::new();
for (k, &x) in nb.iter().enumerate() {
let val = x - (l as i64 - 1 - k as i64);
if val > 0 {
parts.push(val as u32);
}
}
out.push((Partition::from_sorted(parts), height));
}
out
}
fn border_strips_masked(lambda: &Partition, l: usize, r: u32) -> Vec<(Partition, u32)> {
let mut mask = 0u64;
for i in 0..l {
mask |= 1u64 << (lambda.part(i) as usize + l - 1 - i);
}
let mut out = Vec::new();
let mut rest = mask;
while rest != 0 {
let b = rest.trailing_zeros();
rest &= rest - 1;
if b < r {
continue; }
let bp = b - r;
if mask >> bp & 1 == 1 {
continue; }
let between = mask & (((1u64 << b) - 1) ^ ((1u64 << (bp + 1)) - 1));
let nm = (mask & !(1u64 << b)) | (1u64 << bp);
out.push((mask_to_partition(nm, l), between.count_ones()));
}
out
}
#[allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
fn mask_to_partition(mask: u64, l: usize) -> Partition {
let mut parts = Vec::new();
let mut rest = mask;
let mut i = 0usize;
while rest != 0 {
let b = 63 - rest.leading_zeros() as usize;
rest &= !(1u64 << b);
let val = b - (l - 1 - i);
if val > 0 {
parts.push(val as u32);
}
i += 1;
}
Partition::from_sorted(parts)
}
#[cfg(test)]
mod tests {
use super::*;
fn p(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn generic_character_table_agrees_and_accepts_a_polynomial_ring() {
use crate::qt::QtPoly;
for n in 0..=9u32 {
let plain = character_table(n);
let poly: Vec<Vec<QtPoly<i64>>> = character_table_in(n);
for i in 0..plain.len() {
for j in 0..plain.len() {
assert_eq!(
poly[i][j].coeff(0, 0),
plain[i][j] as i64,
"({i},{j}) deg {n}"
);
assert!(poly[i][j].len() <= 1, "a character is a constant");
}
}
}
}
#[test]
fn masked_recursion_matches_the_partition_keyed_one() {
let general = |lam: &Partition, mu: &Partition| -> Option<i128> {
if lam.is_empty() && mu.is_empty() {
return Some(1);
}
if mu.is_empty() || lam.size() != mu.size() {
return Some(0);
}
character_cached(lam, mu, || character_uncached(lam, mu))
};
let check = |lambda: &Partition, mu: &Partition| {
let want = general(lambda, mu);
assert_eq!(
character_masked::<u64>(lambda, mu),
want,
"χ^{lambda}({mu}), u64"
);
assert_eq!(
character_masked::<u128>(lambda, mu),
want,
"χ^{lambda}({mu}), u128"
);
};
for n in 0..=11u32 {
for lambda in crate::memo::partitions_cached(n).iter() {
for mu in crate::memo::partitions_cached(n).iter() {
check(lambda, mu);
}
}
}
let big = [
(p(&[9, 8, 7, 6]), p(&[5, 5, 4, 4, 3, 3, 2, 2, 1, 1])),
(p(&[12, 8, 4, 2]), p(&[7, 6, 5, 4, 3, 1])),
(p(&[6, 6, 6, 6, 6]), p(&[6, 5, 4, 3, 3, 3, 2, 2, 1, 1])),
(
p(&[16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]),
p(&[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]),
),
];
for (lambda, mu) in &big {
check(lambda, mu);
}
let lambda = p(&std::iter::once(33)
.chain(std::iter::repeat_n(1, 32))
.collect::<Vec<_>>());
let mu = p(&[8, 8, 8, 8, 8, 8, 8, 8, 1]);
assert!(!fits_mask::<u64>(&lambda), "the hook must not fit a u64");
assert_eq!(
character_masked::<u128>(&lambda, &mu),
general(&lambda, &mu),
"χ^{lambda}({mu}), u128"
);
}
#[test]
fn character_row_matches_the_independent_recursion() {
let mut memo = HashMap::new();
for n in 0..=11u32 {
let mus = crate::memo::partitions_cached(n);
for lambda in mus.iter() {
let row = character_row(lambda);
let wide = character_row_masked::<u128>(lambda, &mus);
assert_eq!(row.len(), mus.len(), "row of {lambda} is p({n}) long");
for ((mu, got), w) in mus.iter().zip(&row).zip(&wide) {
let want: i128 = character_generic(lambda, mu, &mut memo);
assert_eq!(*got, Some(want), "χ^{lambda}({mu})");
assert_eq!(*w, Some(want), "χ^{lambda}({mu}), u128");
}
}
}
}
#[test]
fn swept_character_table_matches_per_entry() {
for n in 0..=11u32 {
let parts = crate::memo::partitions_cached(n);
let table = character_table(n);
assert_eq!(table.len(), parts.len(), "table is p({n}) square");
for (i, lambda) in parts.iter().enumerate() {
for (j, mu) in parts.iter().enumerate() {
assert_eq!(
table[i][j],
character(lambda, mu),
"χ^{lambda}({mu}) at degree {n}"
);
}
}
}
}
#[test]
fn masked_border_strips_match_the_general_form() {
for n in 0..=11u32 {
for lambda in crate::memo::partitions_cached(n).iter() {
for r in 1..=n {
let mut got = border_strips_masked(lambda, lambda.len(), r);
let mut want = border_strips_general(lambda, r);
got.sort();
want.sort();
assert_eq!(got, want, "strips of size {r} from {lambda}");
}
}
}
}
#[test]
fn s4_character_table_rows() {
let lam = p(&[2, 2]);
assert_eq!(character(&lam, &p(&[1, 1, 1, 1])), 2); assert_eq!(character(&lam, &p(&[2, 1, 1])), 0);
assert_eq!(character(&lam, &p(&[2, 2])), 2);
assert_eq!(character(&lam, &p(&[3, 1])), -1);
assert_eq!(character(&lam, &p(&[4])), 0);
}
fn dimension_by_hooks(lam: &[u32]) -> i128 {
fn gcd(mut a: i128, mut b: i128) -> i128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
}
if lam.is_empty() {
return 1;
}
let m: usize = lam.iter().map(|&x| x as usize).sum();
let mut conj = vec![0i64; lam[0] as usize];
for &part in lam {
for c in conj.iter_mut().take(part as usize) {
*c += 1;
}
}
let mut num: Vec<i128> = (2..=m as i128).collect();
for (i, &row) in lam.iter().enumerate() {
for j in 0..row as usize {
let mut h = (row as i64 - j as i64) + (conj[j] - i as i64) - 1;
for ni in num.iter_mut() {
if h == 1 {
break;
}
let g = gcd(*ni, h as i128);
if g > 1 {
*ni /= g;
h /= g as i64;
}
}
assert_eq!(h, 1, "hook did not cancel — d_λ is not an integer");
}
}
num.into_iter().product()
}
#[test]
fn identity_class_matches_hook_formula_past_the_i64_ceiling() {
for n in [20u32, 30, 34, 36, 40, 48] {
let (mut parts, mut left, mut k) = (Vec::new(), n, 1);
while left > 0 {
let part = k.min(left);
parts.push(part);
left -= part;
k += 1;
}
parts.sort_unstable_by(|a, b| b.cmp(a));
let lam = Partition::new(parts.iter().copied());
let ones = Partition::new(std::iter::repeat_n(1, n as usize));
let want = dimension_by_hooks(&parts);
assert_eq!(character(&lam, &ones), want, "χ^{lam}(1^{n})");
assert!(want > 0, "a dimension must be positive");
if n >= 36 {
assert!(want > i64::MAX as i128, "n={n} should exceed i64 range");
}
}
}
#[test]
fn overflow_is_reported_not_wrapped() {
let n = 70u32;
let lam = Partition::new(std::iter::once(n)); let ones = Partition::new(std::iter::repeat_n(1, n as usize));
assert_eq!(
try_character(&lam, &ones),
Some(1),
"χ^(n)(1ⁿ) = 1, no overflow"
);
let big = Partition::new([n / 2, n / 2 - 1, n / 2 - 2, n / 2 - 3].iter().copied());
let m = big.size();
let ones_m = Partition::new(std::iter::repeat_n(1, m as usize));
match try_character(&big, &ones_m) {
None => {} Some(v) => assert!(v > 0, "if it fits, it must still be positive"),
}
}
#[test]
fn sign_and_trivial_characters() {
for mu in [p(&[3]), p(&[2, 1]), p(&[1, 1, 1])] {
assert_eq!(character(&p(&[3]), &mu), 1, "trivial at {mu}");
}
assert_eq!(character(&p(&[1, 1, 1]), &p(&[1, 1, 1])), 1); assert_eq!(character(&p(&[1, 1, 1]), &p(&[2, 1])), -1); assert_eq!(character(&p(&[1, 1, 1]), &p(&[3])), 1); }
}