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)}\).