Generalizations of Khovanski's theorems on the growth of sumsets in Abelian semigroups

• Published in: Advances in applied mathematics 2008-07, Vol.41 (1), p.115-132
• Main Authors: Jelinek, Vit, Klazar, Martin
• Format: Article
• Language: English
• ISSN: 0196-8858; 1090-2074
• DOI: 10.1016/j.aam.2007.07.003

We show that if P is a lattice polytope in the nonnegative orthant of and chi is a coloring of the lattice points in the orthant such that the color chi(a+b) depends only on the colors chi(a) and chi(b), then the number of colors of the lattice points in the dilation nP of P is for large n given by a polynomial (or, for rational P, by a quasipolynomial). This unifies a classical result of Ehrhart and Macdonald on lattice points in polytopes and a result of Khovanski on sumsets in semigroups. We also prove a strengthening of multivariate generalizations of Khovanski's theorem. Another result of Khovanski states that the size of the image of a finite set after n applications of mappings from a finite family of mutually commuting mappings is for large n a polynomial. We give a combinatorial proof of a multivariate generalization of this theorem.