CHARACTERIZATION OF POLYNOMIAL PRIME BIDECOMPOSITIONS A SIMPLIFIED PROOF

FRANZ BINDER

Abstract. Bidecompositions, i.e., solutions to r ∘ p = s ∘ q, play a central rôle in the study of uniqueness properties of complete decompositions with respect to functional composition. In [Rit22] all bidecompositions using polynomials over the complex number field have been characterized. Later the result was generalized to more general fields. All proofs tend to be rather long and involved. The object of this paper is to develop a version that is simpler than the existing ones, while keeping completely elementary, thus making it accessible to a wider community.

1. Bidecompositions

In the whole paper we will deal with polynomials over a field, which is usually denoted by k. The indeterminant, or identity polynomial, will be denoted by x. Thus, whenever we just say polynomial, elements of k[x] are intended, if not specified differently. Their functional composition will be denoted by ∘. Thus for polynomials r and p we use the notations

r ∘ p = r ∘ p(x) = r(p(x)) = r(p)

interchangably. The degree of a polynomial p is denoted by [p]. As usual when dealing with composition, we use the convention [0] = 0. Thus the degree function is a homomorphism of the monoid (k[x], ∘) onto the monoid (N_{0}, ·). The units of (k[x], ∘) are the polynomials of degree 1.

We have to clarify some basic notions.

1.1. Definition.

1. Two polynomials p and q are called associated, in symbols p ∼ q, whenever there exist units a and b such that

p = a ∘ q ∘ b.

2. A polynomial f is said to be decomposable iff it has a decomposition f = r ∘ p into two non-units r and p. Otherwise it is called indecomposable. f = f_{n} ∘ … ∘ f_{1} is called a prime decomposition of f iff all its componets f_{i} are indecomposable.

3. A bidecomposition consists of two decompositions f = r ∘p = s∘q that are not associated. A prime bidecomposition consists of prime decompositions.

4. If r ∘ p = s ∘ q is a bidecomposition and a, b, c, and d are units, then

(a ∘ r ∘ b) ∘ (b^{−1} ∘ p ∘ c) = (a ∘ s ∘ d) ∘ (d^{−1} ∘ q ∘ c)

is a bidecomposition that is associated to the original one.

1.2. Remark. Two polynomials over k that are not associated may be associated when viewed as polynomials over an extension field. So we must be careful with this notion.

Suppose that f has a prime decomposition of the form

f = … ∘ r ∘ p ∘ …,

and that r ∘ p = s ∘ q is a prime bidecomposition. Then we can replace r and p by s and q to get another prime decomposition

f = … ∘ s ∘ q ∘ ….

If two prime decompositions can be joined by a sequence of such replacements, then they are called related. The importance of bidecomposition comes from the following theorem, that goes back essentially to [Ritt 22]. First a definition.

1.3. Definition. A polynomial over k is called tame iff its degree is not a multiple of the characteristic of k.

1.4. Remark. If char k = 0, then tame just means non-constant.

1.5. Theorem (Ritt). All prime decompositions of a tame polynomial f are related. In particular, the number of its indecomposable components and their degrees, but not nescessarily their order, are uniquely determined by f.

Other proofs and generalizations of this theorem as well as related results are e.g. in [Eng41], [LN73], [DW74], [Sch82], and [Bin95].

Some other facts from the above references that usually are proved in this context should be mentioned.

1.6. Corollary. In a tame nontrivial bidecomposition r ∘ p = s ∘ q the outer resp. the inner polynomials have the same degrees, i.e.,

[r] = [q] , [p] = [s] .

Additionally, [p] and [q] are relatively prime.

1.7. Theorem (Lüroth). All intermediate fields of the extension k(x) : k are simple. In particular, if polynomials p and q have no common right component, then there is a rational function f in two variables such that

x = f(p, q).

Decompositions of tame polynomials do not depend on the ground field:

