Polynomial ring automorphisms, rational (w,sigma)-canonical forms, and the assignment problem

Polynomial ring automorphisms, rational (w,sigma)-canonical forms, and the assignment problem

We investigate representations of a rational function R in k(x) in the form R = K * sigma S / S where K, S are again in k(x) and sigma is an automorphism of k(x) such that sigma(k[x]) =  k[x] and sigma(k) = k. There are infinitely many such representations, so we begin by showing how to minimize the degrees of the numerator and denominator of K simultaneously. Then we present an algorithm for minimizing w(deg num S,deg den S) among all representations with minimal K, where w is any appropriate weight function. This algorithm is based on reduction to the so-called assignment problem of combinatorial optimization. Finally we show how to use these representations to obtain succinct presentations of sigma-hypergeometric terms.