Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation

Source abstract

The Ehrhart series of the $n$th Birkhoff polytope is $\sum_{r\geq0}H_n(r)z^r$, where $H_n(r)$ counts nonnegative integer $n\times 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 $m$th 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\geq5$. 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 $12$. The Birkhoff series for orders $10$--$12$ and the World Cup series for orders $9$--$12$ are tabulated in the appendices.