Integer Points in Dilates of Polytopes

Saraf, Shubhangi; Varadarajan, Narmada

doi:10.4230/LIPIcs.SoCG.2026.88

Integer Points in Dilates of Polytopes

Shubhangi Saraf

University of Toronto, Canada Narmada Varadarajan

University of Toronto, Canada

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 [4] 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^{2}\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\}^{n}$ can have at most $s^{O(d^{2}\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.

Keywords and phrases:

Computational geometry, Complexity theory, Integer polytopes

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

Related Version:

Full Version: https://arxiv.org/pdf/2510.16481

Acknowledgements:

We thank the reviewers for their helpful suggestions.

Funding:

Research partially supported by the McLean Award and an NSERC Discovery Grant.

DOI:

10.4230/LIPIcs.SoCG.2026.88

Event:

42nd International Symposium on Computational Geometry (SoCG 2026)

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Integer polytopes play a starring role in several areas of mathematics, and have recently found very interesting applications in theoretical computer science. In particular, the problem of counting integer points in polytopes lies at the intersection of combinatorics and convex geometry, with applications in algebraic geometry [7, 8], number theory [3, 6], optimization [2, 1], cryptography [10], and algebraic complexity theory [4], just to name a few. Perhaps the most celebrated result on this topic is the Ehrhart polynomial: given an integer polytope $P\subseteq\mathbb{R}^{n}$ , the number of integer points in its dilate, $|dP\cap\mathbb{Z}^{n}|$ , is a polynomial in $d$ [9]. When $P$ is an $n$ -dimensional polytope, the leading term of its Ehrhart polynomial is $\mathrm{vol}(P)d^{n}$ , which is a good approximation to the number of integer points for large values of $d$ . However, the coefficients of the Ehrhart polynomial are notoriously difficult to compute (see, for example, [11] for examples of polytopes with negative Ehrhart coefficients), so we have little information about integer points when the dilation factor $d$ is much smaller than the dimension $n$ .

Motivation from algebraic complexity theory

Our interest in estimating $|dP\cap\mathbb{Z}^{n}|$ when $d$ is smaller than $n$ comes from the problem of sparse polynomial factorization in complexity theory. A multivariate polynomial $f\in\mathbb{F}[X_{1},\dots,X_{n}]$ where each variable $X_{i}$ appears with degree $\leq d$ is sparse if it only has $\mathrm{poly}(n)$ monomials. Polynomial factorization is a fundamental question in computational algebra, and sparse polynomial factorization is a special case that has been studied for several decades now [4, 5, 13]. The first randomized algorithm for sparse polynomial factorization exhibited a dependence on the sparsity of the factors of the polynomial [13], which raised the natural question: do factors of sparse polynomials have to be sparse?

We know that this is not true in general: if $g$ is a factor of some polynomial $f$ , there is no polynomial upper bound for the number of monomials of $g$ in terms of the number of monomials of $f$ . In characteristic $0$ , we have the counterexample $f=\prod_{i=1}^{n}(X_{i}^{d}-Y_{i}^{d})$ and $g=\prod_{i=1}^{n}(X_{i}^{d-1}+X_{i}^{d-2}Y_{i}+\dots+Y_{i}^{d-1})$ . Here, $f$ has $2^{n}$ monomials, but $g$ is a factor of $f$ with $d^{n}$ monomials. In characteristic $p$ , this gap can be more stark. Consider $f=\sum_{i=1}^{n}X_{i}^{p}$ and $g=\left(\sum_{i=1}^{n}X_{i}\right)^{\lfloor p/2\rfloor}$ , so $f$ has $n$ monomials, but $g$ is a factor of $f$ with at least $n^{p/2}$ monomials. In general, we do not have know better than the trivial upper bound of $d^{n}$ for the number of monomials in a factor of a sparse polynomial. However, note that in the setting where we assume that the individual degree $d$ is an absolute constant and $n$ can be arbitrarily large, these two counterexamples no longer exhibit significant sparsity gaps.

The current best-known bound for sparse factorization in this setting is due to [4], who show that if $f$ has $s$ monomials and $g$ is a factor of $f$ , then $g$ has at most $s^{O(d^{2}\log n)}$ monomials. The key technique of their proof is to reduce the problem of counting monomials in $f$ and $g$ into one of counting integer points in their Newton polytopes. In this paper we further study the problem of counting integer points in polytopes, since a better upper bound there would directly imply a better bound for the factoring problem. Unfortunately, our results indicate that there is no better upper bound for polytopes, so any attempt to improve the bound for sparsity will require a new approach.

Connections to studying dilates of polytopes

The key technique to proving the upper bound of $s^{O(d^{2}\log n)}$ in [4] is to study integer points in polytopes. In particular if $f=g\times h$ , then one can show that the Newton polytope of $f$ is the Minkowski sum of the Newton polytopes of $g$ and $h$ . The high-level idea in the proof is to show the following: If $g$ has too many monomials, then the Newton polytope of $g$ must necessarily have many vertices. This can then be used to show that the Newton polytope of $f$ must also have many vertices, hence $f$ must have many monomials. Their main technical contribution is to show that any polytope with $s$ vertices, where each vertex lies in $[-d,+d]^{n}$ , can have at most $s^{O(d^{2}\log n)}$ integer points. The precise dependence on $d$ of the number of integer points was left open.

The main goal of our paper is to understand if this bound for integer points in polytopes is tight. Saptharishi observed that the $\log n$ in the exponent of the bound is necessary (see [4] for a proof of this) by counting integer points in Hadamard polytopes, a class of simplices with vertices in $\{-1,1\}^{n}$ . Specifically, he shows that the number of integer points in the Hadamard polytope is at least $n^{\Omega(\log n)}$ . In this paper, we show that the dependence of $d^{2}$ in the exponent is also essentially tight by studying dilates of the Hadamard polytope.

An astute reader may recognize the Hadamard polytope as the extremal solution to Hadamard’s maximal determinant problem: the parallelepiped spanned by its vertices maximizes volume among all parallelepipeds with vertices in $\{-1,1\}^{n}$ . We expect that the Hadamard polytope should also maximize the number of integer points – a discrete analog of volume – among all simplices with vertices in $\{-1,1\}^{n}$ . This is the heuristic that motivates us to study the Hadamard polytope as the “worst-case simplex” for our problem.

In the case when $s=\mathrm{poly}(n)$ (as with factors of sparse polynomials), we can reduce our problem about counting integer points in polytopes in $[-d,d]^{n}$ to counting integer points in dilates of polytopes as follows. First, by Carathéodory’s theorem, each vertex of $P$ is a convex combination of at most $n+1$ points of $\{-d,d\}^{n}$ . Replacing the vertices of $P$ with these points, we obtain a polytope $P_{d}$ containing $P$ that still has $\mathrm{poly}(n)$ vertices, but they now lie in $\{-d,d\}^{n}$ . So, $P_{0}=\frac{1}{d}P_{d}$ is an integer polytope with vertices in $\{-1,1\}^{n}$ and $|dP_{0}\cap\mathbb{Z}^{n}|\geq|P\cap\mathbb{Z}^{n}|$ .

Our contribution in this paper is to provide lower bounds for the number of integer points in the Hadamard polytope. Our first main result is an elegant algebraic characterization of the integer points in the Hadamard polytope by constructing an explicit bijection with affine subspaces of $\mathbb{F}_{2}^{\log n}$ . This underpins part of our second main result: a lower bound for the number of integer points in small dilates. To lower bound the points in larger dilates, we use the probabilistic method. These bounds show that both the dependences on $d^{2}$ and on $\log n$ in the bound $|dP\cap\mathbb{Z}^{n}|\leq|V(P)|^{O(d^{2}\log n)}$ are necessary.

2 Main results

Let $n=2^{m}$ for some $m\in\mathbb{N}$ . The $n\times n$ Hadamard matrix $H$ has its rows and columns indexed by elements of the vector space $\mathbb{F}_{2}^{m}$ :

\displaystyle H(a,b)

\displaystyle=(-1)^{\langle a,b\rangle},

where $\langle a,b\rangle$ is the standard dot product on $\mathbb{F}_{2}^{m}$ .

Definition 1.

The Hadamard polytope $P_{\mathrm{Had}}\subset\mathbb{R}^{n}$ is the convex hull of the column vectors of $H$ .

The columns of $H$ are linearly independent so they form the vertices of $P_{\mathrm{Had}}$ ; the Hadamard polytope is an $(n-1)$ –simplex with vertices in $\{-1,1\}^{n}$ . The lower bound $|P_{\mathrm{Had}}\cap\mathbb{Z}^{n}|\geq n^{\Omega(\log n)}$ was first observed by Ramprasad Saptharishi and appears in the paper [4]. Our contribution is a matching upper bound on $|P_{\mathrm{Had}}\cap\mathbb{Z}^{n}|$ through a complete characterization of all integer points in the Hadamard polytope using the vector space structure of $F_{2}^{m}$ . This characterization will also be useful when we study integer points in dilates of $P_{\mathrm{Had}}$ .

First, some notation: let $\{h_{a}:a\in\mathbb{F}_{2}^{m}\}$ be the set of column vectors of the Hadamard matrix $H$ , i.e. the vertices of the Hadamard polytope $P_{\mathrm{Had}}$ . We can also identify the coordinates of $\mathbb{R}^{n}$ with vectors in $\mathbb{F}_{2}^{m}$ , with the convention that the first coordinate in $\mathbb{R}^{n}$ corresponds to the zero vector in $\mathbb{F}_{2}^{m}$ . For every $a\in\mathbb{F}_{2}^{m}$ and $v\in\mathbb{R}^{n}$ , let $v(a)$ denote the $a$ th coordinate of $v$ in the standard basis, and

\displaystyle\mathrm{supp}(v)=\{a\in\mathbb{F}_{2}^{m}:v(a)\neq 0\}

We also know that every point $v\in P_{\mathrm{Had}}$ can be expressed as a convex combination $v=\sum_{a\in\mathbb{F}_{2}^{m}}t_{a}h_{a}$ . Since the vectors $\{h_{a}:a\in\mathbb{F}_{2}^{m}\}$ are linearly independent, this expression is unique, and we can define

\displaystyle T(v)

\displaystyle=\{a\in\mathbb{F}_{2}^{m}:t_{a}\neq 0\}.

This can also be thought of as the support of $v$ in the basis $\{h_{a}:a\in\mathbb{F}_{2}^{m}\}$ .

Statements of main results

Theorem 2.

For every $v\in P_{\mathrm{Had}}\cap\mathbb{Z}^{n}$ , $\mathrm{supp}(v)$ is a subspace of $\mathbb{F}_{2}^{m}$ . Further, $T(v)=\mathrm{supp}(v)^{\perp}+b$ for some $b\in\mathbb{F}_{2}^{m}$ , and

\displaystyle v

\displaystyle=\frac{1}{|T(v)|}\sum_{c\in T(v)}h_{c}

is actually a uniform linear combination of vertices.

Notice that this theorem is a combinatorial correspondence between affine subspaces of $\mathbb{F}_{2}^{m}$ and integer points in $P_{\mathrm{Had}}$ . That is, every affine subspace $S\subseteq\mathbb{F}_{2}^{m}$ , let $v_{S}$ be the uniform convex combination of the vertices of $P_{\mathrm{Had}}$ corresponding to the points of $S$ . In other words, $v_{S}$ is the barycenter of the corresponding face of $P_{\mathrm{Had}}$ . Then, the map $S\to v_{S}$ is a bijection between affine subspaces of $\mathbb{F}_{2}^{m}$ and integer points in $P_{\mathrm{Had}}$ .

Corollary 3.

The number of integer points in $P_{\mathrm{Had}}$ is $|P_{\mathrm{Had}}\cap\mathbb{Z}^{n}|=n^{\Theta(\log n)}$ .

Theorem 4.

For any $d<n\log n$ and fixed $0<\varepsilon<1/2$ , the number of integer points in the dilate $dP_{\mathrm{Had}}$ is lower bounded by

\displaystyle|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|\geq\begin{cases}n^{\Omega(d% \log n)},&d\leq\frac{\log n}{4};\\ n^{\Omega(\log^{2}n)},&\frac{\log n}{4}\leq d\leq\log^{1.5}n\\ n^{2\varepsilon d^{2}/\log n},&\log^{1.5}n\leq d\leq(n\log n)^{1/2-\varepsilon% };\\ \left(d^{2\varepsilon}/4\right)^{n},&(n\log n)^{1/2+\varepsilon}\leq d<n\log n% .\end{cases}

Proofs of main results

Proof of Theorem 2.

First, we need to show that $\mathrm{supp}(v)$ is a subspace of $\mathbb{F}_{2}^{m}$ . We will actually show something stronger: if $v(a)\neq 0$ and $v(b)\neq 0$ , then $v(a+b)=v(a)v(b)$ . Note that since $v$ is an integer point in $P_{\mathrm{Had}}\subset[-1,1]^{n}$ , its coordinates actually lie in $\{-1,0,1\}^{n}$ . So, the three cases we need to consider for our proof are: $v(a)=v(b)=1$ ; $v(a)=v(b)=-1$ ; and $v(a)=1$ , $v(b)=-1$ . We will write out the details for the case when $v(a)=v(b)=1$ , and the other cases will follow a similar computation.

Since $v$ is a convex combination of the vertices of $P_{\mathrm{Had}}$ , we can write it as $v=\sum_{c\in\mathbb{F}_{2}^{m}}t_{c}h_{c}$ , for some nonnegative real numbers $(t_{c})_{c\in\mathbb{F}_{2}^{m}}$ that satisfy $\sum_{c\in\mathbb{F}_{2}^{m}}t_{c}=1$ . From the definition of the Hadamard matrix $H$ , we get the following identities for the coordinates $a,b\in\mathbb{F}_{2}^{m}$ ,

	$\displaystyle v(a)$	$\displaystyle=\sum_{c\in\mathbb{F}_{2}^{m}}t_{c}h_{c}(a)=\sum_{c\in\mathbb{F}_% {2}^{m}}(-1)^{\langle c,a\rangle}t_{c}=\sum_{c\perp a}t_{c}-\sum_{c\not\perp a% }t_{c},$
	$\displaystyle v(b)$	$\displaystyle=\sum_{c\in\mathbb{F}_{2}^{m}}t_{c}h_{c}(b)=\sum_{c\in\mathbb{F}_% {2}^{m}}(-1)^{\langle c,b\rangle}t_{c}=\sum_{c\perp b}t_{c}-\sum_{c\not\perp b% }t_{c}.$

Define

\displaystyle s_{ab}=\sum_{c\perp a,c\perp b}t_{c};\quad s_{a}=\sum_{c\perp a,% c\not\perp b}t_{c};\quad s_{b}=\sum_{c\not\perp a,c\perp b}t_{c};\quad s_{0}=% \sum_{c\not\perp a,c\not\perp b}t_{c}.

This allows us to rewrite our identity for $v(a)$ as

\displaystyle v(a)

\displaystyle=s_{ab}+s_{a}-s_{b}-s_{0}.

A similar identity for $v(b)$ and the identity $\sum_{c\in\mathbb{F}_{2}^{m}}t_{c}=1$ gives us the system of linear equations

	$\displaystyle s_{ab}+s_{a}-s_{b}-s_{0}$	$\displaystyle=v(a)=1$
	$\displaystyle s_{ab}-s_{a}+s_{b}-s_{0}$	$\displaystyle=v(b)=1$
	$\displaystyle s_{ab}+s_{a}+s_{b}+s_{0}$	$\displaystyle=1$

The general solution to this system has the form

	$\displaystyle s_{ab}-s_{0}$	$\displaystyle=1$
	$\displaystyle s_{a}+s_{b}$	$\displaystyle=0$
	$\displaystyle s_{b}+s_{0}$	$\displaystyle=0.$

Since each of $s_{ab},s_{a},s_{b},$ and $s_{0}$ must be nonnegative, this yields a unique solution $s_{ab}=1,s_{a}=s_{b}=s_{0}=0$ . So,

	$\displaystyle v(a+b)$	$\displaystyle=\sum_{c\in\mathbb{F}_{2}^{m}}(-1)^{\langle a+b,c\rangle}t_{c}$
		$\displaystyle=\sum_{c\perp a,c\perp b}t_{c}-\sum_{c\perp a,c\not\perp b}t_{c}-% \sum_{c\not\perp a,c\perp b}t_{c}+\sum_{c\not\perp a,c\not\perp b}t_{c}$
		$\displaystyle=s_{ab}-s_{a}-s_{b}+s_{0}$
		$\displaystyle=1=v(a)v(b).$

The argument for the other cases follows similarly: we set up a system of equations in the variables $s_{ab},s_{b},s_{a},s_{0}$ that has a unique solution subject to nonnegativity. Computing the value of $v(a+b)$ for this unique solution shows that $v(a+b)=v(a)v(b)$ . This shows not only that $\mathrm{supp}(v)$ is a basis, but also that the entries of $v$ are determined by their values on a basis of $\mathrm{supp}(v)$ .

Now, let $b_{1},\dots,b_{k}\in\mathbb{F}_{2}^{m}$ be a basis for $\mathrm{supp}(v)$ , and choose $\varepsilon_{i}\in\{0,1\}$ so that $v(b_{i})=(-1)^{\varepsilon_{i}}$ for each $i=1,\dots,k$ . Consider the linear map $\mathbb{F}_{2}^{m}\to\mathrm{supp}(v)$ that sends $c\in\mathbb{F}_{2}^{m}$ to $\langle b_{1},c\rangle b_{1}+\dots+\langle b_{k},c\rangle b_{k}\in\mathrm{supp% }(v)$ . The kernel of this map is exactly $\mathrm{supp}(v)^{\perp}$ , so its range must be all of $\mathrm{supp}(v)$ . In particular, there is some $b\in\mathbb{F}_{2}^{m}$ whose image under this map is $\varepsilon_{1}b_{1}+\dots+\varepsilon_{k}b_{k}$ . So, $v(b_{i})=(-1)^{\langle b_{i},b\rangle}$ for each $i=1,\dots,k$ . For any $a\in\mathrm{supp}(v)$ , we know that $a=\sum_{i\in I}b_{i}$ for some $I\subseteq[k]$ , so

\displaystyle v(a)=\prod_{i\in I}v(b_{i})=(-1)^{\sum_{i\in I}\langle b_{i},b% \rangle}=(-1)^{\langle a,b\rangle}.

We claim that $T(v)=\mathrm{supp}(v)^{\perp}+b$ for this vector $b$ .

Define the vector $v^{\prime}\in\mathbb{F}_{2}^{m}$ by

\displaystyle v^{\prime}

\displaystyle=\frac{1}{\left|\mathrm{supp}(v)^{\perp}\right|}\sum_{c\in\mathrm% {supp}(v)^{\perp}+b}h_{c}.

We will show that $v^{\prime}=v$ by showing that $v^{\prime}(a)=v(a)$ for every coordinate $a\in\mathbb{F}_{2}^{m}$ .

First, for each $a\in\mathrm{supp}(v)$ and $c\in\mathrm{supp}(v)^{\perp}+b$ , we have that $\langle a,c\rangle=\langle a,b\rangle$ . So,

	$\displaystyle v^{\prime}(a)$	$\displaystyle=\frac{1}{\|\mathrm{supp}(v)^{\perp}\|}\sum_{c\in\mathrm{supp}(v)^{% \perp}+b}h_{c}(a)$
		$\displaystyle=\frac{1}{\|\mathrm{supp}(v)^{\perp}\|}\sum_{c\in\mathrm{supp}(v)^{% \perp}+b}(-1)^{\langle a,c\rangle}$
		$\displaystyle=(-1)^{\langle a,b\rangle}$
		$\displaystyle=v(a).$

Next, for each $a\notin\mathrm{supp}(v)$ , the $\mathbb{F}_{2}$ -linear map from $\mathrm{supp}(v)^{\perp}\to\{0,1\}$ that sends $c\in\mathrm{supp}(v)^{\perp}$ to $\langle a,c\rangle$ is not identically zero. So, the size of the preimage of $0$ under this map is equal to the size of the preimage of $1$ . This property still holds when we consider the translate $\mathrm{supp}(v)^{\perp}+b$ : the dot product $\langle a,c\rangle$ is $0$ for exactly half the vectors $c\in\mathrm{supp}(v)^{\perp}+b$ , and is $1$ for the other half. Thus, the average of $h_{c}(a)$ over all $c\in\mathrm{supp}(v)^{\perp}+b$ is zero, so

\displaystyle v^{\prime}(a)=\frac{1}{|\mathrm{supp}(v)^{\perp}|}\sum_{c\in% \mathrm{supp}(v)^{\perp}+b}(-1)^{\langle a,c\rangle}=0=v(a),

since $a\notin\mathrm{supp}(v)$ . This shows that $v$ does indeed have the form we claimed, with $T(v)=\mathrm{supp}(v)^{\perp}+b$ and

\displaystyle v=\frac{1}{|T(v)|}\sum_{c\in T(v)}h_{c}

$\hfill\blacktriangleleft$

Proof of Corollary 3.

Note again that the lower bound $|P_{\mathrm{Had}}\cap\mathbb{Z}^{n}|=n^{\Omega(\log n)}$ was already known by Saptharishi’s contribution to [4]; we will provide a matching upper bound of $n^{O(\log n)}$ . By Theorem 2, integer points of $P_{\mathrm{Had}}\cap\mathbb{Z}^{n}$ are in one-to-one correspondence with affine subspaces of $\mathbb{F}_{2}^{m}$ . Any $k$ -dimensional subspace $V\subseteq\mathbb{F}_{2}^{m}$ has exactly $2^{m-k}$ corresponding affine subspaces, and there are exactly ${m\brack k}_{2}$ (the Gaussian binomial coefficient) subspaces of dimension $k$ . So, using the upper bound ${m\brack k}_{2}\leq 2^{4m^{2}}$ (see, for example, [12] for a proof of this bound),

|P_{\mathrm{Had}}\cap\mathbb{Z}^{n}|=\sum_{k=0}^{m}2^{m-k}{m\brack k}_{2}\leq(% m+1)2^{m+4m^{2}}=n^{O(\log n)},

which completes the proof. $\hfill\blacktriangleleft$

Now we are ready to prove our main theorem: lower bounding the growth of integer points in the dilates $dP_{\mathrm{Had}}$ .

Proof of Theorem 4.

Case 1.

$d\leq(\log n)/4$ .

Let us introduce some more notation for our counting argument. We will show that there are $n^{\Omega(d\log n)}$ distinct sets of $d$ integer points in $P_{\mathrm{Had}}$ whose sums are all distinct in $dP_{\mathrm{Had}}$ . For $v\in P_{\mathrm{Had}}\cap\mathbb{Z}^{n}$ , define the exponent of $v$ as $\exp(v)=\dim(\mathrm{supp}(v)^{\perp})$ , so $|T(v)|=2^{\exp(v)}$ , and

\displaystyle v

\displaystyle=\frac{1}{2^{\exp(v)}}\sum_{a\in T(v)}h_{a}.

Let $t_{a}(v)$ be $2^{-\exp(v)}$ if $a\in T(v)$ , and $0$ otherwise; that is, $t_{a}(v)$ is the coefficient of the vertex $h_{a}$ in the convex combination for $v$ . Look at all sets $\{v_{1},\dots,v_{d}\}$ such that

(i)

$T(v_{i})$ is a subspace, i.e. $T(v_{i})=\mathrm{supp}(v_{i})^{\perp}$ ;
(ii)

$\frac{\log n}{2}-d<\exp(v_{i})<\frac{\log n}{2}+d$ ;
(iii)

$\exp(v_{i})\neq\exp(v_{j})$ if $i\neq j$ .

Since $d\leq\frac{\log n}{4}$ , for $n$ large enough, the number of subspaces of $\mathbb{F}_{2}^{\log n}$ with dimension $k$ for some $k\in\left(\frac{\log n}{2}-d,\frac{\log n}{2}+d\right)$ is ${\log n\brack k}_{2}\geq 2^{k(\log n-k)}=n^{\Omega(\log n)}$ . So, the number of choices for the set of subspaces $\{T(v_{1}),\dots,T(v_{d})\}$ with distinct exponents in $\left(\frac{\log n}{2}-d,\frac{\log n}{2}+d\right)$ is $n^{\Omega(d\log n)}$ . We will now show that each set $\{v_{1},\dots,v_{d}\}$ satisfying these properties produces a distinct point in $dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}$ , proving the lower bound $|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|\geq n^{\Omega(d\log n)}.$

Now, suppose $\{v_{1},\dots,v_{d}\}$ and $\{u_{1},\dots,u_{d}\}$ are two distinct sets satisfying the above conditions. And suppose for contradiction that $\sum_{i}v_{i}=\sum_{i}u_{i}$ . Expanding this in terms of the vertices of $P_{\mathrm{Had}}$ , we get

\displaystyle\sum_{i=1}^{d}\sum_{a\in\mathbb{F}_{2}^{m}}t_{a}(v_{i})h_{a}

\displaystyle=\sum_{i=1}^{d}\sum_{a\in\mathbb{F}_{2}^{m}}t_{a}(u_{i})h_{a}

Since the vertices of $P_{\mathrm{Had}}$ are linearly independent, we must have the following stronger identity for all $a\in\mathbb{F}_{2}^{m}$ :

\displaystyle\sum_{i=1}^{d}t_{a}(v_{i})=\sum_{i=1}^{d}t_{a}(u_{i}).

For each fixed $a$ , since $t_{a}(v_{i})$ is either zero or $2^{-\exp(v_{i})}$ and the exponents are all distinct, we can think of each sum as the unique binary representation of some dyadic rational number.

When $a=0$ , we get $t_{0}(v_{i})=2^{-\exp(v_{i})}$ and $t_{0}(u_{i})=2^{-\exp(u_{i})}$ since $T(v_{i})$ and $T(u_{i})$ are linear subspaces containing $0$ , for every $i=1,\dots,d$ . This gives us the identity

\displaystyle\sum_{i=1}^{d}2^{-\exp(v_{i})}=\sum_{i=1}^{d}2^{-\exp(u_{i})}.

So, the sets $\{\exp(v_{i}):i\leq d\}$ and $\{\exp(u_{i}):i\leq d\}$ must be equal since the above sums represent the same binary number. This means that the only way for the sums $\sum_{i=1}^{d}v_{i}$ and $\sum_{i=1}^{d}u_{i}$ to be equal at the $0$ th coordinate is if their exponents are all the same. Now we will find another coordinate where they differ.

Assume without loss of generality that $\exp(v_{i})=\exp(u_{i})$ for all $i=1,\dots,d$ , and $\exp(v_{1})<\dots<\exp(v_{d})$ . There must be some $k$ such that $T(v_{k})\neq T(u_{k})$ . Choose $a\in T(v_{k})\setminus T(u_{k})$ (which is possible since they are different subspaces of the same dimension), and now look at the identity

\displaystyle\sum_{i=1}^{d}t_{a}(v_{i})=\sum_{i=1}^{d}t_{a}(u_{i}).

Again, each sum is the unique binary representation of some dyadic rational number, but $t_{a}(v_{k})\neq 0$ while $t_{a}(u_{k})=0$ , so they cannot represent the same number, which is the desired contradiction.

Case 2.

$(\log n)/4\leq d\leq\log^{1.5}n$ .

We simply reuse the bound from case 1 (note that the lower bound is monotone in $d$ and hence we can just use the bound in the setting $d=\frac{\log n}{4})$ ,

\displaystyle|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|\geq\left|\frac{\log n}{4}P_% {\mathrm{Had}}\cap\mathbb{Z}^{n}\right|\geq n^{\Omega(\log^{2}n)}.

Case 3.

$d\geq\log^{1.5}n$ .

For this final case we will use the probabilistic method. Take the projection $\mathbb{R}^{n}\to\mathbb{R}^{n-1}$ that deletes the first coordinate of every vector, and let $P_{0}$ be the image of $P_{\mathrm{Had}}$ under this map. Recall that $P_{\mathrm{Had}}\subseteq\mathbb{R}^{n}$ is an $(n-1)$ -simplex whose vertices all have first coordinate equal to $1$ , since the first coordinate corresponds to the zero vector in $\mathbb{F}_{2}^{m}$ . So, this projection is a bijection on $P_{\mathrm{Had}}$ . In particular, integer points of $dP_{0}$ are in one-to-one correspondence with integer points of $dP_{\mathrm{Had}}$ , so $|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|=|dP_{0}\cap\mathbb{Z}^{n-1}|$ .

The new polytope $P_{0}$ is now a full-dimensional simplex in $[-1,1]^{n-1}$ . Since the vertices of the original Hadamard polytope $P_{\mathrm{Had}}\subseteq\mathbb{R}^{n}$ were orthogonal, for each vertex $v\in V(P_{0})\subseteq\mathbb{R}^{n-1}$ , the face of $P_{0}$ that does not contain $v$ is defined by the hyperplane $\{x\in\mathbb{R}^{n-1}:\langle x,v\rangle=-1\}$ . In particular, we can write the simplex $P_{0}$ as an intersection of half-spaces:

\displaystyle P_{0}

\displaystyle=\bigcap_{v\in V(P_{0})}\{x\in\mathbb{R}^{n-1}:\langle x,v\rangle% \geq-1\},

and

\displaystyle dP_{0}

\displaystyle=\bigcap_{v\in V(P_{0})}\{x\in\mathbb{R}^{n-1}:\langle x,v\rangle% \geq-d\}.

Fix some set of $c$ coordinates $S\subset[n]$ and some $D\in[d]$ (with $c$ and $D$ to be determined later) and look at the discrete hypercube $H_{S}[D]$ supported on those coordinates,

\displaystyle H_{S}[D]=\left([-D,D]\setminus\{0\}\right)^{S}\times\{0\}^{[n]% \setminus S}.

We will use the probabilistic method to show that $P_{0}$ contains at least $1/2$ the points of $H_{S}[D]$ for every choice of $S$ . Note that the hypercubes $H_{S}[D]$ are disjoint by construction, so

\displaystyle|dP_{0}\cap\mathbb{Z}^{n}|\geq\sum_{S\subseteq[n],|S|=c}\left|dP_% {0}\cap H_{S}[D]\right|.

Fix a vertex $v\in V(P_{0})$ , and a hypercube $H_{S}[D]$ . Let $X$ be a uniform random variable taking values in $H_{S}[D]$ . Since $v$ is a $\pm 1$ -valued vector, $\mathbb{E}|\langle X,v\rangle|=0$ . Hoeffding’s inequality implies that

\displaystyle\mathbb{P}(|\langle X,v\rangle|>d)

\displaystyle\leq 2e^{-d^{2}/2cD}.

By the union bound,

\displaystyle\mathbb{P}(X\notin dP_{0})\leq\sum_{v\in V(P_{0})}\mathbb{P}(|% \langle X,v\rangle|>d)\leq 2ne^{-d^{2}/2cD}.

Assuming that $2cD\leq\frac{d^{2}}{2\log n}$ , the above probability is at most $1/2$ , so at least $1/2$ the points of $H_{S}[D]$ must be contained in $dP_{0}$ . Now, summing over the disjoint sets $H_{S}[D]$ for all $\binom{n}{c}$ choices of $S$ ,

\displaystyle|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|=|dP_{0}\cap\mathbb{Z}^{n-1}% |\geq\sum_{S\subseteq[n],|S|=c}|H_{S}[D]\cap dP_{0}|\geq\frac{1}{2}{n\choose c% }(2D)^{c}.

We divide our analysis into two subcases.

Case 3a.

$d\leq\left(n\log n\right)^{\frac{1}{2}-\varepsilon}$ , which implies that $\frac{d^{2}}{\log n}\leq n^{1-2\varepsilon}$

In this case, set $D=1$ and $c=\frac{d^{2}}{4\log n}$ , so

Case 3b.

$d\geq\left(n\log n\right)^{\frac{1}{2}+\varepsilon}$ .

For our probabilistic argument to work, we need $2cD\leq\frac{d^{2}}{2\log n}$ , which rearranges to $D\leq\frac{d^{2}}{4c\log n}$ . Set $D=d^{2\varepsilon}/4$ and $c=n$ . Now,

as desired. Now,

\displaystyle|dP_{\mathrm{Had}}\cap\mathbb{Z}^{n}|

\displaystyle\geq\frac{1}{2}{n\choose c}(2D)^{c}\geq\left(d^{2\varepsilon}/4% \right)^{n}.

$\hfill\blacktriangleleft$

References

[1] Divesh Aggarwal, Antoine Joux, Miklos Santha, and Karol Węgrzycki. Polynomial time algorithms for integer programming and unbounded subset sum in the total regime, 2024. Submitted July 7, 2024; revised July 11, 2024. doi:10.48550/arXiv.2407.05435.
[2] Iskander Aliev and Martin Henk. Feasibility of integer knapsacks. SIAM Journal on Optimization, 20(6):2978–2993, 2010. doi:10.1137/090778043.
[3] Matthias Beck and Sinai Robins. Computing the Continuous Discretely. Undergraduate Texts in Mathematics. Springer, New York, NY, 1 edition, 2007. doi:10.1007/978-0-387-46112-0.
[4] Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Deterministic factorization of sparse polynomials with bounded individual degree. J. ACM, 67(2), May 2020. doi:10.1145/3365667.
[5] P. Bisht and I. Volkovich. On solving sparse polynomial factorization related problems. Computational Complexity, 34(7), 2025. doi:10.1007/s00037-025-00268-5.
[6] Sheng Chen, Nan Li, and Steven V. Sam. Generalized ehrhart polynomials. Transactions of the American Mathematical Society, 364(1):551–569, 2012. doi:10.1090/S0002-9947-2011-05494-2.
[7] David A. Cox. Recent developments in toric geometry, 1996. arXiv:alg-geom/9606016.
[8] Luis Crespo, Álvaro Pelayo, and Francisco Santos. Ewald’s conjecture and integer points in algebraic and symplectic toric geometry, 2024. arXiv:2310.10366.
[9] Eugène Ehrhart. Sur les polyèdres rationnels homothétiques à n dimensions. Comptes rendus de l’Académie des Sciences, 254:616–618, 1962.
[10] Yansong Feng, Hengyi Luo, Qiyuan Chen, Abderrahmane Nitaj, and Yanbin Pan. Computing asymptotic bounds for small roots in coppersmith’s method via sumset theory. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology – CRYPTO 2025, pages 3–32, Cham, 2025. Springer Nature Switzerland. doi:10.1007/978-3-032-01855-7_1.
[11] Takayuki Hibi, Akihiro Higashitani, Akiyoshi Tsuchiya, and Koutarou Yoshida. Ehrhart polynomials with negative coefficients. Graphs and Combinatorics, 35(1):363–371, 2019. doi:10.1007/S00373-018-1990-9.
[12] Peter M. Neumann and Cheryl E. Praeger. Cyclic matrices over finite fields. Journal of the London Mathematical Society, Series 2, 52(2):263–284, 1995. doi:10.1112/jlms/52.2.263.
[13] Joachim von zur Gathen and Erich Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31(2):265–287, 1985. doi:10.1016/0022-0000(85)90044-3.

[bib.bib1] [1] Divesh Aggarwal, Antoine Joux, Miklos Santha, and Karol Węgrzycki. Polynomial time algorithms for integer programming and unbounded subset sum in the total regime, 2024. Submitted July 7, 2024; revised July 11, 2024. doi:10.48550/arXiv.2407.05435.

[bib.bib2] [2] Iskander Aliev and Martin Henk. Feasibility of integer knapsacks. SIAM Journal on Optimization, 20(6):2978–2993, 2010. doi:10.1137/090778043.

[bib.bib3] [3] Matthias Beck and Sinai Robins. Computing the Continuous Discretely. Undergraduate Texts in Mathematics. Springer, New York, NY, 1 edition, 2007. doi:10.1007/978-0-387-46112-0.

[bib.bib4] [4] Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Deterministic factorization of sparse polynomials with bounded individual degree. J. ACM, 67(2), May 2020. doi:10.1145/3365667.

[bib.bib5] [5] P. Bisht and I. Volkovich. On solving sparse polynomial factorization related problems. Computational Complexity, 34(7), 2025. doi:10.1007/s00037-025-00268-5.

[bib.bib6] [6] Sheng Chen, Nan Li, and Steven V. Sam. Generalized ehrhart polynomials. Transactions of the American Mathematical Society, 364(1):551–569, 2012. doi:10.1090/S0002-9947-2011-05494-2.

[bib.bib7] [7] David A. Cox. Recent developments in toric geometry, 1996. arXiv:alg-geom/9606016.

[bib.bib8] [8] Luis Crespo, Álvaro Pelayo, and Francisco Santos. Ewald’s conjecture and integer points in algebraic and symplectic toric geometry, 2024. arXiv:2310.10366.

[bib.bib9] [9] Eugène Ehrhart. Sur les polyèdres rationnels homothétiques à n dimensions. Comptes rendus de l’Académie des Sciences, 254:616–618, 1962.

[bib.bib10] [10] Yansong Feng, Hengyi Luo, Qiyuan Chen, Abderrahmane Nitaj, and Yanbin Pan. Computing asymptotic bounds for small roots in coppersmith’s method via sumset theory. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology – CRYPTO 2025, pages 3–32, Cham, 2025. Springer Nature Switzerland. doi:10.1007/978-3-032-01855-7_1.

[bib.bib11] [11] Takayuki Hibi, Akihiro Higashitani, Akiyoshi Tsuchiya, and Koutarou Yoshida. Ehrhart polynomials with negative coefficients. Graphs and Combinatorics, 35(1):363–371, 2019. doi:10.1007/S00373-018-1990-9.

[bib.bib12] [12] Peter M. Neumann and Cheryl E. Praeger. Cyclic matrices over finite fields. Journal of the London Mathematical Society, Series 2, 52(2):263–284, 1995. doi:10.1112/jlms/52.2.263.

[bib.bib13] [13] Joachim von zur Gathen and Erich Kaltofen. Factoring sparse multivariate polynomials. Journal of Computer and System Sciences, 31(2):265–287, 1985. doi:10.1016/0022-0000(85)90044-3.