1.8. Proposition. A tame polynomial is indecomposable over k iff it is indecomposable over some extension fields.

This allows us to pass over to the algebraic closure of k without losing indecomposablility. But bidecompositions associated over an extension field need not be associated over k. For these reason we do the proof for arbitrary fields. algebraicall

1.9. Example. An easy example of bidecompositions is given by the powers, because they trivially satisfy

x^{m} ∘ x^{n} = x^{n} ∘ x^{m}.

This can be generalized a bit to

(x^{m} · t(x)^{n}) ∘ x^{n} = x^{n} ∘ (x^{m} · t(x^{n})),  (1)

for an arbitrary polynomial t, as can be verfied immediately. A second important class comes from the Dickson polynomials, as defined in the next section. They satisfy, similarly,

D_{m}(x, a^{n}) ∘ D_{n}(x, a) = D_{n}(x, a^{m}) ∘ D_{m}(x, a).  (2)

1.10. Definition. A bidecomposition associated to (1) is called exponential, one associated to (2) is called trigonometric.

1.11. Definition. A tame polynomial f is called completely tame iff for each multiplicity μ of a zero of f′, m + 1 is not a multiple of char k.

1.12. Remark. Again, in the case of characteristic 0, completely tame just means non-constant. Otherwise a sufficient condition is [f] < char k.

Now we can express the theorem that we want to proof in the next five sections.

1.13. Theorem (Ritt). All prime completely tame bidecompositions over a field not of characterisic 2 are either exponential or trigonometric.

1.14. Corollary.

1. Over a field of characteritic 0 all bidecompositions are either exponential or trigonometric.

2. If char k ≠ 0 then all bidecompositions using polynomials of degrees < char k are either exponential or trigonometric.

This theorem goes back essentially to [Rit22], with generalizations in [Lev42], [LN73], [DW74], [Sch82].

The proof given in this paper is completely elementary, in the sense that the basic facts about field extensions are the most advanced results used. Nevertheless it is not longer, quite on the contrary, some simplifications, just in the most involved passages, were possible. Our schedule will be as follows.

After discussing some not so widely known properties of Dickson (or Chebyshev) polynomials and of the Tschirnhaus transform (similar to the norm of a linear transformation), we will take a closer look at the ramification structure of the components in a bidecomposition. Then, in §5, we can give a condition for a bidecomposition to be exponential. The same is done in §6 for trigonometric solutions. As one of these two conditions must be satisfied the proof is complete then.

2. Dickson Polynomials

As the (prime-degree) Dickson polynomials constitute bidecompositions, a closer look at their properties will be useful.

2.1. Definition. Let a ∈ k. We define the Dickson polynomials D_{n}(x, a) recursively as

D_{n+2}(x, a) = x · D_{n+1}(x, a) − aD_{n}(x, a); D_{0}(x, a) = 2, D_{1}(x, a) = x.

Instead of D_{n}(x, 1) we sometimes simply write D_{n}.

Note. The classical Chebyshev polynomials t_{n}, usually defined by cos nx = t_{n}(cos x), are conjugate to our Dickson polynomials by t_{n}(x) = \frac{1}{2}D_{n}(2x, 1). Using Dickson polynomials instead of Chebyshev ones has the advantage that they are normed, whenever n is odd. And there is an additional parameter.

Almost directly from the definition we get

2.2. Proposition. The Dickson polynomials satisfy 1. D_{n}(λx, λ^{2}) = λ^{n}D_{n}(x, 1).

2. D_{n}(x, a) ∘ (x + ax^{−1}) = (x + a^{n}x^{−1}) ∘ x^{n}.

3. D_{m}(x, a) ∘ D_{n}(x, a) == D_{nm}(x, a) = D_{n}(x, a) ∘ D_{m}(x, a) for arbitrary constants a, λ.

This result among many other ones can be found e.g. in [LMT93].

