pith. sign in

arxiv: 2605.22378 · v1 · pith:U4ZTP65Nnew · submitted 2026-05-21 · 🧮 math.CO · cs.MS

Fast computation of Ehrhart polynomials of Gelfand--Tsetlin polytopes via Macdonald reciprocity

Per Alexandersson This is my paper

Pith reviewed 2026-05-22 04:37 UTC · model grok-4.3

classification 🧮 math.CO cs.MS MSC 52B2005A15
keywords Ehrhart polynomialsGelfand-Tsetlin polytopesMacdonald reciprocityKostka coefficientsstrict Gelfand-Tsetlin patternscombinatorial enumerationpolytope computation
0
0 comments X

The pith

Evaluating Ehrhart polynomials at negative integers via strict Gelfand-Tsetlin pattern counts speeds up the computation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper describes an efficient method for computing Ehrhart polynomials of Gelfand-Tsetlin polytopes that arise from Kostka coefficients. The approach exploits Ehrhart-Macdonald reciprocity so that evaluation at negative integers reduces to counting strict Gelfand-Tsetlin patterns, which are frequently zero or small for low dilations. An adaptive strategy then selects the cheaper of positive or negative evaluation points at each interpolation step. This combination produces practical speedups relative to general-purpose polytope software, with benchmarks against OSCAR and polymake, and the same ideas extend to order polytopes and permutation posets.

Core claim

By Ehrhart-Macdonald reciprocity, the value of the Ehrhart polynomial of a Gelfand-Tsetlin polytope at a negative integer equals the number of strict Gelfand-Tsetlin patterns of the corresponding size. These counts are often much smaller than the lattice-point enumerations required at positive integers. An adaptive algorithm therefore chooses, for each required evaluation point, the direction (positive or negative) whose count is cheaper to compute, thereby determining the full polynomial with substantially less total work than standard methods.

What carries the argument

Ehrhart-Macdonald reciprocity applied to strict Gelfand-Tsetlin patterns, which converts negative evaluations into small combinatorial counts.

If this is right

  • The method yields substantial practical speedups compared to general-purpose polytope software such as OSCAR and polymake.
  • The same reciprocity and adaptive evaluation technique applies directly to Ehrhart polynomials of order polytopes and permutation posets.
  • The implementation in the Rust kostka package makes these computations available for Kostka coefficients and related objects.
  • Optimizations from the approach are incorporated into the lrcalc-rs replacement for lrcalc.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Reciprocity-based evaluation could accelerate Ehrhart computations for other families of polytopes that appear in representation theory or algebraic combinatorics.
  • The adaptive choice of evaluation sign might be generalized to other polynomial interpolation tasks that admit both positive and negative counting interpretations.
  • Empirical testing on larger or different classes of posets would clarify the range of instances where the speedups remain significant.

Load-bearing premise

That counting strict Gelfand-Tsetlin patterns at negative integers is reliably cheaper than counting ordinary lattice points for the dilation values needed to interpolate the polynomial.

What would settle it

A concrete Gelfand-Tsetlin polytope and set of dilation factors where the time to count strict patterns at the chosen negative points exceeds the time for lattice-point enumeration at the corresponding positive points, so that the adaptive method yields no net speedup.

read the original abstract

We describe an efficient method for computing the Ehrhart polynomial of Gelfand--Tsetlin polytopes arising from Kostka coefficients. The key idea is to exploit Ehrhart--Macdonald reciprocity: evaluating the Ehrhart polynomial at negative integers reduces to counting \emph{strict} Gelfand--Tsetlin patterns, which are often zero or very small for low dilations. Combined with an adaptive strategy that chooses the cheapest evaluation point (positive or negative) at each step, this yields substantial practical speedups compared to general-purpose polytope software. We benchmark against $\mathtt{OSCAR}$/$\mathtt{polymake}$, and illustrate the broader applicability of the method through order polytopes and permutation posets. The implementation is available in the Rust \texttt{kostka} package, with related optimizations also incorporated in the new \texttt{lrcalc-rs} replacement for \texttt{lrcalc}.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper presents a method for fast computation of Ehrhart polynomials of Gelfand-Tsetlin polytopes associated to Kostka coefficients. It exploits Ehrhart-Macdonald reciprocity so that evaluations at negative integers reduce to counting strict Gelfand-Tsetlin patterns (often zero or small for low dilations), combined with an adaptive strategy that selects the cheaper (positive or negative) evaluation point during interpolation. The approach is benchmarked against OSCAR/polymake, extended to order polytopes and permutation posets, and implemented in the Rust kostka package (with related changes in lrcalc-rs).

