symfn 0.9.0

A modern, fast kernel for computing with symmetric functions.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
//! Labeled Dyck paths, and the combinatorial side of the Delta conjecture.
//!
//! ## The objects
//!
//! A Dyck path of size `n` is its **area sequence** `a_1 … a_n` with `a_1 = 0`
//! and `0 ≤ a_i ≤ a_{i−1} + 1`. A *labeled* Dyck path attaches a positive
//! integer `ℓ_i` to row `i`, strictly increasing up a rise:
//!
//! ```text
//!   a_i = a_{i−1} + 1   ⟹   ℓ_i > ℓ_{i−1}
//! ```
//!
//! and then, [HRW]:
//!
//! ```text
//!   area(P) = Σ_i a_i
//!   d_i(P)  = #{ j > i : a_i = a_j,     ℓ_i < ℓ_j }
//!           + #{ j > i : a_i = a_j + 1, ℓ_i > ℓ_j }
//!   dinv(P) = Σ_i d_i(P)
//!   Rise(P) = { i : a_i = a_{i−1} + 1 }
//!   Val(P)  = { i : a_i < a_{i−1} } ∪ { i : a_i = a_{i−1}, ℓ_i > ℓ_{i−1} }
//! ```
//!
//! `Val` is the definition that has to be read carefully: it is **not**
//! `a_i ≤ a_{i−1}`. The ties are included only when the label goes *up*, and
//! taking the easy reading instead makes the valley side disagree with the rise
//! side everywhere except `k = n−1`, where nothing is chosen and both collapse
//! to the shuffle theorem.
//!
//! ## Getting the whole symmetric function
//!
//! `x^P = ∏_i x_{ℓ_i}`, so the coefficient of `m_μ` is the number-with-weights
//! of labeled paths whose labels have **content μ** — `⟨f, h_μ⟩`, since `h`
//! and `m` are dual. So the monomial expansion is one enumeration per partition
//! of `n`, and `μ = (1ⁿ)` (all labels distinct) is the `⟨·, h_1ⁿ⟩` coefficient
//! on its own — the one that counts `(n+1)^{n−1}` paths at `k = n−1`.
//!
//! ## The `z` extraction is an elementary symmetric polynomial
//!
//! Both sides read off `z^{n−k−1}` from a product over the chosen statistic:
//!
//! ```text
//!   Rise:   ∏_{i ∈ Rise(P)} (1 + z / t^{a_i})
//!   Valley: ∏_{i ∈ Val(P)}  (1 + z / q^{d_i(P)+1})
//! ```
//!
//! which is `e_{n−k−1}` of those weights. Enumerating the subsets is
//! unnecessary — a two-line knapsack over the exponents gives the whole
//! selection polynomial at once, and it is what keeps the inner loop cheap.
//!
//! ## The rise side does not need the labels at all
//!
//! `Rise(P)` and the weights `t^{−a_i}` it selects over are functions of the
//! **area sequence alone** — no label appears in either. So the whole
//! `z`-extraction is a constant of the labeling sum and factors straight out
//! of it:
//!
//! ```text
//!   Rise_{n,k} = Σ_D [ Σ_{S ⊆ Rise(D), |S| = n−1−k} t^{area(D) − Σ_{i∈S} a_i} ] · G_D(x; q)
//! ```
//!
//! where `G_D(x;q) = Σ_labelings q^{dinv} x^ℓ` is the **vertical-strip LLT
//! polynomial** of the path. That is the whole rise ladder from `C_n` LLT
//! evaluations plus one knapsack each, in place of one labeled-path walk per
//! content — and [`crate::llt`] computes `G_D` from `#SYT` standard objects
//! rather than `#labelings`, by [HHL]'s standardization. Measured against the
//! labeled walk, identical at every `k`; `docs/record/llt.md` has the table.
//!
//! Standardizing *labeled paths* has no `dinv`-invariant tie-break; it is the
//! *tuple* fillings that get standardized, where [HHL] (82) is an identity
//! rather than a convention. `docs/record/dyck-paths.md` records it.
//!
//! **The valley side does not factor, and that is what it is for.**
//! `Val(P)` reads the labels — its tie clause is `ℓ_i > ℓ_{i−1}` — and its
//! weights are `q^{d_i+1}`, per labeling. So [`Side::Valley`] keeps the honest
//! enumeration below, and since valley is the *open* side, this makes the rise
//! half of the comparison free rather than moving the conjecture.
//! [`ladder_at_content`] keeps the labeled walk for **both** sides: it is the
//! oracle the fast route is checked against, and for a coarse content like
//! `μ = (n)` — one labeling — it is also simply cheaper.
//!
//! ## Negative exponents, and the one offset
//!
//! The rise weights divide by `t^{a_i}` and the chosen exponents sum to at most
//! `area(P)`, so `t` stays non-negative. The valley weights divide by
//! `q^{d_i+1}` and `Σ_{i∈S}(d_i + 1)` can exceed `dinv(P)` — by at most `|S| ≤ n`
//! — so the valley side genuinely visits negative powers of `q` before the sum
//! closes up. [`QtPoly`] has unsigned exponents, so the accumulation carries a
//! uniform `q^n` and divides it out at the end; the division is exact, and a
//! remainder there would mean the offset was too small rather than that the
//! conjecture failed.
//!
//! ## The Sage dictionary
//!
//! `ParkingFunctions(n)` is labeled Dyck paths with distinct labels, and its
//! `.area()` and `.dinv()` were confirmed to be [HRW]'s before being relied on;
//! `scripts/check_deltaop.py` uses it as an oracle. It carries no `Rise(P)`, no
//! `Val(P)`, no per-row `d_i(P)`, and no repeated labels, so it reaches the
//! `h_1ⁿ` coefficient alone — the `k = n−1` slice.
//! `docs/record/dyck-paths.md` records the confirmation.
//!
//! ## Range
//!
//! [`ladder`] has been run on both sides for every `k` and every content at
//! n ≤ 9, agreeing with [`deltaop`](crate::deltaop) throughout;
//! `docs/record/dyck-paths.md` has the table.
//!
//! What stops it is the enumeration. The valley side walks labeled paths, of
//! which content 1ⁿ alone has `(n+1)^{n−1}`, so n = 10 is out of reach by
//! direct enumeration. The rise side pays `C_n` LLT evaluations and one
//! knapsack each instead.
//!
//! The fixed-width arithmetic wall is unmeasured on either side
//! (`docs/policies/failure.md`, R9).
//!
//! ## Reference
//!
//! J. Haglund, J. Remmel, A. Wilson, *The Delta Conjecture*,
//! [arXiv:1509.07058](https://arxiv.org/abs/1509.07058), cited as **[HRW]**.
//! Their Conjecture 1.1 has two combinatorial sides for the same symmetric
//! function:
//!
//! ```text
//!   Δ'_{e_k} e_n  =  Rise_{n,k}(x;q,t)  =  Valley_{n,k}(x;q,t)
//! ```
//!
//! The **rise** version is a theorem (D'Adderio–Mellit; Blasiak–Haiman–Morse–
//! Pun–Seelinger, by two independent routes). The **valley** version is still
//! open. [`deltaop`](crate::deltaop) computes the left-hand side; this module
//! computes the two right-hand sides, so the three can be held against each
//! other.
//!
//! That makes this module what the Macdonald-operator work was built for,
//! rather than a test fixture. `docs/record/dyck-paths.md` records the
//! measurement: this enumeration, not the operator, is what stops a search at
//! the degrees a search runs at.
//!
//! [HHL]: https://arxiv.org/abs/math/0409538
//! [HRW]: https://arxiv.org/abs/1509.07058

