COMPOSITE RATIONAL FUNCTIONS EXPRESSIBLE WITH FEW TERMS

CLEMENS FUCHS AND UMBERTO ZANNIER

Abstract. We consider a rational function f which is ‘lacunary’ in the sense that it can be expressed as the ratio of two polynomials (not necessarily coprime) having each at most a given number ℓ of terms. Then we look at the possible decompositions f(x) = g(h(x)), where g, h are rational functions of degree larger than 1. We prove that, apart from certain exceptional cases which we completely describe, the degree of g is bounded only in terms of ℓ (and we provide explicit bounds). This supports and quantifies the intuitive expectation that rational operations of large degree tend to destroy lacunarity.

As an application in the context of algebraic dynamics, we show that the minimum number of terms necessary to express an iterate h^{∘n} of a rational function h, tends to infinity with n, provided h(x) is not of an explicitly described special shape. The conclusions extend some previous results for the case when f is a Laurent-polynomial; the proofs present several features which did not appear at all in the special cases treated so far.

1. Introduction and results

In this paper we are concerned with ‘lacunary’ rational functions; by this we mean expressions f(x) = P (x)/Q(x), where P, Q are polynomials (not necessarily coprime) having altogether at most a given number ℓ of terms. We think of the number of terms as being bounded whereas we allow the degrees of the terms and their coefficients to be arbitrary.

More specifically, the paper studies the decomposability of such a lacunary function, namely the equation f(x) = g(h(x)), where g, h are rational functions of degree > 1.

We remark that lacunary polynomials (or rational functions) appear in many mathematical investigations: the binomials have an ancient history; reducibility of trinomials and ℓ-nomials was studied by Selmer, ..., Schinzel (see e.g. [13], Chs. 5, 6). Lacunary polynomials are meaningful also because they appear as expressing restrictions of any prescribed regular function on 𝔾_{m}^{n} to varying 1-dimensional algebraic subgroups.

Generally speaking, lacunary polynomials also appear in computational issues since we may ‘write down’ a formula for a polynomial with given number of terms, thinking of the degrees and coefficients as indeterminates. (For instance lacunary polynomials appear as one-way functions in cryptography.) We may further quote work in real geometry (see e.g. the survey [9]) showing that sometimes it is possible to have control on objects defined by equations with boundedly many terms, even if they have large degree.

And also ‘decomposability’ of a rational function f is relevant in arithmetical and algebraic questions; it is for instance deeply related to the Galois group of the rational cover f : ℙ_{1} → ℙ_{1}, and has impact in Diophantine equations with separated variables (see e.g. [1, 3]).

The paper [18] studied the decomposability of lacunary polynomials; note that since the degree of a polynomial with a fixed number of terms may be arbitrarily large, it does not appear an obvious issue to check whether it is decomposable. It has been proved therein that if f is a ‘lacunary’ polynomial, say with at most ℓ non-constant terms, and if f(x) = g(h(x)) for polynomials g, h of degree larger than 1, then either h(x) has the special shape ax^{n} +b or deg g is bounded in terms only of ℓ. In other words, roughly speaking, if g has ‘large’ degree then g(h(x)) has ‘many’ terms (or else h is very special). So this kind of result supports and quantifies the intuitive expectation that polynomial operations of large degree tend to destroy lacunarity.

Moreover, this bound led in [19] to a proof of a conjecture of Schinzel, and even to describe ‘algorithmically’ all the possible decompositions of a polynomial with a given number of terms.

In [20] a similar bound was extended to Laurent-polynomials (with a new unavoidable exceptional shape) also with the purpose of application to certain questions studied by Watt and Zieve on symbolic polynomials [16]. Actually, these last authors would also require, for further applications, some extension of such bounds to general rational functions, and on the other hand this could also admit applications to a generalisation of the results of [19].

It is the purpose of this paper to carry out this program. We remark at once that this extension does not appear to follow by a mere straightforward modification of the methods of [18, 20], as several new crucial obstacles appear. (For the treatment of one case we have even found it necessary to rely on a paper using the classification of finite simple groups.)

As a simple immediate application in the context of one-variable dynamics, we shall also prove a corollary bounding below the number of terms of an n-times iterate h^{∘n} of a rational function h. (This was done in [18] for Laurent-polynomials.)

Notation.

• We let k be a field of characteristic zero. For the present purposes it causes no loss of generality to suppose, as we shall do, that k is algebraically closed. As usual we set k^{∗} = k\{0}.

• The degree of f ∈ k(x) is defined by deg f = [k(x) : k(f(x))]. In case f(x) = p(x)/q(x), with p, q ∈ k[x] coprime, deg f is just the maximum of the degrees of p and q respectively. (We shall also use degrees in function fields other than k(x); see Section 2.)

• We denote by PGL_{2}(k) = Aut(ℙ_{1}(k)) the group of linear fractional transformations, i.e. rational functions of the form (ax + b)/(cx + d) with a, b, c, d ∈ k, ad − bc ≠ 0, and by ∞ = (0 : 1) the unique point at infinity of ℙ_{1}(k).

• We say that a rational function f ∈ k(x) is decomposable if there is a non-trivial decomposition of f as a rational function in k(x), i.e. an equation f(x) = g(h(x)) with g, h ∈ k(x), deg g, deg h > 1. Observe that we can modify such decompositions by replacing g, h resp. by g ∘λ^{−1}, λ∘h with any λ ∈ PGL_{2}(k). We remark that if f is a polynomial or a Laurent-polynomial, then we can easily normalize correspondingly g, h; see Remark 1.1 below.

Accordingly, we say that f is indecomposable if the equality f(x) = g(h(x)), g, h ∈ k(x), implies deg g = 1 or deg h = 1.

• We denote by T_{n} the Chebyshev polynomial of degree n; it is uniquely determined by the equation T_{n}(x + x^{−1}) = x^{n} + x^{−n}.

We are now ready to formulate the main result.

Main Theorem. Let ℓ be a positive integer and let f ∈ k(x) be expressible as f(x) = P (x)/Q(x), where P, Q ∈ k[x] have altogether at most ℓ terms. Suppose that f(x) = g(h(x)), where g, h ∈ k(x) and where h(x) is not of the shape λ(ax^{n} + bx^{−n}) for any a, b ∈ k, n ∈ ℕ and λ ∈ PGL_{2}(k). Then

deg g ≤ 2016 · 5^{ℓ}.

Note that in this statement we are not assuming that P, Q are coprime (which would lead to an easier discussion). We shall refer to the shape λ(ax^{n} + bx^{−n}) as the forbidden shape (for the Main Theorem).

Here is the simple application to iterates alluded to above, where we denote by h^{∘n} the nth iterate h(h(… h(x)) …):

Corollary. Let q ∈ k(x) be non-constant and let h ∈ k(x) be of degree d ≥ 3. Suppose that h(x) is not conjugate (with respect to the group action given by PGL_{2}(k) on k(x)) to ±x^{d} or to ±T_{d}(x). Then, for any integer n ≥ 3, we cannot express h^{∘n}(q(x)) as a ratio of polynomials having altogether less than \frac{1}{log 5}((n − 2) log d − log 2016) terms.

Note that in the cases h(x) = x^{d} and h(x) = T_{d}(x) we cannot obtain any bound tending to infinity with d, in view of the equations h^{∘n}(x) = x^{d^{n}} in the first case and h^{∘n}(x + x^{−1}) = x^{d^{n}} + x^{−d^{n}} in the second case. We have restricted to deg h ≥ 3 for simplicity. If deg h = 2 we may obtain a similar statement with a slightly more boring proof, or by applying this one with h(h(x)) in place of h(x). Inspection shows that the proof yields further precision on the shape of q(x) if the conclusion does not hold.

The Main Theorem takes into account the most general case, but it subdivides into a number of subcases according to the shape of f and h, where the bound takes different forms and the proofs can be more or less involved. Therefore we add to this statement the corresponding statements for the subcases; in turn, the Main Theorem follows easily from these statements.

Theorem 1 (Polynomial case). Let ℓ be a positive integer and let f ∈ k[x] be a polynomial with ℓ non-constant terms. Suppose that f(x) = g(h(x)), where g, h ∈ k[x] and where h(x) is not of the shape ax^{n} + b for a, b ∈ k, n ∈ ℕ. Then

deg f + ℓ − 1 ≤ 2ℓ(ℓ − 1) deg h

and

deg g ≤ 2ℓ(ℓ − 1).

This is [18, Theorem 1]. We remark (as is pointed out in [18]) that the exclusion of polynomials h of the shape ax^{n} + b is really necessary as is shown by simple examples like g(x) = g^{∗}(x − b), where g^{∗} ∈ k[x] has ℓ non-constant terms.

Theorem 2 (Laurent case). Let ℓ be a positive integer and let f ∈ k[x, x^{−1}]\k[x] be a Laurentpolynomial with ℓ non-constant terms. Suppose that f(x) = g(h(x)), where g ∈ k[x], h ∈ k[x, x^{−1}] and where h(x) is not of the shape ax^{n} + b + cx^{−n} for a, b, c ∈ k, n ∈ ℕ. Then

deg f ≤ 2(2ℓ − 1)(ℓ − 1)(deg h − 2)

and

deg g ≤ 2(2ℓ − 1)(ℓ − 1).

This follows at once from [20]. We again remark (as in [20]) that the exclusion of Laurentpolynomials h of the shape as in the theorem cannot be avoided as follows e.g. from the example T_{n}(x+x^{−1}) = x^{n} +x^{−n}. Thus these exceptions also have to be taken into account in the present Main Theorem.

Remark 1.1 Suppose that f ∈ k[x] is a polynomial which is decomposable as a rational function: f = g ∘ h, g, h ∈ k(x). Then observe that, by changing h into λ ∘ h for a λ ∈ PGL_{2}(k), and changing g into g ∘ λ^{−1}, which does not change deg g, deg h, we may assume that g, h are polynomials: in fact, the preimage f^{−1}(∞) consists just of ∞ (since f is a polynomial) and, by choosing λ suitably, the same becomes true for g and h. Thus f is decomposable also as a polynomial.

Similarly for the case when f is a Laurent-polynomial, but neither f ∈ k[x] nor f ∈ k[x^{−1}]: First, the preimage f^{−1}(∞) is {0, ∞}. If f = g ∘ h, then g^{−1}(∞) is either {P } or {P, Q}, P, Q ∈ ℙ_{1}(k), P ≠ Q and we have h^{−1}(P) = {0, ∞} or h^{−1}({P, Q}) = {0, ∞}, respectively. In the first case we may choose λ so to assume that P = ∞ and thus g is a polynomial and h a Laurent-polynomial. In the second case, if h^{−1}(P) = {0}, h^{−1}(Q) = {∞}, we choose a λ so to transform Q into ∞ and P into 0 (this is possible since PGL_{2}(k) is doubly-transitive). Then g becomes a Laurent-polynomial and h(x) = cx^{n} becomes of the forbidden shape.

(In particular, this shows that when h is a (Laurent-) polynomial, the exceptional shapes of the Main Theorem may be reduced to the shapes stated in Theorem 1 and Theorem 2.)

The normalization described in this remark shall be used repeatedly in what follows.

These two theorems present the current state of the problem. In the next statements we give the new results, which together with the stated theorems will yield the Main Theorem.

With the phrasing ‘(non-)Laurent case’ we refer to the shape of h; however, even when h is a (Laurent-) polynomial, the situation differs from the previous two theorems in the fact that we compose h with a rational function g (rather than a polynomial).

Of course it may happen that h ∉ k[x, x^{−1}] but λ ∘ h ∈ k[x, x^{−1}] for a suitable λ ∈ PGL_{2}(k), so that after changing g, h resp. by g ∘ λ^{−1}, λ ∘ h we are in the Laurent case. To express rapidly this fact, we have found it convenient to introduce the following simple definition:

Definition NL: h satisfies NL :⟺ For any λ ∈ PGL_{2}(k): λ ∘ h ∉ k[x, x^{−1}].

Namely, h satisfies NL (Non-Laurent) if h cannot be turned into a Laurent-polynomial by applying a linear fractional transformation on the left.

This definition allows us to reduce more simply the remaining cases to the following theorems:

Theorem 3 (Laurent case for rational functions). Let ℓ be a positive integer and let f ∈ k(x) be expressible as f(x) = P (x)/Q(x), where P, Q ∈ k[x] have altogether at most ℓ terms. Suppose that f(x) = g(h(x)), where g ∈ k(x), h ∈ k[x, x^{−1}], and where h(x) ≠ ax^{n} + b + cx^{−n} for any a, b, c ∈ k, n ∈ ℕ. Then we have the following two cases:

(i) If P, Q are coprime in k[x], then

deg f ≤ 2(2ℓ − 1)(ℓ − 1) deg h, deg g ≤ 2(2ℓ − 1)(ℓ − 1).

(ii) In general we have

deg f ≤ (2016 · 5^{ℓ})(deg h − 1), deg g ≤ 2016 · 5^{ℓ}.

Note that the inequalities on the right for deg g follow from the respective ones on the left for deg f, in view of deg f = deg g deg h.

