* [BKS04] Paul Beame, Henry A. Kautz, and Ashish Sabharwal.  Towards understanding and harnessing the potential of clause learning.  Journal of Artificial Intelligence Research, 22:319–351, 2004.
  * [BS09] Eli Ben-Sasson.  Size space tradeoffs for resolution.  SIAM Journal on Computing, 38(6):2511–2525, 2009.
  * [BSIW04] Eli Ben-Sasson, Russell Impagliazzo, and Avi Wigderson.  Near optimal separation of tree-like and general resolution.  Combinatorica, 24(4):585–603, 2004.
  * [BSW01] Eli Ben-Sasson and Ave Wigderson.  Short proofs are narrow — resolution made simple.  Journal of the ACM, 48:149–169, 2001.
  * [BT19] Sam Buss and Neil Thapen.  DRAT proofs, propagation redundancy, and extended resolution.  In Proc. 22nf Intl. Conference on Theory and Applications of Satisfiability Testing (SAT 2019), Springer-Verlag Lecture Notes in Computer Science 11628, pages 71–89, 2019.
  * [Bus86] Samuel R. Buss.  Bounded Arithmetic.  Bibliopolis, Naples, Italy, 1986.  Revision of 1985 Princeton University Ph.D. thesis.
  * [Cha70] C. L. Chang.  The unit proof and the input proof in theorem proving.  J. ACM, 17(4):698–707, 1970.
  * [Coo75] Stephen A. Cook.  Feasibly constructive proofs and the propositional calculus.  In Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, pages 83–97. Association for Computing Machinery, 1975.
  * [CR74] Stephen A. Cook and Robert A. Reckhow.  On the lengths of proofs in the propositional calculus, preliminary version.  In Proceedings of the Sixth Annual ACM Symposium on the Theory of Computing, pages 135–148, 1974.
  * [CR79] Stephen A. Cook and Robert A. Reckhow.  The relative efficiency of propositional proof systems.  Journal of Symbolic Logic, 44:36–50, 1979.
  * [GN03] Evguenii I. Goldberg and Yakov Novikov.  Verification of proofs of unsatisfiability for CNF formulas.  In Design, Automation and Test in Europe Conference (DATE), pages 10886–10891. IEEE Computer Society, 2003.
  * [GS88] Joachim Grollmann and Alan Selman.  Complexity measures for public-key cryptosystems.  SIAM Journal on Computing, 17(2):309–335, 1988.
  * [HB18] Marijn J. H. Heule and Armin Biere.  What a difference a variable makes.  In Tools and Algorithms for the Construction and Analysis of Systems - 24th International Conference (TACAS 2018), Lecture Notes in Computer Science 10806, pages 75–92. Springer Verlag, 2018.
  * [HHJW13a] Marijn J. H. Heule, Warren A. Hunt Jr., and Nathan Wetzler.  Trimming while checking clausal proofs.  In Formal Methods in Computer-Aided Design (FMCAD), pages 181–188. IEEE, 2013.
  * [HHJW13b] Marijn J. H. Heule, Warren A. Hunt Jr., and Nathan Wetzler.  Verifying refutations with extended resolution.  In Automated Deduction - 24th International Conference (CADE), Lecture Notes in Computer Science 7898, pages 345–359. Springer Verlag, 2013\.
  * [HKB17] Marijn J. H. Heule, Benjamin Kiesl, and Armin Biere.  Short proofs without new variables.  In Automated Deduction - 26th International Conference (CADE), Lecture Notes in Computer Science 10395, pages 130–147. Springer Verlag, 2017\.
  * [HKB19] Marijn J. H. Heule, Benjamin Kiesl, and Armin Biere.  Strong extension-free proof systems.  Journal of Automated Reasoning, pages 1–22, 2019.  Extended version of [HKB17].
  * [HKSB17] Marijn J. H. Heule, Benjamin Kiesl, Martina Seidl, and Armin Biere.  PRuning through satisfaction.  In Hardware and Software: Verification and Testing - 13th International Haifa Verification Conference (HVC), Lecture Notes in Computer Science 10629, pages 179–194. Springer Verlag, 2017.
  * [HN12] Trinh Huynh and Jakob Nordström.  On the virtue of succinct proofs: Amplifying communication complexity hardness to time-space trade-offs in proof complexity (Extended abstract).  In Proc. 44th Annual ACM Symposium on Theory of Computing (STOC’12), pages 233–248, 2012.
  * [JHB12] Matti Järvisalo, Marijn J. H. Heule, and Armin Biere.  Inprocessing rules.  In Automated Reasoning - 6th International Joint Conference (IJCAR), Lecture Notes in Computer Science 7364, pages 355–270. Springer Verlag, 2012.
  * [KPW95] Jan Krajíček, Pavel Pudlák, and Alan Woods.  Exponential lower bound to the size of bounded depth Frege proofs of the pigeonhole principle.  Random Structures and Algorithms, 7:15–39, 1995.
  * [Kra97] Jan Krajíček.  Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.  Journal of Symbolic Logic, 62:457–486, 1997.
  * [KRPH18] Benjamin Kiesl, Adrián Rebola-Pardo, and Marijn J. H. Heule.  Extended resolution simulates DRAT.  In Automated Reasoning - 6th International Joint Conference (IJCAR), Lecture Notes in Computer Science 10900, pages 516–531. Springer Verlag, 2018.
  * [Kul97] Oliver Kullmann.  Worst-case analysis, 3-SAT decision and lower bounds: Approaches for improved SAT algorithms.  DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 35:261–313, 1997.
  * [Kul99a] Oliver Kullmann.  New methods for 3-SAT decision and worst-case analysis.  Theoretical Computer Science, 223(1):1–72, 1999.
  * [Kul99b] Oliver Kullmann.  On a generalizaton of extended resolution.  Discrete Applied Mathematics, 96-97:149–176, 1999.
  * [Mar06] Klas Markström.  Locality and hard SAT-instances.  Journal on Satisfiability, Boolean Modeling and Computation (JSAT), 2:221–227, 2006.
  * [PBI93] Toniann Pitassi, Paul Beame, and Russell Impagliazzo.  Exponential lower bounds for the pigeonhole principle.  Computational Complexity, 3:97–140, 1993.
  * [PS10] Toniann Pitassi and Rahul Santhanam.  Effectively polynomial simulations.  In Innovations in Computer Science (ICS), pages 370–381, 2010.
  * [Pud97] Pavel Pudlák.  Lower bounds for resolution and cutting planes proofs and monotone computations.  Journal of Symbolic Logic, 62(3):981–998, 1997.
  * [Pud00] Pavel Pudlák.  Proofs as games.  American Mathematical Monthly, 107(6):541–550, 2000.
  * [Pud03] Pavel Pudlák.  On reducibility and symmetry of disjoint NP pairs.  Theoretical Computer Science, 205:323–339, 2003.
  * [Raz94] Alexander A. Razborov.  On provably disjoint NP-pairs.  Technical Report TR94-006, Electronic Colloquium in Computational Complexity (ECCC), 1994.  Also available as BRIC technical report RS-94-36.
  * [RM99] Ran Raz and Pierre McKenzie.  Separation of the monotone NC hierarchy.  Combinatorica, 19(3):403–435, 1999.
  * [RS18] Adrián Rebola-Pardo and Martin Suda.  A theory of satisfiability-preserving proofs in SAT solving.  In Proc., 22nd Intl. Conf. on Logic for Programming, Artificial Intelligence and Reasoning (LPAR’22), EPiC Series in Computing 57, pages 583–603. EasyChair, 2018.
  * [SW83] Jorg Siekmann and Graham Wrightson.  Automation of Reasoning, volume 1&2\.  Springer-Verlag, Berlin, 1983.
  * [Sze03] Stefan Szeider.  Homomorphisms of conjunctive normal forms.  Discrete Applied Mathematics, 130:351–365, 2003.
  * [Tse68] G. S. Tsejtin.  On the complexity of derivation in propositional logic.  Studies in Constructive Mathematics and Mathematical Logic, 2:115–125, 1968.  Reprinted in: [SW83, vol 2], pp. 466-483.
  * [Urq87] Alasdair Urquhart.  Hard examples for resolution.  Journal of the ACM, 34:209–219, 1987.
  * [Urq11] Alasdair Urquhart.  A near-optimal separation of regular and general resolution.  SIAM Journal on Computing, 40(1):107–121, 2011.
  * [Van08] Allen Van Gelder.  Verifying RUP proofs of propositional unsatisfiability.  In 10th International Symposium on Artificial Intelligence and Mathematics (ISAIM), 2008.  http://isaim2008.unl.edu/index.php?page=proceedings.
  * [WHHJ14] Nathan Wetzler, Marijn J. H. Heule, and Warren A. Hunt Jr.  DRAT-trim: Efficient checking and trimming using expressive clausal proofs.  In Theory and Applications of Satisfiability Testing - 17th International Conference (SAT), Lecture Notes in Computer Science 8561, pages 422–429. Springer Verlag, 2014.


# Khovanskii’s Theorem and Effective Results on Sumset Structure

Michael J. Curran  Leo Goldmakher

###### Abstract

A remarkable theorem due to Khovanskii asserts that for any finite subset $A$
of an abelian group, the cardinality of the $h$-fold sumset $hA$ grows like a
polynomial for all sufficiently large $h$. Currently, neither the polynomial
nor what sufficiently large means are understood. In this paper we obtain an
effective version of Khovanskii’s theorem for any $A\subset\mathbb{Z}^{d}$
whose convex hull is a simplex; previously, such results were only available
for $d=1$. Our approach gives information about not just the cardinality of
$hA$, but also its structure, and we prove two effective theorems describing
$hA$ as a set: one answering a recent question posed by Granville and Shakan,
the other a Brion-type formula that provides a compact description of $hA$ for
all large $h$. As a further illustration of our approach, we derive a
completely explicit formula for $|hA|$ whenever $A\subset\mathbb{Z}^{d}$
consists of $d+2$ points.

232D title = Khovanskii’s Theorem and Effective Results on Sumset Structure,
author = Michael J. Curran and Leo Goldmakher, plaintextauthor = Michael J.
Curran and Leo Goldmakher, plaintexttitle = Khovanskii’s Theorem and Effective
Results on Sumset Structure, runningtitle = Effective Khovanskii,
runningauthor = Michael J. Curran and Leo Goldmakher, copyrightauthor =
Michael J. Curran and Leo Goldmakher, keywords = Ehrhart theory, iterated
sumsets, year=2021, number=27, received=30 November 2020, revised=3 November
2021, published=23 December 2021, doi=10.19086/da.28814,

[classification=text]

##  1 Introduction

Given a finite set $A\subset\mathbb{Z}^{d}$, a central object of study in
arithmetic combinatorics is the $h$-fold sumset

$hA:=\\{\bm{x}_{1}+\cdots+\bm{x}_{h}:\bm{x}_{i}\in A\\}.$

Both the structure and the cardinality of sumsets can be quite complicated,
but Khovanskii made the beautiful discovery that once enough copies of $A$ are
added together, the behavior stabilizes:

######  Theorem 1.1 (Khovanskii [9]).

Given a finite set $A\subset\mathbb{Z}^{d}$, there exists a polynomial
$p\in\mathbb{Q}[x]$ of degree at most $d$ such that $|hA|=p(h)$ for all
sufficiently large $h$. Moreover, if the difference set $A-A$ generates all of
$\mathbb{Z}^{d}$ additively, then $\deg p=d$ and the leading coefficient of
$p$ is the volume of the convex hull of $A$.

Khovanskii’s original proof interprets $|hA|$ as the Hilbert function of a
finitely generated graded module over the ring of polynomials in several
variables and then employs the Hilbert polynomial theorem. This approach is
elegant but ineffective: it yields no information about $p(h)$ apart from its
degree and leading term, nor any indication of where the phase transition
occurs (i.e. what “sufficiently large” means). There have been other proofs of
Khovanskii’s theorem since, including a geometric proof (which also patches an
error in Khovanskii’s original paper) by Lee [10] and a purely combinatorial
proof by Nathanson and Ruzsa [13, 14], but to our knowledge no effective
version of Khovanskii’s theorem is known for subsets of $\mathbb{Z}^{d}$ for
any $d>1$. In this paper we give a different approach to Khovanskii’s theorem
that yields more information than previous approaches about the structure of
the polynomial and where the phase transition occurs. In some cases, our
approach produces a complete description of the cardinality of $hA$ for _all_
$h$.

The special case $A\subset\mathbb{Z}$ has received a fair bit of attention
(see e.g. [5, 6, 12, 17]), sometimes under the name of the Frobenius coin
problem or the chicken nugget problem. By shifting and dilating $A$, we may
assume that its minimal element is 0 and that the greatest common divisor of
its elements is 1. It follows that

$\bigcup_{h\geq 0}hA=\mathbb{N}\setminus\mathcal{E}(A)$

for some finite exceptional set $\mathcal{E}(A)$.111Here and throughout we
define $\mathbb{N}$ to be the set of _non-negative_ integers. Very recently,
Granville and Walker [6, Theorem 1] proved that if $b$ is the largest element
of $A$, then for any $h\geq b-|A|+2$ we have

$hA=\\{0,1,\ldots,bh\\}\setminus\bigg{(}\mathcal{E}(A)\cup\Big{(}bh-\mathcal{E}(b-A)\Big{)}\bigg{)},$
(1)

and moreover that the bound $h\geq b-|A|+2$ is sharp. This result on the
structure of $hA$ can be used to produce a more explicit version of
Khovanskii’s theorem for subsets of $\mathbb{Z}$. For example, suppose
$A=\\{0,a,b\\}$ where $0<a<b$ and $(a,b)=1$. Classical work of Sylvester [15]
implies that

