Polynomial-Time Lattice-Point Counting without Barvinok Decomposition

Abstract

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 𝒦 in fixed dimension d, with dual cone 𝒦^*, the algorithm achieves recursion depth O_d(1+loglog(2+ind(𝒦^*))) and produces a signed sum of at most (1+logind(𝒦^*))^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.

Counting Integral Matrices with Given Cubic Characteristic Polynomial
Philipp Habegger
arXiv26 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
From Cell Decomposition to Motivic Integration, Hensel Minimality, and Point Counting
Raf Cluckers
arXiv7 Oct 2026PreprintCC BY 4.0Full textLogic & foundationsarXiv
Counting matrices with given characteristic polynomial
Tim Browning, Fabian Gundlach, Will Sawin
arXiv13 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
A Direct Polynomial Approach to Spectral Decomposition
Simon Bossoney, Marc Troyanov
arXiv31 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Eigensolvers for polynomial roots and tensor decomposition
Enrica Barrilli, Bernard Mourrain
arXiv14 Sep 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{xin2026polynomialtime,
  title = {{Polynomial-Time Lattice-Point Counting without Barvinok Decomposition}},
  author = {Guoce Xin and Zihao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2608.11709},
  eprint = {2608.11709},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.11709},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Polynomial-Time Lattice-Point Counting without Barvinok Decomposition
AU  - Guoce Xin
AU  - Zihao Zhang
PY  - 2026
DA  - 2026/10/06
PB  - arXiv
DO  - 10.48550/arxiv.2608.11709
UR  - https://arxiv.org/abs/2608.11709
AB  - 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 𝒦 in fixed dimension d, with dual cone 𝒦^*, the algorithm achieves recursion depth O_d(1+loglog(2+ind(𝒦^*))) and produces a signed sum of at most (1+logind(𝒦^*))^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.
ER  -

Abstract

Related

Cite