#![allow(
clippy::cast_possible_truncation,
clippy::cast_sign_loss,
clippy::cast_possible_wrap
)]
use crate::coeff::Ring;
use crate::partition::Partition;
use crate::qt::QtPoly;
use crate::sym::{Monomial, SymFn};
fn for_each_area(n: usize, visit: &mut impl FnMut(&[u32])) {
let mut area = Vec::with_capacity(n);
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();
}
}
rec(n, &mut area, visit);
debug_assert!(area.is_empty());
}
fn for_each_labeling(
area: &[u32],
counts: &mut [u32],
labels: &mut Vec<u32>,
visit: &mut impl FnMut(&[u32]),
) {
let i = labels.len();
if i == area.len() {
visit(labels);
return;
}
let rise = i > 0 && area[i] == area[i - 1] + 1;
for j in 0..counts.len() {
if counts[j] == 0 {
continue;
}
let label = j as u32 + 1;
if rise && label <= labels[i - 1] {
continue;
}
counts[j] -= 1;
labels.push(label);
for_each_labeling(area, counts, labels, visit);
labels.pop();
counts[j] += 1;
}
}
fn d_row(area: &[u32], labels: &[u32], i: usize) -> u32 {
let mut d = 0;
for j in (i + 1)..area.len() {
if (area[i] == area[j] && labels[i] < labels[j])
|| (area[i] == area[j] + 1 && labels[i] > labels[j])
{
d += 1;
}
}
d
}
fn choose_all(weights: &[u32], top: usize) -> Vec<Vec<(u32, i128)>> {
let top = top.min(weights.len());
let span: u32 = weights.iter().sum();
let width = span as usize + 1;
let mut dp = vec![0i128; (top + 1) * width];
dp[0] = 1;
for &w in weights {
for j in (0..top).rev() {
for s in (0..width).rev() {
let c = dp[j * width + s];
if c != 0 {
dp[(j + 1) * width + s + w as usize] += c;
}
}
}
}
(0..=top)
.map(|j| {
(0..width)
.filter_map(|s| {
let c = dp[j * width + s];
(c != 0).then_some((s as u32, c))
})
.collect()
})
.collect()
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side {
Rise,
Valley,
}
pub fn ladder<C: Ring>(n: u32, which: Side) -> Vec<Monomial<QtPoly<C>>> {
if n == 0 {
return Vec::new();
}
if which == Side::Rise {
return rise_ladder_via_llt(n);
}
let mut out = vec![Monomial::zero(); n as usize];
for mu in crate::partitions_of(n) {
for (k, c) in ladder_at_content::<C>(&mu, which).into_iter().enumerate() {
if !c.is_empty() {
out[k].add_term(mu.clone(), c);
}
}
}
out
}
fn rise_ladder_via_llt<C: Ring>(n: u32) -> Vec<Monomial<QtPoly<C>>> {
let nn = n as usize;
let mut out = vec![Monomial::zero(); nn];
for_each_area(nn, &mut |area| {
let g: Monomial<QtPoly<C>> = crate::llt::llt_g(&crate::llt::SkewTuple::from_area(area));
let areasum: u32 = area.iter().sum();
let rises: Vec<u32> = (1..nn)
.filter(|&i| area[i] == area[i - 1] + 1)
.map(|i| area[i])
.collect();
for (j, row) in choose_all(&rises, nn - 1).into_iter().enumerate() {
let k = nn - 1 - j;
for (sub, mult) in row {
let scale = C::from_i128(mult);
for (mu, poly) in g.terms() {
out[k]
.terms_mut()
.entry(mu.clone())
.or_insert_with(<QtPoly<C> as Ring>::zero)
.add_scaled_shifted(poly, (0, areasum - sub), &scale);
}
}
}
});
for slot in &mut out {
slot.terms_mut().retain(|_, c| !c.is_zero());
}
out
}
pub fn ladder_at_content<C: Ring>(mu: &Partition, which: Side) -> Vec<QtPoly<C>> {
let n = mu.size() as usize;
assert!(n > 0, "the Delta conjecture asks for n > 0");
let offset = match which {
Side::Rise => 0,
Side::Valley => n as u32,
};
let mut counts: Vec<u32> = mu.parts().to_vec();
let mut acc: Vec<QtPoly<C>> = vec![QtPoly::zero(); n];
let mut labels: Vec<u32> = Vec::with_capacity(n);
let mut d: Vec<u32> = vec![0; n];
for_each_area(n, &mut |area| {
let areasum: u32 = area.iter().sum();
for_each_labeling(area, &mut counts, &mut labels, &mut |labels| {
for (i, slot) in d.iter_mut().enumerate() {
*slot = d_row(area, labels, i);
}
let dinv: u32 = d.iter().sum();
let weights: Vec<u32> = match which {
Side::Rise => (1..n)
.filter(|&i| area[i] == area[i - 1] + 1)
.map(|i| area[i])
.collect(),
Side::Valley => (1..n)
.filter(|&i| {
area[i] < area[i - 1]
|| (area[i] == area[i - 1] && labels[i] > labels[i - 1])
})
.map(|i| d[i] + 1)
.collect(),
};
for (j, row) in choose_all(&weights, n - 1).into_iter().enumerate() {
let k = n - 1 - j;
for (sub, mult) in row {
let (a, b) = match which {
Side::Rise => (dinv, areasum - sub),
Side::Valley => (dinv + offset - sub, areasum),
};
acc[k].add_term(a, b, C::from_i128(mult));
}
}
});
});
if offset == 0 {
return acc;
}
let divisor: QtPoly<C> = QtPoly::term(offset, 0, C::one());
acc.into_iter()
.map(|f| {
f.divide_exact(&divisor)
.expect("the q-offset must divide out exactly")
})
.collect()
}
pub fn side<C: Ring>(n: u32, k: u32, which: Side) -> Monomial<QtPoly<C>> {
assert!(k < n, "the Delta conjecture asks for k < n");
ladder::<C>(n, which).swap_remove(k as usize)
}
pub fn side_at_content<C: Ring>(mu: &Partition, k: u32, which: Side) -> QtPoly<C> {
assert!(k < mu.size(), "the Delta conjecture asks for k < n");
ladder_at_content::<C>(mu, which).swap_remove(k as usize)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::coeff::Rational;
use crate::convert::ToSchur;
fn part(v: &[u32]) -> Partition {
Partition::new(v.iter().copied())
}
#[test]
fn distinct_labelings_count_the_diagonal_harmonics() {
for n in 1..=7u32 {
let f: QtPoly<Rational> =
side_at_content(&part(&vec![1; n as usize]), n - 1, Side::Rise);
let total: i128 = f.terms().map(|(_, c)| c.numer()).sum();
assert_eq!(
total,
(n as i128 + 1).pow(n - 1),
"labeled Dyck paths of size {n}"
);
}
}
#[test]
fn the_rise_side_is_delta_prime() {
for n in 0..=6u32 {
for k in 0..n {
let got = side::<Rational>(n, k, Side::Rise).to_schur();
let want = crate::deltaop::delta_prime_e::<Rational>(k, n);
assert_eq!(got, want, "Rise_{{{n},{k}}}");
}
}
}
#[test]
fn the_valley_side_is_delta_prime() {
for n in 0..=6u32 {
for k in 0..n {
let got = side::<Rational>(n, k, Side::Valley).to_schur();
let want = crate::deltaop::delta_prime_e::<Rational>(k, n);
assert_eq!(got, want, "Valley_{{{n},{k}}}");
}
}
}
#[test]
fn the_two_sides_agree() {
for n in 0..=6u32 {
for k in 0..n {
assert_eq!(
side::<Rational>(n, k, Side::Rise),
side::<Rational>(n, k, Side::Valley),
"the two sides at n={n}, k={k}"
);
}
}
}
#[test]
fn the_top_of_the_ladder_is_the_shuffle_theorem() {
for n in 1..=6u32 {
let want = crate::deltaop::nabla_e::<Rational>(n);
for which in [Side::Rise, Side::Valley] {
assert_eq!(
side::<Rational>(n, n - 1, which).to_schur(),
want,
"{which:?} at k = n-1, n={n}"
);
}
}
}
#[test]
fn the_rise_ladder_via_llt_agrees_with_the_labeled_walk() {
for n in 1..=6u32 {
let fast = rise_ladder_via_llt::<Rational>(n);
let mut slow = vec![Monomial::zero(); n as usize];
for mu in crate::partitions_of(n) {
for (k, c) in ladder_at_content::<Rational>(&mu, Side::Rise)
.into_iter()
.enumerate()
{
if !c.is_empty() {
slow[k].add_term(mu.clone(), c);
}
}
}
for k in 0..n as usize {
assert_eq!(fast[k], slow[k], "Rise_{{{n},{k}}} via LLT vs labelings");
}
}
}
#[test]
fn the_selection_knapsack_agrees_with_enumerating_subsets() {
let weights = [0u32, 1, 2, 2, 3, 1];
for m in 0..=weights.len() {
let mut want: std::collections::BTreeMap<u32, i128> = Default::default();
for mask in 0u32..(1 << weights.len()) {
if mask.count_ones() as usize != m {
continue;
}
let s: u32 = (0..weights.len())
.filter(|&i| mask >> i & 1 == 1)
.map(|i| weights[i])
.sum();
*want.entry(s).or_insert(0) += 1;
}
let rows = choose_all(&weights, weights.len());
let got: std::collections::BTreeMap<u32, i128> = rows[m].iter().copied().collect();
assert_eq!(got, want, "choosing {m}");
}
}
}