Generalizations of Khovanskii's theorems on growth of sumsets in abelian semigroups
| dc.creator | Jelinek, Vit | |
| dc.creator | Klazar, Martin | |
| dc.date | 2007-06-07 | |
| dc.date.accessioned | 2026-07-07T08:04:35Z | |
| dc.date.available | 2026-07-07T08:04:35Z | |
| dc.description | We show that if $P$ is a lattice polytope in the nonnegative orthant of $\R^k$ and $χ$ is a coloring of the lattice points in the orthant such that the color $χ(a+b)$ depends only on the colors $χ(a)$ and $χ(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\uı on sumsets in semigroups. We also prove a strengthening of multivariate generalizations of Khovanski\uı's theorem. Another result of Khovanski\uı 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. | |
| dc.description | 21 pages | |
| dc.identifier | https://arxiv.org/abs/0706.1092 | |
| dc.identifier | http://arxiv.org/abs/0706.1092 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/130020 | |
| dc.subject | Combinatorics | |
| dc.subject | Number Theory | |
| dc.subject | 05A15; 11P99 | |
| dc.title | Generalizations of Khovanskii's theorems on growth of sumsets in abelian semigroups | |
| dc.type | text |