ON TREES THAT COVER CHAINS OR STARS

F. PAKOVICH

1. Introduction

In this paper, within the framework of the Grothendieck theory of “Dessins d’enfants”, we describe combinatorial conditions for an n-edged plane tree λ to cover a d-edged tree from the classes of “chains” or “stars” (see Fig. 1). Since for a d-edged chain (resp. a d-edged star) a corresponding Shabat polynomial is equivalent to the d-th Chebyshev polynomial T_{d}(z) (resp. to the polynomial z^{d}) these conditions correspond to the requirement that, after an appropriate normalisation, a Shabat polynomial P (z) corresponding to λ admits a compositional factorisation of the form P (z) = T_{d}(P̃(z)) or P (z) = (P̃(z))^{d}. Our main result was announced with a sketched proof in the note [4]. Here we give a detailed proof and discuss some applications.

Figure 1.

Conditions for a tree to cover a chain are related to arithmetics of hyperelliptic curves via a construction proposed in [3]. This construction associates to an n-edged tree λ a hyperelliptic curve H_{λ} defined over the field of modules of λ such that the divisor n(ρ_{∞}^{+} − ρ_{∞}^{−}), where ρ_{∞}^{+}, ρ_{∞}^{−} are the points of H_{λ} over infinity, is principal. The order of the divisor ρ_{∞}^{+} − ρ_{∞}^{−} in the Picard group of H_{λ} is equal to n/d_{c}, where d_{c} is a maximal number such that λ covers a d_{c}-edged chain. This order is invariant with respect to the action of Gal (ℚ̄/ℚ) on trees and just the calculation of this invariant in purely combinatorial terms was the principal motivation for investigations of this paper.

To formulate our main result explicitly let us introduce the following notation. For a tree λ a branch growing from one of its vertices u is a maximal subgraph of λ containing u as a vertex of valency one. The orientation of the sphere induces in a natural way a cyclic ordering of branches of λ growing from the same vertex. We say that two branches of a tree λ are adjacent if they grow from the same vertex and one of them follows the other with respect to the natural cyclic ordering. The number of edges of a branch a is called its weight and is denoted by |a|.

Theorem 1.1. Let λ be an n-edged tree and let d|n. Then λ covers a d-edged chain (respectively, a d-edged star) if and only if the sum (respectively, the difference) of the weights of any two adjacent branches of λ is divisible by d.

It is not hard to see that for an n-edged tree λ the number d_{c} as well as a maximal number d_{s} such that λ covers a d_{s}-edged star are invariant with respect to the action of the group Gal (ℚ̄/ℚ) on trees. Theorem 1.1 provides a purely combinatorial description of these invariants.

Corollary 1.1. For a tree λ the invariant d_{c} (resp. d_{s}) is equal to the greatest common divisor of all sums |a| + |b| (resp. differences |a| − |b|) such that a and b are adjacent branches of λ.

This paper has the following structure. At first we recall the construction from [3] which explains an algebro-geometric meaning of the invariant d_{c} and discuss some situations in which theorem 1.1 and corollary 1.1 may be useful. Then we give conditions for an unicellular dessin λ to cover an other unicellular dessin or to be a chain (a star) in terms of arithmetical properties of the canonical involution of oriented edges of λ. Finally we prove theorem 1.1 and discuss some of its particular cases.

Throughout this paper we will freely use standard definitions and results of the “Dessins d’enfants” theory; for details we refer the reader to the books [1], [2]. Note that by a dessin (resp. a Belyi function) we always mean a clean dessin (resp. a clean Belyi function).

2. Plane trees and n-division points on hyperelliptic curves

In this subsection we recall the construction from the paper [3] which associates to an n-edged tree λ with the field of modules k_{λ} a hyperelliptic curve H_{λ} defined over k_{λ} such that the divisor n(ρ_{∞}^{+} − ρ_{∞}^{−}), where ρ_{∞}^{+}, ρ_{∞}^{−} are the points of H_{λ} over infinity, is principal.

Let λ be a tree and let β(z) be a polynomial from the corresponding equivalence class of Belyi functions. Set

H_{λ} : w^{2} = R(z),

where R(z) is a monic polynomial whose (simple) roots are zeroes of odd multiplicity of the polynomial β(z). In other words, roots of R(z) coincide with vertices of odd valency of the tree λ identified with the preimage of the segment [0, 1] under the map β(z) : ℂℙ^{1} → ℂℙ^{1}.

