Annales Academiæ Scientiarum Fennicæ Series A. I. Mathematica Volumen 18, 1993, 125–146

GRAPHS AND FUNCTIONAL EQUATIONS

Lowell J. Hansen and Harold S. Shapiro

Wayne State University, Department of Mathematics Detroit, MI 48202, U.S.A.; lowell@math.wayne.edu Royal Institute of Technology, Department of Mathematics S-10044 Stockholm, Sweden; shapiro@math.kth.se

Abstract. Given two polynomials P and Q and a class of functions (e.g., meromorphic, entire, rational, polynomial), we study conditions under which there exist no nonconstant functions f and g in the given class which satisfy the functional equation f(P (z)) = g(Q(z)).

1. Introduction

Let P be entire and h meromorphic on the complex plane, C. For each w ∈ C, the w-level set of P is the set {z : P (z) = w}. We will say that h is a function of P if h is constant on the w-level set of P for every w. It is easy to see that this is equivalent to the existence of a meromorphic function f on C such that h = f ∘ P.

This paper and a sequel in preparation deal with the following problem. Let k denote a given meromorphic function on C, and P, Q given polynomials. Look for all pairs of meromorphic functions f, g on C such that

(1)  f(P (z)) − g(Q(z)) = k(z).

As we shall see in the sequel, (1) is closely related to Dirichlet’s problem for the Laplace equation, especially the question of the harmonic continuation of the solution in the exterior of the domain where the problem is posed.

In this paper we consider the special case where k = 0. Then (1) becomes

(2)  f(P (z)) = g(Q(z)) =: h(z),

in which case we say that h is a function of both P and Q. Thus we could phrase our goal as follows: Given the polynomials P and Q and a class of functions (meromorphic, entire or polynomials), we wish to determine all nonconstant functions h of the given class which are functions of both P and Q. Clearly, for a smaller class of allowable solutions, it is less likely that nonconstant solutions will exist. For many pairs (P, Q) it will turn out that (2) has no nonconstant solution.

1991 Mathematics Subject Classification: Primary 30D05; Secondary 39B32.

This will in turn imply that on certain algebraic curves no nonconstant functions of the given class can have vanishing real part, results of a type studied earlier in [FNS]. Special cases of our investigation are a theorem of Rényi and Rényi [RR] and its generalization by Fuchs and Gross [FG] concerning periodicity of functions of the form (f ∘ P).

Another way of formulating the problem is as follows. Let ℳ = ℳ (C), ℰ = ℰ (C) denote the meromorphic and entire functions on the complex plane, respectively. For a given polynomial P, ℳ_{P} and ℰ_{P} denote, respectively, the meromorphic and entire functions that are “functions of P ”. Then the question of whether, for given polynomials P and Q, any nonconstant function h satisfies (2) is the question of the existence of nonconstant functions in ℳ_{P} ∩ ℳ_{Q}.

An important tool in studying these questions is the notion of cyclic elements in the group of invertible germs of analytic functions. This is classical but, as it is not easy to find accessible references, we recall this material in Section 2. In order to have a handy language for some of the considerations in this paper, we introduce in Section 3 an infinite graph Γ(P, Q) induced by any given pair of polynomials P, Q of degrees ≥ 2. Its nodes, or vertices, are the points of C. Two vertices z, ζ of Γ(P, Q) are connected by an edge if and only if at least one of the relations P (z) = P (ζ), Q(z) = Q(ζ) holds. It is then clear that h satisfying (2) takes the same value at two points whenever they can be joined by a path (finite succession of edges) of this graph. Thus, for example, if infinitely many distinct points lying in a bounded region can be joined by paths to one and the same point, h must be constant.

The balance of the paper is organized as follows. In Section 4 we present the history of the problem. For expository purposes, we recap the original proofs of a theorem of Rényi and Rényi [RR] and its generalization by Fuchs and Gross [FG]. In Section 5 we link together the notions of Sections 2 and 3 to provide an alternative mechanism for studying the problem and giving computer-assisted proofs that certain functional equations (2) have no nonconstant meromorphic solutions. We conclude in Section 6 with various further remarks.

2. The group of invertible germs

By a germ we shall mean a function φ analytic on some neighborhood of 0 in the complex plane satisfying φ(0) = 0. We say φ is invertible if φ′(0) ≠ 0. In this case, the equation w − φ(z) = 0 is uniquely solvable for z (for w sufficiently near 0) and we get z = ψ(w) for some germ ψ. We will also denote ψ by φ^{[−1]} , and call it the inverse of φ. It is easy to see that, under functional composition, the invertible germs form a group, which we shall denote by 𝒢 . The identity of 𝒢 is, of course, the germ e defined by e(z) ≡ z.

We summarize the main information we need in the following

Proposition 2.1. The following are equivalent for an element φ of 𝒢 and integer k ≥ 1.

(i) φ^{[k]} is the identity of 𝒢 , where φ^{[k]} denotes φ ∘ φ ⋯ ∘ φ (k times). (ii) There exists ψ ∈ 𝒢 and a k^{th} root of unity (denoted by ω) such that

φ(z) = ψ^{[−1]}(ωψ(z))

(in other words, φ is conjugate to the rotation ζ ↦ ωζ). (iii) There exists a function f holomorphic near 0, having a Taylor expansion of

the form z^{k}+ (higher order terms), such that f ∘ φ = f.

Proof. Assume first that (iii) holds. Then, f can be written as g^{k} where g is holomorphic near 0 and has the expansion

g(z) = z + (higher order terms).

Then (iii) implies that

g(φ(z))^{k} = g(z)^{k}

so there is some k^{th} root ω of 1 such that

g(φ(z)) = ωg(z).

This yields (ii), with ψ = g.

Now assume (ii) holds. Then

φ^{[2]}(z) = φ(φ(z)) = ψ^{[−1]}(ωψ(φ(z)))ψ^{[−1]} (ωψ(ψ^{[−1]}(ωψ(z)))) = ψ^{[−1]}(ω^{2}ψ(z))

Proceeding iteratively, we conclude that

φ^{[k]}(z) = ψ^{[−1]}(ω^{k}ψ(z)) = z,

proving (i).

Finally, we will show that (i) implies (iii). Assume (i) holds, and let

f(z) := zφ(z)φ^{[2]}(z) ⋯ φ^{[k−1]}(z).

Clearly f is holomorphic near z = 0 and its power series has the form

z^{k} + (higher order terms).

Moreover, f(φ(z)) = f(z), verifying (iii).

Remark. An element φ of 𝒢 satisfying (i) for some k is said to be cyclic. The order of φ is then the smallest k such that φ^{[k]} is the identity. It is easy to see that φ is cyclic of order k if and only if (ii) holds for some ψ ∈ 𝒢 and primitive k^{th} root ω of unity.

3. Reentrant graphs

Our basic question is closely linked with a purely combinatorial one: Let P, Q be polynomials with complex coefficients, of degrees p, q, respectively. We assume p ≥ 2 and q ≥ 2. We define a graph (with infinitely many nodes) Γ(P, Q) as follows: The nodes are the points of the complex plane, C. Given two points z_{1} , z_{2} (z_{1} ≠ z_{2} ) of C, we connect them by an edge if and only if at least one of the relations P (z_{1}) = P (z_{2}), Q(z_{1}) = Q(z_{2}) holds. Moreover, we “color” the edge “red” if the first relation holds, “blue” if the second holds, and “red/blue” if both hold. This colored graph is denoted Γ(P, Q).

A path on Γ(P, Q) is a sequence of directed edges such that the initial point of each edge after the first is the endpoint of the preceding. The path is proper if the edges comprising it alternate in color. A red/blue edge may be considered as red, or blue as desired; thus, the sequences (red, red/blue, red, red/blue) and (red/blue, red/blue) alternate. A closed proper path has, of course, an even number of edges. (It is easy to see that if we were to allow, say, two or more consecutive “red” edges, they could always be replaced by just one, so the requirement that paths be proper is not really restrictive.) We will call a closed proper path consisting of m edges an m-cycle.

