14
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ May 15, 2011 at 5:12
  • $\begingroup$ The affine semigroup could consist of $0$ only which allows for $P$ to be finite. $\endgroup$ May 15, 2011 at 5:36
  • $\begingroup$ 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. $\endgroup$ May 15, 2011 at 11:18
  • $\begingroup$ 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. $\endgroup$
    – Alex Fink
    May 16, 2011 at 16:05
  • $\begingroup$ 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$... $\endgroup$
    – Alex Fink
    May 16, 2011 at 16:21

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Re: the last question, have you asked Stanley? $\endgroup$ May 18, 2011 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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