We remark that our proof of the last case (ii) in this statement is the most involved step in the whole paper and requires a result of Müller [11] relying on the classification of finite simple groups. This is not needed in the case (i), when f is in reduced form, since we may apply [20, Theorem 2*] to the numerator and the denominator to get the conclusion; for this case we do not even need the auxiliary results in Section 2 or the normalizations from Section 3; we give the proof, which is independent of the rest, in Subsection 5.1.

We also point out that Theorem 3(ii) gives a partly new proof for Theorems 1, 2 (with a worse bound for deg f).

Theorem 4 (Non-Laurent case for rational functions). Let ℓ be a positive integer and let f ∈ k(x) be expressible as f(x) = P (x)/Q(x), where P, Q ∈ k[x] have altogether at most ℓ terms. Suppose that f(x) = g(h(x)), where g, h ∈ k(x) with both h satisfies NL and for every equation h(x) = p(q(x)) either q satisfies NL or q(x) = λ(ax^{n} + bx^{−n}) for a λ ∈ PGL_{2}(k) and some a, b ∈ k, n ∈ ℕ. Then

deg f ≤ (267 · 5^{ℓ})(deg h − 1), deg g ≤ 267 · 5^{ℓ}.

Before we continue with some remarks on the stated results we now give at once the deduction of the Main Theorem from the other theorems; the proof is almost immediate:

Deduction of the Main Theorem from Theorems 1, 2, 3 and 4: If f is a polynomial or a Laurent-polynomial that is decomposable as f(x) = g(h(x)) with h(x) not of the forbidden shape (of the Main Theorem), then by Remark 1.1 we may change the decomposition (from f = g ∘ h to f = (g ∘ λ^{−1}) ∘ (λ ∘ h) with λ ∈ PGL_{2}(k)) so that for the new composition factors we have either g, h ∈ k[x] or g ∈ k[x], h ∈ k[x, x^{−1}]; then the result follows by Theorem 1 or Theorem 2 respectively (observe that by the assumptions of the Main Theorem the modified h certainly cannot be of the forbidden shape of the respective theorem). (We mention that as noted right before Theorem 4, this opening paragraph could be skipped and subsumed in the arguments below.)

Now let f ∈ k(x) and f(x) = g(h(x)) with h(x) not of the forbidden shape (of the Main Theorem). If h satisfies NL and for every equation h(x) = p(q(x)) either q satisfies NL or q(x) = λ(ax^{n} + bx^{−n}) for a λ ∈ PGL_{2}(k) and some a, b ∈ k, n ∈ ℕ, then the conclusion follows from Theorem 4.

Otherwise we have two cases:

In the first case, h does not satisfy NL, so there is a homography λ ∈ PGL_{2}(k) with λ ∘ h ∈ k[x, x^{−1}]; now, on replacing g, h resp. by g ∘ λ^{−1}, λ ∘ h, we may assume that h ∈ k[x, x^{−1}], and the conclusion follows from Theorem 3.

In the second case there exists an equation h(x) = p(q(x)) with p, q ∈ k(x) such that λ^{∗} ∘ q ∈ k[x, x^{−1}] for a suitable λ^{∗} ∈ PGL_{2}(k) and q(x) is not of the stated shape λ(ax^{n} + bx^{−n}). In this case, by changing the equation h = p ∘ q into h = (p ∘ (λ^{∗})^{−1}) ∘ (λ^{∗} ∘ q), we may again assume that q ∈ k[x, x^{−1}], and we have a fortiori that q(x) ≠ ax^{n} + b + cx^{−n} for any a, b, c ∈ k, n ∈ ℕ. Also, we have now the decomposition f(x) = (g ∘ p)(q(x)), and we may apply to it Theorem 3 with g ∘ p in place of g and q in place of h. Since deg(g ∘ p) ≥ deg g, the result again follows.

Since there are no further cases, the deduction of the Main Theorem is complete. □

Remark 1.2

(i) We did not make any special effort to derive good numerical constants in the theorems; however, the exponential dependence of the bound on ℓ cannot be improved using our way of reasoning. (This step occurs in the subdivision - introduced below - of the set of exponents appearing in P, Q into ‘large’ and ‘small’ ones; such a subdivision was not necessary and not taken into account in the polynomial and Laurent case treated in previous papers, which explains the better dependence on ℓ obtained therein.) Also, we do not have lower bounds better than linear in ℓ and we do not have definite ideas on what could be a best-possible shape for them.

(ii) Note that in the most general case we do not assume that the ‘lacunary’ expression f(x) =

P (x)/Q(x) for f is in reduced form. (iii) The issue arises if more is true, namely a similar bound on the mere assumption that the

numerator is lacunary. This in turns naturally leads to the following strictly related question:

Question: Suppose that f is a polynomial with at most ℓ terms, and that it is divisible by g(h(x)) for g, h ∈ k[x], deg g, deg h ≥ 2, h(x) not of the form ax^{n} + b, a, b ∈ k, n ∈ ℕ. Is is true that deg g is necessarily bounded only in terms of ℓ?

We feel that this question might have a positive answer in general, but certainly a proof would require new methods. Some evidence for a positive answer is provided by the case when f has at most two terms; we treat this special case in the appendix to this paper.

The strategy of our method is very roughly as follows: We choose a conjugate y ≠ x of x over the field k(h), so we have h(x) = h(y). The equation f(x) = g(h(x)) ∈ k(h) then implies f(x) = f(y). Thus we end up with P (x)Q(y) − P (y)Q(x) = 0. We view this last equation as an S-unit equation with ‘few’ terms (here we use the lacunarity), and apply a theorem of Brownawell-Masser (cf. Lemma 2) to bound the maximal involved degree. However, this theorem can be applied directly only to equations in which no proper subsum vanishes. Hence we are led to study the vanishing subsums of the numerator of f(x) − f(y). If f is a (Laurent-) polynomial, this is easier because each vanishing subsum may then be written as p(x) − q(y) = 0 and has the same ‘separated variables’ structure as the original equation. (This analysis was the one carried out in the previous papers on the topic.)

On the other hand, if f is not a Laurent-polynomial, the vanishing subsums may have a priori a different structure. To study them we then distinguish between ‘large’ and ‘small’ exponents. In order to take advantage of the alluded upper bound, we are led to investigate lower bounds for the degree deg_{K}(z) = [K : k(z)] in K = k(x, y) of expressions of the form z = x^{m}y^{n} with m, n ∈ ℤ; we need a bound of the shape deg_{K}(z) ≥ ε max{|m|, |n|} deg_{K}(x) for some specific number ε > 0, where the dependence on deg_{K}(x) is essential in comparison with the upper bound that follows from the Brownawell-Masser inequality. (This problem reflects another major difference with the case of Laurent-polynomials.)

In order to overcome this issue we use the partition of the exponents mentioned before and moreover we require detailed information on the irreducible factors of h(Y) − h(x) and their associated Puiseux series; in turn, this involves a deep result by Müller in one of the cases into consideration. We do not enter now in any detail concerning this point; we shall comment further on this at the end of Section 3.

The paper is organized as follows: In the next section we will collect some auxiliary results which are all well known and which are needed in our proof. We formulate these results in a way suitable for our applications. In Section 3 we start with some first reductions and normalizations and we study lower bounds for the degree of x^{m}y^{n}. In Section 4 we give the proof of a ‘big’ part of our theorem; in other words we prove Theorem 4. In this case a lemma by Hajós (cf. Lemma 1) will also be of importance. In Section 5 we prove the result in the Laurent case for rational functions (that is Theorem 3), and then in the last section we give the proof of the corollary. Finally, in the appendix we discuss the afore-mentioned result concerning the more general question.

2. Auxiliary results

In this section we collect some auxiliary results that we will use in the proof of our theorems and that already appear in the literature; in general we shall give no proofs.

Lemma 1 (Hajós lemma). Let f ∈ k[x] have ℓ non-constant terms and let β ∈ k^{∗}. Then ord_{β}(f(x) − f(β)) ≤ ℓ.

The proof of this lemma is in fact very easy by calculating the first ℓ + 1 derivatives of f(x) − f(β) and then reducing the resulting linear system of equations in the ℓ + 1 unknown coefficients to a system of Vandermonde type.

Before we state our next lemma we briefly review the theory of valuations/places on function fields (for which we refer e.g. to [10]).

For each θ ∈ k we have a place of k(x) whose valuation v_{θ} expresses the order of vanishing at θ, namely is given by v_{θ}(f) = n if f(x) = (x − θ)^{n}g(x) with g(θ) ≠ 0. Moreover, there is a place ∞ whose valuation v_{∞} is given by v_{∞}(f) = deg Q − deg P for f(x) = P (x)/Q(x) with P, Q ∈ k[x]. As a matter of terminology, if f has a pole at v, i.e. v(f) < 0, then the order ord(f) of v as a pole of f is given by −v(f) > 0.

In this way all (normalized) valuations of k(x)/k are obtained.

Now, let K be a finite extension of k(x). Each of the places of k(x) can be extended in at most [K : k(x)] ways to a place on K and in this way all places v on K are obtained (normalized so that v(K\{0}) = ℤ). Furthermore, the places of K are in a one-to-one correspondence with the points over k of a(ny) nonsingular complete curve over k with function field K; in particular, for the rational function field k(x) the places are in one-to-one correspondence with the points of ℙ_{1}(k).

For an element f ∈ K we define the degree (sometimes also called the height) of f with respect to K by

deg_{K}(f) = ∑_{v} max{0, v(f)} = − ∑_{v} min{0, v(f)},

where the sum is taken over all places of K; thus it is just the number of zeros respectively poles of f counted according to multiplicity. Equivalently, we have deg_{K}(f) = [K : k(f)]. A useful property for us is deg_{K}(f) − deg_{K}(g) ≤ deg_{K}(fg) ≤ deg_{K}(f) + deg_{K}(g) for fg ≠ 0.

As in the quoted previous papers on this topic, we shall need the following crucial result on S-units in function fields.

Lemma 2 (Brownawell-Masser). Let K/k be a function field (in one variable), of genus 𝔤, and let z_{1}, …, z_{s} ∈ K be not all constant and such that 1 + z_{1} + … + z_{s} = 0. Suppose also that no proper subsum of the left side vanishes. Then

max\{deg_{K}(z_{i})\} ≤ \binom{s}{2}(2𝔤 − 2 + |S|),

where S is any set of places of K containing all zeros and poles of the z_{i}.

We have taken this formulation from [18, 20], but we mention again that it is an immediate consequence from [4] (or from [17]).

Our next lemma involves permutation groups, so we recall some standard definitions before giving the statement. Let S_{n}, A_{n} denote the symmetric group and the alternating group of n elements respectively. Assume that a group G is acting on a set Ω and let α ∈ Ω. The orbit of α under G is defined by Gα = {gα : g ∈ G} and the point stabilizer of α in G by G_{α} = {g ∈ G : gα = α}. A group is said to act transitively on Ω if it has only one orbit, i.e. Gα = Ω for all α ∈ Ω. Let m be an integer with 1 ≤ m ≤ |Ω| and denote by Ω^{m} the mth cartesian power of Ω. G acts on Ω^{m} componentwise and the subset Ω^{(m)} of unordered m-tuples of distinct points is G-invariant for every choice of G and m. We say that G is m-transitive if G is transitive on Ω^{(m)}. Finally, let G be a group acting transitively on a set Ω with at least two points. We call G primitive if each point stabilizer G_{α} is a maximal subgroup of G. For these definitions we refer e.g. to [5].

Lemma 3 (Müller). Let h be an indecomposable Laurent-polynomial, written as h(x) = p(x)/x^{e}, p ∈ k[x], e ∈ ℕ, and suppose that d = deg h = deg p > e > 0. Then the Galois group G of the equation h(X) − h(x) over k(h(x)), as a permutation group on the d roots, is primitive and contains an element with exactly two cycles of lengths say n and d − n; it satisfies at least one of the following:

(i) A_{d} ⊆ G, (ii) d = m^{2} with 1 < m ∈ ℕ, n = ma with gcd(m, a) = 1, G = (S_{m} × S_{m}) ⋊ ℤ/(2) and the

stabilizer of a point is conjugate to (S_{m−1} × S_{m−1}) ⋊ ℤ/(2), (iii) d ≤ 64.

This statement follows immediately from the paper [11] (which in turn is essentially contained in [12]); more precisely it follows from Theorem 4.8, the additional information in case (ii) comes from Theorem 3.3 that contains the main classification result for primitive permutation groups with cyclic two-orbit. The upper bound appearing in case (iii) could be replaced by an explicit list of sporadic groups, but since this has only a small impact on the numerical estimates in our theorems, we prefer not to deal with such exceptional cases of small degree.

We mention that G being 2-transitive amounts to (h(X) − h(Y))/(X − Y) being absolutely irreducible over k. This is an information (not always verified) that is important in our application to the Laurent-case for rational functions. (For polynomials the corresponding classification is due to Fried [7]; the paper of Müller [11] also records precise information on the Galois group in this case, namely for an indecomposable h ∈ k[x], d = deg h ≥ 32 the Galois group G of h(X) − h(x) over k(h(x)) is either ℤ/(p) or the dihedral group of p elements for some prime p = d or A_{d} or S_{d}; see [11, Theorem 4.9, p. 63].)