Significance. If the claimed practical speedups hold under the reported conditions, the work supplies a useful specialized algorithm for Ehrhart computations in combinatorial representation theory. The core idea re-uses a standard reciprocity theorem to convert expensive positive-dilation counts into cheaper strict-pattern enumerations, and the adaptive interpolation is a straightforward dynamic-programming optimization over a fixed number of points. The open-source Rust implementation and the extension to other poset polytopes are concrete strengths that support reproducibility and broader applicability.

major comments (2)
  1. [§3.2] §3.2, Algorithm 1: the adaptive selection rule compares estimated costs of positive versus negative evaluations, but the manuscript does not specify how the cost of enumerating strict Gelfand-Tsetlin patterns is computed or bounded; without an explicit complexity model or timing breakdown for the counting subroutine, it is impossible to verify that the adaptive choice reliably produces net speedups rather than merely shifting overhead.
  2. [Table 1] Table 1, rows for dilation 3–5: the reported wall-clock times for the new method are substantially lower than OSCAR, yet no standard deviation, number of independent runs, or hardware specification is given; this weakens the quantitative claim of “substantial practical speedups” and makes it difficult to assess statistical significance of the improvement.
minor comments (3)
  1. [Abstract / §4] The abstract states that strict patterns are “often zero or very small,” but the main text never quantifies the proportion of zero counts or the typical size for the dilations actually used in the benchmarks; adding a short table or sentence with these statistics would clarify the source of the observed efficiency.
  2. [§2] Notation for the Gelfand-Tsetlin polytope and its strict variant is introduced without a self-contained definition or reference to a standard source; a one-paragraph reminder of the precise inequalities would help readers who are not specialists in the area.
  3. [§5] The Rust implementation is mentioned but no link, repository commit, or instructions for reproducing the benchmarks appear in the manuscript; adding these details would improve verifiability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment, and recommendation for minor revision. We address each major comment below and will incorporate clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§3.2] §3.2, Algorithm 1: the adaptive selection rule compares estimated costs of positive versus negative evaluations, but the manuscript does not specify how the cost of enumerating strict Gelfand-Tsetlin patterns is computed or bounded; without an explicit complexity model or timing breakdown for the counting subroutine, it is impossible to verify that the adaptive choice reliably produces net speedups rather than merely shifting overhead.

    Authors: We agree that the cost model underlying the adaptive rule merits a more explicit description. The negative-evaluation cost is estimated from the number of strict Gelfand-Tsetlin patterns, which is obtained via a dynamic-programming recurrence whose running time scales linearly with the (typically small or zero) pattern count for low negative dilations; positive-evaluation cost is taken from the known complexity of the general-purpose Ehrhart routine. In the revision we will add a short paragraph in §3.2 describing this heuristic together with a brief complexity discussion, and we will include a timing breakdown of the counting subroutine in the experimental section. revision: yes

  2. Referee: Table 1, rows for dilation 3–5: the reported wall-clock times for the new method are substantially lower than OSCAR, yet no standard deviation, number of independent runs, or hardware specification is given; this weakens the quantitative claim of “substantial practical speedups” and makes it difficult to assess statistical significance of the improvement.

    Authors: We acknowledge that additional experimental details would strengthen the presentation. Because the algorithm is fully deterministic, repeated runs on the same input produce identical timings, so standard deviations are not applicable. In the revised manuscript we will state the hardware platform used for the benchmarks and note that each entry reflects a single execution; the open-source Rust implementation will allow readers to reproduce the measurements exactly. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central method applies the standard external Ehrhart-Macdonald reciprocity theorem to convert negative evaluations of the Ehrhart polynomial into counts of strict Gelfand-Tsetlin patterns, then uses an adaptive choice of positive or negative evaluation points for interpolation. This reciprocity is a well-known theorem independent of the present work, the pattern-counting step is a direct application of the theorem's statement, and the adaptive strategy is a standard dynamic-programming optimization over a fixed set of points. No equations reduce to self-definitions, no fitted parameters are relabeled as predictions, and no load-bearing claims rest on self-citations or author-specific uniqueness results. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method rests on the application of a known reciprocity theorem to reduce computation cost; no new free parameters or invented entities are introduced.

