On some counting problems for semi-linear sets

Abstract

Let $X$ be a subset of ${\mathbb{N}}^t$ or ${\mathbb{Z}}^t$. We can associate with $X$ a function ${\mathcal{G}}_X:{\mathbb{N}}^t⟶\mathbb{N}$ which returns, for every $(n_1,...,n_t)\in {\mathbb{N}}^t$, the number ${\mathcal{G}}_X(n_1,...,n_t)$ of all vectors $x\in X$ such that, for every $i=1,...,t,|x_i|\le n_i$. This function is called the {\em growth function} of $X$. The main result of this paper is that the growth function of a semi-linear set of ${\mathbb{N}}^t$ or ${\mathbb{Z}}^t$ is a box spline. By using this result and some theorems on semi-linear sets, we give a new proof of combinatorial flavour of a well-known theorem by Dahmen and Micchelli on the counting function of a system of Diophantine linear equations.

34 pages

References in corpus (1)

• Vector partition function and generalized Dahmen-Micchelli spaces

Cited by in corpus (1)

• Presburger arithmetic, rational generating functions, and quasi-polynomials