We end this section by collecting some information on the Puiseux series for the equation h(Y) = h(x) for an h ∈ k(x).

Lemma 4. Let h(x) = x^{e}p(x)/q(x) with p, q ∈ k[x] coprime, p(0)q(0) ≠ 0, e ∈ ℤ\{0}. Define s = e + deg p − deg q. Assume that h(∞) = ∞, i.e. s > 0. Let y be a solution of the equation h(Y) − h(x) = 0 in an algebraic closure of k(x). For e < 0, the dominant terms of the possible Puiseux series for y are as follows. At x = 0 there are precisely 1. |e| Puiseux series with y = θx + …, θ^{|e|} = 1,

2. s Puiseux series with y = θx^{−|e|/s} + …, θ^{s} = 1,

3. deg q Puiseux series with y = θ + …, where θ ∈ k^{∗} satisfies q(θ) = 0, and at x = ∞

1. s Puiseux series with y = θx + …, θ^{s} = 1,

2. |e| Puiseux series with y = θx^{−s/|e|} + …, θ^{|e|} = 1,

3. deg q Puiseux series with y = θ + …, where θ ∈ k^{∗} satisfies q(θ) = 0. For e > 0, the first terms of the Puiseux series are as follows. At x = 0 there are precisely

1. e Puiseux series with y = θx + …, θ^{e} = 1,

2. deg p Puiseux series with y = θ + …, where θ ∈ k^{∗} satisfies p(θ) = 0, and at x = ∞

1. s Puiseux series with y = θx + …, θ^{s} = 1,

2. deg q Puiseux series with y = θ + …, where θ ∈ k^{∗} satisfies q(θ) = 0.

We remark that the dots here indicate that the terms which follow have a higher order of zero than the first one (at the relevant point).

Proof. We start with the case e < 0 and x = 0. Observe that deg h = deg p = s + |e| + deg q > 0. From the definition of y we have

(1)  h(x) = \frac{p(x)}{x^{|e|}q(x)} = \frac{p(y)}{y^{|e|}q(y)} = h(y).

At x = 0 we have h = ∞ and therefore either y = 0 or y = ∞ or y = θ ∈ k^{∗} with q(θ) = 0. In the first case, equation (1) implies that the Puiseux expansion at x = 0 of y satisfies y^{|e|} + … = x^{|e|} + … and therefore y = θx + … for θ an |e|th root of unity. Clearly, we have |e| series of this type. In the second case, (1) implies the relation

x^{|e|} + … = \frac{1}{y^{s}} + …

and therefore y = θx^{−|e|/s} + … for θ an sth root of unity. Altogether we have s series of that type. Finally in the third case, (1) means that we have y = θ + …, where θ ∈ k^{∗} is a root of q. Altogether there are deg q series of this type. Thus we have the result in the case x = 0.

The Puiseux factorisation of h(Y) − h(x) at x = ∞ and the case e > 0 can be obtained following the same line of arguments. □

We remark that in all cases when the series looks like y = θ + …, the root θ ∈ k^{∗} of q respectively p appears as many times as its multiplicity; we shall not need this.

3. Normalizations and preliminaries on degrees

Let ℓ be a positive integer. The proofs of Theorem 3(ii) and Theorem 4, respectively, will be done by induction on ℓ.

So let f ∈ k(x) with f(x) = P (x)/Q(x) = g(h(x)) ∈ k(x), where g, h ∈ k(x), deg g, deg h > 1, and where P, Q ∈ k[x] are not necessarily coprime; however, we assume them not to be both divisible by x, which we may do without affecting their number of terms. We assume that the number of terms appearing in P, Q altogether is ℓ. By the last normalization it follows that there are exactly ℓ − 1 non-constant terms; in particular, this implies that ℓ ≥ 2.

We shall assume throughout that h(x) is not of the forbidden shape λ(ax^{n} + bx^{−n}) for any a, b ∈ k, n ∈ ℕ and λ ∈ PGL_{2}(k). We remark that we may consider the statements also for deg h = 1 in which case they are empty (and so trivially true) since then h(x) has forbidden shape.

As a second normalization we show that we may reduce to the case when

h(∞) = ∞ and g(∞) = ∞.

