DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2026.88

Integer Points in Dilates of Polytopes

Authors: Shubhangi Saraf and Narmada Varadarajan

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

In this paper we study how the number of integer points in a polytope grows as we dilate the polytope. We prove new and essentially tight bounds on this quantity by specifically studying dilates of the Hadamard polytope. The motivation for studying this question comes from the question of understanding the maximal number of monomials in a factor of a multivariate polynomial of s monomials. A recent result by Bhargava, Saraf and Volkovich [Bhargava et al., 2020] showed that if f is an n-variate polynomial, where each variable has degree d, and f has s monomials, then any factor of f has at most s^{O(d² log n)} monomials. The key technical ingredient of their proof was to show that any polytope with s vertices, where each vertex lies in {0,..,d}ⁿ can have at most s^{O(d² log n)} integer points. The precise dependence on d of the number of integer points was left open. We show that this bound, and in particular the dependence on d is essentially tight by studying dilates of the Hadamard polytope and proving new lower bounds on its number of integer points.

Cite as

Shubhangi Saraf and Narmada Varadarajan. Integer Points in Dilates of Polytopes. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 88:1-88:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{saraf_et_al:LIPIcs.SoCG.2026.88,
  author =	{Saraf, Shubhangi and Varadarajan, Narmada},
  title =	{{Integer Points in Dilates of Polytopes}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{88:1--88:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.88},
  URN =		{urn:nbn:de:0030-drops-258948},
  doi =		{10.4230/LIPIcs.SoCG.2026.88},
  annote =	{Keywords: Computational geometry, Complexity theory, Integer polytopes}
}

Search Results

Documents authored by Varadarajan, Narmada

Integer Points in Dilates of Polytopes

Abstract

Cite as

Thanks for your feedback!

Could not send message