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

We investigate the representations of a rational function R∈k(x) where k is a field of characteristic zero, in the form R=K⋅σS/S. Here K,S∈k(x), and σ is an automorphism of k(x) which maps k[x] onto k[x]. We show that the degrees of the numerator and denominator of K are simultaneously minimized iff K=r/s where r,s∈k[x] and r is coprime with σns for all n∈Z. Assuming existence of algorithms for computing orbital decompositions of R∈k(x) and semi-periods of irreducible p∈k[x]∖k, we present an algorithm for minimizing among representations with minimal K, where w is any appropriate weight function. This algorithm is based on a reduction to the well-known assignment problem of combinatorial optimization. We show how to use these representations of rational functions to obtain succinct representations of σ-hypergeometric terms.