# ALGEBRAIC COMBINATORICS

A positive formula for the Ehrhart-like polynomials from root system chip-firing
Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1159-1196.

In earlier work in collaboration with Pavel Galashin and Thomas McConville we introduced a version of chip-firing for root systems. Our investigation of root system chip-firing led us to define certain polynomials analogous to Ehrhart polynomials of lattice polytopes, which we termed the symmetric and truncated Ehrhart-like polynomials. We conjectured that these polynomials have nonnegative integer coefficients. Here we affirm “half” of this positivity conjecture by providing a positive, combinatorial formula for the coefficients of the symmetric Ehrhart-like polynomials. This formula depends on a subtle integrality property of slices of permutohedra, and in turn a lemma concerning dilations of projections of root polytopes, which both may be of independent interest. We also discuss how our formula very naturally suggests a conjecture for the coefficients of the truncated Ehrhart-like polynomials that turns out to be false in general, but which may hold in some cases.

Revised: 2019-04-01
Accepted: 2019-04-08
Published online: 2019-12-04
DOI: https://doi.org/10.5802/alco.79
Classification: 17B22,  52B20
Keywords: root system, chip-firing, Ehrhart polynomial, permutohedron, zonotope, root polytope
@article{ALCO_2019__2_6_1159_0,
author = {Hopkins, Sam and Postnikov, Alexander},
title = {A positive formula for the Ehrhart-like polynomials from root system chip-firing},
journal = {Algebraic Combinatorics},
pages = {1159--1196},
publisher = {MathOA foundation},
volume = {2},
number = {6},
year = {2019},
doi = {10.5802/alco.79},
mrnumber = {4049842},
zbl = {07140429},
language = {en},
url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1159_0/}
}
Hopkins, Sam; Postnikov, Alexander. A positive formula for the Ehrhart-like polynomials from root system chip-firing. Algebraic Combinatorics, Volume 2 (2019) no. 6, pp. 1159-1196. doi : 10.5802/alco.79. https://alco.centre-mersenne.org/item/ALCO_2019__2_6_1159_0/

[1] Abe, Takuro; Terao, Hiroaki The freeness of Shi–Catalan arrangements, European J. Combin., Volume 32 (2011) no. 8, pp. 1191-1198 | Article | MR 2838007 | Zbl 1235.52035

[2] Athanasiadis, Christos A. Deformations of Coxeter hyperplane arrangements and their characteristic polynomials, Arrangements – Tokyo 1998 (Adv. Stud. Pure Math.) Volume 27, Kinokuniya, Tokyo, 2000, pp. 1-26 | MR 1796891 | Zbl 0976.32016

[3] Beck, Matthias; Robins, Sinai Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2015, xx+285 pages | Article | MR 3410115 | Zbl 1339.52002

[4] Björner, Anders; Brenti, Francesco Combinatorics of Coxeter groups, Graduate Texts in Mathematics, Volume 231, Springer, New York, 2005, xiv+363 pages | MR 2133266 | Zbl 1110.05001

[5] Bourbaki, Nicolas Lie groups and Lie algebras. Chapters 4–6, Elements of Mathematics (Berlin), Springer-Verlag, Berlin, 2002, xii+300 pages (Translated from the 1968 French original by Andrew Pressley) | MR 1890629 | Zbl 0983.17001

[6] Cellini, Paola; Marietti, Mario Root polytopes and Borel subalgebras, Int. Math. Res. Not. IMRN (2015) no. 12, pp. 4392-4420 | Article | MR 3356759 | Zbl 1337.17011

[7] Dyer, M. J.; Lehrer, G. I. Parabolic subgroup orbits on finite root systems, J. Pure Appl. Algebra, Volume 222 (2018) no. 12, pp. 3849-3857 | Article | MR 3818283 | Zbl 1398.20048

[8] Edelman, Paul H.; Reiner, Victor Free arrangements and rhombic tilings, Discrete Comput. Geom., Volume 15 (1996) no. 3, pp. 307-340 | Article | MR 1380397 | Zbl 0853.52013

[9] Ehrhart, E. Polynômes arithmétiques et méthode des polyèdres en combinatoire, International Series of Numerical Mathematics, Volume 35, Birkhäuser Verlag, Basel-Stuttgart, 1977, 165 pages | MR 0432556 | Zbl 0337.10019

[10] Galashin, Pavel; Hopkins, Sam; McConville, Thomas; Postnikov, Alexander Root system chip-firing I: Interval-firing (Forthcoming, Mathematische Zeitschrift) | Article | Zbl 07081703

