Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation
Abstract
The Ehrhart series of the nth Birkhoff polytope is ∑r≥0Hn(r)zr, where Hn(r) counts nonnegative integer n× n matrices whose row and column sums all equal r. We present an exact method for computing this series using constant terms and finite fields. A root filter expresses Hn(r) as a weighted sum of the values hr(M)n, where hr is the complete homogeneous symmetric polynomial and M ranges over multisets of mth roots of unity with m=r+1. Constant-term cancellation reduces the evaluation of hr(M) to a sum over repeated elements a of M. For a particular a of multiplicity μa, the computation uses a generalized Todd coefficient of degree μa−2. Sums of hr(M)n over selected multiplicity classes are handled using symmetric function techniques. Together with the remaining individual evaluations, this gives On(mn−5+m4) field operations for each admissible prime and fixed n≥5. An explicit bound and the Chinese remainder theorem recover the integer counts, and Ehrhart symmetry determines the full series. The same method applies to the World Cup problem, which counts the same matrices with diagonal entries required to be $0$. We prove correctness and compute complete series for both families through order $13$. The Birkhoff series for orders $10−−13$ and the World Cup series for orders $9−−13$ are tabulated in the appendices.
Related
- Equivariant Ehrhart series for rational simplices and rational cross-polytopes
- Ehrhart polynomials of cyclic polytopes as averages of zonotope Ehrhart polynomials
- Ehrhart positivity of smooth polytopes with few facets
- Ehrhart Properties under Operations on Lattice Polytopes
- The equivariant Ehrhart theory of polytopes with order-two symmetries: Part II
BibTeX
@misc{jiang2026exact,
title = {{Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation}},
author = {Xinru Jiang and Guoce Xin and Chen Zhang and Yueming Zhong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.25863},
eprint = {2609.25863},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25863},
}
RIS
TY - UNPB
TI - Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation
AU - Xinru Jiang
AU - Guoce Xin
AU - Chen Zhang
AU - Yueming Zhong
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2609.25863
UR - https://arxiv.org/abs/2609.25863
AB - The Ehrhart series of the nth Birkhoff polytope is ∑_r≥0H_n(r)z^r, where H_n(r) counts nonnegative integer n× n matrices whose row and column sums all equal r. We present an exact method for computing this series using constant terms and finite fields. A root filter expresses H_n(r) as a weighted sum of the values h_r(M)^n, where h_r is the complete homogeneous symmetric polynomial and M ranges over multisets of mth roots of unity with m=r+1. Constant-term cancellation reduces the evaluation of h_r(M) to a sum over repeated elements a of M. For a particular a of multiplicity μ_a, the computation uses a generalized Todd coefficient of degree μ_a−2. Sums of h_r(M)^n over selected multiplicity classes are handled using symmetric function techniques. Together with the remaining individual evaluations, this gives O_n(m^n−5+m^4) field operations for each admissible prime and fixed n≥5. An explicit bound and the Chinese remainder theorem recover the integer counts, and Ehrhart symmetry determines the full series. The same method applies to the World Cup problem, which counts the same matrices with diagonal entries required to be $0$. We prove correctness and compute complete series for both families through order $13$. The Birkhoff series for orders $10−−13$ and the World Cup series for orders $9−−13$ are tabulated in the appendices.
ER -