Stretched Schubert coefficients are eventually quasi-polynomial
Pith reviewed 2026-05-07 08:15 UTC · model grok-4.3
The pith
Stretched Schubert coefficients become eventually quasi-polynomial for fixed permutations.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For permutations u, v, w in the symmetric group, the stretched Schubert coefficient f_{u,v,w}(N) := c_{N*u, N*v}^{N*w} is eventually quasi-polynomial. The proof expresses these coefficients as alternating sums of the numbers of integer points in polytopes coming from the pipe-dream model; these polytopes scale in a controlled way, so Ehrhart theory supplies the quasi-polynomial form.
What carries the argument
Pipe-dream polytopes whose lattice-point counts, under linear stretching by N, yield the Schubert coefficients via an alternating sum to which Ehrhart theory applies.
If this is right
- The ordinary generating function summing f_{u,v,w}(N) over N is a rational function.
- New infinite families of counterexamples to the saturation conjecture for Schubert coefficients exist.
- Algorithms that evaluate or interpolate the quasi-polynomial can compute stretched coefficients for large N without enumerating all pipe dreams.
- The same polytope construction yields effective bounds on the eventual period and degree of the quasi-polynomial.
Where Pith is reading between the lines
- The same stretching-plus-Ehrhart technique may apply to other families of coefficients defined by alternating sums over combinatorial models, such as Littlewood-Richardson or Kronecker coefficients.
- Rationality of the generating function supplies a new source of asymptotic formulas for the growth rate of ordinary Schubert coefficients.
- The counterexamples to saturation suggest that positivity conjectures for Schubert coefficients may require stronger conditions than merely non-negative stretching.
- Computational packages that compute Ehrhart quasi-polynomials of pipe-dream polytopes could be used to tabulate large tables of stretched coefficients automatically.
Load-bearing premise
The polytopes arising in the pipe-dream representation of Schubert coefficients scale linearly with the stretch factor N so that standard Ehrhart theory directly governs their lattice-point enumerators.
What would settle it
An explicit triple of permutations u, v, w together with a concrete computation of the first several dozen values of f(N) that fails to match any quasi-polynomial of the predicted period and degree.
Figures
read the original abstract
For a permutation $u\in S_n$, let $N\ast u\in S_{Nn}$ be the permutation with scaled Lehmer code. For given $u,v,w\in S_n$ and integer $N$, the stretched Schubert coefficients are defined as $f_{u,v,w}(N):=c_{N*u,N*v}^{N*w}$. Our main result is that the function $f_{u,v,w}(N)$ is eventually quasi-polynomial. This proves Kirillov's conjecture (2004), that the generating function for the sequence $\{f_{u,v,w}(N)\}$ is rational. For the proof, we use combinatorics of pipe dreams to show that Schubert coefficients are given as an alternating sum of the numbers of integer points in certain polytopes. These polytopes behave nicely under stretching, and we use Ehrhart theory to obtain the result. As a consequence of the proof, we also present new counterexamples to the saturation conjecture for Schubert coefficients, and give computational applications.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that for fixed u, v, w in S_n the stretched Schubert coefficient f_{u,v,w}(N) := c_{N*u, N*v}^{N*w}, where N*u denotes the permutation whose Lehmer code is scaled by N, is eventually quasi-polynomial in N. The proof expresses Schubert coefficients via the pipe-dream model as an alternating sum of lattice-point counts in certain polytopes; these polytopes are shown to admit facet descriptions that scale linearly with the stretching parameter N. Ehrhart theory then implies that each lattice-point enumerator is a quasi-polynomial in N, and the alternating sum of finitely many such quasi-polynomials (with N-independent signs and number of summands) remains quasi-polynomial. This establishes rationality of the ordinary generating function, proving Kirillov's 2004 conjecture. The manuscript also derives new counterexamples to the saturation conjecture for Schubert coefficients and outlines computational applications.
Significance. Resolving Kirillov's conjecture is a substantial contribution to Schubert calculus and algebraic combinatorics. The argument combines the pipe-dream formula with Ehrhart theory in a direct manner that avoids new ad-hoc parameters and relies on independently established results, thereby keeping circularity risk low. The additional counterexamples to saturation and the computational consequences are concrete bonuses. The central modeling step—that the relevant polytopes scale appropriately under stretching—is the only non-routine ingredient, and the manuscript appears to establish the necessary niceness properties.
minor comments (3)
- [Introduction] The introduction would be strengthened by a short concrete example: take a small permutation u in S_3, compute N*u for N=2 and N=3, and display the corresponding Schubert coefficient values for small N to illustrate the stretching operation and the quasi-polynomial behavior.
- [§4] In the section applying Ehrhart theory, explicitly record the degree and period of the quasi-polynomials that arise from the pipe-dream polytopes; this would make the eventual quasi-polynomial statement more quantitative and facilitate comparison with known degree bounds for Schubert coefficients.
- [§6] The computational applications paragraph would benefit from a brief complexity discussion or pseudocode for extracting the quasi-polynomial from the polytope description; without it the claim of 'computational applications' remains somewhat vague.
Simulated Author's Rebuttal
We thank the referee for their positive and accurate summary of our manuscript, which correctly identifies the main result on the eventual quasi-polynomiality of stretched Schubert coefficients, the proof strategy combining pipe dreams with Ehrhart theory, and the additional contributions regarding saturation counterexamples and computational applications. We are pleased that the referee views the resolution of Kirillov's conjecture as a substantial contribution and notes the low risk of circularity in the argument. The recommendation for minor revision is noted; since the report contains no specific major comments or requested changes, we interpret this as an invitation to incorporate any minor editorial or presentational improvements in the revised version.
Circularity Check
No significant circularity in the derivation chain
full rationale
The paper derives eventual quasi-polynomiality of f_{u,v,w}(N) by modeling the stretched Schubert coefficients via the pipe-dream formula as an alternating sum of lattice-point counts in polytopes whose facet inequalities scale linearly with the stretching parameter N. Standard Ehrhart theory for rational polytopes then supplies the quasi-polynomiality of each count (with N-independent signs and number of summands), so the alternating sum remains quasi-polynomial and its generating function is rational. Both the pipe-dream expression for Schubert coefficients and Ehrhart quasi-polynomials are independently established external results; the only non-routine step is the combinatorial verification that the relevant polytopes remain rational and scale linearly under stretching, which is proved directly rather than by self-definition, fitted parameters, or load-bearing self-citation. The argument is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Ehrhart theory: the number of integer points in a rational polytope dilated by N is a quasi-polynomial in N
- domain assumption Schubert coefficients admit a pipe-dream formula that expresses them as alternating sums of lattice points in explicitly described polytopes
Reference graph
Works this paper leans on
-
[1]
338 (2015), 93--102
Per Alexandersson, A combinatorial proof of the skew K-saturation theorem, Discrete Math. 338 (2015), 93--102
2015
-
[2]
28 (2019), 115--120
Per Alexandersson, Polytopes and large counterexamples, Exp.\ Math. 28 (2019), 115--120
2019
- [3]
-
[4]
David Anderson and William Fulton, Equivariant cohomology in algebraic geometry, Cambridge Univ.\ Press, Cambridge, UK, 2024, 446 pp
2024
-
[5]
Welleda Baldoni, Matthias Beck, Charles Cochet and Mich\`ele Vergne, Volume computation for polytopes and partition functions for classical root systems, Discrete Comput.\ Geom
M. Welleda Baldoni, Matthias Beck, Charles Cochet and Mich\`ele Vergne, Volume computation for polytopes and partition functions for classical root systems, Discrete Comput.\ Geom. 35 (2006), 551--595
2006
-
[6]
Alexander Barvinok, Integer points in polyhedra, EMS, Z\"urich, 2008, 191 pp
2008
-
[7]
Pommersheim, An algorithmic theory of lattice points in polyhedra, in New perspectives in algebraic combinatorics, Cambridge Univ
Alexander Barvinok and James E. Pommersheim, An algorithmic theory of lattice points in polyhedra, in New perspectives in algebraic combinatorics, Cambridge Univ. Press, Cambridge, UK, 1999, 91--147
1999
-
[8]
Integer-point enumeration in polyhedra, Springer, New York, 2007, 226 pp
Matthias Beck and Sinai Robins, Computing the continuous discretely. Integer-point enumeration in polyhedra, Springer, New York, 2007, 226 pp
2007
-
[9]
Beckenbach and Richard Bellman, Inequalities, Springer, Berlin, 1961, 198 pp
Edwin F. Beckenbach and Richard Bellman, Inequalities, Springer, Berlin, 1961, 198 pp
1961
-
[10]
2 (1993), 257--269
Nantel Bergeron and Sara Billey, RC-Graphs and Schubert Polynomials, Exp.\ Math. 2 (1993), 257--269
1993
-
[11]
Sara Billey, Kostant polynomials and the cohomology ring for G/B , Duke Math. J. 96 (1999), 205--224
1999
-
[12]
Sara Billey and Ravi Vakil, Intersections of S chubert varieties and other permutation array schemes, in Algorithms in algebraic geometry, Springer, New York, 2008, 21--54
2008
-
[13]
Mulmuley), Comp.\ Complexity 18 (2009), 577--600
Emmanuel Briand, Rosa Orellana and Mercedes Rosas, Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH (with an appendix by K. Mulmuley), Comp.\ Complexity 18 (2009), 577--600
2009
-
[14]
Buch, The saturation conjecture (after A
Anders S. Buch, The saturation conjecture (after A. Knutson and T. Tao). With an appendix by William Fulton, Enseign.\ Math. 46 (2000), 43--60
2000
-
[15]
Buch, Andrew Kresch, Kevin Purbhoo and Harry Tamvakis, The puzzle conjecture for the cohomology of two-step flag manifolds, J
Anders S. Buch, Andrew Kresch, Kevin Purbhoo and Harry Tamvakis, The puzzle conjecture for the cohomology of two-step flag manifolds, J. Algebraic Combin. 44 (2016), 973--1007
2016
-
[16]
Sam, Generalized Ehrhart Polynomials, Trans.\ AMS 364 (2012), 551--569
Sheng Chen, Nan Lil and Steven V. Sam, Generalized Ehrhart Polynomials, Trans.\ AMS 364 (2012), 551--569
2012
-
[17]
Matthias Christandl, Brent Doran and Michael Walter, Computing multiplicities of Lie group representations, in Proc.\ 53rd FOCS (2012), IEEE, 639--648
2012
-
[18]
Fomin, ukasz Kowalik, Daniel Lokshtanov, D\' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, Parameterized algorithms, Springer, Cham, 2015, 613 pp
Marek Cygan, Fedor V. Fomin, ukasz Kowalik, Daniel Lokshtanov, D\' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk and Saket Saurabh, Parameterized algorithms, Springer, Cham, 2015, 613 pp
2015
-
[19]
De Loera and Tyrrell B
Jes\'us A. De Loera and Tyrrell B. McAllister, On the computation of C lebsch-- G ordan coefficients and the dilation effect, Experiment.\ Math. 15 (2006), 7--19
2006
-
[20]
Algebra 255 (2002), 247--257
Harm Derksen and Jerzy Weyman, On the Littlewood–-Richardson polynomials, J. Algebra 255 (2002), 247--257
2002
- [21]
-
[22]
William Fulton, Young tableaux, Cambridge Univ.\ Press, Cambridge, UK, 1997, 260 pp
1997
-
[23]
William Fulton, Eigenvalues, invariant factors, highest weights, and Schubert calculus, Bull.\ AMS 37 (2000), 209--249
2000
-
[24]
Gelfand and Michael L
Izrail M. Gelfand and Michael L. Tsetlin, Finite-dimensional representations of the group of unimodular matrices (in Russian), Doklady Akad.\ Nauk SSSR 71 (1950), 825--828
1950
-
[25]
Gelfand and Andrey V
Izrail M. Gelfand and Andrey V. Zelevinsky, Polyhedra in a space of diagrams and the canonical basis in irreducible representations of gl _3 , Funct.\ Anal.\ Appl. 19 (1985), 141--144
1985
-
[26]
Christian Haase and Tyrrell B. McAllister, Quasi-period collapse and GL _n( Z) -scissors congruence in rational polytopes, in Integer points in polyhedra—geometry, number theory, representation theory, algebra, optimization, statistics, AMS, Providence, RI, 2008, 115--122
2008
-
[27]
Piechnik and Francisco Santos, Existence of unimodular triangulations --- positive results, Mem.\ AMS 270 (2021), no
Christian Haase, Andreas Paffenholz, Lindsay C. Piechnik and Francisco Santos, Existence of unimodular triangulations --- positive results, Mem.\ AMS 270 (2021), no. 1321, 83 pp
2021
-
[28]
Symbolic Comput
Nickolas Hein and Frank Sottile, A lifted square formulation for certifiable S chubert calculus, J. Symbolic Comput. 79 (2017), 594--608
2017
-
[29]
Mulmuley and Michael Walter, On vanishing of Kronecker coefficients, Comp.\ Complexity 26 (2017), 949--992
Christian Ikenmeyer, Ketan D. Mulmuley and Michael Walter, On vanishing of Kronecker coefficients, Comp.\ Complexity 26 (2017), 949--992
2017
-
[30]
King, Christophe Tollu and Fr\'ed\'eric Toumazet, Stretched Littlewood--Richardson and Kostka coefficients, in Symmetry in physics, AMS, Providence, RI, 2004, 99--112
Ronald C. King, Christophe Tollu and Fr\'ed\'eric Toumazet, Stretched Littlewood--Richardson and Kostka coefficients, in Symmetry in physics, AMS, Providence, RI, 2004, 99--112
2004
-
[31]
Kirillov, An invitation to the generalized saturation conjecture, Publ.\ RIMS 40 (2004), 1147--1239
Anatol N. Kirillov, An invitation to the generalized saturation conjecture, Publ.\ RIMS 40 (2004), 1147--1239
2004
-
[32]
71, Math.\ Soc.\ Japan, Tokyo, 2016, 185--209
Allen Knutson, Schubert calculus and puzzles, in Adv.\ Stud.\ Pure Math. 71, Math.\ Soc.\ Japan, Tokyo, 2016, 185--209
2016
-
[33]
VI, EMS Press, 4582--4605
Allen Knutson, Schubert calculus and quiver varieties, in Proc.\ ICM (2022, virtual), Vol. VI, EMS Press, 4582--4605
2022
-
[34]
AMS 12 (1999), 1055--1090
Allen Knutson and Terence Tao, The honeycomb model of _n( ) tensor products I: Proof of the saturation conjecture, Jour. AMS 12 (1999), 1055--1090
1999
- [35]
-
[36]
With an appendix by M
Shrawan Kumar, A survey of the additive eigenvalue problem. With an appendix by M. Kapovich, Transform.\ Groups 19 (2014), 1051--1148
2014
-
[37]
Ian G. Macdonald, Notes on Schubert polynomials, Publ.\ LaCIM, UQAM, Montreal, 1991, 116 pp.; available at tinyurl.com/382f7an7 http://www.math.uwaterloo.ca/ opecheni/macdonaldschubert.pdf
1991
-
[38]
Laurent Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS, Providence, RI, 2001, 167 pp
2001
-
[39]
29 (2022), no
Cara Monical, Benjamin Pankow and Alexander Yong, Reduced word enumeration, complexity, and randomization, Electron.\ J.\ Combin. 29 (2022), no. 2, Paper 2.46, 28 pp
2022
-
[40]
Ketan D. Mulmuley, Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry, preprint (2009, v4), 139 pp.; arXiv:0704.0229
work page Pith review arXiv 2009
-
[41]
Igor Pak, What is a combinatorial interpretation?, in Open Problems in Algebraic Combinatorics, AMS, Providence, RI, 2024, 191--260
2024
-
[42]
Igor Pak and Greta Panova, On the complexity of computing Kronecker coefficients, Comput.\ Complexity 26 (2017), 1--36
2017
-
[43]
R.\ Math.\ Acad.\ Sci.\ Paris 358 (2020), no
Igor Pak and Greta Panova, Breaking down the reduced Kronecker coefficients, C. R.\ Math.\ Acad.\ Sci.\ Paris 358 (2020), no. 4, 463--468
2020
- [44]
-
[45]
Igor Pak and Colleen Robichaux, Signed combinatorial interpretations in algebraic combinatorics, Algebraic Combinatorics 8 (2025), 495--519
2025
- [46]
- [47]
- [48]
-
[49]
Stanley, Chains in the Bruhat order, J.\ Algebraic Combin
Alexander Postnikov and Richard P. Stanley, Chains in the Bruhat order, J.\ Algebraic Combin. 29 (2009), 133--174
2009
-
[50]
Combin.\ Theory, Ser
Etienne Rassart, A polynomiality property for Littlewood--Richardson coefficients, J. Combin.\ Theory, Ser. A 107 (2004), 161--179
2004
-
[51]
Sam and Andrew Snowden, Proof of Stembridge's conjecture on stability of Kronecker coefficients, J
Steven V. Sam and Andrew Snowden, Proof of Stembridge's conjecture on stability of Kronecker coefficients, J. Algebraic Combin. 43 (2016), 1--10
2016
-
[52]
32 (2018), 173--190
Bobby Shen, Parametrizing an integer linear program by an integer, SIAM J.\ Discrete Math. 32 (2018), 173--190
2018
-
[53]
Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319
Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, in Mathematics: frontiers and perspectives, AMS, Providence, RI, 2000, 295--319
2000
- [54]
-
[55]
(2026), 12 pp
Ada Stelzer, Surprise polynomiality in algebraic combinatorics, to appear in Proc.\ 38th FPSAC Conf. (2026), 12 pp
2026
-
[56]
Stembridge, Generalized stability of Kronecker coefficients, preprint (2014), 27 pp.; available at https://tinyurl.com/5xecksf5 https://websites.umich.edu/ jrs/papers/kron.pdf
John R. Stembridge, Generalized stability of Kronecker coefficients, preprint (2014), 27 pp.; available at https://tinyurl.com/5xecksf5 https://websites.umich.edu/ jrs/papers/kron.pdf
2014
-
[57]
Combin.\ Theory, Ser
Bernd Sturmfels, On vector partition functions, J. Combin.\ Theory, Ser. A 72 (1995), 302--309
1995
-
[58]
162 (2025), 205--212
Warut Thawinrak, A short proof for the polynomiality of the stretched Littlewood--Richardson coefficients, Ars Combin. 162 (2025), 205--212
2025
-
[59]
Kevin Woods, The unreasonable ubiquitousness of quasi-polynomials, Electron.\ J. Combin. 21 (2014), no. 1, Paper 44, 23 pp
2014
-
[60]
Andrei Zelevinsky, Littlewood--Richardson semigroups, in New perspectives in algebraic combinatorics, Cambridge Univ.\ Press, Cambridge, UK, 1999, 337--345
1999
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.