2.3. Remark. Part 1 of his proposition suggests that the second parameter is superfluous because all Dickson polynomials of degree n are associated to D_{n}. Suppose, however, that λ ∉ k, but a := λ^{2} ∈ k. Then

D_{n}(x, a) = λ^{n}x ∘ D_{n}(x, 1) ∘ \frac{1}{λ}x.

Thus D_{n}(x, a) is associated to D_{n}(x, 1) as polynomial over k(λ), but not necessarily over k. Using this extra parameter we can avoid the usage of extension fields in such cases.

Note. Using proposition 2.2 it is easy to prove the well known differential equation for Dickson polynomials

(D_{n}^{2} − 4) · n^{2} = (x^{2} − 4) · D′_{n}^{2}.

Conversely, the Dickson polynomials D_{n} and their negatives constitute all polynomial solutions to this differential equation. This is proved e.g. in [LN73] or [Sch82]. The essential idea in the later reference is used in the proof of the next lemma, which will be enough for our purposes.

2.4. Lemma. Let K be a field. Suppose that char K ≠ 2; If a polynomial f over K of degree n satisfies

f − 2λ^{n} = (x − 2λ) · g_{−}^{2}
f + 2λ^{n} = (x + 2λ) · g_{+}^{2}

for some polynomials g_{−}, g_{+} and λ ∈ K, then

f = D_{n}(x, λ^{2}).

Proof. Let a = λ^{2}. We substitute x + ax^{−1} and multiply by x^{n}; thus obtain

(f(x + ax^{−1}) − 2λ^{n}) · x^{n} = (x + ax^{−1} − 2λ^{n}) · g_{−}^{2}(x + x^{−1}) · x · x^{n−1}
= (x − λ)^{2} · g_{−}^{2}(x + x^{−1}) · x^{n−1}
= h_{−}^{2}

for some polynomial h_{−}, because [g_{−}] = \frac{n−1}{2}. Similarly

(f(x + ax^{−1}) + 2λ^{n}) · x^{n} = h_{+}^{2}.

Substracting these two equations we get

4λ^{n}x^{n} = h_{+}^{2} − h_{−}^{2} = (h_{+} + h_{−}) · (h_{+} − h_{−})

But both h_{+} and h_{−} have degree n. As char K ≠ 2, we can choose the signs such that [h_{+} + h_{−}] = n. But then [h_{+} − h_{−}] = 0, thus h_{+} − h_{−} = c for some constant c. We substitute λ for x into equation (∗) to obtain

4a^{n} = (2h_{−}(λ) + c) · c.

Using h_{−}(λ) = 0 we see c^{2} = 4a^{n}, thus can assume c = 2λ^{n}. Now equation (∗) turns into

4λ^{n}x^{n} = (2h_{+} − 2λ^{n}) · 2λ^{n},

from which it follows that h_{+} = x^{n}+λ^{n} and consequently h_{−} = x^{n}−λ^{n}. Therefore

f(x + ax^{−1}) + 2λ^{n} = x^{−n} · (x^{n} + λ^{n})^{2}
= x^{n} + 2λ^{n} + a^{n}x^{−n},

thus

f(x + ax^{−1}) = x^{n} + ax^{−n},

which is the characteristic equation for a Dickson polynomial (2).

The assumption in 2.4 was rather special. Using linear transformations we can make it more general.

2.5. Corollary. Let K ≥ k be an extension field of k. If a polynomial f over k satisfies

f − e_{1} = (x − ξ_{1}) · g_{1}^{2}
f − e_{2} = (x − ξ_{2}) · g_{2}^{2},

for some constants ξ_{1}, ξ_{2} ∈ K, polynomials g_{1}, g_{2} over K, and e_{1}, e_{2} ∈ K that are two different solutions of some quadratic equation over k, then f ∼ D(x, a) (as a polynomials over k) for some a ∈ k.

Proof. Being the solution of a quadratic equation, the e_{i} have the form

e_{1,2} = e ± λ