Clearly, if h ∈ ℳ_{P} ∩ ℳ_{Q}, then h(z) = h(z_{1}) for each z reachable from z_{1} by a path of finite length along Γ(P, Q). (An alternative formalism, in terms of equivalence relations is given at the end of this section.)

We will say that Γ(P, Q) has the clustering property if, within some bounded region D, there are infinitely many distinct points connected to some fixed point z_{1} along Γ(P, Q). Then, obviously, if Γ(P, Q) has the clustering property, each function in ℳ_{P} ∩ ℳ_{Q} is constant.

Γ(P, Q) has the weak clustering property if there is a compact set K ⊂ C such that for every positive integer N, there is a point connectable to N distinct points of K.

Proposition 3.1. If Γ(P, Q) is weak clustering, then ℳ_{P} ∩ ℳ_{Q} consists only of constants.

Proof. Suppose not, and h ∈ ℳ_{P} ∩ ℳ_{Q} is nonconstant meromorphic. Then, by assumption, for each N we have z_{1}, z_{2}, …, z_{N} in K such that

h(z_{1}) = h(z_{2}) = ⋯ = h(z_{N}) = w_{N}.

Then, either w_{N} → ∞ or else {w_{N}} has a bounded subsequence. Clearly, it is sufficient to treat the second case, since otherwise we consider 1/h. So, by passing to a subsequence if necessary, we may assume w_{n} → λ ∈ C. Let now γ be a contour surrounding K, on which h(z) does not take the value λ. Then, for large N, h does not take the value w_{N} on γ. Now

J_{N} := \frac{1}{2πi} ∫_{γ} \frac{h′(z)}{h(z) − w_{N}} dz

is the number of roots of h(z) = w_{N} inside γ, minus the number of poles of h. As N → ∞, the former is at least N, so J_{N} → +∞. However,

lim_{N→∞} J_{N} = \frac{1}{2πi} ∫_{γ} \frac{h′(z)}{h(z) − λ} dz

which is finite.

We define the graph Γ(P, Q) to be reentrant if there exists a compact set K ⊂ C such that every ζ ∈ C can be connected to some point in K by a path in Γ(P, Q).

A relationship between reentrant graphs and our basic question is set forth in the following theorem.

Theorem 3.1. If Γ(P, Q) is reentrant and h_{1} and h_{2} belong to ℳ_{P} ∩ ℳ_{Q}, then there exists a nontrivial polynomial π with π(h_{1}, h_{2}) = 0.

Proof. The hypothesis that h_{1} and h_{2} belong to ℳ_{P} ∩ ℳ_{Q} implies that there exist f_{i}, g_{i} meromorphic on C with