// Path indices, bounded by the path length.
#![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};

/// Every area sequence of size `n`.
///
/// `a_1 = 0` and `a_i ≤ a_{i−1} + 1`, which is the standard bijection with Dyck
/// paths; there are `C_n` of them.
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());
}

/// Every labeling of `area` whose labels have content `counts`
/// (`counts[j]` copies of the label `j+1`), strictly increasing up a rise.
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;
    }
}

/// `d_i(P)`, the diagonal inversions beginning in row `i`.
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
}

/// `e_j` of the weights `x^{-w}` for **every** `j ≤ top`, as
/// `j ↦ [(subtracted exponent, multiplicity)]`.
///
/// A knapsack rather than a walk over the `C(|w|, j)` subsets: `dp[j][s]` counts
/// the ways to choose `j` of the weights with exponent sum `s`.
///
/// Every `j` at once, because the enumeration around this is the expensive part
/// and the `j`s are what the `k` ladder ranges over. Asking for one `j` per
/// pass re-walks every labeled path `n` times to produce `n` slices of a table
/// that one walk already fills.
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()
}

/// Which side of \[HRW\]'s Delta conjecture to build — the rise version or
/// the valley version.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Side {
    /// \[HRW\]'s rise version — a **theorem**, so a mismatch is a bug here.
    Rise,
    /// \[HRW\]'s valley version — **open**, so a mismatch is a result and must
    /// be reported as one rather than debugged away.
    Valley,
}

/// `Rise_{n,k}` or `Valley_{n,k}` in the monomial basis, for **every** `k` at
/// once: the returned vector is indexed by `k`, `0 ≤ k < n`.
///
/// Returns an empty vector at `n = 0`.
///
/// This is the unit of work, and the two sides reach it differently.
///
/// [`Side::Rise`] goes through the per-path LLT polynomials — the
/// factorization in the module docs, which replaces the labeled-path walk
/// entirely. [`Side::Valley`] cannot factor and so enumerates one labeled walk
/// per content. One knapsack produces every `k`'s slice, so asking for a
/// single `k` costs the same as asking for all of them.
///
/// Both routes are held against each other by
/// `the_rise_ladder_via_llt_agrees_with_the_labeled_walk`.
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
}

