Which sets of lattice points have rational generating functions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T11:22:55Z http://mathoverflow.net/feeds/question/65023 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/65023/which-sets-of-lattice-points-have-rational-generating-functions Which sets of lattice points have rational generating functions? Alex Fink 2011-05-15T04:22:13Z 2011-05-17T20:43:11Z <p>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?<br> 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$?</p> <p>(My proximal motivation for asking is the appearance of both conditions in <a href="http://www.math.duke.edu/~ezra/Games/cgt.pdf" rel="nofollow">Guo &amp; Miller, <em>Lattice point methods for combinatorial games</em></a>. 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.)</p> http://mathoverflow.net/questions/65023/which-sets-of-lattice-points-have-rational-generating-functions/65252#65252 Answer by David Speyer for Which sets of lattice points have rational generating functions? David Speyer 2011-05-17T15:54:59Z 2011-05-17T20:43:11Z <p>I feel like there has to be an easier proof of this, but I just posted <a href="http://www.math.lsa.umich.edu/~speyer/PowSerNote.pdf" rel="nofollow">a note</a> on my webpage proving the following Theorem. The key is a <a href="http://arxiv.org/abs/0706.2438" rel="nofollow">paper of Sam Payne's</a>.</p> <p>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 <code>$\mathbb{C}_p$</code> be the completion of the algebraic closure of <code>$\mathbb{Q}_p$</code>, so <code>$\mathbb{C}_{\infty}$</code> means the standard complex numbers. We define a function <code>$\phi: \mathbb{Z}_{\geq 0}^n \to \mathbb{Q}$</code> to be a quasi-polynomial if <code>$\mathbb{Z}_{\geq 0}^n$</code> 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.</p> <p><strong>Theorem:</strong> The following are equivalent:</p> <p>(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$.</p> <p>(2) The function $(d_1, \ldots, d_n) \mapsto a(d_1, \ldots, d_n)$ is a quasi-polynomial.</p> <p>(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.$$</p> <p>(4) For every absolute value <code>$| \ |_p$</code> on $\mathbb{Q}$ (including the archimedean norm), there are no zeroes of $g(t_1, \ldots, t_n)$ in the open polydisc <code>$\{ (u_1, \ldots, u_n) \in \mathbb{C}_p : |u_1|, |u_2|, \ldots, |u_n| &lt; 1 \}$</code>.</p> <p>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.</p> <p>Can someone tell me whether this is new? I think it might be worth publishing, if so.</p>