$|\mathcal{E}(A)|=\frac{1}{2}(a-1)(b-1),$

It is also easy to see that $\mathcal{E}(A)\subseteq[0,ab)$ since the numbers
$0,a,2a,\cdots,(b-1)a$ form a complete residue set modulo $b$, hence also that
$bh-\mathcal{E}(b-A)\subset(bh-(b-a-1)b,bh]$. These facts in combination with
(1) yield

$\phantom{\qquad\forall h\geq
2\lfloor\frac{b}{2}\rfloor.}|hA|=bh-\frac{1}{2}b^{2}+\frac{3}{2}b\qquad\forall
h\geq b$

since the sets $[0,ab)$ and $(bh-(b-a)b,bh]$ are disjoint fot $h\geq b$. This
leaves open the question of whether $b$ is the true location of the phase
transition, as well as what the behavior of $|hA|$ is for small values of $h$.

The approach we introduce in the present work allows us to completely resolve
this question: we will show that

$|hA|=\begin{cases}\frac{1}{2}h^{2}+\frac{3}{2}h+1&\mbox{if }0\leq h<b-2\\\
bh-\frac{1}{2}b^{2}+\frac{3}{2}b&\mbox{if }h\geq b-2.\end{cases}$

The proof of this is in fact very short, and can be found at the beginning of
section 2. Moreover, we can generalize this to arbitrary dimension and
describe the growth of $hA$ for any $A\subset\mathbb{Z}^{d}$ containing $d+2$
elements:

######  Theorem 1.2.

Suppose $A\subset\mathbb{Z}^{d}$ consists of $d+2$ elements, and further that
$A-A$ generates $\mathbb{Z}^{d}$ additively. Let $\Delta_{A}$ denote the
convex hull of $A$. Then

$|hA|=\binom{h+d+1}{d+1}\qquad\text{whenever }0\leq
h<\text{vol}(\Delta_{A})\cdot d!-d-1$

and

$|hA|=\binom{h+d+1}{d+1}-\binom{h-\text{vol}(\Delta_{A})\cdot
d!+d+1}{d+1}\qquad\text{whenever }h\geq\text{vol}(\Delta_{A})\cdot d!-d-1.$

######  Remark.

One counterintuitive consequence of this is that for small $h$, the
cardinality of $hA$ is independent of the specific elements of $A$. This is
because for small values of $h$ each element in $hA$ has a unique
representation as a sum of elements of $A$.

For a general set $A\subset\mathbb{Z}^{d}$ with $d>1$, the structure of the
sumset of $hA$ is less well understood. Granville and Shakan [5] recently
proved a higher dimensional but ineffective analogue of (1), and asked for an
explicit bound on the phase transition. We are able to deduce such a bound in
the case that the convex hull of $A$ is a $d$-simplex:

######  Theorem 1.3.

Let $A\subset\mathbb{Z}^{d}$ be a finite set such that $A-A$ generates
$\mathbb{Z}^{d}$ additively and $\Delta_{A}$ is a $d$-dimensional simplex.
Denote by $\bm{v}_{1},\ldots,\bm{v}_{d+1}$ the vertices of $\Delta_{A}$ and
let

$T_{i}(A)=\bigcup_{k\geq 0}k(A-\bm{v}_{i}).$

Then for all non-negative integers
$h\geq\text{vol}(\Delta_{A})\cdot(d+1)!-2-2d$ we have

$hA=\bigcap_{i=1}^{d+1}\bigg{(}h\bm{v}_{i}+T_{i}(A)\bigg{)}$ (2)

######  Remark.

Note that the $T_{i}(A)$ are independent of $h$, so the only dependence on $h$
in the right hand side of (2) lies in the dilates $h\bm{v}_{i}$.

Theorem 1.3 gives an expression for $hA$ but can be difficult to use in
practice. It turns out that by translating the problem into the language of
power series, one can describe the elements of $hA$ more explicitly. To any
set $A\subseteq\mathbb{Z}$, associate the power series $\sum\limits_{a\in
A}x^{a}$; for example, $A=\\{0,2,5\\}$ would correspond to $1+x^{2}+x^{5}$.
For this choice of $A$, we will show that for all $h\geq 3$ the power series
associated to $hA$ is given by

$\frac{1+x^{2}+x^{4}+x^{6}+x^{8}-x^{5h-7}(1+x^{3}+x^{6}+x^{9}+x^{12})}{1-x^{5}}.$

This may appear complicated at first glance, but for large values of $h$ it
produces a compact description of the set $hA$. In Theorem 5.1 we generalize
this phenomenon, proving that for any $A$ the power series associated to $hA$
is the ratio of two explicit (and easy to compute) polynomials associated to
$A$. This is analogous to a famous formula of Brion [2] expressing the lattice
generating function of a convex polytope in terms of the lattice generating
functions of its tangent cones.

If rather than associating a power series to $hA$ in the manner described
above one studies the standard generating function of $|hA|$, it’s possible to
obtain an effective version of Khovanskii’s theorem for simplicial sumsets,
i.e. those $A$ whose convex hull is a simplex:

######  Theorem 1.4.

If $A\subset\mathbb{Z}^{d}$ is a finite set such that $A-A$ generates
$\mathbb{Z}^{d}$ additively and $\Delta_{A}$ is a $d$-dimensional simplex,
then there exists a polynomial $p\in\mathbb{Q}[x]$ such that $|hA|=p(h)$ for
all non-negative $h\geq\text{vol}(\Delta_{A})\cdot(d+1)!-1-3d$.

The key new idea that allows us to prove all our results on iterated sumsets
is that rather than studying the structure of $hA$ individually for each $h$,
we embed them all into a higher-dimensional space and study the geometry of
the resulting object (called a _cone_). This idea is essentially a geometric
version of a generating function, and is inspired by work of Ehrhart [4] on
counting lattice points in dilates of polytopes. More precisely, Ehrhart used
this approach to prove that for any convex polytope
$\mathcal{P}\subset\mathbb{R}^{d}$ whose vertices are lattice points, there
exists a polynomial $p\in\mathbb{Q}[t]$ such that the number of lattice points
in the $t^{\text{th}}$ dilate of $\mathcal{P}$ is precisely $p(t)$ for all
$t\in\mathbb{N}$ (see [3] for more background on Ehrhart theory, including a
proof of this theorem). A key difference between our proof and the proof of
Ehrhart’s theorem is that for sumsets the associated cone is not _simplicial_
, meaning that the cardinality of its minimal generating set is greater than
its dimension. It is this difference that causes difficulty in obtaining
information on the phase transition when $\Delta_{A}$ is not a simplex.

We are not the first to connect Khovanskii’s theorem to Ehrhart theory; in
2008, Jelínek and Klazar [8] proved a common generalization of Khovanskii’s
theorem and Ehrhart’s theorem. In their work Jelínek and Klazar employ
Dickson’s lemma to show that a certain set has finitely many minimal elements,
a tool which is also used in Nathanson and Ruzsa’s combinatorial proof of
Khovanskii’s theorem in [13, 14]. While very clean, this has the disadvantage
of rendering their results ineffective. Indeed, not only does Jelínek and
Klazar’s main theorem not yield an effective version of Khovanskii’s theorem,
it only implies an ineffective version of Ehrhart’s theorem (the original
version of which is effective).

Before concluding this introduction we briefly discuss the interesting work of
Barvinok and Woods [1], in which rather than looking at sumsets they
investigate lattice generating functions for linear transformations of
rational polytopes. They study the complexity of computing such generating
functions, in particular showing that there exist polynomial-time algorithms
for accomplishing this. Phrased in terms of sumsets, Barvinok and Woods bound
$|hA|$ in terms of the heights of the generators of the cone generated by $A$.
However, since they bound neither the number of these generators nor their
heights, their results are of necessity ineffective. One of the key
innovations in our work is an explicit bound on the heights of the generators
in terms of the geometry of $A$ (see section 3 below, in particular Lemmas 3.1
and 3.2), which is what allows us to prove effective versions of Khovanskii’s
theorem. Moreover, we derive a structure theorem and a Brion-like formula for
$hA$. It would be interesting to obtain analogues of our results in the more
general setting of Barvinok-Woods.

The structure of this paper is as follows. In section 2 we illustrate our
approach using some explicit examples; generalizing these, we deduce Theorem
1.2 in the special case that the convex hull of $A$ is a simplex. Next, in
section 3, we use our approach to prove Theorem 1.4, an effective version of
Khovanskii’s theorem that holds for all sets $A$ whose convex hull is a
simplex. In section 4 we build on these ideas to prove Theorem 1.3, an
effective structure theorem on iterated sumsets. We explore the structure of
$hA$ further in section 5 and obtain an explicit and compact Brion-type
formula capturing the structure of $hA$ for any $A\subset\mathbb{Z}$. In
section 6 we return to Theorem 1.2 and prove it (i.e. we remove the additional
hypothesis we made in section 2). We conclude with section 7, which contains a
few conjectures and empirical observations that we hope will inspire further
research.

##  2 Warm up: Explicit Formulae for $|hA|$

To illustrate our approach, we start by computing $|hA|$ for some simple sets
${A=\\{\bm{a}_{1},\ldots,\bm{a}_{k}\\}\subset\mathbb{Z}^{d}}$. Throughout this
section, we’ll assume that the convex hull of $A$ is a simplex, and that $A$
contains the origin and generates $\mathbb{Z}^{d}$ additively.

Our primary object of study will be the _cone over $A$_, a $(d+1)$-dimensional
object that captures the structure of $hA$ for all $h$ simultaneously. To
define this precisely, we first need a bit of notation. Given
$\bm{a}=(a_{1},\ldots,a_{d})\in\mathbb{Z}^{d}$, define its _lift_
$\widetilde{\bm{a}}\in\mathbb{Z}^{d+1}$ to be
$\widetilde{\bm{a}}=(a_{1},\ldots,a_{d},1)$. More generally, if
$\bm{a}=(a_{1},\ldots,a_{d})\in\mathbb{Z}^{d}$ and $h\in\mathbb{N}$, we will
write $(\bm{a},h)$ instead of $(a_{1},\ldots,a_{d},h)$, and refer to $h$ as
the _height_ of this point. The following notions are fundamental to our work:

######  Definition 1.

Define the _cone over $A$_ to be

$\mathcal{C}_{A}:=\text{span}_{\mathbb{N}}\\{\widetilde{\bm{a}}_{1},\ldots,\widetilde{\bm{a}}_{k}\\}=\\{n_{1}\widetilde{\bm{a}}_{1}+\cdots+n_{k}\widetilde{\bm{a}}_{k}:n_{1},\ldots,n_{k}\in\mathbb{N}\\}.$
(3)

To the cone $\mathcal{C}_{A}$ we associate a generating series
$\mathcal{C}_{A}(t)\in\mathbb{Q}\llbracket t\rrbracket$:

$\mathcal{C}_{A}(t):=\sum_{\bm{a}\in\mathcal{C}_{A}}t^{\text{height}(\bm{a})}.$
(4)

It may be more intuitive to think about $\mathcal{C}_{A}$ geometrically: the
points at height $h$ in $\mathcal{C}_{A}$ form a copy of $hA$, embedded into
$\mathbb{Z}^{d+1}$. Viewed from this perspective, we see that
$\mathcal{C}_{A}(t)$ is simply the generating function of $hA$:

$\mathcal{C}_{A}(t)=\sum_{h\geq 0}|hA|t^{h}.$ (5)

Our goal is to partition $\mathcal{C}_{A}$ into simple geometric pieces, and
then use this to decompose $\mathcal{C}_{A}(t)$ into a sum of nice rational
functions. Once this is accomplished, we’ll be able to determine $|hA|$ for
all values of $h$.

The following example captures the key components of our approach. Let
${A=\\{0,1,7,8\\}}$; the first few levels of $\mathcal{C}_{A}$ are illustrated
in Figure 1. Note the two boundary rays are spanned by the vectors $(0,1)$ and
$(8,1)$, which are linearly independent. Therefore the lattice
$\Lambda=\text{span}_{\mathbb{Z}}\\{(0,1),(8,1)\\}$ has finite index in
$\mathbb{Z}^{2}$, so we can partition $\mathcal{C}_{A}$ into finitely many
equivalence classes modulo $\Lambda$.

Figure 1: The cone $\mathcal{C}_{A}$ over $A=\\{0,1,7,8\\}$. Elements lying
above the residue class 0 mod 8 are labeled with bold circles, elements lying
above the residue class 4 mod 8 are labeled with hollow squares, and the other
elements are simply dots.

Given $0\leq m<8$, let $\mathcal{S}_{m}$ denote the points of
$\mathcal{C}_{A}$ lying in the residue class of $(m,1)$. The equivalence class
$\mathcal{S}_{0}$ is simple to understand: it is just the set
$\Lambda^{+}:=\text{span}_{\mathbb{N}}\\{(0,1),(8,1)\\}$, represented by bold
circles in Figure 1. By the geometric series formula, the generating series of
$\mathcal{S}_{0}$ is simply

$\sum_{\bm{a}\in\mathcal{S}_{0}}t^{\text{height}(\bm{a})}=\frac{1}{(1-t)^{2}}.$

The residue class $\mathcal{S}_{4}$ consists of the hollow squares in Figure
1, and can be viewed as a union of two translates of $\Lambda^{+}$:

$\mathcal{S}_{4}=\bigg{(}(4,4)+\Lambda^{+}\bigg{)}\cup\bigg{(}(28,4)+\Lambda^{+}\bigg{)}.$

