#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::{BTreeMap, HashMap};
use crate::afrac::AFrac;
use crate::coeff::Ring;
use crate::jack::{jack_j_powersum, jack_norm_j};
use crate::partition::Partition;
use crate::sym::SymFn;
pub type Key = (Partition, Partition, Partition);
type Tensor = HashMap<Key, AFrac<i128>>;
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct BPoly {
pub num: Vec<i128>,
pub den: u128,
}
impl BPoly {
pub fn is_positive(&self) -> bool {
self.num.iter().all(|&c| c >= 0)
}
pub fn is_integral(&self) -> bool {
self.den == 1
}
pub fn at_zero(&self) -> (i128, u128) {
(self.num.first().copied().unwrap_or(0), self.den)
}
}
#[derive(Clone, Debug)]
pub struct GjTables {
pub n: u32,
pub c: BTreeMap<Key, BPoly>,
pub h: BTreeMap<Key, BPoly>,
pub not_polynomial: Vec<(&'static str, Key)>,
pub c_not_integral: Vec<Key>,
pub negative: Vec<(&'static str, Key, BPoly)>,
pub peak_bits: u32,
pub primes_used: u32,
}
impl GjTables {
pub fn laws_hold(&self) -> bool {
self.not_polynomial.is_empty() && self.c_not_integral.is_empty()
}
}
fn tensor_mul(a: &Tensor, b: &Tensor) -> Tensor {
let mut out: Tensor = HashMap::new();
for ((l1, m1, n1), ca) in a {
for ((l2, m2, n2), cb) in b {
let key = (union(l1, l2), union(m1, m2), union(n1, n2));
let v = ca.mul(cb);
if v.is_zero() {
continue;
}
match out.entry(key) {
std::collections::hash_map::Entry::Occupied(mut e) => e.get_mut().add_assign(&v),
std::collections::hash_map::Entry::Vacant(e) => {
e.insert(v);
}
}
}
}
out.retain(|_, v| !v.is_zero());
out
}
fn union(a: &Partition, b: &Partition) -> Partition {
let mut parts = a.parts().to_vec();
parts.extend_from_slice(b.parts());
Partition::new(parts)
}
fn phi_slice(n: u32) -> Tensor {
let mut out: Tensor = HashMap::new();
if n == 0 {
out.insert(
(
Partition::default(),
Partition::default(),
Partition::default(),
),
<AFrac<i128> as Ring>::one(),
);
return out;
}
for theta in crate::partitions_of(n) {
crate::interrupt::poll();
let j = jack_j_powersum::<i128>(&theta);
let inverse: BTreeMap<(u32, u32), i32> = jack_norm_j(&theta)
.into_iter()
.map(|(k, m)| (k, -m))
.collect();
let scaled: Vec<(&Partition, AFrac<i128>)> = j
.terms()
.iter()
.map(|(rho, c)| {
let mut v = c.mul_factors(&inverse);
v.reduce();
(rho, v)
})
.collect();
for (la, ca) in &scaled {
for (mu, cb) in j.terms() {
let ab = ca.mul(cb);
if ab.is_zero() {
continue;
}
for (nu, cc) in j.terms() {
let v = ab.mul(cc);
if v.is_zero() {
continue;
}
let key = ((*la).clone(), mu.clone(), nu.clone());
match out.entry(key) {
std::collections::hash_map::Entry::Occupied(mut e) => {
e.get_mut().add_assign(&v)
}
std::collections::hash_map::Entry::Vacant(e) => {
e.insert(v);
}
}
}
}
}
}
for v in out.values_mut() {
v.reduce();
}
out.retain(|_, v| !v.is_zero());
out
}
fn shift_to_b(coeffs: &[i128]) -> Vec<i128> {
let mut out = vec![0i128; coeffs.len()];
for (k, &c) in coeffs.iter().enumerate() {
if c == 0 {
continue;
}
let mut binom: i128 = 1;
for j in 0..=k {
out[j] += c * binom;
binom = binom * (k - j) as i128 / (j + 1) as i128;
}
}
while out.last() == Some(&0) {
out.pop();
}
out
}
fn collapse(v: AFrac<i128>, tag: &'static str, key: &Key, t: &mut GjTables) -> Option<BPoly> {
let Some((coeffs, den)) = v.into_rational_poly() else {
t.not_polynomial.push((tag, key.clone()));
return None;
};
for &c in &coeffs {
t.peak_bits = t.peak_bits.max(128 - c.unsigned_abs().leading_zeros());
}
let poly = BPoly {
num: shift_to_b(&coeffs),
den,
};
if poly.num.is_empty() {
return None;
}
if tag == "c" && !poly.is_integral() {
t.c_not_integral.push(key.clone());
}
if !poly.is_positive() {
t.negative.push((tag, key.clone(), poly.clone()));
}
Some(poly)
}
pub fn gj_connection_tables(n: u32) -> GjTables {
let mut t = GjTables {
n,
c: BTreeMap::new(),
h: BTreeMap::new(),
not_polynomial: Vec::new(),
c_not_integral: Vec::new(),
negative: Vec::new(),
peak_bits: 0,
primes_used: 0,
};
if n == 0 {
return t;
}
let phi: Vec<Tensor> = (0..=n).map(phi_slice).collect();
let mut g: Vec<Tensor> = vec![HashMap::new()];
for k in 1..=n as usize {
crate::interrupt::poll();
let mut acc: Tensor = phi[k]
.iter()
.map(|(key, v)| (key.clone(), v.scale_int(k as i64)))
.collect();
for (j, gj) in g.iter().enumerate().skip(1) {
for (key, v) in tensor_mul(gj, &phi[k - j]) {
match acc.entry(key) {
std::collections::hash_map::Entry::Occupied(mut e) => {
e.get_mut().add_assign(&v.neg())
}
std::collections::hash_map::Entry::Vacant(e) => {
e.insert(v.neg());
}
}
}
}
for v in acc.values_mut() {
v.reduce();
}
acc.retain(|_, v| !v.is_zero());
g.push(acc);
}
let alpha = |power: i32| -> BTreeMap<(u32, u32), i32> {
let mut f = BTreeMap::new();
if power != 0 {
f.insert((1, 0), power);
}
f
};
for (key, v) in &phi[n as usize] {
crate::interrupt::poll();
let scaled = v
.mul_factors(&alpha(key.0.len() as i32))
.mul(&AFrac::from_u128(key.0.z()));
if let Some(poly) = collapse(scaled, "c", key, &mut t) {
t.c.insert(key.clone(), poly);
}
}
for (key, v) in &g[n as usize] {
crate::interrupt::poll();
let scaled = v.mul_factors(&alpha(1));
if let Some(poly) = collapse(scaled, "h", key, &mut t) {
t.h.insert(key.clone(), poly);
}
}
t
}
pub fn class_algebra_coefficient(la: &Partition, mu: &Partition, nu: &Partition) -> i128 {
try_class_algebra_coefficient(la, mu, nu).unwrap_or_else(|| {
panic!("a^{la}_{{{mu},{nu}}} leaves i128 in its intermediates; use try_class_algebra_coefficient")
})
}
pub fn try_class_algebra_coefficient(
la: &Partition,
mu: &Partition,
nu: &Partition,
) -> Option<i128> {
let n = la.size();
if mu.size() != n || nu.size() != n {
return Some(0);
}
let factorial: i128 = (1..=i128::from(n)).try_fold(1i128, i128::checked_mul)?;
let thetas = crate::partitions_of(n);
let dims: Vec<i128> = thetas
.iter()
.map(|th| i128::try_from(crate::dimension(th)?).ok())
.collect::<Option<_>>()?;
let mut num = 0i128;
let mut den = 1i128;
for (th, &f) in thetas.iter().zip(dims.iter()) {
let term = crate::try_character(th, la)?
.checked_mul(crate::try_character(th, mu)?)?
.checked_mul(crate::try_character(th, nu)?)?;
let g = gcd(den, f);
num = num
.checked_mul(f / g)?
.checked_add(term.checked_mul(den / g)?)?;
den = (den / g).checked_mul(f)?;
let g = gcd(num.abs(), den);
if g > 1 {
num /= g;
den /= g;
}
}
let whole = num.checked_mul(factorial)?;
let denom = den
.checked_mul(i128::try_from(mu.try_z()?).ok()?)?
.checked_mul(i128::try_from(nu.try_z()?).ok()?)?;
debug_assert_eq!(
whole % denom,
0,
"the connection coefficient must be an integer"
);
Some(whole / denom)
}
fn coset_type(a: &[usize], b: &[usize]) -> Partition {
let mut seen = vec![false; a.len()];
let mut parts = Vec::new();
for start in 0..a.len() {
if seen[start] {
continue;
}
let mut j = start;
let mut k = 0u32;
loop {
seen[j] = true;
seen[a[j]] = true;
j = b[a[j]];
k += 1;
if j == start {
break;
}
}
parts.push(k);
}
Partition::new(parts)
}
fn matching_of_type(lambda: &Partition) -> Vec<usize> {
let n = lambda.size() as usize;
let mut m = vec![0usize; 2 * n];
let mut base = 0usize;
for &part in lambda.parts() {
let len = 2 * part as usize;
for s in (1..len).step_by(2) {
m[base + s] = base + (s + 1) % len;
m[base + (s + 1) % len] = base + s;
}
base += len;
}
m
}
fn pairs_in_order(n: usize) -> Vec<usize> {
let mut m = vec![0usize; 2 * n];
for i in 0..n {
m[2 * i] = 2 * i + 1;
m[2 * i + 1] = 2 * i;
}
m
}
fn for_each_matching(n: usize, mut f: impl FnMut(&[usize])) {
let mut m = vec![usize::MAX; 2 * n];
fn go(m: &mut Vec<usize>, f: &mut impl FnMut(&[usize])) {
match m.iter().position(|&v| v == usize::MAX) {
None => f(m),
Some(i) => {
for j in i + 1..m.len() {
if m[j] == usize::MAX {
m[i] = j;
m[j] = i;
go(m, f);
m[i] = usize::MAX;
m[j] = usize::MAX;
}
}
}
}
}
go(&mut m, &mut f);
}
pub fn double_coset_coefficient(la: &Partition, mu: &Partition, nu: &Partition) -> u64 {
let n = la.size() as usize;
if mu.size() as usize != n || nu.size() as usize != n {
return 0;
}
let d0 = pairs_in_order(n);
let d1 = matching_of_type(la);
debug_assert_eq!(&coset_type(&d0, &d1), la, "the witness has the wrong type");
let mut count = 0u64;
for_each_matching(n, |d| {
if &coset_type(&d0, d) == mu && &coset_type(d, &d1) == nu {
count += 1;
}
});
count
}
pub fn double_coset_table(n: u32) -> BTreeMap<Key, u64> {
let mut out: BTreeMap<Key, u64> = BTreeMap::new();
if n == 0 {
return out;
}
let d0 = pairs_in_order(n as usize);
for la in crate::partitions_of(n) {
let d1 = matching_of_type(&la);
for_each_matching(n as usize, |d| {
let mu = coset_type(&d0, d);
let nu = coset_type(d, &d1);
*out.entry((la.clone(), mu, nu)).or_insert(0) += 1;
});
}
out
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Coverage {
ProvedByGj,
SinglePartVariant,
Open,
}
pub fn matchings_jack_coverage(la: &Partition, mu: &Partition, nu: &Partition) -> Coverage {
let n = la.size();
let is_single = |p: &Partition| p.parts() == [n];
let all_ones = la.parts().iter().all(|&p| p == 1);
let hook21 = {
let p = la.parts();
p.first() == Some(&2) && p[1..].iter().all(|&v| v == 1)
};
if all_ones || hook21 {
Coverage::ProvedByGj
} else if is_single(la) || is_single(mu) || is_single(nu) {
Coverage::SinglePartVariant
} else {
Coverage::Open
}
}
fn gcd(mut a: i128, mut b: i128) -> i128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a.max(1)
}
#[cfg(test)]
mod tests {
use super::*;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn class_algebra_on_s3() {
let t = part(&[2, 1]);
assert_eq!(class_algebra_coefficient(&part(&[1, 1, 1]), &t, &t), 3);
assert_eq!(class_algebra_coefficient(&part(&[3]), &t, &t), 3);
assert_eq!(class_algebra_coefficient(&part(&[2, 1]), &t, &t), 0);
}
#[test]
fn the_tables_are_empty_at_zero() {
let t = gj_connection_tables(0);
assert!(t.c.is_empty(), "c at n = 0: {:?}", t.c);
assert!(t.h.is_empty(), "h at n = 0: {:?}", t.h);
assert!(t.not_polynomial.is_empty(), "{:?}", t.not_polynomial);
assert!(t.c_not_integral.is_empty(), "{:?}", t.c_not_integral);
assert!(t.negative.is_empty(), "{:?}", t.negative);
}
#[test]
fn the_c_table_at_b_zero_is_the_class_algebra() {
for n in 1..=6u32 {
let t = gj_connection_tables(n);
assert!(t.laws_hold(), "a proven law failed at n = {n}: {t:?}");
let parts = crate::partitions_of(n);
for la in &parts {
for mu in &parts {
for nu in &parts {
let key = (la.clone(), mu.clone(), nu.clone());
let got = t.c.get(&key).map_or((0, 1), BPoly::at_zero);
let want = class_algebra_coefficient(la, mu, nu);
assert_eq!(got.1, 1, "c must be integral at {key:?}");
assert_eq!(
got.0, want,
"c^{la}_{{{mu},{nu}}}(0) = {} but a^λ_μν = {want}",
got.0
);
}
}
}
}
}
#[test]
fn the_proven_laws_hold() {
for n in 1..=6u32 {
let t = gj_connection_tables(n);
assert!(
t.not_polynomial.is_empty(),
"n = {n}: [DF] says these collapse: {:?}",
t.not_polynomial
);
assert!(
t.c_not_integral.is_empty(),
"n = {n}: [BD] says c is integral, but {:?}",
t.c_not_integral
);
assert!(
!t.c.is_empty() && !t.h.is_empty(),
"n = {n} produced nothing"
);
}
}
#[test]
fn positivity_is_observed_not_assumed() {
for n in 1..=6u32 {
let t = gj_connection_tables(n);
assert!(
t.negative.is_empty(),
"n = {n}: a NEGATIVE coefficient — this is a RESULT, verify the \
normalization against docs/record/jack.md and REPORT \
it, do not 'fix' it: {:?}",
t.negative
);
}
}
#[test]
fn h_is_supported_where_c_is() {
for n in 1..=5u32 {
let t = gj_connection_tables(n);
for key in t.h.keys() {
assert!(
t.c.contains_key(key),
"n = {n}: h has {key:?} where c does not"
);
}
}
}
#[test]
fn the_binomial_shift() {
assert_eq!(shift_to_b(&[5]), vec![5]);
assert_eq!(shift_to_b(&[0, 1]), vec![1, 1], "α = 1 + b");
assert_eq!(shift_to_b(&[0, 0, 1]), vec![1, 2, 1], "α² = 1 + 2b + b²");
assert_eq!(shift_to_b(&[0, -1, 1]), vec![0, 1, 1], "α² − α = b + b²");
}
#[test]
fn the_b_one_slice_is_the_double_coset_algebra() {
for n in 1..=6u32 {
let t = gj_connection_tables(n);
let want = double_coset_table(n);
let parts = crate::partitions_of(n);
let mut checked = 0;
for la in &parts {
for mu in &parts {
for nu in &parts {
let key = (la.clone(), mu.clone(), nu.clone());
let got =
t.c.get(&key)
.map_or((0i128, 1u128), |p| (p.num.iter().sum::<i128>(), p.den));
let b = *want.get(&key).unwrap_or(&0) as i128;
assert_eq!(got.1, 1, "c^{la}_{{{mu},{nu}}}(1) is not an integer");
assert_eq!(got.0, b, "c^{la}_{{{mu},{nu}}}(1)");
checked += 1;
}
}
}
assert!(checked > 0);
}
}
#[test]
fn coset_types_are_what_they_should_be() {
for n in 0..=5usize {
let d0 = pairs_in_order(n);
assert_eq!(coset_type(&d0, &d0), Partition::new(vec![1; n]));
for la in crate::partitions_of(n as u32) {
assert_eq!(coset_type(&d0, &matching_of_type(&la)), la);
}
let mut count = 0usize;
for_each_matching(n, |_| count += 1);
let want: usize = (1..=n).map(|k| 2 * k - 1).product();
assert_eq!(count, want, "matchings of 2*{n} points");
}
}
#[test]
fn the_coverage_classifier_is_conservative() {
let p = |v: Vec<u32>| Partition::new(v);
let ones = p(vec![1, 1, 1, 1]);
let hook = p(vec![2, 1, 1]);
assert_eq!(
matchings_jack_coverage(&ones, &p(vec![2, 2]), &p(vec![2, 2])),
Coverage::ProvedByGj
);
assert_eq!(
matchings_jack_coverage(&hook, &p(vec![2, 2]), &p(vec![2, 2])),
Coverage::ProvedByGj
);
assert_eq!(
matchings_jack_coverage(&p(vec![2, 2]), &p(vec![4]), &p(vec![2, 2])),
Coverage::SinglePartVariant
);
assert_eq!(
matchings_jack_coverage(&p(vec![2, 2]), &p(vec![2, 2]), &p(vec![2, 2])),
Coverage::Open
);
for n in 0..=3u32 {
for la in crate::partitions_of(n) {
for mu in crate::partitions_of(n) {
for nu in crate::partitions_of(n) {
assert_ne!(
matchings_jack_coverage(&la, &mu, &nu),
Coverage::Open,
"{la} {mu} {nu}"
);
}
}
}
}
}
}