#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::BTreeMap;
use crate::coeff::Ring;
use crate::convert::jt_compositions;
use crate::partition::Partition;
use crate::qt::QtPoly;
pub(crate) fn eigenvalue<C: Ring>(alpha: &[u32]) -> QtPoly<C> {
let n = alpha.len();
let mut out = QtPoly::zero();
for (i, &a) in alpha.iter().enumerate() {
out.add_term(a, (n - 1 - i) as u32, C::one());
}
out
}
pub(crate) fn eigenvalue_of<C: Ring>(lambda: &Partition, n: usize) -> QtPoly<C> {
let padded: Vec<u32> = (0..n).map(|i| lambda.part(i)).collect();
eigenvalue(&padded)
}
pub fn operator_matrix<C: Ring>(n: u32) -> Vec<Vec<QtPoly<C>>> {
let parts = crate::memo::partitions_cached(n);
let index: std::collections::HashMap<&Partition, usize> =
parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let width = n as usize;
let kostka = crate::kostka::kostka_table(n);
let mut out = vec![vec![QtPoly::zero(); parts.len()]; parts.len()];
let mut d: Vec<QtPoly<C>> = vec![QtPoly::zero(); parts.len()];
for (j, mu) in parts.iter().enumerate() {
for e in d.iter_mut() {
*e = QtPoly::zero();
}
let padded: Vec<u32> = (0..width).map(|i| mu.part(i)).collect();
jt_compositions(&padded, &mut |alpha, sign| {
let ev: QtPoly<C> = eigenvalue(alpha);
let nu = Partition::new(alpha.iter().copied());
let slot = &mut d[index[&nu]];
if sign < 0 {
slot.sub_assign(&ev);
} else {
slot.add_assign(&ev);
}
});
for (nu, dv) in d.iter().enumerate() {
if dv.is_empty() {
continue;
}
for kappa in 0..parts.len() {
let k = kostka[kappa][nu];
if k == 0 {
continue;
}
let scaled = dv.mul(&QtPoly::term(0, 0, C::from_u128(k)));
out[kappa][j].add_assign(&scaled);
}
}
}
out
}
pub fn eigenvector<C: Ring>(lambda: &Partition) -> (Vec<QtPoly<C>>, QtPoly<C>) {
let n = lambda.size();
let a: Vec<Vec<QtPoly<C>>> = operator_matrix(n);
solve(n, &a, lambda)
}
pub fn eigenvectors<C: Ring>(n: u32) -> Vec<(Partition, Vec<QtPoly<C>>, QtPoly<C>)> {
let a: Vec<Vec<QtPoly<C>>> = operator_matrix(n);
crate::memo::partitions_cached(n)
.iter()
.map(|lambda| {
let (b, v) = solve(n, &a, lambda);
(lambda.clone(), b, v)
})
.collect()
}
#[derive(Clone)]
struct Coeff<C: Ring> {
num: QtPoly<C>,
den: BTreeMap<usize, u32>,
}
impl<C: Ring> Coeff<C> {
fn zero() -> Self {
Coeff {
num: QtPoly::zero(),
den: BTreeMap::new(),
}
}
fn one() -> Self {
Coeff {
num: <QtPoly<C> as Ring>::one(),
den: BTreeMap::new(),
}
}
fn is_zero(&self) -> bool {
self.num.is_empty()
}
fn lift(&self, target: &BTreeMap<usize, u32>, gap: &[QtPoly<C>]) -> QtPoly<C> {
let mut num = self.num.clone();
for (&k, &m) in target {
for _ in 0..(m - self.den.get(&k).copied().unwrap_or(0)) {
num = num.mul(&gap[k]);
}
}
num
}
fn add_mul(&mut self, other: &Self, p: &QtPoly<C>, gap: &[QtPoly<C>]) {
if other.is_zero() || p.is_empty() {
return;
}
if self.is_zero() {
self.num = other.num.mul(p);
self.den = other.den.clone();
return;
}
if other.den != self.den {
let mut lcm = self.den.clone();
for (&k, &m) in &other.den {
let e = lcm.entry(k).or_insert(0);
*e = (*e).max(m);
}
self.num = self.lift(&lcm, gap);
self.den = lcm;
}
let lifted = other.lift(&self.den, gap);
self.num.add_assign(&lifted.mul(p));
}
fn reduce(&mut self, gap: &[QtPoly<C>]) {
if self.num.is_empty() {
self.den.clear();
return;
}
self.den.retain(|&k, m| {
while *m > 0 {
match self.num.divide_exact(&gap[k]) {
Some(q) => {
self.num = q;
*m -= 1;
}
None => break,
}
}
*m > 0
});
}
}
fn solve<C: Ring>(n: u32, a: &[Vec<QtPoly<C>>], lambda: &Partition) -> (Vec<QtPoly<C>>, QtPoly<C>) {
let parts = crate::memo::partitions_cached(n);
let width = n as usize;
let evs: Vec<QtPoly<C>> = parts.iter().map(|p| eigenvalue_of(p, width)).collect();
let li = parts
.iter()
.position(|p| p == lambda)
.expect("lambda must be a partition of its own size");
let gap: Vec<QtPoly<C>> = evs
.iter()
.map(|e| {
let mut d = e.clone();
d.sub_assign(&evs[li]);
d
})
.collect();
let above: Vec<usize> = (0..parts.len())
.filter(|&k| k != li && crate::kostka::dominates(&parts[k], lambda))
.collect();
let mut coeff: Vec<Coeff<C>> = vec![Coeff::zero(); parts.len()];
coeff[li] = Coeff::one();
let mut order = above.clone();
order.sort_by(|&x, &y| parts[x].parts().cmp(parts[y].parts()));
for &k in &order {
let mut sum = Coeff::zero();
for m in 0..parts.len() {
if m == k {
continue;
}
let prev = coeff[m].clone();
sum.add_mul(&prev, &a[k][m], &gap);
}
sum.num = sum.num.neg();
*sum.den.entry(k).or_insert(0) += 1;
sum.reduce(&gap);
coeff[k] = sum;
}
let mut lcm: BTreeMap<usize, u32> = BTreeMap::new();
for c in &coeff {
for (&k, &m) in &c.den {
let e = lcm.entry(k).or_insert(0);
*e = (*e).max(m);
}
}
let mut v = <QtPoly<C> as Ring>::one();
for (&k, &m) in &lcm {
for _ in 0..m {
v = v.mul(&gap[k]);
}
}
let b = coeff.iter().map(|c| c.lift(&lcm, &gap)).collect();
(b, v)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::sym::{Homogeneous, Schur, SymFn};
#[test]
fn the_action_is_triangular_with_the_eigenvalues_on_the_diagonal() {
for n in 0..=7u32 {
let parts = crate::partitions_of(n);
let a: Vec<Vec<QtPoly<Rational>>> = operator_matrix(n);
for (j, mu) in parts.iter().enumerate() {
for (i, kappa) in parts.iter().enumerate() {
if i == j {
assert_eq!(a[i][j], eigenvalue_of(mu, n as usize), "diagonal at {mu}");
} else if !crate::kostka::dominates(kappa, mu) {
assert!(
a[i][j].is_empty(),
"M1 S_{mu} has a {kappa} term, but {kappa} does not dominate {mu}"
);
}
}
}
}
}
#[test]
fn the_solution_really_is_an_eigenvector() {
for n in 0..=7u32 {
let parts = crate::partitions_of(n);
let a: Vec<Vec<QtPoly<i64>>> = operator_matrix(n);
for lambda in &parts {
let (b, v) = eigenvector::<i64>(lambda);
assert!(!v.is_empty(), "the common denominator must be nonzero");
let ev = eigenvalue_of::<i64>(lambda, n as usize);
for k in 0..parts.len() {
let mut lhs = QtPoly::zero();
for m in 0..parts.len() {
lhs.add_assign(&a[k][m].mul(&b[m]));
}
let rhs = ev.mul(&b[k]);
assert_eq!(lhs, rhs, "row {} of M1 b = [|{lambda}|] b", parts[k]);
}
}
}
}
#[test]
fn the_eigenvector_is_supported_above_lambda() {
for n in 0..=7u32 {
let parts = crate::partitions_of(n);
for (li, lambda) in parts.iter().enumerate() {
let (b, v) = eigenvector::<i64>(lambda);
assert_eq!(b[li], v, "the {lambda} coefficient is the normalization");
for (k, kappa) in parts.iter().enumerate() {
if !crate::kostka::dominates(kappa, lambda) {
assert!(b[k].is_empty(), "J_{lambda} should have no {kappa} term");
}
}
}
}
}
#[test]
fn the_eigenvector_is_the_integral_form() {
use crate::convert::{FromSchur, ToSchur};
use crate::frac::Frac;
use crate::sym::{Monomial, PowerSum};
use std::collections::BTreeMap;
fn modify(f: &Schur<Frac<Rational>>) -> Schur<Frac<Rational>> {
let p: PowerSum<Frac<Rational>> = PowerSum::from_schur(f);
let mut out = PowerSum::zero();
for (rho, c) in p.terms() {
let mut factors: BTreeMap<(u32, u32), i32> = BTreeMap::new();
for &k in rho.parts() {
*factors.entry((0, k)).or_insert(0) += 1; *factors.entry((k, 0)).or_insert(0) -= 1; }
let mut v = c.mul_factors(&factors);
v.reduce();
out.add_term(rho.clone(), v);
}
out.to_schur()
}
for n in 0..=5u32 {
let parts = crate::partitions_of(n);
for lambda in &parts {
let (b, v) = eigenvector::<Rational>(lambda);
let mut formal: Schur<Frac<Rational>> = Schur::zero();
for (k, kappa) in parts.iter().enumerate() {
formal.add_term(kappa.clone(), Frac::from_poly(b[k].clone()));
}
let got = modify(&formal);
let j: Monomial<Frac<Rational>> = crate::macdonald_j(lambda);
let j: Schur<Frac<Rational>> = j.to_schur();
let scale = Frac::from_poly(v.clone());
let want: Schur<Frac<Rational>> = Schur::from_terms(
j.terms()
.iter()
.map(|(k, c)| (k.clone(), c.mul(&scale)))
.collect(),
);
let (gl, wl) = (got.coeff(lambda), want.coeff(lambda));
assert!(
!gl.is_zero() && !wl.is_zero(),
"{lambda} coefficient vanished"
);
let keys: std::collections::BTreeSet<_> =
got.terms().keys().chain(want.terms().keys()).collect();
for kappa in keys {
assert_eq!(
got.coeff(kappa).mul(&wl),
want.coeff(kappa).mul(&gl),
"J_{lambda} at {kappa}"
);
}
}
}
}
#[test]
fn the_solve_is_exact_in_fixed_width() {
for n in 0..=8u32 {
let narrow: Vec<(_, Vec<QtPoly<i64>>, QtPoly<i64>)> = eigenvectors(n);
let wide: Vec<(_, Vec<QtPoly<i128>>, QtPoly<i128>)> = eigenvectors(n);
for ((lambda, x, _), (_, y, _)) in narrow.iter().zip(wide.iter()) {
for (p, q) in x.iter().zip(y.iter()) {
let widened: Vec<_> = p.terms().map(|(k, c)| (*k, *c as i128)).collect();
let got: Vec<_> = q.terms().map(|(k, c)| (*k, *c)).collect();
assert_eq!(widened, got, "J_{lambda} differs between i64 and i128");
}
}
}
}
#[test]
fn the_eigenvalues_are_distinct() {
for n in 0..=8u32 {
let parts = crate::partitions_of(n);
let evs: Vec<QtPoly<Rational>> =
parts.iter().map(|p| eigenvalue_of(p, n as usize)).collect();
for i in 0..evs.len() {
for j in (i + 1)..evs.len() {
assert_ne!(evs[i], evs[j], "{} and {}", parts[i], parts[j]);
}
}
}
}
#[test]
fn the_composition_walk_reproduces_the_s_to_h_transition() {
use crate::convert::FromSchur;
for n in 0..=7u32 {
for mu in crate::partitions_of(n) {
let padded: Vec<u32> = (0..n as usize).map(|i| mu.part(i)).collect();
let mut got: Homogeneous<Rational> = Homogeneous::zero();
jt_compositions(&padded, &mut |alpha, sign| {
got.add_term(
Partition::new(alpha.iter().copied()),
Rational::from_int(i128::from(sign)),
);
});
let want: Homogeneous<Rational> =
Homogeneous::from_schur(&Schur::monomial(mu.clone(), Rational::from_int(1)));
assert_eq!(got, want, "s -> h at {mu}");
}
}
}
}