for some e ∈ k and λ ∈ K such that λ^{2} ∈ k.

In particular, f has its coefficients in k[λ], and so has x − ξ_{i}, as this is a factor of the square-free factorization. Thus the ξ_{i} have the form

ξ_{1,2} = ξ ± cλ

for some ξ, c ∈ k. Let n = [f]; it is odd, directly from the assumption. After multipliying with 2λ^{n−1} (∈ k, as n is odd) the equations look like

2λ^{n−1}(f − e) ± 2λ^{n} = (x − ξ + cλ)2λ^{n−1}g_{1,2}^{2}.

Now f̃ = (2λ^{n−1} − e) ∘ f ∘ (\frac{c}{2}x + ξ) ∼ f satisfies

f̃± 2λ^{n} = (x − 2λ) · cλ^{n−1}g_{1,2}^{2},

which is the form required to use the lemma.

3. The Tschirnhaus Transform

3.1. Definition. Let p, q ∈ k[x], q monic with canonical factorization ∏_{i}(x − ξ_{i})^{ν_{i}} over its splitting field. Then the Tschirnhaus transform of q by p, denoted by ^{p}q is defined by

pq := ∏_{i}(x − p(ξ_{i}))^{ν_{i}}.

In other words, we obtain the Tschirnhaus by transforming the zeros of q by p. As it is a symmetric function of the zeros of q, it is clear that its value is always in k. In fact, the Tschirnhaus can easily be expressed without any reference to an extension field as a resultant:

3.2. Proposition. For any polynomials p, q, we have up to the sign

pq(y) = res_{x}(p(x) − y, q(x)).

Proof. Let q = ∏_{i}(x − ξ_{i})^{ν_{i}} as above. Then by an elementary property of the resultant

res_{x}(p(x) − y, q(x)) = ∏_{i}(p(ξ_{i}) − y) =≠ ^{p}qj

For bidecompositions the following property turns out to be very useful.

3.3. Proposition. Let f = r ∘ p = s ∘ q be a prime bidecomposition using monic polynomials; then

p(q − b) = r − s(b).

Proof. Let q − b = ∏_{i}(x − β_{i}). Thus ^{p}(q − b) = ∏_{i}(x − p(β_{i})). But β_{i} is also a zero of r − s(b), because r(p(β)) = s(q(β)) = s(b).

Assume that b is transcentental. Then all the β_{i} are distinct, as q is tame. Suppose p(β_{1}) = p(β_{2}). As p and q have no common right component, Lüroth’s theorem, provides a rational function f such that f(p, q) = x. Now

β_{1} = f(p, q)(β_{1}) = f(p(β_{1}), q(β_{1})) = f(p(β_{2}), q(β_{2})) = β_{2},

which means, that p maps the zeros of q − b injectively to the zeros of r − s(b). As [p] = [q], this is even a bijection, and the proof is complete for transcendental b.

For arbitrary b we choose some new transcendental element, say y. Then ^{p}(q − y) = r − s(y). Proposition 3.2 allows us to subsitute b for y here, thus providing the full assertion.

4. Ramification

4.1. Definition. We say that e is a ramification point of some polynomial r iff r−e and r′ have a common zero. The degree of gcd(r−e, r′) is called the (ramification) index of r at e and is denoted by ind_{e} r.

4.2. Remark. As r − e and r′ have a common zero iff res(r − e, r′) = 0, the ramification points of r are just the zeros of ^{r}r′.

4.3. Proposition. Let r be a tame polynomial. Then

∑_{e} ind_{e} r = [r] − 1

Proof. As r is tame, [r′] = [r] − 1, and if ξ is a zero of r′ of multiplicity κ, then (x − ξ)^{κ} divides r − e for exactly one e. Thus the sum of the gcd’s is [r′].

The next very important proposition needs a stronger hypothesis (remember definition 1.11).

4.4. Proposition. Suppose that r is completely tame. If we have the canonical factorization r − e = c ∏(x − a_{i})^{α_{i}}, then

