MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.)

share|cite|improve this question
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
up vote 11 down vote accepted

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.

share|cite|improve this answer
Re: the last question, have you asked Stanley? – Qiaochu Yuan May 18 '11 at 7:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.