# Which sets of lattice points have rational generating functions?

Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said about the structure of $P$? In particular, must $P$ be a finite (disjoint) union of finitely generated modules over affine sub-semigroups?
Equivalently, must $P$ be a finite (disjoint) union of intersections of a rational polyhedron in $\mathbb N^d$ with a sublattice of $\mathbb Z^d$?

(My proximal motivation for asking is the appearance of both conditions in Guo & Miller, Lattice point methods for combinatorial games. One would like to speak on the level of rational generating functions, but the tools they develop only let them get at sets with a given decomposition into modules for sub-semigroups.)

-
Can you clarify what a finitely-generated module over an affine sub-semigroup is? Any definition of this I can think of would require that $P$ be infinite. –  Qiaochu Yuan May 15 '11 at 5:12
The affine semigroup could consist of $0$ only which allows for $P$ to be finite. –  Torsten Ekedahl May 15 '11 at 5:36
I wonder if this works. Multiply through by the denominator of the rational function; the vanishing of most of the terms in the product gives you a recurrence relation, in many variables, satisfied by the coefficients. Then maybe it's possible to eliminate all but one variable, and apply the well-known theory of one-variable recurrences. –  Gerry Myerson May 15 '11 at 11:18
Qiaochu: yes, I meant to allow for the affine subsemigroup to be 0, or in general to be generated by any finite subset of $\mathbb N^d$. I've edited the question to say the same thing more polyhedrally. –  Alex Fink May 16 '11 at 16:05
Here's an approach similar to Gerry's I'd been trying. Take a linear map $\mathbb N^d\to\mathbb N$ with finite fibers, so that the gf for the size of the fibers is the image of $f$ under $t_i\mapsto t^{a_i}$, with all $a_i>0$. The size of the fibers is integral and bounded by a polynomial, so by the one-variable theory it has to be a quasi-polynomial. It seems like that should impose useful conditions on $f$... –  Alex Fink May 16 '11 at 16:21

I feel like there has to be an easier proof of this, but I just posted a note on my webpage proving the following Theorem. The key is a paper of Sam Payne's.

Let $f(t_1, \ldots, t_n)/g(t_1, \ldots, t_n) = \sum a(d_1, \ldots, d_n) t_1^{d_1} \cdots t_n^{d_n}$ be a rational function with coefficients in $\mathbb{Q}$. Let $\mathbb{C}_p$ be the completion of the algebraic closure of $\mathbb{Q}_p$, so $\mathbb{C}_{\infty}$ means the standard complex numbers. We define a function $\phi: \mathbb{Z}_{\geq 0}^n \to \mathbb{Q}$ to be a quasi-polynomial if $\mathbb{Z}_{\geq 0}^n$ can be partitioned into finitely many sets $S_k$, each one the translate of a finitely generated semi-group, such that the restriction of $\phi$ to each $S_k$ is a polynomial.

Theorem: The following are equivalent:

(1) The polynomial $g$ factors as $\prod_i \Phi_{d_i}\left( t_1^{e^i_1} \cdots t_n^{e^i_n} \right)$ where $\Phi_d$ is the $d$-th cylotomic polynomial and $(e^i_1, e^i_2, \ldots, e^i_n) \in \mathbb{Z}_{\geq 0}^n$, with at least one component of $e^i$ nonzero for each $i$.

(2) The function $(d_1, \ldots, d_n) \mapsto a(d_1, \ldots, d_n)$ is a quasi-polynomial.

(3) There are constants $C$ and $D$ such that $$|a(d_1, \ldots, d_n)|_{\infty} \leq C \left( \sum d_i \right)^D$$ and, for every finite prime $p$, there is a constant $C_p$ such that $$|a(d_1, \ldots, d_n)|_{p} \leq C_p.$$

(4) For every absolute value $| \ |_p$ on $\mathbb{Q}$ (including the archimedean norm), there are no zeroes of $g(t_1, \ldots, t_n)$ in the open polydisc $\{ (u_1, \ldots, u_n) \in \mathbb{C}_p : |u_1|, |u_2|, \ldots, |u_n| < 1 \}$.

In your setting, suppose that $\sum_{d \in P} t_1^{d_1} \cdots t_n^{d_n}$ is rational. Let $\chi_P$ be the characteristic function of $P$. It clearly obeys condition (3). So the theorem states that $\chi_P$ is a quasi-polynomial. Each of the polynomials making it up must have degree $0$, as it only assumes two values. So the support of $\chi_P$ (that is to say, the set $P$) must be a union of translates of finitely generated semi-groups.

Can someone tell me whether this is new? I think it might be worth publishing, if so.

-
For (1), you mean $(e_1,\dots,e_n)$ t depend on $i$, right? –  Gjergji Zaimi May 17 '11 at 20:18
Fixed, thanks for the correction. –  David Speyer May 17 '11 at 20:43
Re: the last question, have you asked Stanley? –  Qiaochu Yuan May 18 '11 at 7:37