Metraipolis › archive › dc_fcabcf56b015

Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation — arXiv:2609.25863

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.25863
License (as archived)
CC0-1.0
Archived
2026-10-08T15:55:56.783Z
SHA-256 of the archived text
f71b872b9464f65c5ae309e5b7032dec3342046a932948d9fe38a87f22b1bbf3
Stable URL of this page
https://metraipolis.com/documento/dc_fcabcf56b015

How to cite

Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation — arXiv:2609.25863 — arXiv (en), https://arxiv.org/abs/2609.25863 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fcabcf56b015 (Metraipolis archive dc_fcabcf56b015, sha256 f71b872b9464f65c5ae309e5b7032dec3342046a932948d9fe38a87f22b1bbf3)
BibTeX
@misc{dcfcabcf56b015,
  title = {Exact Ehrhart Series of Birkhoff Polytopes via Constant Terms and Finite-Field Evaluation — arXiv:2609.25863},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.25863},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fcabcf56b015; sha256 f71b872b9464f65c5ae309e5b7032dec3342046a932948d9fe38a87f22b1bbf3},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25863. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mu_a$, the computation uses a generalized Todd coefficient of degree $\mu_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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.25863 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T15:16:21.683Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).