ind_{e} r = ∑_{i}(α_{i} − 1).

Proof. As r was assumed to be completely tame, all α_{i} ≠ 0 (mod char k). Thus the multiplicity of a_{i} in r′ is α_{i} − 1, which proves the result.

4.5. Remark. If a polynomial p has only one ramification point e, then ind_{e} p = [p′], thus p is associated to x^{[p]}. Such polynomials are also called exponential.

4.6. Remark. For the rest of this section and the following two ones we fix a non-trivial completely tame prime bidecomposition

f = r ∘ p = s ∘ q

with n = [p] = [s] and m = [q] = [r]. Whenever we want, we can assume all polynomials to be monic. For every point e we use the canonical factorizations over the algebraic closure of k

r − e = ∏_{i}(x − a_{i})^{α_{i}}
s − e = ∏_{j}(x − b_{j})^{β_{j}}.

Then

f − e = ∏_{i}(p − a_{i})^{α_{i}}

= ∏_{j}(q − b_{j})^{β_{j}}

= ∏_{i,j} ∏_{κ=1}^{γ_{ij}}(x − ξ_{ijκ})^{ϵ_{ijκ}},

where the ξ_{ijκ} should be the zeros of f − e classified according to p(ξ_{ijκ}) = a_{i} and q(ξ_{ijκ}) = b_{j}; the ϵ_{ijκ} denote their multiplicities and the γ_{ij} the number of such zeros. Comparing the above factorizations we see that for all i resp. j

(p − a_{i})^{α_{i}} = ∏_{j} ∏_{κ=1}^{γ_{ij}}(x − ξ_{ijκ})^{ϵ_{ijκ}}

(q − b_{j})^{β_{j}} = ∏_{i} ∏_{κ=1}^{γ_{ij}}(x − ξ_{ijκ})^{ϵ_{ijκ}}.

All these notions depend on the point e. If it is nescessary to indicate this dependence, we use upper indices: a_{i}^{(e)}, ξ_{ijκ}^{(e)} and so on.

4.7. Lemma. For i, j we have

α_{i}β_{j} = ∑_{κ=1}^{γ_{ij}} ϵ_{ijκ}

In particular ϵ_{ijκ} ≤ α_{i}β_{j} for all i, j, κ.

Proof. Taking the Tschirnhaus transform we get

p(q − b_{j})^{β_{j}} = ∏_{i} ∏_{κ=1}^{γ_{ij}} ^{p}(x − ξ_{ijκ})^{ϵ_{ijκ}}

= ∏_{i} ∏_{κ=1}^{γ_{ij}}(x − p(ξ_{ijκ}))^{ϵ_{ijκ}}.

= ∏_{i} ∏_{κ=1}^{γ_{ij}}(x − a_{i})^{ϵ_{ijκ}} = ∏_{i}(x − a_{i})^{∑_{κ} ϵ_{ijκ}}.

But on the other hand, using proposition 3.3,

p(q − b_{j})^{β_{j}} = (r − s(b_{j}))^{β_{j}} = (r − e)^{β_{j}} = ∏_{i}(x − a_{i})^{α_{i}β_{j}},

and this factorization must coincide with that obtained before.

4.8. Notation. We will write n ⊆ m or m ⊇ n iff the integer n divides m. Note that (N_{0}, ⊇) is a lattice. Thus it makes sense to use the symbols ∩ and ∪ to denote the greatest common divisor resp. the least common multiple of integers. This intuitive notation will simplify many of our formulas considerably.

4.9. Lemma. For all i, j, κ we have

ϵ_{ijκ} ⊇ α_{i} ∪ β_{j}  (3)
γ_{ij} ⊆ α_{i} ∩ β_{j}.  (4)

