use crate::coeff::{Plethystic, Ring};
use crate::convert::FromSchur;
use crate::partition::Partition;
use crate::sym::{Homogeneous, Schur, SymFn};
use crate::convert::ToSchur;
use crate::sym::PowerSum;
pub fn adams_one_row<C: Ring>(k: u32, m: u32) -> Schur<C> {
assert!(k > 0, "p_k[h_m] needs k ≥ 1");
let slots = k as usize;
let mut out = Schur::zero();
let base_even = (slots * (slots - 1) / 2).is_multiple_of(2);
let mut rows = Vec::with_capacity(slots);
compositions(m, slots, &mut rows, &mut |a: &[u32]| {
let betas: Vec<u32> = (0..k).zip(a).map(|(i, &x)| k * x + i).collect();
let inversions = (0..slots)
.flat_map(|x| (x + 1..slots).map(move |y| (x, y)))
.filter(|&(x, y)| betas[x] < betas[y])
.count();
let mut sorted = betas;
sorted.sort_unstable_by(|a, b| b.cmp(a));
let parts: Vec<u32> = sorted
.iter()
.zip(0..k)
.map(|(&b, j)| b - (k - 1 - j))
.filter(|&p| p > 0)
.collect();
let positive = inversions.is_multiple_of(2) == base_even;
let c = if positive { C::one() } else { C::one().neg() };
out.add_term(Partition::from_sorted(parts), c);
});
out
}
fn adams_schur(k: u32, nu: &Partition) -> Vec<(Partition, i128)> {
let n = nu.size();
if n == 0 {
return vec![(Partition::default(), 1)];
}
let beads = n + 1;
let base_positive = quotient_sign(&vec![Partition::default(); k as usize], k, beads).1;
let cx = Sweep {
k,
nu,
beads,
base_positive,
};
let mut out: Vec<(Partition, i128)> = Vec::new();
let mut quot: Vec<Partition> = Vec::with_capacity(k as usize);
let root: Vec<(Partition, i128)> = vec![(Partition::default(), 1)];
sweep_slots(&cx, n, 0, &mut quot, &root, &mut out);
out
}
struct Sweep<'a> {
k: u32,
nu: &'a Partition,
beads: u32,
base_positive: bool,
}
fn sweep_slots(
cx: &Sweep,
left: u32,
slot: u32,
quot: &mut Vec<Partition>,
layer: &[(Partition, i128)],
out: &mut Vec<(Partition, i128)>,
) {
let (k, nu, beads, base_positive) = (cx.k, cx.nu, cx.beads, cx.base_positive);
if slot == k {
if left == 0 {
if let Some(&(_, c)) = layer.iter().find(|(lambda, _)| lambda == nu) {
let (lambda, positive) = quotient_sign(quot, k, beads);
let signed = if positive == base_positive { c } else { -c };
out.push((lambda, signed));
}
}
return;
}
crate::interrupt::poll();
let remaining_slots = k - slot - 1;
for size in 0..=left {
if remaining_slots == 0 && size != left {
continue;
}
for q in crate::partitions_of(size) {
let next = extend_layer(layer, &q, nu);
if next.is_empty() {
continue;
}
quot.push(q);
sweep_slots(cx, left - size, slot + 1, quot, &next, out);
quot.pop();
}
}
}
fn extend_layer(
layer: &[(Partition, i128)],
q: &Partition,
nu: &Partition,
) -> Vec<(Partition, i128)> {
if q.is_empty() {
return layer.to_vec();
}
let mut acc: std::collections::BTreeMap<Partition, i128> = std::collections::BTreeMap::new();
for (lambda, c) in layer {
let a: Schur<i128> = Schur::monomial(lambda.clone(), *c);
let b: Schur<i128> = Schur::monomial(q.clone(), 1);
for (mu, d) in a.mul(&b).terms() {
if fits_inside(mu, nu) {
*acc.entry(mu.clone()).or_insert(0) += *d;
}
}
}
acc.into_iter().filter(|&(_, c)| c != 0).collect()
}
fn fits_inside(lambda: &Partition, nu: &Partition) -> bool {
lambda.len() <= nu.len() && (0..lambda.len()).all(|i| lambda.part(i) <= nu.part(i))
}
fn quotient_sign(quot: &[Partition], k: u32, beads: u32) -> (Partition, bool) {
let mut betas: Vec<u32> = Vec::with_capacity(quot.len() * beads as usize);
for (i, q) in (0..).zip(quot) {
for j in 0..beads {
let part = if (j as usize) < q.len() {
q.part(j as usize)
} else {
0
};
betas.push(k * (part + beads - 1 - j) + i);
}
}
let inversions = (0..betas.len())
.flat_map(|x| (x + 1..betas.len()).map(move |y| (x, y)))
.filter(|&(x, y)| betas[x] < betas[y])
.count();
let total = k * beads;
let mut sorted = betas;
sorted.sort_unstable_by(|a, b| b.cmp(a));
let parts: Vec<u32> = sorted
.iter()
.zip(0..total)
.map(|(&b, j)| b - (total - 1 - j))
.filter(|&p| p > 0)
.collect();
(Partition::from_sorted(parts), inversions.is_multiple_of(2))
}
pub fn adams<C: Plethystic>(k: u32, g: &Schur<C>) -> Schur<C> {
assert!(k > 0, "p_k[g] needs k ≥ 1");
let mut out = Schur::zero();
for (nu, c) in g.terms() {
crate::interrupt::poll();
let terms: Vec<(Partition, i128)> = if nu.len() == 1 {
adams_one_row::<i128>(k, nu.part(0))
.terms()
.iter()
.map(|(l, v)| (l.clone(), *v))
.collect()
} else {
adams_schur(k, nu)
};
let scale = c.frobenius(k);
for (lambda, v) in terms {
out.add_term(lambda, C::from_i128(v).mul(&scale));
}
}
out
}
fn compositions(m: u32, k: usize, cur: &mut Vec<u32>, emit: &mut impl FnMut(&[u32])) {
if cur.len() + 1 == k {
cur.push(m);
emit(cur);
cur.pop();
return;
}
for a in 0..=m {
cur.push(a);
compositions(m - a, k, cur, emit);
cur.pop();
}
}
fn h_ladder<C: Plethystic>(g: &Schur<C>, upto: u32) -> Vec<Schur<C>> {
let adams: Vec<Schur<C>> = (1..=upto).map(|k| adams(k, g)).collect();
let mut h: Vec<Schur<C>> = vec![Schur::monomial(Partition::default(), C::one())];
for n in 1..=upto {
crate::interrupt::poll();
let mut acc: Schur<C> = Schur::zero();
for k in 1..=n {
acc = acc.add(&adams[(k - 1) as usize].mul(&h[(n - k) as usize]));
}
let mut hn: Schur<C> = Schur::zero();
for (lambda, c) in acc.terms() {
hn.add_term(lambda.clone(), c.div_u128(u128::from(n)));
}
h.push(hn);
}
h
}
pub fn plethysm_via_ladder<C: Plethystic>(f: &Schur<C>, g: &Schur<C>) -> Schur<C> {
let hf: Homogeneous<C> = Homogeneous::from_schur(f);
let upto = hf
.terms()
.keys()
.flat_map(Partition::parts)
.copied()
.max()
.unwrap_or(0);
let ladder = h_ladder::<C>(g, upto);
let mut out = Schur::zero();
for (mu, c) in hf.terms() {
crate::interrupt::poll();
let mut prod: Schur<C> = Schur::monomial(Partition::default(), C::one());
for &part in mu.parts() {
prod = prod.mul(&ladder[part as usize]);
}
out = out.add(&prod.scale(c));
}
out
}
fn scale_parts<C: Plethystic>(g: &PowerSum<C>, n: u32) -> PowerSum<C> {
let mut out = PowerSum::zero();
for (mu, d) in g.terms() {
let scaled = Partition::new(mu.parts().iter().map(|&x| x * n));
out.add_term(scaled, d.frobenius(n));
}
out
}
pub fn plethysm<C: Plethystic>(f: &Schur<C>, g: &Schur<C>) -> Schur<C> {
if takes_the_ladder(f, g) {
return plethysm_via_ladder(f, g);
}
plethysm_via_power_sum(f, g)
}
fn takes_the_ladder<C: Plethystic>(f: &Schur<C>, g: &Schur<C>) -> bool {
let inner_is_one_row = g.terms().keys().all(|nu| nu.len() <= 1);
if inner_is_one_row {
return true;
}
let depth = Homogeneous::<C>::from_schur(f)
.terms()
.keys()
.flat_map(Partition::parts)
.copied()
.max()
.unwrap_or(0);
let inner_size = g.terms().keys().map(Partition::size).max().unwrap_or(0);
depth <= inner_size
}
fn plethysm_via_power_sum<C: Plethystic>(f: &Schur<C>, g: &Schur<C>) -> Schur<C> {
let pf: PowerSum<C> = PowerSum::from_schur(f);
let pg: PowerSum<C> = PowerSum::from_schur(g);
let mut acc = PowerSum::zero();
for (lambda, c) in pf.terms() {
let mut prod: PowerSum<C> = PowerSum::monomial(Partition::default(), C::one());
for &part in lambda.parts() {
crate::interrupt::poll();
prod = prod.mul(&scale_parts(&pg, part));
}
acc = acc.add(&prod.scale(c));
}
acc.to_schur()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::{Rational, Ring};
fn s(v: &[u32]) -> Schur<Rational> {
Schur::monomial(Partition::new(v.iter().copied()), Rational::one())
}
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn classic_plethysms() {
let r = plethysm(&s(&[2]), &s(&[2]));
assert_eq!(r.coeff(&part(&[4])), Rational::one());
assert_eq!(r.coeff(&part(&[2, 2])), Rational::one());
assert_eq!(r.terms().len(), 2);
let r = plethysm(&s(&[1, 1]), &s(&[2]));
assert_eq!(r.coeff(&part(&[3, 1])), Rational::one());
assert_eq!(r.terms().len(), 1);
}
#[test]
fn a_constant_outer_argument_survives_the_ladder() {
let one: Schur<Rational> = Schur::monomial(Partition::default(), Rational::one());
for m in 1..=3u32 {
assert_eq!(
plethysm_via_ladder(&one, &s(&[m])),
one,
"1[s_{m}] is not 1"
);
}
let zero: Schur<Rational> = Schur::zero();
assert_eq!(
plethysm_via_ladder(&zero, &s(&[2])),
zero,
"0[s_2] is not 0"
);
}
#[test]
fn plethysm_identities() {
let g = s(&[2, 1]);
assert_eq!(plethysm(&s(&[1]), &g), g);
assert_eq!(plethysm(&g, &s(&[1])), g);
}
#[test]
fn the_two_routes_are_one_operation() {
let outers: [&[u32]; 8] = [
&[1],
&[2],
&[3],
&[1, 1],
&[2, 1],
&[2, 2],
&[3, 1],
&[2, 1, 1],
];
let inners: [&[u32]; 7] = [&[1], &[2], &[3], &[4], &[2, 1], &[2, 2], &[3, 1]];
for inner in inners {
for outer in outers {
let (f, g) = (s(outer), s(inner));
let ladder = plethysm_via_ladder(&f, &g);
let via_p = plethysm_via_power_sum(&f, &g);
assert_eq!(ladder, via_p, "s{outer:?}[s{inner:?}] differs by route");
}
}
}
#[test]
fn a_sum_as_the_inner_argument_agrees_by_route() {
let mut g: Schur<Rational> = Schur::zero();
g.add_term(part(&[2]), Rational::one());
g.add_term(part(&[1, 1]), Rational::one());
for outer in [&[2u32][..], &[1, 1], &[3], &[2, 1]] {
let f = s(outer);
assert_eq!(
plethysm_via_ladder(&f, &g),
plethysm_via_power_sum(&f, &g),
"s{outer:?}[s_2 + s_{{1,1}}] differs by route"
);
}
let mut d: Schur<Rational> = Schur::zero();
d.add_term(part(&[2]), Rational::one());
d.add_term(part(&[1, 1]), Rational::one().neg());
for outer in [&[2u32][..], &[3], &[2, 1]] {
let f = s(outer);
assert_eq!(
plethysm_via_ladder(&f, &d),
plethysm_via_power_sum(&f, &d),
"s{outer:?}[s_2 − s_{{1,1}}] differs by route"
);
}
}
#[test]
fn the_ladder_reproduces_the_classical_plethysms() {
let r = plethysm_via_ladder(&s(&[2]), &s(&[2]));
assert_eq!(r.coeff(&part(&[4])), Rational::one());
assert_eq!(r.coeff(&part(&[2, 2])), Rational::one());
assert_eq!(r.terms().len(), 2);
let r = plethysm_via_ladder(&s(&[2]), &s(&[3]));
for lambda in [&[6u32][..], &[4, 2]] {
assert_eq!(
r.coeff(&part(lambda)),
Rational::one(),
"s_2[s_3] misses s{lambda:?}"
);
}
assert_eq!(r.terms().len(), 2, "s_2[s_3] is not two terms");
let r = plethysm_via_ladder(&s(&[3]), &s(&[2]));
for lambda in [&[6u32][..], &[4, 2], &[2, 2, 2]] {
assert_eq!(
r.coeff(&part(lambda)),
Rational::one(),
"s_3[s_2] misses s{lambda:?}"
);
}
assert_eq!(r.terms().len(), 3, "s_3[s_2] is not three terms");
}
#[test]
fn degree_is_multiplicative() {
for f in [&[2][..], &[1, 1], &[2, 1]] {
for g in [&[2][..], &[1, 1]] {
let r = plethysm(&s(f), &s(g));
let want = part(f).size() * part(g).size();
assert_eq!(r.degree(), Some(want), "deg s{:?}[s{:?}]", f, g);
}
}
}
}