Khovanskii's theorem and effective results on sumset structure

DOI10.19086/DA.28814MaRDI QIDQ5028491zbMATH OpenOpenAlexFDO

Authors Michael J. Curran, Leo Goldmakher

Publication date 10 February 2022

Published in discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2009.02140

zbMATH Keywords

Ehrhart theoryiterated sumsets

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Lattices and convex bodies (number-theoretic aspects) (11H06) Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40) Toric varieties, Newton polyhedra, Okounkov bodies (14M25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20)

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 $Asubsetmathbb{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 $Asubsetmathbb{Z}^d$ consists of $d+2$ points.

Recommendations

• A New Proof of Khovanskiĭ’s Theorem on the Geometry of Sumsets
• A tight structure theorem for sumsets
• Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups
• On the structure of the sumsets
• Tauberian theorems for sum sets
• scientific article; zbMATH DE number 3323138
• Generalizations of Khovanskiĭ's theorem on growth of sumsets in abelian semigroups
• A Kneser-Type Theorem for Restricted Sumsets
• The structure of higher sumsets
• Sumsets and Veronese varieties

Cites work

• A tight structure theorem for sumsets
• Algebraic Proof for the Geometric Structure of Sumsets
• Computing the Continuous Discretely
• Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups
• scientific article; zbMATH DE number 3163858 (Why is no real title available?)
• scientific article; zbMATH DE number 2066396 (Why is no real title available?)
• scientific article; zbMATH DE number 933467 (Why is no real title available?)
• scientific article; zbMATH DE number 5663738 (Why is no real title available?)
• Newton polyhedron, Hilbert polynomial, and sums of finite sets
• On the structure of the sumsets
• Points entiers dans les polyèdres convexes
• Polynomial growth of sumsets in abelian semigroups
• Short rational generating functions for lattice point problems
• Sums of Finite Sets of Integers
• The Frobenius postage stamp problem, and beyond

Cited in

(9)

• Iterated sumsets and Hilbert functions
• Generalizations of Khovanskiĭ's theorem on growth of sumsets in abelian semigroups
• scientific article; zbMATH DE number 2066396 (Why is no real title available?)
• A New Proof of Khovanskiĭ’s Theorem on the Geometry of Sumsets
• Effective results on the size and structure of sumsets
• Sumsets and Veronese varieties
• On the size and structure of \(t\)-representable sumsets
• On the structure of length sets with maximal elasticity
• Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups

This page was built for publication: Khovanskii's theorem and effective results on sumset structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028491)