These two cones are not disjoint, with intersection at $(28,7)+\Lambda^{+}$.
Inclusion-exclusion implies

$\sum_{\bm{a}\in\mathcal{S}_{4}}t^{\text{height}(\bm{a})}=\frac{t^{4}}{(1-t)^{2}}+\frac{t^{4}}{(1-t)^{2}}-\frac{t^{7}}{(1-t)^{2}}=\frac{2t^{4}-t^{7}}{(1-t)^{2}}.$

Making similar calculations for the remaining residue classes of
$\mathcal{C}_{A}$ and adding the corresponding generating functions together,
one finds

$\displaystyle\mathcal{C}_{A}(t)$
$\displaystyle=\frac{1+2t+2t^{2}+2t^{3}+2t^{4}+2t^{5}+2t^{6}-5t^{7}}{(1-t)^{2}}.$

Expanding this as a power series, we conclude

$\sum_{h\geq
0}|hA|t^{h}=\mathcal{C}_{A}(t)=-5t-8t^{2}-9t^{3}-8t^{4}-5t^{5}+\sum_{h\geq
0}(8h+1)t^{h}.$

We deduce from this a totally explicit version of Khovanskii’s theorem for the
set $A=\\{0,1,7,8\\}$: $|hA|=8h+1$ for $h\geq 6$. Our goal in the sequel will
be to adapt this approach to more general sets $A$.

As a first step, consider any 3-element set $A\subset\mathbb{Z}$; after
translating and dilating, we may assume $A=\\{0,a,b\\}$ where $0<a<b$ and $a$
and $b$ are relatively prime. Since $a$ and $b$ are relatively prime, all of
the elements $(ma,m)$ for $0\leq m<b$ are distinct modulo the lattice spanned
by $(b,1)$ and $(0,1)$. Furthermore, they necessarily generate the residue
class modulo $\Lambda$ they lie in:

$\mathcal{S}_{ma}=(ma,m)+\text{span}_{\mathbb{N}}\\{(0,1),(0,b)\\}.$

Now because the number of residue classes modulo $\Lambda$ is exactly $b$, it
follows that

$\displaystyle\mathcal{C}_{A}(t)$
$\displaystyle=\frac{1+t+t^{2}+\cdots+t^{b-1}}{(1-t)^{2}}=\frac{1-t^{b}}{(1-t)^{3}}$

Expanding $\mathcal{C}_{A}(t)$ as a power series gives that

$\displaystyle\sum_{h\geq 0}|hA|t^{h}$
$\displaystyle=\frac{1-t^{b}}{(1-t)^{3}}=\sum_{h\geq
0}\binom{h+2}{h}t^{h}-\sum_{h\geq 0}\binom{h+2}{h}t^{h+b}$
$\displaystyle=\sum_{h\geq 0}\binom{h+2}{2}t^{h}-\sum_{h\geq
b}\binom{h-b+2}{2}t^{h}.$

Equating coefficients, we find

$|hA|=\binom{h+2}{2}\qquad\text{whenever }0\leq h<b-2$

and

$|hA|=\binom{h+2}{2}-\binom{h-b+2}{2}\qquad\text{whenever }h\geq b-2.$

These formulas generalize to arbitrary dimension, as was stated in Theorem
1.2. We conclude this section by proving Theorem 1.2 in the special case that
$\Delta_{A}$ is a simplex.

###### Proof of Theorem 1.2 for simplicial sumsets.

Denote the vertices of $\Delta_{A}$ by $\bm{v}_{1},\ldots,\bm{v}_{d+1}$, and
without loss of generality suppose the $(d+2)^{\text{nd}}$ element of $A$ is
$\bm{0}$. Set
$\Lambda:=\text{span}_{\mathbb{Z}}\\{\widetilde{\bm{v}}_{1},\ldots,\widetilde{\bm{v}}_{d+1}\\}$
and
$\Lambda^{+}:=\text{span}_{\mathbb{N}}\\{\widetilde{\bm{v}}_{1},\ldots,\widetilde{\bm{v}}_{d+1}\\}$.
It is a well-known result in the geometry of numbers that
$\mathbb{Z}^{d+1}/\Lambda$ can be identified with the set of lattice points in
the fundamental domain of $\Lambda$, and that the number of lattice points
lying in the fundamental domain of $\Lambda$ is the determinant of the matrix
whose columns are $\widetilde{\bm{v}_{i}}$ [11, Ch. 6, Sec. 1]. Thus,

$|\mathbb{Z}^{d+1}/\Lambda|=\text{vol}(\Delta_{A})\cdot d!.$

Because $A$ generates $\mathbb{Z}^{d}$ it follows that all the vectors
$(\bm{0},m)$ with $0\leq m<\text{vol}(\Delta_{A})\cdot d!$ are distinct modulo
$\Lambda$, whence

$\mathcal{C}_{A}=\bigsqcup_{m=0}^{\text{vol}(\Delta_{A})\cdot
d!-1}\bigg{(}(\bm{0},m)+\Lambda^{+}\bigg{)}.$

This implies

$\mathcal{C}_{A}(t)=\frac{1+t+\cdots+t^{\text{vol}(\Delta_{A})\cdot
d!-1}}{(1-t)^{d+1}}=\frac{1-t^{\text{vol}(\Delta_{A})\cdot d!}}{(1-t)^{d+2}}.$

Now observe that

$\frac{1}{(1-t)^{d+2}}=\sum_{h\geq 0}\binom{h+d+1}{h}t^{h}=\sum_{h\geq
0}\binom{h+d+1}{d+1}t^{h}$

while

$\displaystyle\frac{t^{\text{vol}(\Delta_{A})\cdot d!}}{(1-t)^{d+2}}$
$\displaystyle=\sum_{h\geq
0}\binom{h+d+1}{d+1}t^{h+\text{vol}(\Delta_{A})\cdot
d!}=\sum_{h\geq\text{vol}(\Delta_{A})\cdot
d!}\binom{h-\text{vol}(\Delta_{A})\cdot d!+d+1}{d+1}t^{h}.$

The claim follows. ∎

##  3 Effective Khovanskii for simplicial sumsets: Proof of Theorem 1.4

In the last section we proved a completely explicit version of Khovanskii’s
theorem over $\mathbb{Z}^{d}$ in the special case that $A$ consists of $d+2$
points and the convex hull of $A$ is a simplex. In this section we drop the
condition on the size of $A$ and try to push our methods further. This comes
at a cost—the geometry of the cone $\mathcal{C}_{A}$ becomes more
complicated—but we will still be able to obtain an effective bound on the
phase transition (i.e. what ‘sufficiently large’ means) in Khovanskii’s
theorem.

Let $A\subset\mathbb{Z}^{d}$ be a finite set such that $A-A$ generates
$\mathbb{Z}^{d}$ additively and $\Delta_{A}$ is a simplex. Denote the $d+1$
vertices of $\Delta_{A}$ by $\bm{v}_{1},\ldots,\bm{v}_{d+1}$. These span a
lattice

$\Lambda:=\text{span}_{\mathbb{Z}}\\{\widetilde{\bm{v}}_{1},\ldots,\widetilde{\bm{v}}_{d+1}\\}\subset\mathbb{Z}^{d+1}$

of finite index in $\mathbb{Z}^{d+1}$. (Recall that $\widetilde{\bm{v}}$
denotes the lift of $\bm{v}$ to height 1 in $\mathbb{Z}^{d+1}$.) We will also
be interested in the subset

$\Lambda^{+}:=\text{span}_{\mathbb{N}}\\{\widetilde{\bm{v}}_{1},\ldots,\widetilde{\bm{v}}_{d+1}\\}\subset\Lambda.$

Finally, we denote by $\Pi$ the set of integer lattice points lying in the
fundamental domain of $\Lambda$; in symbols,

$\Pi:=\left\\{\sum_{i=1}^{d+1}\lambda_{i}\widetilde{\bm{v}}_{i}:0\leq\lambda_{i}<1\right\\}\cap\mathbb{Z}^{d+1}.$

We now partition $\mathcal{C}_{A}$ according to the residue classes (mod
$\Lambda$), each of which can be represented by an element of $\Pi.$ Given
$\bm{\pi}\in\Pi$, define $\mathcal{S}_{\bm{\pi}}$ to be the set of elements of
$\mathcal{C}_{A}$ that are congruent to $\bm{\pi}$ modulo $\Lambda$. We call
$(\bm{g},N)\in\mathcal{S}_{\bm{\pi}}$ a _minimal element_ if
$(\bm{g},N)-\widetilde{\bm{v}}_{i}$ does not lie in $\mathcal{C}_{A}$ for any
$i$.

######  Remark.

The set $\mathcal{S}_{\bm{\pi}}$ can be given the structure of a partially
ordered set, where $(\bm{a},N)\leq(\bm{b},M)$ if and only if
$(\bm{b},M)-(\bm{a},N)\in\Lambda^{+}$. Our definition of minimal element
coincides with the minimal elements of $\mathcal{S}_{\bm{\pi}}$ as a poset.

As in the previous section, we associate to each residue class
$\bm{\pi}\in\Pi$ a generating series

$\mathcal{S}_{\bm{\pi}}(t)=\sum_{\bm{a}\in\mathcal{S}_{\bm{\pi}}}t^{\text{height}(\bm{a})}.$

In the examples from the previous section, $\mathcal{S}_{\bm{\pi}}(t)$ was a
rational function of the form ${P(t)/(1-t)^{d}}$, and we will soon see (Lemma
3.2) that this is always the case. In order to obtain an effective version of
Khovanskii’s theorem, it will be necessary to obtain bounds on the degree of
$P$. We do this in two steps: first, we control the heights of the minimal
elements, and then we relate the degree of $P$ to the minimal elements of
$\mathcal{S}_{\pi}$.

######  Lemma 3.1.

If $(\bm{\alpha},M)$ is a minimal element of $\mathcal{S}_{\bm{\pi}}$, then

$M\leq\text{vol}(\Delta_{A})\cdot d!-1.$

In particular there are finitely many minimal elements.

###### Proof.

Without loss of generality assume that $\bm{0}$ is a vertex of $\Delta_{A}$,
say $\bm{v}_{d+1}=0$. By assumption we may write
$\bm{\alpha}=\bm{a}_{1}+\cdots+\bm{a}_{M}$ with each $\bm{a}_{i}\in A$. We
claim that the $M$ subsums

$\bm{a}_{1},\;\bm{a}_{1}+\bm{a}_{2},\;\bm{a}_{1}+\bm{a}_{2}+\bm{a}_{3},\;\ldots,\;\bm{a}_{1}+\cdots+\bm{a}_{M}$

are all distinct modulo $\Lambda$; since the number of nonzero residue classes
modulo $\Lambda$ is $\text{vol}(\Delta_{A})\cdot d!-1$, the claim follows.

Suppose instead that $\bm{a}_{1}+\cdots+\bm{a}_{m}$ and
$\bm{a}_{1}+\cdots+\bm{a}_{n}$ were congruent modulo $\Lambda$ for some $m<n$.
Then $\bm{a}_{m+1}+\cdots+\bm{a}_{n}\in\Lambda$. Since each $\bm{a}_{i}$ lies
in $\Delta_{\Lambda^{+}}$ and $\Delta_{\Lambda^{+}}$ is convex, we must have
$\bm{a}_{m+1}+\cdots+\bm{a}_{n}\in\Delta_{\Lambda^{+}}\cap\Lambda=\Lambda^{+}$.
It follows that there exist $k_{i}\in\mathbb{N}$ such that

$\bm{a}_{m+1}+\cdots+\bm{a}_{n}=\sum_{i=1}^{d}k_{i}\bm{v}_{i}.$

Writing each $\bm{a}_{j}$ in barycentric coordinates
${\bm{a}_{j}=\sum_{i=1}^{d}\lambda_{i,j}\bm{v}_{i}}$ with $\lambda_{i,j}\geq
0$ and $\sum_{i=1}^{d}\lambda_{i,j}\leq 1$, we see that

$\bm{a}_{m+1}+\cdots+\bm{a}_{n}=\sum_{i=1}^{d}\left(\sum_{j=m+1}^{n}\lambda_{i,j}\right)\bm{v}_{i}=\sum_{i=1}^{d}k_{i}\bm{v}_{i}.$

Since the nonzero vertices of $\Delta_{A}$ are linearly independent we deduce

$\sum_{i=1}^{d}k_{i}=\sum_{j=m+1}^{n}\sum_{i=1}^{d}\lambda_{i,j}\leq\sum_{j=m+1}^{n}1=n-m.$

But this contradicts the minimality of $(\bm{\alpha},M)$! To see this, set
$\bm{\beta}:=\bm{\alpha}-(\bm{a}_{m+1}+\cdots+\bm{a}_{n})$ and note that

$(\bm{\alpha},M)-(\bm{\beta},M-(n-m))=\left(\sum_{i=1}^{d}k_{i}\bm{v}_{i},n-m\right)\in\Lambda^{+}$

since $\sum_{i}k_{i}\leq n-m$ and $\bm{0}$ is a vertex of $\Delta_{A}$. This
implies $(\bm{\alpha},M)$ is not minimal. ∎

######  Lemma 3.2.

Suppose the minimal elements of $\mathcal{S}_{\bm{\pi}}$ are
$(\bm{g}_{1},H_{1}),\ldots,(\bm{g}_{n},H_{n})$. Then we can write

$\mathcal{S}_{\bm{\pi}}(t)=\frac{P(t)}{(1-t)^{d+1}}$