/// The rise ladder from the per-path LLT decomposition — see the module docs.
///
/// One [`llt::llt_g`](crate::llt::llt_g) per area sequence gives `G_D` in the
/// monomial basis for **all** contents at once, where the labeled walk pays
/// one enumeration per content; the `z`-extraction is then the same knapsack
/// over the rise weights, which depend only on the area sequence.
///
/// The `t` exponent `area(D) − Σ_{i∈S} a_i` is non-negative because `S` is a
/// subset of the rows and the weights are those rows' own `a_i`, which is the
/// same reason [`ladder_at_content`] needs no offset on this side.
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();
        // Slot j of the knapsack is the `z^j` coefficient, i.e. k = n−1−j.
        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);
                }
            }
        }
    });
    // The slots were filled through the raw entry API, which bypasses
    // `add_term`'s zero check, so an explicit zero can survive a cancellation.
    for slot in &mut out {
        slot.terms_mut().retain(|_, c| !c.is_zero());
    }
    out
}

/// `⟨Rise_{n,k}, h_μ⟩` or `⟨Valley_{n,k}, h_μ⟩` for every `k`, indexed by `k`.
///
/// `μ = (1ⁿ)` is the cheap slice — the coefficient of `x_1 ⋯ x_n`, which at
/// `k = n−1` counts the `(n+1)^{n−1}` parking functions.
///
/// # Panics
///
/// Panics if `μ` is empty. The Delta conjecture is stated for `n > 0`, and the
/// returned vector is indexed by `k ∈ 0..n`, so `n = 0` has no answer to hold.
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");
    // The valley weights can subtract more powers of q than `dinv` supplies; see
    // the module docs. `n` is enough: at most `|S| ≤ n` excess.
    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(),
            };

            // slot j of the knapsack is the `z^{j}` coefficient, i.e. k = n−1−j.
            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;
    }
    // Divide the uniform q^offset back out. Exact by construction — a failure
    // here means the offset was too small, not that the conjecture broke.
    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()
}

/// `Rise_{n,k}` or `Valley_{n,k}` for one `k`.
///
/// A slice of [`ladder`], and it costs the same as the whole ladder — see
/// there.
///
/// # Panics
///
/// Panics unless `k < n`, which is the range the Delta conjecture is stated
/// over.
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)
}

/// One coefficient of one `k`. A slice of [`ladder_at_content`], at the same
/// cost.
///
/// # Panics
///
/// Panics unless `k < |μ|`, and if `μ` is empty; see [`ladder_at_content`].
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())
    }

    /// The count of labeled Dyck paths with distinct labels is `(n+1)^{n−1}` —
    /// the dimension of the diagonal harmonics.
    ///
    /// This is the enumeration under test on its own, before any statistic is
    /// involved: `k = n−1` chooses nothing, so every path contributes 1.
    #[test]
    fn distinct_labelings_count_the_diagonal_harmonics() {
        // The ladder is indexed by k = n-1, which has no n = 0 case.
        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}"
            );
        }
    }

    /// **The rise version, against the operator.** A theorem, so a mismatch
    /// here is a bug on one side or the other.
    ///
    /// Compared as whole symmetric functions, not just at `h_1ⁿ`: the monomial
    /// expansion is one enumeration per content, and a statistic that was wrong
    /// only on repeated labels would survive the `(1ⁿ)` check alone.
    #[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}}}");
            }
        }
    }

    /// **The valley version, against the operator — an open conjecture.**
    ///
    /// If this ever fails, the first thing to check is `Val(P)`: the tie case
    /// belongs in only when the label rises (see the module docs). If it fails
    /// with `Val` right, it is a counterexample and must be reported as one.
    #[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}}}");
            }
        }
    }

    /// The two sides must agree with each other, which is the conjecture stated
    /// without the operator in the way.
    #[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}"
                );
            }
        }
    }

    /// `k = n−1` is the shuffle theorem: both sides must be `∇e_n`.
    #[test]
    fn the_top_of_the_ladder_is_the_shuffle_theorem() {
        // The ladder is indexed by k = n-1, which has no n = 0 case.
        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}"
                );
            }
        }
    }

    /// **The rise route against the labeled walk it replaced.**
    ///
    /// [`ladder`] no longer enumerates labeled paths on the rise side, so the
    /// walk that used to be the implementation is now the oracle. It is checked
    /// at every `k` and every content, not just in total: the factorization
    /// moves the `z`-extraction outside the labeling sum, so an error there
    /// redistributes between `k`s, which any aggregate check would miss.
    #[test]
    fn the_rise_ladder_via_llt_agrees_with_the_labeled_walk() {
        // rise_ladder_via_llt has one slot per k = 0..n-1, so it is empty at n = 0.
        for n in 1..=6u32 {
            let fast = rise_ladder_via_llt::<Rational>(n);
            // The labeled walk, one content at a time — the pre-LLT route.
            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");
            }
        }
    }

    /// The subset knapsack must agree with a direct walk over the subsets.
    #[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}");
        }
    }
}