The inverse of an automorphism in polynomial time (Q1190750)

A \(K\)-endomorphism of a polynomial ring \(K[\vec x]\) is a mapping of the polynomial ring to itself which preserves addition and multiplication and which fixes every element \(k\) of \(K\). Problem 1 (Endomorphism invertibility) Let \(\sigma : x_ i \mapsto h_ i (\vec x)\) for \(1 \leq i \leq d\) be an endomorphism over a polynomial ring \(K [\vec x]\) given by the coefficients of the polynomials \(h_ i \in K [\vec x]\). Determine if \(\sigma\) is invertible, and if it is compute its inverse. A subproblem of problem 1 is the following: Problem 2 (Inverse of an automorphism) Let \(\sigma : x_ i \mapsto h_ i (\vec x)\) for \(1 \leq i \leq d\) be an automorphism over a polynomial ring \(K[\vec x]\) given by the coefficients of the polynomials \(h_ i \in K [\vec x]\). Compute the inverse of \(\sigma\). In this paper we give a new solution to problem 2 which works over any commutative ring \(K\) and requires a number of arithmetic operations which is polynomial in the dense representation of the input and output polynomials. Our algorithm for problem 2 also leads to a new, exponential time solution to problem 1 in the case where \(K\) is a field.