[11] Galashin, Pavel; Hopkins, Sam; McConville, Thomas; Postnikov, Alexander Root system chip-firing II: Central-firing (2017) (Forthcoming, International Mathematics Research Notices, https://arxiv.org/abs/1708.04849)

[12] Garibaldi, Skip ${E}_{8}$, the most exceptional group, Bull. Amer. Math. Soc. (N.S.), Volume 53 (2016) no. 4, pp. 643-671 | Article | MR 3544263 | Zbl 1398.20062

[13] Hopkins, Sam; McConville, Thomas; Propp, James Sorting via chip-firing, Electron. J. Combin., Volume 24 (2017) no. 3, 20 pages | MR 3691530 | Zbl 1369.05148

[14] Humphreys, James E. Introduction to Lie algebras and representation theory, Graduate Texts in Mathematics, Volume 9, Springer-Verlag, New York-Berlin, 1972, xii+169 pages | MR 0323842 | Zbl 0254.17004

[15] Lam, Thomas; Postnikov, Alexander Alcoved Polytopes II, Lie Groups, Geometry, and Representation Theory: A Tribute to the Life and Work of Bertram Kostant, Springer International Publishing, Cham, 2018, pp. 253-272 | Article | Zbl 1414.52007

[16] Liu, Fu On Positivity of Ehrhart Polynomials, Recent Trends in Algebraic Combinatorics, Springer International Publishing, Cham, 2019, pp. 189-237 | Article | MR 3969575 | Zbl 07064989

[17] Macdonald, I. G. Polynomials associated with finite cell-complexes, J. London Math. Soc. (2), Volume 4 (1971), pp. 181-192 | Article | MR 0298542 | Zbl 0216.45205

[18] McMullen, Peter Valuations and Euler-type relations on certain classes of convex polytopes, Proc. London Math. Soc. (3), Volume 35 (1977) no. 1, pp. 113-135 | Article | MR 0448239 | Zbl 0353.52001

[19] McMullen, Peter Lattice invariant valuations on rational polytopes, Arch. Math., Volume 31 (1978/79) no. 1, pp. 509-516 | Article | MR 526617 | Zbl 0387.52007

[20] Mészáros, Karola Root polytopes, triangulations, and the subdivision algebra. I, Trans. Amer. Math. Soc., Volume 363 (2011) no. 8, pp. 4359-4382 | Article | MR 2792991 | Zbl 1233.05215

[21] Mészáros, Karola Root polytopes, triangulations, and the subdivision algebra, II, Trans. Amer. Math. Soc., Volume 363 (2011) no. 11, pp. 6111-6141 | Article | MR 2817421 | Zbl 1233.05216

[22] Oshima, Toshio A classification of subsystems of a root system (2006) (https://arxiv.org/abs/math/0611904)

[23] Postnikov, Alexander Permutohedra, associahedra, and beyond, Int. Math. Res. Not. IMRN (2009) no. 6, pp. 1026-1106 | Article | MR 2487491 | Zbl 1162.52007

[24] Postnikov, Alexander; Stanley, Richard P. Deformations of Coxeter hyperplane arrangements, J. Combin. Theory Ser. A, Volume 91 (2000) no. 1-2, pp. 544-597 (In memory of Gian-Carlo Rota) | Article | MR 1780038 | Zbl 0962.05004

[25] Sage-Combinat community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics, 2018 (http://combinat.sagemath.org)

[26] Sage Developers SageMath, the Sage Mathematics Software System (Version 8.2) (2018) (http://www.sagemath.org)

[27] Shephard, Geoffrey C. Combinatorial properties of associated zonotopes, Canad. J. Math., Volume 26 (1974) no. 2, pp. 302-321 | Article | MR 0362054 | Zbl 0287.52005

[28] Stanley, Richard P. Decompositions of rational convex polytopes, Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978) (Ann. Discrete Math.) Volume 6, North Holland, 1980, pp. 333-342 | MR 593545 | Zbl 0812.52012

[29] Stanley, Richard P. A zonotope associated with graphical degree sequences, Applied geometry and discrete mathematics (DIMACS Ser. Discrete Math. Theoret. Comput. Sci.) Volume 4, Amer. Math. Soc., Providence, RI, 1991, pp. 555-570 | MR 1116376 | Zbl 0737.05057

[30] Stanley, Richard P. Enumerative combinatorics. Volume 1, Cambridge Studies in Advanced Mathematics, Volume 49, Cambridge University Press, Cambridge, 2012, xiv+626 pages | MR 2868112 | Zbl 1247.05003

[31] Stembridge, John R. The partial order of dominant weights, Adv. Math., Volume 136 (1998) no. 2, pp. 340-364 | Article | MR 1626860 | Zbl 0916.06001

[32] Terao, Hiroaki Multiderivations of Coxeter arrangements, Invent. Math., Volume 148 (2002) no. 3, pp. 659-674 | Article | MR 1908063 | Zbl 1032.52013

[33] Yoshinaga, Masahiko Characterization of a free arrangement and conjecture of Edelman and Reiner, Invent. Math., Volume 157 (2004) no. 2, pp. 449-454 | Article | MR 2077250 | Zbl 1113.52039

[34] Yoshinaga, Masahiko Worpitzky partitions for root systems and characteristic quasi-polynomials, Tohoku Math. J. (2), Volume 70 (2018) no. 1, pp. 39-63 | Article | MR 3772805 | Zbl 1390.52026