for some $P\in\mathbb{Q}[t]$ with $\deg P\leq(d+1)\cdot\max_{i}(H_{i})-d.$

######  Remark.

When $n=1$, we simply have $P(t)=t^{H_{1}}$.

###### Proof.

As before assume $\bm{v}_{d+1}=\bm{0}$. Furthermore, we may assume that the
elements $\bm{g}_{i}$ are not congruent to $\bm{0}$ (mod $\Lambda$) since the
origin in $\mathbb{Z}^{d+1}$ is the unique minimal element of
$\mathcal{S}_{\bm{0}}$. By assumption we may write

$\mathcal{S}_{\bm{\pi}}=\bigcup_{i=1}^{n}\bigg{(}(\bm{g}_{i},H_{i})+\Lambda^{+}\bigg{)}.$

Inclusion-exclusion implies that $\mathcal{S}_{\bm{\pi}}(t)$ is a weighted sum
of the generating series of all possible intersections of the sets
$(\bm{g}_{i},H_{i})+\Lambda^{+}$. Now observe that for each
$I\subseteq\\{1,\ldots,n\\}$, we can write

$\bigcap_{i\in
I}\bigg{(}(\bm{g}_{i},H_{i})+\Lambda^{+}\bigg{)}=(\bm{g}_{I},H_{I})+\Lambda^{+}$

for some $\bm{g}_{I}\in\mathcal{C}_{A}$ and $H_{I}\in\mathbb{N}$. Since the
generating series of $(\bm{g}_{I},H_{I})+\Lambda^{+}$ is simply
$\displaystyle\frac{t^{H_{I}}}{(1-t)^{d+1}},$ it suffices to bound $H_{I}$ as
$I$ varies over all subsets of $\\{1,\ldots,n\\}$. In fact, we only need to
bound $H_{I}$ with $I=\\{1,\ldots,n\\}$, since
$(\bm{g},H)+\Lambda^{+}\subset(\bm{g}^{\prime},H^{\prime})+\Lambda^{+}$
implies $H\geq H^{\prime}$.

Without loss of generality assume that $\max_{i}H_{i}=H_{1}$. Since
$\bm{v}_{d+1}=\bm{0}$, for each $i>1$ there exist integers
$m_{i,1},\ldots,m_{i,d}$ such that

$\bm{g}_{i}-\bm{g}_{1}=\sum_{j=1}^{d}m_{i,j}\bm{v}_{j}.$

Now for each $j,$ let $m_{j}=\max_{i}(|m_{i,j}|)$. We claim that $m_{j}\leq
H_{1}-1$ for each $j$. To this end, if we denote by $\overline{\bm{\pi}}$ the
projection of $\bm{\pi}$ to $\mathbb{Z}^{d}$ then we may write

$\bm{g}_{1}=\overline{\bm{\pi}}+\sum_{j=1}^{d}n_{1,j}\bm{v}_{j},\qquad\bm{g}_{i}=\overline{\bm{\pi}}+\sum_{j=1}^{d}n_{i,j}\bm{v}_{j}$

for integers $n_{1,j},n_{i,j}$. Next observe that $\bm{g}_{1}$ and
$\bm{g}_{i}$ lie in the convex hull of $H_{1}A$, so it follows that $n_{1,j}$
and $n_{i,j}$ are nonnegative and that

$\sum_{j=1}^{d}n_{1,j}\leq H_{1},\qquad\sum_{j=1}^{d}n_{i,j}\leq H_{1}.$

In fact both of these inequalities are strict since
$\overline{\bm{\pi}}\neq\bm{0}$, so the they hold with $H_{1}-1$ in place of
$H_{1}$. In particular it follows that $0\leq n_{i,j},n_{1,j}\leq H_{1}-1$.
Therefore $|m_{i,j}|=|n_{i,j}-n_{1,j}|\leq H_{1}-1$, hence the claim since $i$
was arbitrary.

Now let

$\bm{\alpha}:=\bm{g}_{1}+\sum_{i=1}^{d}m_{j}\bm{v}_{j}$

and observe that $\bm{\alpha}\in\Big{(}(d+1)H_{1}-d\Big{)}A$ since
$\bm{g}_{1}\in H_{1}A$ and each $m_{j}\leq H_{1}-1$. We claim in fact that

$(\bm{\alpha},(d+1)H_{1}-d)\in\bigcap_{i=1}^{n}\bigg{(}(\bm{g}_{i},H_{i})+\Lambda^{+}\bigg{)}.$

It suffices to show that $\bm{\alpha}-\bm{g}_{i}\in\Lambda^{+}$ for each $i$.
Clearly $\bm{\alpha}-\bm{g}_{1}\in\Lambda^{+}$, and otherwise

$\bm{\alpha}-\bm{g}_{i}=\sum_{j=1}^{d}(m_{j}-m_{i,j})\bm{v}_{j}\in\Lambda^{+}$

because $m_{j}\geq m_{i,j}$ for each $i$. Therefore

$(\bm{\alpha},(d+1)H_{1}-d)+\Lambda^{+}\subseteq\bigcap_{i=1}^{n}\bigg{(}(\bm{g}_{i},H_{i})+\Lambda^{+}\bigg{)}=(\bm{g}_{I},H_{I})+\Lambda^{+},$

so $H_{I}\leq(d+1)H_{1}-d$. ∎

With these results in hand, it’s not too difficult to establish an effective
version of Khovanskii’s theorem for the case that the convex hull of $A$ is a
simplex:

###### Proof of Theorem 1.4.

By the previous lemmas, we can write

$\mathcal{C}_{A}(t)=\frac{P(t)}{(1-t)^{d+1}}$

where $\deg P\leq\text{vol}(\Delta_{A})\cdot(d+1)!-1-2d$. The division
algorithm furnishes $R,Q\in\mathbb{Q}[t]$ with $\deg R\leq d$ and $\deg Q=\deg
P-d-1$ such that

$\mathcal{C}_{A}(t)=\frac{P(t)}{(1-t)^{d+1}}=Q(t)+\frac{R(t)}{(1-t)^{d+1}}.$

Write $R(t)=a_{0}+a_{1}t+\cdots+a_{d}t^{d}$ where $a_{i}$ are (possibly zero)
rational numbers, and observe that

$\displaystyle\frac{R(t)}{(1-t)^{d+1}}$
$\displaystyle=(a_{0}+a_{1}t+\cdots+a_{d}t^{d})\sum_{n\geq
0}\binom{n+d}{d}t^{n}$ $\displaystyle=a_{0}\sum_{h\geq
0}\binom{h+d}{d}t^{h}+a_{1}\sum_{h\geq
1}\binom{h-1+d}{d}t^{h}+\cdots+a_{d}\sum_{h\geq d}\binom{h}{d}t^{h}$
$\displaystyle=\sum_{h\geq
0}\left(\sum_{k=0}^{d}a_{k}\binom{h+d-k}{d}\right)t^{h}.$

The final equality holds since $\binom{h+d-k}{d}$ vanishes for $0\leq h\leq
k$. In particular, it follows that there is some $p\in\mathbb{Q}[x]$ such that

$\frac{R(t)}{(1-t)^{d+1}}=\sum_{h\geq 0}p(h)t^{h}.$

This agrees with $\mathcal{C}_{A}(t)$ for all terms beyond $t^{\deg Q}$, and
the claim follows. ∎

##  4 A local-global structure theorem for sumsets: Proof of Theorem 1.3

In the previous section we proved results about the structure of the cone
$\mathcal{C}_{A}$ and deduced information about the cardinality of $hA$ for
all sufficiently large $h$. The goal of this section is to deduce information
about the structure of $hA$ instead. For example, one consequence of our work
will be an explicit description of $hA$ for all $h\in\mathbb{N}$ in terms of
the minimal elements of the cone $\mathcal{C}_{A}$:

######  Proposition 4.1.

Suppose $A\subset\mathbb{Z}^{d}$ has convex hull $\Delta_{A}$ a simplex. Say
the vertices of $\Delta_{A}$ are $\bm{v}_{1},\bm{v}_{2},\ldots,\bm{v}_{d+1}$,
and denote the minimal elements of the cone $\mathcal{C}_{A}$ by
$(\bm{g}_{1},H_{1}),(\bm{g}_{2},H_{2}),\ldots$ Then for all $h\in\mathbb{N}$,

$hA=\bigcup_{j}\bigg{\\{}\bm{g}_{j}+\sum_{i\leq
d+1}k_{i}\bm{v}_{i}:k_{i}\in\mathbb{N}\text{ for all $i$ and }\sum_{i\leq
d+1}k_{i}=h-H_{j}\bigg{\\}}.$

######  Remark.

We are slightly abusing our terminology, since we previously defined _minimal
element_ only for a given residue class $\mathcal{S}_{\bm{\pi}}$. The
collection of all the minimal elements from all the $\mathcal{S}_{\bm{\pi}}$
is what we mean by the minimal elements of $\mathcal{C}_{A}$.

While this proposition completely describes all iterated sumsets of $A$, it
does so in terms of the minimal elements of $\mathcal{C}_{A}$, whose structure
remains elusive. (Computationally the minimal elements can be determined
without much difficulty in view of Lemma 3.1.) Nonetheless, the fact that we
are able to prove such a result for all $h\in\mathbb{N}$ will prove critical
in our proof of Theorem 1.3, the main goal of this section.

Our first step is to rephrase Theorem 1.3 in a geometric form. To this end, we
introduce a new tool to our kit:

######  Definition 2.

Given a vertex $\bm{v}$ of the convex hull of $A$, define the _tangent cone at
$\bm{v}$_ by

$T_{\bm{v}}(A):=\bigcup_{h\geq 0}h(A-\bm{v}).$ (6)

Thus, for example, $T_{\bm{0}}(A)=\bigcup_{h\geq 0}hA$, the projection of the
cone $\mathcal{C}_{A}$ onto $\mathbb{Z}^{d}$ that deletes the final
coordinate.

Starting with the identity $hA=h\bm{v}+h(A-\bm{v})$, notice that in order for
$\bm{a}\in\mathbb{Z}^{d}$ to lie in $hA$ for some $h$, it must lie in
$h\bm{v}+T_{\bm{v}}(A)$ for each vertex. Thus, in a sense, the tangent cones
take into account local obstructions near each vertex of $\Delta_{hA}$ to
writing an element of $\mathbb{Z}^{d}$ as a positive linear combination of
elements of $A$. For the rest of this section, we will denote the vertices of
$\Delta_{A}$ by $\bm{v}_{1},\ldots,\bm{v}_{d+1}$; without loss of generality,
$\bm{v}_{d+1}=\bm{0}$. It is immediate that

$hA\subseteq\bigcap_{i=1}^{d+1}\Big{(}h\bm{v}_{i}+T_{\bm{v}_{i}}(A)\Big{)}.$

The content of Theorem 1.3 is that the reverse inclusion holds for large $h$.
In other words, for large $h$, the global structure of $hA$ is completely
determined by the local structure at each vertex of $\Delta_{hA}$.

Our approach will follow that of the previous section, except that we will
consider not just the single cone $\mathcal{C}_{A}$ but rather the $d+1$
different cones $\mathcal{C}_{i}:=\mathcal{C}_{A-\bm{v}_{i}}$. To each of
these cones we can associate quantities analogous to those in section 3: let
$\Lambda_{i}$ denote the lattice in $\mathbb{Z}^{d+1}$ spanned by
$(\bm{v}_{j}-\bm{v}_{i},1)$ with $1\leq j\leq d+1$, denote by
$\Lambda_{i}^{+}$ the set of nonnegative integer linear combinations of
$(\bm{v}_{j}-\bm{v}_{i},1)$ with $1\leq j\leq d+1$, and let $\Pi_{i}$ denote
the set of lattice points in the fundamental domain of $\Lambda_{i}$. For any
given $i$ and each $\bm{\pi}\in\Pi_{i}$, let $\mathcal{S}_{\bm{\pi},i}$ denote
the elements of $\mathcal{C}_{i}$ that are congruent to $\bm{\pi}$ modulo
$\Lambda_{i}$.

This notation allows us to describe the tangent cones $T_{\bm{v}_{i}}(A)$ in
terms of the minimal elements of $\mathcal{C}_{i}$. Let $m(\bm{\pi},i)$ be the
total number of minimal elements of $\mathcal{S}_{\bm{\pi},i}$, and enumerate
these minimal elements in the form
$\left(\bm{g}_{\bm{\pi},i}^{1},H_{\bm{\pi},i}^{1}\right),\left(\bm{g}_{\bm{\pi},i}^{2},H_{\bm{\pi},i}^{2}\right),\ldots$
In particular,

$\mathcal{S}_{\bm{\pi},i}=\bigcup_{j=1}^{m(\bm{\pi},i)}\bigg{(}\left(\bm{g}_{\bm{\pi},i}^{j},H_{\bm{\pi},i}^{j}\right)+\Lambda_{i}^{+}\bigg{)},$

whence

$T_{\bm{v}_{i}}(A)=\bigsqcup_{\bm{\pi}\in\Pi_{i}}\bigcup_{j=1}^{m(\bm{\pi},i)}\left\\{\bm{g}_{\bm{\pi},i}^{j}+\sum_{k=1}^{d+1}n_{k}(\bm{v}_{k}-\bm{v}_{i}):n_{k}\in\mathbb{N}\right\\}.$
(7)