Proposition 2.1 ([3]). For an n-edged tree λ the curve H_{λ} is defined over k_{λ} and the divisor n(ρ_{∞}^{+} − ρ_{∞}^{−}) is principal. Furthermore, the order of the divisor ρ_{∞}^{+} − ρ_{∞}^{−} in the Picard group of H_{λ} is equal to n/d_{c}, where d_{c} is a maximal number such that λ covers a d_{c}-edged chain.

To make proposition 2.1 useful it is important to have an expression of the order of the divisor ρ_{∞}^{+} − ρ_{∞}^{−} in the Picard group of H_{λ} in purely combinatorial terms and corollary 1.1 provides such an expression. Below we briefly discuss some applications of proposition 2.1.

For any tree λ the total number o_{λ} of vertices of odd valency is even and o_{λ} = 2 if and only if λ is a chain. Furthermore, the genus g_{λ} of H_{λ} is expressed via the number o_{λ} by the formula g_{λ} = (o_{λ} − 2)/2. So, first interesting examples to which the construction above is applicable are trees with 4 vertices of odd valency. This class consists of trees that are homeomorphic to the letter X or to the letter Y (see Fig. 2). An X- or a Y -tree λ leads to an elliptic curve H_{λ}. Note that after a passage to the Weierstrass canonical form the divisor ρ_{∞}^{+} − ρ_{∞}^{−} transforms simply to a point (A, B) of finite order on H_{λ} such that A, B ∈ k_{λ}.

For instance ([3]), the 5-edged Y -tree λ_{1} shown on the Fig. 2 leads to the point (21, −243) of order 5 on the curve w^{2} = 4v^{3} +540v +10665. On the other hand, the 6-edged X-tree λ_{2} leads to the point (3, −16) on the curve w^{2} = 4v^{3} + 84v − 104 where order of (3, −16) equals 3 since d_{c}(λ_{2}) = 2.

Figure 2.

For X- or Y -trees proposition 2.1 permits to use a very powerful arithmetical theory of elliptic curves. So, in the paper [3], as a corollary of the description of groups E(ℚ)_{tors} for elliptic curves over ℚ given by B. Mazur [8], a complete list of Y -trees defined over ℚ was deduced. More general, using the result of L. Merel [7] one can provide a lower bound on the degree of field of modules of an X- or a Y -tree depending only on the invariant d_{c} (see [3]).

An other interesting arithmetical application of proposition 2.1 is a method for finding examples of rational divisors of finite order on curves defined over ℚ (or more generally over number fields) with g > 1; since for curves with g > 1 there are no results similar to ones of B. Mazur and L. Merel, it is interesting what values such an order can take with respect to g (see e.g. [5], [6]). For instance, applying proposition 2.1 to a certain series of trees λ that are determined uniquely by the list of valences of vertices (this implies that k_{λ} = ℚ) one can deduce the following result ([3]): for any m from the interval g + 1 ≤ m ≤ 2g + 1 there exists a hyperelliptic curve of genus g defined over ℚ with a rational divisor of order m. Note that to establish this result we do not have to calculate any Belyi functions, all the information needed can be read out from combinatorics.

3. Conditions for an unicellular dessin to cover an other unicellular dessin or to be a chain or a star

Recall that an edge rotation group ER(λ) of a dessin λ is a permutation group of oriented edges of λ generated by two permutations ρ_{0}, ρ_{1}, where ρ_{0} cyclically permutes oriented edges of λ in the order induced by the orientation of the ambient surface around vertices from which they go and ρ_{1} reverses the orientation of edges. Clearly, ER(λ) can be identified with the monodromy group of a Belyi function corresponding to λ.

