Complexity of the Inversion Algorithm of Polynomial Mappings

Paweł Bogdan

In this paper we will recall the inversion algorithm described in [1].
The algorithm classifies polynomial automorphisms into two sets: Pascal finite
and Pascal infinite. In this article the complexity of the inversion algorithm
will be estimated. To do so, we will present two popular ways how Computer
Algebra Systems (CASes) keep the information about multivariate polynomials.
We will define the complexity as the amount of simple operations performed
by the algorithm as a function of the size of the input. We will define simple
operations of the algorithm. Then we will estimate complexity of checking that
the polynomial map is not a polynomial automorphism. To do so we will use
theorem 3.1 from [1].
Słowa kluczowe: polynomial automorphism, differential Galois theory, computational complexity, computer algebra system

[1] Adamu E., Bogdan P., Crespo T., Hajto Z., An effective study of polynomial
maps. Journal of Algebra and Its Applications, 2017, 16(5).
[2] Campbell L.A., A condition for a polynomial map to be invertible. Mathematische
Annalen, 1973, 205(3), pp. 243–248.
[3] Crespo T., Hajto Z., Picard-vVessiot theory and the Jacobian problem. Israel
Journal of Mathematics, 2012, 186(1), pp. 401–406.
[4] Adamus E., Bogdan P., Hajto Z., An effective approach to Picard-Vessiot theory
and the Jacobian Conjecture, 2015, submitted.
[5] M¨uller N.T., Uniform Computational Complexity of Taylor Series. In: 14th
International Colloquium on Automata, Languages and Programming, London,
UK, UK, Springer-Verlag, 1987, pp. 435–444.
[6] Bardet M., Faug`ere J.C., Salvy B., On the complexity of the F5 Gr´’obner basis
algorithm. Journal of Symbolic Computation, 2014, 70, pp. 1–24.
[7] Faug`ere J.C., Safey El Din M., Spaenlehauer P.J., Gr¨obner Bases of Bihomogeneous
Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity.
Journal of Symbolic Computation, 2011, 46(4), pp. 406–437 Available
online 4 November 2010.
[8] Adamus E., Bogdan P., Crespo T., Hajto Z., An effective study of polynomial
maps, 2016, submitted.
[9] Developers T.S., Sage Mathematics Software (Version 7.1). 2015.
[10] Winkler F., Polynomial Algorithms in Computer Algebra. Texts & Monographs
in Symbolic Computation. Springer Vienna, 1996.
[11] van den Essen A., Polynomial Automorphisms: and the Jacobian Conjecture
(Progress in Mathematics). Birkhuser, 2000.
[12] Yagzhev A.V., Keller’s problem. Siberian Mathematical Journal, 1980, 21(5),
pp. 747–754.
[13] Bass H., Connell E.H., Wright D., The Jacobian conjecture: Reduction of degree
and formal expansion of the inverse. Bulletin of the AMS – American Mathematical
Society (NS), 1982, 7(2), pp. 287–330.
[14] Druzkowski L.M., An Effective Approach to Keller’s Jacobian Conjecture. Mathematische
Annalen, 1983, 264, pp. 303–314.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.

Wersja papierowa czasopisma dostępna na