Shortest representation of a rational function

39 Views Asked by At

Sometimes a rational function can have multiple representations. As a simple example, we have equality between the following two rational functions, for any $n$

$$ f(x) = \frac{1 - x^n}{1 - x} = 1 + x + x^2 + x^3 + ... + x^{n-1} $$

The right hand side is "reduced" in that it is in lowest terms. This really is an $n-1$'th degree polynomial, and if we do polynomial long division on the left hand side, we get the right hand side. However, the left-hand side version is much shorter and easy for computation.

Is there anything that can be said about finding such "short" representations for rational functions, or developing a "canonical" representation that is typically short?

I'm sure that the general problem of finding the ultimate shortest representation is probably too difficult to solve, but I am wondering if there is something simple that can be done at least to make numeric computation easier, in the particular case of rational functions.