Marko Petkovsek, University of Ljubljana

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 in k(x) and sigma is an
automorphism of k(x) such that sigma(k[x]) = k[x]. There are infinitely
many such forms, 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 forms 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 forms to obtain succinct
representations of sigma-hypergeometric terms.

This is joint work with Sergei A. Abramov.