When a formal power series is a rational function in disguise - MathOverflow

When a formal power series is a rational function in disguise

2010-02-10T02:12:40Z

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.

Answer by Qiaochu Yuan for When a formal power series is a rational function in disguise

2010-02-10T02:22:05Z

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.

Answer by Sridhar Ramesh for When a formal power series is a rational function in disguise

2010-02-10T02:43:20Z

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.

Answer by Gerry Myerson for When a formal power series is a rational function in disguise

2010-02-10T02:44:18Z

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.

Answer by Gjergji Zaimi for When a formal power series is a rational function in disguise

2010-02-10T03:00:56Z

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.

Answer by Bjorn Poonen for When a formal power series is a rational function in disguise

2010-02-10T08:18:29Z

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!