When a formal power series is a rational function in disguise

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!

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 coefficients in a 0-characteristic field $K$. If every $t_n$ is different 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.