#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use std::collections::{BTreeMap, HashMap};
use crate::coeff::{QAlgebra, Ring};
use crate::partition::Partition;
use crate::qt::QtPoly;
use crate::sym::{Monomial, PowerSum, Schur, SymFn};
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
struct Cell {
comp: u32,
row: i32,
col: i32,
content: i32,
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct SkewTuple {
cells: Vec<Cell>,
offsets: Vec<i32>,
reading: Vec<u32>,
attack: Vec<(u32, u32)>,
weak: Vec<(u32, u32)>,
strict: Vec<(u32, u32)>,
attack_mask: Vec<u64>,
pred_mask: Vec<u64>,
}
impl SkewTuple {
pub fn from_cells(comps: &[(Vec<(i32, i32)>, i32)]) -> Self {
let mut cells = Vec::new();
let mut offsets = Vec::with_capacity(comps.len());
for (k, (cs, off)) in comps.iter().enumerate() {
offsets.push(*off);
for &(row, col) in cs {
cells.push(Cell {
comp: k as u32,
row,
col,
content: col - row + off,
});
}
}
let n = cells.len();
let mut order: Vec<u32> = (0..n as u32).collect();
order.sort_by_key(|&i| {
let c = cells[i as usize];
(c.content, c.comp, c.row)
});
let mut reading = vec![0u32; n];
for (pos, &i) in order.iter().enumerate() {
reading[i as usize] = pos as u32;
}
assert!(
n <= MAX_CELLS,
"a SkewTuple holds at most {MAX_CELLS} cells, got {n}; this is a \
representation limit, not a mathematical one"
);
let mut attack = Vec::new();
let mut attack_mask = vec![0u64; n];
for a in 0..n {
for b in 0..n {
let (x, y) = (cells[a], cells[b]);
let attacks = (y.content == x.content && x.comp < y.comp)
|| (y.content == x.content + 1 && y.comp < x.comp);
if attacks {
attack.push((a as u32, b as u32));
attack_mask[a] |= 1u64 << b;
}
}
}
let index: HashMap<(u32, i32, i32), u32> = cells
.iter()
.enumerate()
.map(|(i, c)| ((c.comp, c.row, c.col), i as u32))
.collect();
let mut weak = Vec::new();
let mut strict = Vec::new();
let mut pred_mask = vec![0u64; n];
for (i, c) in cells.iter().enumerate() {
if let Some(&j) = index.get(&(c.comp, c.row, c.col + 1)) {
weak.push((i as u32, j));
pred_mask[j as usize] |= 1u64 << i;
}
if let Some(&j) = index.get(&(c.comp, c.row + 1, c.col)) {
strict.push((i as u32, j));
pred_mask[j as usize] |= 1u64 << i;
}
}
SkewTuple {
cells,
offsets,
reading,
attack,
weak,
strict,
attack_mask,
pred_mask,
}
}
pub fn from_skews(skews: &[(Partition, Partition)], offsets: &[i32]) -> Self {
assert_eq!(skews.len(), offsets.len(), "one offset per component");
let comps: Vec<(Vec<(i32, i32)>, i32)> = skews
.iter()
.zip(offsets)
.map(|((outer, inner), &off)| {
assert!(
outer.contains(inner),
"a skew shape needs inner ⊆ outer: {inner} ⊄ {outer}"
);
let cells = (0..outer.len())
.flat_map(|r| (inner.part(r)..outer.part(r)).map(move |c| (r as i32, c as i32)))
.collect();
(cells, off)
})
.collect();
Self::from_cells(&comps)
}
pub fn from_partitions(shapes: &[Partition], offsets: &[i32]) -> Self {
let skews: Vec<(Partition, Partition)> = shapes
.iter()
.map(|s| (s.clone(), Partition::default()))
.collect();
Self::from_skews(&skews, offsets)
}
pub fn quotient(lambda: &Partition, k: u32) -> Option<Self> {
if !lambda.has_empty_k_core(k) {
return None;
}
let shapes = lambda.k_quotient(k);
let offsets = vec![0i32; shapes.len()];
Some(Self::from_partitions(&shapes, &offsets))
}
pub fn from_area(area: &[u32]) -> Self {
let n = area.len();
let mut comps: Vec<(Vec<(i32, i32)>, i32)> = Vec::new();
let mut start = 0usize;
for i in 1..=n {
if i == n || area[i] != area[i - 1] + 1 {
let cells = (start..i).map(|r| ((r - start) as i32, 0i32)).collect();
comps.push((cells, -(area[start] as i32)));
start = i;
}
}
comps.reverse();
Self::from_cells(&comps)
}
pub fn conjugate(&self) -> Self {
let ncomps = self.offsets.len();
let mut comps: Vec<(Vec<(i32, i32)>, i32)> = (0..ncomps)
.map(|k| (Vec::new(), -self.offsets[k]))
.collect();
for c in &self.cells {
comps[c.comp as usize].0.push((c.col, c.row));
}
comps.reverse();
Self::from_cells(&comps)
}
pub fn attacking_pairs(&self) -> usize {
self.attack.len()
}
pub fn size(&self) -> usize {
self.cells.len()
}
pub fn components(&self) -> usize {
self.offsets.len()
}
fn syt_buckets(&self) -> Vec<(u64, Vec<u128>)> {
self.syt_buckets_within(FLAT_TABLE_BUDGET)
}
fn syt_buckets_within(&self, budget: usize) -> Vec<(u64, Vec<u128>)> {
let n = self.cells.len();
if n == 0 {
return vec![(0u64, vec![1u128])];
}
let width = self.attack.len() + 1; let masks = 1usize << (n - 1);
let mut out = if masks.saturating_mul(width) <= budget {
let mut sink = FlatSink {
table: vec![0u128; masks * width],
width,
};
self.walk(n, &mut sink);
sink.table
.chunks(width)
.enumerate()
.filter(|(_, row)| row.iter().any(|&c| c != 0))
.map(|(mask, row)| (mask as u64, row.to_vec()))
.collect()
} else {
let mut sink = MapSink {
buckets: Default::default(),
};
self.walk(n, &mut sink);
sink.buckets.into_iter().collect::<Vec<_>>()
};
out.sort_unstable_by_key(|e| e.0);
out
}
fn walk<S: Sink>(&self, n: usize, sink: &mut S) {
let all = if n == 64 { u64::MAX } else { (1u64 << n) - 1 };
self.walk_rec(1, n, all, 0, 0, 0, 0, sink);
}
#[allow(clippy::too_many_arguments)]
fn walk_rec<S: Sink>(
&self,
step: usize,
n: usize,
all: u64,
assigned: u64,
prev_pos: u32,
inv: u32,
mask: u64,
sink: &mut S,
) {
if step > n {
sink.hit(mask, inv);
return;
}
let mut cand = all & !assigned;
while cand != 0 {
let c = cand.trailing_zeros();
cand &= cand - 1;
let cell = c as usize;
if self.pred_mask[cell] & !assigned != 0 {
continue;
}
let delta = (self.attack_mask[cell] & assigned).count_ones();
let pos = self.reading[cell];
let bit = if step >= 2 && pos < prev_pos {
1u64 << (step - 2)
} else {
0
};
self.walk_rec(
step + 1,
n,
all,
assigned | 1u64 << c,
pos,
inv + delta,
mask | bit,
sink,
);
}
}
fn inv_range(&self) -> (u32, u32) {
if self.cells.is_empty() {
return (0, 0);
}
let mut sink = RangeSink {
lo: u32::MAX,
hi: 0,
};
self.walk(self.cells.len(), &mut sink);
(sink.lo.min(sink.hi), sink.hi)
}
}
trait Sink {
fn hit(&mut self, mask: u64, inv: u32);
}
struct FlatSink {
table: Vec<u128>,
width: usize,
}
impl Sink for FlatSink {
#[inline]
fn hit(&mut self, mask: u64, inv: u32) {
self.table[mask as usize * self.width + inv as usize] += 1;
}
}
const FLAT_TABLE_BUDGET: usize = 1 << 20;
struct MapSink {
buckets: crate::fasthash::Map<u64, Vec<u128>>,
}
impl Sink for MapSink {
fn hit(&mut self, mask: u64, inv: u32) {
let counts = self.buckets.entry(mask).or_default();
if counts.len() <= inv as usize {
counts.resize(inv as usize + 1, 0);
}
counts[inv as usize] += 1;
}
}
struct RangeSink {
lo: u32,
hi: u32,
}
impl Sink for RangeSink {
#[inline]
fn hit(&mut self, _mask: u64, inv: u32) {
self.lo = self.lo.min(inv);
self.hi = self.hi.max(inv);
}
}
fn partial_sum_mask(mu: &Partition) -> u64 {
let mut mask = 0u64;
let mut acc = 0u32;
for &p in mu.parts().iter().take(mu.len().saturating_sub(1)) {
acc += p;
mask |= 1u64 << (acc - 1);
}
mask
}
pub fn llt_g<C: Ring>(nu: &SkewTuple) -> Monomial<QtPoly<C>> {
let buckets = nu.syt_buckets();
let mut out = Monomial::zero();
for mu in crate::partitions_of(nu.size() as u32) {
crate::interrupt::poll();
let allowed = partial_sum_mask(&mu);
let mut poly = QtPoly::zero();
for (mask, counts) in &buckets {
if mask & !allowed != 0 {
continue;
}
for (inv, c) in counts.iter().enumerate() {
if *c != 0 {
poly.add_term(inv as u32, 0, C::from_u128(*c));
}
}
}
out.add_term(mu, poly);
}
out
}
pub fn llt_min_inv(nu: &SkewTuple) -> u32 {
nu.inv_range().0
}
pub fn llt_max_inv(nu: &SkewTuple) -> u32 {
nu.inv_range().1
}
pub fn llt_fundamental<C: Ring>(nu: &SkewTuple) -> Vec<(Vec<u32>, QtPoly<C>)> {
let n = nu.size() as u32;
let mut out = Vec::new();
for (mask, counts) in nu.syt_buckets() {
crate::interrupt::poll();
let mut comp = Vec::new();
let mut prev = 0u32;
for i in 1..n {
if mask >> (i - 1) & 1 == 1 {
comp.push(i - prev);
prev = i;
}
}
if n > 0 {
comp.push(n - prev);
}
let mut poly = QtPoly::zero();
for (inv, c) in counts.iter().enumerate() {
if *c != 0 {
poly.add_term(inv as u32, 0, C::from_u128(*c));
}
}
out.push((comp, poly));
}
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
type Abacus = u128;
const ABACUS_BITS: u32 = 128;
fn abacus_of(lambda: &Partition, rows: usize) -> Abacus {
let conj = lambda.conjugate();
let beta = conj.beta_numbers(rows);
let top = beta.first().copied().unwrap_or(0);
assert!(
top < ABACUS_BITS,
"β-number {top} does not fit a {ABACUS_BITS}-bit abacus"
);
beta.iter().fold(0u128, |acc, &b| acc | 1u128 << b)
}
fn shape_of(beta: Abacus) -> Partition {
let rows = beta.count_ones() as usize;
let mut desc = Vec::with_capacity(rows);
let mut b = beta;
while b != 0 {
let top = ABACUS_BITS - 1 - b.leading_zeros();
desc.push(top);
b &= !(1u128 << top);
}
Partition::from_beta_numbers(&desc).conjugate()
}
fn abacus_contained(beta: Abacus, target: Abacus) -> bool {
debug_assert_eq!(beta.count_ones(), target.count_ones());
let mut d = beta ^ target;
let mut acc = 0i32;
while d != 0 {
let b = ABACUS_BITS - 1 - d.leading_zeros();
d &= !(1u128 << b);
if target >> b & 1 == 1 {
acc += 1;
} else {
acc -= 1;
if acc < 0 {
return false;
}
}
}
true
}
#[derive(Default)]
struct StripScratch {
beads: Vec<u32>,
blocks: Vec<(u32, u32)>,
room: Vec<u32>,
runner_masks: Vec<Abacus>,
runner_k: u32,
}
#[allow(dead_code)]
fn for_each_strip_up(
beta: Abacus,
k: u32,
m: u32,
sc: &mut StripScratch,
visit: &mut impl FnMut(Abacus, u32),
) {
collect_blocks(beta, k, sc);
sc.room.clear();
sc.room.resize(sc.blocks.len() + 1, 0);
for i in (0..sc.blocks.len()).rev() {
sc.room[i] = sc.room[i + 1] + sc.blocks[i].1;
}
strip_rec(beta, k, &sc.beads, &sc.blocks, &sc.room, 0, m, 0, m, visit);
}
fn collect_blocks(beta: Abacus, k: u32, sc: &mut StripScratch) {
if sc.runner_k != k {
sc.runner_masks.clear();
for r in 0..k {
let mut mask: Abacus = 0;
let mut g = r;
while g < ABACUS_BITS {
mask |= 1u128 << g;
g += k;
}
sc.runner_masks.push(mask);
}
sc.runner_k = k;
}
sc.beads.clear();
sc.blocks.clear();
for r in 0..k as usize {
let mut b = beta & sc.runner_masks[r];
let mut start = sc.beads.len() as u32;
let mut len = 0u32;
let mut prev: Option<u32> = None;
while b != 0 {
let g = b.trailing_zeros();
b &= b - 1;
if prev.is_some_and(|p| g != p + k) {
sc.blocks.push((start, len));
start = sc.beads.len() as u32;
len = 0;
}
sc.beads.push(g);
len += 1;
prev = Some(g);
}
if len > 0 {
sc.blocks.push((start, len));
}
}
}
fn for_each_strip_any(
beta: Abacus,
k: u32,
max_w: u32,
sc: &mut StripScratch,
visit: &mut impl FnMut(u32, Abacus, u32),
) {
collect_blocks(beta, k, sc);
strip_any_rec(beta, k, &sc.beads, &sc.blocks, 0, 0, max_w, 0, visit);
}
#[allow(clippy::too_many_arguments)]
fn strip_any_rec(
beta: Abacus,
k: u32,
beads: &[u32],
blocks: &[(u32, u32)],
bi: usize,
w: u32,
max_w: u32,
moved: Abacus,
visit: &mut impl FnMut(u32, Abacus, u32),
) {
if bi == blocks.len() {
if w >= 1 {
let unmoved = beta & !moved;
let shifted = moved << k;
debug_assert_eq!(shifted & unmoved, 0, "a block prefix never collides");
let mut cross = 0u32;
for i in 1..k {
cross += ((moved << i) & unmoved).count_ones();
}
visit(w, unmoved | shifted, (k - 1) * w - cross);
}
return;
}
let (off, len) = blocks[bi];
let top = len.min(max_w - w);
let mut mv = moved;
for j in 0..=top {
if j > 0 {
mv |= 1u128 << beads[(off + len - j) as usize];
}
strip_any_rec(beta, k, beads, blocks, bi + 1, w + j, max_w, mv, visit);
}
}
#[allow(clippy::too_many_arguments)]
#[allow(dead_code)]
fn strip_rec(
beta: Abacus,
k: u32,
beads: &[u32],
blocks: &[(u32, u32)],
room: &[u32],
bi: usize,
remaining: u32,
moved: Abacus,
m: u32,
visit: &mut impl FnMut(Abacus, u32),
) {
if remaining > room[bi] {
return;
}
if bi == blocks.len() {
if remaining == 0 {
let unmoved = beta & !moved;
let shifted = moved << k;
debug_assert_eq!(shifted & unmoved, 0, "a block prefix never collides");
let mut cross = 0u32;
for i in 1..k {
cross += ((moved << i) & unmoved).count_ones();
}
visit(unmoved | shifted, (k - 1) * m - cross);
}
return;
}
let (off, len) = blocks[bi];
let top = len.min(remaining);
let mut mv = moved;
for j in 0..=top {
if j > 0 {
mv |= 1u128 << beads[(off + len - j) as usize];
}
strip_rec(
beta,
k,
beads,
blocks,
room,
bi + 1,
remaining - j,
mv,
m,
visit,
);
}
}
type States<C> = crate::fasthash::Map<Abacus, QtPoly<C>>;
struct RibbonWalk<'a, C: Ring> {
k: u32,
target: Option<Abacus>,
weight: Vec<u32>,
out: HashMap<Partition, Monomial<QtPoly<C>>>,
keep: Option<&'a Partition>,
}
impl<C: Ring> RibbonWalk<'_, C> {
fn step(&mut self, states: &States<C>, remaining: u32, max_w: u32, sc: &mut StripScratch) {
if remaining == 0 {
let weight = Partition::from_sorted(self.weight.clone());
for (state, poly) in states {
let shape = shape_of(*state);
if let Some(keep) = self.keep {
if &shape != keep {
continue;
}
}
self.out
.entry(shape)
.or_insert_with(Monomial::zero)
.add_term(weight.clone(), poly.clone());
}
return;
}
let (k, target) = (self.k, self.target);
let wmax = max_w.min(remaining);
let mut next: Vec<States<C>> = vec![States::default(); wmax as usize + 1];
for (state, poly) in states {
for_each_strip_any(*state, k, wmax, sc, &mut |w, nb, spin| {
if let Some(t) = target {
if !abacus_contained(nb, t) {
return;
}
}
next[w as usize]
.entry(nb)
.or_insert_with(QtPoly::zero)
.add_shifted(poly, (spin, 0), false);
});
}
for w in (1..=wmax).rev() {
if next[w as usize].is_empty() {
continue;
}
self.weight.push(w);
let level = std::mem::take(&mut next[w as usize]);
self.step(&level, remaining - w, w, sc);
self.weight.pop();
}
}
}
fn assert_abacus_fits(top_beta: u32, what: &str) {
assert!(
top_beta < ABACUS_BITS,
"{what} needs β-numbers up to {top_beta}, past this abacus's \
{ABACUS_BITS} bits"
);
}
pub fn abacus_reach(lambda: &Partition, k: u32) -> u32 {
lambda.len() as u32 + lambda.part(0).max(1) + k
}
pub fn abacus_reach_table(n: u32, k: u32) -> u32 {
let size = k * n;
size + size + k
}
pub const ABACUS_REACH_LIMIT: u32 = ABACUS_BITS;
pub const MAX_CELLS: usize = 64;
pub fn free_edges(g: &DecoratedGraph) -> Vec<(u32, u32)> {
let mut free: Vec<(u32, u32)> = g
.weak
.iter()
.map(|&(u, v)| (u.min(v), u.max(v)))
.filter(|e| !g.strict.contains(e))
.collect();
free.sort_unstable();
free.dedup();
free
}
pub const MAX_FREE_EDGES: usize = 32;
pub fn llt_g_lt<C: Ring>(lambda: &Partition, k: u32) -> Monomial<QtPoly<C>> {
assert!(k >= 1, "a ribbon level needs k ≥ 1");
let n = lambda.size();
if !n.is_multiple_of(k) || !lambda.has_empty_k_core(k) {
return Monomial::zero();
}
if n == 0 {
return Monomial::monomial(Partition::default(), <QtPoly<C> as Ring>::one());
}
let rows = lambda.part(0).max(1) as usize;
assert_abacus_fits(
abacus_reach(lambda, k),
&format!("the shape {lambda} at level {k}"),
);
let target = abacus_of(lambda, rows);
let empty = abacus_of(&Partition::default(), rows);
let mut walk = RibbonWalk::<C> {
k,
target: Some(target),
weight: Vec::new(),
out: HashMap::new(),
keep: Some(lambda),
};
let mut start: States<C> = States::default();
start.insert(empty, <QtPoly<C> as Ring>::one());
let r = n / k;
walk.step(&start, r, r, &mut StripScratch::default());
walk.out.remove(lambda).unwrap_or_else(Monomial::zero)
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Grading {
Cospin,
Spin,
}
fn regrade<C: Ring>(f: &Monomial<QtPoly<C>>, how: Grading) -> Monomial<QtPoly<C>> {
let smax = f
.terms()
.values()
.filter_map(|p| p.degrees())
.map(|(a, _)| a)
.max()
.unwrap_or(0);
let mut out = Monomial::zero();
for (mu, p) in f.terms() {
crate::interrupt::poll();
let mut np = QtPoly::zero();
for (&(a, b), c) in p.terms() {
let e = match how {
Grading::Cospin => smax - a,
Grading::Spin => a,
};
assert!(
e % 2 == 0,
"{how:?} of {mu} is half-integral (spin_LT {a}, s* {smax}): this \
shape's grading carries a q^(1/2)"
);
np.add_term(e / 2, b, c.clone());
}
out.add_term(mu.clone(), np);
}
out
}
pub fn llt_gtilde<C: Ring>(lambda: &Partition, k: u32) -> Monomial<QtPoly<C>> {
let raw = llt_g_lt::<C>(lambda, k);
if raw.is_zero() {
return raw;
}
regrade(&raw, Grading::Cospin)
}
pub fn llt_h_tilde<C: Ring>(mu: &Partition, k: u32) -> Monomial<QtPoly<C>> {
llt_gtilde(&scale(mu, k), k)
}
pub fn llt_h<C: Ring>(mu: &Partition, k: u32) -> Monomial<QtPoly<C>> {
let raw = llt_g_lt::<C>(&scale(mu, k), k);
if raw.is_zero() {
return raw;
}
regrade(&raw, Grading::Spin)
}
fn scale(mu: &Partition, k: u32) -> Partition {
Partition::from_sorted(mu.parts().iter().map(|&p| k * p).collect())
}
pub fn llt_h_table<C: Ring>(n: u32, k: u32) -> Vec<(Partition, Monomial<QtPoly<C>>)> {
crate::partitions_of(n)
.into_iter()
.map(|mu| {
let f = llt_h::<C>(&mu, k);
(mu, f)
})
.collect()
}
pub fn monomial_in_llt_h_table<C: Ring>(
n: u32,
k: u32,
) -> Vec<(Partition, BTreeMap<Partition, QtPoly<C>>)> {
h_inverse_and_star::<C>(n, k).0
}
fn h_inverse_and_star<C: Ring>(
n: u32,
k: u32,
) -> (Vec<(Partition, BTreeMap<Partition, QtPoly<C>>)>, Vec<u32>) {
use crate::convert::ToSchur;
let parts = crate::memo::partitions_cached(n);
let index: HashMap<&Partition, usize> = parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let one = <QtPoly<C> as Ring>::one();
let mut in_h: Vec<BTreeMap<usize, QtPoly<C>>> = Vec::with_capacity(parts.len());
let mut star: Vec<u32> = Vec::with_capacity(parts.len());
for (j, mu) in parts.iter().enumerate() {
crate::interrupt::poll();
let h = llt_h::<C>(mu, k);
star.push(
h.terms()
.values()
.filter_map(|p| p.degrees())
.map(|(a, _)| a)
.max()
.unwrap_or(0),
);
let mut acc: BTreeMap<usize, QtPoly<C>> = BTreeMap::new();
acc.insert(j, one.clone());
let mut diagonal = false;
for (lambda, c) in h.to_schur().terms() {
let i = index[lambda];
if i == j {
assert!(
*c == one,
"[s_{mu}] H^({k})_{mu} is not 1; the substitution would divide"
);
diagonal = true;
continue;
}
assert!(
i < j,
"H^({k})_{mu} has s_{lambda}, which does not come before {mu} lexicographically"
);
for (&l, v) in &in_h[i] {
acc.entry(l)
.or_insert_with(QtPoly::zero)
.add_assign(&c.mul(v).neg());
}
}
assert!(diagonal, "H^({k})_{mu} has no s_{mu} term");
acc.retain(|_, v| !v.is_zero());
in_h.push(acc);
}
let rows = parts
.iter()
.map(|nu| {
crate::interrupt::poll();
let mut out: BTreeMap<Partition, QtPoly<C>> = BTreeMap::new();
for (lambda, c) in Monomial::monomial(nu.clone(), one.clone())
.to_schur()
.terms()
{
for (&l, v) in &in_h[index[lambda]] {
out.entry(parts[l].clone())
.or_insert_with(QtPoly::zero)
.add_assign(&c.mul(v));
}
}
out.retain(|_, v| !v.is_zero());
(nu.clone(), out)
})
.collect();
(rows, star)
}
pub fn monomial_in_llt_h_tilde_table<C: Ring>(
n: u32,
k: u32,
) -> Vec<(Partition, u32, BTreeMap<Partition, QtPoly<C>>)> {
let (rows, star) = h_inverse_and_star::<C>(n, k);
let parts = crate::memo::partitions_cached(n);
let index: HashMap<&Partition, usize> = parts.iter().enumerate().map(|(i, p)| (p, i)).collect();
let depth =
|mu: &Partition, p: &QtPoly<C>| star[index[mu]] + p.degrees().map(|(a, _)| a).unwrap_or(0);
rows.into_iter()
.map(|(nu, row)| {
crate::interrupt::poll();
let shift = row.iter().map(|(mu, p)| depth(mu, p)).max().unwrap_or(0);
let out = row
.iter()
.map(|(mu, p)| {
let s = star[index[mu]];
let mut rev = QtPoly::zero();
for (&(a, b), c) in p.terms() {
rev.add_term(shift - s - a, b, c.clone());
}
(mu.clone(), rev)
})
.collect();
(nu, shift, out)
})
.collect()
}
pub fn llt_gtilde_table<C: Ring>(n: u32, k: u32) -> Vec<(Partition, Monomial<QtPoly<C>>)> {
assert!(k >= 1, "a ribbon level needs k ≥ 1");
if n == 0 {
return vec![(
Partition::default(),
Monomial::monomial(Partition::default(), <QtPoly<C> as Ring>::one()),
)];
}
let size = k * n;
let rows = size as usize;
assert_abacus_fits(
abacus_reach_table(n, k),
&format!("every shape of size {size} at level {k}"),
);
let empty = abacus_of(&Partition::default(), rows);
let mut walk = RibbonWalk::<C> {
k,
target: None,
weight: Vec::new(),
out: HashMap::new(),
keep: None,
};
let mut start: States<C> = States::default();
start.insert(empty, <QtPoly<C> as Ring>::one());
walk.step(&start, n, n, &mut StripScratch::default());
let mut out: Vec<(Partition, Monomial<QtPoly<C>>)> = walk
.out
.into_iter()
.map(|(shape, f)| {
let g = regrade(&f, Grading::Cospin);
(shape, g)
})
.collect();
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
pub fn llt_schur<C: Ring>(lambda: &Partition, k: u32) -> Schur<QtPoly<C>> {
use crate::convert::ToSchur;
llt_gtilde::<C>(lambda, k).to_schur()
}
pub fn nabla_e_by_path<C: Ring>(n: u32) -> Vec<(Vec<u32>, Monomial<QtPoly<C>>)> {
let mut out = Vec::new();
for_each_area(n as usize, &mut |area| {
let g = llt_g::<C>(&SkewTuple::from_area(area));
let areasum: u32 = area.iter().sum();
let mut scaled = Monomial::zero();
for (mu, poly) in g.terms() {
scaled.add_term(mu.clone(), poly.shift_t(areasum));
}
out.push((area.to_vec(), scaled));
});
out
}
fn for_each_area(n: usize, visit: &mut impl FnMut(&[u32])) {
fn rec(n: usize, area: &mut Vec<u32>, visit: &mut impl FnMut(&[u32])) {
if area.len() == n {
visit(area);
return;
}
let top = if area.is_empty() {
0
} else {
area[area.len() - 1] + 1
};
for a in 0..=top {
area.push(a);
rec(n, area, visit);
area.pop();
}
}
let mut area = Vec::with_capacity(n);
rec(n, &mut area, visit);
}
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct DecoratedGraph {
n: u32,
weak: Vec<(u32, u32)>,
strict: Vec<(u32, u32)>,
}
impl DecoratedGraph {
pub fn new(n: u32, weak: &[(u32, u32)], strict: &[(u32, u32)]) -> Self {
assert!(
strict.iter().all(|&(u, v)| u < v),
"a strict edge is oriented u < v: κ(u) < κ(v) is the constraint"
);
assert!(
weak.iter().chain(strict).all(|&(u, v)| u < n && v < n),
"edges must land inside 0..n"
);
let unordered = |&(u, v): &(u32, u32)| (u.min(v), u.max(v));
assert!(
weak.iter()
.map(unordered)
.all(|e| !strict.iter().map(unordered).any(|s| s == e)),
"an edge is either weak (counted) or strict (constraining), never both"
);
DecoratedGraph {
n,
weak: weak.to_vec(),
strict: strict.to_vec(),
}
}
pub fn from_area(area: &[u32]) -> Self {
let n = area.len();
let mut weak = Vec::new();
for x in 0..n {
for y in (x + 1)..n {
if area[x] == area[y] {
weak.push((x as u32, y as u32));
} else if area[x] == area[y] + 1 {
weak.push((y as u32, x as u32));
}
}
}
let strict: Vec<(u32, u32)> = (1..n)
.filter(|&i| area[i] == area[i - 1] + 1)
.map(|i| ((i - 1) as u32, i as u32))
.collect();
DecoratedGraph {
n: n as u32,
weak,
strict,
}
}
pub fn unit_interval(area: &[u32]) -> Self {
let n = area.len();
let mut weak = Vec::new();
for i in 0..n {
for j in (i.saturating_sub(area[i] as usize))..i {
weak.push((j as u32, i as u32));
}
}
DecoratedGraph {
n: n as u32,
weak,
strict: Vec::new(),
}
}
pub fn order(&self) -> u32 {
self.n
}
fn for_each_coloring(&self, mu: &Partition, visit: &mut impl FnMut(&[u32])) {
let n = self.n as usize;
let nvals = mu.len();
let mut counts: Vec<u32> = mu.parts().to_vec();
let mut kappa: Vec<u32> = Vec::with_capacity(n);
self.color_rec(n, nvals, &mut counts, &mut kappa, visit);
}
fn color_rec(
&self,
n: usize,
nvals: usize,
counts: &mut [u32],
kappa: &mut Vec<u32>,
visit: &mut impl FnMut(&[u32]),
) {
let v = kappa.len();
if v == n {
visit(kappa);
return;
}
for j in 0..nvals {
if counts[j] == 0 {
continue;
}
let c = j as u32 + 1;
let ok = self
.strict
.iter()
.all(|&(a, b)| b as usize != v || kappa[a as usize] < c);
if !ok {
continue;
}
counts[j] -= 1;
kappa.push(c);
self.color_rec(n, nvals, counts, kappa, visit);
kappa.pop();
counts[j] += 1;
}
}
fn ascents(&self, kappa: &[u32]) -> u32 {
self.weak
.iter()
.filter(|&&(a, b)| kappa[a as usize] < kappa[b as usize])
.count() as u32
}
}
pub fn llt_graph<C: Ring>(g: &DecoratedGraph) -> Monomial<QtPoly<C>> {
let mut out = Monomial::zero();
for mu in crate::partitions_of(g.n) {
let mut poly = QtPoly::zero();
g.for_each_coloring(&mu, &mut |kappa| {
poly.add_term(g.ascents(kappa), 0, C::one());
});
out.add_term(mu, poly);
}
out
}
pub fn chromatic_from_llt<C: QAlgebra>(g: &DecoratedGraph) -> Monomial<QtPoly<C>> {
use crate::convert::{FromSchur, ToSchur};
let n = g.n;
let f: Monomial<QtPoly<C>> = llt_graph(g);
let p: PowerSum<QtPoly<C>> = PowerSum::from_schur(&f.to_schur());
let mut twisted: PowerSum<QtPoly<C>> = PowerSum::zero();
for (rho, c) in p.terms() {
let mut factor = <QtPoly<C> as Ring>::one();
for &r in rho.parts() {
let mut term: QtPoly<C> = QtPoly::term(r, 0, C::one());
term.add_term(0, 0, C::one().neg());
factor = factor.mul(&term);
}
twisted.add_term(rho.clone(), c.mul(&factor));
}
let mut divisor = <QtPoly<C> as Ring>::one();
let mut qm1: QtPoly<C> = QtPoly::term(1, 0, C::one());
qm1.add_term(0, 0, C::one().neg());
for _ in 0..n {
divisor = divisor.mul(&qm1);
}
let mut out: PowerSum<QtPoly<C>> = PowerSum::zero();
for (rho, c) in twisted.terms() {
let q = c
.divide_exact(&divisor)
.expect("(q−1)^n must divide the twisted expansion exactly");
out.add_term(rho.clone(), q);
}
Monomial::from_schur(&out.to_schur())
}
pub fn llt_e_expansion<C: Ring>(g: &DecoratedGraph) -> Vec<(Partition, QtPoly<C>)> {
let n = g.n as usize;
let strict: Vec<(u32, u32)> = g.strict.clone();
let free = free_edges(g);
assert!(
free.len() < MAX_FREE_EDGES,
"the orientation sum is 2^{} terms",
free.len()
);
let mut acc: HashMap<Partition, QtPoly<C>> = HashMap::new();
for mask in 0u32..(1u32 << free.len()) {
let mut adj: Vec<Vec<u32>> = vec![Vec::new(); n];
for &(u, v) in &strict {
adj[u as usize].push(v);
}
let mut asc = 0u32;
for (i, &(u, v)) in free.iter().enumerate() {
if mask >> i & 1 == 1 {
adj[u as usize].push(v);
asc += 1;
}
}
let mut blocks: HashMap<u32, u32> = HashMap::new();
for u in 0..n {
let mut seen = vec![false; n];
let mut stack = vec![u as u32];
seen[u] = true;
let mut best = u as u32;
while let Some(w) = stack.pop() {
best = best.max(w);
for &z in &adj[w as usize] {
if !seen[z as usize] {
seen[z as usize] = true;
stack.push(z);
}
}
}
*blocks.entry(best).or_insert(0) += 1;
}
let lambda = Partition::new(blocks.values().copied());
acc.entry(lambda)
.or_insert_with(QtPoly::zero)
.add_term(asc, 0, C::one());
}
let mut out: Vec<(Partition, QtPoly<C>)> = acc.into_iter().collect();
out.sort_by(|a, b| a.0.cmp(&b.0));
out
}
pub fn htilde_by_llt<C: Ring>(mu: &Partition) -> Monomial<QtPoly<C>> {
let k = mu.part(0);
if k == 0 {
return Monomial::monomial(Partition::default(), <QtPoly<C> as Ring>::one());
}
let conj = mu.conjugate();
let cand: Vec<(u32, u32)> = (1..=k)
.flat_map(|j| (2..=conj.part((j - 1) as usize)).map(move |i| (i, j)))
.collect();
let arm = |(i, j): (u32, u32)| mu.part((i - 1) as usize) - j;
let leg = |(i, j): (u32, u32)| conj.part((j - 1) as usize) - i;
let offset: u32 = cand.iter().map(|&c| arm(c)).sum();
let mut acc: Monomial<QtPoly<C>> = Monomial::zero();
for mask in 0u64..(1u64 << cand.len()) {
let d: Vec<(u32, u32)> = (0..cand.len())
.filter(|i| mask >> i & 1 == 1)
.map(|i| cand[i])
.collect();
let a: u32 = d.iter().map(|&c| arm(c)).sum();
let maj: u32 = d.iter().map(|&c| leg(c) + 1).sum();
let comps: Vec<(Vec<(i32, i32)>, i32)> = (1..=k)
.map(|j| {
let size = conj.part((j - 1) as usize);
let des: Vec<u32> = d
.iter()
.filter(|&&(_, jj)| jj == j)
.map(|&(i, _)| i)
.collect();
(ribbon_from_descents(size, &des), 0)
})
.collect();
let g = llt_g::<C>(&SkewTuple::from_cells(&comps));
for (nu, poly) in g.terms() {
acc.terms_mut()
.entry(nu.clone())
.or_insert_with(<QtPoly<C> as Ring>::zero)
.add_shifted(poly, (offset - a, maj), false);
}
}
acc.terms_mut().retain(|_, c| !c.is_zero());
let divisor: QtPoly<C> = QtPoly::term(offset, 0, C::one());
let mut out = Monomial::zero();
for (nu, poly) in acc.terms() {
out.add_term(
nu.clone(),
poly.divide_exact(&divisor)
.expect("the q-offset must divide out exactly"),
);
}
out
}
fn ribbon_from_descents(size: u32, des: &[u32]) -> Vec<(i32, i32)> {
if size == 0 {
return Vec::new();
}
let mut cells = vec![(1i32, 0i32)];
for c in 2..=size {
let (r, cc) = *cells.last().expect("cells is seeded with the first cell");
if des.contains(&c) {
cells.push((r + 1, cc));
} else {
cells.push((r, cc - 1));
}
}
cells
}
type Wedge = Vec<i32>;
type Straightened<C> = crate::fasthash::Map<Wedge, QtPoly<C>>;
fn neg_v_times<C: Ring>(p: &QtPoly<C>) -> QtPoly<C> {
let mut out = <QtPoly<C> as Ring>::zero();
out.add_shifted(p, (1, 0), true);
out
}
fn v2_minus_one_times<C: Ring>(p: &QtPoly<C>) -> QtPoly<C> {
let mut out = <QtPoly<C> as Ring>::zero();
out.add_shifted(p, (2, 0), false);
out.add_shifted(p, (0, 0), true);
out
}
fn straighten<C: Ring>(w: &mut [i32], coeff: &QtPoly<C>, k: u32, out: &mut Straightened<C>) {
if coeff.is_zero() {
return;
}
for i in 0..w.len().saturating_sub(1) {
if w[i] == w[i + 1] {
return; }
if w[i] < w[i + 1] {
let (l, m) = (w[i], w[i + 1]);
let diff = (m - l) as u32;
w[i] = m;
w[i + 1] = l;
if diff.is_multiple_of(k) {
straighten(w, &coeff.neg(), k, out);
} else {
straighten(w, &neg_v_times(coeff), k, out);
let mut term = v2_minus_one_times(coeff);
let im = diff % k;
let mut a = im;
while 2 * a < diff {
w[i] = m - a as i32;
w[i + 1] = l + a as i32;
straighten(w, &term, k, out);
term = neg_v_times(&term); a = if a.is_multiple_of(k) {
a + im
} else {
a - im + k
};
}
}
w[i] = l;
w[i + 1] = m;
return;
}
}
if let Some(slot) = out.get_mut(&*w) {
slot.add_assign(coeff);
} else {
out.insert(w.to_vec(), coeff.clone());
}
}
fn v_op<C: Ring>(wedges: &Straightened<C>, m: u32, k: u32) -> Straightened<C> {
let mut out: Straightened<C> = Straightened::default();
let mut buf: Wedge = Vec::new();
for (wedge, coeff) in wedges {
buf.clear();
buf.extend_from_slice(wedge);
boson_rec(&mut buf, 0, m as usize, k, coeff, &mut out);
}
out.retain(|_, c| !c.is_zero());
out
}
fn boson_rec<C: Ring>(
buf: &mut [i32],
lo: usize,
m: usize,
k: u32,
coeff: &QtPoly<C>,
out: &mut Straightened<C>,
) {
if m == 0 {
straighten(buf, coeff, k, out);
return;
}
for j in lo..buf.len() {
buf[j] += k as i32;
boson_rec(buf, j, m - 1, k, coeff, out);
buf[j] -= k as i32;
}
}
pub fn llt_kl_column<C: Ring>(lambda: &Partition, k: u32) -> Vec<(Partition, QtPoly<C>)> {
use crate::convert::FromSchur;
assert!(k >= 1, "a ribbon level needs k ≥ 1");
let deg = lambda.size();
if deg == 0 {
return vec![(Partition::default(), <QtPoly<C> as Ring>::one())];
}
let rows = (k * deg) as usize;
let rho: Wedge = (0..rows as i32).rev().collect();
let s: Schur<i64> = Schur::monomial(lambda.clone(), 1);
let h = crate::sym::Homogeneous::from_schur(&s);
let mut acc: HashMap<Wedge, QtPoly<C>> = HashMap::new();
for (nu, c) in h.terms() {
let mut wedges: Straightened<C> = Straightened::default();
wedges.insert(rho.clone(), QtPoly::term(0, 0, C::from_i64(*c)));
for &part in nu.parts() {
wedges = v_op(&wedges, part, k);
}
for (w, cc) in wedges {
acc.entry(w)
.or_insert_with(<QtPoly<C> as Ring>::zero)
.add_assign(&cc);
}
}
let mut out = Vec::new();
for mu in crate::partitions_of(k * deg) {
if mu.len() > rows {
continue;
}
let key: Wedge = (0..rows).map(|j| mu.part(j) as i32 + rho[j]).collect();
if let Some(c) = acc.get(&key) {
if !c.is_zero() {
out.push((mu, c.clone()));
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::convert::{FromSchur, ToSchur};
use crate::sym::Elementary;
type Q = QtPoly<i64>;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
fn q_pow(e: u32) -> Q {
QtPoly::term(e, 0, 1)
}
fn poly(terms: &[(u32, i64)]) -> Q {
let mut p = QtPoly::zero();
for &(e, c) in terms {
p.add_term(e, 0, c);
}
p
}
fn tuple(shapes: &[&[u32]]) -> SkewTuple {
let shapes: Vec<Partition> = shapes.iter().map(|s| part(s)).collect();
let offsets = vec![0i32; shapes.len()];
SkewTuple::from_partitions(&shapes, &offsets)
}
#[test]
fn both_syt_bucket_sinks_agree_up_to_trailing_zeros() {
fn trim(b: Vec<(u64, Vec<u128>)>) -> Vec<(u64, Vec<u128>)> {
b.into_iter()
.map(|(mask, mut counts)| {
while counts.last() == Some(&0) {
counts.pop();
}
(mask, counts)
})
.collect()
}
for shapes in [
&[&[2u32, 1][..], &[2, 1][..]][..],
&[&[3, 2][..], &[2][..]][..],
&[&[2, 2][..], &[2, 1][..], &[1][..]][..],
&[&[3, 1, 1][..]][..],
] {
let nu = tuple(shapes);
assert_eq!(
trim(nu.syt_buckets()),
trim(nu.syt_buckets_within(0)),
"sinks disagree on {shapes:?}"
);
}
}
fn g_direct(nu: &SkewTuple) -> Monomial<Q> {
let n = nu.size();
let mut out = Monomial::zero();
for mu in crate::partitions_of(n as u32) {
let nvals = mu.len();
let mut counts: Vec<u32> = mu.parts().to_vec();
let mut filling: Vec<u32> = Vec::with_capacity(n);
let mut acc = QtPoly::zero();
fill_rec(nu, n, nvals, &mut counts, &mut filling, &mut acc);
out.add_term(mu, acc);
}
out
}
fn fill_rec(
nu: &SkewTuple,
n: usize,
nvals: usize,
counts: &mut [u32],
filling: &mut Vec<u32>,
acc: &mut Q,
) {
let cell = filling.len();
if cell == n {
let inv = nu
.attack
.iter()
.filter(|&&(a, b)| filling[a as usize] > filling[b as usize])
.count() as u32;
acc.add_term(inv, 0, 1);
return;
}
for j in 0..nvals {
if counts[j] == 0 {
continue;
}
let v = j as u32 + 1;
let ok_weak = !nu.weak.iter().any(|&(x, y)| {
let (x, y) = (x as usize, y as usize);
(y == cell && filling[x] > v) || (x == cell && y < cell && v > filling[y])
});
let ok_strict = !nu.strict.iter().any(|&(x, y)| {
let (x, y) = (x as usize, y as usize);
(y == cell && filling[x] >= v) || (x == cell && y < cell && v >= filling[y])
});
if ok_weak && ok_strict {
counts[j] -= 1;
filling.push(v);
fill_rec(nu, n, nvals, counts, filling, acc);
filling.pop();
counts[j] += 1;
}
}
}
fn floored(f: &Monomial<Q>, floor: u32) -> Monomial<Q> {
let divisor = q_pow(floor);
let mut out = Monomial::zero();
for (mu, p) in f.terms() {
out.add_term(mu.clone(), p.divide_exact(&divisor).expect("floor divides"));
}
out
}
#[test]
fn the_convention_gate() {
let g: Monomial<Q> = llt_g(&tuple(&[&[1], &[1]]));
assert_eq!(g.coeff(&part(&[2])), poly(&[(0, 1)]), "m_2");
assert_eq!(g.coeff(&part(&[1, 1])), poly(&[(0, 1), (1, 1)]), "m_11");
assert_eq!(g.terms().len(), 2);
}
#[test]
fn standardization_agrees_with_direct_enumeration() {
let straight: &[&[&[u32]]] = &[
&[&[2], &[1]],
&[&[1, 1], &[1]],
&[&[2, 1], &[1]],
&[&[1], &[1], &[1]],
&[&[2], &[2]],
&[&[2, 1], &[2]],
];
for shapes in straight {
let nu = tuple(shapes);
assert_eq!(llt_g::<i64>(&nu), g_direct(&nu), "{shapes:?}");
}
let skews: &[&[(&[u32], &[u32])]] = &[
&[(&[2, 1], &[1]), (&[1], &[])],
&[(&[2, 2], &[1]), (&[2], &[1])],
];
for sk in skews {
let shapes: Vec<(Partition, Partition)> =
sk.iter().map(|(o, i)| (part(o), part(i))).collect();
let nu = SkewTuple::from_skews(&shapes, &vec![0i32; sk.len()]);
assert_eq!(llt_g::<i64>(&nu), g_direct(&nu), "{sk:?}");
}
}
#[test]
fn content_offsets_are_load_bearing() {
let shapes = [part(&[1]), part(&[1])];
let a: Monomial<Q> = llt_g(&SkewTuple::from_partitions(&shapes, &[0, 0]));
let b: Monomial<Q> = llt_g(&SkewTuple::from_partitions(&shapes, &[0, 5]));
assert_ne!(a, b);
}
#[test]
fn at_q_one_it_is_a_product_of_skew_schurs() {
let cases: &[&[(&[u32], &[u32])]] = &[
&[(&[2, 1], &[]), (&[1], &[])],
&[(&[2, 2], &[1]), (&[2, 1], &[])],
&[(&[3, 1], &[1]), (&[2], &[]), (&[1, 1], &[])],
];
for sk in cases {
let shapes: Vec<(Partition, Partition)> =
sk.iter().map(|(o, i)| (part(o), part(i))).collect();
let nu = SkewTuple::from_skews(&shapes, &vec![0i32; sk.len()]);
let got: Schur<i64> = {
let g: Monomial<Q> = llt_g(&nu);
let mut at_one: Monomial<i64> = Monomial::zero();
for (mu, p) in g.terms() {
at_one.add_term(mu.clone(), p.eval(&1, &1));
}
at_one.to_schur()
};
let mut want: Schur<i64> = Schur::monomial(Partition::default(), 1);
for (o, i) in &shapes {
let mut factor: Schur<i64> = Schur::zero();
for (nu, c) in crate::skew_lr::expand_skew_shared(o, i).iter() {
factor.add_term(nu.clone(), *c as i64);
}
want = want.mul(&factor);
}
assert_eq!(got, want, "{sk:?} at q = 1");
}
}
#[test]
fn the_quotient_dictionary_is_the_floored_tuple() {
let mut floors = 0;
let mut shapes = 0;
for k in 2..=3u32 {
for n in [k, 2 * k, 3 * k] {
for lambda in crate::partitions_of(n) {
let Some(nu) = SkewTuple::quotient(&lambda, k) else {
continue;
};
if nu.size() == 0 {
continue;
}
shapes += 1;
let floor = llt_min_inv(&nu);
if floor > 0 {
floors += 1;
}
let got = floored(&llt_g::<i64>(&nu), floor);
let want: Monomial<Q> = llt_gtilde(&lambda, k);
assert_eq!(got, want, "λ = {lambda}, k = {k}, floor {floor}");
}
}
}
assert!(shapes >= 40, "the sweep shrank to {shapes} shapes");
assert!(
floors > 0,
"no shape in the sweep has a nonzero min-inv floor, so the floor is \
untested — λ = (2,2,2) at k = 2 is the smallest witness"
);
}
#[test]
fn the_min_inv_floor_is_forced() {
let nu = SkewTuple::quotient(&part(&[2, 2, 2]), 2).expect("empty 2-core");
assert_eq!(
part(&[2, 2, 2]).k_quotient(2),
vec![part(&[1]), part(&[1, 1])]
);
assert_eq!(llt_min_inv(&nu), 1);
let flat = SkewTuple::quotient(&part(&[2, 2]), 2).expect("empty 2-core");
assert_eq!(llt_min_inv(&flat), 0);
}
#[test]
fn tuples_lose_absolute_spin() {
let lambda = part(&[1, 1, 1, 1]);
let raw: Monomial<Q> = llt_g_lt(&lambda, 2);
let smax = raw
.terms()
.values()
.filter_map(|p| p.degrees())
.map(|(a, _)| a)
.max()
.unwrap();
assert_eq!(smax, 2, "spin_LT of the one tableau, i.e. s* = 1");
let nu = SkewTuple::quotient(&lambda, 2).unwrap();
assert_eq!(llt_min_inv(&nu), llt_max_inv(&nu));
}
#[test]
fn llt_example_68i() {
let g: Monomial<Q> = llt_gtilde(&part(&[3, 3, 3, 2, 1]), 3);
assert_eq!(g.coeff(&part(&[3, 1])), poly(&[(0, 1)]));
assert_eq!(g.coeff(&part(&[2, 2])), poly(&[(0, 1), (1, 1)]));
assert_eq!(g.coeff(&part(&[2, 1, 1])), poly(&[(0, 2), (1, 2), (2, 1)]));
assert_eq!(
g.coeff(&part(&[1, 1, 1, 1])),
poly(&[(0, 3), (1, 5), (2, 3), (3, 1)])
);
assert_eq!(g.terms().len(), 4);
let s = g.to_schur();
assert_eq!(s.coeff(&part(&[3, 1])), poly(&[(0, 1)]));
assert_eq!(s.coeff(&part(&[2, 2])), poly(&[(1, 1)]));
assert_eq!(s.coeff(&part(&[2, 1, 1])), poly(&[(1, 1), (2, 1)]));
assert_eq!(s.coeff(&part(&[1, 1, 1, 1])), poly(&[(3, 1)]));
assert_eq!(s.terms().len(), 4);
}
#[test]
fn llt_example_68ii() {
let h: Monomial<Q> = llt_h(&part(&[3, 2, 1, 1]), 2);
let s = h.to_schur();
let want: &[(&[u32], &[(u32, i64)])] = &[
(&[3, 2, 1, 1], &[(0, 1)]),
(&[3, 2, 2], &[(1, 1)]),
(&[3, 3, 1], &[(1, 1)]),
(&[4, 1, 1, 1], &[(1, 1)]),
(&[4, 2, 1], &[(1, 1), (2, 1)]),
(&[4, 3], &[(2, 1)]),
(&[5, 1, 1], &[(2, 1)]),
(&[5, 2], &[(3, 1)]),
];
for (nu, terms) in want {
assert_eq!(s.coeff(&part(nu)), poly(terms), "s_{nu:?}");
}
assert_eq!(s.terms().len(), want.len());
}
#[test]
fn lt_example_41() {
let g: Monomial<Q> = llt_g_lt(&part(&[3, 3, 3, 2, 1]), 3);
let s = g.to_schur();
assert_eq!(s.coeff(&part(&[3, 1])), poly(&[(7, 1)]));
assert_eq!(s.coeff(&part(&[2, 2])), poly(&[(5, 1)]));
assert_eq!(s.coeff(&part(&[2, 1, 1])), poly(&[(3, 1), (5, 1)]));
assert_eq!(s.coeff(&part(&[1, 1, 1, 1])), poly(&[(1, 1)]));
}
#[test]
fn level_one_is_the_schur_function() {
for n in 0..=6u32 {
for lambda in crate::partitions_of(n) {
let got: Schur<Q> = llt_schur(&lambda, 1);
let want: Schur<Q> = Schur::monomial(lambda.clone(), <Q as Ring>::one());
assert_eq!(got, want, "G̃^(1)_{lambda}");
}
}
}
#[test]
fn h_is_the_cospin_flip() {
for k in 2..=3u32 {
for n in 0..=4u32 {
for mu in crate::partitions_of(n) {
let cos: Monomial<Q> = llt_h_tilde(&mu, k);
let h: Monomial<Q> = llt_h(&mu, k);
let sstar = cos
.terms()
.values()
.filter_map(|p| p.degrees())
.map(|(a, _)| a)
.max()
.unwrap_or(0);
let mut flipped: Monomial<Q> = Monomial::zero();
for (nu, p) in cos.terms() {
let mut np = QtPoly::zero();
for (&(a, b), c) in p.terms() {
np.add_term(sstar - a, b, *c);
}
flipped.add_term(nu.clone(), np);
}
assert_eq!(flipped, h, "H^({k})_{mu} = q^s* H̃(1/q)");
}
}
}
}
#[test]
fn large_level_is_hall_littlewood() {
for n in 0..=4u32 {
for mu in crate::partitions_of(n) {
let k = mu.len().max(1) as u32;
let got: Schur<Q> = llt_h::<i64>(&mu, k).to_schur();
let want_t: Schur<Q> = crate::hl::hall_littlewood(&mu);
let mut want: Schur<Q> = Schur::zero();
for (nu, p) in want_t.terms() {
let mut np = QtPoly::zero();
for (&(a, b), c) in p.terms() {
assert_eq!(a, 0, "Hall–Littlewood lives in t alone");
np.add_term(b, 0, *c);
}
want.add_term(nu.clone(), np);
}
assert_eq!(got, want, "H^({k})_{mu} vs Q'_{mu}");
}
}
}
#[test]
fn the_inverse_table_undoes_the_h_table() {
for k in 1..=4u32 {
for n in 0..=6u32 {
let h: HashMap<Partition, Monomial<Q>> =
llt_h_table::<i64>(n, k).into_iter().collect();
for (nu, row) in monomial_in_llt_h_table::<i64>(n, k) {
let mut back: Monomial<Q> = Monomial::zero();
for (mu, c) in &row {
for (lambda, v) in h[mu].terms() {
back.add_term(lambda.clone(), c.mul(v));
}
}
let want = Monomial::monomial(nu.clone(), <Q as Ring>::one());
assert_eq!(back, want, "m_{nu} at k={k}");
}
}
}
}
#[test]
fn the_inverse_at_large_level_is_hall_littlewood() {
for n in 1..=5u32 {
for (nu, got) in monomial_in_llt_h_table::<i64>(n, n) {
let s: Schur<Q> =
Monomial::<Q>::monomial(nu.clone(), <Q as Ring>::one()).to_schur();
let want: BTreeMap<Partition, Q> = crate::hl::schur_to_hall_littlewood_qp(&s)
.into_iter()
.map(|(mu, p)| {
let mut np = QtPoly::zero();
for (&(a, b), c) in p.terms() {
assert_eq!(a, 0, "Hall–Littlewood lives in t alone");
np.add_term(b, 0, *c);
}
(mu, np)
})
.collect();
assert_eq!(got, want, "m_{nu} at k={n}");
}
}
}
#[test]
fn the_cospin_inverse_table_undoes_the_h_tilde_table() {
for k in 1..=4u32 {
for n in 1..=6u32 {
let h: HashMap<Partition, Monomial<Q>> = crate::partitions_of(n)
.into_iter()
.map(|mu| {
let f = llt_h_tilde::<i64>(&mu, k);
(mu, f)
})
.collect();
for (nu, shift, row) in monomial_in_llt_h_tilde_table::<i64>(n, k) {
let mut back: Monomial<Q> = Monomial::zero();
for (mu, c) in &row {
for (lambda, v) in h[mu].terms() {
back.add_term(lambda.clone(), c.mul(v));
}
}
let want =
Monomial::monomial(nu.clone(), QtPoly::term(shift, 0, <i64>::from(1u8)));
assert_eq!(back, want, "m_{nu} at k={k}");
assert!(
row.values().any(|p| p.terms().any(|(&(a, _), _)| a == 0)),
"the row at {nu}, k={k} is divisible by q: the shift is not minimal"
);
}
}
}
}
#[test]
fn omega_duality() {
for shapes in [
&[&[1u32][..], &[1]][..],
&[&[2], &[1]],
&[&[2, 1], &[1]],
&[&[2], &[2]],
] {
let nu = tuple(shapes);
let a = nu.attacking_pairs() as u32;
let lhs: Schur<Q> = llt_g::<i64>(&nu.conjugate()).to_schur();
let g: Schur<Q> = llt_g::<i64>(&nu).to_schur();
let mut rhs: Schur<Q> = Schur::zero();
for (lambda, p) in g.terms() {
let mut np = QtPoly::zero();
for (&(e, b), c) in p.terms() {
assert!(e <= a, "the flip must stay polynomial");
np.add_term(a - e, b, *c);
}
rhs.add_term(lambda.conjugate(), np);
}
assert_eq!(lhs, rhs, "{shapes:?}");
}
}
#[test]
fn the_three_vertical_strip_models_agree() {
for n in 0..=6usize {
for_each_area(n, &mut |area| {
let from_tuple: Monomial<Q> = llt_g(&SkewTuple::from_area(area));
let from_graph: Monomial<Q> = llt_graph(&DecoratedGraph::from_area(area));
assert_eq!(from_tuple, from_graph, "area {area:?}");
assert_eq!(from_tuple, dinv_model(area), "area {area:?}");
});
}
}
fn dinv_model(area: &[u32]) -> Monomial<Q> {
let n = area.len();
let mut out = Monomial::zero();
for mu in crate::partitions_of(n as u32) {
let nvals = mu.len();
let mut counts: Vec<u32> = mu.parts().to_vec();
let mut labels: Vec<u32> = Vec::with_capacity(n);
let mut acc = QtPoly::zero();
label_rec(area, nvals, &mut counts, &mut labels, &mut acc);
out.add_term(mu, acc);
}
out
}
fn label_rec(
area: &[u32],
nvals: usize,
counts: &mut [u32],
labels: &mut Vec<u32>,
acc: &mut Q,
) {
let i = labels.len();
if i == area.len() {
let mut dinv = 0u32;
for x in 0..area.len() {
for y in (x + 1)..area.len() {
if (area[x] == area[y] && labels[x] < labels[y])
|| (area[x] == area[y] + 1 && labels[x] > labels[y])
{
dinv += 1;
}
}
}
acc.add_term(dinv, 0, 1);
return;
}
let rise = i > 0 && area[i] == area[i - 1] + 1;
for j in 0..nvals {
if counts[j] == 0 {
continue;
}
let v = j as u32 + 1;
if rise && v <= labels[i - 1] {
continue;
}
counts[j] -= 1;
labels.push(v);
label_rec(area, nvals, counts, labels, acc);
labels.pop();
counts[j] += 1;
}
}
#[test]
fn the_shuffle_refinement_is_nabla_e() {
for n in 0..=5u32 {
let mut total: Monomial<QtPoly<Rational>> = Monomial::zero();
for (_, g) in nabla_e_by_path::<Rational>(n) {
total = total.add(&g);
}
let want = crate::deltaop::nabla_e::<Rational>(n);
assert_eq!(total.to_schur(), want, "∇e_{n} by path");
}
}
#[test]
fn every_path_piece_is_schur_positive() {
for n in 0..=5u32 {
for (area, g) in nabla_e_by_path::<i64>(n) {
for (lambda, p) in g.to_schur().terms() {
for (_, c) in p.terms() {
assert!(
*c >= 0,
"negative Schur coefficient {c} on s_{lambda} for area \
{area:?}: report this, do not repair it"
);
}
}
}
}
}
#[test]
fn the_chromatic_bridge_is_shareshian_wachs() {
for n in 0..=5usize {
for_each_area(n, &mut |area| {
let g = DecoratedGraph::unit_interval(area);
let got: Monomial<QtPoly<Rational>> = chromatic_from_llt(&g);
assert_eq!(got, proper_colorings(&g), "area {area:?}");
});
}
}
#[test]
fn isolated_vertices_survive() {
let g = DecoratedGraph::new(2, &[], &[]);
let x: Monomial<QtPoly<Rational>> = chromatic_from_llt(&g);
assert_eq!(x.coeff(&part(&[2])), <QtPoly<Rational> as Ring>::one());
assert_eq!(
x.coeff(&part(&[1, 1]))
.eval(&Rational::from_int(1), &Rational::from_int(1)),
Rational::from_int(2)
);
}
fn proper_colorings(g: &DecoratedGraph) -> Monomial<QtPoly<Rational>> {
let n = g.n as usize;
let edges: Vec<(u32, u32)> = g.weak.iter().map(|&(u, v)| (u.min(v), u.max(v))).collect();
let mut out = Monomial::zero();
for mu in crate::partitions_of(g.n) {
let nvals = mu.len();
let mut counts: Vec<u32> = mu.parts().to_vec();
let mut kappa: Vec<u32> = Vec::with_capacity(n);
let mut acc: QtPoly<Rational> = QtPoly::zero();
proper_rec(n, nvals, &edges, &mut counts, &mut kappa, &mut acc);
out.add_term(mu, acc);
}
out
}
fn proper_rec(
n: usize,
nvals: usize,
edges: &[(u32, u32)],
counts: &mut [u32],
kappa: &mut Vec<u32>,
acc: &mut QtPoly<Rational>,
) {
let v = kappa.len();
if v == n {
let asc = edges
.iter()
.filter(|&&(a, b)| kappa[a as usize] < kappa[b as usize])
.count() as u32;
acc.add_term(asc, 0, Rational::from_int(1));
return;
}
for j in 0..nvals {
if counts[j] == 0 {
continue;
}
let c = j as u32 + 1;
if edges
.iter()
.any(|&(a, b)| b as usize == v && kappa[a as usize] == c)
{
continue;
}
counts[j] -= 1;
kappa.push(c);
proper_rec(n, nvals, edges, counts, kappa, acc);
kappa.pop();
counts[j] += 1;
}
}
fn shift_q<C: Ring>(p: &QtPoly<C>, d: i64) -> QtPoly<C> {
let mut out = QtPoly::zero();
for (&(a, b), c) in p.terms() {
let mut binom: i128 = 1;
for i in (0..=a).rev() {
let scale = binom * (d as i128).pow(a - i);
out.add_term(i, b, C::from_i128(scale).mul(c));
if i > 0 {
binom = binom * i as i128 / (a - i + 1) as i128;
}
}
}
out
}
#[test]
fn the_as_orientation_formula_reproduces_g() {
for n in 0..=5usize {
for_each_area(n, &mut |area| {
let g = DecoratedGraph::unit_interval(area);
let e = llt_e_expansion::<i64>(&g);
for (lambda, p) in &e {
for (_, c) in p.terms() {
assert!(*c >= 0, "[DA] positivity fails on e_{lambda}: our bug");
}
}
let mut got: Elementary<Q> = Elementary::zero();
for (lambda, p) in e {
got.add_term(lambda, shift_q(&p, -1));
}
let want: Elementary<Q> = Elementary::from_schur(&llt_graph::<i64>(&g).to_schur());
assert_eq!(got, want, "area {area:?}");
});
}
}
#[test]
fn published_schroder_fixtures() {
let g = graph_from_word("nndee");
let s = llt_graph::<i64>(&g).to_schur();
assert_eq!(s.coeff(&part(&[1, 1, 1])), poly(&[(2, 1)]), "[AS] Ex 6.1");
assert_eq!(s.coeff(&part(&[2, 1])), poly(&[(1, 1)]), "[AS] Ex 6.1");
assert_eq!(s.terms().len(), 2);
let g = graph_from_word("ndndee");
let e: Elementary<Q> = Elementary::from_schur(&llt_graph::<i64>(&g).to_schur());
assert_eq!(e.coeff(&part(&[3, 1])), poly(&[(1, 1)]), "[DA] Ex 5.6");
assert_eq!(
e.coeff(&part(&[4])),
poly(&[(1, -1), (2, 1)]),
"[DA] Ex 5.6"
);
assert_eq!(e.terms().len(), 2);
}
fn graph_from_word(word: &str) -> DecoratedGraph {
let (mut x, mut y) = (0i64, 0i64);
let mut colheight: Vec<i64> = Vec::new();
let mut diag: Vec<(usize, usize)> = Vec::new();
for st in word.chars() {
match st {
'n' => y += 1,
'e' => {
colheight.push(y);
x += 1;
}
'd' => {
colheight.push(y + 1);
x += 1;
y += 1;
diag.push((x as usize, y as usize));
}
c => panic!("unexpected step {c}"),
}
}
let n = x as usize;
let mut weak = Vec::new();
for u in 1..=n {
for v in (u + 1)..=n {
if (v as i64) <= colheight[u - 1] {
weak.push(((u - 1) as u32, (v - 1) as u32));
}
}
}
let strict: Vec<(u32, u32)> = diag
.iter()
.map(|&(u, v)| ((u - 1) as u32, (v - 1) as u32))
.collect();
weak.retain(|e| !strict.contains(e));
DecoratedGraph::new(n as u32, &weak, &strict)
}
#[test]
fn the_hhl_assembly_is_htilde() {
for n in 0..=4u32 {
for mu in crate::partitions_of(n) {
let got = htilde_by_llt::<i64>(&mu).to_schur();
let want = crate::qtkostka::macdonald_ht::<i64>(&mu);
assert_eq!(got, want, "H̃_{mu} by LLT decomposition");
}
}
}
#[test]
fn fock_straightening_is_the_ribbon_column_at_q_eq_minus_v() {
let mut multi = 0;
for (k, top) in [(2u32, 4u32), (3, 3)] {
for lambda in (1..=top).flat_map(crate::partitions_of) {
let got: HashMap<Partition, Q> =
llt_kl_column::<i64>(&lambda, k).into_iter().collect();
for mu in crate::partitions_of(k * lambda.size()) {
let s: Schur<Q> = llt_g_lt::<i64>(&mu, k).to_schur();
let c = s.coeff(&lambda);
if c.terms().count() > 1 {
multi += 1;
}
let mut want = QtPoly::zero();
for (&(a, b), cc) in c.terms() {
let v = if a % 2 == 1 { cc.neg() } else { *cc };
want.add_term(a, b, v);
}
let have = got.get(&mu).cloned().unwrap_or_else(QtPoly::zero);
assert_eq!(have, want, "c^{lambda}_{mu} at k={k}, q = −v");
}
}
}
assert!(
multi > 0,
"no multi-term KL entry in range: the q = −v dictionary is untested"
);
}
#[test]
fn strip_blocks_agree_with_naive_subsets() {
for k in 2..=4u32 {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let rows = lambda.part(0).max(1) as usize + 4;
if lambda.len() + rows + 4 >= 128 {
continue;
}
let beta = abacus_of(&lambda, rows);
for m in 0..=4u32 {
let mut got: Vec<(Abacus, u32)> = Vec::new();
let mut sc = StripScratch::default();
for_each_strip_up(beta, k, m, &mut sc, &mut |nb, spin| {
got.push((nb, spin))
});
got.sort_unstable();
let mut want = naive_strips(beta, rows, k, m);
want.sort_unstable();
assert_eq!(got, want, "λ={lambda} k={k} m={m} rows={rows}");
}
}
}
}
}
#[test]
fn abacus_containment_is_partition_containment() {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let rows = lambda.part(0).max(1) as usize + 3;
let target = abacus_of(&lambda, rows);
for m in 0..=n {
for nu in crate::partitions_of(m) {
if nu.len() > rows || nu.part(0) as usize > rows {
continue;
}
let beta = abacus_of(&nu, rows);
assert_eq!(
abacus_contained(beta, target),
lambda.contains(&nu),
"{nu} ⊆ {lambda}?"
);
}
}
}
}
}
#[test]
fn the_all_weights_walk_agrees_with_the_fixed_weight_one() {
for k in 1..=4u32 {
for n in 0..=8u32 {
for lambda in crate::partitions_of(n) {
let rows = lambda.part(0).max(1) as usize + 4;
if lambda.len() + rows + 4 >= 128 {
continue;
}
let beta = abacus_of(&lambda, rows);
let max_w = 5u32;
let mut sc = StripScratch::default();
let mut got: Vec<(u32, Abacus, u32)> = Vec::new();
for_each_strip_any(beta, k, max_w, &mut sc, &mut |w, nb, spin| {
got.push((w, nb, spin))
});
got.sort_unstable();
let mut want: Vec<(u32, Abacus, u32)> = Vec::new();
for m in 1..=max_w {
for_each_strip_up(beta, k, m, &mut sc, &mut |nb, spin| {
want.push((m, nb, spin))
});
}
want.sort_unstable();
assert_eq!(got, want, "λ={lambda} k={k} rows={rows}");
}
}
}
}
fn naive_strips(beta: Abacus, rows: usize, k: u32, m: u32) -> Vec<(Abacus, u32)> {
let beads: Vec<u32> = (0..128u32).filter(|&b| beta >> b & 1 == 1).collect();
assert_eq!(beads.len(), rows);
let mut out = Vec::new();
for mask in 0u64..(1u64 << rows) {
if (mask.count_ones()) != m {
continue;
}
let mut moved: Abacus = 0;
for (i, &b) in beads.iter().enumerate() {
if mask >> i & 1 == 1 {
moved |= 1u128 << b;
}
}
let unmoved = beta & !moved;
let shifted = moved << k;
if shifted & unmoved != 0 {
continue;
}
let mut cross = 0u32;
for i in 1..k {
cross += ((moved << i) & unmoved).count_ones();
}
out.push((unmoved | shifted, (k - 1) * m - cross));
}
out
}
#[test]
fn the_two_walks_agree() {
for k in 1..=3u32 {
for n in 0..=4u32 {
let table: Vec<(Partition, Monomial<Q>)> = llt_gtilde_table(n, k);
for (lambda, got) in &table {
assert_eq!(*got, llt_gtilde::<i64>(lambda, k), "λ={lambda} k={k}");
}
for lambda in crate::partitions_of(k * n) {
if lambda.has_empty_k_core(k) {
assert!(
table.iter().any(|(l, _)| *l == lambda),
"{lambda} missing from the k={k} degree-{n} table"
);
}
}
}
}
}
#[test]
fn h_table_agrees_with_individual_calls() {
for k in 1..=3u32 {
for n in 0..=4u32 {
for (mu, got) in llt_h_table::<i64>(n, k) {
assert_eq!(got, llt_h::<i64>(&mu, k), "H^({k})_{mu}");
}
}
}
}
#[test]
fn fixed_width_ladders_agree() {
for k in 1..=3u32 {
for n in 0..=4u32 {
for mu in crate::partitions_of(n) {
let narrow: Monomial<QtPoly<i64>> = llt_h(&mu, k);
let wide: Monomial<QtPoly<i128>> = llt_h(&mu, k);
assert_eq!(narrow.terms().len(), wide.terms().len(), "{mu} at k={k}");
for (nu, p) in narrow.terms() {
let w = wide.coeff(nu);
for (&(a, b), c) in p.terms() {
assert_eq!(i128::from(*c), w.coeff(a, b), "{mu}/{nu} at k={k}");
}
}
}
}
}
}
#[test]
fn the_fundamental_expansion_refines_the_monomial_one() {
for shapes in [
&[&[2u32][..], &[1]][..],
&[&[1], &[1], &[1]],
&[&[2, 1], &[2]],
] {
let nu = tuple(shapes);
let f = llt_fundamental::<i64>(&nu);
let m: Monomial<Q> = llt_g(&nu);
let total: u32 = f.iter().map(|(c, _)| c.iter().sum::<u32>()).max().unwrap();
assert_eq!(total, nu.size() as u32, "compositions of n");
for mu in crate::partitions_of(nu.size() as u32) {
let allowed = partial_sum_mask(&mu);
let mut acc = QtPoly::zero();
for (comp, p) in &f {
let mut mask = 0u64;
let mut acc_s = 0u32;
for &c in &comp[..comp.len() - 1] {
acc_s += c;
mask |= 1u64 << (acc_s - 1);
}
if mask & !allowed == 0 {
acc.add_assign(p);
}
}
assert_eq!(acc, m.coeff(&mu), "[m_{mu}]");
}
}
}
}