Khovanskii's theorem and effective results on sumset structure
Discrete analysis (2021)
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.
@article{DAS_2021_a9,
author = {Michael J. Curran and Leo Goldmakher},
title = {Khovanskii's theorem and effective results on sumset structure},
journal = {Discrete analysis},
year = {2021},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DAS_2021_a9/}
}
Michael J. Curran; Leo Goldmakher. Khovanskii's theorem and effective results on sumset structure. Discrete analysis (2021). http://geodesic.mathdoc.fr/item/DAS_2021_a9/