When a formal power series is a rational function in disguise

Given a formal power series $f \in k[[X]]$, where $k$ is a commutative field, is there any good way to tell whether or not $f\in k(X)$?

Edit: To clarify, "good way to tell" means "computable algorithm to tell".

Edit 2: I really screwed up this question, so I am recusing myself from accepting an answer. I will accept an answer after a sufficient number of votes have been cast for the best answer.

-
… where k is a what or commutative field? –  Harald Hanche-Olsen Feb 10 '10 at 2:21
Isn't it "when the coefficients satisfy a linear recursion of finite length"? –  Alon Amit Feb 10 '10 at 2:22
The series is a rational function iff they satisfy a linear recurrence with constant coefficients. –  Mariano Suárez-Alvarez Feb 10 '10 at 2:23
You still haven't specified how f is given. I'm guessing there is a Turing machine outputting its coefficients? –  Qiaochu Yuan Feb 10 '10 at 2:27
I have no idea. You tell me in an answer, and I'll accept that answer. –  Harry Gindi Feb 10 '10 at 2:33

Continued fractions!

To motivate this answer, first recall the continued fraction algorithm for testing whether a real number is rational. Namely, given a real number $r$, subtract its floor $\lfloor r \rfloor$, take the reciprocal, and repeat. The number $r$ is rational if and only if at some point subtracting the floor gives $0$.

Of course, an infinite precision real number is not something that a Turing machine can examine fully in finite time. In practice, the input would be only an approximation to a real number, say specified by giving the first 100 digits after the decimal point. There is no longer enough information given to determine whether the number is rational, but it still makes sense to ask whether up to the given precision it is a rational number of small height, i.e., with numerator and denominator small relative to the amount of precision given. If the number is rational of small height, one will notice this when computing its continued fraction numerically, because subtracting the floor during one of the first few steps (before errors compound to the point that they dominate the results) will give a number that is extremely small relative to the precision; replacing this remainder by $0$ in the continued fraction built up so far gives the small height rational number.

What is the power series analogue? Instead of the field of real numbers, work with the field of formal Laurent series $k((x))$, whose elements are series with at most finitely many terms with negative powers of $x$: think of $x$ as being small. For $f = \sum a_n x^n \in k((x))$, define $\lfloor f \rfloor = \sum_{n \le 0} a_n x^n$; this is a sum with only finitely many nonzero terms. Starting with $f$, compute $f - \lfloor f \rfloor$, take the reciprocal, and repeat. The series $f$ is a rational function (in $k(x)$) if and only if at some point subtracting the floor gives $0$.

The same caveats as before apply. In practice, the model is that one has exact arithmetic for elements of $k$ (the coefficients), but a series will be specified only partially: maybe one is given only the first 100 terms of $f$, say. The only question you can hope to answer is whether $f$ is, up to the given precision, equal to a rational function of low height (i.e., with numerator and denominator of low degree). The answer will become apparent when the continued fraction algorithm is applied: check whether subtracting the floor during one of the first few steps gives a series that starts with a high positive power of $x$.

Bonus: Just as periodic continued fractions in the classical case correspond to quadratic irrational real numbers, periodic continued fractions in the Laurent series case correspond to series belonging to a quadratic extension of $k(x)$, i.e., to the function field of a hyperelliptic curve over $k$. Abel in 1826 exploited this idea as an ingredient in a method for determining which hyperelliptic integrals could be computed in elementary terms!

-
I'm sorry that your answer was forced into community wiki status. –  Harry Gindi Feb 10 '10 at 8:44
This is the pade tables of pade approximants, right? One of the papers I linked to in my answer was precisely about the fact that if the function is not rational than for some neighborhood of zero the origin shifted determinants characterizing the approximants are all non zero (you get a normal table). I guess this is a good indicator of whether the function is equal, up to precision, to a rational function of low weight. –  Gjergji Zaimi Feb 10 '10 at 9:36
Also, +1 for the nice explanation (and the Bonus connection). –  Gjergji Zaimi Feb 10 '10 at 9:38
@Gjergji: I think you are right that the Padé table of approximants is closely related to continued fractions, though I am not clear on whether it is exactly the same kind of continued fraction as I was discussing. For instance, the article jstor.org/stable/1969008 (Annals of Math. 41, no. 2, 328-349) discusses some other variants of continued fractions for power series. –  Bjorn Poonen Feb 11 '10 at 3:12

Whether a power series corresponds to a rational function or not is independent of any finite initial segment of its coefficients; accordingly, (as some power series are and others are not given by rational functions), one has to know infinitely many coefficients of the power series in order to tell whether it is given by a rational function or not. On most natural accounts of what it means to present such a series (e.g., as a black box which one can query for the coefficient at a particular index, or even as the code for a Turing machine/program in a standard language which produces the sequence of coefficients), it will follow that it is impossible to compute the answer (a computation taking only finitely many steps).

Edit: "a computation taking only finitely many steps" is enough to show the impossibility in the black box case (it would take infinitely many queries to establish the values of infinitely many coefficients). I forgot to add the reasoning that covers the Turing machine code case: if one did have such an algorithm, then one could use it to solve the Halting Problem, like so: let $I_i$ be a computable stream of coefficients defining a non-rational series, and let $Q(p)_i$ be 0 if p does halt within i steps, and $I_i$ otherwise. The code for a Turing machine computing $Q(p)$ can be easily (computably) constructed from p itself, and this machine is guaranteed to output a stream of infinitely many coefficients, the result defining a rational series if and only if p eventually halts. Accordingly, the undecidability of the halting problem gives the desired impossibility result.

-