Let us first check that we can assume h(∞) = ∞. In fact, suppose first that we are dealing with Theorem 3(ii), i.e. that h is a Laurent-polynomial. Then either h(∞) = ∞ or h ∈ k[x^{−1}]. In this last case we just replace x by x^{−1}; observe that we continue to be in the case of Theorem 3(ii) (i.e. the number of terms of f(x^{−1}) = P (x^{−1})/Q(x^{−1}) = x^{deg Q−deg P} (x^{deg P} P (x^{−1})/(x^{deg Q}Q(x^{−1})) is the same as that one for f and the new h is also a Laurent-polynomial). Suppose now that we are dealing with an h satisfying the assumptions for Theorem 4. In this case we replace g, h resp. by g ∘ λ^{−1}, λ ∘ h for a suitable λ ∈ PGL_{2}(k), i.e. such that h(∞) = λ^{−1}(∞). Again, we remain in the case of Theorem 4. Note that the modified h continues not to be of the forbidden shape.

Now, acting on the left of g (and thus also of f) by a suitable element in PGL_{2}(k), we may further achieve that g(∞) = ∞. This normalization is harmless; it does neither modify the degree of g, nor the function h, nor the number of terms in a suitable expression for f: in fact this replaces P, Q by two independent linear forms in them.

In conclusion, from now on we assume that h(∞) = g(∞) = ∞.

Observe also that in proving the theorems we may assume, by a further induction on deg h, that h ∉ k(x^{n}) for any n > 1. The theorems hold for deg h = 1 since then the statements are empty.

For the induction step assume that we have h(x) = h^{∗}(x^{m}) with h^{∗} ∈ k(x) and m ∈ ℕ, m > 1. Then f(x) = g(h(x)) = g(h^{∗}(x^{m})) = f^{∗}(x^{m}) for f^{∗} = g ∘ h^{∗} ∈ k(x). By grouping the terms of P, Q with respect to the residue class modulo m of their degrees, we can write P (x) = P_{0}(x^{m}) + P_{1}(x^{m})x + … + P_{m−1}(x^{m})x^{m−1}, Q(x) = Q_{0}(x^{m}) + Q_{1}(x^{m})x + … + Q_{m−1}(x^{m})x^{m−1} with P_{0}, …, P_{m−1}, Q_{0}, …, Q_{m−1} ∈ k[x]. Since P (x) = f^{∗}(x^{m})Q(x) it follows that P_{i}(x^{m}) = f^{∗}(x^{m})Q_{i}(x^{m}) for i = 0, 1, …, m − 1. Pick a j ∈ {0, 1, …, m − 1} with Q_{j} ≠ 0. Then the equation P_{j}(x) = f^{∗}(x)Q_{j}(x) holds and thus we have

g(h^{∗}(x)) = f^{∗}(x) = \frac{P_{j}(x)}{Q_{j}(x)},

where the terms in P_{j}, Q_{j} on the right form a subset of the terms of P, Q.

Observe that h ∈ k[x, x^{−1}] if and only if h^{∗} ∈ k[x, x^{−1}]. Also, if h satisfies NL and for every equation h(x) = p(q(x)) either q satisfies NL or q(x) = λ(ax^{n} + bx^{−n}) for a λ ∈ PGL_{2}(k), n ∈ ℕ and a, b ∈ k, then the same is true for h^{∗}. In conclusion, if we are in the cases of Theorems 3(ii), 4 for h, then we are in the respective cases for h^{∗}.

Thus each of the statements will follow by induction once we have treated the case h not a rational function in x^{n}, for any n > 1, since g has not changed and moreover h^{∗}(x) cannot be of the forbidden shape for otherwise h(x) would also be.

Next we show that it is sufficient to prove the theorems for h having one of the following two additional properties (which exclude each other):

(H1) We have h ∉ k(x^{n}) for any n > 1 and h is indecomposable.

(H2) We have h ∉ k(x^{n}) for any n > 1, h is decomposable as h(x) = h̃(x + ηx^{−1}) where η ∈ k^{∗}, and moreover every decomposition h(x) = p(q(x)) with deg p, deg q > 1 has q(x) = λ(ax + bx^{−1}) for some a, b ∈ k^{∗} and a λ ∈ PGL_{2}(k).

As to (H2), note that h(x) = h(ηx^{−1}). If we also have h(x) = h(cx^{−1}) for some c ∈ k^{∗}, then h(x) = h((c/η)x), whence c/η is a root of unity, say of exact order n, so h(x) = h^{∗}(x^{n}) for some h^{∗} ∈ k(x). Since this can happen only for n = 1, we see that c = η, so in particular η is uniquely determined.

Note also that since h is not of the forbidden shape, under (H2) necessarily we have deg h̃ > 1.

We prove this reduction to either (H1) or (H2) by induction on deg h. We already noticed that we may suppose h ∉ k(x^{n}), n > 1. Assume now that the theorems are proved in degree lower than deg h, the case deg h = 1 being empty since h is then of the forbidden shape.

First assume that h is indecomposable. Then it satisfies (H1) and we are done if we know the result under this assumption.

Let us now assume that h is decomposable. We separately consider the cases of Theorem 3(ii) and Theorem 4 respectively.

In the case of Theorem 3(ii) we have that h ∈ k[x, x^{−1}] and that h(x) is not of the shape ax^{n} + b + cx^{−n}, a, b, c ∈ k, n ∈ ℕ. Suppose that we have a decomposition h = p ∘ q. By Remark 1.1 we may further assume (on replacing p, q resp. by p ∘ λ^{−1}, λ ∘ q for a suitable λ ∈ PGL_{2}(k)) that q is a Laurent-polynomial.

If in some such decomposition q(x) is not of the forbidden shape, we may replace g, h resp. by g ∘ p, q, and apply induction on deg h. Otherwise (i.e. if we cannot find such a decomposition) in every decomposition h(x) = p(q(x)) with q ∈ k[x, x^{−1}], the inner factor q(x) is necessarily of the forbidden shape (with n = 1). This says that either (H1) or (H2) holds.

Now we come to Theorem 4. Clearly, h is not of the forbidden shape since it satisfies NL. Let h(x) = p(q(x)) be a decomposition of h; then by the assumption for Theorem 4 either q satisfies NL or (again on replacing p, q resp. by p∘λ^{−1}, λ∘q for a suitable λ ∈ PGL_{2}(k)) we have q(x) = ax + bx^{−1}, a, b ∈ k. (Observe in fact that q does not lie in k(x^{n}) for any n > 1 because h does not.) If q satisfies NL, then every decomposition of q has an inner composition factor satisfying NL or being forbidden, because otherwise h would not have this property; so we can argue by induction as before and replace h by q. Sooner or later we arrive at a stage where either h is indecomposable or for every such decomposition of h, we have q(x) of the forbidden shape λ(ax + bx^{−1}), a, b ∈ k, λ ∈ PGL_{2}(k). This means that (H1) or (H2) is satisfied, as wanted.

Altogether it follows that, in proving either Theorem 3(ii) or Theorem 4, we may assume (H1) or (H2) to hold.

Hence, let us assume from now on that h is not of the forbidden shape but that it satisfies either (H1) or (H2).

Furthermore from now on, if we use the symbols h̃ resp. η, we always refer to the special decomposition for h appearing in (H2); especially, η denotes the (unique) constant appearing therein.

To go on, we again shall distinguish two cases, in which we slightly modify the notation of Lemma 4 by changing the sign of e so that it is always positive:

• h(0) = ∞; now we may assume deg h > 2 since otherwise h(x) would be of the forbidden shape. Hence, we may write

h(x) = \frac{p̃(x)}{x^{e}q̃(x)}

with e > 0, p̃, q̃ ∈ k[x] coprime satisfying p̃(0)q̃(0) ≠ 0, d = deg p̃ = deg h > 2, and finally s = d − e − deg q̃ > 0.

• h(0) ≠ ∞; by replacing g, h resp. by g ∘ λ^{−1}, λ ∘ h with λ ∈ PGL_{2}(k) defined by λ(x) = x − h(0), we may assume h(0) = 0 and thus we may write

h(x) = \frac{x^{e}p̃(x)}{q̃(x)}

with e > 0, p̃, q̃ ∈ k[x] coprime satisfying p̃(0)q̃(0) ≠ 0, d = e + deg p̃ = deg h ≥ 2, and

finally s = deg q̃ − d > 0.

(We point out that throughout the proof the symbols p̃, q̃, e, s and d will only be used to refer to the quantities related to h that are introduced above.)

In the first case, namely for e < 0 or equivalently h(0) = ∞, we have the following important lemma that plays a central role in the proofs.

Before stating it, we anticipate a simple remark that shall be useful throughout: If K is a function field over k containing both x, y, with h(x) = h(y), we have

deg_{K}(x) = deg_{K}(y).

In fact, this follows from the general equality deg_{K}(h(u)) = (deg h) deg_{K}(u) for any u ∈ K \ k.

Lemma 5. Assume that h(0) = ∞ and that either (H1) or (H2) holds. Then there exists a conjugate y of x over k(h), different from x and also from ηx^{−1} in case (H2), such that the following holds, on putting K = k(x, y):

(i) if u ∈ k(x) is such that u(x) = u(y), then u ∈ k(h), (ii) for all m, n ∈ ℕ we have

deg_{K}(x^{m}y^{n}) ≥ 0.12 max{m, n} deg_{K}(x).

Moreover, if min{e, s} ≤ 0.75 max{e, s}, then (ii) holds for all m, n ∈ ℤ.

We remark that the precise numerical values here are relatively immaterial; for instance, any larger number in place of 0.75 would lead to a similar statement with 0.12 replaced by some corresponding positive number. Ultimately, this would only result in different numerical constants in the Main Theorem. (We only observe that the larger constant we get in the lower bound (ii), the better numerical constant shall be gotten in the theorems.)

Proof. Let y ≠ x be a conjugate of x over k(h), i.e. we have h(x) = h(y). We define L = {u ∈ k(x) : u(x) = u(y)}. Note that L is a subfield of k(x) and that k(h) ⊆ L ⊆ k(x). Since y is different from x, we have L ≠ k(x). By Lüroth Theorem (cf. [14]) it follows that L = k(z) for a z ∈ k(x); thus we get h(x) = h^{∗}(z) with h^{∗} ∈ k(x). Since L ≠ k(x), we have deg z > 1. Now let us distinguish between (H1) and (H2).

We first consider (H1): In this case h is indecomposable, so since deg z > 1, we have deg h^{∗} = 1, i.e. L = k(h). It clearly follows that requirement (i) is verified for any such y.

Now we turn to (H2): We have h(x) = h̃(q(x)) where q(x) = x + ηx^{−1} and η ≠ 0. Then h(ηx^{−1}) = h(x) (because q(ηx^{−1}) = q(x)). Hence ηx^{−1} is a conjugate of x but we have excluded it too. (In fact recall that working under (H2), we assume y ≠ x and y ≠ ηx^{−1}.)

Observe that since h(x) is not of the forbidden shape, we have deg h̃ > 1, so in particular deg h > 2.

Going back to the above decomposition, we assume first that deg h^{∗} > 1. Then h = h^{∗} ∘ z with deg z > 1 and deg h^{∗} > 1. By (H2) this implies z(x) = λ(ax + bx^{−1}) for some a, b ∈ k^{∗} and λ ∈ PGL_{2}(k). We have already seen (in the discussion below (H2)) that this implies b/a = η. It follows that q(x) = cλ^{−1}(z) for c = 1/a ∈ k and, since L = k(z), we have also q ∈ L, which means q(x) = q(y). But this is a quadratic equation in y which has the two roots y = x and y = ηx^{−1}, and we have excluded from the beginning these possibilities. Therefore this case cannot occur.

Thus we have deg h^{∗} = 1. However, this means that L = k(h) and so (i) is verified in this case too.

It follows that, apart from the choice y = x and possibly y = ηx^{−1} (which may only occur in the case (H2)), any other conjugate y of x over k(h) will automatically satisfy (i). (Note that such a conjugate certainly exists, because we have deg h > 2 since otherwise h(0) = h(∞) = ∞ implies that h(x) is of the forbidden shape.)

We now turn to (ii) and to the additional statement.

For (ii) let z = x^{m}y^{n} with m, n ∈ ℕ. In the sequel we shall show that there exists a suitable choice for the conjugate y (y ≠ x and y ≠ ηx^{−1} in case (H2)) so to satisfy (ii) for all such m, n; this choice shall be made along the proof because we think this leads to better clarity.

However, let us immediately note that if |m − n| ≥ 0.12 max{m, n}, then our inequality is true no matter the choice of the conjugate. In fact, taking into account that deg_{K}(x) = deg_{K}(y), from the properties of the degree we infer that in this case we have

deg_{K}(z) ≥ (max{m, n} − min{m, n}) deg_{K}(x) ≥ 0.12 max{m, n} deg_{K}(x),

proving (ii).

Therefore from now on in the proof of (ii), we shall choose the sought conjugate on assuming that m ≥ 0.88n > 0.

For a given choice of the conjugate y, we also put δ = δ_{y} := [k(x, y) : k(x)], so deg_{K}(x) = deg_{K}(y) = δ.

Finally, we put ε = 0.14. We will show that deg_{K}(z) ≥ εmδ; this then implies that deg_{K}(z) ≥ 0.88ε max{m, n}δ ≥ 0.12 max{m, n}δ and thus the sought inequality.

We count the zeros of z through the zeros of x. Assume that v is a zero of x, i.e. v(x) > 0. We have now two possibilities for y: If v(y) ≥ 0, then v(z) ≥ mv(x) ≥ εmv(x) > 0. If v(y) < 0, then by Lemma 4 (or just by using the equation h(x) = h(y)) we have −sv(y) = ev(x) and therefore

v(z) = (m − n\frac{e}{s}) v(x) = m (\frac{s}{e} − \frac{n}{m}) \frac{e}{s}v(x).

If

(2)  (\frac{s}{e} − \frac{n}{m}) ≥ ε\frac{s}{e}

then we get

deg_{K}(z) = ∑_{v} max{0, v(z)} ≥ ∑_{v(x)>0} max{0, v(z)} ≥ εm ∑_{v(x)>0} v(x) = εmδ,

because δ = deg_{K}(x) = ∑_{v(x)>0} v(x).

The same inequality also follows if we assume that, in the irreducible factor of h(Y) − h(x) defining y, there are at least εδ Puiseux series at x = 0 of type 1. or 3., in the notation of Lemma 4; in fact, in such case we have

deg_{K}(z) ≥ m ∑ v(x) ≥ εmδ,

where the sum is taken over all zeros of x, and corresponding to a Puiseux series at x = 0 of type 1. or 3. in Lemma 4.

So in proving our conclusion let us assume that (2) is not true and that the number of Puiseux series at x = 0 of type 1. and 3. is less than εδ.

Now we count the poles of z through the poles of x. If v(x) < 0, then either v(y) ≤ 0 and therefore v(z) ≤ mv(x) ≤ εmv(x) < 0 or v(y) > 0. In the last case, again by Lemma 4, we have ev(y) = −sv(x), which implies

v(z) = m (\frac{e}{s} − \frac{n}{m}) \frac{s}{s}v(x).

As before we get deg_{K}(z) ≥ εmδ unless

(\frac{e}{s} − \frac{n}{m}) < ε\frac{e}{s}

and unless the number of Puiseux series at x = ∞ of type 1. and 3. is less than εδ.

In the remaining cases we have by the last displayed inequality and by (2) that

(1 − ε)\frac{e}{s} < \frac{n}{m} and (1 − ε)\frac{s}{e} < \frac{n}{m}.

But since m ≥ 0.88n > 0 we get

\frac{max\{e, s\}}{min\{e, s\}} < \frac{n}{(1 − ε)m} ≤ \frac{1}{0.88(1 − ε)} ≤ \frac{1}{0.75}.

It follows that

(3)  min{e, s} > 0.75 max{e, s}.

Moreover, we also have that the number of Puiseux series of type 1. and 3. at x = 0 and at x = ∞ is less than εδ in every irreducible factor defining a y ≠ x, ηx^{−1} over k(h).

The number of Puiseux series at x = 0 of type 1. and 3. in the Puiseux factorisation of the numerator of (h(Y) − h(x))/(Y − x) is e + deg q̃ − 1 = d − s − 1, which follows from Lemma 4. (The subtraction of 1 comes from the factor Y − x which clearly contains exactly one series of type 1. or 3. at x = 0, whereas the factor xY − η, in case (H2), has no series of this type at x = 0 at all.)

Since we are in the case where we assume that in each irreducible factor, of degree δ, of the numerator of (h(Y) − h(x))/(Y − x) there are at most εδ such series, by summing up the contributions from each factor we conclude that d−s−1 < ε(d−1) and (1−ε)d+ε−1 < s. From (3) we get 0.75s < e. Hence, we obtain d − deg q̃ = e + s > 1.75s > 1.75(1 − ε)d − 1.75(1 − ε) and therefore 0 ≤ deg q̃ < (−0.75+1.75ε)d+1.75(1−ε) ≤ 3(−0.75+1.75ε)+1.75(1−ε) = −0.01 < 0. (In fact we have used that by our choice ε = 0.14 we have −0.75 + 1.75ε < 0 and that d ≥ 3.)

This contradiction implies that in at least one irreducible factor the number of Puiseux series at x = 0 of type 1. and 3. is ≥ εδ and by choosing y as a root corresponding to such a factor we conclude the sought inequality. (We could have also argued with the number of Puiseux series at x = ∞ of type 1. and 3. and on using that s > 0.75e.)

Finally, we prove the remaining part of the statement. We have already seen that, if min{e, s} ≤ 0.75 max{e, s}, then we get the sought lower bound for deg_{K}(z) for all positive exponents independently of the choice of the irreducible factor from which we take y (excluding, as always, y = x and y = ηx^{−1} in case (H2)). Observe also that the case of both exponents negative follows trivially from the positive case since deg_{K}(z) = deg_{K}(1/z).

Now we consider the exponents of opposite sign. Let z = x^{m}y^{n} with m, n ∈ ℤ and mn < 0. As above, if ||m| − |n|| ≥ 0.12 max{|m|, |n|}, then the sought inequality holds independently of the choice of the conjugate.

Therefore, and since deg_{K}(z) = deg_{K}(1/z), we may just consider the cases z = x^{m}y^{−n} with m ≥ 0.88n > 0. We put ε = 0.14 as before. We will again show that deg_{K}(z) ≥ εmδ from which it then follows deg_{K}(z) ≥ 0.88ε max{m, n}δ ≥ 0.12 max{m, n}δ and so the sought inequality.

As above, we count the zeros of z through the zeros of x. Let v be such a zero of x. If v(y) ≤ 0, then v(z) ≥ mv(x). Therefore, if there are ≥ εδ Puiseux series at x = 0 of type 2. or 3. in at least one irreducible factor, then we can choose it to define y and the sought inequality follows. Similarly, arguing with the poles of x, it suffices that at least one of the factors contains ≥ εδ Puiseux series at x = ∞ of type 2. or 3. since then we again get the sought inequality for the corresponding y.

We now show that the assumption min{e, s} ≤ 0.75 max{e, s} implies the existence of such a factor.

Assume that 0.75s ≥ e and that at x = 0 all factors different from Y − x, xY − η have at most εδ Puiseux series at x = 0 of type 2. or 3. The arguments under (H1) and (H2) are slightly different; we first consider (H2): Then d − e − 1 = s + deg q̃ − 1 < ε(d − 1) (now the subtraction of 1 comes from the factor xY − η which clearly contains exactly one series of type 2. or 3. at x = 0, whereas the factor Y − x has no series of this type at x = 0 at all). It follows that d − deg q̃ = e + s ≤ 1.75s < 1.75ε(d − 1) − 1.75 deg q̃ + 1.75 and therefore 0 ≤ 0.75 deg q̃ < (1.75ε−1)d+1.75(1−ε) ≤ 3(1.75ε−1)+1.75(1−ε) = 3.5ε−1.25 = −0.76 < 0, a contradiction (by our choice ε = 0.14). In the case (H1) the assumption that at x = 0 all factors different from Y − x (now there is no factor xY − η) have at most εδ Puiseux series of type 2. or 3. implies d − e = s + deg q̃ < εd, and then the contradiction follows from 0 ≤ 0.75 deg q̃ < (1.75ε − 1)d < 0 by our choice of ε.

If 0.75e ≥ s one can argue similarly with the Puiseux series at x = ∞ by using that ε = 0.14. Thus the proof of the statement is complete. □

In the second case, namely e > 0 or equivalently h(0) = 0, the situation is simpler and we need less. Here we have the following

Lemma 6. Assume that h(0) = 0 and that either (H1) or (H2) holds. Then there exists a conjugate y of x over k(h), different from x and also from ηx^{−1} in case (H2), such that the following holds:

(i) if u(x) = u(y), u ∈ k(x), then u ∈ k(h), (ii) for all m, n ∈ ℕ we have

deg_{K}(x^{m}y^{n}) ≥ max{m, n} deg_{K}(x),

where K = k(x, y).

Proof. For (i) we can argue as in the previous lemma; just observe that the alternative (H2) is clearly excluded since we have h(∞) = ∞ and h(0) = 0, hence h(x) cannot be of the shape h̃(x + ηx^{−1}) with η ≠ 0. It follows that for every conjugate y of x over k(h), that is different from x, condition (i) will be satisfied. Let y be such a conjugate and define δ = [k(x, y) : k(x)].

Now we prove (ii). Let z = x^{m}y^{n}, m, n ∈ ℕ. We may assume that m ≥ n ≥ 0 since otherwise we just have the change the role of x and y (observe that here we have already chosen the conjugate y) in the arguments below. As in the proof of Lemma 5 we count the zeros of z by going through the zeros of x. Assume that v(x) > 0. Clearly, v(y) < 0 is impossible and so we have v(y) ≥ 0. In this case we get v(z) ≥ mv(x). It immediately follows that

deg_{K}(z) ≥ mδ

independently of the factor from which we choose y. This already proves the statement. □

Note that in both cases for h (that is for both possible values for h(0)) we have, for every conjugate y of x over k(h), that deg_{K}(x) = deg_{K}(y) ≤ d − 1 (as follows immediately from h(x) = h(y)).

Further strategy: Let us emphasize that the lower bounds obtained in the last two lemmas work only on additional conditions, namely concerning the ratio s/e or the signs of m, n. In the non-Laurent case and for h(0) = 0 there are now different devices which prevent us from the need of more, but in the remaining situations, i.e. in the Laurent case with h(0) = ∞, we need a bound which does not depend on these issues: Therefore, to overcome this difficulty, we start there by choosing a factor (or equivalently a conjugate y) so that Lemma 5(i) holds. Further, if s/e is not near to 1 we can choose it so that the bound holds for all m, n, whereas if s/e is near to 1, we can only say that the bound holds for non-negative m, n for an appropriate choice of the factor. Hence, no difficulty arises if s/e is not near to 1. In the case when s/e is near to 1, we could first choose the factor so that the bound holds for non-negative m, n, but then the factor is fixed and we cannot change it anymore. This means that if we want the estimate for all m, n ∈ ℤ we need a priori more information on the possible factors and this is the place where the result of Müller [11] will play an essential role (see Subsection 5.2 for the precise statement and the detailed proof of this).

After these remarks we are now ready to prove Theorem 3(ii) and Theorem 4, which we will do in the following two sections. Before we start we summarise, for the readers convenience, some points of the proof.

In the first place, we are arguing by induction on ℓ and, for given ℓ, also by a second induction on deg h.

Further, we recall the normalizations obtained so far: We may assume that P, Q are not both divisible by x, that g(∞) = h(∞) = ∞, that h(0) ∈ {0, ∞} and that h satisfies (H1) or (H2). (This last reduction has been shown in Section 3, before Lemma 5.)

4. The non-Laurent case for rational functions

In this section we shall give the proof of Theorem 4. Let f(x) = g(h(x)) with the notation and normalizations just recalled.

Note that the assumption that h satisfies NL implies that deg q̃ ≥ 1 and deg p̃ ≥ 1, where we refer to the displayed equations h(x) = x^{±e}p̃(x)/q̃(x) just before Lemma 5. (E.g., if p̃ would be constant, 1/h would be a Laurent-polynomial.)

As before, we shall consider two cases depending on whether h(0) = ∞ or h(0) = 0.

4.1. Proof of Theorem 4 in the case h(0) = ∞. First we shall use the lacunarity of f to partition the set Σ of exponents appearing in P, Q into two groups with a controlled gap. We set

Σ = {0 = m_{1} < m_{2} < ⋯ < m_{ℓ}}

for the set of exponents appearing in P, Q (ordered by size); especially we have m_{ℓ} ≥ deg f (with equality if P, Q are coprime). Observe that |Σ| = ℓ ≥ 2. We partition (0, m_{ℓ}] into infinitely many intervals (m_{ℓ}/3, m_{ℓ}], (m_{ℓ}/9, m_{ℓ}/3], …. It follows that at least one interval, say (m_{ℓ}/3^{l}, m_{ℓ}/3^{l−1}] with 2 ≤ l ≤ ℓ, is disjoint from Σ. We set

Σ_{L} = {m ∈ Σ : m > m_{ℓ}/3^{l−1}},
Σ_{S} = {m ∈ Σ : m ≤ m_{ℓ}/3^{l}}.

So Σ = Σ_{L} ∪ Σ_{S} and any difference m′ − m, m′ ∈ Σ_{L}, m ∈ Σ_{S} satisfies

m′ − m > (2/3^{l})m_{ℓ}.

Moreover, the difference between any two elements in Σ_{S} is at most m_{ℓ}/3^{l}.

Let y be the conjugate of x over k(h) from Lemma 5. From the equation f(x) = g(h) ∈ k(h) we deduce f(x) = f(y). Writing f(x) = P (x)/Q(x) we get the equation

P (x)Q(y) − P (y)Q(x) = 0.

This gives a relation involving terms of the form x^{m}y^{n} with m, n ∈ Σ and with at most ℓ^{2} − 1 such summands. (Recall in fact that f(∞) = ∞, so m_{ℓ} appears only in P and this implies that x^{m_{ℓ}}y^{m_{ℓ}} does not occur in the relation above.)

We say that a term of the said form is of type LL if (m, n) ∈ Σ_{L} × Σ_{L}; similarly terms of type SL, LS and SS are defined.

We partition the sum on the left of this equation into minimal vanishing subsums, where no further proper subsum vanishes. (This partition may be possibly done in several ways; we can choose freely one of them.) Observe that in order to apply Lemma 2 to one of these minimal vanishing subsums we first have to normalize it, on dividing by one of the terms, so that the constant term 1 appears in the sum.

Let us assume that there is such a minimal vanishing subsum containing a term of type LL and another one of type SS. The ratio z of these terms is of shape x^{m}y^{n} where m, n ∈ Σ_{L} − Σ_{S}. So m and n are > (2/3^{l})m_{ℓ}. An application of Lemma 5 leads to

deg_{K}(z) ≥ \frac{2ε}{3^{l}}m_{ℓ}δ ≥ \frac{2ε}{3^{ℓ}}m_{ℓ}δ,

where K = k(x, y), δ = deg_{K}(x) = deg_{K}(y) = [K : k(x)] and ε = 0.12. Then, by Lemma 2, we get

\frac{2ε}{3^{ℓ}}m_{ℓ}δ ≤ \binom{ℓ^{2} − 2}{2}(2𝔤 − 2 + |S|),

where 𝔤 is the genus of k(x, y). We have

𝔤 ≤ (δ − 1)^{2}

(where we use that δ = deg_{K}(x) = deg_{K}(y) and therefore the bound follows from Castelnuovo’s inequality; cf. [14, III.10.3 Theorem]).

Further, the set S consisting of the zeros and poles of x and y in K satisfies |S| ≤ 2(deg_{K}(x)+ deg_{K}(y)) ≤ 4δ and so 2𝔤 − 2 + |S| ≤ 2(δ − 1)^{2} − 2 + 4δ = 2δ^{2}. Therefore we get

m_{ℓ} ≤ \frac{3^{ℓ}}{2ε}\binom{ℓ^{2} − 2}{2}2δ ≤ \frac{3^{ℓ}}{ε} \binom{ℓ^{2} − 2}{2}(d − 1) ≤ (267 · 5^{ℓ})(d − 1),

where we have used the inequality

(4)  \binom{ℓ^{2} − 2}{2} = \frac{(ℓ^{2} − 2)(ℓ^{2} − 3)}{2} ≤ 32 · (\frac{5}{3})^{ℓ} .

(Here the constant 32 is obtained by bringing the exponential term to the left and calculating the maximal values of the resulting function in ℓ by differentiation; this gives a polynomial equation of degree 4 that has its positive roots at 1.5717... and at 8.1381....)

If there is a minimal vanishing subsum that involves both terms of type LS and of type SS, then the ratio z is of the shape z = x^{m}y^{n} with m ≥ (2/3^{l})m_{ℓ} and |n| ≤ m_{ℓ}/3^{l}. Hence,

deg_{K}(z) ≥ |m| deg_{K}(x) − |n| deg_{K}(y) = (|m| − |n|)δ ≥ \frac{1}{3^{ℓ}} m_{ℓ}δ

leading even to a better bound than before. We can argue similarly for subsums involving terms of type SL and SS.

We may therefore assume that each minimal vanishing subsum involves either just terms of the type SS or the rest (i.e. (Σ_{L} × Σ_{S}) ∪ (Σ_{S} × Σ_{L}) ∪ (Σ_{L} × Σ_{L})). Let us then write

P (x) = a(x) + A(x)
Q(x) = b(x) + B(x)

where the capitals involve precisely those exponents which lie in Σ_{L}. The full relation is

a(x)b(y) − a(y)b(x) + A(x)B(y) − A(y)B(x)
+A(x)b(y) − A(y)b(x) + a(x)B(y) − a(y)B(x) = 0

and the above shows that we may assume

a(x)b(y) = a(y)b(x).

Now we show that we can also reduce to the assumption a(x)b(x) ≠ 0. In the first place, a(x) ≠ 0 since a(x) involves a constant term; this follows from P (0) ≠ 0, which in turn is implied by f(0) = g(h(0)) = g(∞) = ∞. (Recall also that, although P, Q are not supposed to be coprime, we are working under the harmless normalization that they do not both vanish at 0.)

For the reduction to the crucial fact that b(x) ≠ 0 we will use that we are in the non-Laurent case (in fact we only need deg q̃ ≥ 1, which is implied by NL). We start by writing

f(x) = \frac{P (x)}{Q(x)} = \frac{P (x)}{x^{E}Q̃(x)}

with E > 0, P (0)Q̃(0) ≠ 0. (Observe again that we have f(0) = g(h(0)) = g(∞) = ∞.) Moreover, P (x) and x^{E}Q̃(x) have ℓ − 1 non-constant terms altogether. We write

g(x) = ax^{ord_{∞}(g)} + …

up to terms of smaller order at x = ∞, where a ∈ k^{∗}. Recall that h satisfies NL, so q̃ is not constant and we may pick a root θ ∈ k^{∗} of q̃, say of multiplicity μ ≥ 1. Then at x = θ we have

g(h(x)) = \frac{b}{(x − θ)^{μ ord_{∞}(g)}} + …

for some b ∈ k^{∗}. This implies that Q̃(x) has θ as a root with multiplicity ≥ μ ord_{∞}(g). So with Lemma 1 we get ord_{∞}(g) ≤ μ ord_{∞}(g) ≤ ord_{θ}(Q̃) ≤ ℓ − 1. It follows that

(5)  E = ord_{0}(f) = e ord_{∞}(g) ≤ (ℓ − 1)e ≤ (ℓ − 1)(d − 1)

and thus Q(x) involves the term x^{E} with E ≤ (ℓ − 1)(d − 1).

If E ∈ Σ_{L}, then

m_{ℓ} ≤ (ℓ − 1)3^{ℓ−1}(d − 1) ≤ 5^{ℓ}(d − 1)

and we are done (here we e.g. use that the real function \sqrt[x]{x} takes its maximum at x = exp(1) = 2.7182...).

Hence, we may assume that E ∈ Σ_{S}, implying b(x) ≠ 0. Now this gives

\frac{a(x)}{b(x)} = \frac{a(y)}{b(y)}

and by the property of y expressed in Lemma 5(i) we deduce

\frac{a(x)}{b(x)} = φ(h)

where φ ∈ k(x). Let x^{M} be the largest power of x dividing both A(x) and B(x). Write A(x) = x^{M} Ã(x), B(x) = x^{M} B̃(x). Since M ∈ Σ_{L}, we note

(6)  M > m_{ℓ}/3^{l−1}.

Furthermore, we have

f(x) = \frac{a(x) + x^{M} Ã(x)}{b(x) + x^{M} B̃(x)} = g(h).

Define ψ(x) := g(x) − φ(x), so

ψ(h) = g(h) − φ(h) = f(x) − \frac{a(x)}{b(x)} = x^{M} \frac{Ã(x)b(x) − a(x)B̃(x)}{b(x)Q(x)}.

Now, by a similar Hajós-argument as before, we first have

v_{0}(ψ(h)) ≥ M − v_{0}(b) − v_{0}(Q) ≥ M − 2E ≥ M − 2(ℓ − 1)(d − 1),

where we have used (5) again. We may assume that M − 2(ℓ − 1)(d − 1) > 0 since otherwise

m_{ℓ} < 2(ℓ − 1)3^{ℓ−1}(d − 1) ≤ (2 · 5^{ℓ})(d − 1)

and we are done. It follows that v_{0}(ψ(h)) = ord_{0}(h)v_{∞}(ψ) = ev_{∞}(ψ) > 0, and therefore v_{∞}(ψ) > 0 since we have e > 0; especially, we get ψ(∞) = 0 and

(7)  e v_{∞}(ψ) = v_{0}(ψ(h)) ≥ M − 2(ℓ − 1)(d − 1).

Now pick as before a θ ∈ k^{∗} with q̃(θ) = 0, so h(θ) = ∞ and

v_{θ}(ψ(h)) = v_{θ}(q̃) v_{∞}(ψ) > 0.

Therefore Ã(x)b(x) − a(x)B̃(x) vanishes at θ of order at least v_{∞}(ψ) > 0.

Now, if Ã(x)b(x) ≠ a(x)B̃(x), the difference has ≤ ℓ^{2} terms (in fact every term has a degree of the form m + m′ − M with m, m′ ∈ Σ). So by Lemma 1 again

v_{∞}(ψ) ≤ v_{θ}(Ãb − aB̃) ≤ ℓ^{2},

whence by (7) it follows M ≤ ℓ^{2}e + 2(ℓ − 1)(d − 1) ≤ ℓ(ℓ + 2)(d − 1) and by using (6) we get

m_{ℓ} < ℓ(ℓ + 2)3^{ℓ−1}(d − 1) ≤ (2 · 5^{ℓ})(d − 1)

and we are done. (The second inequality is obtained as in (4).)

On the other hand, suppose Ã(x)b(x) = a(x)B̃(x). Since Ã(x) ≠ 0 (otherwise Σ_{L} would be empty), we get B̃(x) ≠ 0 and so

\frac{Ã(x)}{B̃(x)} = \frac{a(x)}{b(x)} = φ(h) = f(x)

and we have expressed f with a proper subset of Σ. In this case we can argue by induction on ℓ, the case ℓ = 2 being trivial (e.g. we can repeat all arguments of this proof and observe that b(x) ≠ 0 is impossible since then Σ contains at least the three elements 0, E, m_{ℓ}). Therefore deg φ ≤ 267 · 5^{ℓ−1} and thus deg f = deg φ · d ≤ (267 · 5^{ℓ})(d − 1).

Summing up we have proved that in all cases

deg f ≤ m_{ℓ} ≤ (267 · 5^{ℓ})(d − 1),

which is the sought inequality. □

4.2. Proof of Theorem 4 in the case h(0) = 0. Recall that both p̃, q̃ are non-constant; in fact here we will only use that deg p̃ ≥ 1. We start by observing that we may also assume, on subtracting a constant from both g, f, that

g(0) ∈ {0, ∞}.

This is like saying that v_{0}(g) ≠ 0 and it implies f(0) = g(h(0)) = g(0) ∈ {0, ∞}.

As before we partition the set Σ consisting of the terms contained in the numerator and denominator of f into the two disjoint sets Σ_{S} and Σ_{L}. We investigate the equation f(x)−f(y) = 0, where y is the conjugate obtained in Lemma 6, and partition the terms in P (x)Q(y)−P (y)Q(x) into minimal sets with vanishing sum.

For each monomial z = x^{m}y^{n} that appears as a ratio of a monomial of type LL, or LS, or SL and a monomial of type SS in a minimal vanishing subsum, we get

deg_{K}(z) ≥ \frac{1}{3^{l}} m_{ℓ}δ ≥ \frac{1}{3^{ℓ}} m_{ℓ}δ,

where δ = deg_{K}(x). Thus, by Lemma 2,

\frac{1}{3^{ℓ}} m_{ℓ}δ ≤ \binom{ℓ^{2} − 2}{2}(2𝔤 − 2 + |S|).

We have |S| ≤ 4δ and thus 2𝔤 − 2 + |S| ≤ 2(δ − 1)^{2} − 2 + 4δ = 2δ^{2}. Therefore we get

m_{ℓ} ≤ 3^{ℓ}\binom{ℓ^{2} − 2}{2}2δ ≤ (64 · 5^{ℓ})(d − 1)

by using the inequality (4).

Otherwise we have again that a(x)b(y) − a(y)b(x) = 0. Since g(0) ∈ {0, ∞}, we get

g(x) = cx^{v_{0}(g)} + …,

where c ∈ k^{∗}. Now like before we write

f(x) = \frac{P (x)}{Q(x)} = x^{E} \frac{P̃(x)}{Q̃(x)}

with E ∈ ℤ\{0}, P̃(0)Q̃(0) ≠ 0. (Observe that we have f(0) ∈ {0, ∞}.) Moreover, x^{max{0,E}}P̃(x) and x^{− min{0,E}}Q̃(x) have ℓ − 1 non-constant terms altogether. Since p̃ is not constant, we let θ ∈ k^{∗} be a root of p̃ of multiplicity μ ≥ 1. We have v_{θ}(g(h)) = μv_{0}(g) and thus either P̃(x) or Q̃(x) has θ as a root with multiplicity ≥ μ|v_{0}(g)|. By Lemma 1 we get μ|v_{0}(g)| ≤ ℓ − 1. Finally, we obtain

|E| = e|v_{0}(g)| ≤ e(ℓ − 1) ≤ (ℓ − 1)(d − 1).

We may assume that |E| ∈ Σ_{S} (otherwise we are done), whence both a(x) and b(x) are nonzero since now one of the two contains the constant term and the other one x^{|E|}, and thus we infer that

\frac{a(x)}{b(x)} = φ(h)

and

ψ(h) = f(x) − φ(h) = x^{M} \frac{Ã(x)b(x) − a(x)B̃(x)}{b(x)Q(x)},

where x^{M} is the largest power of x dividing both A(x) and B(x). Especially, we have M ∈ Σ_{L}, i.e. M > m_{ℓ}/3^{l−1} (that is (6) in the previous case). Now the factor x^{|E|} may appear in the numerator or the denominator of the second factor. In any case

v_{0}(ψ(h)) ≥ M − 2|E| ≥ M − 2(ℓ − 1)(d − 1).

We may again assume that M − 2(ℓ − 1)(d − 1) > 0 (otherwise we get the sought inequality) and thus v_{0}(ψ) > 0; especially, we have ψ(0) = 0. Hence, we get

ev_{0}(ψ) = v_{0}(ψ(h)) ≥ M − 2(ℓ − 1)(d − 1).

Again if p̃(θ) = 0 for θ ∈ k^{∗}, then h(θ) = 0 and this gives

v_{θ}(ψ(h)) = ord_{θ}(p̃)v_{0}(ψ) ≥ v_{0}(ψ) ≥ \frac{1}{d − 1}(M − 2(ℓ − 1)(d − 1)).

If Ã(x)b(x) − a(x)B̃(x) ≠ 0, then by Lemma 1 the left hand side of the above inequality is ≤ ord_{θ}(Ãb − aB̃) ≤ ℓ^{2} and we get the sought bound as before. Otherwise, the result follows by induction on ℓ.

Putting all the upper bounds for m_{ℓ} together we get

deg f ≤ m_{ℓ} ≤ (267 · 5^{ℓ})(d − 1),

which is what we want. □

5. The Laurent case for rational functions

In this section we give the proof of Theorem 3. We start with the case when f(x) = P (x)/Q(x) is in reduced form, i.e. with P, Q ∈ k[x] coprime; here we do not need any of the normalizations from Section 3.

5.1. Proof of Theorem 3 for reduced f. We write g(x) = g_{1}(x)/g_{2}(x) with g_{1}, g_{2} ∈ k[x] coprime and thus we get

\frac{P (x)}{Q(x)} = \frac{g_{1}(h(x))}{g_{2}(h(x))}.

Since the quotient on the left side of the equation is reduced and g_{1}, g_{2} are coprime, it follows that P (x)P_{1}(x) = g_{1}(h(x)), Q(x)Q_{1}(x) = g_{2}(h(x)) with P_{1}, Q_{1} units in k[x, x^{−1}], i.e. of the form x^{±n} with n ∈ ℕ. Now since P P_{1} has the same number of terms as P and QQ_{1} has the same number of terms as Q, the result follows at once from [20, Theorem 2*]. □

We are left with the general case in which P, Q may be not coprime.

Now we argue by induction on ℓ and we remind the reader that, by a further induction on deg h, we have reduced to assume that either (H1) or (H2) holds. (We recall that this reduction has been shown in Section 3, before Lemma 5.)

Let f(x) = g(h(x)) with h ∈ k[x, x^{−1}] and with h(x) not of the shape ax+b+cx^{−1}, a, b, c ∈ k, where we again use the notation and normalizations described in Section 3. Therefore, we may now write

h(x) = x^{±e}p̃(x), p̃(0) ≠ 0,

and we again have to consider the cases h(0) = ∞ or h(0) = 0 (i.e. minus or plus sign respectively). Observe that deg p̃ ≥ 1 since otherwise h would be of the forbidden shape.

5.2. Proof of Theorem 3 in the case h(0) = ∞. We start by proving that there is a conjugate y of x over k(h) satisfying (i) of Lemma 5 and

(8)  deg_{K}(z) ≥ \frac{1}{63} max\{|m|, |n|\} deg_{K}(x)

for all z = x^{m}y^{n} with m, n ∈ ℤ. We shall set δ = deg_{K}(x) = deg_{K}(y) as usual.

We first show this property whenever y ≠ x, ηx^{−1} and deg_{K}(y) ≤ 63. Note that this last inequality holds, in particular, for all h with deg h ≤ 64.

Observe that for every conjugate y of x over k(h) different from both x and ηx^{−1}, condition (i) is fulfilled; this follows as in the proof of Lemma 5. Since deg h > 2 such conjugate certainly exists and we go on to show that it necessarily satisfies also (8) for the relevant values of m, n.

To show (8), note that the divisors of x, y (with respect to the function field K = k(x, y)) are not proportional (otherwise xy^{±1} ∈ k^{∗}, but in the opening arguments for Lemma 5 we have already seen that only Y − x, xY − η would be admissible, and we have excluded these possibilities).

Assume first that m ≥ n ≥ 0. If there is a valuation v with v(x) > 0 and v(y) ≥ 0, then v(z) = mv(x) + nv(y) ≥ m ≥ m deg_{K}(x)/63 and we are done.

Otherwise for every v with v(x) > 0 we have v(y) < 0; it follows that there is one such v with v(x) ≠ |v(y)| (here we use that the divisors are not proportional), and since deg_{K}(x) = deg_{K}(y), there exists a v with v(x) > |v(y)| ≥ 1. Thus v(z) = mv(x) − n|v(y)| ≥ m + (m − n)|v(y)| ≥ m. Now assume that m ≥ −n > 0. If there is a v with v(x) > 0, v(y) ≤ 0, then we get v(z) ≥ m; otherwise we have v(y) > 0 for all v with v(x) > 0 and as above there is such a v with v(x) > v(y), which then implies v(z) = m + (m + n)v(y) ≥ m. It follows that

deg_{K}(z) ≥ max\{|m|, |n|\} ≥ \frac{1}{63} max\{|m|, |n|\}δ.

The key point in this argument is that deg h is absolutely bounded, and hence the same holds for δ ≤ deg h − 1. So we do not have to worry about the dependence of the lower bound on δ. In turn, this implies that we have a lower bound for deg_{K}(z) without using Lemma 5.

From now on we therefore assume that δ ≥ 64.

Now if 0.75 max{e, s} ≥ min{e, s}, the sought inequality (8) follows immediately from the additional statement in Lemma 5. We therefore assume that 0.75 max{e, s} < min{e, s} or equivalently 0.75e < s < e/0.75.

If h satisfies (H1), then h is indecomposable and we apply Müller’s theorem (cf. Lemma 3). Clearly, the sporadic cases are covered (by the condition δ ≥ 64). Thus let us now only look at infinite families and assume that δ ≥ 64.

If we are in case (i) of Lemma 3, i.e. if we have G ⊇ A_{d}, then (h(Y)−h(x))/(Y −x) is absolutely irreducible and thus we take it as the defining polynomial for y. We have δ = d − 1 and clearly y ≠ x, ηx^{−1}, which implies (i) of Lemma 5. Here it follows, on using s = d − e > d − (s/0.75) and e = d − s > d − (e/0.75) (observe that we have deg q̃ = 0 and therefore there are no Puiseux series of type 3. in Lemma 4), that there are at least

s > \frac{d}{2.34} ≥ \frac{δ}{62}

Puiseux series at x = 0 of type 2. and at least

e − 1 > \frac{d}{2.34} − 1 ≥ \frac{δ}{62}

Puiseux series at x = 0 of type 1. in Lemma 4 in the factor defining y. Then the sought lower bound for deg_{K}(z) follows by the same arguments as used in the proof of Lemma 5: Let z = x^{m}y^{n} with m, n ∈ ℤ. If ||m|−|n|| ≥ (1/63) max{|m|, |n|}, then we are done by properties of the degree, and if this is not the case, then it is enough to consider z = x^{m}y^{n} with m ∈ ℕ, n ∈ ℤ and m ≥ (62/63)|n| > 0. Since we have already proved that there are ≥ (1/62)δ Puiseux series at x = 0 of type 1. and 2. in Lemma 4, it follows that we get deg_{K}(z) ≥ (1/62)mδ ≥ (1/63) max{m, |n|}δ. (This is obtained, as before, by counting the zeros of z by going through the zeros of x and using that in both cases n ≥ 0 resp. n < 0 there are ≥ (1/62)δ places that contribute at least m to the lower bound.) So we are done again.

Otherwise we are in case (ii) of Lemma 3. It follows that d = m^{2} with m ≥ 8 and G = (S_{m} × S_{m}) ⋊ ℤ/(2). The orders of the distinct orbits induced by the action of G (that are the degrees in Y of the irreducible factors of h(Y) − h(x)) are (m − 1)^{2}, 2m − 2 and 1. Let y be defined by the factor corresponding to (m − 1)^{2}. Clearly, (i) of Lemma 5 is satisfied. Since we are assuming that 0.75e < s < e/0.75, which implies s > m^{2}/2.34 and e > m^{2}/2.34, similarly to the above we get that there are at least

e − 2m + 1 > \frac{m^{2}}{2.34} − 2m + 1 ≥ \frac{1}{62}(m − 1)^{2}

Puiseux series at x = 0 of type 1. and at least

s − 2m + 1 > \frac{1}{62}(m − 1)^{2}

Puiseux series at x = 0 of type 2. in the defining equation of y (with δ = (m − 1)^{2}). This again implies the sought lower bound for deg_{K}(z).

Finally assume that h satisfies (H2), so h(x) = h̃(x + ηx^{−1}), η ∈ k^{∗}. After rescaling x we may assume that η = 1, i.e. that h(x) = h̃(x + x^{−1}). Observe that d = 2 deg h̃; we set n := deg h̃ = d/2 ≥ 32.

Since h is a Laurent-polynomial, it follows that h̃ ∈ k[x] (otherwise h would have a pole outside {0, ∞}) and since every decomposition h = p∘q has q(x) = λ(ax+bx^{−1}) for a, b ∈ k, λ ∈ PGL_{2}(k), it also follows that h̃ is indecomposable.

So we have (e.g. by [13, Theorem 10, p. 52]) three cases: Either h̃ is related to a cyclic or a Chebyshev polynomial (i.e. h(x) = c_{1}(x + x^{−1} + c_{2})^{n} + c_{3} or h(x) = c_{1}T_{n}(c_{2}(x + x^{−1}) + c_{3}) + c_{4}, c_{1}, c_{2}, c_{3}, c_{4} ∈ k), or H(U, V) := (h̃(U) − h̃(V))/(U − V) is absolutely irreducible.

In the first two cases H(U, V) splits into factors of degree 1 or, by [13, Lemma 1, p. 52], into factors of degree 2 and therefore δ ≤ 4. Thus we can forget about these cases since we are assuming here that δ ≥ 64.

Hence, in the sequel we assume that we fall into the third case, i.e. that H is absolutely irreducible. We now apply a result analogous to Müller’s quoted one, but for the simpler case of polynomials (instead of Laurent-polynomials); it appears in Müller’s paper [11, Theorem 4.9, p. 63] (but is proved elsewhere). We may already forget about the sporadic cases and thus consider only the infinite families (given at the beginning of the cited statement). The first cases (a), (b) correspond to the cyclic and Chebyshev case (in fact now the Galois group structure says that H is not absolutely irreducible). Hence these cases have already been taken into account.

Therefore we concentrate on case (c), namely we assume that the Galois group G of the equation h̃(U) − h̃ over k(h̃) is either A_{n} or S_{n} (remember that now n = deg h̃); recall moreover that n ≥ 32. We denote by L the splitting field of this equation over k(h̃). We let u, v ∈ L be distinct solutions to this equation, so u ≠ v and h̃ = h̃(u) = h̃(v).

We have the field inclusions k(h̃) ⊆ k(u) ⊆ k(u, v) ⊆ L. The Galois group of L/k(u) corresponds to the stabilizer in G of 1, say, whereas the Galois group of L/k(u, v) corresponds to the stabilizer of both 1 and 2. These two subgroups in turn correspond to natural inclusions, either A_{n−2} ⊆ A_{n−1} or S_{n−2} ⊆ S_{n−1} (depending on whether G is A_{n} or S_{n}).

Suppose now that there is a field F, quadratic over k(u) and with k(u) ⊆ F ⊆ k(u, v). This would correspond to a group Γ of index 2 either in A_{n−1} or in S_{n−1}, and with either A_{n−2} ⊆ Γ ⊆ A_{n−1} or S_{n−2} ⊆ Γ ⊆ S_{n−1} in the respective situations for G. Say that G = A_{n}: since n ≥ 32, A_{n−1} is simple, so we cannot have [A_{n−1} : Γ] = 2. Similarly if G = S_{n}: we would have Γ = A_{n−1}, contrary to S_{n−2} ⊆ Γ. We conclude that such a quadratic extension does not exist.

Let us now define x as a solution of X +X^{−1} = u, in an algebraic closure of k(u) containing L; so x + x^{−1} = u. The other solution is x^{−1}, so k(x) is independent of the solution, and k(x)/k(u) is quadratic. Hence, k(x) is not included in k(u, v), and therefore x has degree 2 over k(u, v).

Similarly, we may define y as a solution of Y + Y^{−1} = v in the same algebraic closure, and then y has also degree 2 over k(u, v).

Note that h̃(u) = h(x), h̃(v) = h(y), and y is a conjugate of x over k(h).

Now, k(x, y) has either degree 4 or degree 2 over k(u, v). We get the tower of fields k(u) ⊆ k(x) ⊆ k(x, y) = K given by the defining equations x + x^{−1} = u and h(x) − h(y) = 0 with the respective degrees [k(x) : k(u)] = 2, [K : k(x)] = δ = deg_{K}(x). Also we have k(u) ⊆ k(u, v) ⊆ K; the first extension is given by H(u, v) = 0 and has therefore degree [k(u, v) : k(u)] equal to n − 1 = d/2 − 1 and the second is given by x + x^{−1} = u, y + y^{−1} = v.

If [K : k(u, v)] = 4, then a comparison of the degree [K : k(u)] obtained from the two towers gives δ = d − 2. Hence the numerator of

\frac{h(Y) − h(X)}{(Y − X)(Y X − 1)}

is absolutely irreducible and is therefore the only choice as defining polynomial for y. As before we can use 0.75e < s < e/0.75, and the fact that there are s − 1 Puiseux series of type 2. and e−1 Puiseux series of type 1. at x = 0 in this irreducible factor of h(X)−h(Y) to get the sought lower bound for deg_{K}(z).

We are left with the case when [K : k(u, v)] = 2, and we proceed to prove that this case cannot occur at all. Note that k(x) = k(u, \sqrt{u^{2} − 4}) and k(y) = k(v, \sqrt{v^{2} − 4}). Hence, K = k(x, y) = k(u, v)(\sqrt{u^{2} − 4}, \sqrt{v^{2} − 4}). Since none of the fields k(x), k(y) is included in k(u, v), we have that none of u^{2} − 4, v^{2} − 4 is a square in k(u, v) but the ratio (v^{2} − 4)/(u^{2} − 4) is a square in k(u, v). We distinguish between two further cases.

• Case: h̃(2) ≠ h̃(−2).

Since (v^{2} −4)/(u^{2} −4) is a square in k(u, v), the function u−2 must have even order at all the places of k(u, v) lying above the place u = 2 of k(u), except possibly for the places with v = 2 (v = −2 does not lie above u = 2 because h̃(2) ≠ h̃(−2)). Since H(U, V) is absolutely irreducible, the places of k(u, v) above u = 2 correspond to the Puiseux series of h̃(Z) − h̃(u), as series Z = Z(u) centered at u = 2, where we disregard the ‘trivial’ series Z = u = 2 + (u − 2).

It is very easy to determine some features of these series: Let z = ξ be a root of multiplicity μ_{ξ} of the equation h̃(z) − h̃(2) = 0; then the ramification index at v = ξ above u = 2 is μ_{ξ}/ gcd(μ_{ξ}, μ_{2}) (see e.g. [8]). Since (v^{2} − 4)/(u^{2} − 4) has even order at all places, this index has to be even for ξ ≠ 2 (note that in the present case the value ξ = −2 does not appear). Hence in particular μ_{ξ} is even for ξ ≠ 2. Note that μ_{2} cannot be even, for otherwise h̃(Z) − h̃(2) would be a square, and H(U, V) would be reducible, a contradiction. Similarly at u = −2. We deduce that

h̃(Z) − h̃(±2) = (Z ∓ 2)Q_{±}^{2}(Z),

for a suitable Q_{±} ∈ k[Z]. By [13, Lemma 4, p. 27] (applied with q_{1} = ξ_{1} = 2, q_{2} = ξ_{2} = −2), we have h̃(Z) = ±T_{n}(Z) where T_{n} is the nth Chebyshev polynomial. But then again H(U, V) would be reducible, which is not the case.

• Case: h̃(2) = h̃(−2).

Now the same argument as above yields again that μ_{ξ} is an even integer for ξ^{2} ≠ 4. Also, putting μ_{2} = α_{+}ρ, μ_{−2} = α_{−}ρ, where ρ = gcd(μ_{2}, μ_{−2}), it is easy to see, on looking at Puiseux series, that the ramification index of any place in k(u, v)/k(u) with v = −2 above u = 2 is α_{−}, and the order of (v^{2} − 4)/(u^{2} − 4) at such a place is α_{−}((μ_{2}/μ_{−2}) − 1) = α_{+} − α_{−}. Hence the present assumption implies that α_{−} and α_{+} are odd and μ_{2} − μ_{−2} is even.

Hence h̃(u) − h̃(2) = (u^{2} − 4)^{m}R^{2}(u) for a polynomial R ∈ k[u] and an integer m ∈ {0, 1}, whence h(x) − h(1) = (x − x^{−1})^{2m}R^{2}(x + x^{−1}) is a square Q^{2}(x) in k(x). This however contradicts condition (H2), because we would have the decomposition h(x) = p(q(x)) with p(x) = x^{2} + h(1), q(x) = Q(x). (Note that deg Q = deg h/2 ≥ 32.)

In conclusion, in the cases under consideration the degree [K : k(u, v)] cannot be 2 but must be 4, and we are done as remarked above.

After all of this work we have merely achieved (8); however with this tool we are ready to give the proof of the statement in question. We study the equation f(x) − f(y) = 0 and take the same partition coming from Σ = Σ_{L} ∪ Σ_{S} as before. Suppose that a vanishing minimal subsum of f(x) − f(y) contains terms of type LL and LS, say x^{m}y^{n} and x^{m′}y^{n′}. Then the ratio is z = x^{m−m′}y^{n−n′}, where |n − n′| > (2/3^{l})m_{ℓ}, and hence

deg_{K}(z) ≥ \frac{2}{63 · 3^{ℓ}} m_{ℓ}δ,

where we have used (8). So by Lemma 2 and by using 2𝔤 − 2 + |S| ≤ 2δ^{2} and the inequality (4) we get

deg f ≤ m_{ℓ} ≤ \frac{63 · 3^{ℓ}}{2} \binom{ℓ^{2} − 2}{2}2δ ≤ (2016 · 5^{ℓ})(d − 1),

and similarly if two of the four sets contain terms from some minimal subsum. Hence, we may assume that each of the four sets is a union of vanishing subsums, so:

a(x)b(y) = a(y)b(x)
A(x)B(y) = A(y)B(x)
A(x)b(y) = B(x)a(y)
a(x)B(y) = b(x)A(y)

Suppose that some among a(x), A(x), b(x), B(x) vanish. We know A(x) ≠ 0 (it contains the term x^{m_{ℓ}} with the maximal degree) and also a(x) ≠ 0 (it contains the constant term). If b(x) = 0, we have B(x)a(y) = A(x)b(y) = 0, so B(x) = 0 which is impossible. If B(x) = 0, then we similarly conclude b(x) = 0, that is again impossible. So a(x)A(x)b(x)B(x) ≠ 0. We find

\frac{a(x)}{b(x)} = \frac{a(y)}{b(y)} = \frac{A(x)}{B(x)} = \frac{A(y)}{B(y)} = φ(h)

for some φ ∈ k(x). Thus a(x) = φ(h)b(x), A(x) = φ(h)B(x) and therefore a(x) + A(x) = φ(h)(b(x) + B(x)) implying

f(x) = \frac{a(x) + A(x)}{b(x) + B(x)} = φ(h) = \frac{a(x)}{b(x)}.

By induction on ℓ we get that deg φ ≤ 2016 · 5^{ℓ−1} and thus deg f = deg φ · d ≤ (2016 · 5^{ℓ})(d − 1). (The case ℓ = 2 again follows, e.g. on following the arguments made above and observing that the last case is impossible since then Σ contains at least three elements.) Thus the statement is proved. □

5.3. Proof of Theorem 3 in the case h(0) = 0. This last part of the proof proceeds exactly like the one for the non-Laurent case in Subsection 4.2 above: We just have to observe that h(x) = x^{e}p̃(x), where p̃ is a non-constant polynomial, not vanishing at 0. The arguments therein do not require any modification. □

6. Proof of the Corollary

In this section we give the proof of the corollary. We argue similarly to [6, Lemma 2] or [18].

Suppose that one among q(x), h(q(x)), h(h(q(x))) is not of the forbidden shape (of the Main Theorem). Then we may apply such theorem with h^{∘(n−i)} in place of g (with suitable i ≤ 2) and h^{∘i} ∘ q in place of h. If h^{∘n}(q(x)) = P (x)/Q(x), where P, Q are polynomials having altogether at most ℓ terms, then the conclusion of the Main Theorem gives 2016 · 5^{ℓ} ≥ deg g = (deg h)^{n−i} = d^{n−i} ≥ d^{n−2}, whence

ℓ ≥ \frac{1}{log 5}((n − 2) log d − log 2016),

proving the conclusion.

So let us assume that each among q(x), h(q(x)), h(h(q(x))) is of the forbidden shape, i.e. λ(ax^{n} + bx^{−n}), a, b ∈ k, n ∈ ℕ, λ ∈ PGL_{2}(k).

Take this expression for q(x) and assume first that ab ≠ 0. On rescaling x, setting x in place of a suitable power of it, and changing h with λ^{−1} ∘ h ∘ λ, we may write q(x) = x + x^{−1}. (Note that these substitutions do not affect the conclusions.)

Then we have h(x+x^{−1}) = λ_{1}(a_{1}x^{r}+b_{1}x^{−r}) for a_{1}, b_{1} ∈ k, λ_{1} ∈ PGL_{2}(k) and some r > 0. Since the left side is invariant under x ↦ x^{−1}, we must have a_{1} = b_{1} ≠ 0, and then r = d = deg h. Recall now that T_{d}(x + x^{−1}) = x^{d} + x^{−d}, for the Chebyshev polynomial T_{d} of degree d, so h(x) = λ_{1}(a_{1}T_{d}(x)) = (λ_{1}^{∗} ∘ T_{d})(x) for a λ_{1}^{∗} ∈ PGL_{2}(k).

Further, we have h(h(q(x))) = λ_{2}(a_{2}x^{m} + b_{2}x^{−m}) for a_{2}, b_{2} ∈ k, λ_{2} ∈ PGL_{2}(k), m ∈ ℕ. Again, a_{2} = b_{2}, and d is a divisor of m: m = ld for a positive integer l. The above equation yields h(λ_{1}^{∗}(T_{d})) = λ_{2}^{∗}(T_{m}) = λ_{2}^{∗}(T_{ld}) = λ_{2}^{∗}(T_{l}(T_{d}))), for suitable λ_{2}^{∗} ∈ PGL_{2}(k), where we have used the composition property T_{rs} = T_{r} ∘ T_{s} for positive integers r, s. Then h ∘ λ_{1}^{∗} = λ_{2}^{∗} ∘ T_{l}, whence l = d and, on taking λ_{3} = (λ_{1}^{∗})^{−1} ∘ λ_{2}^{∗} ∈ PGL_{2}(k), we get

