#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::gj::{BPoly, GjTables, Key};
use crate::jack::{jack_j_powersum, jack_norm_j};
use crate::modular as mp;
use crate::partition::Partition;
use crate::sym::SymFn;
struct Degrees {
parts: Vec<Vec<Partition>>,
index: Vec<BTreeMap<Partition, usize>>,
union: Vec<Vec<Vec<u32>>>,
}
impl Degrees {
fn new(n: u32) -> Self {
let parts: Vec<Vec<Partition>> = (0..=n).map(crate::partitions_of).collect();
let index: Vec<BTreeMap<Partition, usize>> = parts
.iter()
.map(|v| v.iter().cloned().zip(0..).collect())
.collect();
let mut union = vec![vec![Vec::new(); n as usize + 1]; n as usize + 1];
for j in 0..=n as usize {
for m in 0..=n as usize - j {
let mut t = Vec::with_capacity(parts[j].len() * parts[m].len());
for a in &parts[j] {
for b in &parts[m] {
let mut v = a.parts().to_vec();
v.extend_from_slice(b.parts());
t.push(index[j + m][&Partition::new(v)] as u32);
}
}
union[j][m] = t;
}
}
Degrees {
parts,
index,
union,
}
}
fn len(&self, k: usize) -> usize {
self.parts[k].len()
}
fn cube(&self, k: usize) -> usize {
let p = self.len(k);
p * p * p
}
}
struct Exact {
jp: Vec<Vec<Vec<(Vec<i128>, u128)>>>,
norm: Vec<Vec<Vec<((u32, u32), i32)>>>,
}
impl Exact {
fn new(n: u32, deg: &Degrees) -> Self {
let mut jp = vec![Vec::new(); n as usize + 1];
let mut norm = vec![Vec::new(); n as usize + 1];
for k in 1..=n as usize {
for theta in °.parts[k] {
let f = jack_j_powersum::<i128>(theta);
let mut row = vec![(Vec::new(), 1u128); deg.len(k)];
for (rho, c) in f.terms() {
let (num, den, scale) = c.parts();
assert_eq!(
den.count(),
0,
"J_{theta} at p_{rho} carries a linear atom; the modular \
engine's evaluation of it would be wrong"
);
row[deg.index[k][rho]] = (num.to_vec(), scale);
}
jp[k].push(row);
norm[k].push(jack_norm_j(theta).into_iter().collect());
}
}
Exact { jp, norm }
}
}
fn run_point(n: usize, deg: &Degrees, ex: &Exact, alpha: u64, p: mp::Md) -> (Vec<u64>, Vec<u64>) {
let mut phi: Vec<Vec<u64>> = Vec::with_capacity(n + 1);
phi.push(vec![1u64]); for k in 1..=n {
let pk = deg.len(k);
let mut slab = vec![0u64; deg.cube(k)];
for (t, row) in ex.jp[k].iter().enumerate() {
let a: Vec<u64> = row
.iter()
.map(|(num, scale)| {
if num.is_empty() {
return 0;
}
let mut acc = 0u64;
for c in num.iter().rev() {
acc = mp::add(mp::mul(acc, alpha, p), mp::from_i128(*c, p), p);
}
mp::mul(acc, mp::inv(p.from_u128(*scale), p), p)
})
.collect();
let mut den = 1u64;
for &((u, v), m) in &ex.norm[k][t] {
let f = mp::add(mp::mul(u as u64 % p.p, alpha, p), v as u64 % p.p, p);
for _ in 0..m {
den = mp::mul(den, f, p);
}
}
let inv_den = mp::inv(den, p);
let scaled: Vec<u64> = a.iter().map(|&x| mp::mul(x, inv_den, p)).collect();
for i in 0..pk {
if scaled[i] == 0 {
continue;
}
for j in 0..pk {
if a[j] == 0 {
continue;
}
let ij = mp::mul(scaled[i], a[j], p);
let base = (i * pk + j) * pk;
for l in 0..pk {
if a[l] == 0 {
continue;
}
slab[base + l] = mp::add(slab[base + l], mp::mul(ij, a[l], p), p);
}
}
}
}
phi.push(slab);
}
let mut g: Vec<Vec<u64>> = Vec::with_capacity(n + 1);
g.push(vec![0u64]);
for k in 1..=n {
let pk = deg.len(k);
let mut acc: Vec<u64> = phi[k]
.iter()
.map(|&x| mp::mul(x, k as u64 % p.p, p))
.collect();
for j in 1..k {
let m = k - j;
let (pj, pm) = (deg.len(j), deg.len(m));
let (uj, gj, pm_slab) = (°.union[j][m], &g[j], &phi[m]);
for a1 in 0..pj {
for b1 in 0..pj {
for c1 in 0..pj {
let lhs = gj[(a1 * pj + b1) * pj + c1];
if lhs == 0 {
continue;
}
for a2 in 0..pm {
let ta = uj[a1 * pm + a2] as usize;
for b2 in 0..pm {
let tb = uj[b1 * pm + b2] as usize;
let base = (ta * pk + tb) * pk;
for c2 in 0..pm {
let rhs = pm_slab[(a2 * pm + b2) * pm + c2];
if rhs == 0 {
continue;
}
let tc = uj[c1 * pm + c2] as usize;
let v = mp::mul(lhs, rhs, p);
acc[base + tc] = mp::sub(acc[base + tc], v, p);
}
}
}
}
}
}
}
g.push(acc);
}
let pn = deg.len(n);
let mut c = vec![0u64; deg.cube(n)];
for i in 0..pn {
let lam = °.parts[n][i];
let w = mp::mul(p.from_u128(lam.z()), mp::pow(alpha, lam.len() as u64, p), p);
for j in 0..pn {
for l in 0..pn {
let idx = (i * pn + j) * pn + l;
c[idx] = mp::mul(phi[n][idx], w, p);
}
}
}
let h: Vec<u64> = g[n].iter().map(|&x| mp::mul(x, alpha, p)).collect();
(c, h)
}
type Rows = (Vec<Vec<u64>>, Vec<Vec<u64>>);
fn rows_for_prime(n: usize, deg: &Degrees, ex: &Exact, points: usize, p: mp::Md) -> Rows {
let xs: Vec<u64> = (1..=points as u64).collect();
let mut cs: Vec<Vec<u64>> = Vec::with_capacity(points);
let mut hs: Vec<Vec<u64>> = Vec::with_capacity(points);
for &x in &xs {
let (c, h) = run_point(n, deg, ex, x, p);
cs.push(c);
hs.push(h);
}
let size = deg.cube(n);
let tmat = mp::lagrange_matrix(&xs, 1, p);
let mut cpoly = Vec::with_capacity(size);
let mut hpoly = Vec::with_capacity(size);
let mut cv = vec![0u64; points];
let mut hv = vec![0u64; points];
for idx in 0..size {
for k in 0..points {
cv[k] = cs[k][idx];
hv[k] = hs[k][idx];
}
cpoly.push(mp::apply_matrix(&tmat, &cv, p));
hpoly.push(mp::apply_matrix(&tmat, &hv, p));
}
(cpoly, hpoly)
}
fn assemble(n: u32, deg: &Degrees, rows: &[Rows]) -> (GjTables, usize) {
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: rows.len() as u32,
};
let pn = deg.len(n as usize);
let size = deg.cube(n as usize);
let lift_count = rows.len() - 1;
let lift_primes: Vec<mp::Md> = (0..lift_count).map(mp::nth_prime).collect();
let check = mp::nth_prime(lift_count);
let modulus: u128 = lift_primes.iter().map(|q| q.p as u128).product();
let bound = mp::bound_for(modulus);
let mut short = 0usize;
for idx in 0..size {
let (i, j, l) = (idx / (pn * pn), (idx / pn) % pn, idx % pn);
let key: Key = (
deg.parts[n as usize][i].clone(),
deg.parts[n as usize][j].clone(),
deg.parts[n as usize][l].clone(),
);
for (tag, which) in [("c", 0usize), ("h", 1usize)] {
let all: Vec<&Vec<u64>> = rows
.iter()
.map(|r| if which == 0 { &r.0[idx] } else { &r.1[idx] })
.collect();
if all
.iter()
.any(|poly| poly.iter().skip(n as usize + 1).any(|&v| v != 0))
{
t.not_polynomial.push((tag, key.clone()));
continue;
}
let Some(poly) = lift(&all[..lift_count], &lift_primes, modulus, bound) else {
t.not_polynomial.push((tag, key.clone()));
short += 1;
continue;
};
if !agrees_mod(&poly, all[lift_count], check) {
t.not_polynomial.push((tag, key.clone()));
short += 1;
continue;
}
if poly.num.is_empty() {
continue;
}
for &v in &poly.num {
t.peak_bits = t.peak_bits.max(128 - v.unsigned_abs().leading_zeros());
}
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()));
}
if which == 0 {
t.c.insert(key.clone(), poly);
} else {
t.h.insert(key.clone(), poly);
}
}
}
(t, short)
}
pub fn gj_connection_tables_modular(n: u32) -> GjTables {
const MIN_PRIMES: usize = 4;
const MAX_PRIMES: usize = 5;
if n == 0 {
return 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,
};
}
let deg = Degrees::new(n);
let ex = Exact::new(n, °);
let points = n as usize + 4;
let mut rows: Vec<Rows> = Vec::new();
let mut want = MIN_PRIMES;
loop {
while rows.len() < want {
let p = mp::nth_prime(rows.len());
rows.push(rows_for_prime(n as usize, °, &ex, points, p));
}
let (t, short) = assemble(n, °, &rows);
if short == 0 || want >= MAX_PRIMES {
return t;
}
want += 1;
}
}
fn agrees_mod(poly: &BPoly, want: &[u64], p: mp::Md) -> bool {
let inv_den = mp::inv(p.from_u128(poly.den), p);
(0..want.len()).all(|k| {
let got = poly
.num
.get(k)
.map_or(0, |&v| mp::mul(mp::from_i128(v, p), inv_den, p));
got == want[k]
})
}
fn lift(rows: &[&Vec<u64>], primes: &[mp::Md], modulus: u128, bound: u128) -> Option<BPoly> {
let width = rows[0].len();
let mut nums: Vec<i128> = Vec::with_capacity(width);
let mut dens: Vec<u128> = Vec::with_capacity(width);
let mut residues = vec![0u64; rows.len()];
for k in 0..width {
for (r, row) in residues.iter_mut().zip(rows.iter()) {
*r = row[k];
}
let (x, m) = mp::crt(&residues, primes);
debug_assert_eq!(m, modulus);
let (num, den) = mp::reconstruct(x, modulus, bound)?;
nums.push(num);
dens.push(den);
}
let mut common: u128 = 1;
for &d in &dens {
common = common / mp::gcd128(common, d) * d;
}
let num: Vec<i128> = nums
.iter()
.zip(dens.iter())
.map(|(&n, &d)| {
let scale = i128::try_from(common / d)
.unwrap_or_else(|_| panic!("the scale {common}/{d} does not fit i128"));
n * scale
})
.collect();
let mut out = BPoly { num, den: common };
while out.num.last() == Some(&0) {
out.num.pop();
}
let mut g = out.den;
for &v in &out.num {
g = mp::gcd128(g, v.unsigned_abs());
}
if g > 1 {
out.den /= g;
let g = i128::try_from(g).unwrap_or_else(|_| panic!("the gcd {g} does not fit i128"));
for v in &mut out.num {
*v /= g;
}
}
Some(out)
}
pub fn engines_agree(n: u32) -> Result<usize, String> {
let exact = crate::gj::gj_connection_tables(n);
let modular = gj_connection_tables_modular(n);
if !modular.laws_hold() {
return Err(format!(
"modular engine reported a broken law at n = {n}: {:?} / {:?}",
modular.not_polynomial, modular.c_not_integral
));
}
let mut checked = 0;
for (name, a, b) in [("c", &exact.c, &modular.c), ("h", &exact.h, &modular.h)] {
if a.len() != b.len() {
return Err(format!(
"{name} at n = {n}: exact has {} entries, modular {}",
a.len(),
b.len()
));
}
for (key, want) in a {
match b.get(key) {
Some(got) if got == want => checked += 1,
Some(got) => {
return Err(format!(
"{name} at {key:?}: exact {want:?}, modular {got:?}"
))
}
None => return Err(format!("{name} at {key:?}: missing from the modular table")),
}
}
}
Ok(checked)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn the_modular_engine_agrees_with_the_exact_one() {
for n in 1..=6u32 {
let checked = engines_agree(n).unwrap_or_else(|e| panic!("{e}"));
assert!(checked > 0, "n = {n} compared nothing");
}
}
#[test]
fn the_spare_coefficients_vanish() {
for n in 1..=5u32 {
let t = gj_connection_tables_modular(n);
assert!(
t.not_polynomial.is_empty(),
"n = {n}: an interpolated answer exceeded its degree bound or \
failed reconstruction: {:?}",
t.not_polynomial
);
for poly in t.c.values().chain(t.h.values()) {
assert!(
poly.num.len() <= n as usize,
"n = {n}: b-degree {} exceeds the measured n−1 bound",
poly.num.len() - 1
);
}
}
}
#[test]
fn the_modular_b_zero_slice_is_the_class_algebra() {
for n in 1..=6u32 {
let t = gj_connection_tables_modular(n);
for la in crate::partitions_of(n) {
for mu in crate::partitions_of(n) {
for nu in crate::partitions_of(n) {
let key = (la.clone(), mu.clone(), nu.clone());
let got = t.c.get(&key).map_or((0, 1), BPoly::at_zero);
let want = crate::class_algebra_coefficient(&la, &mu, &nu);
assert_eq!(got, (want, 1), "c^{la}_{{{mu},{nu}}}(0)");
}
}
}
}
}
#[test]
fn the_reconstruction_bound_is_reached_and_then_escaped() {
let n = 8u32;
let deg = Degrees::new(n);
let ex = Exact::new(n, °);
let points = n as usize + 4;
let rows: Vec<Rows> = (0..4)
.map(|k| rows_for_prime(n as usize, °, &ex, points, mp::nth_prime(k)))
.collect();
let (thin, short) = assemble(n, °, &rows[..2]);
assert!(
short > 0,
"a 2^15 bound was somehow enough for 18-bit values"
);
assert!(!thin.laws_hold(), "and it must be reported, not swallowed");
let (full, short) = assemble(n, °, &rows[..4]);
assert_eq!(short, 0, "three primes must be enough at n = 8");
assert!(full.laws_hold());
assert_eq!(full.primes_used, 4);
let driver = gj_connection_tables_modular(n);
assert_eq!(driver.c, full.c);
assert_eq!(driver.h, full.h);
assert_eq!(driver.primes_used, 4);
}
}