ac.commutative algebra - 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!