Proof. Note that ϵ_{ijκ}, the multiplicity of ξ_{ijκ} in f − e equals α_{i} times its multiplicity in p − a_{i}. Thus ϵ_{ijκ} ⊇ α_{i}. Similarly ϵ_{ijκ} ⊇ β_{j}. Thus the first inequality is clear. From this, together with the previous lemma

α_{i}β_{j} = ∑_{κ=1}^{γ_{ij}} ϵ_{ijκ} ⊇ γ_{ij}(α_{i} ∪ β_{j}).

Then the second equation follows from dividing by α_{i} ∪ β_{j}.

4.10. Lemma. For all i we have

ind_{a_{i}} p = ∑_{j}(β_{j} − γ_{ij}) ≥ ∑_{j}(β_{j} − α_{i} ∩ β_{j}).

Proof. Using proposition 4.4 we get

ind_{a_{i}} p = ∑_{j} ∑_{κ=1}^{γ_{ij}} (\frac{ϵ_{ijκ}}{α_{i}} − 1) = ∑_{j} (∑_{κ=1}^{γ_{ij}} \frac{ϵ_{ijκ}}{α_{i}} − ∑_{κ=1}^{γ_{ij}} 1) = ∑_{j}(β_{j} − γ_{ij}).

The inequality then follows from the previous lemma.

5. Exponential Solutions

The next proposition is very important for our simplifications. First we need a technical lemma.

5.1. Lemma. Suppose that the positive integers α_{i} have no common divisor, i.e., ⋂_{i} α_{i} = 1. Then for all positive integers β

∑_{i}(β − α_{i} ∩ β) ≥ β − 1.

Proof. For β = 1 this is trivial. So we assume β > 1. Suppose that α_{i} is not a multiple of β. Then α_{i} ∩ β ⊂ β, thus ≤ \frac{β}{2} , and the i-th summand is ≥ \frac{β}{2} . If there are two such summands, then they sum up to β and the lemma is proved. Thus consider the case that α_{i} ⊇ β for all but at most one i. Take i = 1 for the possible exception. Then

1 = ⋂ α_{i} = α_{1} ∩ ⋂_{i≠1} α_{i} ⊇ α_{1} ∩ β,

thus α_{1} ∩ β = 1, and we just have to look at the first summand β − α_{1} ∩ β = β − 1 to prove the lemma also in this case.

The following result now has got a direct and considerably shorter proof. It continues in the style of the previous proofs.

5.2. Proposition. If s has only one ramification point, then our bidecomposition is exponential.

Proof. Let e be the unique ramification point. Then e ∈ k, and in our factorizations

ν = 1, β_{1} = n,

where n must be prime by indecomposability. Hence some α_{i} is relatively prime to n, again by indecomposability. Thus let us assume n ∩ α_{1} = 1. Now from lemma 4.10

n − 1 ≥ ind_{a_{1}} p ≥ ∑_{i=1}^{ν}(β_{j} − α_{1} ∩ β_{j}) = n − α_{1} ∩ n = n − 1.

Thus a_{1} is the unique ramification point of p, and as such is in k. For i ≠ 1 we have

0 = ind_{a_{i}} p ≥ n − α_{i} ∩ n,

hence α_{i} ⊇ n. So r has the form

r − e = (x − a_{1})^{α_{1}} · t^{n}

for some polynomial t. a_{1} and the coefficients of t are elements of k because they can be computed from the squarefree factorization. The form of q is determined by the other three polynomials.

Because the results in this section are symmetric in the sense that we can interchange the rôles of the two decompositions r ∘ p and s ∘ q, we can summarize

5.3. Proposition. If at least one of the two polynomials r and s has only one ramification point, then our bidecomposition is exponential.

6. Trigonometric Solutions

6.1. Proposition. If r has at least two ramification points, then

∑_{i} ind_{a_{i}} p = ind_{e}s.

Proof. Because r −e is not exponential, but indecomposable, ⋂ α_{i} = 1. Thus we can apply the lemma for each β_{j} and, after summation, we get

