# Rational Function Reconstruction

## Rational Function Reconstruction

Keywords: computer algebra, polynomial approximation, algorithm

Prerequisites: None

Imagine that I give you any decimal number, say 2.3834296, and I ask you to find me a fraction $$\frac a b$$, where both $$a$$ and $$b$$ are small integers, and such that $$\frac a b \approx 2.3834296$$. This problem might at first seem contrived, but it has many applications in a broad range of practical and theoretical problems. It can, surprisingly, be solved extremely efficiently using the Euclidean algorithm for computing the greatest common divisor.

There is a completely analogous problem over polynomial rings. Here I give you a power series (infinite degree polynomial) $$S(x) = 2 + 3x + 8x^2 + \ldots$$, and I ask you to give me a polynomial fraction $$\frac {a(x)}{b(x)}$$ such that
$$\frac {a(x)}{b(x)} \equiv S(x) \mod x^{8} \ ,$$ or, put another way, that $$a(x)$$ and $$b(x)S(x)$$ agree all the way up to $$x^8$$. The coefficients of $$a, b$$ might be over $$\mathbb{Q}$$ or over e.g.~a finite field $$\mathbb{F}_q$$. The Euclidean algorithm works for polynomials as well and solves the problem very well.

The problem has a natural vectorial generalisation: I give you $$\ell$$ power series at the same time $$S_1(x), \ldots, S_\ell(x)$$, and I ask for $$\ell$$ simultaneous approximations which share the same denominator, i.e. $$\frac {a_1(x)}{b(x)}, \ldots, \frac {a_\ell(x)}{b(x)}$$.