# What characterizes rational functions with nonnegative integer Taylor coefficients?

I believe that there is a statement along the following lines (I would, of course, love to be corrected): a formal power series is the Taylor expansion of a rational function if and only if the coefficients eventually satisfy a linear relationship.

Let's suppose that I understand what "satisfy a linear relationship" means, because it's not the part I actually want to ask about (although clarifications are very welcome!). What I would like to know is what conditions on a rational function are equivalent to all the Taylor coefficients being nonnegative integers. For example, I happen to know that $1/(1-kx) = \sum (kx)^n$, and so any sum or product of such functions works. In particular, I can try playing around with partial-fraction decompositions to see if I can write a given rational function in this way. But I have no idea if this is all of them.

Put another way, there is a map $\mathbb R(x) \to \mathbb R[x^{-1},x]]$ (rational functions to Laurent series). I would like to understand the inverse image of $\mathbb N[x^{-1},x]]$.

(Oh, also, I have no idea how to tag this, and I think "general mathematics" is probably an inappropriate tag for MO. So please re-tag as you see fit.)

-
I don't know what you mean by "satisfy a linear relationship" either, and I would appreciate clarification. I have done a tiny bit of work on such things, so I know that the Taylor series expansion of a rational function can be at least as complicated as an arbitrary quasi-polynomial -- see Section 3 of cs.uwaterloo.ca/journals/JIS/VOL8/Clark/clark80.pdf Note that this paper is concerned with a family of rational functions whose Taylor series have non-negative coefficients, so this might be of interest to you. – Pete L. Clark Jan 29 '10 at 6:13
You can find some discussion of the linear relationship condition near the end of Koblitz's GTM text on p-adic numbers. It is used in the exposition of Dwork's "unscheduled" proof of the rationality of the zeta function (cf. Weil conjectures). – S. Carnahan Jan 29 '10 at 15:28

This paper (?) of Gessel might help you out, although it is mostly about combinatorics. There are two natural ways to write down rational functions with non-negative integer coefficients in combinatorics, one coming from transfer matrices / finite automata and one coming from regular languages. The two give the same class of rational functions, but there exist rational functions with non-negative integer coefficients which provably don't arise in this way, so the situation seems complicated.

Your question seems to indicate you're not familiar with this class of rational functions, so here are two equivalent definitions: it is, on the one hand, the class of all non-negative linear combinations of entries of matrices of the form $(\mathbf{I} - \mathbf{A})^{-1}$ where $\mathbf{A}$ is a square matrix with entries in $x \mathbb{N}[x]$, and on the other hand the minimal class of rational functions containing $1, x$, and closed under addition, multiplication, and the operation $f \mapsto \frac{1}{1 - xf}$.

Edit: One reason there isn't likely to be a particularly nice classification is that one can start with any rational function with integer coefficients and add a polynomial and a term of the form $\frac{1}{1 - kx}$ for $k$ such that $\frac{1}{k}$ is smaller than the smallest pole.

-
That theorem gives a condition for a function to be $\mathbb N$-rational, but in the same page he notes there are rational functions with nonnegative integer coefficients which are not $\mathbb N$-rational. – Mariano Suárez-Alvarez Jan 29 '10 at 20:04
Whoops. Corrected. – Qiaochu Yuan Jan 29 '10 at 20:12

By linear relationship, you mean a linear recurrence relation. Do it by writing down P(z)/Q(z) = sum(a_n * x^n), multiply by Q(z) on both sides, regroup terms. You'll get something like 0 = sum((c_1 * a_(n+k) + c_2 * a_(n+k-1) + ... + c_k * a_n)*x^n) so the coefficients do indeed satisfy a linear recurrence.

Furthermore, I think that a function, with radius of convergence 1, and positive integer coefficients, has to be either a rational function (in which case the coefficients satisfy a linear recurrence relation) or has natural boundary on the circle |z| = 1 (in which case the function could be taught off as rather complicated).

So in the end, your question is really a question about linear recurrences relations, rather than about rational functions. I think Narkiewicz did some work in the field, but I have no reference on top of my head.

P.S: Sorry for not LaTeX-ing, I am slightly short on time.

-
I just realized that the "linear recurrence part" got already clarified. I taught of deleting my post, but was unable to do so. – maks Jan 29 '10 at 7:14
Oh, don't delete the post, and sorry for being unclear in my question. I mean, I do appreciate the clarification. – Theo Johnson-Freyd Jan 30 '10 at 5:29

It is apparently «unknown whether the problem "$a_n > 0$ for all $n$?" is decidable for linear recurrence sequences», according to these notes by Stefan Gerhold.

-
I take it that satisfying a linear recurrence as in the link is what TJF means by a "linear relationship" among the coefficients? – Pete L. Clark Jan 29 '10 at 6:20
Do you know a published reference for this assertion? – Richard Stanley Jan 30 '10 at 17:44
Terence Tao's post on the Skolem-Mahler-Lech theorem might have a reference: terrytao.wordpress.com/2007/05/25/… – Qiaochu Yuan Jan 30 '10 at 18:00