Skip to main content

Crate symfn

Crate symfn 

Source
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_coeff answers c^w_{uv} by Bruhat pruning for pairs whose product no machine holds, and ops::kronecker_coeff (under bignum) answers one g^ν_{λμ} 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 two llt outputs with no Sage entry point at any speed: the ∇e_n by-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 / BigRational coefficient rings and the guarded escalation they complete. An entry point whose fixed-width path fails across most of its intended range — ops::kronecker_coeff is one — exists only under this feature.
  • python — the PyO3 bindings the wheel is built from; enables bignum. 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α + v and 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, then QAlgebra and Plethystic for 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) and h^λ_{μν}(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 normalizations Q and J.
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 by Perm.
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 SkewLr otherwise.
CacheStat
One table’s share of the memory the caches hold, as cache_stats reports it.
StripLr
Row-level DP backend for Littlewood–Richardson coefficients.

Functions§

cache_budget
The byte budget the caches are held to, or None for 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, or None if either is not.
okada_product
s_μ · s_ν when both μ and ν are rectangles, or None if either is not — including ∅, which is not a rectangle here.
set_cache_budget
Hold the caches to budget bytes, or lift the bound with None.
three_row_product
s_a · s_b when one factor has exactly three rows, else None.
two_row_coeff
c^λ_{μν} when one factor has exactly two rows, else None.
two_row_product
s_a · s_b when one factor has exactly two rows, else None.