Expand description
A kernel for computing with symmetric functions: the six classical bases, every transition between them, and the Hall–Littlewood, Macdonald, LLT and Jack families above them, together with Schubert polynomials.
Each basis is a distinct Rust type over a coefficient ring the caller
chooses, so a basis mix-up is a compile error and ℚ[q,t] is as ordinary a
coefficient ring as ℤ. Every value that leaves the library is exact, or
the call fails loudly.
§What it computes
The classical core. The six bases — Schur, Homogeneous,
Elementary, Monomial, PowerSum, Forgotten — as distinct
types unified by the SymFn trait, with convert() between every
ordered pair. Three products: ordinary — Littlewood–Richardson behind the
LrBackend trait, native in Rust with no external C library —
plethystic (plethysm()) and internal (kronecker). The full Hopf
structure: coproduct, counit, antipode, and skewing by an
arbitrary symmetric function (SkewBy). Evaluation at a finite
alphabet, the principal specializations and their q-analog (eval),
symmetric-group characters (character()) and Kostka numbers
(kostka()) — as single values and as whole tables.
The parametrized families. Hall–Littlewood Q'_λ(x;t) and P_λ(x;t)
(hl) and the Kostka–Foulkes polynomials (kf); Macdonald P_λ,
Q_λ and J_λ (macdonald); the (q,t)-Kostka polynomials and the
modified Macdonald basis Ht (qtkostka); Jack P/Q/J_λ(x;α) and
the zonal specialization (jack); LLT polynomials in both the ribbon
and tuple models, the tuple entries straight or skew (llt,
SkewTuple); the delta-operator tower ∇, Δ'_f, Θ (deltaop);
Schubert polynomials and their structure constants (schubert). Each
family’s deformed Hall pairing sits beside the classical one —
hl::scalar_t, macdonald::scalar_qt, jack_scalar — and each
family is orthogonal under its own.
Everything is generic over Ring, and the paths that divide ask only
for QAlgebra, a ring containing ℚ, because every division in the
library is by z_μ — an integer. That is weaker than a field on
purpose: ℚ[t] and ℚ[q,t] are not fields, and they are exactly the
rings Hall–Littlewood and Macdonald need. Plethysm asks one thing more,
Plethystic, since p_n acts on the coefficients too.
§What this opens
- A single structure constant for a product that cannot be
materialized.
schubert::schubert_coeffanswersc^w_{uv}by Bruhat pruning for pairs whose product no machine holds, andops::kronecker_coeff(underbignum) answers oneg^ν_{λμ}where the whole internal product does not fit. The query itself is the capability, not a faster route to the full product. - Reduced (stable) Kronecker coefficients as an outer product in the
Orellana–Zabrocki bases (
character_basis). The calculation never leaves the power-sum basis, so no Littlewood–Richardson coefficient enters it at all. - Matchings–Jack and b-conjecture coefficients (
gj), which no other package computes, and the twolltoutputs with no Sage entry point at any speed: the∇e_nby-path Schur-positive refinement, and parabolic affine Kazhdan–Lusztig columns.
docs/record/oracles-and-comparisons.md is the measured survey of the
incumbents behind those claims, including what does exist elsewhere;
docs/record/ carries the degrees and shapes each engine reaches.
§Conventions
Every K_{λμ} variant, LLT G, and H̃ in circulation differs from its
rivals by a normalization twist that yields plausible wrong answers, not
errors. Each family’s module doc therefore opens with the conventions in
circulation, names the one that ships with references by equation number,
and pins it with a doctest whose value distinguishes it from its rivals —
“The conventions in circulation” in llt is the fullest example.
§Exactness
Every value that leaves this library is exact, or the call fails
loudly — in every build profile. A computation has three legal outcomes
and no fourth: the exact answer; escalation to a wider ring and then the
exact answer; or a refusal the caller cannot mistake for an answer —
None, Err, a typed Python exception, or a panic the item documents. No
path returns a wrapped, truncated or rounded value.
The default coefficient rings i64, i128 and Rational are the fast
path: exact until a value leaves the width, and then a panic rather than a
wrap. BigInt and BigRational (the bignum feature) have no wall. In
between, Guarded and GuardedRat inside a guarded scope
report an overflow instead of panicking, so a caller can re-run the same
generic code over a bignum ring — which is what the Python boundary does
on every call. Where a fixed-width family has a wall a caller can reach,
its own module doc states the wall in reproducible terms, next to the
degrees and shapes the engine is measured to reach.
docs/policies/failure.md is the rulebook this compresses.
§Verification
The test suite checks computed values against reference output from
independent software, committed to the tree: tests/sage_oracle.rs and
tests/lrcalc_oracle.rs compare against fixtures Sage and lrcalc
produced, with scripts/gen_sage_oracle.sage alongside so an auditor can
regenerate the fixtures rather than trust them; tests/algebra_laws.rs
checks the laws a fixed value cannot — conversions are ring homomorphisms,
ω is an involutive algebra map, Δ is an algebra map; and
scripts/check_backend.py runs this crate underneath Sage, so the inputs
are chosen by Sage rather than by these tests. Where no independent
software computes a family at all, the cross-check is internal: the
(q,t)-Kostka table is computed by three algorithms sharing nothing above
Partition, and the three LrBackend implementations agree
exhaustively on every product with |μ| + |ν| ≤ 7.
docs/policies/validation.md is the standard each family is held to.
§Feature flags
bignum—BigInt/BigRationalcoefficient rings and theguardedescalation they complete. An entry point whose fixed-width path fails across most of its intended range —ops::kronecker_coeffis one — exists only under this feature.python— the PyO3 bindings the wheel is built from; enablesbignum. The Python surface has its own reference at https://symfn.readthedocs.io.
§Examples
Littlewood–Richardson over ℤ:
use symfn::{Schur, SymFn, Partition};
// s_2 · s_1 = s_3 + s_{21}
let s2: Schur<i64> = Schur::monomial(Partition::new([2]), 1);
let s1: Schur<i64> = Schur::monomial(Partition::new([1]), 1);
let prod = s2.mul(&s1);
assert_eq!(prod.coeff(&Partition::new([3])), 1);
assert_eq!(prod.coeff(&Partition::new([2, 1])), 1);Hall–Littlewood over ℤ[q,t] — the same Schur type, with QtPoly
coefficients:
use symfn::{hall_littlewood, Partition, QtPoly, SymFn};
// Q'_{21}(x; t) = s_{21} + t·s_3
let qp = hall_littlewood::<i64>(&Partition::new([2, 1]));
assert_eq!(qp.coeff(&Partition::new([3])), QtPoly::t());
assert_eq!(qp.coeff(&Partition::new([2, 1])).coeff(0, 0), 1);
assert!(qp.coeff(&Partition::new([1, 1, 1])).is_empty());Re-exports§
pub use afrac::AFrac;pub use character::character;pub use character::character_in;pub use character::try_character;pub use character_basis::reduced_kronecker;pub use character_basis::reduced_kronecker_product;pub use coeff::Field;pub use coeff::Plethystic;pub use coeff::QAlgebra;pub use coeff::Rational;pub use coeff::Ring;pub use convert::convert;pub use convert::convert_named;pub use convert::convert_named_to_power;pub use convert::FromSchur;pub use convert::ToSchur;pub use deltaop::big_pi;pub use deltaop::big_pi_inverse;pub use deltaop::delta;pub use deltaop::delta_prime;pub use deltaop::delta_prime_e;pub use deltaop::macdonald_ht_to_schur;pub use deltaop::nabla;pub use deltaop::nabla_e;pub use deltaop::nabla_power;pub use deltaop::scalar_qt_ratio;pub use deltaop::schur_to_macdonald_ht;pub use deltaop::theta;pub use deltaop::Atom;pub use deltaop::Ratio;pub use dyck::ladder;pub use dyck::ladder_at_content;pub use dyck::side;pub use dyck::side_at_content;pub use dyck::Side;pub use eval::dimension;pub use eval::principal_specialization;pub use eval::principal_specialization_q;pub use frac::Frac;pub use gj::class_algebra_coefficient;pub use gj::double_coset_coefficient;pub use gj::double_coset_table;pub use gj::gj_connection_tables;pub use gj::try_class_algebra_coefficient;pub use gj::BPoly;pub use gj::GjTables;pub use guard::guarded;pub use guard::Guarded;pub use guard::GuardedRat;pub use hl::hall_littlewood;pub use hl::hall_littlewood_p;pub use hl::hall_littlewood_p_table;pub use hl::hall_littlewood_p_to_schur;pub use hl::hall_littlewood_qp_to_schur;pub use hl::hall_littlewood_table;pub use hl::powersum_scalar_t;pub use hl::scalar_t;pub use hl::schur_to_hall_littlewood_p;pub use hl::schur_to_hall_littlewood_qp;pub use hopf::antipode;pub use hopf::coproduct;pub use hopf::counit;pub use hopf::skew_schur;pub use hopf::SkewBy;pub use hopf::SymTensor;pub use jack::jack_j;pub use jack::jack_j_powersum;pub use jack::jack_j_table;pub use jack::jack_j_to_monomial;pub use jack::jack_norm_j;pub use jack::jack_norm_p;pub use jack::jack_p;pub use jack::jack_p_to_monomial;pub use jack::jack_powersum_table;pub use jack::jack_q;pub use jack::jack_q_to_monomial;pub use jack::jack_scalar;pub use jack::jack_structure_constant;pub use jack::jack_table;pub use jack::monomial_to_jack_j;pub use jack::monomial_to_jack_p;pub use jack::monomial_to_jack_q;pub use jack::omega_alpha;pub use jack::powersum_scalar;pub use jack::stanley_table;pub use jack::zonal_j;pub use jack::zonal_p;pub use kf::kostka_foulkes;pub use kf::kostka_foulkes_column;pub use kf::kostka_foulkes_table;pub use kostka::kostka;pub use kostka::try_kostka;pub use llt::chromatic_from_llt;pub use llt::llt_e_expansion;pub use llt::llt_fundamental;pub use llt::llt_g;pub use llt::llt_g_lt;pub use llt::llt_graph;pub use llt::llt_gtilde;pub use llt::llt_gtilde_table;pub use llt::llt_h;pub use llt::llt_h_table;pub use llt::llt_h_tilde;pub use llt::llt_kl_column;pub use llt::llt_schur;pub use llt::monomial_in_llt_h_table;pub use llt::monomial_in_llt_h_tilde_table;pub use llt::nabla_e_by_path;pub use llt::DecoratedGraph;pub use llt::SkewTuple;pub use lr::LrBackend;pub use lr::NaiveLr;pub use macdonald::macdonald_j;pub use macdonald::macdonald_j_to_monomial;pub use macdonald::macdonald_p;pub use macdonald::macdonald_p_table;pub use macdonald::macdonald_p_to_monomial;pub use macdonald::macdonald_q;pub use macdonald::macdonald_q_to_monomial;pub use macdonald::monomial_to_macdonald_p;pub use macdonald::monomial_to_macdonald_q;pub use macdonald::powersum_scalar_qt;pub use macdonald::scalar_qt;pub use ops::hall;pub use ops::internal;pub use ops::kronecker;pub use ops::omega;pub use partition::partitions_of;pub use partition::Partition;pub use partition::PartitionError;pub use plethysm::plethysm;pub use qt::QtPoly;pub use qtkostka::macdonald_ht;pub use qtkostka::modified_qt_kostka;pub use qtkostka::qt_kostka;pub use qtkostka::qt_kostka_column;pub use qtkostka::qt_kostka_table;pub use qtkostka::schur_in_j_table;pub use qtkostka::schur_to_macdonald_j;pub use skew_lr::expand_skew;pub use skew_lr::SkewLr;pub use sym::Elementary;pub use sym::Forgotten;pub use sym::Homogeneous;pub use sym::Ht;pub use sym::Monomial;pub use sym::PowerSum;pub use sym::Schur;pub use sym::St;pub use sym::SymAlgebra;pub use sym::SymFn;
Modules§
- afrac
- ℚ(α), with denominators that factor into linear forms
uα + vand a general factor beside them for the one operation that leaves that class. - character
- Irreducible characters χ^λ(μ) of the symmetric group, via the Murnaghan–Nakayama rule.
- character_
basis - The Orellana–Zabrocki character bases, and a reduced-Kronecker engine.
- charge
- The charge statistic, and Kostka–Foulkes polynomials as a reference.
- coeff
- The coefficient-ring abstraction:
Ring, thenQAlgebraandPlethysticfor the two things a ring may additionally have to supply. - convert
- The basis-change engine: conversions between all six classical bases, routed through the Schur hub except where a pair has a direct rule.
- deltaop
- The Macdonald operator algebra: ∇, Δ_f, Δ’_f, Π and Θ_f.
- dyck
- Labeled Dyck paths, and the combinatorial side of the Delta conjecture.
- eval
- Evaluation at a finite alphabet, and the principal specializations.
- frac
- ℚ(q,t), restricted to denominators that are products of binomials
1 − qᵃtᵇ. - gj
- The Goulden–Jackson connection-coefficient pipeline:
c^λ_{μν}(b)andh^λ_{μν}(b). - guard
- Fixed-width coefficients that report overflow instead of wrapping, and the scope that turns a report into a re-run.
- hl
- Hall–Littlewood polynomials, by the Morris (1963) recursion.
- hopf
- The Hopf-algebra structure of Sym: skewing, comultiplication, counit, and antipode.
- interrupt
- Cancellation: how a caller stops a computation that is already running.
- jack
- Jack polynomials
P_λ(x; α), and the two other normalizationsQandJ. - kf
- Kostka–Foulkes polynomials
K_{λμ}(t), from the Hall–Littlewood transition. - kostka
- Kostka numbers K_{λμ} = number of semistandard Young tableaux of shape λ and content μ (μ_i entries equal to i, rows weakly increasing, columns strictly increasing).
- llt
- LLT polynomials: the ribbon model, the tuple model, and the dictionary between them.
- lr
- Littlewood–Richardson coefficients, computed natively in Rust.
- macdonald
- Macdonald’s
P_λ(x; q, t), by the branching formula. - ops
- Standard operations on symmetric functions: the ω involution, the Hall inner product, and the internal (Kronecker) product.
- partition
- Integer partitions — a “real type” with its invariant enforced at construction.
- permutation
- Permutations of ℕ₊ moving finitely many points — the index type for
Schubert. - plethysm
- Plethysm
f[g]of two symmetric functions in the Schur basis. - qt
- Bivariate
(q, t)polynomials as a coefficient ring. - qtkostka
- The (q,t)-Kostka polynomials
K_{λμ}(q,t). - schubert
- Schubert polynomials
S_w, indexed byPerm. - skew_lr
- Whole-shape Littlewood–Richardson expansion.
- sym
- Symmetric functions as real types, one per basis, unified by a trait.
Structs§
- AutoLr
- The backend the library uses by default: a closed form when both factors
are rectangles, a counting route on some two- and three-row products, and
SkewLrotherwise. - Cache
Stat - One table’s share of the memory the caches hold, as
cache_statsreports it. - StripLr
- Row-level DP backend for Littlewood–Richardson coefficients.
Functions§
- cache_
budget - The byte budget the caches are held to, or
Nonefor unbounded. - cache_
stats - What every memo table holds right now, one row per table.
- clear_
caches - Drop every cached table, releasing the memory.
- okada_
coeff c^λ_{μν}when both μ and ν are rectangles, orNoneif either is not.- okada_
product s_μ · s_νwhen both μ and ν are rectangles, orNoneif either is not — including∅, which is not a rectangle here.- set_
cache_ budget - Hold the caches to
budgetbytes, or lift the bound withNone. - three_
row_ product s_a · s_bwhen one factor has exactly three rows, elseNone.- two_
row_ coeff c^λ_{μν}when one factor has exactly two rows, elseNone.- two_
row_ product s_a · s_bwhen one factor has exactly two rows, elseNone.