T_{d} ∘ λ_{1}^{∗} = λ_{3} ∘ T_{d}.

Now, T_{d} is a polynomial of degree d. Since d ≥ 3, ∞ is the unique totally ramified point of the map x ↦ T_{d}(x) and it follows that λ_{1}^{∗}, λ_{3} must fix ∞. We therefore invoke [13, Lemma 5, p. 28] to conclude that λ_{1}^{∗}(x) = ±x, λ_{3}(x) = (±1)^{d}x. This implies λ_{2}^{∗}(x) = (±1)^{d+1}x and also h(x) = (±1)^{d}T_{d}(x).

Consider now the case when ab = 0 in the expression for q. Up to conjugation by an element in PGL_{2}(k) and on setting x in place of a suitable power of it we may now assume that q(x) = x. Write then as above h(x) = λ_{1}(a_{1}x^{d} + b_{1}x^{−d}) with (new) a_{1}, b_{1} ∈ k and λ_{1} ∈ PGL_{2}(k). If a_{1}b_{1} ≠ 0, the arguments are as before. Then assume a_{1}b_{1} = 0, so h(x) = λ_{1}^{∗}(x^{d}) for a λ_{1}^{∗} ∈ PGL_{2}(k). Similarly to the case treated above, we obtain also λ_{1}^{∗}(x)^{d} = λ_{3}(x^{d}), and the conclusion easily follows. □