One of the difficulties in working with tangent cones is that distinct sets
may have the same tangent cone. For example, if $A=\\{0,1,3,4\\}$ and
$B=\\{0,1,2,3,4\\}$ then $T_{0}(A)=T_{0}(B)=\mathbb{N}$ and
$T_{b}(A)=T_{b}(B)=-\mathbb{N}$, so the tangent cones lose some information
about the underlying set. In particular, the tangent cones only determine the
long term behavior of $hA$. In order to obtain the explicit bound on the phase
transition in Theorem 1.3, it turns out we will need insight into the
structure of $hA$ for _all_ $h\in\mathbb{N}$. In the example of
$A=\\{0,1,3,4\\}$, even though the elements $(2,2)$ and $(6,2)$ are both
minimal elements of residue class $(2,2)$ in $\mathcal{C}_{A}$, all of the
elements of $T_{0}(A)$ equivalent to 2 mod 4 can be expressed in the form
$2+4n$ so we can think of 2 as a minimal element of the points in $T_{0}(A)$
congruent to 2 mod 4. In other words, the tangent cone at 0 fails to recognize
6 as a minimal element mod 4 (see Figure 2). In one dimension, the natural
ordering on $\mathbb{Z}$ lets one get away with only knowing the smallest
minimal elements. For higher dimensions, however, one must keep track of all
of the minimal elements, which the cones $\mathcal{C}_{i}$ allow us to do;
this is what permits us to make the structure theorem given in [5] effective
for dimensions greater than 1.

Figure 2: The cone $\mathcal{C}_{A}$ over $A=\\{0,1,3,4\\}$ lying above the
tangent cone $T_{0}(A)$ at 0. The points lying above the residue class 2 mod 4
are labeled with boxes, and the minimal elements are labeled with shaded
boxes. In $\mathcal{C}_{A}$, it is clear that there are two minimal elements,
but we lose this distinction upon projecting onto $T_{0}(A)$.

It turns out that for any choices of index $i,j$, the minimal elements of
$\mathcal{C}_{i}$ and $\mathcal{C}_{j}$ are closely related to one another. To
state this as transparently and concretely as possible, we adopt our notation
from section 3: let $\Lambda$ be the lattice in $\mathbb{Z}^{d+1}$ generated
by
$\widetilde{\bm{0}},\widetilde{\bm{v}}_{1},\widetilde{\bm{v}}_{2},\ldots,\widetilde{\bm{v}}_{d}$,
fix a lattice point $\bm{\pi}$ in the fundamental domain of $\Lambda$, and let
$\mathcal{S}_{\bm{\pi}}$ be the collection of all points of $\mathcal{C}_{A}$
equivalent to $\bm{\pi}{\text{\rm\ (mod~{}$\Lambda$)}}$. Denote the minimal
elements of $\mathcal{S}_{\bm{\pi}}$ by
$(\bm{g}_{1},H_{1}),(\bm{g}_{2},H_{2}),\ldots,(\bm{g}_{n},H_{n})$.

######  Lemma 4.2.

For any $1\leq i\leq d$, the number of minimal elements in
$\mathcal{S}_{\bm{\pi}-\widetilde{\bm{v}}_{i},i}$ is precisely $n$, and (after
suitably permuting the order of the minimal elements) we have

$\bm{g}_{\bm{\pi}-\widetilde{\bm{v}}_{i},i}^{j}=\bm{g}_{j}-H_{j}\bm{v}_{i}\qquad\text{and}\qquad
H_{\bm{\pi}-\widetilde{\bm{v}}_{i},i}^{j}=H_{j}$

for all $j\leq n$.

###### Proof.

Observe that $h(A-\bm{v}_{i})=hA-h\bm{v}_{i}$ furnishes a bijection between
$hA$ and $h(A-\bm{v}_{i})$. Thus if $\left(\bm{g}_{j},H_{j}\right)$ is a
minimal element of $\mathcal{S}_{\bm{\pi}}$, then
$\left(\bm{g}_{j}-H_{j}\bm{v}_{i},H_{j}\right)$ must be a minimal element of
$\mathcal{C}_{i}$ congruent to $\bm{\pi}-(\bm{v}_{i},0)$ modulo $\Lambda_{i}$
and vice versa. The claim now follows since $\widetilde{\bm{0}}\in\Lambda_{i}$
for each $1\leq i\leq d+1$, so $\bm{\pi}-(\bm{v}_{i},0)$ is equivalent to
$\bm{\pi}-\widetilde{\bm{v}}_{i}$ modulo $\Lambda_{i}$. ∎

With this in hand, we can now prove our structure theorem for $hA$:

###### Proof of Theorem 1.3.

Our goal is to show that for all
$h\geq\text{vol}(\Delta_{A})\cdot(d+1)!-2-2d$,

$\bigcap_{i=1}^{d+1}\Big{(}h\bm{v}_{i}+T_{\bm{v}_{i}}(A)\Big{)}\subseteq hA.$
(8)

Let
$\Gamma=\text{span}_{\mathbb{Z}}\\{\bm{v}_{1},\ldots,\bm{v}_{d}\\}\subseteq\mathbb{Z}^{d}$
and
$\Gamma^{+}=\text{span}_{\mathbb{N}}\\{\bm{v}_{1},\ldots,\bm{v}_{d}\\}\subset\mathbb{Z}^{d}$.
Fix any lattice point $\bm{\pi}$ in the fundamental domain of $\Lambda$, and
consider the set $\mathcal{S}_{\bm{\pi}}$ consisting of all points of
$\mathcal{C}_{A}$ that are equivalent to $\bm{\pi}$ modulo $\Lambda$. Denote
the minimal elements of $\mathcal{S}_{\bm{\pi}}$ by
$(\bm{g}_{1},H_{1}),(\bm{g}_{2},H_{2}),\ldots,(\bm{g}_{n},H_{n})$. Note that
the assumption that $\bm{0}$ is a vertex of $\Delta_{A}$ implies that
$\widetilde{\bm{0}}\in\Lambda$, so every residue class of $\mathbb{Z}^{d+1}$
modulo $\Lambda$ contains a representative in $\Gamma$. In particular,
$\bm{g}_{i}\equiv\bm{g}_{j}{\text{\rm\ (mod~{}$\Gamma$)}}$ for any $i,j$.

Having set the notation, we turn to the proof. Let

$L_{\bm{\pi}}(h):=\left(\bigcap_{i=1}^{d+1}\Big{(}h\bm{v}_{i}+T_{\bm{v}_{i}}(A)\Big{)}\right)\cap(\bm{g}_{1}+\Gamma)$

and

$R_{\bm{\pi}}(h):=hA\cap(\bm{g}_{1}+\Gamma).$

Informally, $L_{\bm{\pi}}(h)$ is the “$\bm{\pi}$-part” of the left hand side
of (8), and $R_{\bm{\pi}}(h)$ is the “$\bm{\pi}$-part” of the right hand side.
Since $\bm{\pi}$ was arbitrarily chosen, to prove (8) it suffices to prove
that $L_{\bm{\pi}}(h)\subseteq R_{\bm{\pi}}(h)$ for all
$h\geq\text{vol}(\Delta_{A})\cdot(d+1)!-2-2d$.

We rewrite these two quantities, beginning with $L_{\bm{\pi}}(h)$. Combining
(7) with Lemma 4.2, we deduce

$\begin{split}L_{\bm{\pi}}(h)&=\bigcap_{i\leq
d+1}\bigcup_{j=1}^{m(\bm{\pi}-\widetilde{\bm{v}}_{i},i)}\left\\{h\bm{v}_{i}+\bm{g}_{\bm{\pi}-\widetilde{\bm{v}}_{i},i}^{j}+\sum_{k=1}^{d+1}n_{i,k}(\bm{v}_{k}-\bm{v}_{i}):n_{i,k}\in\mathbb{N}\right\\}\\\
&=\bigcap_{i\leq d+1}\bigcup_{j\leq
n}\left\\{h\bm{v}_{i}+\bm{g}_{j}-H_{j}\bm{v}_{i}+\sum_{k=1}^{d+1}n_{i,k}(\bm{v}_{k}-\bm{v}_{i}):n_{i,k}\in\mathbb{N}\right\\}\end{split}$
(9)

Next we turn to $R_{\bm{\pi}}(h)$. Note that any point of $R_{\bm{\pi}}(h)$
has the form $\bm{g}_{j}+\sum_{i=1}^{d}k_{i}\bm{v}_{i}$, which lives in $hA$
whenever $H_{j}+\sum_{i=1}^{d}k_{i}\leq h$. Since $(\bm{g}_{j},H_{j})$ is a
minimal element, we deduce

$R_{\bm{\pi}}(h)=\bigcup_{j\leq
n}\left\\{\bm{g}_{j}+\sum_{i=1}^{d}k_{i}\bm{v}_{i}:k_{i}\in\mathbb{N}\text{
and }\sum_{i=1}^{d}k_{i}\leq h-H_{j}\right\\}.$ (10)

Our strategy from here will be to dissect $L_{\bm{\pi}}(h)$ into two pieces,
one that only depends on $\bm{\pi}$ and lives in $R_{\bm{\pi}}(h)$ for
sufficiently large $h$, the other depending on $h$ in a tame enough way that
it lives in $R_{\bm{\pi}}(h)$ for all $h\in\mathbb{N}$.

Exactly as in the proof of Lemma 3.2, we may write

$\bigcap_{j\leq
n}\bigg{(}(\bm{g}_{j},H_{j})+\Lambda^{+}\bigg{)}=(\bm{g}_{\bm{\pi}},H_{\bm{\pi}})+\Lambda^{+}$
(11)

with $H_{\bm{\pi}}\leq\text{vol}(\Delta_{A})\cdot(d+1)!-1-2d$. Set

$\mathcal{P}_{\bm{\pi}}:=\left\\{\bm{g}_{\bm{\pi}}-\sum_{i=1}^{d}n_{i}\bm{v}_{i}:n_{i}\in\mathbb{Z}_{>0}\right\\}\cap
L_{\bm{\pi}}(h).$

It immediately follows that $\mathcal{P}_{\bm{\pi}}\subseteq R_{\bm{\pi}}(h)$
whenever $h\geq H_{\bm{\pi}}-1$. We claim that
${L_{\bm{\pi}}(h)\setminus\mathcal{P}_{\bm{\pi}}\subseteq R_{\bm{\pi}}(h)}$
for all $h\in\mathbb{N}$, thus completing the proof.

Pick $\bm{a}\in L_{\bm{\pi}}(h)\setminus\mathcal{P}_{\bm{\pi}}$. Since
$\bm{a}\not\in\mathcal{P}_{\bm{\pi}}$, we may write

$\bm{a}=\bm{g}_{\bm{\pi}}+\sum_{k=1}^{d}m_{k}\bm{v}_{k}$

where $m_{k}$ are integers with at least one non-negative, say $m_{1}\geq 0$.
On the other hand, since $\bm{a}\in L_{\bm{\pi}}(h)$, the identity (9) implies
the existence of $j$ such that

$\bm{a}=h\bm{v}_{1}+\bm{g}_{j}-H_{j}\bm{v}_{1}+\sum_{k=2}^{d+1}n_{k}(\bm{v}_{k}-\bm{v}_{1}).$
(12)

Comparing these two expressions for $\bm{a}$, we deduce

$\bm{g}_{\bm{\pi}}-\bm{g}_{j}=\left(h-H_{j}-m_{1}-\sum_{k=2}^{d+1}n_{k}\right)\bm{v}_{1}+\sum_{k=2}^{d}(n_{k}-m_{k})\bm{v}_{k}.$

But from (11) we know $\bm{g}_{\bm{\pi}}-\bm{g}_{j}\in\Gamma^{+}$, whence

$h-H_{j}-m_{1}-\sum_{k=2}^{d+1}n_{k}\geq 0.$

Since $m_{1}\geq 0$, it follows that

$\sum_{k=2}^{d+1}n_{k}\leq h-H_{j}.$

Keeping this inequality in mind and regrouping the terms in (12), we conclude
from (10) that $\bm{a}$ satisfies the membership requirements of
$R_{\bm{\pi}}(h)$. This concludes the proof. ∎

######  Remark.

Proposition 4.1 isn’t a corollary of Theorem 1.3; its conclusion is stronger
(holding for all $h\in\mathbb{N}$), and its hypotheses more relaxed (there’s
no assumption about $A-A$ generating $\mathbb{Z}^{d}$ additively). It is,
however, a porism: after shifting $A$ by one of the vertices in its convex
hull we may assume that $\bm{0}$ is a vertex of $\Delta_{A}$, and the
proposition follows from (10) by taking the union over all lattice points
$\bm{\pi}$ in the fundamental domain of $\Lambda$.

##  5 A Brion-type formula for sumsets

Recall that in section 3 we proved results on the cardinality of $hA$,
essentially by realizing the generating function of $|hA|$ in two different
ways and comparing the coefficients. In section 4 we explored the structure of
$hA$ by other means, exploiting the relationship among the tangent cones of
$A$. The goal of this section is to demonstrate a hybrid of these approaches:
to explore the structure of $hA$ by associating a generating function to the
tangent cones of $A$. The outcome will be a compact formula for computing the
elements of $hA$ for all large $h$. For simplicity we shall restrict ourselves
to the dimension 1 case, but with more effort we expect our approach should
generalize to arbitrary dimension. We give an indication of how to do so in
section 7, and invite the motivated reader to carry this out.

For the rest of this section we assume that $0$ is the smallest element of
$A\subset\mathbb{Z}$ and that $\gcd A=1$, and denote the largest element of
$A$ by $b$. The cardinality $|hA|$ can be viewed as assigning to each point of
$hA$ a weight of $1$ and summing all the weights, and we can obtain more
refined information about the structure of the sumset $hA$ by assigning
different weights to its elements. Introducing a formal variable $x$, we
assign to any set $S\subseteq\mathbb{Z}$ the generating function