∑_{j} ∑_{i}(β_{j} − α_{i} ∩ β_{j}) ≥ ∑_{j} β_{j} − 1.

Now we use lemma 4.10 to estimate

∑_{i} ind_{a_{i}} p ≥ ∑_{i} ∑_{j}(β_{j} − α_{i} ∩ β_{j}) ≥ ∑_{j} β_{j} − 1 = ind_{e}s,

thus proving the ≥-part.

To see equality we consider the factorizations of remark 4.6 for various e’s. Note that for r − e_{1} and r − e_{2} have no common zero whenever e_{1} ≠ e_{2}, thus all the elements α_{i}^{(e)} are distinct, so from summing up over all e ∈ k we get

m − 1 = ∑_{e} ind_{e} p = ∑_{e} ∑_{i} ind a_{i}p ≥ ∑_{e} ind_{e} s = m − 1,

hence the ≥ here is an equality, and by the part just proved all summands are equal, too.

6.2. Lemma. If r has two ramification points and r − e contains a simple zero, say a_{1} (i.e. α_{1} = 1), then

α_{i} ⊇ ⋃_{j} β_{j}, for all i ≠ 1.

Proof. By proposition 6.1 together with lemma 4.10

∑_{j}(β_{j} − 1) = ind_{e} s = ∑_{i} ind_{a_{i}} p ≥ ∑_{i} ∑_{j}(β_{j} − α_{i} ∩ β_{j}),

and using α_{1} ∩ β_{j} = 1,

= ∑_{j}(β_{j} − 1) + ∑_{i≠1} ∑_{j}(β_{j} − α_{i} ∩ β_{j})  (5)

Thus for i ≠ 1 and all j we have β_{j} ≤ α_{i} ∩ β_{j}, i.e. α_{i} ⊇ β_{j}.

6.3. Remark. If r − e has no simple zero, then all its zeroes are at least double, hence their number is at most \frac{m}{2}, so ind_{e} r ≥ \frac{m}{2}. This cannot happen twice.

6.4. Proposition. If both r and s have at least two ramification points, then they have exactly two (common) ones. Let e be one of them. Then both r − e and s − e have exactly one simple zero, the remaining ones being double.

Proof. Suppose e is a ramification point of s such that r − e has a simple zero, say a_{1}, thus α_{1} = 1. By the lemma, all the remaining α_{i} are multiples of all the β_{j}. But some b_{j} > 1, thus, in particular, a_{i} ≥ 2 for all i ≠ 1. Hence e is also a ramification point of r and ind_{e} r ≥ \frac{m−1}{2} because μ ≤ \frac{m−1}{2}. If e′ is another ramification point of r, then its index is bounded by \frac{m−1}{2}, so r − e′ has also a simple zero, and the whole story is equally true for this second ramification point. Thus r has exactly the two ramification points e and e′, both with index \frac{m−1}{2}, hence μ = \frac{m+1}{2}. r − e has a simple zero, the remaining \frac{m−1}{2} ones sum up to m−1, thus are double. The same is true for e′ and, by symmetry, for the ramification points of s.

6.5. Remark. This means that for α_{1} = β_{1} = 1 and α_{i} = β_{i} = 2 for all i ≠ 1 for both ramification points e. Thus γ_{11} = 1, ϵ_{111} = 1, and ϵ_{ijκ} ⊇ 2, if not i = j = 1. Thus, if e_{1}, e_{2} are the two ramification points, then

f − e_{1} = (x − ξ_{1}) · g_{1}^{2},
f − e_{2} = (x − ξ_{2}) · g_{2}^{2}

for some polynomials g_{1}, g_{2}. Because f has exactly two ramification points, e_{1} and e_{2} satisfy a quadratic equation over k (4.2). So we can apply proposition 2.4, and obtain:

6.6. Corollary. If both r and s contain two ramification points, then our bidecomposition is trigonometric.

7. Final Remarks