7. Appendix: Composite factors of binomials

We prove here that the question posed at the end of the introduction (see Remark 1.2(iii)) has an affirmative answer in the special case of binomials. To recall this, let us assume that a binomial x^{m′}(x^{m} + a) with 0 ≤ m′ < m, m, m′ ∈ ℕ, a ∈ k, is divisible by the composite g(h(x)) of two polynomials g, h ∈ k[x], where as usual deg g, deg h ≥ 2 and h(x) is not of the shape bx^{n} + c, b, c ∈ k, n ∈ ℕ. We thus have the equation

(9)  x^{m′}(x^{m} + a) = q(x)g(h(x)), q(x) ∈ k[x].

We prove

Theorem 5. Equation (9) implies deg g ≤ 24.

Proof. If a = 0, then g(h(x)) is a power of x. Hence, for every root ξ of g we have h(x) − ξ = bx^{d}, where b and d are the leading coefficient and degree of h respectively. Hence, h is of the exceptional shape. Let us then assume that a ≠ 0. By rescaling we may further assume a = −1, so the equation becomes

x^{m′}(x^{m} − 1) = q(x)g(h(x)).

We note at once that we may reduce to the case h ∉ k[x^{s}] for any s > 1. To prove this reduction we argue by induction on deg h, similarly to what we did in connection with the previous results. Assuming h(x) = h^{∗}(x^{s}) for a polynomial h^{∗} ∈ k[x], we write q(x) = q_{0}(x^{s}) + xq_{1}(x^{s}) + … + x^{s−1}q_{s−1}(x^{s}) for polynomials q_{0}, q_{1}, …, q_{s−1} ∈ k[x]. Note that x^{m′}(x^{m} − 1) = ∑_{i=0}^{s−1} x^{i}q_{i}(x^{s})g(h^{∗}(x^{s})), where all the terms in the summand indexed by i on the right have degree ≡ i (mod s).