Given a function $f(z)= \sum _{k=1}^{\infty} a _kz^{-k}$, it is the symbol of the Hankel operator $$H=\left(a _{i+j-1}\right) _{i,j}$$ Kronecker's theorem tells you that $f$ is rational iff $H$ is of finite rank $n$.

From a system-theoretic point of view, the possibility of recovering a rational function $P(z)/Q(z)$ , where is $Q(z)$ monic, by its MacLaurin expansion at infinity has been extensively studied as the partial realization problem of system theory. It is intimately connected to such topics as the Berlekamp–Massey algorithm in the context of coding theory and Kalman filtering.

In approximation theory Pade approximation deals with approximation to a rational function but as an algorithm it is pretty inconvenient.

On the other hand an approach like the one taken here seems more efficient. You only have to check the vanishing of the Toeplitz determinants $D(m,n;u)$ at only one coordinate $(m,n)$, eventhough this must be done for all $u$ in a neighborhood of the origin.

I also wanted to mention that investigating rational functions is not limited to analytic properties, they are closed under $+$ and $\otimes$ (Hadamard product) but not under arbitrary Hadamard quotients.The following has been proved by van der Poorten. Reference

("Pisot’s Conjecture") Let $\sum s _n z^n$ and $\sum t _n z^n$ be two rational power series with coeﬃcients in a 0-characteristic ﬁeld $K$. If every $t_n$ is diﬀerent from 0 and there exists a finitely generated ring over $\mathbb{Z}$, $A$ such that $s _n /t _n \in A$ for all $n$, then the power series $\sum (s _n /t _n) z^n$ is rational.

And it seems like there is more arithmetic/algebraic structure, if familiar with classical results on Hopf algebra structures you might be interested in this paper: "The algebraic structure of linearly recursive sequences under Hadamard product" R.G. Larson, E.J. Taft.

-
Eh, are you sure about your formulation of Pisot's conjecture? What exactly stops me from taking $A=K$ ? –  darij grinberg Feb 10 '10 at 18:43
Fixed. I added a reference too. –  Gjergji Zaimi Feb 10 '10 at 21:54
Thanks, this makes much more sense now. –  darij grinberg Feb 10 '10 at 23:00

As noted the question is whether the coefficients satisfy a linear recursion. But how do you tell that? There is a theorem of Kronecker (it's Lemma III on page 5 of Chapter 1 of Raphael Salem, Algebraic Numbers and Fourier Analysis, published by Wadsworth in 1983, originally published by D C Heath, 1963) that says sum to infinity of c_n z^n is a rational function if and only if the determinant of Delta_m is zero for all m sufficiently large, where Delta_m is an m + 1 by m + 1 matrix in which the j-th row is c_{j-1}, c_j, ..., c_{m+j-1} for j = 1, ..., m + 1. So you can calculate the determinants for various m and if you start getting zeros you can figure it's time to start looking for that linear recurrence.

-
Sure, but this algorithm doesn't terminate. –  Qiaochu Yuan Feb 10 '10 at 2:47
Another way is to compute the Pade approximants (Wikipedia mentions the algorithm for this obliquely). If the approximants stabilize then success. –  Steve Huntsman Feb 10 '10 at 2:55
"Sure, but this algorithm doesn't terminate." I'm not sure this comment makes any sense! If you have a formula for c_n, then you have a formula for all the Delta_m's, and you can try and prove a theorem that says that the det is zero for m suff large. On the other hand if you just have a black box where you can put in n and it spits out c_n, then there is visibly no algorithm at all that will terminate in finite time, because in finite time you can only analyse finitely many of the c_n so don't have enough information to answer the question. –  Kevin Buzzard Feb 10 '10 at 13:49

More or less by definition this is the case precisely when the coefficients of $f$ satisfies a homogeneous linear recurrence with coefficients in $k$. Equivalently, the coefficients of $f$ are a linear combination of terms of the form $n^r \lambda^n, \lambda \in \bar{k}, r \in \mathbb{Z}_{\ge 0}$. But it's not clear to me what you do and don't know about this problem and how $f$ is given.

Edit: This seems to me to be impossible by Rice's theorem. I'll quote from the Wikipedia article:

Suppose we have a set of languages S. Then the problem of deciding whether the language of a given Turing machine is in S is undecidable, provided that there exists a Turing machine that recognizes a language in S and a Turing machine that recognizes a language not in S. Effectively this means that there is no machine that can always correctly decide whether the language of a given Turing machine has a particular nontrivial property. Special cases include the undecidability of whether a Turing machine accepts a particular string, whether a Turing machine recognizes a particular recognizable language, and whether the language recognized by a Turing machine could be recognized by a nontrivial simpler machine, such as a finite automaton.

This particular problem is actually very close to determining whether a Turing machine recognizes a regular language.

-
Sorry for unaccepting your answer, but Gerry's answer was the answer I was looking for. –  Harry Gindi Feb 10 '10 at 2:47
Rice's theorem immediately tells us we cannot solve the problem "Design an algorithm which, given an input, determines whether this is the code for a Turing machine which outputs an infinite stream of coefficients which corresponds to a rational function". However, it does not immediately tell us that we cannot solve the problem "Design an algorithm which, given an input which is the code for a Turing machine which outputs an infinite stream of coefficients, will determine whether that stream corresponds to a rational function", this presumably being closer in spirit to the question. –  Sridhar Ramesh Feb 10 '10 at 2:48
(That having been said, this latter problem, despite being a priori easier, is also unsolvable, for the reasons I outline in my answer, which, although they don't invoke Rice's theorem, are similarly general and require little knowledge of the properties of rational power series specifically [they amount to a simple variant of the more powerful Rice-Shapiro theorem]) –  Sridhar Ramesh Feb 10 '10 at 3:19