$\sigma_{S}(x)=\sum_{a\in S}x^{a}.$ (13)

For example, if $A=\\{0,3,4,7\\}$, then $\sigma_{A}(x)=1+x^{3}+x^{4}+x^{7}$.

Recall that the tangent cone of $A$ at $v$ is defined by

$T_{v}(A)=\bigcup_{h\geq 0}h(A-v).$

To each tangent cone $T_{v}(A)$ we may associate the generating function
$\sigma_{T_{v}(A)}(x)$, but for brevity we abuse notation and simply write

$\sigma_{v}(x)=\sum_{a\in T_{v}(A)}x^{a}.$ (14)

We shall prove that the structure of $hA$ can be simply and compactly
described in terms of $\sigma_{0}(x)$ and $\sigma_{b}(x)$. More precisely:

######  Theorem 5.1.

Given $A\subset\mathbb{Z}$ with $\min{A}=0$, $\max{A}=b$, and $\gcd A=1$.
Define $\sigma_{v}(x)$ as in (14). Then both $\sigma_{0}(x)$ and
$\sigma_{b}(x)$ are rational functions in $x$, and for all non-negative $h\geq
2b-4$ we have

$\sigma_{hA}(x)=\sigma_{0}(x)+x^{hb}\sigma_{b}(x).$ (15)

######  Remark.

This is analogous to a formula discovered by Brion [2] that relates the
lattice generating function of a convex polytope to the lattice generating
functions of its tangent cones. See section 7 for a generalization of our
formula to higher dimensions.

Before presenting the proof of Theorem 5.1 we build intuition by applying it
to the simple example $A=\\{0,2,5\\}$ mentioned in the introduction. Observe
that

$T_{0}(A)=\\{0,2,4,5,6,7,8,9,\ldots\\}=\mathbb{N}\setminus\\{1,3\\}.$

Since every element of $T_{0}(A)$ can be written uniquely in the form $m+5n$
where $m\in\\{0,2,4,6,8\\}$ and $n\in\mathbb{N}$, we find

$\sigma_{0}(x)=\frac{1+x^{2}+x^{4}+x^{6}+x^{8}}{1-x^{5}}.$

On the other hand, note that

$T_{5}(A)=\\{0,-3,-5,-6,-8,-9,-10,\ldots\\}=-\mathbb{N}\setminus\\{-1,-2,-4,-7\\},$

and it follows that

$\sigma_{5}(x)=\frac{1+x^{-3}+x^{-6}+x^{-9}+x^{-12}}{1-x^{-5}}.$

Theorem 5.1 therefore implies that for all $h\geq 6$,

$\displaystyle\sigma_{hA}(x)$
$\displaystyle=\frac{1+x^{2}+x^{4}+x^{6}+x^{8}}{1-x^{5}}+x^{5h}\cdot\frac{1+x^{-3}+x^{-6}+x^{-9}+x^{-12}}{1-x^{-5}}$
$\displaystyle=\frac{1+x^{2}+x^{4}+x^{6}+x^{8}-x^{5h-7}(1+x^{3}+x^{6}+x^{9}+x^{12})}{1-x^{5}}$

a compact way to express the elements of $hA$ whenever $h$ is large. (In fact,
one can manually check that this identity holds for all $h\geq 3$.)

A key role in the proof of Theorem 5.1 is played by a generalization of the
sumset generating series (4). Any point in $\mathcal{C}_{A}$ can be written in
the form $(a,h)$, where $a\in hA$. We define the formal power series
$\mathcal{C}_{A}(x,t)\in\mathbb{Q}\llbracket x,t\rrbracket$ by

$\mathcal{C}_{A}(x,t):=\sum_{(a,h)\in\mathcal{C}_{A}}x^{a}t^{h}.$ (16)

From the definition, we immediately obtain the formula

$\mathcal{C}_{A}(x,t)=\sum_{h\geq 0}\sigma_{hA}(x)t^{h}.$ (17)

As in the proof of Theorem 1.4, we will proceed by expressing
$\mathcal{C}_{A}$ as a rational function in $x$ and $t$. Recall that $\Lambda$
is defined to be the vectors spanned by the lifts of the convex hull of $A$;
in this case, we simply have $\Lambda=\\{(bn,m+n):m,n\in\mathbb{Z}\\}$, and
$\Lambda^{+}=\\{(bn,m+n):m,n\in\mathbb{N}\\}$. For brevity we denote the
points of $\mathcal{C}_{A}$ congruent to $(a,1)$ modulo $\Lambda$ by
$\mathcal{S}_{a}$, following our convention from section 2.

Recall that one of the technical difficulties in our proof of Theorem 1.4 was
the possibility of multiple generators (minimal elements) of
$\mathcal{S}_{a}$. We circumvent this here by introducing the concept of a
_virtual generator_ , a single point that generates all of $\mathcal{S}_{a}$
plus possibly a few extraneous points.

######  Proposition 5.2.

Given $a\in\\{0,1,\ldots,b-1\\}$, there exists a unique
$(g_{a},h_{a})\in\mathbb{N}^{2}$ such that
$\mathcal{S}_{a}\subset(g_{a},h_{a})+\Lambda^{+}$ and the extraneous set

$E_{a}:=\bigg{(}(g_{a},h_{a})+\Lambda^{+}\bigg{)}\setminus\mathcal{S}_{a}$

is finite. We call $(g_{a},h_{a})$ the _virtual generator_ of
$\mathcal{S}_{a}$.

Before proving this, we briefly apply the proposition to the example
$A=\\{0,1,7,8\\}$ from section 2. Recall (see Figure 1) that

$\mathcal{S}_{4}=\bigg{(}(4,4)+\Lambda^{+}\bigg{)}\cup\bigg{(}(28,4)+\Lambda^{+}\bigg{)},$

i.e. $\mathcal{S}_{4}$ has two minimal elements $(4,4)$ and $(28,4)$.
Examining Figure 1, we see that $(4,1)$ is a virtual generator of
$\mathcal{S}_{4}$, generating all of $\mathcal{S}_{4}$ plus the extraneous set

$E_{4}:=\bigg{(}(4,1)+\Lambda^{+}\bigg{)}\setminus\mathcal{S}_{4}=\left\\{(4,1),(4,2),(4,3),(12,2),(12,3),(12,4),(20,3),(20,4),(20,5)\right\\}.$

With this intuition in hand, we prove the proposition.

###### Proof of Proposition 5.2.

First we prove existence. Note that $(0,0)$ is a virtual generator for
$S_{0}=\Lambda^{+}$, so assume $1\leq a<b$. Then it is immediate that
$\mathcal{S}_{a}\subset(a,1)+\Lambda^{+}$. Choose maximal $m,n\in\mathbb{N}$
such that

$\mathcal{S}_{a}\subset(a+bn,1+m+n)+\Lambda^{+},$

i.e. such that $\mathcal{S}_{a}\not\subset(a+bk,1+j+k)+\Lambda^{+}$ whenever
$j>m$ or $k>n$; such integers are guaranteed to exist since $\mathcal{S}_{a}$
has finitely many minimal elements. We claim $(g_{a},h_{a})=(a+bn,1+m+n)$ is a
virtual generator of $\mathcal{S}_{a}$.

Suppose for contradiction that $E_{a}$ were infinite. Since
$(a,h)+\Lambda^{+}\subset\mathcal{S}_{a}$ whenever $(a,h)\in\mathcal{S}_{a}$,
we must have either $\\{(g_{a},h_{a}+n):n\in\mathbb{N}\\}\subset E_{a}$, in
which case $\mathcal{S}_{a}\subset(g_{a},h_{a})+(b,1)+\Lambda^{+}$, or
$\\{(g_{a}+bn,h_{a}+n):n\in\mathbb{N}\\}\subset E_{a}$, in which case
$\mathcal{S}_{a}\subset(g_{a},h_{a})+(0,1)+\Lambda^{+}$. Either way we reach a
contradiction to the definition of $(g_{a},h_{a})$. This concludes the proof
of existence.

Uniqueness immediately follows because if $(a,h)\neq(b,k)$ then
$(a,h)+\Lambda^{+}$ and $(b,k)+\Lambda^{+}$ differ by infinitely many points.
∎

Note that in the example $A=\\{0,1,7,8\\}$ we considered following Proposition
5.2, all the heights appearing in the extraneous set were quite small, as was
the height of the virtual generator. Our previous work implies that this is a
general phenomenon. First, observe that the height of any virtual generator is
bounded by the heights of the minimal elements, which we have a bound for
thanks to Lemma 3.1:

$h_{a}\leq b-1.$ (18)

To bound the heights appearing in the extraneous set, note that Proposition
5.2 implies

$\mathcal{S}_{a}(x,t)=\frac{x^{g_{a}}t^{h_{a}}}{(1-t)(1-x^{b}t)}-\sum_{(n,h)\in
E_{a}}x^{n}t^{h}=\frac{x^{g_{a}}t^{h_{a}}-(1-t)(1-x^{b}t)\sum\limits_{(n,h)\in
E_{a}}x^{n}t^{h}}{(1-t)(1-x^{b}t)}.$

Specializing this to $x=1$ and applying Lemmas 3.1 and 3.2, we deduce:

######  Corollary 5.3.

For all $(n,h)\in E_{a}$ we have $h\leq 2b-5$.

It follows that

$\mathcal{C}_{A}(x,t)=Q(x,t)+\frac{1}{(1-t)(1-x^{b}t)}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}$
(19)

where $Q\in\mathbb{Q}[x,t]$ has $t$-degree less than or equal to $2b-5$.

To prove Theorem 5.1 we need to understand the structure of the tangent cones,
which admit a simple expression in terms of the virtual generators of $A$.

######  Proposition 5.4.

The tangent cone $T_{0}(A)$ can be written as

$T_{0}(A)=\bigcup_{a=0}^{b-1}\Big{(}g_{a}+b\cdot\mathbb{N}\Big{)}$

where $b\cdot\mathbb{N}=\\{0,b,2b,\ldots\\}$.

###### Proof.

First, observe that $g_{a}\in T_{0}(A)$. Indeed,
$(g_{a},k)\in(g_{a},h_{a})+\Lambda^{+}$ for all $k\geq h_{a}$, and only
finitely many of these can live outside of $\mathcal{S}_{a}$; it follows that
$\mathcal{S}_{a}$, and hence $\mathcal{C}_{a}$, must contain a point of the
form $(g_{a},h)$ for some $h\in\mathbb{N}$. By construction, $g_{a}\equiv
a{\text{\rm\ (mod~{}$b$)}}$. Thus the claim boils down to showing that $g_{a}$
is the _smallest_ element of $T_{0}(A)$ congruent to $a{\text{\rm\
(mod~{}$b$)}}$.

Pick any $m\in\\{n\in T_{0}(A):n\equiv a{\text{\rm\ (mod~{}$b$)}}\\}$. Since
$m\in T_{0}(A)$, we deduce $(m,h)\in\mathcal{C}_{A}$ for some
$h\in\mathbb{N}$, and $m\equiv a{\text{\rm\ (mod~{}$b$)}}$ then implies that
$(m,h)\in\mathcal{S}_{a}$. By definition,
$\mathcal{S}_{a}\subset(g_{a},h_{a})+\Lambda^{+}$, so $m\geq g_{a}$. ∎

Furthermore, the virtual generators possess a similar symmetry to the minimal
elements of $\mathcal{C}_{A}$.

######  Proposition 5.5.

Given $0\leq a<b$, let $(g_{a},h_{a})$ denote the corresponding virtual
generator of $A$ and $(g_{a}^{\prime},h_{a}^{\prime})$ denote the virtual
generator of $b-A$. Then $h_{a}=h_{b-a}^{\prime}$ and
$g_{b-a}^{\prime}=g_{a}-bh_{a}$

###### Proof.

Write

$E_{a}=\left\\{(g_{a},h_{a})+m(0,1)+n(b,1):(m,n)\in I_{a}\right\\}$

where $I_{a}\subset\mathbb{N}\times\mathbb{N}$ is some finite set. If we
denote the elements of $\mathcal{C}_{A-b}$ congruent to $b-a{\text{\rm\
(mod~{}$b$)}}$ by $\mathcal{S}_{b-a}^{\prime}$, then since $h(b-A)=hb-hA$,

$\mathcal{S}_{b-a}^{\prime}=\bigg{(}(g_{a}-bh_{a},h_{a})+\text{span}_{\mathbb{N}}\\{(0,1),(-b,1)\\}\bigg{)}\setminus
E_{b-a}^{\prime}$

where

$E_{b-a}^{\prime}=\left\\{(g_{a}-bh_{a},h_{a})+m(0,1)+n(-b,1):(m,n)\in
I_{a}\right\\}.$

The claim now follows by uniqueness of virtual generators. ∎

###### Proof of Theorem 5.1.

By Propositions 5.4 and 5.5, we obtain the following expressions for the power
series corresponding to the tangent cones $T_{0}(A)$ and $T_{b}(A)$:

$\sigma_{0}(x)=\frac{1}{1-x^{b}}\sum_{a=0}^{b-1}x^{g_{a}}\qquad\qquad\text{and}\qquad\qquad\sigma_{b}(x)=\frac{1}{1-x^{-b}}\sum_{a=0}^{b-1}x^{g_{a}-bh_{a}}$

where $(g_{a},h_{a})$ are the virtual generators corresponding to each $0\leq
a<b$. From (19) we know the existence of some $Q\in\mathbb{Q}[x,t]$ of
$t$-degree less than or equal to $2b-5$ such that