(3)  \{ \begin{matrix}h_{1}(z) = f_{1}(P (z)) = g_{1}(Q(z)), \\ h_{2}(z) = f_{2}(P (z)) = g_{2}(Q(z)). \end{matrix}

By a well-known procedure (cf. [AS, p. 52]) there exists a nontrivial polynomial π such that the meromorphic function h = π(h_{1}, h_{2}) has no poles in {|z| ≤ R}. Also, because of equation (3), h_{1} and h_{2} (and hence h) are constant along the vertices of each proper path in Γ(P, Q). Therefore, all values taken by h in C are taken in {|z| ≤ R}, which implies that h is a bounded entire function. Hence h is constant.

Corollary 3.1. If h is any entire function satisfying (2) for suitable entire f, g and Γ(P, Q) is reentrant, then h is constant.

We will use the notation n(z_{∗}, h) to denote the multiplicity at z_{∗} of the nonconstant meromorphic function h. That is, n(z_{∗}, h) is the order of the zero of h − h(z_{∗}) at z_{∗} if h is analytic at z_{∗}, and is the order of the pole at z_{∗} otherwise.

Remarks. 1. The multiplicity of a nonconstant meromorphic function differs from 1 only on the isolated set where it has a pole of order larger than 1 or where its derivative is zero. Thus, the multiplicity of a nonconstant meromorphic function is bounded on compact sets.

2. Let P and f be nonconstant meromorphic functions with P analytic at z_{∗} and f analytic at w = P (z_{∗}). Then there exists p_{∗} analytic at z_{∗} with p_{∗}(z_{∗}) ≠ 0 so that

P (z) − w = (z − z_{∗})^{n(z_{∗},P)}p_{∗}(z).

Using a similar formula for f near w and taking compositions, it follows that

n(z_{∗}, f ∘ P) = n(z_{∗}, P)n(P (z_{∗}), f).

The same formula also holds when f has a pole at P (z_{∗}).

Proposition 3.2. If Γ(P, Q) is reentrant (with associated compact set K), there is, to each nonconstant h ∈ ℳ_{P} ∩ ℳ_{Q}, an integer N = N_{h} such that

(a) all poles of h have multiplicity ≤ N

(b) for each a ∈ C, all roots of h(z) = a have multiplicity ≤ N.

Proof. Pick any point z in C for which h(z) = a. There is a path (z, z_{1}, …, z_{n}, ζ) connecting it to a point ζ ∈ K.

Suppose first that P′ and Q′ are nonzero at all vertices of this path. If, say P (z) = P (z_{1}), then it follows from Remark 2 above that the multiplicities of the a-points which h has at z and z_{1} are the same. Continuing along the chain to ζ we see that the multiplicity in question is that of the a-point at ζ. But this is bounded independently of a by Remark 1 above.

In case, as we move along the path, we reach a point where P′, say, vanishes to order r, then the multiplicity of the a-point can be multiplied by r + 1 in the passage. Taking account that there are at most (deg P) − 1 such points (and similarly for Q), we see that the multiplicity of h at ζ cannot exceed that at z by more than a factor C depending only on the degrees of P and Q.

Theorem 3.1 demonstrates that it is of interest to have conditions which imply that the graph Γ(P, Q) induced by a pair of polynomials P and Q is reentrant. The next theorem gives such a condition:

Theorem 3.2. Let P and Q be monic polynomials of degrees p and q, respectively. Suppose that the rational function

R(z) = \frac{P (z)^{q}}{Q(z)^{p}}

is nonconstant and that its Laurent expansion about ∞ has the form

(4)  R(z) = 1 + az^{−s} + 𝒪(|z|^{−s−1})

where s ≥ 1 and a ≠ 0. If

(5) neither p nor q divides s and at least one of them does not divide 2s,

then Γ(P, Q) is reentrant.

Remarks. 1. Before giving the proof, we give some examples that illustrate the theorem.

(a) Let P (z) = (z − 1)^{3} and Q(z) = z^{3} . Here, R(z) = (1 − z^{−1})^{9} = 1 − 9z^{−1} + ⋯, so s = 1 and the hypotheses of the theorem are satisfied. In this case the conclusion can be verified directly, since it is easy to see that the vertices of Γ(P, Q) reachable from ζ are exactly the orbit of ζ under the group generated by the maps z ↦ (2 − z) and z ↦ ωz, where ω = e^{2πi/3} .

(b) If P and Q are monic of the same degree p ≥ 3 and (P − Q) is neither constant nor of degree p/2, the conditions of our theorem are again satisfied. Indeed, (P/Q) − 1 = (P − Q)/Q is, for large z, asymptotic to cz^{k−p} where k = deg(P −Q) and c ≠ 0. Thus P/Q = 1+cz^{k−p}+⋯, (P/Q)^{p} = 1+pcz^{k−p}+⋯ and so the s in equation (4) is (p − k) and (5) holds by virtue of the conditions on (P − Q). To see why (P − Q) may not be of degree p/2, consider the following example: Let P (z) = z^{4} + 2z^{2} + 1 and Q(z) = z^{4} . Then P is P_{1}(z^{2}) and Q is Q_{1}(z^{2}) (with P_{1}(z) = (z + 1)^{2} and Q_{1}(z) = z^{2} ). Now there exists a nonconstant entire function, f, with f(P_{1}) = f(Q_{1}). And so, composing with z^{2} , we get a nonconstant entire solution to f(P) = f(Q). Notice that here p = 4 and the degree of (P − Q) is p/2 = 2.

(c) If P = T_{p} and Q = T_{q}, where T_{p} and T_{q} are Chebyshev polynomials of the first kind, the hypotheses of the theorem do not hold. Verifying this is simple if we replace T_{p}(z) and T_{q}(z) by the monic polynomials 2T_{p}(z/2) and 2T_{q}(z/2), respectively, which we now relabel as P and Q, respectively. To check condition (4), we suppose that p < q and seek first to determine the degree of

P (z)^{q} − Q(z)^{p} = (2 cos (p cos^{−1}(z/2)))^{q} − (2 cos (q cos^{−1}(z/2)))^{p} .

If we replace cos^{−1}(z/2) by t and express cos(pt) and cos(qt) in terms of complex exponentials, the degree we seek is the largest r such that a u^{r} term appears in

(u^{p} + u^{−p})^{q} − (u^{q} + u^{−q})^{p}.

Now u^{pq} cancels and the next term in the expansions is a constant times u^{p(q−2)} (since p < q). Thus (P − Q) is of degree p(q − 2), the s of (4) is 2p and so condition (5) is not satisfied. Also, since T_{p} ∘ T_{q} = T_{q} ∘ T_{p} = T_{pq}, the points of the graph Γ(P, Q) to which a given ζ can be connected is simply the finite set where T_{pq} takes on the same value that it does at ζ, and so the graph Γ(P, Q) is not reentrant.

2. If d denotes the greatest common divisor of (p, q), then R in (4) may be replaced by

\frac{P (z)^{(q/d)}}{Q(z)^{(p/d)}}

with no resulting change in the value of s.

3. Note that condition (5) implies that max(p, q) ≥ 3.

Proof of Theorem 3.1. The first step in the proof is contained in:

Proposition 3.3. Given P and Q satisfying the hypotheses of the theorem, there exist positive numbers M, t with t < 1 such that for |ζ| > M, one of the following holds:

(i) there exists z satisfying P (z) = P (ζ) and |Q(z)| ≤ t|Q(ζ)|; or, (ii) there exists z satisfying Q(z) = Q(ζ) and |P (z)| ≤ t|P (ζ)|.

Suppose that this proposition is proved. The theorem may then be deduced as follows: Let K = {z : |z| ≤ M}∪{z : |P (z)Q(z)| ≤ 1}. Then K is compact. Now, start with any ζ, |ζ| > M and apply the proposition. Suppose that (i) holds, and let P (z_{1}) = P (ζ), |Q(z_{1})| ≤ t|Q(ζ)|. Then |P (z_{1})Q(z_{1})| ≤ t|P (ζ)Q(ζ)|. (Note that this last inequality would have followed similarly in the case that (ii) holds.) We continue inductively as follows: Suppose that z_{j} has been produced with |P (z_{j})Q(z_{j})| ≤ t^{j}|P (ζ)Q(ζ)|. If |z_{j}| ≤ M, then z_{j} belongs to K and we are done. If |z_{j}| > M, apply the proposition again to find z_{j+1} with |P (z_{j+1})Q(z_{j+1})| ≤ t|P (z_{j})Q(z_{j})|. The inductive hypothesis then implies that |P (z_{j+1})Q(z_{j+1})| ≤ t^{j+1}|P (ζ)Q(ζ)|. In this way we produce a path in Γ(P, Q) for which we either eventually reach a z_{j} with |z_{j}| ≤ M or else a z_{j} with |P (z_{j})Q(z_{j})| ≤ 1 by virtue of the inequality |P (z_{j})Q(z_{j})| ≤ t^{j}|P (ζ)Q(ζ)|. Consequently, in either case, we enter K after finitely many steps. Thus, the proof of the theorem will be complete once this proposition is proved.

Proof of Proposition 3.3. In the proof of this proposition, we will need the following lemma:

Lemma 3.1. Let P be monic of degree p. Then there exist constants C_{1} , C_{2} such that for all ζ ∈ C, |ζ| ≥ C_{1} , the roots of P (z) = P (ζ) distinct from ζ satisfy

(6)  |z_{j} − ω_{j}ζ| ≤ C_{2};  j = 1, 2, …, p − 1

where ω_{j} = e^{2πij/p}.

Proof. Let {z_{j}}_{j=1}^{p−1} denote the roots of
(7)  P (z) = P (ζ)

other than ζ. We will show that for j = 1, 2, …, p − 1, z_{j} = ω_{j}ζ + 𝒪(1).

First, fix j and a > 0 and let D_{j}(a) denote the disk {|z −ω_{j}ζ| < a|ζ|}. Easy estimates show that there exist positive constants C_{1} and a so that if |ζ| > C_{1} ,

|(z^{p} − ζ^{p}) − (P (z) − P (ζ))| < |z^{p} − ζ^{p}|

for z on ∂D_{j}(a). Then, by Rouché’s theorem, (P (z) − P (ζ)) has inside this disk as many zeroes as (z^{p} − ζ^{p}), namely 1.

To get more precise information, consider (for fixed j, 1 ≤ j ≤ p − 1) the polynomial

k(t) = P (ω_{j}ζ + t) − P (ζ).

Thus k has p roots. By our first estimate, it is easy to see that there are p−1 roots t_{1}, …, t_{p−1} (corresponding to (ω_{j}ζ + t) ∼ ω_{k}ζ with k ≠ j) satisfying |t_{i}| ≥ a|ζ| for some a > 0 depending only on P. Thus, the product of these roots of k is, in absolute value, ≥ (a|ζ|)^{p−1} . But, the product of absolute values of all the roots of k is |P (ω_{j}ζ) − P (ζ)|, which is ≤ A|ζ|^{p−1} . We conclude that the other root of k has absolute value ≤ A/a^{p−1} , which we now call C_{2} . This completes the proof of the lemma since we have shown that to each j there is a root of P (z) = P (ζ) with |z − ω_{j}ζ| ≤ C_{2} .

Remark. One can produce finer asymptotics of the roots as follows: Again, let

k(t) := P (ω_{j}ζ + t) − P (ζ) = [P (ω_{j}ζ) + tP′(ω_{j}ζ) + ⋯ + t^{p}] − P (ζ).

If t_{0} denotes the root of k with |t_{0}| ≤ C_{2} , this gives

|P (ω_{j}ζ) − P (ζ) + t_{0}P′(ω_{j}ζ)| ≤ C_{3}(1 + |ζ|)^{p−2}.

Hence,

t_{0} = \frac{P (ζ) − P (ω_{j}ζ)}{P′(ω_{j}ζ)} + 𝒪(|ζ|^{−1}).

This estimate will be needed later.

To complete the proof of the proposition, we first try, with z_{j} as in the lemma, to find j with

(8)  P (z_{j}) = P (ζ)  and  |Q(z_{j})| ≤ t|Q(ζ)|

for some t < 1. We assume M ≥ C_{1} , so that (6) holds. Now,

(9)  |\frac{Q(ζ)}{Q(z_{j})}|^{p} = |\frac{P (z_{j})^{q}}{Q(z_{j})^{p}} | · |\frac{Q(ζ)^{p}}{P (ζ)^{q}} | = |R(z_{j})| · |R(ζ)|^{−1}.

Also, from (4), we have, putting a = Ae^{iα}, A > 0

(10)  |R(re^{iθ})|^{2} = 1 + 2Ar^{−s} cos(sθ − α) + 𝒪(r^{−s−1})

for large r. Writing ζ = ϱe^{iφ}, z_{j} = r_{j}e^{iθ_{j}}, we get from (9) and (10):

(11)

|\frac{Q(ζ)}{Q(z_{j})}|^{2p} = (1 + 2Ar_{j}^{−s} cos(sθ_{j} − α) + 𝒪(r_{j}^{−s−1}))·
· (1 + 2Aϱ^{−s} cos(sφ − α) + 𝒪(ϱ^{−s−1}))^{−1}
= 1 + 2Ar_{j}^{−s} cos(sθ_{j} − α) − 2Aϱ^{−s} cos(sφ − α) + 𝒪(ϱ^{−s−1})

Now, by (6),

(12)  |r_{j}e^{iθ_{j}} − ϱe^{i(φ+(2πj/p))}| ≤ C_{2};  j = 1, 2, …, p − 1.

Also, |r_{j} − ϱ| ≤ C_{2} , so |1 − r_{j}/ϱ| ≤ C_{2}ϱ^{−1} and (12) implies

|e^{iθ_{j}} − e^{i(φ+(2πj/p))}| ≤ C_{3}ϱ^{−1}

(where, henceforth all C_{j} denote constants that can depend only on P and Q). Consequently,

(13)  |θ_{j} − (φ + (2πj/p))| ≤ C_{4}ϱ^{−1}.

From these estimates it is clear that if we replace r_{j} and θ_{j} by ϱ and φ + 2πj/p, respectively, in the right side of (12) we only introduce an error that is 𝒪(ϱ^{−s−1}). Hence

|\frac{Q(ζ)}{Q(z_{j})}|^{2p} = 1 + 2Aϱ^{−s} [cos (s(φ + (2πj/p)) − α) − cos(sφ − α)] + 𝒪(ϱ^{−s−1})

for j = 1, 2, …, p − 1. Suppose now there is a constant λ(p, q) > 0 such that

(14)  max_{1≤j≤(p−1)} [cos (s(φ + (2πj/p)) − α) − cos(sφ − α)] ≥ λ(p, q)

(where λ(p, q) does not depend on φ, α). Then, for some j ∈ {1, 2, …, p − 1}

|\frac{Q(ζ)}{Q(z_{j})}|^{2p} ≥ 1 + 2Aλ(p, q)ϱ^{−s} + 𝒪(ϱ^{−s−1}).

This leads easily to

|Q(z_{j})| ≤ [1 − δϱ^{−s} + 𝒪(ϱ^{−s−1})] · |Q(ζ)|

for some δ > 0 depending only on p, q, P, Q. Thus,

(15)  |Q(z_{j})| ≤ [1 − δϱ^{−s}] · |Q(ζ)|

holds for some j ∈ {1, 2, …, p − 1}, if |ζ| = ϱ ≥ C_{5} . We thus have: If (14) holds, then for |ζ| ≥ C_{5} , we can find z with P (z) = P (ζ) and |Q(z)| ≤ t|Q(ζ)| for some t < 1. This t = t(ζ) is uniformly less than 1 on bounded ζ -sets.

Let us examine condition (14). If it fails, there is an example of this with α = 0, as we see by putting φ − (α/s) = φ′. Now, the function

F (φ) = max_{1≤j≤(p−1)} [ cos s(φ + (2πj/p)) − cos sφ]

is continuous, of period 2π, and so if it is positive for each φ, it is bounded below by a positive constant λ(p, q). This can only fail if all the inequalities

(16)  cos s(φ + (2πj/p)) − cos sφ ≤ 0,  j = 1, 2, …, p − 1

hold. In exactly the same way we can show that, for |ζ| ≥ C_{6} , unless all the inequalities

(17)  cos s(φ + (2πk/q)) − cos sφ ≥ 0,  k = 1, 2, …, q − 1

hold, there is a point z with Q(z) = Q(ζ) and |P (z)| ≤ t|P (ζ)| (here again, t < 1 and is bounded away from 1 on bounded ζ -sets).

Thus, the proposition, and the theorem, will be demonstrated once we show: the inequalities (16) and (17) cannot all hold. Indeed, we will show that a contradiction follows from the assumption that they all hold. Summing (16) from j = 1 to p − 1, and (17) from k = 1 to q − 1 gives −p cos sφ ≤ 0 and −q cos sφ ≥ 0, respectively (here it is crucial that e^{2πis/p} and e^{2πis/q} are both different from 1). Hence cos sφ = 0 and (16), (17) become

(18)  − sin(2πjs/p) sin sφ ≤ 0,  j = 1, 2, …, p − 1

and

(19)  − sin(2πks/q) sin sφ ≥ 0,  k = 1, 2, …, q − 1.

But at least one of p, q (say, p) does not divide 2s. Then (18) cannot hold, because sin sφ = ±1, and the numbers sin(2πs/p) and sin (2π(p − 1)s/p) are nonzero and negatives of one another. Thus, either the term with j = 1 or that with j = p − 1 is positive in (18). This completes the proof of Proposition 3.3 and, thereby, the proof of Theorem 3.1.

Before closing this section, we remark on a more general formulation of the basic combinatorial problem underlying Γ(P, Q). Given two equivalence relations, ≡_{1} and ≡_{2} , on a set (like C), there is induced a new equivalence relation ≡_{1,2} as the “smallest” equivalence relation ∼ such that x ≡_{1} y or x ≡_{2} y implies that x ∼ y. Since the relation “x ≡_{1} y or x ≡_{2} y ” is not transitive, we must define x ∼ y so that it holds if and only if there is a finite sequence z_{1}, …, z_{n} such that “x ≡_{1} z_{1} or x ≡_{2} z_{1} ”, and “z_{1} ≡_{1} z_{2} or z_{1} ≡_{2} z_{2} ”, and ⋯ “z_{n} ≡_{1} y or z_{n} ≡_{2} y ” all hold. Thus, the equivalence classes are precisely sets of vertices of the graph gotten by joining two points whenever they are either 1-equivalent, or 2-equivalent, that are connected with one another, that is components of Γ(P, Q). In particular, if the underlying set is C and we define z_{1} ≡_{P} z_{2} to mean that P (z_{1}) = P (z_{2}), then ≡_{P,Q} is the equivalence relation corresponding to components of Γ(P, Q). Thus, we can reformulate, for example, the definition of weak clustering, as: To each compact K ⊂ C and N there is a set of N distinct points in K which are ≡_{P,Q} equivalent.

4. History of the problem

In one sense, our problem originates in work of F. Marty ([M1] and [M2]) and T. Shimizu ([Shi1], [Shi2] and [Shi3]) from the 1930’s dealing with the non-Möbius (and even, non single-valued) automorphisms of analytic functions. These questions were later taken up and given a systematic exposition by Gunnar af Hällström in several papers of which we especially mention [H1] and [H2]. Paper [H1] contains numerous references to the work of Marty and Shimizu. In [H1, p. 13], af Hällström writes (we translate from the German): “Here the question arises whether, given (rational) functions f_{1}, …, f_{m} a rational (nonconstant) function g can be found which is simultaneously a rational function of each of the f_{j}.” This is essentially the problem studied in the present paper, except that

(i) the question as posed by af Hällström is more general in that m functions are allowed rather than 2, and these may be rational, not merely polynomials, while

(ii) his question is also less general in that g is required to be rational, not merely

meromorphic. However, apart from noting some trivial examples where no g exists, he does not go further into the problem. In Section 6 below we shall present a method that yields nontrivial necessary conditions for the existence of a (nonconstant) rational g.

Another case of our problem turned up in the work of Rényi and Rényi [RR], who proved: ℰ_{P} ∩ℰ_{per 1} is trivial when deg P ≥ 3. (Here, ℰ_{per 1} is the set of entire functions of period 1.)

Their proof is very easy. Suppose that f ∈ ℰ_{P} has period 1. Look at a large disk D = {z : |z| < R} and let z_{0} ∈ ∂D be a point where |f(z_{0})| = max_{z∈D} |f(z)|. By periodicity f takes the same value f(z_{0}) at all points z_{0}+ integer. If any of these enters D, then f is constant by the maximum modulus theorem. If none of them enters D, then clearly z_{0} is close to either the north pole or south pole of ∂D. But if deg P = p ≥ 3 and R is fairly large, then Lemma 3.1 shows that f takes the value f(z_{0}) at points close to (e^{2πij/p}) · z_{0} , j = 1, 2, …, p − 1. Since p ≥ 3, at least one of these numbers has imaginary part of absolute value much less than R, so f(z_{0}) = f(z_{1}) for some z_{1} whose integer translates really enter D. (In terms of earlier terminology: the graph induced by P and the “periodicity 1” partition is reentrant.)

Fuchs and Gross [FG] showed that a suitably modified theorem holds also for meromorphic functions, and the proof is very similar. Before turning to this, however, let us look at some examples: Let P (z) = (z − a)^{p}, Q(z) = (z − b)^{q} where p, q are at least as large as 2 and a ≠ b. h ∈ ℳ_{P} means h(z_{1}) = h(z_{2}) whenever (z_{1} − a)^{p} = (z_{2} − a)^{p}. That is, z_{1} − a = ω(z_{2} − a) for ω some p^{th} root of unity. In other words, ℳ_{P} is the set of meromorphic functions invariant under the group generated by the substitution

(20)  z ↦ ωz + (1 − ω)a,  ω = e^{2πi/p}.

Likewise, ℳ_{Q} is the set of meromorphic functions invariant under

(21)  z ↦ λz + (1 − λ)b,  λ = e^{2πi/q}.

It is now fairly easy to decide when Γ(P, Q) has any of the basic properties embodied in earlier definitions. For example, it is clustering if p = q ≥ 7, it is reentrant (but not weak clustering) for p = q = 3. There are a finite number of choices of p ≥ 2, q ≥ 2 such that (20), (21) generate a properly discontinuous group; in these cases, and only these, ℳ_{P} ∩ ℳ_{Q} is nontrivial.

What Fuchs and Gross really prove is: If p = deg P and cos 2π/p is irrational, then the graph Γ generated by P and “periodicity 1” is clustering. Here is an outline of the proof. We will use ≡ to denote the equivalence relation generated by ≡_{P} and ≡_{per 1} (notation as introduced in the last paragraph of Section 3). We will assume without loss of generality that P (z) = z^{p} + cz^{p−k} + ⋯ with k ≥ 2. This can be accomplished, if necessary, by replacing P by P ∘ φ, where φ is a linear polynomial. Then, if N is a large integer, the remark following Lemma 3.1 implies that the roots of P (z) = P (N) are ω^{j}N + 𝒪(N^{−1}), j = 1, 2, …, p.

Therefore,

\begin{aligned}0 & ≡ N ≡ Nω^{2} + 𝒪(N^{−1}) ≡ Nω^{2} + N + 𝒪(N^{−1}) \\ & ≡ \overline{ω}(Nω^{2} + N) + 𝒪(N^{−1}) + M ≡ 2N cos 2π/p + M + 𝒪(N^{−1}) \end{aligned}

where M is any integer. Assume here that ω^{2} + 1 ≠ 0, so that Nω^{2} + N is large when N is. If now cos 2π/p is irrational, then we can, for each ξ ∈ R find a sequence N_{j} → ∞, M_{j} → ∞ such that 2N_{j} cos 2π/p+M_{j} → ξ. Thus, 0 is ≡ to a sequence which converges to ξ. Now, cos 2π/p is irrational unless p = 1, 2, 3, 4, 6. To see this, note that, since ω + \overline{ω} = 2 cos 2π/p, ω satisfies the quadratic equation z^{2} − 2(cos 2π/p)z + 1 = 0. So, if cos 2π/p = r/s, where r, s are relatively prime integers, we see that s must be 1 or 2 since otherwise ω is not an algebraic integer. Thus cos 2π/p = 0, ±1, ±1/2 corresponding to p = 4, 1, 2, 3, 6, respectively. So, for p = deg P not equal to 1, 2, 3, 4, or 6, ℳ_{P} contains no nontrivial periodic function.

Fuchs and Gross also find the exceptional cases: If cos 2π/p is rational, then we have, for each z:

z ≡ z + n (for all integers n) ≡ ω^{2}(z + n) + 𝒪(n^{−1})
≡ ω^{2}(z + n) + n + 𝒪(n^{−1}) ≡ ω^{2}z + (ω^{2} + 1)n + 𝒪(n^{−1})
≡ ωz + (ω + \overline{ω})n + 𝒪(n^{−1}).

If ω^{2} + 1 = 0 (that is, p = 4), then letting n approach infinity we get a sequence (all terms of which are equivalent to z) converging to ω^{2}z and thus h(z) = h(ω^{2}z). That is, for p = 4, h(z) = h(−z). If, on the other hand, ω^{2} + 1 ≠ 0, then, since (ω + \overline{ω}) is rational, there are arbitrarily large n such that n(ω + \overline{ω}) is an integer. Letting n → ∞ through such values, we get a sequence converging to ωz all of which are equivalent to z and thus h(z) = h(ωz). The complete theorem is gotten by a few more similar steps and we will not give them here. It leads to the choices P (z) = (z − a)^{p} for arbitrary a.

In [FNS] algebraic curves in the plane were exhibited with the property that the real part of nonconstant meromorphic functions on C cannot vanish on them (examples are the curves given in Cartesian coordinates as the graphs of y = x^{n}, where n ≥ 3). Actually, [FNS] worked with entire rather than meromorphic functions, but the main technique employed, based on invertible germs, applies to the meromorphic problem without changes. The relation of the problem studied in [FNS] to that of this paper can be seen as follows. Suppose, for example, that f is nonconstant and meromorphic on C , and Re (f(z)) = 0 on the curve Γ := {(x, x^{3}) : x ∈ R}. Then Re (f(x + ix^{3})) = 0, x ∈ R so, denoting the meromorphic function \overline{f(\overline{z})} by f^{∗}(z), we have f(x+ix^{3}) = −f^{∗}(x−ix^{3}), x ∈ R. By analytic continuation we have then

f(z + iz^{3}) = g(z − iz^{3}), z ∈ C

where g = −f^{∗}, and this is a relation of type (2) with P (z) = z + iz^{3} , Q(z) = z − iz^{3} . It is important to observe that the failure of curves such as Γ above to be level curves of harmonic functions is a global, not a local feature: There are indeed functions holomorphic (and nonconstant) on a neighborhood of Γ, with real part vanishing on Γ. It is only when we try to make this neighborhood sufficiently large (e.g., the whole plane) that the task becomes impossible if we try to have at worst polar singularities.

L. Flatto [Fl] extended this work on level curves by giving a complete description of some exceptional cases arising in [FNS].

Finally, the paper [Sha] adapted some of the ideas from [FNS] to the study of the functional equation (2).

5. Eliminants

Let P, Q be polynomials with complex coefficients, of degrees p, q, respectively, and let Γ(P, Q) denote the corresponding colored graph introduced in Section 3. Suppose now that z_{1} , z_{2} are the endpoints of a red edge (that is, P (z_{1}) = P (z_{2})) and assume that neither z_{1} nor z_{2} is a critical point of P (that is, both P′(z_{1}) and P′(z_{2}) are nonzero). Consider the function u(s, t) = P (z_{2}+t)−P (z_{1}+s). It is holomorphic on C^{2} and ∂u/∂s, ∂u/∂t are both nonzero at (0, 0). By the implicit function theorem there is a function φ(s) holomorphic on a neighborhood of 0 such that φ(0) = 0 and u(s, φ(s)) = 0. Observe that, since P (z_{2} + φ(s)) − P (z_{1} + s) = 0, we have

φ′(0) = \frac{P′(z_{1})}{P′(z_{2})}.

Thus, φ is an element of the group 𝒢 of invertible germs at 0 considered in Section 2. A similar consideration holds, of course, for “blue” edges. Thus, to each directed edge of Γ(P, Q) whose endpoints are not critical points of P or Q is associated an element φ of 𝒢 .

Suppose now there exist nonconstant meromorphic functions f, g and h such that

(22)  h(z) = f(P (z)) = g(Q(z)).

Let Φ denote a proper closed path in Γ(P, Q) with successive vertices (z_{1}, z_{2}, …, z_{m}, z_{1}) where m ≥ 2 is an even integer. Suppose none of these vertices is a critical point of P or Q. We shall also suppose that no z_{j} is a pole of h. Let φ_{1} denote the element of 𝒢 associated to the edge (z_{1}, z_{2}) by the above procedure, φ_{2} that associated to (z_{2}, z_{3}), etc. up to φ_{m}. Thus, we have the relations

P (z_{1}) = P (z_{2}),  P (z_{1} + s) = P (z_{2} + φ_{1}(s))
Q(z_{2}) = Q(z_{3}),  Q(z_{2} + s) = Q(z_{3} + φ_{2}(s))
P (z_{3}) = P (z_{4}),  P (z_{3} + s) = P (z_{4} + φ_{3}(s))
⋮
Q(z_{m}) = Q(z_{1}),  Q(z_{m} + s) = Q(z_{1} + φ_{m}(s)).

By virtue of (22) we get from these relations

h(z_{1} + s) = f(P (z_{1} + s)) = f(P (z_{2} + φ_{1}(s))) = h(z_{2} + φ_{1}(s))
h(z_{2} + s) = g(Q(z_{2} + s)) = g(Q(z_{3} + φ_{2}(s))) = h(z_{3} + φ_{2}(s))
⋮
h(z_{m} + s) = g(Q(z_{m} + s)) = g(Q(z_{1} + φ_{m}(s))) = h(z_{1} + φ_{m}(s))

and so

\begin{aligned}h(z_{1} + s) & = h(z_{2} + φ_{1}(s)) = h(z_{3} + φ_{2}(φ_{1}(s))) = ⋯ \\ & = h(z_{1} + φ_{m}(φ_{m−1}( ⋯ φ_{2}(φ_{1}(s))))). \end{aligned}

That is, for the germ ψ = (φ_{m} ∘ φ_{m−1} ⋯ ∘ φ_{1}) ∈ 𝒢 we have

(23)  h(z_{1} + s) = h(z_{1} + ψ(s)).

We call ψ the germ associated to the closed path Φ.

Thus, in view of the discussion in Section 2, we can assert: Under the assumptions just made, ψ in (23) is, for some n ≥ 1, an n^{th} root of the identity in the group 𝒢 , and in particular ψ′(0)^{n} = 1. It is not hard to see this is true also if the points z_{j} are poles of h.

Using this, one can sometimes show that, for a given pair of polynomials P, Q there are no nonconstant meromorphic solutions f, g to (22). Essentially this was done in [FNS] for the pair P (z) = z + iz^{m}, Q(z) = z − iz^{m} by finding a closed proper path in Γ(P, Q) for which the associated ψ was not a cyclic element of 𝒢 (in fact ψ′(0) was not a root of unity). We illustrate this technique for P (z) = z^{3} + z, Q(z) = z^{3} − z. To find z_{1} and z_{2} with P (z_{1}) = P (z_{2}) and z_{1} ≠ z_{2} , we seek solutions to the equation P^{#}(z_{1}, z_{2}) = 0, where

(24)  P^{#}(z, w) = \frac{P (z) − P (w)}{z − w}.

Similarly, to find z_{2} and z_{3} with Q(z_{2}) = Q(z_{3}) and z_{2} ≠ z_{3} , we solve the equation Q^{#}(z_{2}, z_{3}) = 0, where

(25)  Q^{#}(z, w) = \frac{Q(z) − Q(w)}{z − w}.

To find a 2-cycle z_{1} , z_{2} , z_{1} , the equations

\begin{aligned}P^{#}(z_{1}, z_{2}) & = z_{1}^{2} + z_{1}z_{2} + z_{2}^{2} + 1 = 0 \\ Q^{#}(z_{2}, z_{1}) & = z_{1}^{2} + z_{1}z_{2} + z_{2}^{2} − 1 = 0 \end{aligned}

would have to be satisfied. Clearly, this system has no solutions. For a 4-cycle, we need distinct points z_{1}, z_{2}, z_{3}, z_{4} so that P (z_{1}) = P (z_{2}), Q(z_{2}) = Q(z_{3}),P (z_{3}) = P (z_{4}) and Q(z_{4}) = Q(z_{1}). This translates into the system

\begin{aligned}z_{1}^{2} + z_{1}z_{2} + z_{2}^{2} + 1 & = 0 \\ z_{2}^{2} + z_{2}z_{3} + z_{3}^{2} − 1 & = 0 \\ z_{3}^{2} + z_{3}z_{4} + z_{4}^{2} + 1 & = 0 \\ z_{4}^{2} + z_{4}z_{1} + z_{1}^{2} − 1 & = 0. \end{aligned}

It can be seen that this implies that z_{1}^{4} + 1 = 0. Beginning with the choice of z_{1} = ζ = e^{πi/4} , the above system then gives rise to the 4-cycle z_{1} = ζ, z_{2} = ζ^{3} , z_{3} = ζ^{5} , and z_{4} = ζ^{7} . Then, there must exist germs φ_{1} , φ_{2} , φ_{3} , φ_{4} satisfying

\begin{aligned}P (z_{1} + s) & = P (z_{2} + φ_{1}(s)) \\ Q(z_{2} + s) & = Q(z_{3} + φ_{2}(s)) \\ P (z_{3} + s) & = P (z_{4} + φ_{3}(s)) \\ Q(z_{4} + s) & = Q(z_{1} + φ_{4}(s)). \end{aligned}

Hence if h, f, g are nonconstant meromorphic solutions to (22), the above chain produces ψ = φ_{4} ∘ φ_{3} ∘ φ_{2} ∘ φ_{1} with h(z_{1} + s) = h(z_{1} + φ(s)). Then there must exist a positive integer m (the valence of h at z_{1} ) so that φ^{[m]} is the identity map and [ψ′(0)]^{m} = 1. Now

ψ′(0) = φ′_{4}(0)φ′_{3}(0)φ′_{2}(0)φ′_{1}(0) = \frac{Q′(z_{4})}{Q′(z_{1})} \frac{P′(z_{3})}{P′(z_{4})} \frac{Q′(z_{2})}{Q′(z_{3})} \frac{P′(z_{1})}{P′(z_{2})}.

Then, from the definition of z_{1}, z_{2}, z_{3}, z_{4} we get

\begin{aligned}ξ = ψ′(0) & = \frac{3(ζ^{7})^{2} − 1}{3ζ^{2} − 1} \frac{3(ζ^{5})^{2} + 1}{3(ζ^{7})^{2} + 1} \frac{3(ζ^{3})^{2} − 1}{3(ζ^{5})^{2} − 1} \frac{3ζ^{2} + 1}{3(ζ^{3})^{2} + 1} \\ & = (\frac{3ζ^{2} + 1}{3ζ^{2} − 1})^{4} = (\frac{3i + 1}{3i − 1})^{4} = \frac{−527}{625} − \frac{336}{625}i. \end{aligned}

But then,

ξ^{2} + \frac{1054}{625}ξ + 1 = 0,

and so ξ (although it is of modulus 1) is not even an algebraic integer and so is not a root of unity. Consequently there can exist no nonconstant meromorphic functions f and g for which f ∘ P = g ∘ Q.

In case, for some proper closed path, the associated ψ turns out to be cyclic, we can nevertheless draw a strong conclusion:

Theorem 5.1. Suppose that Γ(P, Q) contains a proper closed path of length m (no vertices of which are singular points of P or Q) for which the associated ψ is cyclic of order n. Then, to each point z ∈ C there exists a proper closed path of length mn in Γ(P, Q) having z as a vertex.

Proof. The points of C reachable by a “red” edge starting at z_{1} are the roots w of the equation P^{#}(z_{1}, w) = 0. Starting from w, the points reachable by a “blue” edge are the roots ζ of Q^{#}(w, ζ) = 0 (here, P^{#} and Q^{#} are as defined in (24) and (25), respectively). Continuing in this fashion we arrive at the following proposition:

The points w reachable from z by a proper path of length 2k are the roots w of the equation E_{k}(z, w) = 0, where E_{k} (which we shall call the k^{th} eliminant of the ordered pair (P, Q)) is the polynomial obtained by eliminating t_{1}, t_{2}, …, t_{2k−1} from the equations

P^{#}(z, t_{1}) = 0
Q^{#}(t_{1}, t_{2}) = 0
P^{#}(t_{2}, t_{3}) = 0
Q^{#}(t_{3}, t_{4}) = 0
⋮
P^{#}(t_{2k−2}, t_{2k−1}) = 0
Q^{#}(t_{2k−1}, w) = 0.

Returning to the proof of the theorem, suppose we have a proper closed path Ψ ⊂ Γ(P, Q) of length m = 2k and vertices (z_{1}, z_{2}, … z_{2k}, z_{1}) with associated germ ψ which is an n^{th} root of the identity. For a point ζ = z_{1} + t with |t| sufficiently small, the calculations made earlier show that the points

z_{1} + t, z_{2} + φ_{1}(t), z_{3} + φ_{2}(φ_{1}(t)), …, z_{1} + φ_{2k}( ⋯ (φ_{1}(t)) ⋯)

are the vertices of a proper path starting at ζ. The last point is z_{1} + ψ(t) where ψ = φ_{2k} ∘ ⋯ ∘ φ_{1} is, by assumption, an n^{th} root of the identity in 𝒢 . Iterating, we see that z_{1} + ψ^{[r]}(t) is the endpoint of a proper path of length 2kr starting at ζ (recall that ψ^{[r]} denotes the r^{th} iterate of ψ under composition). For r = n, ψ^{[r]} is the identity, so the endpoint is ζ. That is, the path closes.

Consider now the eliminant E_{kn}(z, w). For fixed z, its roots are all points w attainable as the endpoints of proper paths of length 2kn starting at z. The above discussion implies that E_{kn}(ζ, ζ) vanishes for all ζ on a neighborhood of z_{1} , and hence identically. But this implies that, for each ζ ∈ C, there exists a proper path of length 2kn starting at ζ and terminating at ζ.

This theorem allows one to give computer-assisted proofs that certain functional equations (22) have no nonconstant meromorphic solutions. As an example, consider the case P (z) = z^{3} , Q(z) = z^{3} + 3z^{2} + \frac{9}{2}z. To find a 2-cycle z_{1} , z_{2} , z_{1} , the equations

\begin{aligned}z_{1}^{2} + z_{1}z_{2} + z_{2}^{2} & = 0 \\ z_{1}^{2} + z_{1}z_{2} + z_{2}^{2} + 3(z_{1} + z_{2}) + \frac{9}{2} & = 0 \end{aligned}

must be satisfied. This occurs for z_{1} = 3ω/2 and z_{2} = 3ω^{2}/2, where ω = e^{2πi/3} . If ψ is the germ associated with this 2-cycle and ξ = ψ′(0), a calculation shows that ξ = −1. Since this was a 2-cycle and −1 is a second root of unity, we conclude by Theorem 5.1 that if h = f ∘ P = g ∘ Q admits a nonconstant solution, then every point in the plane lies on a 4-cycle. However, the corresponding eliminant E_{4}(z, w), when w is replaced by z, does not vanish identically. Indeed, it equals

15116544(4z^{2} + 6z + 9)^{3}(16z^{4} + 24z^{3} + 72z^{2} − 54z + 81).

Consequently, nearly all points in the plane do not lie on a 4-cycle in Γ(P, Q) and thus h = f ∘ P = g ∘ Q possesses no nonconstant meromorphic solution.

Remark. We have seen that, when Φ is a proper closed path in Γ(P, Q) with vertices (z_{1}, z_{2}, …, z_{m}, z_{1}) and none of the z_{j} is a zero of P′ or Q′, there is associated with Φ a certain ψ ∈ 𝒢 whose cyclicity is necessary for the existence of nontrivial meromorphic f, g satisfying (2). It is easy to see that if ψ is noncyclic, Γ(P, Q) has the weak clustering property. It is also trivial that Γ(P, Q) is clustering if |ψ′(0)| ≠ 1. By virtue of the theorem of C.L. Siegel [Si], a sufficient condition for strong clustering, in case |ψ′(0)| = 1, is (writing ψ′(0) = e^{2πit}, t ∈ R) that there exist positive numbers a, b such that |t − (m/n)| > an^{−b} holds for all integers m, n > 1. This holds, for example, if t is an algebraic irrational number.

6. Remarks and questions

Polynomial solutions. A special case of polynomials P and Q for which there exist polynomial solutions to (2) (that is, the existence of polynomials f and g for which f ∘ P = g ∘ Q) is when P and Q commute under composition. J.F. Ritt [R2] showed, roughly, that P and Q commute only when they are both powers of z or when they are both Chebyshev polynomials of the first kind, or when they are both iterates (under composition) of the same polynomial (here, for simplicity of presentation, we have omitted some roots of unity as well as conjugacy involving linear polynomials).

In another paper written a couple of years earlier, Ritt [R1] provides a useful framework for studying the general question of polynomial solutions to (2) (see [J] and [Fa] for related work). Following the terminology of factorization of integers, Ritt called a polynomial composite if it can be represented as the composition of two polynomials each of degree larger than 1, and prime otherwise. His solution to the problem of representing a polynomial as a composition of prime polynomials is summarized in A and B below: A. Any two decompositions of a given polynomial into prime polynomials con-

tain the same number of polynomials; the degrees of the polynomials in one decomposition are the same as those in the other, except, perhaps, for the order in which they occur. Two decompositions of a polynomial F into the same number of polynomials,

F = φ_{1}φ_{2} ⋯ φ_{r}, F = ψ_{1}ψ_{2} ⋯ ψ_{r}

are called equivalent if there exist r − 1 polynomials of the first degree

λ_{1}, λ_{2}, …, λ_{r−1}

such that

ψ_{1} = φ_{1}λ_{1}, ψ_{2} = λ_{1}^{−1}φ_{2}λ_{2}, …, ψ_{r} = λ_{r−1}^{−1}φ_{r}.

B. If F has two distinct decompositions into prime polynomials, we can pass from either to a decomposition equivalent to the other by repeated switchings of adjacent prime polynomials as follows: φ_{i}φ_{i+1} may be replaced by ψ_{i}ψ_{i+1} precisely when

φ_{i} = λ_{1}π_{1}λ_{2}, φ_{i+1} = λ_{2}^{−1}π_{2}λ_{3}

and

ψ_{i} = λ_{1}ξ_{1}λ_{2}, ψ_{i+1} = λ_{2}^{−1}ξ_{2}λ_{3}

and the pairs π_{1}, π_{2} and ξ_{1}, ξ_{2} are of the following three types:

(a) π_{1} = T_{m}, π_{2} = T_{n}, ξ_{1} = T_{n}, ξ_{2} = T_{m}, (Chebyshev polynomials),

(b) π_{1} = z^{m}, π_{2} = z^{r}g(z^{m}), ξ_{1} = z^{r}[g(z)]^{m}, ξ_{2} = z^{m}, (g any polynomial),

(c) π_{1} = z^{r}[g(z)]^{m}, π_{2} = z^{m}, ξ_{1} = z^{m}, ξ_{2} = z^{r}g(z^{m}), (g any polynomial).

Returning now to our question, suppose that P and Q are given and we seek polynomials f and g for which f ∘ P = g ∘ Q. But then, one must be able to go from the decomposition f ∘ P to g ∘ Q by means of the above “switchings” (a), (b), and (c). Thus, the question of the existence of polynomial solutions can be answered by studying the decompositions of P and Q.

By way of example, consider P (x) := z^{2}(z^{3} + 1) and Q(z) := z^{3} . P and Q do not commute under composition, but there do exist polynomial solutions f(z) := z^{3} , g(z) := z^{2}(z + 1)^{3} to equation (2), in keeping with (c) above.

Rational solutions. Using the asymptotic formula for the roots z of P (z) = P (ζ) (ζ large) given by Lemma 3.1 and the remark following, one can solve many cases of the af Hällström problem mentioned in Section 4 above. We restrict ourselves to one rather simple result, generalizations are straightforward and may be left to the reader.

Theorem 6.1. Let P (z) = z^{p} + az^{p−1} + ⋯, Q(z) = z^{p} + bz^{p−1} + ⋯ be polynomials such that p ≥ 2 and a ≠ b. Then ℳ_{P} ∩ℳ_{Q} contains no nonconstant rational function.

Proof. By estimates from Section 3, for each j ∈ {1, 2, …, p}, P (z) = P (ζ) has a root

z_{j} = ω_{j}ζ + \frac{P (ζ) − P (ω_{j}ζ)}{P′(ω_{j}ζ)} + 𝒪(|ζ|^{−1}),

where ω_{j} = e^{2πij/p}. Simplifying, we get

(26)  z_{j} = ω_{j}ζ + (a/p)(ω_{j} − 1) + 𝒪(|ζ|^{−1}).

In other words, ζ is P -equivalent to each of the numbers z_{j} given by (26), and in like manner it is Q-equivalent to each of the numbers

z′_{j} = ω_{j}ζ + (b/p)(ω_{j} − 1) + 𝒪(|ζ|^{−1}).

Thus, by one P -step with j = 1 followed by a Q-step with j = p − 1, ζ is transformed to (here, we denote ω_{1} by ω, so ω_{p−1} = \overline{ω})

\overline{ω}(ωζ + (a/p)(ω − 1)) + (b/p)(\overline{ω} − 1) + 𝒪(|ζ|^{−1}) = ζ + (\frac{a − b}{p})(1 − \overline{ω}) + 𝒪(|ζ|^{−1}).

Consequently, by a P -step and then a Q-step, ζ is shifted to ζ + c, where c is the nonzero number ((a − b)/p)(1 − \overline{ω}), modulo a 𝒪(|ζ|^{−1}) error. It follows at once that, given any N, if ζ is chosen large enough, there are points

ζ, ζ + c + 𝒪(|ζ|^{−1}), ζ + 2c + 𝒪(|ζ|^{−1}), ⋯, ζ + Nc + 𝒪(|ζ|^{−1})

which are all distinct and are ≡_{P,Q} to ζ. Clearly, no nonconstant rational function can take the same value at all these points, once N is chosen sufficiently large.

In a similar way, we could show under the same hypotheses that ℳ_{P} ∩ ℳ_{Q} cannot contain a nonconstant meromorphic function of sufficiently small order.

Uniformization. The functional equation (2) can also be looked at from a slightly different point of view, very close to that in the papers of Marty, Shimizu and af Hällström already mentioned. Namely, the equations w_{1} = P (z), w_{2} = Q(z) can be viewed as parametric equations of an algebraic variety

V := {(w_{1}, w_{2}) ∈ C^{2} : φ(w_{1}, w_{2}) = 0}

of complex dimension one in C^{2} . (Here φ is some polynomial in w_{1}, w_{2} . Because P and Q are polynomials, this variety (curve) is of genus zero, but it is more natural now to allow φ to be an arbitrary irreducible polynomial).

Our basic question then takes the form: do there exist nonconstant meromorphic (or entire) functions f, g on C such that f(w_{1}) = g(w_{2}) whenever (w_{1}, w_{2}) ∈ V ? Yet another way to look at matters is this: The equation φ(w_{1}, w_{2}) = 0 can be solved for w_{2} = A(w_{1}), where A is an (in general, multi-valued) algebraic function. That there exist nonconstant meromorphic functions f and g with f(w_{1}) = g(A(w_{2})) is the same as requiring: to the given algebraic function A, there corresponds a nonconstant meromorphic function g on C such that g ∘ A remains single-valued under all analytic continuations. The question then arises: Which algebraic functions admit such a “uniformizing” g? Notice that this is quite a different problem from the classical uniformization problem.

146 L.J. Hansen and H.S. Shapiro

References

[AS] Aharonov, D., and H.S. Shapiro: Domains on which analytic functions satisfy quadratic identities. - J. Analyse Math. 30, 1976, 39–73.

[Fa] Fatou, P.: Sur les équations fonctionelles. - Bull. Soc. Math. France, XLVII–XLVIII, 1919–1920.

[Fl] Flatto, L.: A theorem on level curves of harmonic functions. - J. London Math. Soc. (2) 1, 1969, 470–472.

[FNS] Flatto, L., D.J. Newman, and H. S. Shapiro: The level curves of harmonic functions. - Trans. Amer. Math. Soc. 123, 1966, 425–436.

[FG] Fuchs, W.H.J., and F. Gross: Generalization of a theorem of A. and C. Rényi on periodic functions. - Acta Sci. Math. 32, 1971, 83–86.

[H1] af Hällström, G.: Über Substitutionen, die eine rationale Funktion invariant lassen. - Acta Acad. Åbo. Ser. B XV.6, 1946, 3–44.

[H2] af Hällström, G.: Über die Automorphiefunktionen meromorpher Funktionen. - Acta Acad. Åbo. Ser. B XVI.4, 1949, 3–27.

[J] Julia, G.: Mémoire sur la permutabilité des fractions rationelles. - Annales de l’Ecole Normale Supérieure, 39, 1922, 131–215.

[L] Langman, H.: Conformal transformations of period n and groups generated by them. - Amer. J. Math. XLIV, 1922, 54–86.

[M1] Marty, F.: Recherches sur la répartition des valeurs d’une fonction méromorphe. - Ann. Fac. Sci. Toulouse Math. (3) 23, 1931, 183–261.

[M2] Marty, F.: Sur le groupe d’automorphie de certaines fonctions entières. - C. R. Acad. Sci. Paris 195, 1932, 414–416.

[RR] Rényi, A., and C. Rényi: Some remarks on periodic entire functions. - J. Analyse Math. 14, 1965, 303–310.

[R1] Ritt, J.F.: Prime and composite polynomials. - Trans. Amer. Math. Soc. 23, 1922, 51–66.

[R2] Ritt, J.F.: Permutable rational functions. - Trans. Amer. Math. Soc. 25, 1923, 399–448.

[Sha] Shapiro, H.S.: The functional equation f(P (z)) = g(Q(z)) and a problem of A. and C. Rényi. - Studia Sci. Math. Hungar. 1, 1966, 255–259.

[Shi1] Shimizu, T.: On the fundamental domains and the groups for meromorphic functions I–II. - Japan. J. Math. VIII, 1931, 175–304.

[Shi2] Shimizu, T.: On the existence of meromorphic functions which are automorphic with respect to some function-groups. - Proc. Phys.-Math. Soc. Japan (3) 13:10, 1931, 292–296.

[Shi3] Shimizu, T.: On the linear functions of automorphism for meromorphic functions. - Tôhoku Math. J. 38, 1933, 219–224.

[Si] Siegel, C.L.: Iteration of analytic functions. - Ann. of Math. 43, 1942, 607–612 (reprinted in his Werke, Vol. II).

Received 9 April 1992