Let λ be an n-edged unicellular dessin. Then the permutation ρ_{0}ρ_{1} is a cycle of length 2n. We associate with λ a permutation φ_{λ} ⊂ S_{2n} according to the following rule: enumerate oriented edges of λ by the symbols 0, 1, ... , 2n − 1 in such a way that the cycle ρ_{0}ρ_{1} coincides with the cycle (01 ... 2n − 1) and set φ_{λ}(i) = ρ_{1}(i). So, φ_{λ} coincides with ρ_{1} but we use a special notation to stress the fact that oriented edges of λ are numerated in a specific way. Note that φ_{λ} is defined up to a conjugation by some power of the cycle (01 ... 2n − 1). Clearly, φ_{λ} is a fix points free involution. Conversely, starting from a fix points free involution φ_{λ} defined on the set {0, 1, ... , 2n − 1} we can construct an n-edged unicellular dessin as follows: enumerate in the counter-clockwise direction edges of a 2n-gon by the numbers 0, 1, ... , 2n − 1 and glue them along φ_{λ}. Two such involutions correspond to the same dessin if and only if they are conjugated by some power of the cycle (01 ... 2n − 1).

For convenience we will suppose that the involution φ_{λ} is defined on the whole set ℤ setting for j = 2nl + j̃, where l, j̃ ∈ ℤ, 0 ≤ j̃ ≤ 2n − 1, the value of φ_{λ}(j) equal to 2nl + φ_{λ}(j̃).

Proposition 3.1. Let λ be an n-edged unicellular dessin and let d|n. Then λ covers a d-edged dessin μ if and only if

(1)  φ_{λ}(i + 2d) ≡ φ_{λ}(i) (mod 2d) and φ_{λ}(i) ≢ i (mod 2d)

for any i ∈ ℤ. Furthermore, if conditions above are satisfied then μ is also unicellular and is defined uniquely by φ_{μ}(i) ≡ φ_{λ}(i) (mod 2d).

Proof. Indeed, an n-edged dessin λ covers a d-edged dessin μ if and only if ER(λ) has an imprimitivity system Ω with 2d blocks such that a permutation of the set of blocks of Ω induced by φ_{λ} has no fix points. Since ER(λ) contains the cycle (01...2n − 1) such an imprimitivity system can only be a collection of sets A_{i}, 0 ≤ i ≤ 2d − 1, where A_{i} consists of numbers congruent to i mod 2d. Moreover, since the permutations (01...2n − 1) and ρ_{1} = φ_{λ} generate ER(λ), the collection A_{i}, 0 ≤ i ≤ 2d − 1, is an imprimitivity system if and only if φ_{λ}(A_{i}) = A_{φ_{λ}(i)}. This condition is equivalent to the first condition of (1). The second condition of (1) corresponds to the requirement that the permutation of the set of blocks of Ω induced by φ_{λ} has no fix points.

Corollary 3.1. An n-edged tree covers a d-edged tree if and only if

(2)  φ_{λ}(i + 2d) ≡ φ_{λ}(i) (mod 2d)

for any i ∈ ℤ.

Proof. Indeed, for an n-edged tree λ we have:

(3)  φ_{λ}(i) − i ≡ 2|a_{i}| − 1 (mod 2n),

where a_{i} denote the branch of λ that contains the oriented edge with number i and grows from the starting point of this edge (see Fig. 3).

Figure 3.

Therefore, the equality

φ_{λ}(i) − i ≡ 1 (mod 2)

holds and hence the second condition of (1) is always satisfied. Furthermore, since λ is a tree the dessin μ also is a tree.

Proposition 3.2. Let μ be a d-edged unicellular dessin. Then μ is a chain if and only if

(4)  φ_{μ}(i) − φ_{μ}(i + 1) ≡ 1 (mod 2d)

for any i ∈ ℤ.

Proof. If μ is a d-edged chain then φ_{μ} has the form

(5)  φ_{μ}(j) = \begin{cases}φ_{μ}(0) − j, & if 0 ≤ j ≤ φ_{μ}(0); \\ 2d + φ_{μ}(0) − j, & if φ_{μ}(0) < j ≤ 2d − 1, \end{cases}

where φ_{μ}(0) can be any odd number between 1 and 2d − 1 (see Fig. 4). Therefore, condition (4) is satisfied.

In the opposite direction, summing equalities (4) from i = 0 to i = j − 1 we find that

φ_{μ}(j) ≡ φ_{μ}(0) − j (mod 2d).

It follows that φ_{μ} has the form (5). To establish that φ_{μ}(0) is odd note that if φ_{μ}(0) = 2l for some l, 0 ≤ l ≤ d−1, then (5) implies that φ_{μ}(l) = l in contradiction with the assumption that φ_{μ} has no fix points.

Proposition 3.3. Let μ be a d-edged unicellular dessin. Then μ is a star if and only if