$\displaystyle\mathcal{C}_{A}(x,t)$
$\displaystyle=Q(x,t)+\frac{1}{(1-t)(1-x^{b}t)}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}$
$\displaystyle=Q(x,t)+\left(\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}\right)\left(\sum_{h\geq
0}t^{h}\right)\left(\sum_{j\geq 0}x^{jb}t^{j}\right)$
$\displaystyle=Q(x,t)+\left(\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}\right)\sum_{h\geq
0}\left(\sum_{j=0}^{h}x^{jb}\right)t^{h}.$

We can rearrange the product of sums above as follows:

$\displaystyle\sum_{h\geq
0}\Bigg{[}\frac{1}{1-x^{b}}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}$
$\displaystyle+\frac{x^{hb}}{1-x^{-b}}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}\Bigg{]}t^{h}=$
$\displaystyle\sum_{h\geq
0}\left[\frac{1}{1-x^{b}}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}\right]t^{h}$
$\displaystyle+\sum_{h\geq
0}\left[\frac{x^{hb}}{1-x^{-b}}\sum_{a=0}^{b-1}x^{g_{a}}t^{h_{a}}\right]t^{h}.$

Setting $H=\max\\{h_{0},\ldots,h_{b-1}\\}$, we may further rewrite this in the
form

$P(x,t)+\sum_{h\geq
H}\left[\frac{1}{1-x^{b}}\sum_{a=0}^{b-1}x^{g_{a}}\right]t^{h}+\sum_{h\geq
H}\left[\frac{x^{hb}}{1-x^{-b}}\sum_{a=0}^{b-1}x^{g_{a}-bh_{a}}\right]t^{h}=P(x,t)+\sum_{h\geq
H}(\sigma_{0}(x)+x^{hb}\sigma_{b}(x))t^{h},$

where $P(x,t)\in(\mathbb{Q}(x))[t]$ has $t$-degree strictly less than $H$.
Putting this all together, we’ve shown that

$\mathcal{C}_{A}(x,t)=P(x,t)+Q(x,t)+\sum_{h\geq
H}(\sigma_{0}(x)+x^{hb}\sigma_{b}(x))t^{h}.$

On the other hand, recall from (17) that

$\mathcal{C}_{A}(x,t)=\sum_{h\geq 0}\sigma_{hA}(x)t^{h}.$

It follows that $\sigma_{hA}(x)=\sigma_{0}(x)+x^{hb}\sigma_{b}(x)$ for
$h>\max\\{\deg_{t}Q,H-1\\}$. Since $\deg_{t}Q\leq 2b-5$ by (19) and $H\leq
b-1$ by (18), we conclude that

$\phantom{\qquad\forall
h\geq\max\\{2b-4,b-1\\}.}\sigma_{hA}(x)=\sigma_{0}(x)+x^{hb}\sigma_{b}(x)\qquad\forall
h\geq\max\\{2b-4,b-1\\}.$

If $b\geq 3$ this implies the claim. The only remaining case is $b=1$ and
$b=2$, i.e. $A=\\{0,1\\}$ and $A=\\{0,1,2\\}$, respectively. In either case,
(15) trivially holds for all $h\in\mathbb{N}$. ∎

##  6 Explicit Khovanskii for arbitrary sumsets: Proof of Theorem 1.2

Recall that in section 2 we proved Theorem 1.2 under the additional hypothesis
that the convex hull of $A$ is a simplex. The goal of this section is to prove
Theorem 1.2 in full generality.

Consider a given $A\subset\mathbb{Z}^{d}$ consisting of precisely $d+2$
points. As usual, we may assume that $A$ contains $0$ and that $A$ generates
$\mathbb{Z}^{d}$ additively. Denote the nonzero elements of $A$ by
$\bm{v}_{0},\ldots,\bm{v}_{d}$; without loss of generality, we may assume
$\bm{v}_{1},\ldots,\bm{v}_{d}$ are linearly independent. Our starting point is
the observation that

$hA=\bigcup_{j=0}^{h}\left(j\bm{v}_{0}+C_{h-j}\right),\quad\text{where}\quad
C_{k}:=\left\\{\sum_{i=1}^{d}n_{i}\bm{v}_{i}:n_{i}\in\mathbb{N}\text{ and
}\sum_{i=1}^{d}n_{i}\leq k\right\\}.$ (20)

We’re naturally led to study truncated cones of the form

$A_{j,h}:=j\bm{v}_{0}+C_{h-j}.$

When $h$ is small enough, all these truncated cones are disjoint, in which
case we can compute $|hA|$ easily. Set

$H:=\max\\{\ell:A_{j,h}\cap A_{j^{\prime},h}=\varnothing\text{ whenever }j\neq
j^{\prime}\text{ and }h<\ell\\};$

this is necessarily finite, since the $d+1$ nonzero elements of $A$ are
linearly dependent. Thus when $h<H$,

$|hA|=\sum_{j=0}^{h}|A_{j,h}|=\sum_{j=0}^{h}|C_{h-j}|=\sum_{j=0}^{h}\binom{h-j+d}{d}=\binom{h+d+1}{d+1}.$

This agrees with the first part of Theorem 1.2. Our task now is to compute the
value of $H$, and to explore what happens when $h\geq H$, i.e. once the
truncated cones $A_{j,h}$ intersect one another. We are able to give an
explicit description of such intersections, but to do so we require a bit more
notation.

Let $B:=\\{\bm{v}_{1},\bm{v}_{2},\ldots,\bm{v}_{d}\\}$, and consider the cone
$\Gamma:=\textup{span}_{\mathbb{N}}\ B.$ Since $B$ is a basis of
$\mathbb{R}^{d}$, the $\mathbb{Z}$-span of $B$ has finite index in
$\mathbb{Z}^{d}$, whence $\bm{v}_{0}$ has finite order in
$\mathbb{Z}^{d}/\textup{span}_{\mathbb{Z}}\ B$. Let $N$ denote the order of
$\bm{v}_{0}$; in particular, $N\bm{v}_{0}$ is an element of the lattice
$\textup{span}_{\mathbb{Z}}\ B$. Finally, define $\bm{w}\in\Gamma$ via the
relation

$\Gamma\cap(N\bm{v}_{0}+\Gamma)=\bm{w}+\Gamma.$

We can now state the promised explicit description of the intersections of
truncated cones $A_{j,h}$. First, observe that $C_{k}\subset\Gamma$ for any
$k$; it immediately follows that if $A_{j,h}$ and $A_{j^{\prime},h}$
intersect, then $j\equiv j^{\prime}{\text{\rm\ (mod~{}$N$)}}$. Moreover, it
turns out any intersection boils down to a single intersection:

######  Lemma 6.1.

Suppose all elements of $I\subseteq[0,h]$ are congruent (mod $N$). Then
$\bigcap\limits_{j\in I}A_{j,h}=A_{m,h}\cap A_{M,h},$ where $m:=\min\ I$ and
$M:=\max\ I$.

It therefore suffices to describe the intersection of two cones:

######  Lemma 6.2.

Let $a,j,h\in\mathbb{N}$. Then $A_{j,h}\cap
A_{j+aN,h}=j\bm{v}_{0}+a\bm{w}+C_{h-j-aH},$ where $C_{k}:=\varnothing$ for
$k<0$.

We will prove Lemmas 6.1 and 6.2 below, using the same circle of ideas we
developed in Sections 2–5. But first, we demonstrate their utility by giving a
short derivation of Theorem 1.2 from them.

Recall from (20) that we can express $hA$ as a union of truncated cones.
Breaking this up further (mod $N$), we have

$hA=\bigsqcup_{j=0}^{N-1}\bigcup_{a\geq 0}A_{j+aN,h}.$ (21)

Inclusion-exclusion implies

$\left|\bigcup_{a\geq
0}A_{j+aN,h}\right|=\sum_{I\subseteq\left[\frac{h-j}{N}\right]}(-1)^{|I|+1}\Bigg{|}\bigcap_{a\in
I}A_{j+aN,h}\Bigg{|}$ (22)

where $[\alpha]:=\\{n\in\mathbb{N}:n\leq\alpha\\}$. Lemma 6.1 allows us to
simplify the intersection on the right hand side, whence by Lemma 6.2 we find

$\Bigg{|}\bigcap_{a\in I}A_{j+aN,h}\Bigg{|}=|A_{j+mN,h}\cap
A_{j+MN,h}|=|C_{h-(j+mN)-(M-m)H}|=\binom{h-(j+mN)-(M-m)H+d}{d}$ (23)

where $m:=\min\ I$ and $M:=\max\ I$.

We now claim that the only subsets $I$ that do not cancel out in (22) are the
singleton sets $\\{k\\}$ and sets of the form $\\{k,k+1\\}$. To see this, fix
$m,M$ with $M\geq m+2$. All the $I$ in (22) that have minimal element $m$ and
maximal element $M$ contribute

$\sum_{\begin{subarray}{c}I\subseteq\\{m,m+1,\ldots,M\\}\\\ m,M\in
I\end{subarray}}(-1)^{|I|+1}\Bigg{|}\bigcap_{a\in
I}A_{j+aN,h}\Bigg{|}=\sum_{\begin{subarray}{c}I\subseteq\\{m,m+1,\ldots,M\\}\\\
m,M\in I\end{subarray}}(-1)^{|I|+1}\binom{h-(j+mN)-(M-m)H+d}{d}.$

The key observation is that the summands on the right hand side do not depend
on $I$, but only on its cardinality. Ordering the sum by size of $I$, we find

$\begin{split}\sum_{\begin{subarray}{c}I\subseteq\\{m,m+1,\ldots,M\\}\\\
m,M\in I\end{subarray}}&(-1)^{|I|+1}\Bigg{|}\bigcap_{j\in
I}A_{j,h}\Bigg{|}=\\\
&=\binom{h-(j+mN)-(M-m)H+d}{d}\sum_{\ell=2}^{M-m+1}(-1)^{\ell+1}\\#\Big{\\{}I\subseteq\\{m,\ldots,M\\}:m,M\in
I\text{ and }|I|=\ell\Big{\\}}\\\
&=\binom{h-(j+mN)-(M-m)H+d}{d}\sum_{\ell=2}^{M-m+1}(-1)^{\ell+1}\binom{M-m-1}{\ell-2}=0.\end{split}$

Thus, the only $I$ that contribute to (22) are singletons or pairs of
consecutive integers, as claimed. Combining this with (21) and (22) yields

$\begin{split}|hA|&=\sum_{j=0}^{N-1}\sum_{a\in\left[\frac{h-j}{N}\right]}\bigg{(}|A_{j+aN,h}|-|A_{j+aN,h}\cap
A_{j+(a+1)N,h}|\Bigg{)}=\sum_{k=0}^{h}\bigg{(}|C_{h-k}|-|C_{h-k-H}|\Bigg{)}\\\
&=\sum_{k=0}^{h}|C_{h-k}|-\sum_{k=H}^{h+H}|C_{h-k}|=\sum_{k=0}^{h}\binom{h-k+d}{d}-\sum_{k=H}^{h}\binom{h-k+d}{d}\\\
&=\binom{h+d+1}{d+1}-\binom{h-H+d+1}{d+1}\end{split}$

for any $h\geq H$.

All that remains is to compute $H$. We can do this easily by using
Khovanskii’s theorem: for any $h\geq H$,

$\binom{h+d+1}{d+1}-\binom{h-H+d+1}{d+1}$

is a polynomial of degree $d$ and leading coefficient $H/d!$, so Theorem 1.1
implies

$H=\text{vol}(\Delta_{A})\cdot d!.$

This concludes the proof of Theorem 1.2 assuming Lemmas 6.1 and 6.2. We now
circle back and prove these.

As in our work in Sections 2–5, we disentangle the geometry from the
combinatorics by lifting $A$ and its associated truncated cones $A_{j,h}$ to
one dimension higher. More precisely, recall that the _lift_ of
$\bm{v}\in\mathbb{Z}^{d}$ is the vector
$\widetilde{\bm{v}}:=(\bm{v},1)\in\mathbb{Z}^{d+1}$. Then

$A_{j,h}=\pi\Big{(}\widetilde{A}_{j}\cap\mathcal{H}_{h}\Big{)}$ (24)

where

$\widetilde{A}_{j}:=j\widetilde{\bm{v}}_{0}+\widetilde{\Gamma}\quad,\quad\widetilde{\Gamma}:=\text{span}_{\mathbb{N}}\\{\widetilde{\bm{0}},\widetilde{\bm{v}}_{1},\ldots,\widetilde{\bm{v}}_{d}\\}\quad,\quad\mathcal{H}_{h}:=\left\\{\bm{x}\in\mathbb{R}^{d+1}:\text{height}(\bm{x})=h\right\\},$

and $\pi:\mathbb{R}^{d+1}\to\mathbb{R}^{d}$ is the projection onto the first
$d$ coordinates. Thus $\widetilde{\Gamma}\subseteq\mathbb{Z}^{d+1}$ is an
infinite cone, $\widetilde{A}_{j}$ is a translation of this cone, and we are
viewing $A_{j,h}$ as a level set of this translated cone.

###### Proof of Lemma 6.1.

By (24), it suffices to prove

$\underbrace{\bigcap_{j\in
I}\widetilde{A}_{j}}_{L}=\underbrace{\widetilde{A}_{m}\cap\widetilde{A}_{M}}_{R}.$
(25)