If m ≢ 0 (mod s), then we conclude that x^{m′} is of the shape x^{i}q_{i}(x^{s})g(h(x)), so we fall in a case just excluded in the opening argument. Therefore we have m ≡ 0 (mod s), and for some i, x^{m′}(x^{m} −1) = x^{i}q_{i}(x^{s})g(h(x)). Hence, x^{(m′−i)/s}(x^{m/s} −1) = q_{i}(x)g(h^{∗}(x)); this is an equation of the same type as before, with the same g but lowered degrees. So eventually we reach a situation when h ∉ k(x^{s}), for any s > 1, as we shall assume from now on.

For each root ξ of g we have that all the roots of h(x) − ξ are either 0 or roots of unity. Here 0 may appear at most for one ξ, and the other roots are simple. Also, for all ξ the set of non-zero roots, say denoted by S_{ξ}, is nonempty. We have the equation

h(θ) − h(ζ) = 0

for all θ, ζ ∈ S_{ξ}.

Now, by a theorem of Beukers and Smyth [2] (see also [15] for the main argument of their proof), the number of pairs (θ, ζ) of roots of unity which lie on an irreducible curve f(θ, ζ) = 0, when f is not of the special shape bx^{n}y^{n′} + c or bx^{n} + cy^{n′}, is bounded by 11(deg f)^{2}.