(6)  φ_{μ}(i) + φ_{μ}(i + 1) ≡ 2i + 1 (mod 2d)

for any i ∈ ℤ and μ has at least one vertex of valency 1.

Proof. If μ is a d-edged star then φ_{μ} has the form

(7)  φ_{μ}(j) = \begin{cases}j + (−1)^{j}φ_{μ}(0), & if 0 ≤ j + (−1)^{j}φ_{μ}(0) ≤ 2d − 1; \\ j + (−1)^{j}φ_{μ}(0) − 2d, & if 2d − 1 < j + (−1)^{j}φ_{μ}(0); \\ 2d + j + (−1)^{j}φ_{μ}(0), & if j + (−1)^{j}φ_{μ}(0) < 0, \end{cases}

where either φ_{μ}(0) = 1 or φ_{μ}(0) = 2d − 1 (see Fig. 4).

Figure 4.

Therefore, condition (6) is satisfied.

In the opposite direction, we have:

φ_{μ}(0) + (−1)^{j−1}φ_{μ}(j) = ∑_{i=0}^{j−1}(−1)^{i}(φ_{μ}(i) + φ_{μ}(i + 1)) ≡ ∑_{i=0}^{j−1}(−1)^{i}(2i + 1) (mod 2d).

Since

∑_{i=0}^{j−1}(−1)^{i}(2i + 1) = (−1)^{j−1}j ,

we conclude that

(8)  φ_{μ}(j) ≡ j + (−1)^{j}φ_{μ}(0) (mod 2d).

It follows that φ_{μ} has the form (7). To show that φ_{μ}(0) ≡ ±1 (mod 2d) note that, since μ has at least one vertex of valency 1, the permutation ρ_{0} has at least one fixed point l. Since ρ_{0} is a composition of the permutations ρ_{1} = φ_{μ} and (01...2d − 1), it follows from ρ_{0}(l) = l and (8) that φ_{μ}(0) ≡ ±1 (mod 2d).

Corollary 3.2. An n-edged tree covers a d-edged chain (resp. a d-edged star) if and only if

(9)  φ_{λ}(i) − φ_{λ}(i + 1) ≡ 1 (mod 2d)

(resp.

(10)  φ_{λ}(i) + φ_{λ}(i + 1) ≡ 2i + 1 (mod 2d) )

for any i ∈ ℤ.

Proof. Indeed, if an n-edged tree λ covers a d-edged tree μ then by corollary 3.1 equality (2) holds. Furthermore, if μ is a d-edged chain (respectively, a d-edged star) then by proposition 3.2 (resp. by proposition 3.3) equality (4) (resp. equality (6)) holds. Since φ_{μ}(i) ≡ φ_{λ}(i) (mod 2d), it follows that condition (9) (resp. condition (10)) is satisfied.

In the opposite direction, acting as above we conclude that condition (9) (resp. condition (10)) implies the condition

(11)  φ_{λ}(j) ≡ φ_{λ}(0) − j (mod 2d)

(resp. the condition

(12)  φ_{λ}(j) ≡ j + (−1)^{j}φ_{λ}(0) (mod 2d) ).

Since (11) as well as (12) yields (2) it follows from corollary 3.1 that λ covers some d-edged tree μ. Furthermore, since (9) (resp. (10)) implies (4) (resp. (6)), proposition 3.2 (resp. proposition 3.3 taking into account that any tree has vertices of valency one) implies that μ is a d-edged chain (resp. a d-edged star).

4. Proof of theorem 1.1

In view of corollary 3.2 to prove theorem 1.1 we only must show that conditions (9),(10) are actually equivalent to the conditions described in the theorem. To establish it note that for any i ∈ ℤ taking into account formula (3) we have:

φ_{λ}(i + 1) − φ_{λ}(i) + 1 = (φ_{λ}(i + 1) − (i + 1)) + (i − φ_{λ}(i)) + 2 ≡
≡ 2|a_{i+1}| + 2|a_{φ_{λ}(i)}| (mod 2d),

under the convention that for j = 2nl + j̃, where l, j̃ ∈ ℤ, 0 ≤ j̃ ≤ 2n − 1, we set a_{j} = aj̃. Since branches a_{i+1} and a_{φ_{λ}(i)} are adjacent and any two adjacent branches have such a form for some i ∈ ℤ (see Fig. 5), it follows that condition (9) holds if and only if the sum of the weights of any two adjacent branches of λ is divisible by d. Similarly,

