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

Let \(k[x]\) be a univariate polynomial ring over a field of characteristic zero and \(w\) a weight function. Any automorphism \(\sigma \) of \(k[x]\) is uniquely extendable to an automorphism of the rational function field \(k(x)\). The authors investigate representations of rational functions \(R\in k(x)\) of the form \[ R=K\cdot \frac{\sigma S}{S} \tag{\(*\)} \] with \(K, S\in k(x)\). Such an equality is called a rational \(\sigma\)-normal form \((RNF_\sigma)\) of \(R\) if the numerator of \(K\) is coprime to the image of the denominator of \(K\) by all iterates \(\sigma ^n\), \(n \in \mathbb Z\). Related notions of strict \(RNF_\sigma\)'s and rational \((w,\sigma)\)-canonical forms \((RCF_{w,\sigma})\) are introduced. The paper contains a theory and algorithms for computing \(RNF_\sigma\)'s and \(RCF_{w,\sigma}\)'s for any \(R\in k(x)\). A constructive proof of their existence is given before it is shown that the degrees of the numerator and denominator of \(K\) in a representation (\(*\)) can be simultaneously minimized precisely when (\(*\)) is an \(RNF_\sigma\) of \(R\). A core result shows how to reduce computation of \(RCF_{w,\sigma}\)'s to the well-known assignment problem. Moreover, it is proved that \(R\in k(x)\) has unique rational \((w,\sigma)\)-canonical form provided a suitable hypothesis on the irreducible factors of \(R\) is satisfied. The theory developed in this paper has applications to the problem of succinct representation of \(\sigma\)-hypergeometric terms.