axioms (1)
  • standard math Ehrhart-Macdonald reciprocity
    Invoked to equate negative evaluations of the Ehrhart polynomial with counts of strict Gelfand-Tsetlin patterns.

pith-pipeline@v0.9.0 · 5688 in / 1240 out tokens · 58726 ms · 2026-05-22T04:37:01.360064+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    2023 , Eprint =

    Per Alexandersson and Ezgi Kantarci Oğuz , Title =. 2023 , Eprint =

    work page 2023

  2. [2]

    2019 , month = jun, publisher =

    Per Alexandersson and Elie Alhajjar , title =. 2019 , month = jun, publisher =. doi:10.1142/9789811200489_0003 , url2 =

    work page doi:10.1142/9789811200489_0003 2019

  3. [3]

    McAllister , title =

    Christian Haase and Tyrrell B. McAllister , title =. Contemporary Mathematic , doi =. 2008 , volume=

    work page 2008

  4. [4]

    Stanley , title =

    Richard P. Stanley , title =. 2011 , isbn =. doi:10.1017/CBO9781139058520 , publisher =

    work page doi:10.1017/cbo9781139058520 2011

  5. [5]

    Anders Skovsted Buch , title =. Enseign. Math. (2) , volume =

    work page

  6. [6]

    R. C. King and C. Tollu and F. Toumazet , title =. CRM Proceedings and Lecture Notes , year =

    work page

  7. [7]

    On the computation of

    Jes. On the computation of. doi:10.1080/10586458.2006.10128948 , journal =

    work page doi:10.1080/10586458.2006.10128948 2006

  8. [8]

    Etienne Rassart , title =. J. Comb. Theory Ser. A , issue_date =. 2004 , issn =. doi:10.1016/j.jcta.2004.04.003 , acmid =

    work page doi:10.1016/j.jcta.2004.04.003 2004

  9. [9]

    Order , year=

    Graham Brightwell and Peter Winkler , title=. Order , year=

    work page

  10. [10]

    Gelfand--

    Ricky Ini Liu and Karola M. Gelfand--. 2019 , Eprint =

    work page 2019

  11. [11]

    Combinatoire

    A. Combinatoire. 1986 , publisher=. doi:10.1007/BFb0072521 , author=

    work page doi:10.1007/bfb0072521 1986

  12. [12]

    , year =

    Stanley, Richard P. , year =. A Monotonicity Property of h-vectors and h*-vectors , volume =. European Journal of Combinatorics , publisher =. doi:10.1006/eujc.1993.1028 , number =

    work page doi:10.1006/eujc.1993.1028 1993

  13. [13]

    European Journal of Combinatorics , volume =

    Beck, Matthias and Sottile, Frank , title =. European Journal of Combinatorics , volume =. 2007 , doi =

    work page 2007

  14. [14]

    2015 , doi =

    Beck, Matthias and Robins, Sinai , title =. 2015 , doi =

    work page 2015

  15. [15]

    Polytopes --- Combinatorics and Computation , publisher =

    Gawrilow, Ewgenij and Joswig, Michael , title =. Polytopes --- Combinatorics and Computation , publisher =. 2000 , pages =

    work page 2000

  16. [16]

    J.\ Algebra , year =

    Bruns, Winfried and Ichim, Bogdan , title =. J.\ Algebra , year =

    work page

  17. [17]

    Macdonald, I. G. , title =. J. London Math. Soc. , volume =. 1971 , doi =

    work page 1971

  18. [18]

    2025 , note =

    Hogman, Oskar , title =. 2025 , note =

    work page 2025

  19. [19]

    2026 , eprint =

    Katharina Jochemko and Krishna Menon , title =. 2026 , eprint =

    work page 2026

  20. [20]

    Discrete & Computational Geometry , volume =

    Matthias Beck and Dennis Pixton , title =. Discrete & Computational Geometry , volume =. 2003 , eprint =

    work page 2003

  21. [21]

    Kostka numbers and

    Janvier Nzeutchap and Fr. Kostka numbers and. Proceedings of Professor Brian G. Wybourne Commemorative Meeting , year =

    work page

  22. [22]

    King and Christophe Tollu and Fr

    Ronald C. King and Christophe Tollu and Fr. The hive model and the polynomial nature of stretched. S. 2006 , url =

    work page 2006