Metraipolis › archive › dc_1cd0f3335552

Polynomial-Time Lattice-Point Counting without Barvinok Decomposition — arXiv:2608.11709

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11709
License (as archived)
CC0-1.0
Archived
2026-10-19T05:47:42.016Z
SHA-256 of the archived text
fe405d328ad5f1cb16706c84d94a8f5697b74415d28374d01fd8c6c3737d02be
Stable URL of this page
https://metraipolis.com/documento/dc_1cd0f3335552

How to cite

Polynomial-Time Lattice-Point Counting without Barvinok Decomposition — arXiv:2608.11709 — arXiv (en), https://arxiv.org/abs/2608.11709 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1cd0f3335552 (Metraipolis archive dc_1cd0f3335552, sha256 fe405d328ad5f1cb16706c84d94a8f5697b74415d28374d01fd8c6c3737d02be)
BibTeX
@misc{dc1cd0f3335552,
  title = {Polynomial-Time Lattice-Point Counting without Barvinok Decomposition — arXiv:2608.11709},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11709},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1cd0f3335552; sha256 fe405d328ad5f1cb16706c84d94a8f5697b74415d28374d01fd8c6c3737d02be},
  year = {2026}
}

Archived text

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

By using constant term manipulations, we present the first polynomial-time algorithm for lattice-point counting in fixed dimension that does not rely on Barvinok's unimodular decomposition. Our method starts from partial fraction decompositions and root-of-unity formulas for the lattice-point generating function of a rational simplicial cone. By means of a residue-lattice argument based on Minkowski's theorem, we construct a short multiplier that enables an exact recursive reduction. Smith normal form is then used to normalize the resulting child terms and restore the recursive structure. These transformations are justified by algebraic identities involving roots of binomial equations, while the algorithm itself works with integer exponent data and requires no explicit root computations. More precisely, for a rational simplicial cone \(\mathcal K\) in fixed dimension \(d\), with dual cone \(\mathcal K^*\), the algorithm achieves recursion depth \(O_d(1+\log\log(2+\ind(\mathcal K^*)))\) and produces a signed sum of at most \((1+\log\ind(\mathcal K^*))^{O_d(1)}\) unimodular cone generating functions. The framework uniformly handles numerators that are Laurent polynomials, not merely monomials, thereby giving a polynomial-time algorithm for MacMahon's partition analysis when the dimension is fixed.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.11709 — 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-19T05:40:33.646Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).