φ_{λ}(i + 1) + φ_{λ}(i) − (2i + 1) = (φ_{λ}(i + 1) − (i + 1)) − (i − φ_{λ}(i)) ≡

≡ 2|a_{i+1}| − 2|a_{φ_{λ}(i)}| (mod 2d)

and therefore condition (10) is satisfied if and only if the difference of the weights of any two adjacent branches of λ is divisible by d.

Figure 5.

Let us remark that the condition of the theorem concerning chains is automatically satisfied at every vertex of λ of valency 2; in particular, an n-edged chain covers a d-edged chain if and only if d|n that corresponds to the decomposition T_{n}(z) = T_{d}(T_{n/d}(z)) for d|n. On the other hand, for a vertex u of odd valency k this condition is equivalent to the requirement that d| |a| for any branch a growing from u. Indeed, the set of all branches growing from u has the form a_{i}, a_{ρ_{0}(i)}, a_{ρ_{0}^{2}(i)}, ..., a_{ρ_{0}^{k−1}(i)} for some i, 0 ≤ i ≤ 2n − 1. Since k is odd, for any j ≥ 0 we have:

|a_{ρ_{0}^{j+1}(i)}| − |a_{ρ_{0}^{j}(i)}| = ∑_{s=0}^{k−2}(−1)^{s}( |a_{ρ_{0}^{j+s+1}(i)}| + |a_{ρ_{0}^{j+s+2}(i)}| ) ≡ 0 (mod d).

Since also

(13)  |a_{ρ_{0}^{j+1}(i)}| + |a_{ρ_{0}^{j}(i)}| ≡ 0 (mod d), j ≥ 0,

it follows that 2|a_{ρ_{0}^{j}(i)}| ≡ 0 (mod d) for any j, 0 ≤ j ≤ k − 1. Hence, either |a_{ρ_{0}^{j}(i)}| ≡ 0 (mod d) or |a_{ρ_{0}^{j}(i)}| ≡ d/2 (mod d). If for all j, 0 ≤ j ≤ k − 1, we have |a_{ρ_{0}^{j}(i)}| ≡ d/2 (mod d) then summing these equalities and taking into account that k is odd we conclude that

n = |a_{i}| + |a_{ρ_{0}(i)}| + ... + |a_{ρ_{0}^{k−1}(i)}| ≡ d/2 (mod d)

in contradiction with d|n. Therefore, d| |a_{ρ_{0}^{j}(i)}| for at least one j, 0 ≤ j ≤ k − 1. It follows now from equalities (13) by induction that d| |a_{ρ_{0}^{j}(i)}| for all j, 0 ≤ j ≤ k − 1.

References

1. The Grothendieck Theory of Dessins D’enfants, ed. L. Schneps, London mathematical society lecture notes series, vol. 200, Cambridge University Press 1994.

2. Geometric Galois Actions, eds. L. Schneps, P. Lochak, London mathematical society lecture notes series, part 1,2, v. 242,243, Cambridge University Press, 1997.

3. F. Pakovitch, Combinatoire des arbres planaires et arithmétique des courbes hyperelliptiques, Ann. Inst. Fourier, 48, No. 2, 1998, p. 1001-1029.

4. F. Pakovich, On trees admitting morphisms onto hedgehogs or onto chains, Russ. Math. Surv. 55, No.3, 593-594 (2000).

5. E. F. Flynn, The arithmetic of hyperelliptic curves, in “Algorithms in Algebraic Geometry and applications”, Birkhauser, (“Progress in Mathematics”, vol. 143), 165-175 (1996).

6. F. Leprévost, Famille de courbes hyperelliptique de genre g munies d’une classe de diviseurs rationnels d’ordre 2g^{2} + 4g + 1, (“Progress in Mathematics”, vol. 116), 107-119 (1994).

7. L. Merel, Bornes pour la torsion des courbes elliptiques sur les corps de nombres, Invent. Math. 124, no. 1-3, 437–449 (1996).

8. B. Mazur, Rational points on modular curves, in Modular functions of one variable, V, Lecture Notes in Math., Vol. 601, Springer, Berlin, 1977, 107-148.