Now the proof of Ritt’s bidecomposition theorem is complete. Let us outline where simplifications have been made, and which further improvements seem to be possible.

Previous proofs assume that the ground field k is algebraically closed. In [Sch82] the theorem for general fields is obtained as a corollary to that for algebraically closed ones. Our version proves the general form directly. There are only few points where we must take care of this, e.g. in 2.5 whose nontrivial part says that we the linear transformations can be chosen in the ground field.

That we use the Tschirnhaus transform instead of the norm as previous elementary proofs is mainly a matter of taste. Note that pq ·p = ±N_{k(x):k(p)}(q). The usage of the resultant is new in this context and may supply further improvements, when used more extensively. Our proof of proposition 3.3 serves as an alternative to the usage of norms and minimal polynomials; it seems to be more direct.

The section on ramification contains results mixed from the previous proofs. Lemma 4.9 has got an elementary proof.

Our major simplifications are contained in sections 5 and 6. There is no discussion of extra points anymore. We just make the distinction on the number of ramification points and quickly see by analyzing the ramification structure that we have the exponential or trigonometric case respectively.

These improvements essentially use that the components of prime bidecompostions are indecomposable. Thus they do not generalize as in [Sch82], partially characterizing bidecompositions that need not be prime. This raises the question, whether the two theorems of Ritt (1.5 and 1.13) can be used to give a general exact description of all possible decompositons. In particular, we may ask whether there is a canonical decomposition.

The decompositions of exponential polynomials (associated to x^{n}) may be considered to be trivial as they simply correspond to the factors of n. The same is true with Dickson polynomials. This suggest that a canonical decomposition could look like this: a composition of polynomials that are either Dickson or occur in some bidecomposition or have nothing to do with bidecompositions.

As another further improvement it might be possible to use the resultant and square-free factorizations indstead of the involved anaysis of the zeros and their multiplicities in sections 4 to 6.

The assumption about char 2 in the theorem was necessary because proposition 2.4 uses it, which again is needed in 6.6. It is not clear whether we get any additional bidecompositions in case of characteristic 2.

The restriction to completely tame polynomials was necessary in proving 4.4, which is basic for all results about the index. It is not known how far this can be weakened, e.g. to tame polynomials..

Another open problem is, how far the assumptions can be weakened, or how the assertion should be changed for finite characteristic. One form of counterexample can be obtained as follows. Let χ = char k; then for all indecomposable polynomials f

x^{χ} · f = f · x^{χ}

is a bidecompositions. Can all bidecompositions be reduced to trigonometric or exponential form using this ambiguity somehow?

The characterization of bidecompositions of rational functions seems to be more difficult. In this case, for example one gets the Redei functions as another class of permuting functions.

References

[Bin95] Franz Binder, Polynomial decomposition, Master’s thesis, University of Linz, June 1995.

[DW74] F. Dorey and G. Whaples, Prime and composite polynomials, Journal of Algebra (1974), no. 28, 88–101.

[Eng41] H. T. Engström, Polynomial substitutions, American Journal of Mathematics (1941), no. 63, 249–255.

[Lev42] H. Levi, Composite polynomials with coefficients in an arbitrary field of characteristic zero, American Journal of Mathematics (1942), no. 23, 51– 66.

[LMT93] R. Lidl, G. L. Mullen, and G. Turnwald, Dickson polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 65, Longman Scientific & Technical, London, 1993.

[LN73] Hans Lausch and Wilfried Nöbauer, Algebra of polynomials, North-Holland Mathematical Library, vol. 5, North Holland, Amsterdam, 1973.

[Rit22] J. F. Ritt, Prime and composite polynomials, Transactions of the American Mathematical Society (1922), no. 23, 51–66.

[Sch82] A. Schinzel, Seclected topics on polynomials, Ann Arbor, University of Michigan press, 1982.

Department of Mathematics, Johannes Kepler University Linz, Austria

E-mail address: xbx@bruckner.stoch.uni-linz.ac.at