On Ritt's polynomial decomposition theorems

Abstract

Ritt studied the functional decomposition of a univariate complex polynomial f into prime (indecomposable) polynomials, f = u_1 o u_2 o ... o u_r. His main achievement was a procedure for obtaining any decomposition of f from any other by repeatedly applying certain transformations. However, Ritt's results provide no control on the number of times one must apply the basic transformations, which makes his procedure unsuitable for many theoretical and algorithmic applications. We solve this problem by giving a new description of the collection of all decompositions of a polynomial. Our results have been used by Ghioca, Tucker and Zieve (arXiv:0807.3576) to describe the polynomials f,g having orbits with infinite intersection; they have also been used by Medvedev and Scanlon to describe the affine curves invariant under a coordinatewise polynomial action.

38 pages

References in corpus (3)

• Linear relations between polynomial orbits
• Decompositions of Laurent polynomials
• Prime and composite Laurent polynomials

Cited by in corpus (14)

• Factorization theory: From commutative to noncommutative settings
• Linear relations between polynomial orbits
• Factorizations of Elements in Noncommutative Rings: A Survey
• Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets
• Generalized "second Ritt theorem" and explicit solution of the polynomial moment problem
• Normal form for Ritt's Second Theorem
• Functional composition of polynomials: indecomposability, Diophantine equations and lacunary polynomials
• On factorizations of maps between curves
• On the inhomogeneity of the Mandelbrot set
• Two questions on polynomial decomposition
• Diophantine equations and the monodromy groups
• Diophantine equations in separated variables and lacunary polynomials
• Decomposable polynomials in second order linear recurrence sequences
• A dynamical Mordell Lang property on the disk