Let us detect the special factors dividing h(x) − h(y). One factor is x − y. If another factor is of the above shape, we have h(x^{n}) = h(cx^{n′}) for some constant c ∈ k^{∗} and coprime exponents n, n′ ∈ ℤ. Necessarily n = n′, so we may assume h(x) = h(cx). Then c is a root of unity and h(x) = h^{∗}(x^{e}) for h^{∗} ∈ k[x] and an e > 1, a case which has been excluded above.

So there are no other such special factors, whence

|{(θ, ζ) : θ ≠ ζ, h(θ) = h(ζ), θ, ζ roots of unity}| ≤ 11(deg h)^{2}.

Hence,

∑_{g(ξ)=0} |S_{ξ}|(|S_{ξ}| − 1) ≤ 11(deg h)^{2}.

On the other hand, since |S_{ξ}| = deg h for all but possibly one ξ, in which case it is ≥ 1, we have that

∑_{g(ξ)=0} |S_{ξ}| ≥ deg g deg h − deg h + 1 = deg h(deg g − 1) + 1.

Using the Cauchy-Schwarz inequality we get

σ^{2} := ( ∑_{g(ξ)=0} |S_{ξ}|)^{2} ≤ deg g ∑_{g(ξ)=0} |S_{ξ}|^{2},

and thus

11(deg h)^{2} ≥ ∑_{g(ξ)=0} |S_{ξ}|(|S_{ξ}| − 1) ≥ \frac{σ^{2}}{deg g} − σ = σ (\frac{σ}{deg g} − 1) .

Furthermore, this implies

11(deg h)^{2} ≥ deg h(deg g − 1) (\frac{deg h(deg g − 1)}{deg g} + \frac{1}{deg g} − 1) .

Dividing by (deg h)^{2} and using deg g, deg h ≥ 2, it follows

11 ≥ (deg g − 1) (\frac{deg g − 1}{deg g} − \frac{1}{deg h} + \frac{1}{deg h deg g} )

≥ \frac{(deg g − 1)^{2}}{2 deg g} ≥ \frac{deg g}{2} − 1,

and finally deg g ≤ 24. □

Remark 7.1 We remark that there are certainly non-trivial (that is, with deg g > 1) solutions to (9). For instance, observe that

x^{n(n−1)+1} − x = (x − 1)^{2}h(x)(h(x) − 1) = (x − 1)^{2}g(h(x)),

with

h(x) = \frac{x^{n} − 1}{x − 1}, g(x) = x(x − 1).

This provides an example with deg g = 2.

Most probably however, the estimate deg g ≤ 24 may be sharpened, possibly to deg g ≤ 2, which would then be best-possible. It is also possible that there are no solutions in which deg g ≥ 2 and m′ = 0.

These questions amount to certain systems of equations to be solved in roots of unity. We plan to return to them in a future paper.

On the other hand, the general question of divisibility of an ℓ-nomial by a composite factor g(h(x)) appears to be difficult and not in the range of the methods of the present paper.

8. Acknowledgments

This paper was partly written during a stay of the second author at ETH in October 2009; he is grateful for financial support and hospitality during the stay. Furthermore, both authors would like to thank M. Fried and P. Müller for very helpful discussions and references.

References

[1] R. Avanzi, U. Zannier, The equation f(X) = f(Y) in rational functions X = X(t), Y = Y (t), Compositio Math. 139 (2003), 263–295.

[2] F. Beukers, C.J. Smyth, Cyclotomic points on curves, Number theory for the millennium, I (Urbana, IL, 2000), 67–85, A K Peters, Natick, MA, 2002.

[3] Y. Bilu, R. Tichy, The Diophantine equation f(x) = g(y), Acta Arith. 95 (2000), 261–288.

[4] D. Brownawell, D. Masser, Vanishing sums in function fields, Math. Proc. Camb. Phil. Soc. 100 (1986), 427-434.

[5] J.D. Dixon, B. Mortimer, Permutation Groups, Graduate Texts in Mathematics 163, Springer-Verlag, New York - Berlin - Heidelberg, 1996.

[6] R. Dvornicich, U. Zannier, Cyclotomic Diophantine problems (Hilbert irreducibility and invariant sets for polynomial maps), Duke Math. J. 139 (2007), no. 3, 527–554.

[7] M. Fried, On a conjecture of Schur, Michigan Math. J. 17 (1970), 41–55.

[8] M. Fried, Arithmetical properties of function fields. II. The generalized Schur problem, Acta Arith. 25 (1974), 225–258.

[9] A. Gabrielov, N. Vorobjov, Complexity of computations with Pfaffian and Noetherian functions, Normal forms, bifurcations and finiteness problems in differential equations, 211–250, NATO Sci. Ser. II Math. Phys. Chem., 137, Kluwer Acad. Publ., Dordrecht, 2004.

[10] S. Lang, Introduction to Algebraic and Abelian Functions. Second Edition, Graduate Texts in Mathematics 89, Springer-Verlag, New York - Berlin, 1982.

[11] P. Müller, Permutation Groups with a Cyclic Two-Orbits Subgroup and Monodromy Groups of Siegel Functions, Preprint, arXiv:math/0110060.

[12] P. Müller, Cofinite Integral Hilbert sets, Habilitationsschrift, Heidelberg, 1999.

[13] A. Schinzel, Polynomials with Special Regard to Reducibility, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2000.

[14] H. Stichtenoth, Algebraic Function Fields and Codes, Universitext, Springer-Verlag, Berlin, 1993.

[15] B. Sturmfels, Polynomial equations and convex polytopes, Amer. Math. Monthly 105 (1998), 907–922.

[16] S. Watt, M. Zieve, Functional composition of symbolic Laurent polynomials, in preparation.

[17] U. Zannier, Some remarks on the S-unit equation in function fields, Acta Arith. LXIV (1993), no. 1, 87-98.

[18] U. Zannier, On the number of terms of a composite polynomial, Acta Arith. 127 (2007), no. 2, 157-167.

[19] U. Zannier, On composite lacunary polynomials and the proof of a conjecture of Schinzel, Invent. Math. 174 (2008), no. 1, 127-138.

[20] U. Zannier, Addendum to the paper: On the number of terms of a composite polynomial, Acta Arith. 140 (2009), no. 1, 93-99.

Clemens Fuchs Department of Mathematics ETH Zurich Rämistrasse 101 8092 Zürich Switzerland Email: clemens.fuchs@math.ethz.ch

Umberto Zannier Scuola Normale Superiore Piazza dei Cavalieri, 7 56126 Pisa Italy Email: u.zannier@sns.it