It is clear that $L\subseteq R$, so we focus on the reverse inclusion. Fix any
$j\in[m,M]$ congruent to $m{\text{\rm\ (mod~{}$N$)}}$; our goal is to show
that $\widetilde{A}_{j}\supseteq R.$ Because $R$ is an intersection of cones
we may write $R=\bm{x}+\widetilde{\Gamma}$ for some
$\bm{x}\in\mathbb{Z}^{d+1}$. In particular, there exist
$\bm{y},\bm{z}\in\widetilde{\Gamma}$ such that

$\bm{x}=m\widetilde{\bm{v}}_{0}+\bm{y}=M\widetilde{\bm{v}}_{0}+\bm{z}.$

It follows that

$\bm{x}-j\widetilde{\bm{v}}_{0}=(M-j)\widetilde{\bm{v}}_{0}+\bm{z}\in\widetilde{\Gamma}-\widetilde{\Gamma},$
(26)

since $(M-j)\widetilde{\bm{v}}_{0}$ is a positive integer multiple of
$N\widetilde{\bm{v}}_{0}$, which lives in the lattice
$\widetilde{\Gamma}-\widetilde{\Gamma}$ by definition of $N$.

Next, write $j=m+t(M-m)$ for some $t\in[0,1]$. It follows that

$\bm{x}-j\widetilde{\bm{v}}_{0}=(1-t)\bm{y}+t\bm{z}\in\Delta_{\widetilde{\Gamma}},$

the convex hull of $\widetilde{\Gamma}$. Combining this with (26), we deduce
that $\bm{x}-j\widetilde{\bm{v}}_{0}\in\widetilde{\Gamma}$, whence
$R=\bm{x}+\widetilde{\Gamma}\subseteq
j\widetilde{\bm{v}}_{0}+\widetilde{\Gamma}=\widetilde{A}_{j}.$

∎

###### Proof of Lemma 6.2.

Recall that $\Gamma\cap(N\bm{v}_{0}+\Gamma)=\bm{w}+\Gamma.$ It immediately
follows that

$\widetilde{A}_{0}\cap\widetilde{A}_{N}=(\bm{w},\eta)+\widetilde{\Gamma}$

for some $\eta$. This implies

$\widetilde{A}_{kN}\cap\widetilde{A}_{(k+1)N}=(kN\widetilde{v}_{0}+\widetilde{A}_{0})\cap(kN\widetilde{v}_{0}+\widetilde{A}_{N})=(\bm{w},\eta)+\widetilde{A}_{kN}.$

From this we deduce

$\begin{split}\widetilde{A}_{kN}\cap\widetilde{A}_{(k+1)N}\cap\widetilde{A}_{(k+2)N}&=\left(\widetilde{A}_{kN}\cap\widetilde{A}_{(k+1)N}\right)\cap\left(\widetilde{A}_{(k+1)N}\cap\widetilde{A}_{(k+2)N}\right)\\\
&=\left((\bm{w},\eta)+\widetilde{A}_{kN}\right)\cap\left((\bm{w},\eta)+\widetilde{A}_{(k+1)N}\right)\\\
&=2(\bm{w},\eta)+\widetilde{A}_{kN}.\end{split}$

Proceeding by induction (and using Lemma 6.1) we conclude

$\widetilde{A}_{0}\cap\widetilde{A}_{aN}=\bigcap_{k=0}^{a}\widetilde{A}_{kN}=a(\bm{w},\eta)+\widetilde{\Gamma}.$

Intersecting the left and right hand sides with $\mathcal{H}_{h}$ yields

$A_{0,h}\cap A_{aN,h}=a\bm{w}+C_{h-a\eta},$

whence

$A_{j,h}\cap A_{j+aN,h}=j\bm{v}_{0}+a\bm{w}+C_{h-j-a\eta}.$ (27)

To finish the proof, all that remains is to show that $\eta=H$.

First, observe that (27) yields $A_{0,\eta}\cap A_{N,\eta}=\\{\bm{w}\\}$, so
$\eta\geq H$. On the other hand, by definition of $H$ there exist $a\geq 1$
and $j\geq 0$ such that $A_{j,H}\cap A_{j+aN,H}\neq\varnothing.$ Our identity
(27) then implies that $H-j-a\eta\geq 0$, whence $\eta\leq H$. ∎

##  7 Conclusions: recap, conjectures, and observations

Recall that Khovanskii’s theorem asserts that for any $A\subset\mathbb{Z}^{d}$
there exists some integer $H$ (which we called the _phase transition_) such
that the cardinality of $hA$ is given by some polynomial in $h$ for all $h\geq
H$. Our work improved on this in several ways:

  * •

in Theorem 1.4 we gave an explicit upper bound on the phase transition when
$\Delta_{A}$ is a simplex,

  * •

in Theorem 1.3 we obtained an analogous result on the structure of $hA$, again
with an explicit upper bound on the phase transition when $\Delta_{A}$ is a
simplex,

  * •

in Theorem 5.1 we demonstrated that for any $A\subset\mathbb{Z}$ one can give
a compact expression capturing the structure of $hA$ for all sufficiently
large $h$, and gave an explicit upper bound on the phase transition, and

  * •

in Theorem 1.2 we gave a complete description of $hA$ for all $h$ in the case
that $A$ is small.

All but the last of these offer room for improvement. The goal of this section
is to make some conjectures and share some curious empirical observations.

In section 5, we proved Theorem 5.1, a Brion-type formula in dimension 1. We
expect that one can generalize this theorem to higher dimensions by
associating to the point $\bm{a}=(a_{1},\ldots,a_{d})\in\mathbb{Z}^{d}$ the
monomial weight

$\bm{x}^{\bm{a}}:=x_{1}^{a_{1}}\cdots x_{d}^{a_{d}}.$

Defining the generating functions (13) and (14) with $\bm{x}^{\bm{a}}$ in
place of $x^{a}$, we expect the following analogue of (15) to hold for all
sufficiently large $h$:

$\sigma_{hA}(\bm{x})=\sum_{i=1}^{d+1}\bm{x}^{\bm{h\bm{v}_{i}}}\sigma_{\bm{v}_{i}}(\bm{x}).$

(This can also be thought of as a generating function analogue of Theorem
1.3.) We conjecture that this formula is valid whenever

$h\geq\text{vol}(\Delta_{A})\cdot d!-|A|+2.$ (28)

One reason we did not pursue this theorem in the general case is an additional
technical difficulty: in dimension 1 the extraneous sets are finite
collections of points, but in higher dimensions they are instead finite unions
of hypersurfaces. We invite the motivated reader to carry out this strategy
and obtain a general version of Theorem 5.1.

Our bound on the phase transition in Khovanskii’s Theorem is likely not
optimal. Over $\mathbb{Z}$ it is known that Theorem 1.3 holds for $h\geq
b-|A|+2$, thanks to work of Granville and Walker [6]. For higher dimensions,
we conjecture that Theorem 1.4 holds under the assumption (28) and that
Theorem 1.3 holds under the assumption that

$h\geq\text{vol}(\Delta_{A})\cdot d!-|A|+d+1$

without any assumption on the convex hull of $A$; note that this specializes
to Granville and Walker’s bound in the case $d=1$. The reasoning behind our
conjecture is that our proof shows that the phase transition measures how long
it takes lifts of elements of $A$ to fill in all of the residue classes of
$\mathcal{C}_{A}$. Thus the case of $A$ containing $d+2$ elements should take
the longest time to fill in all residue classes, so we expect this to be the
worst case scenario. Furthermore, the more elements $A$ contains, the faster
it should fill up all of the residue classes, so the phase transition should
occur earlier the larger $|A|$ is. The linear decrease with respect to $|A|$
is motivated by Granville and Walker’s result [6] over $\mathbb{Z}$.

Our conjecture on the phase transition is borne out by computations, but in
sometimes unexpected ways. For example, for the set
$A=\\{(0,0),(-1,1),(1,2),(4,0)\\}$ one can show that

$\mathcal{C}_{A}(t)=\frac{1-t^{11}}{(1-t)^{4}},$

despite the presence of minimal elements of $\mathcal{C}_{A}$ with heights as
large as 14. The fact that the degree of $\mathcal{C}_{A}(t)$ is smaller than
14 comes from a seemingly miraculous cancellation that occurs when adding
together the generating series of the sets $\mathcal{S}_{\bm{\pi}}$. Perhaps
even more surprising is that this miraculous cancellation persists even when
computing the structural generating functions as in Theorem 5.1. For example,
using the same set $A$ as above but keeping track of the positions in
$\mathcal{C}_{A}$ with weights $x$ and $y$, one finds that

$\mathcal{C}_{A}(x,y,t)=\frac{1-x^{4}y^{8}t^{11}}{(1-t)(1-x^{4}t)(1-x^{-1}yt)(1-xy^{2}t)}.$
(29)

We conclude our discussion with some tantalizing numerology. Consider the set

$B=\\{(0,0),(1,2),(2,1),(3,1)\\},$

whose convex hull is a simplex. The method from section 2 produces

$\mathcal{C}_{B}(x,y,t)=\frac{1-x^{10}y^{5}t^{5}}{(1-t)(1-xy^{2}t)(1-x^{3}yt)(1-x^{2}yt)}.$
(30)

The remarkably similar form of (29) and (30) suggests that there may be a
unified approach to proving Theorem 1.2 without treating the simplicial and
non-simplicial cases separately. The $x^{10}y^{5}t^{5}$ term of the numerator
of (30) admits a nice interpretation: it is the weight assigned to the lift of
the interior point $(2,1)$ of $B$ raised to the power 5, the volume of the
fundamental domain of $\mathcal{C}_{B}$. Unfortunately, the corresponding term
$x^{4}y^{8}t^{11}$ in (29) does not seem to have such a nice interpretation.
The volume of the fundamental domain of $\mathcal{C}_{A}$ is 11, so
$x^{4}y^{8}t^{11}$ would correspond to the weight of the lift of the point
$(4/11,8/11)$, which does not lie in $A$, and moreover isn’t even a lattice
point! A proper interpretation of the term $x^{4}y^{8}t^{11}$ appearing in
(29) may well be the key to extending our results to arbitrary
$A\subset\mathbb{Z}^{d}$.

## Acknowledgments

We’re grateful to Andrew Granville and Aled Walker for sharing their work with
us, as well as for pointing out a subtle difficulty in our initial approach.
We’d also like to thank Ben Logsdon and Ralph Morrison for providing helpful
feedback on early versions of this paper, Ilija Vrećica [16] for discovering
an error in our original proof of Theorem 1.2, and the anonymous referees for
their meticulous work—their comments improved the clarity of the manuscript.

## References

  * [1] A. Barvinok, K. Woods, Short rational generating functions for lattice point problems, J. Amer. Math. Soc. 16 (2003), no. 4, pp. 957–979.
  * [2] M. Brion, Points entiers dans les polyèdres convexes, Ann. Sci. École Norm. Sup. (4) 21 (1988), no. 4, pp. 653–663.
  * [3] M. Beck, S. Robins, Computing the continuous discretely: integer point enumeration in polyhedra, 2nd ed., Undergraduate Texts in Mathematics, Springer, New York, 2015.
  * [4] E. Ehrhart, Sur les polyèdres rationnels homothétiques à $n$ dimensions, C. R. Acad. Sci. Paris 254 (1962), pp. 616–618
  * [5] A. Granville, G. Shakan, The Frobenius postage stamp problem, and beyond, Acta Math. Hungar. 161 (2020), no. 2, pp. 700–718
  * [6] A. Granville, A. Walker, A tight structure theorem for sumsets, arXiv preprint (uploaded June, 2020), https://arxiv.org/abs/2006.01041
  * [7] S. Han, The boundary structure of the sumset in $\mathbb{Z}^{2}$, Number Theory (New York, 2003), pp. 201–218, Springer, 2004.
  * [8] V. Jelínek, M. Klazar, _Generalizations of Khovanskii’s theorems on the growth of sumsets in abelian semigroups_ , Adv. in Appl. Math. 41 (2008), no. 1, pp. 115–132.
  * [9] A. Khovanskii, The Newton polytope, the Hilbert polynomial and sums of finite sets, Funktsional. Anal. i Prilozhen. 26 (1992), no. 4, pp. 57–63, 96.
  * [10] J. Lee, _Algebraic proof for the geometric structure of sumsets_ , Integers 11 (2011), no. 4, pp. 477–486.
  * [11] M. B. Nathanson, Additive number theory: Inverse problems and the geometry of sumsets, Graduate Texts in Mathematics, 165, Springer-Verlag, New York (1996).
  * [12] M. B. Nathanson, Sums of finite sets of integers, Amer. Math. Monthly 79 (1972), pp. 1010–1012.
  * [13] M. B. Nathanson, I. Z. Ruzsa, _Polynomial growth of sumsets in abelian semigroups_ , J. Théor. Nombres Bordeaux 14 (2002), no. 2, pp. 553–560.
  * [14] I. Z. Ruzsa, Sumsets and structure, Combinatorial number theory and additive group theory, pp. 87–210, Adv. Courses Math. CRM Barcelona, Birkhäuser Verlag, Basel, 2009.
  * [15] J. J. Sylvester, Mathematical questions, with their linear solutions, Educational times, 41 (1884), 21.
  * [16] I. Vrećica, A result on the size of iterated sumsets in $\mathbb{Z}^{d}$, preprint available at arxiv.org/abs/2109.04377
  * [17] J. D. Wu, F. J. Chen and Y. G. Chen, On the structure of the sumsets, Discrete Math. 311 (2011), no. 6, pp. 408–412.

[mjc] Michael J. Curran
University of Oxford
Oxford, United Kingdom
MichaelCurranmathsoxacuk
[lg5] Leo Goldmakher
Williams College
Williamstown, MA, USA.
LeoGoldmakherwilliamsedu