Edward G Belaga
email: belaga@math.u-strasbg.fr

Maurice Mignotte
email: mignotte@math.u-strasbg.frsubm

Walking Cautiously Into the Collatz Wilderness: Algorithmically, Number Theoretically, Randomly

Keywords: 3n+1, or Collatz problem, Collatz and Conway transforms, discrete dynamical systems, pseudo-rundom walks, algorithmic decidability, exponential Diophantine equations, Diophantine approximations

Building on theoretical insights and rich experimental data of our preprints, we present here new theoretical and experimental results in three interrelated approaches to the Collatz problem and its generalizations: algorithmic decidability, random behavior, and Diophantine representation of related discrete dynamical systems, and their cyclic and divergent properties.

Introduction

From many points of view, the challenge posed by the Collatz problem -written down in his notebook by Lothar Collatz in 1937 and known today also as the 3n+1 mapping, 3n+1 problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problemis unique in the history of modern mathematics.

The fact is -even if the claim of the Collatz conjecture can be easily understood and appreciated by children entering secondary school and in its classic simplicity and beauty it belongs more to the Euclidean than to modern era of mathematics -it remains still unresolved, after more than forty years of sustained theoretical and experimental efforts: cf. the annotated bibliography, by Jeff Lagarias, of 200 papers, books, and preprints [START_REF] Lagarias | 3x + 1 Problem: Annotated Bibliograph[END_REF].

Bibliographical Digression. To avoid bibliographical redundancy, all our references with numbers in outward square brackets direct the reader to corresponding items of the Lagarias bibliography, with his generally very helpful succinct comments. Three papers common to the Lagarias and our own bibliography, at the end of the paper, will be referred to by the double references, as in [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3m + d Context[END_REF] The present paper is building on theoretical insights of the short preprint of the first author [START_REF] Belaga | Reflecting on the 3m + 1 Mystery. Outline of a Scenario -Improbable or Realistic ?[END_REF]-]20[ and on rich experimental data presented in our common preprints, [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 1. Primitive Cycles of (3m + d)-mappings[END_REF](vast tables of primitive cycles for 6667 (3m + d)-dynamical systems) and [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 2. Factorization of Collatz Numbers 2 -3 k[END_REF] (factorization of Collatz numbers 2 -3 k , for all 2 ≤ ≤ 114, 1 ≤ k < log 2 3 ,) and interpreted in our preprint [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3m + d Extensions of Collatz Problem[END_REF]-]23[ (long, 62 pages, and dense: cf. the related comment in Lagarias bibliography), -to succinctly report on our new theoretical and experimental results in three domains closely related to the Collatz problem and its generalizations: algorithmic decidability, asymptotical behaviour of corresponding dynamical systems, and Diophantine interpretation of cyclic properties of such systems.

Basic Definitions, Notations, and Problems

The Collatz problem concerns the iteration of the Collatz map T defined on the set of natural numbers:

T : N -→ N; T (n) = n 2 if n is even; 3n+1 2 if n is odd. (1)
The Collatz conjecture states that a T -trajectory starting from any natural number n passes ultimately by 1 (in other words, for some k > 1, T k (n) = 1), to become the cyclic trajectory

C o = 1 → 2 → 1 . (2)
Since any T -trajectory is either divergent or ultimately cyclic (see Definition 2 below), the Collatz conjecture affirms that there exists only one T -cyclic trajectory (or T -cycle), namely, (2) (the cyclic part of the Collatz conjecture) and that there exist no divergent trajectories (the divergent part of the Collatz conjecture). It goes without saying that both Collatz sub-conjectures are still open.

The Collatz map being defined by the algorithm (1) and, as a result, the Collatz problem being reminiscent of the halting problem for Turing machines, one cannot exclude the unsolvability option to which we now proceed.

Following the trodden path of tweaking with difficult problems by looking at their generalizations, John H. Conway has discovered in 1972 ]52[ a general and, in a sense, the most natural framework for Collatz-type problems, the Conway map on Z (reinvented twice, first, in ]37[ as periodically linear or congruential function, then in ]123 [, ]124[, as generalized Collatz map, and extended in [START_REF] Belaga | Reflecting on the 3m + 1 Mystery. Outline of a Scenario -Improbable or Realistic ?[END_REF]-]20[ to piecewise periodically linear functions defined on subsets Z d of integers relatively prime to d ≥ 2). Definition 1 Let p ≥ 2 be a natural number and

M p = {m 0 , m 1 , . . . , m p-1 } ∈ N p , R p = {r 0 , r 1 , . . . , r p-1 } ∈ Z p (3)
be two p-tuples of, respectively, natural numbers and integers, such that

for all i = 0, . . . , p -1, gcd(m i , p) = 1 & r i ≡ im i (mod p). (4)
(1) The corresponding Conway (M p , R p )-map T = T Mp,Rp is defined on the set Z of integers as follows:

T : Z -→ Z; T (n) = m i n -r i p , if n ≡ i (mod p). (5)
(2) A multiplicative Conway M p -map corresponds to M p -tuples for which r i = 0, for all i ∈ [1, p].

Notational Agreement 1 For notational simplicity, we use the same symbol T for all general and special Conway maps, indicating when necessary which particular map, such as Collatz (1) or multiplicative Conway, or anything else, is specifically discussed.

Conway proved in ]52 [, ]53[ that multiplicative Conway maps are universal computational devices able to simulate Turing machines; we call such maps, both multiplicative and general, universal Conway maps. Their existence implies that at least for some of the Conway maps the Collatz-type problem is equivalent to the halting problem for a universal Turing machine ]37[ and thus, unsolvable.

Conway's theoretical framework represents the most natural and, one can say, ultimate generalization of the Collatz problem, and his undecidability result is as fundamental to this framework as the Davis-Putnam-Matiyasevich solution of Hilbert's tenth problem [START_REF] Jones | Proof of Recursive Unsolvability of Hilbert's Tenth Problem[END_REF] Let D be the set of natural numbers relatively prime to 6; for any d ∈ D, called the shift number of the map, define

T = T d : N -→ N; T = T d (n) = n 2 if n is even; 3n+d 2 if n is odd. (6)
In the above notations (1), T = T 1 and T d = T M2,R2 [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 1. Primitive Cycles of (3m + d)-mappings[END_REF], with M 2 = {1, 3}, R 2 = {0, -d}. This makes clear how far "below" we are with the (3m+d)-extension of the Collatz map from the complexity of the general Conway case and its universal unsolvability. It does not preclude, of course, the possibility that the (3m + d)-problem and even the original Collatz problem might be still unsolvable for less universal reasons.

Incidentally, the question of what is the minimal p > 2 which guarantees the existence of universal computational devices T Mp,Rp (cf. ]121[) remains an open problem -the first one from a series of open problems which relate the arithmetic properties of the definition of a Conway map to the unsolvability of corresponding halting conditions to the pseudo-randomness of the behaviour of trajectories of the corresponding discrete dynamical system (cf. Problems and Observations (1) below).

3 The Unsolvability Option and Its Far-Reaching Formal and Heuristic Ramifications

One usually quotes (with the first reference apparently traced to ]104[) the well-known, startling remark of the late Paul Erdös concerning the Collatz problem, "Mathematics is not yet ready for such problems," to certificate its exceptional difficulty. But it could be also perceived as a hint at an exceptionally rich mathematical "harvest" which we might expect from the sustained efforts to solve this problem. This is the point of the following informal theses inspired by a certain vision, as if from an outer space, of the Diophantine equations theory, this mountainous "landscape", with its lovely oases, its deserts, its "Himalayas" challenging skills and perseverance of "Diophantine climbers", and its forbidding, impenetrable "peaks", unsolvable Diophantine equations. We hope that the theoretical and experimental results presented in the following sections will well illustrate the suggestive power of these informal insight.

Thesis 1. Out of the Diophantine Equations Wilderness, with a Lesson: The presence of unsolvability phenomena in a formally complete mathematical framework brings with it the emergence of a great many isolated and, at first glance, mutually unrelated "mountainous islands", i.e., beautiful, deep, rich in consequences, and difficult "local", i.e., problem-oriented theories, with extremely complicated, lengthy proofs, often preceded and accompanied by intricate, bulky computations, of the most important results and with eventual generalizations and unifications of such local theories representing major theoretical breakthrough. Or, for short, the proximity of unsolvability "peaks" leads to enormous problematic variability and related to it (i) abrupt conceptual discontinuity, (ii) novel meaningfullness, (iii) startling logical complexity. Against such a background, (iv) computational experiment becomes a necessary and respected part of investigations, (v) stimulating the development of new powerful, both general and special, problem oriented methods.

Thesis 2. Into the Collatz Wilderness, to Learn the Lesson:

There is no doubt that the unsolvability properties of problems related to iterations of number-theoretical functions are by their very iterative, "dynamic" nature much more immediate and explicit than those of "static" by their definition Diophantine problems (whose unsolvability is invariably proved by long and intricate translations into the language of recursive functions). It means that the Collatz-related landscape conceptualized by Conway's formal framework is incomparably more "steep", irregular, unpredictable, and inaccessible than the Diophantine one, -testifying in a most unambiguous way to the five aforementioned phenomena: unpredictable variability, pertinence of vast computational experiments, local discontinuity, meaningfulness, complexity. Wanted: formal methods of noticeable power.

To illustrate these local discontinuity, meaningfulness, complexity attributes, let us remind the reader that, back in 1932, Lothar Collatz has written down in his notebook, alongside his (1) map, another -as we call it today -Conway map:

For M 3 = {2, 4, 4} R 3 = {0, 1, -1} define: T (n) = T M3,R3 (n) =    2n 3 if n ≡ 0 (mod 3); 4n-1 3 if n ≡ 1 (mod 3); 4n+1 3 if n ≡ 2 (mod 3). (7)
It is easy to verify that T acts on natural numbers as a one-to-one map; namely, it sends bijectively the sets of natural numbers divisible by 3 with the remainders 0, 1, 2 onto, respectively, the set of even natural numbers, and the sets of odd natural numbers divisible by 4 with the remainders 1 and 3. The map has 1 as its only fixed point, T

   τ T (n) = n = T 0 (n), n 1 = T (n), n 2 = T 2 (n) = T (T (n)), . . . τ T (n) is a T cycle of the length ≥ 1 ⇐⇒ n = T (n) = n, ∀r.(1 ≤ r < ), n r = T r (n) = n . (8)
(2) A non-cyclic T -trajectory starting at n is called ultimately -cyclic or, for short, ultimately cyclic, if there exist j ≥ 1 and ≥ 1, such that the T -trajectory starting at n j = T j (n) is -cyclic.

(

) A T -trajectory τ T (n) starting at n is divergent, if it is neither cyclic, nor ultimately cyclic. Or, equivalently, if |T j (n)| j→∞ →∞. 3
(4) We associate with the map T = T Mp,Rp its contraction-expansion index, or for short, conex-index

µ(T ) = m 0 • • • m p-1 .
(5) We call the inequalities µ(T ) < p p and µ(T ) > p p the contraction and, respectively, expansion conditions, and the corresponding Conway maps contracting and expanding, respectively. 4). (i) If T satisfies the contraction condition, µ(T ) < p p , then all trajectories τ T are ultimately cyclic. In particular, there is at least one cycle.

(ii) If T is expanding, µ(T ) > p p , then almost all trajectories τ T are divergent, except possibly for an exceptional set Q of density zero, which means that for all n from Q,

# n ∈ Q ; ; -X ≤ n ≤ X = o(X).
In particular, there is at least one divergent trajectory.

(iii) The number of cycles is finite.

(iv) If the trajectory τ T (n) is divergent, then the iterates are uniformly distributed (mod p q ) for each q ∈ N:

∀j ∈ [0, p q -1], lim N →∞ ; 1 N +1 ; # i ≤ N ; ; T i (n) ≡ j (mod p q ) = p -q .
Our principal concern lies here with the first, second, and third Matthews-Watts conjectures. An advanced version of the third conjecture limited to (3m + d)-maps will be discussed in Section 6. In the next section, Section 5, we shall exhibit four computational examples confirming the Third Matthews-Watts Conjecture, with the first two confirming the First Conjecture and with the two others confirming the Second Conjecture.

Today, the main heuristic argument in favour of the expected absence (the alternative formulation of the First Conjecture) or presence of divergent trajectories for, respectively, contracting and expanding maps is probabilistic, a particular case of the general approach to Conway dynamical systems (3)-( 5) as pseudorandom walks simulated by corresponding Markov chains (cf., e.g., ]112[). This and similar probabilistic heuristics are typically corroborated by empirical data.

Expected to be implied by the underlying pseudo-random mechanisms, the First Matthews-Watts Conjecture, in its turn, has a striking implication concerning the problem of algorithmic universality of the corresponding maps and unsolvability of related halting problems : cf. Theorem 2 below.

And vice versa, in the case of the Second Conjecture, the algorithmic universality considerations are implying a nontrivial property of dynamical systems produced by universal Conway maps : cf. Theorem 3 below.

The second of the following three theorems is of conditional nature: it recovers algorithmic implications from the first two Matthews-Watts conjectures implied by the character (supposedly, pseudo-random) of walks over Conway-type dynamical systems.

Theorem 1 Conway's unsolvability theorem implies that it is undecidable in the general case whether a trajectory starting at an integer is ultimately cyclic.

Outline of the proof. According to a classic cycle detection device, remarkable for its simplicity, for maps T acting on the set of natural numbers, the trajectory starting at n ∈ N is ultimately cyclic iff

for some k ≥ 1, T 2k (n) = T k (n) . ( 9
)
The undecidability of the verification of the equality (9) for a general Conway map and a given n is an easy corollary of the undecidability of the halting problem for such maps.

Theorem 2 The First Matthews-Watts conjecture implies that contracting Conway maps are not universal.

Outline of the proof. According to the conjecture, all trajectories are ultimately cyclic. Thus, for contracting maps, an equivalent of Turing halting problem can be always resolved. According to Theorem 1, such maps are not universal.

Theorem 3

The exceptional set M T of a universal (and, thus, according to Theorem 2, expanding) Conway map T is nonempty, infinite, and recursively innumerable.

Outline of the proof. (1) A universal map T can be "pre-programmed" to simulate any other map, including contracting ones and those that have cyclic and ultimately cyclic trajectories. Thus, such a map should have at least one cycle and related ultimately cyclic trajectory or trajectories. Hence,

Q = Q T = ∅.
(2) Elements of the set Q are numbers n ∈ Z belonging to cyclic or ultimately cyclic T -trajectories. T being a universal map, the problem of deciding whether or not n ∈ Q is unsolvable.

Problems and Observations. (1)

In the eventuality Matthews-Watts conjectures are true, Theorem 2 relates the numerical characteristics p, p p and µ(T ) of a Conway map T = T Mp,Rp to its algorithmic universality and solvability properties. There are not known at present any other numerical criteria for such properties involving the T -parameters p, m 0 , . . . , m p-1 , r 0 , . . . r p-1 . In particular:

(i) What is the minimal value of p yielding a universal Conway map T = T Mp,Rp ? (ii) If T 1 , T 2 are two Conway maps with the identical parameters p = p 1 = p 2 , µ = µ(T 1 ) = µ(T 2 ) but two substantially different sets of multiplicative coefficients, M T1 = M T2 , ("substantially different" signifies here that they remain different after any permutation of their elements), how this difference affects their dynamical and algorithmic properties ? We present in Section 5 experimental data concerning two substantially different expanding Conway maps with the identical parameters p and µ, p = 3, µ = 28 > p p = 27, but apparently quite different expanding dynamics.

(2) If the Second Matthews-Watts conjecture holds, it would strongly suggest that the unsolvability of the halting problem for Turing machines and of its numerous analogues does not a priori preclude the possibility of our gaining some substantial, if not crucial knowledge about the outcome of related recursive procedures for "almost all" input data.

(3) On the other hand, according to the above Theses 1, 2 (Section 3), the particular methods needed for formally extracting such a knowledge might heavily depend on the formal context of related problems, with the logical complexity and length of corresponding proofs growing with the strength and generality of such problems.

The First Three Matthews-Watts Conjectures and Their Experimental Confirmation

We have carried a series of about two dozen computer experiments for both contracting and expanding Conway maps, with the parameters µ chosen to keep to the absolute minimum, respectively, the positive (i.e., guaranteeing the contraction condition) and negative (i.e., guaranteeing the expanding condition) difference between p p and µ, |p p -µ| = 1. This choice has the specific purpose of creating "escape" conditions for subsequent iterations, with the expected emergence in the contraction case of very long cycles and even (wishful thinking? cf. our commentary to (12) divergent trajectories, as well as an abundance of ultimate cyclic trajectories in the expanding case.

To simplify calculations without compromising neither their generality, nor the plausibility of our conclusions, we have restricted our choice to only such Conway maps T which preserve the set N of natural numbers:

T : Z -→ Z, Image T (N) ⊂ N T = T | N : N -→ N.
Our experiments have basically confirmed the first three of Matthews-Watts conjectures.

Experimental study of the First and Third Matthews-Watts Conjectures : The contracting case.

Here are two examples of contracting Conway maps:

(i) T (1) 3 = T M 1 3 ,R 1 3 , M 1 3 = {1, 13, 2}, R 1 3 = {0, 1, 1}, µ(T (1)
3 (11)

) = 26 < 27 = 3 3 ; (ii) T 4 = T M4,R4 , M 4 = {1, 17, 5, 3}, R 4 = {0, 1, 2, 1}, µ(T 4 ) = 255 < 256 = 4 4 . ( 10
) (i) T = T (
(ii) T = T 4 . The first Matthews-Watts conjecture has been verified for all natural numbers n less than 10 6 , with all trajectories ultimately entering one of the following 7 cycles:

                   C 1 T4 = {min = 1, period = 2, max = 4}, C 2 T4 = {2, 1, 2}, C 3 T4 = {101, 37, 103227}, C 4 T4 = {16577, 8913, 300251686701126925034779159828370513 > 3 • 10 35 }, C 5 T4 = {62210, 1332, 17543625459549387843430332}, C 6 T4 = {198110, 452, 1532835289361956287}, C 7 T4 = {154633, 452, 66726343095755471773728427}. ( 12
)
The presence of the very long, extremely far-straying cycle C 4 T4 is due, without any doubt, to the weakness of the contracting condition (10(ii)).

This experiment has most successfully confirmed the First (and, incidentally, Third) Matthews-Watts Conjecture(s). And, exactly for this reason, it has been a serious disappointment for the authors of the present paper: it did not live up to their expectations to eventually refute the First Matthews-Watts Conjecture by producing strong "escaping" conditions for the emergence of a divergent trajectory in a normatively contracting environment.

Experimental study of the First and Third Matthews-Watts Conjectures : The expanding case. The presence of divergent trajectories considerably complicates experimental studies: in this case, one can be only reasonably, not absolutely sure, following an apparently divergent track even for an extremely long time, that it will not ultimately turn out to be non-divergent.

Here are two examples of expanding Conway maps studied experimentally by us:

(i) T (2) 3 = T M 2 3 ,R 2 3 , M 2 3 = {1, 4, 7}, R 2 3 = {0, 1, 2}, µ = 1 • 4 • 7 = 28 > 27 = 3 3 ; (ii) T (3) 3 = T M 3 3 ,R 3 3 , M 3 3 = {2, 2, 7}, R 3 3 = {0, -1, 2}, µ = 2 • 2 • 7 = 28 > 27 = 3 3 . ( 13
)
In both cases, we have either traced T -trajectories τ T (n) starting at natural numbers n up to one million, n ∈ [1, 10 6 ], until they enter a cycle, or have computed their 50000 iterations, with the value of the maximal computed member n T ,max of the trajectory τ T (n) ranging, in the first case, from 10 88 to 10 587 , and in the second case, from 10 92 to 10 559 :

∀n ∈ [1, 10 6 ] (i) T = T (2) 3 , 10 88 < T n T ,max (n) < 10 587 ; (ii) T = T (3) 3 , 10 92 < T n T ,max (n) < 10 559 . ( 14
) (i) T = T (2)
3 . Three T -cycles have been recovered:

       C 1 T (2) 3 = {min = 2, period = 1, max = 2}, (2 being fixed point), C 2 T (2) 3 = {7, 11, 22}, C 3 T (2) 3 = {10, 3, 30}. (15)
Following the definition of Matthews-Watts Conjecture 4.2(ii), we associate with the map T = T (2) 3 , two complementary sets of natural numbers, D and Q, giving rise, respectively to divergent and convergent trajectories:

n ∈ D T ⇐⇒ τ T (n) is divergent ⇐⇒ lim k→∞ T k (n) = ∞ ; D ∪ Q = N ; n ∈ Q T ⇐⇒ τ T (n) is ultimately cyclic ⇐⇒ ∃N = N (n) , ∀k ≥ 1 . T k (n) < N . (16)
Our computations show that on the interval 1 ≤ n ≤ 10 6 , the set Q T is much more "massive" than D T . However, even on this relatively small interval, the density of D T is steadily growing, in accordance with the prediction of the Second Matthews-Watts Conjecture, as makes clear the below list of 20 numbers, (17)(ii), representing the number of elements of D T (2) 3 on the 20 consecutive intervals of the length 50000:

This reduces the study of non-primitive T d -cycles to the study of their underlying primitive T q -cycles, for all proper divisors q of d. In contrast to the first two conjectures of Lagarias, the following conjecture has no immediately apparent (3n + 1)-precursor or analogue:

Conjecture 3 For any n ∈ D, the set of primitive T d -cycles, d ∈ D (n) , meeting n is infinite.
We interpret this conjecture below as dual to the first conjectures of Lagarias, Conjecture 2, with the emerging disparate duality between dand n-related phenomena being an important new and allpervading intuition behind the present study. This duality finds its precise formal description in the related Diophantine framework, Theorem 4(4).

Experimental Study of the Conjectures and Its Cogency: [START_REF] Belaga | Probing into the 3m + d World[END_REF] We have systematically studied within the range 1 ≤ d ≤ 19999, d ∈ D, all 6667 discrete dynamical systems D d generated by (3m + d)-maps: see [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 1. Primitive Cycles of (3m + d)-mappings[END_REF]. These computations have confirmed two parts of Conjecture 2, albeit inevitably with different degrees of certainty [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3m + d Extensions of Collatz Problem[END_REF]-]23[.

(2) Moreover, the numerical data obtained in our computations suggest the plausibility of previously unknown general laws of the iterative behaviour of (3m + d)-maps: see for detais [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3m + d Extensions of Collatz Problem[END_REF]-]23[. And based on these calculations, the first author has advanced and proved a new deep conjecture concerning a sharp effective upper bound to the minimal member (perigee) of a primitive cycle [Belaga 2003].

(3) Withing the chosen range, Conjecture 2(1) has been fully confirmed: all such systems D d have at least one primitive cycle.

(4) The confirmation of Conjecture 2(2) is more problematic: a priori, no quantity of computations could confirm that a certain (sub)set is finite. Thus, the plausibility of such a claim hinges on the quality of availble evidence that the search was exhaustive. Such an evidence is discussed in our detailed report [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3m + d Extensions of Collatz Problem[END_REF]-]23[, to justify the claim that in every one of 6667 cases we have localized all existing (3m+d)-primitive cycles:

(i) The total number of such cycles is equal to 42765. (5) Compared to the above case of Conjecture 2(2), our claim of the confirmation of Conjecture 3 is even more problematic: no quantity of (always finite) computations could confirm that a certain (sub)set is infinite ! Still, taking into account the total number of memberships in primitive cycles of corresponding numbers n ranging from 18 to 452 (for n = 1) -a relatively small for the total number 42765 of primitive cycles found in the chosen range, we have had a strong evidence of the plausibility of Conjecture 3.

The Shift-Member Disparate Duality

Our theoretical approach to the cyclic structure of dynamical systems D d is based on the concepts of primitive membership and disparate duality between related properties of shift and member numbers.

The impetus for this approach comes from the comparison between the above Conjectures 2 and 3, which is interpreted here as one dual conjecture about projections of the set of memberships. This crucial shift in the perspective becomes possible after the technical passage from primitive cycles to their odd frames, the (obviously, nonempty) cycle of their odd members n ∈ D.

Definition 4 (1) For any positive integer n ∈ N, define the number Odd(n) obtained by factoring out of n the highest possible power of 2; thus Odd(n) is odd and m = Odd(n) • 2 j , for some j. Hence the notation:

∀n ∈ N , ν 2 (n) = max j ≥ 0 ; ; n • 2 -j ∈ N , n = Odd(n) • 2 ν2(n) . ( 21
) (2) Let τ d (n) = {n, T d (n), T d (T d (n)), .
. .} be a primitive T d -trajectory starting at an odd n not divisible by 3 and relatively prime to d, n ∈ D [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 2. Factorization of Collatz Numbers 2 -3 k[END_REF] . The full sequence of odd members, in the order of their appearance in τ d (n) is called the odd frame of τ d (n) and denoted by Oddframe(n, d), with the full sequence of the corresponding exponents of 2, denoted by Evenframe(n, d) (21):

∀n, d ∈ D,            (i) τ d (n) = n, n 1 , n 2 , . . . ; (ii) Evenframe(n, d) = p 1 , p 2 , . . . ⊂ N, ∀j ≥ 1, ∀j ≥ 1, p j = ν 2 (3n j-1 + d) ≥ 1; (iii) Oddframe(n, d) = m 0 = n, m 1 , m 2 , . . . ⊂ D (d) , ∀j ≥ 1, m j = Odd(3m j-1 + d) = n rj , r j = 1≤i≤j p i . (22)
(3) For a T d -cycle C = τ d (n) of the length , Oddframe(C) is a cycle of the period (oddlength) k, 1 < k < , satisfying the following obvious inrequality implied by the cyclic condition (8(i)): (3) From the Diophantine Formulae to their Membership Interpretation. Let k ≥ 2 and P = p 1 , . . . , p k ⊂ N k be a k-tuple of positive integers satisfying the inequality

(i) = p 1 + • • • + p k ≥ k • log 2 3 ⇐⇒ B k, = 2 -3 k > 0; (ii) Λ = {(k, ) ∈ N 2 | ≥ k • log 2 3 } . ( 23
= |P| = p 1 + • • • + p k ≥ k • log 2 3 , (26)
and let the numbers A, B, F, G, H be defined as in (22). Then F, G is a primitive membership.

Why the Diophantine Interpretation of the Collatz and Lagarias Conjectures Strengthen Their Plausibility

We will need a more descriptive presentation of the above diophantine formulae for primitive memberships:

Λ = {(k, ) ∈ Λ | gcd(k, ) = 1} , Λ 0 = {(k, ) ∈ Λ | = k • log 2 3 } , Λ0 = Λ ∩ Λ 0 . (27) (2
p 1 + . . . + p k-1 < , (29)
the following number belongs to A:

A = A(P) = 3 k-1 + 3 k-2 • 2 p1 + . . . + 3 • 2 p1+...+p k-2 + 2 p1+...+p k-1 . ( 30
)
By definition, members of Collatz corona are odd positive integers not divisible by 3.

(3) The Collatz corona corresponding to a simple, narrow, or simple narrow pair (k, ) is called, respectively, simple, narrow, simple narrow.

Theorem 5 (1) Collatz corona A k, is a one-element set iff k = 1 (28).

(2) Otherwise, Collatz corona A k, is a finite set of mutually distinct positive integers not equal to he Collatz number B = B k, , and its cardinality α k, = #A k, is given by the following formula: if m = 1, (-1) q if m is the product of q distinct primes, 0 , if m is divisible by a square of a prime.

∀(k, ) ∈ Λ      α k, = #A k, = -1 k-1 , if gcd(k, ) = 1,
(32)

The low part of the formula (31), defined for pairs (k, ) with the property gcd(k, ) > 1, is universal and covers -but also obscures -the simple upper case gcd(k, ) = 1.

(3) The below lower and upper bounds to members A of Collatz corona are sharp:

∀(k, ) ∈ Λ ∀A ∈ A k, 3 k-1 < A k, ≤ A ≤ A k, < 2 -k+1 • 3 k-1 ; A k, = 3 k -2 k , A k, = 2 -k+1 • 3 k-1 -2 k-1 + 3 k-1 . (33)
The first conjecture of Lagarias is equivalent to the following claim: for any d ∈ D, there exists at least one and not more than a finite number of pairs (k, ) ∈ Λ, such that, for some number from the (k, )-corona, the equality holds

d = B k, gcd(B k, , A) , A ∈ A k, . (38)
(9) The second conjecture of Lagarias is equivalent to the following claim: for any n ∈ D, there exist an infinite number of pairs (k, ) ∈ Λ, such that, for some number from the (k, )-corona, the equality holds

  -]22[, for the 1999 paper of the authors. Not less surprisingly, the Collatz problem and its immediate elementary generalizations ]21[, ]22[, ]23[, ]34[, ]37[, ]52[, ]53[, ]85[, ]105[, ]116[, ]121[, were shown to be relevant in one or another substantial way to the deepest open questions in algorithmic theory ]20[, ]52[, ]53[, ]98[, ]121[, ]131[, ]155[ and mathematical logic ]56[, ]116[, ]119[, Diophantine approximations and equations theory ]21[, ]22[, ]23[, ]36[, ]133[, ]154[, ]158[, ]159[, ]160[, ]165[, p-adic number theory ]1[, ]27[, ]28[, ]43[, ]137[, ]138-139[, multiplicative semigroup theory ]64[, ]13[, ]107[, discrete and continuous dynamical systems theory ]44[, ]59[, ]95[, ]115[, ]134[, ]141[, discrete (random walks) ]32[, ]66, 67[, ]147[, ]182[ and continuous stochastic processes theories ]78[, ]96[, ]97[, ]106[, ]111[, ]112[, ]149[, ]161[, ]162[, ]163[, ]178[, ]181[, ]185[.

= 1 ,

 1 and the iterations of T starting at 2 and 4 yield cycles of the length two and five, respectively. On the other hand, with all ultimately cyclic trajectories of bijective maps being cyclic, it remains an open question whether the trajectory starting at 8 is divergent or cyclic -another open Collatz problem. Neither of the known methods used in the studies of the (first) Collatz problem is helpful in elucidating the iterative behaviour of the map T . And if true, the divergence of the T -trajectory starting at 8 would represent a modest confirmation of the only existing conjecture dealing with general expanding Conway maps: see Section 5 below. The following definitions formalize the notions of cyclic, ultimatiely cyclic, and divergent trajectories: Definition 2 (1) For a given Conway map T = T Mp,Rp , the T -trajectory and T -cycle of length (cyclic, for short) starting at n are defined as follows:

1 ) 3 . 3 =

 133 The verification of the conjectures on the interval n ∈ I = [1, 10 6 ]. One cycle has been recovered, with all other trajectories starting at numbers from the interval I ultimately entering this cycle: C T (1) {min = 1, period = 14, max = 186}.

Conjecture 2 ( 1 )

 21 Primitive trajectories are numerous: according to (19), the T d -trajectory starting at a natural number n relatively prime to d is primitve. But how many of such trajectories are primitive cycles? More specifically, do primitive cycles exist for all systems D d , d ∈ D? And what are the chances of an integer n ∈ D (d) to belong to such a cycle? These are the subjects of the original conjectures of Lagarias ]105[. Existence of a Primitive T d -cycle. For any d ∈ D, there exists at least one primitive T d -cycle. (In the case of the Collatz problem, it is the cycle C o (2). Matthews-Watts conjecture 1(i) represents a far-reaching generalization of the present conjecture.) (2) Finiteness of the Set of Primitive T d -cycles. For any d ∈ D, the number of primitive T d -cycles is finite. (In the case of the Collatz problem, one expects C o to be the only primitive cycle. This conjecture, too, finds in Matthews-Watts conjecture 1(iii) its far-reaching generalization.)

(

  ii) The numbers ω(d) of such cycles for individual systems are ranging from ω(d) = 1, for 1481 systems D d out of 6667, to 2, for 1507 of them, to 3, for 1005, etc., to 944 for the system D 14303 . The following table lists eleven systems D d with the numbers of primitive cycles bigger than 160: d = 7463 18359 7727 15655 10289 9823 17021 14197 13085 6487 14303 ω(d) = 162 164 198 207 214 241 258 329 335 534 944 (20)

)

  We denote by Λ (23(ii)) the set of pairs of natural numbers (k, ) satisfying the inequality (23(i)), and we call B k, the Collatz (k, )-number. Number theoretic properties of Collatz numbers are of crucial importance for the behavior of the dynamical systems D d ; we have studied the factorizations of Collatz numbers experimentally, in the interval 2 ≤ ≤ 114, for all (k, ) ∈ Λ: see[START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 2. Factorization of Collatz Numbers 2 -3 k[END_REF].

)

  Let n, d ∈ M be a primitive (k, )-membership with the corresponding Collatz number B. We associate with n, d ∈ M its Collatz corona A = A k, , a finite set of natural numbers depending only on the Oddlength and length of n, d ∈ M, as follows: (a) If k = 1, then A 1, = {1} . (28) (b) If k > 1, then for any aperiodic (k -1)-tuple P = p 1 , . . . , p k-1 of positive integers satisfying the inequality (25)

1 kr - 1

 11 r| gcd(k, ) µ(r) • r -, otherwise. α k, ≡ 0 (mod k).

( 4 )( 5 )( 6 )( 7 )

 4567 Since the function a in the definition (25) does not actually depend on the k-th component p k of the correspnding Collatz configuration, its values for two k-configurations of different lengths can be equal. More precisely,∀(k, ) ∈ Λ ∀j ≥ 1 , A k, ⊂ A k, +j .(34) With the exception of the trivial case, corresponding to the primitive T 1 -cycle C 0 (cf. (2) and the above statement (1)),k = 1, = 2, A 1,2 = {1}, B = 1 ,no Collatz number ever belongs to the respective Collatz corona and, if k ≥ 4, it is located below the upper bound (33) of the corona,∀(k, ) ∈ Λ , B = B k, < 2 < A k, , if k ≥ 4 .(35) Moreover, if (k, ) is not narrow, then B is located above the low bound (33) of the corona:∀k ≥ 1. (k, ) ∈ Λ \ Λ 0 =⇒ B = B k, = 2 -3 k > A k, = 3 k -2 k . (36)This is no more the case, if (k, ) is narrow:∀k ≥ 1. (k, ) ∈ Λ 0 =⇒ B = B k, = 2 -3 k < A k, = 3 k -2 k . (37)The original, 3n + 1 Collatz conjecture is equivalent to the following claim: for any nontrivial pair (k, ) ∈ Λ \ {(1, 2)}, no member of the Collatz corona A k, is devisible by the Collatz number B k, .

  is to theory of Diophantine equations. Consequently, looking for a positive solution of the Collatz problem, one is entitled to work with its less sweeping generalizations, starting with that of the (3m + d)-extension of the Collatz problem, the

	(3m + d)-problem for short (]31[, ]34[, ]105[, and, independently, [3]-]22[).

4

  The Interplay between the Unsolvability Option for the Generalized Collatz Problem and Pseudo-Random Walks in Corresponding Dynamical Systems To illustrate the above theses, let us look at a very plausible conjecture of Keith R. Matthews and A. M. Watts ]124[, representing, since 1985, the most sweeping generalization of the Collatz conjecture available today. Conjecture 1 Let T = T Mp,Rp be a Conway map (

  Definition 6[START_REF] Belaga | Probing into the 3m + d World[END_REF] The pair (k, ) ∈ Λ and the corresponding Collatz number B = B k, (23) are called simple if gcd(k, ) = 1; they are called narrow if = k • log 2 3 . We denote by, respectively, Λ, Λ 0 , Λ0 , the sets of simple, narrow, and simple narrow pairs (k, ):

Acknowledgements. (1) The authors are grateful to Keith Matthews, of Brisbane, Australia, and Thomàs Oilvera et Silva, of Aveiro, Portugal, for their important corrections and suggestions.

(2) The authors are grateful to two anonymous referees for their helpful reports.

(3) The first author is grateful: (i) to Mme Christine Disdier, -for her enduring, unflinching support at the Strasbourg Mathematical Institute's library;

(ii) to his colleagues of the First International Conference on the Collatz Problem, at the Katholische Universit Ét, Eichst Étt, Germany, 1999, -for continuing fruitful discussions;

(iii) to Mlle Véronique Bertrand, -for her indispensable help in the preparation of the Web site for the (unfortunately, indefinitely adjourned) Second International Conference on the Collatz Problem, at the Université Louis Pasteur, Strasbourg, France;

(iv) and to his son Abraham, -for his interest and help in discussing the first version of the present paper.

(ii) T = T

(3)

3 . The data for this, apparently, less volatile case (the effect of the better distributed multiplicative coefficients ? ) are summarized here:

= {min = 1, period = 1, max = 1}, (1 being fixed point), What we are losing here in the algorithmic generality, we are gaining in the diversity of applicable heuristics and methods, with the Diophantine approximation machinery being a particularly powerful and versatile tool. Its availability is the result of an observation, having a long history, that the walk along the "odd trace" of a cycle of the Collatz dynamical system can be interpreted as a corresponding cyclic transformation of a particularly elegant exponential Diophantine equation preserving some of its characteristics.

Definition 3 (1) For any integer r and any set of integers K, let K (r) denote the subset of all q ∈ K relatively prime to r. In this notation, D = N (6) .

(2) For a given d ∈ D, let T = T d be the corresponding map [START_REF] Belaga | The Collatz Problem and Its Generalizations: Experimental Data. Table 2. Factorization of Collatz Numbers 2 -3 k[END_REF], and let, for a given n ∈ N, τ d (n) = τ T d (n) be, according to (8), the T d -trajectory starting at n. According to ( 6) and ( 8),

(5) Since, for a given membership n, d , the corresponding primitive d) of all memberships with a fixed member number n can be identified with both the set P n of all primitive cycles meeting n and the (sub)set D(n) of those shift numbers relatively prime to n to which corresponds the primitive T d -cycle τ ( n) starting at n. (2) For any n ∈ D, the set M n (or, equivalently, either of the sets P n and D(n)) is infinite.

We pass now to the "Diophantization" of the these constructions:

Definition 5 Let n, d ∈ M be a primitive membership. Using the notations ( 22) and ( 23), we define:

The following theorem translates the iterative "cyclic walk" language for (3m + d)-maps into its Diophantine equivalent:

(2) From Primitive Membership to its Diophantine Representation. Let n, d be a membership, and let the functions a, b, f, g, h be defined as above (22). Then

Why and how the formulae (38), (39) strengthen the plausibility of Collatz and Lagarias conjectures. Collatz Conjecture: According to Theorem 5 [START_REF] Lagarias | 3x + 1 Problem: Annotated Bibliograph[END_REF]


Edward G Belaga
email: belaga@math.u-strasbg.frmignotte@math.u-strasbg.fr

Maurice Mignotte

The Collatz Problem and Its Generalizations: Experimental Data. Table 1. Primitive Cycles of (3n + d)-mappings

We study here experimentally, with the purpose to calculate and display the detailed tables of cyclic structures of dynamical systems D d generated by iterations of the functions T d acting, for all d ≥ 1 relatively prime to 6, on positive integers :

, if n is odd.

In the case d = 1, the properties of the system D = D 1 are the subject of the well-known Collatz, or 3n + 1 conjecture.

According to Jeff Lagarias, 1990, a cycle of the system D d ((3n + d)-cycle, for short) is called primitive if its members have no common divisor > 1. For every one of 6667 systems D d , 1 ≤ d ≤ 19999, we calculate its complete, as we argue, list of primitive cycles. Our calculations confirm, in particular, two long-standing conjectures of Lagarias, 1990, and suggest the plausibility of, and fully confirm several new deep conjectures of Belaga-Mignotte, 2000. Moreover, based on these calculations, the first author, Belaga 2003, advanced and proved a new deep conjecture concerning a sharp effective upper bound to the minimal member (perigee) of a primitive cycle,

§1. Introduction. From many points of view, the challenge posed by the Collatz problem -written down in his notebook by Lothar Collatz in 1937 and known today also as the 3n+1 conjecture, 3n+1 mapping, 3n+1 problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problem -is unique in the history of modern mathematics. The Collatz conjecture affirms that the repeated iterations of the mapping

T : N -→ N; T (n) = n 2 , if n is even; 3n+1 2
, if n is odd.

(1 : 1) produce ultimately the cycle 1 → 2 → 1, whatever would be the initial number n ∈ N.

The fact is -even if the Theorem of the Collatz problem can be easily understood and appreciated by children entering secondary school and in its classic simplicity and beauty it belongs more to the Euclidean than to modern era of mathematics -it remains still unresolved, after more than forty years of sustained theoretical and experimental efforts: cf. the annotated bibliography, by Jeff Lagarias, of 200 papers, books, and preprints (arxiv.org/math.NT/0309224, the last update: January 5, 2006).

Bibliographical Digression. To avoid bibliographical redundancy, all our references with numbers in square brackets direct the reader to corresponding items of the Lagarias bibliography, with his generally very helpful succinct comments. Four papers common to the Lagarias and our own bibliography, at the end of the paper, will be referred to by the double references, as in [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF]]- [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF].

Not less surprisingly, the Collatz problem and its immediate elementary generalizations [START_REF] Edward | [END_REF], [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF], [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3x + d Extensions of Collatz Problem[END_REF], [34], [37], [52], [53], [85], [105], [116], [121], were shown to be relevant in one or another substantial way to the deepest open questions in algorithmic theory [20],

[52], [53], [98], [121], [131], [155] and mathematical logic [56], [116], [119], Diophantine approximations and equations theory [START_REF] Edward | [END_REF], [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF], [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3x + d Extensions of Collatz Problem[END_REF] One of the most simple and natural generalizations of the Collatz problem, introduced by Jeff Lagarias [105] and, independently, by the authors [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF]]- [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF], are so called (3n + d)-, or T d -mappings acting, for all d ≥ 1 relatively prime to 6, on the set N of natural numbers :

T d : N -→ N; T d (n) = n 2 , if n is even; 3n+d 2
, if n is odd.

(1 : 2)

We study here experimentally, with the purpose to calculate and display the detailed tables of cyclic structures of dynamical systems D d generated by iterations of the functions T d . In the case d = 1, the cyclic properties of the system D = D 1 are the subject of the cyclic part of the Collatz conjecture.

According to Lagarias [105], a cycle of the system D d ((3n + d)-cycle, for short) is called primitive if its members have no common divisor > 1. For every one of 6667 systems D d , 1 ≤ d ≤ 19999, we calculate its complete, as we argue, list of primitive cycles. Our calculations confirm, in particular, two long-standing conjectures of Lagarias, 1990, and suggest the plausibility of, and fully confirm several new deep conjectures, Belaga, Mignotte, 2000. Moreover, based on these calculations, the first author, Belaga 2003, advanced and proved a new deep conjecture concerning a sharp effective upper bound to the minimal member (perigee) of a primitive cycle, §2. The 3n + d Generalization of the Collatz Problem and its Diophantine Interpretation. We will need here a short list of Diophantine formulae related to the Collatz problem and its 3n + d generalization. We assume the acquaintance of the reader with the basic notions and reasonings leading to this interpretation. Any of the following papers of the authors will do : [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF]]- [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF], [Belaga, Mignotte 2000]- [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3x + d Extensions of Collatz Problem[END_REF], [Belaga, Mignotte, 2006 a ], [Belaga, Mignotte, 2006 b ].

In this section, we list the principal definitions necessary for an understanding of the Diophantine interpretation of the original and generalized Collatz problems, as well as the most important results, -without motivations, elaborations, and proofs, but, in a few cases, with supplementary references.

Let D be the set of odd natural numbers not divisible by 3. As we have already mentioned above, the iterations of the T d -mapping (1:2) generates on the set of natural numbers N a dynamical system D d :

D d = {N ; T d : N -→ N} .
(2 : 1) Definition 2.1 (1) For a given map T d and a given n ∈ N, the T d -trajectory and, in particular, the T d -cycle of length , starting at n are defined as follows:

       (i) τ T d (n) = n = T 0 d (n), n 1 = T d (n), n 2 = T 2 d (n) = T d (T d (n)), . . . (ii) τ T d (n) is a T d -cycle of the length ≥ 1 ⇐⇒ n = T d (n) = n, ∀r (1 ≤ r < ), n r = T r d (n) = n .
(2 : 2)

(2) A non-cyclic T d -trajectory starting at n is called ultimately cyclic, if there exist j ≥ 1 such that the T d -trajectory starting at

n j = T j d (n) is cyclic. (3) A T d -trajectory τ T d (n) starting at n is divergent if it is neither cyclic, nor ulti- mately cyclic. Or, equivalently, if |T j d (n)| j→∞ →∞. Definition 2.2.
(1) For any integer r and any set of integers K, let K (r) denote the subset of all q ∈ K relatively prime to r. In this notations, D = N (6) .

(2) For a given d ∈ D, let T = T d be the corresponding map (1:2), and let, for a given n ∈ N, τ d (n) = τ T d (n) be, according to (2:2), the T d -trajectory/cycle starting at n. Then,

q = gcd(d, n) > 1 =⇒ ∀k ≥ 1 . q = gcd(d, T k d (n)) = gcd(τ d (n)), τ d (n) = q • τ d/q (n),
(2 : 3) with τ d (n) being called q-multiple of the T d/q -trajectory/cycle τ d/q (n). This reduces the study of non-primitive T d -trajectories, and in particular, T d -cycles, to the study of their underlying primitive T q -cycles, for all proper divisors q of d.

(3) Otherwise, n ∈ N (d) , and the trajectory

τ d (n) is called primitive, gcd(d, n) = 1 =⇒ ∀k ≥ 1 . gcd(d, T k d (n)) = gcd(τ d (n) = 1 . ( 2
C o = {1 → 2 → 1}.
(2) Finiteness of the Set of Primitive T d -cycles. For any d ∈ D, the number of primitive T d -cycles is finite. In the case of the Collatz problem, one conjectures C o being the only primitive cycle.

In contrast to the first two conjectures of Lagarias, the following conjecture has no immediately apparent (3n + 1)-precursor or analogue : Conjecture 2.4. For any n ∈ D, the set of primitive

T d -cycles, d ∈ D (n) , meeting n is infinite.
We have interpreted this conjecture as dual to the first conjectures of Lagarias, with the emerging disparate duality between d-and n-related phenomena being an important new and all-pervading intuition behind the present study [Belaga, Mignotte 2000]- [START_REF] Belaga | Cyclic Structure of Dynamical Systems Associated with 3x + d Extensions of Collatz Problem[END_REF], [Belaga, Mignotte 2006 a ]. This duality finds its precise formal description in the related Diophantine framework, Theorem 2.10(4) below.

Definition 2.5. (1) For any positive integer n ∈ N, define the number Odd(n) obtained by factoring out of n the highest possible power of 2; thus Odd(n) is odd and m = Odd(n) • 2 j , for some j. Hence the notation:

∀n ∈ N , ν 2 (n) = max j ≥ 0 n • 2 -j ∈ N , n = Odd(n) • 2 ν2(n) .
(2 : 5)

(2) Let τ d (n) = {n, T d (n), T d (T d (n)), .
. .} be a primitive T d -trajectory starting at an odd n not divisible by 3 and relatively prime to d, n ∈ D (6) . The full sequence of odd members, in the order of their appearance in τ d (n) is called the odd frame of τ d (n) and denoted by Oddframe(n, d), with the full sequence of the corresponding exponents of 2, denoted by Evenframe(n, d) (2:5):

∀n, d ∈ D,                (i) τ d (n) = n, n 1 , n 2 , . . . ; (ii) Evenframe(n, d) = p 1 , p 2 , . . . ⊂ N, ∀j ≥ 1, p j = ν 2 (3n j-1 + d) ≥ 1; (iii) Oddframe(n, d) = m 0 = n, m 1 , m 2 , . . . ⊂ D (d) , ∀j ≥ 1, m j = Odd(3m j-1 + d) = n rj , r j = 1≤i≤j p i .
(2 : 6)

(3) If τ d (n) is a cycle C of
the length , then the periodic sequence (2:5(iii)) is called the Oddcycle associated with C and denoted by Oddframe(C), with the period k, 1 < k < , called the Oddlength of the cycle C, with the respective list Evenframe(C) of exponents defined by the formula (2:5(ii)), and with the parameters length, Oddlength, and Evenframe(C) satisfying the following obvious relationship implied by the cyclic condition (2:2(ii)):

= p 1 + • • • + p k ≥ k • log 2 3 ⇐⇒ B k, = 2 -3 k > 0 , Λ = {(k, ) ∈ N | ≥ k • log 2 3 }.
(2 : 7) Definition 2.6. Let n, d ∈ M be a primitive membership. Using the notations (7:2,3), we define:

                       a, b, f, g, h : M -→ D ; ∀ n, d ∈ M, A = a( n, d ), B = B k, = b( n, d ), F = f ( n, d ), G = g( n, d ), H = h( n, d ) ; A = 1, if k = 1 ; 3 k-1 + 2 p1 • 3 k-2 + • • • + 2 p1+•••+p k-2 • 3 + 2 p1+•••+p k-1 , otherwise; B = B k, = 2 -3 k = 2 p1+p2+...+p k -3 k > 0 (cf.(4 : 3)); B is called Collatz (k, ) -number; H = gcd(A, B) ; F = A H ; G = B H ; gcd(F, G) = 1.
(2 : 8)

The following theorem translates the iterative "cyclic walk" language for (3n + d)-maps into its Diophantine equivalent: Theorem 2.7. [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF]]- [START_REF] Belaga | Embedding the 3m + 1 Conjecture in a 3x + d Context[END_REF] (1) Diophantine Cyclic Walk. Let n, d ∈ M be a primitive membership, C = C(d, n) be the corresponding primitive T d -cycle starting at m 0 = n, of the Oddlength k > 1, let m 1 = Odd (3m 0 + d) (4:3), and let m 1 , d be the corresponding membership. Let σ k be the circular counterclockwise permutation on k-tuples of positive integers P = Even (n, d). Then the set P 1 = Even (m 1 , d) corresponding to the membership m 1 , d is defined by the formula

P 1 = Even (m 1 , d) = σ k P = σ k p 1 , p 2 , . . . , p k-1 , p k = p 2 , p 3 , . . . , p k , p 1 .
(2) From Primitive Membership to its Diophantine Representation. Let n, d be a membership, and let the functions a, b, f, g, h be defined as above (2:8). Then

F = f ( n, d ) = n, G = g( n, d ) = d.
(3) From the Diophantine Formulae to their Membership Interpretation. Let k ≥ 2 and P = p 1 , . . . , p k ⊂ N k be a k-tuple of positive integers satisfying the inequality

= |P| = p 1 + • • • + p k ≥ k • log 2 3 , (2 : 9)
and let the numbers A, B, F, G, H be defined as in (2:8). Then F, G is a primitive membership.

The following deep theorem demonstrates the strength of the above Diophantine formalism (2:5-9) ; we are not aware of an alternative, non-Diopnantine proof of the below inequality (2:10):

Theorem 2.8. [Belaga 2003]- [START_REF] Edward | [END_REF] (1) Let n, d ∈ M be a primitive membership of the length and Oddlength k, and let τ d (n), (n, d) ∈ ∆ be the corresponding T d -cycle. If n is the minimal member of the Oddframe(n, d), then the inequality holds :

1 ≤ n < d 2 k -3 .
(2 : 10)

(2) The inequality (2:10) is sharp : for any K > 1 and any > 0, there exists the primitive membership n, d ∈ M, such that n is the minimal member of the corresponding primitive cycle of the Oddlength k > K and length satisfying the inequality :

0 < n • (2 k -3) d -1 < .
(2 : 11)

The following statement demonstrates the particular importance of Collatz numbers for our problems : Definition 2.9. (1) The pair (k, ) ∈ Λ (2:7) and the corresponding Collatz number B = B k, (2:8) are called narrow if gcd(k, ) = 1 and = k • log 2 3 . We denote by Λ 0 the set of narrow pairs (k, ) :

Λ 0 = {(k, ) ∈ Λ | gcd(k, ) = 1 & = k • log 2 3 } .
(2 : 12)

(2) Let n, d ∈ M be a primitive (k, )-membership with the corresponding Collatz number B. We associate with n, d ∈ M its Collatz corona A = A k, , a finite set of natural numbers depending only on the Oddlength and length of n, d ∈ M, as follows :

(a) If k = 1, then

A 1, = 1 .
(2 : 13))

(b) If k > 1, then for any aperiodic (k -1)-tuple P = p 1 , . . . , p k-1 of positive integers satisfying the inequality (cf. (2:9))

p 1 + . . . + p k-1 < ,
(2 : 14) the following number belongs to A :

A = A(P) = 3 k-1 + 3 k-2 • 2 p1 + . . . + 3 • 2 p1+...+p k-2 + 2 p1+...+p k-1 .
(2 : 15)

By definition, members of Collatz corona are odd positive integers not divisible by 3. The Collatz corona corresponding to a narrow pair (k, ) is called narrow, too.

Theorem 2.10. (1) Collatz corona A k, is a one-element set iff k = 1 (2:13))

(2) Otherwise, Collatz corona A k, of a Collatz number B = B k, is a finite set of mutually distinct positive integers not equal to B, and its cardinality α k, = #A k, satisfies the following formula (cf. (2:7) for the definition of the set Λ) :

∀(k, ) ∈ Λ        α k, = #A k, = -1 k-1 , if gcd(k, ) = 1 , r| gcd(k, ) µ(r) • r -1 k r -1 , otherwise , α k, ≡ 0 (mod k) , (2 : 16)
where µ is the Möbius function :

µ(m) = 1 , if m = 1 , (-1) q , if m is the product of q distinct primes , 0 ,
if m is divisible by a square of a prime .

The low part of the formula (2:16), defined for pairs (k, ) with the property gcd(k, ) > 1, is universal and covers -but also obscures -the special upper case gcd(k, ) = 1.

(3) The below lower and upper bounds to members A of Collatz corona are sharp :

∀(k, ) ∈ Λ ∀A ∈ A k, A k, = 3 k -2 k , A k, = 2 -k+1 • 3 k-1 -2 k-1 + 3 k-1 ; 3 k-1 < A k, ≤ A ≤ A k, < 2 -k+1 • 3 k-1 .
(2 : 17)

(3) Since the function a in the definition (2:8) and the corresponding construction ((2:15) do not actually depend on the k-th component p k of the correspnding Collatz configuration, their values for two k-configurations of different lengths can be equal. More precisely,

∀(k, ) ∈ Λ ∀j ≥ 1 , A k, ⊂ A k, +j .
(2 : 18)

(4) With the exception of the trivial case, corresponding to the primitive

T 1 -cycle 1 → 2 → 1, k = 1, = 2, A 1,2 = {1}, B = 1 ,
no Collatz number ever belongs to the respective Collatz corona and, if k ≥ 4, it is located below the upper bound (2:17) of the corona,

∀(k, ) ∈ Λ , B = B k, < 2 < A k, , if k ≥ 4 .
(2 : 19)

(5) Moreover, if (k, ) ∈ Λ is not narrow, then A k, extends both below and above B.

Consequently, the original Collatz, or 3n + 1, conjecture is equivalent to the following claim :

The (Diophantine version of the) Collatz conjecture 2.11. For any pair below -albeit inevitably with different degrees of certainty. Moreover, as it has been already mentioned above, the numerical data obtained in our computations suggest the plausibility of previously unknown general laws of the iterative behaviour of (3m + d)-maps, with one of such laws formulated and proved in [Belaga 2003]- [START_REF] Edward | [END_REF].

(k, ) ∈ Λ \ {(1, 2)}, no member of the Collatz corona A k, is
(1) Withing the chosen range, Conjecture 2.3(1) has been fully confirmed: all such systems D d have at least one primitive cycle.

(2) The confirmation of Conjecture 2.3(2) is more problematic: a priori, no quantity of computations could confirm that a certain (sub)set is finite. Thus, the plausibility of such a claim hinges on the quality of availble evidence that the search was exhaustive. Such an evidence is discussed below, §4. (3) Compared to the case of the two Conjectures 2.3, our claim of the confirmation of Conjecture 2.4 is even more problematic: no quantity of (always finite) computations could confirm that a certain (sub)set is infinite ! Still, taking in account relatively small total numbers of memberships in primitive cycles for corresponding numbers n compared to the total number 42765 of primitive cycles found in the chosen range, -the total numbers ranging from 18 to 452 (for n = 1), -we have a strong evidence of the plausibility of Conjecture 2.4. §4. Algorithm Searching for Primitive Cycles.

According to the generalized Collatz conjecture, all trajectories of the system D d , d ∈ D are either cyclic, or ultimately cyclic, This claim became the basic assumption of our algorithm searching for primitive T d -cycles :

Working Assumption 4.1. Let ∆ = {(u, v) ∈ D| gcd(u, v) = 1}.
The following algorithm always halts :

A prim.cycl 3x+d :          ∀(u, v) ∈ ∆ d := u; m := n := v while m = n do m := T d (m); n := T d (n); n := T d (n); endwhile .
(4 : 1)

The algorithm (4:1) computes at the j-th step the iterations T j d (n) and T 2j d (n), and then compares them. See Proposition 4.2 below for a proof that even the full (i. e., not necessarily restricted to primitive cycles) version A cyclic 3x+d of this algorithm detects all T d -cycles.

This classical cycle detection device, remarkable for its simplicity, has been invented by Robert W. Floyd. (Never published by the author. The standard reference is [Knuth 1969], pp. 4-7, Exercise 7. See also [Cohen 1993], §8.5.2, for an update on cycles detection methods.) :

Proposition 4.2. Let f : N -→ N be a function. A f -trajectory starting at a positive integer m, τ (m) = f 0 (m) = m, f (m), f 2 (m) = f (f (m)), f 3 (m), . . . (4 : 2)
is ultimately cyclic iff, for some j ≥ 1, f j (m) = f 2j (m) , (4 : 3)

Proof :

(1) The if (or sufficiency) condition (4:3) is obvious.

(2) The only if (or necessary) condition. Suppose τ (m) runs at the point s = f z (m), z ≥ 1, into a cycle of the length w, so that, for any x ≥ 0, f z+x (n) = f z+x+w (m).

Assuming t = z + x, the condition (4:2) will be satisfied if, for some positive integers x, y ≥ 1, the equality holds :

2t = 2(z + x) = z + x + y • w = t + y • w.
The choice y = z w and x = y • wz would do. End of Proof. The above Working Assumption has been verified in more than 75, 000, 000 cases within the intervals

d ∈ I 1,19999 = [1, 19999] ∩ D , n ∈ I 1,600•d-1 .
(4 : 4) and separately, in a huge controlling check, in more than 24,000,000,000 cases within the intervals

d ∈ I 1,4999 , n ∈ I 1,3000•d-1 . (4 : 5)
To speed the search, trajectories have been traced in the increasing order of the starting number m ∈ D. Then, if the trajectory τ d (m) fell at some point behind the initial point m, n = T j d (m) < m, the search along τ d (m) was ceased, since its continuation, the trajectory τ d (n) starting at n, has been already treated before. Every one of the thus traced trajectories either run ultimately into a primitive cycle, or descended under m, and thus, has been already traced to a cycle earlier.

We have carried out some additional controlling checks, too :

(1) In 82 cases, for all d ∈ I 2755,2999 , an independent search has been carried out, with the bigger initial interval 1 ≤ n ≤ 5000 • d. No new primitive cycles have been discovered.

(2) In one particularly interesting case, d = 343, mentioned below, the chosen initial controlling interval was 1 ≤ n ≤ 60, 000 • 343 > 2 • 10 7 . The calculations have confirmed the existence of only three primitive cycles discovered earlier.

Note also that the minimal members of all primitive cycles, discovered thus far, fall under the upper limit 600 • d in (4:4), with only two cases coming relatively close to this limit :

(1) d = 343; one of primitive T 343 -cycles (out of three discovered) has the minimal member (cf.

Notations :

(1) The data corresponding to a given shift number d is framed by the double backslash \\.

(2) The first line of the block of data corresponding to a given shift number d, for example, d = 5; a = 5; lg = [3,5,5,27,27]; LG = [1,3,3,17,17]; includes the value of d, in this case, d = 5, the number a of primitive cycles found, a = 5, and the lists of lengths, lg, and Oddlengths, LG, of corresponding cycles, respectively : lg= [. . .], LG= [. . .].

(3) Then, for a given d, follows the detaled descriptions of the corresponding primitive T d -cycles, in the order of the values of their perigees (the minimal members).

(4) The list S[j] of the length Oddlength represents the list of odd members of the cycle listed in the order of the index j, 1 ≤ j ≤ a, according to the above definintion of Oddframe of the cycle, (2:6(iii)).

(5) The list P[j], j, 1 ≤ j ≤ a -1, , represents the first Oddlength -1 members of the list of exponents of 2, corresponding to the passage from one odd member of the Oddf rame of the cycle to the next one (cf. (2:6)), with the exponent for the passage from the last odd member of the cycle to the first one omitted. The full list has been defined above (2:6(ii)) as Evenf rame of the cycle.

(6) The last member of the Evenf rame of the cycle, missing in P[j], is presented immediately after P[j], as p= . . .. The reason of such an independent presentation of this member (p k in the notations (2:7)) is its irrelevance to the construction of numbers A of the formulae (2:8).

  : 4) Primitive trajectories are numerous: according to (2:4), the T d -trajectory starting at a natural number n relatively prime to d is primitve. But how many of such trajectories are primitive cycles? More specifically, do primitive cycles exist for all systems d ∈ D ? And what are the chances of an integer n ∈ D (d) to belong to such a cycle? These are the subjects of the original conjectures of Lagarias [105] : Conjecture 2.3. (1) Existence of a Primitive T d -cycle. For any d ∈ D, there exists at least one primitive T d -cycle. In the case of the Collatz problem, it is the cycle

( 4 )

 4 Let ∆ be the subset of the set of pairs (n, d) ∈ D × D, with relatively prime integers n, d. If a primitive T d -cycle C meets a number n, (n, d) ∈ ∆, then the pair n, d is called a primitive membership pair, or simply membership.

  devisible by the Collatz number B k, . §3. Experimental Study of the Cyclic Structure of Dynamical Systems D d generated by the corresponding (3n+d)-mappings. For all 6667 dynamical systems D d within the range 1 ≤ d ≤ 19999, d ∈ D, our computations have confirmed Conjectures 2.3, 2.4, -see our main Table

( i )

 i The total number of experimentally discovered T d -cycles, 1 ≤ d ≤ 19999, d ∈ D, is equal to 42765. (ii) The numbers ω(d) of such cycles for individual systems Dd are ranging from ω(d) = 1, for 1481 systems D d out of 6667, to 2, for 1507 of them, to 3, for 1005, etc., to 944 for the system D 14303 :

  (10:3)) n o = 177, 337; 517 • 343 < n o < 518 • 343 < 600 • 343 (and the maximal member m o = 159, 053, 606). (2) d = 551; one of primitive T 551 -cycles (out of ten) has the minimal member n o = 212, 665; 385 • 551 < n o < 386 • 551 < 600 • 551 (with m o = 8, 332, 648). §5. Commentaries to the Table of Primitive T d -cycles, 1 ≤ d ≤ 19999 (d odd and not divisible by 3).

Table 3 .

 3 1. Eleven systems D d with the numbers of primitive cycles bigger than 160.

	d	7463	18359 7727	15655 10289 9823	17021 14197 13085 6487	14303
	ω(d)	162	164	198	207	214	241	258	329	335	534	944


Athanase Papadopoulos
email: papadopoulos@math.u-strasbg.fr

Guillaume Th Éret

G Théret
email: theret@math.u-strasbg.fr

ON THE TOPOLOGY DEFINED BY THURSTON'S ASYMMETRIC METRIC

Keywords: AMS Mathematics Subject Classification: 30F60 ; 32G15. Keywords: Teichmüller space, Thurston's asymmetric metric, geodesic lamination

In this paper, we establish some properties of Thurston's asymmetric metric L on the Teichmüller space T g,n of a surface of genus g with n punctures and with negative Euler characteristic. We study convergence of sequences of elements in T g,n in the sense of L, as well as sequences that tend to infinity in T g,n . We show that the topology that the asymmetric metric L induces on Teichmüller space is the same as the usual topology. Furthermore, we show that L satisfies the axioms of a (not necessarily symmetric) metric in the sense of Busemann and conclude that L is complete in the sense of Busemann.

Let g and n be two nonnegative integers and let S = S g,n be a connected oriented surface of negative Euler characteristic, obtained from a closed surface of genus g by removing n points which we shall call the punctures. A hyperbolic metric on S is a Riemannian metric of constant curvature -1. The Teichmüller space of S is the space of equivalence classes of complete finite area hyperbolic metrics on S, where two metrics are considered equivalent if they are isotopic, that is, if one of these metrics is the image of the other one by a map which is isotopic to the identity. The Teichmüller space of S is denoted by T(S) = T g,n . This space carries a natural topology that makes it homeomorphic to R 6g-6+2n . In what follows, we shall refer to this topology as the usual topology of Teichmüller space. We briefly recall one way of defining it, by explicitly describing a homemorphism T → R 6g-6+2n . We start by taking a set of closed geodesics decomposing S into hyperbolic pairs of pants. Here, a hyperbolic pair of pants is a sphere with three open disks of dimension zero or two removed, such that each boundary component is either a closed geodesic or a cusp, the cusps being at the punctures of S. The decomposition provides a set of parameters for the space T(S), where two parameters are associated to each geodesic, one parameter (in (0, ∞)) being the length of that geodesic, and the other parameter (in R) being a twist parameter. A twist parameter is defined up to the choice of an origin corresponding to the zero-twist. This collection of parameters gives a homeomorphism between T(S) and R 3g-3+n × (0, ∞) 3g-3+n . For a detailed description of this homeomorphism in the case n = 0, we refer the reader to [START_REF] Thurston | Three-dimensional geometry and topology[END_REF] p. 271. One can also refer to [START_REF] Abikoff | The Real Analytic Theory of Teichmüller space[END_REF], [START_REF] Fathi | Travaux de Thurston sur les surfaces[END_REF] and [START_REF] Imayoshi | An Introduction to Teichmüller Spaces[END_REF]. These length-twist parameters associated to pair of pants decompositions are usually called Fenchel-Nielsen parameters.

We now recall the definition of Thurston's asymmetric metric.

For any two hyperbolic metrics g and h on S and for any diffeomorphism ϕ : S → S which is isotopic to the identity, we consider the Lipschitz constant Lip(ϕ) of ϕ, defined by

Lip(ϕ) = sup x =y∈S d h ϕ(x), ϕ(y) d g x, y .
The infimum of the Lipschitz constants associated to all diffeomorphisms ϕ that are isotopic to the identity is denoted by

(1) L(g, h) = log inf ϕ∼Id S Lip(ϕ).
Making g and h vary in their respective homotopy classes, we obtain a function (which we denote by the same letter)

L : T(S) × T(S) → [0, ∞),
which is Thurston's asymmetric metric.

It is easy to see that the function L satisfies the triangle inequality, but it requires some work to see that L(g, h) > 0 for any g = h (see [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF], Theorem 3.1).

There is another geometrically defined measure of a distance between two metrics g and h, which was introduced by Thurston, which we shall denote by K(g, h). We now recall its definition.

A closed curve in S is called essential if it is not homotopic to a point or to a puncture of S. We let S be the set of isotopy classes of simple essential closed curves in S.

For any homotopy class α of essential simple closed curves on S, we consider the quantity

r g,h (α) = l h (α) l g (α)
,

where l h (α) denotes the length of the closed geodesic in the homotopy class α with respect to the hyperbolic metric h, and we set

(2) K(g, h) = log sup α∈S r g,h (α).
Here also, the function K which is defined on the set of pairs of hyperbolic structures gives a well-defined function (which we denote by the same letter K) defined on pairs of elements of Teichmüller space.

We let ML 0 (S) be the space of compactly supported measured geodesic laminations on S, equipped with its usual topology, and we let PML 0 (S) be the corresponding projective space, that is, the quotient of ML 0 (S) by the natural action of the positive reals. We refer the reader to [START_REF] Thurston | The geometry and topology of Three-manifolds[END_REF] for the definitions and the basic notions concerning these spaces. We shall also use notions like lengths and intersection functions between measured foliations, closed geodesics and compactly supported geodesic laminations, which are now classical notions, and we refer the reader to references such as [START_REF] Thurston | The geometry and topology of Three-manifolds[END_REF], [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF], [START_REF] Penner | Combinatorics of Train Tracks[END_REF] and [START_REF] Fathi | Travaux de Thurston sur les surfaces[END_REF], for the details.

Using the extension of the length of a closed curve to the length of a measured geodesic lamination, we have the following expression of K(g, h)

(3) K(g, h) = log sup α∈ML 0 (S) r g,h (α) = log sup α∈PML 0 (S)
r g,h (α).

The last expression for K is often more useful than Expression 2 because, by compactness of the space PML 0 (S), the supremum in 3 is attained.

It is easy to see that K ≤ L. In his paper [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF], Thurston proved that K = L. He also showed that the function L is not symmetric in general, by considering the structures g and h shown in Figure 1. Figure 2 gives an example of distinct hyperbolic metrics g and h satisfying K(g, h) = K(h, g).

We also need to recall the following notions from Thurston's paper [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF].

For any simple closed geodesic γ in S endowed with a hyperbolic metric, we can construct (in a non-canonical way) a geodesic lamination µ which satisfies the following three properties:

(1) the lamination µ has no other transverse measure of compact support than the Dirac transverse measure supported on γ; (2) each leaf of µ \ γ is bi-infinite and each of its ends either spirals around γ or converges to a cusp of S; (3) the lamination µ is complete. The last condition means that each connected component of the complement of µ in S is isometric to the interior of a hyperbolic ideal triangle. (We recall that a hyperbolic ideal triangle is the convex hull of three distinct points in the boundary at infinity of hyperbolic plane

H 2 .)
The lamination µ is called a completion of γ and the closed geodesic γ is called the stump of µ. An example of a completion of a simple closed geodesic γ is given in Figure 3.

Finally, we recall the construction of the horocyclic measured foliation that is associated to a complete geodesic lamination. We start with a construction in a hyperbolic ideal triangle. Any such triangle is equipped with a canonical partial measured foliation which is called its horocyclic foliation. The term partial means here that the support of PSfrag replacements and h satisfying K(g, h) = K(h, g). Here, h is the image of g by an order-two isometry which is not isotopic to the identity.

L(f ) e d /e c L(f ) d/c c d g h Ae -c Ae -d
the foliation is a subset of the ideal triangle. The horocyclic foliation is characterized by the following three properties:

(1) the leaves are pieces of horocycles that are perpendicular to the edges; (2) the non-foliated region is a triangle bordered by three of these pieces of horocycles (see Figure 4); (3) the transverse measure assigned to any arc which is contained in an edge coincides with the Lebesgue measure induced from the hyperbolic metric. Now if µ is any complete geodesic lamination on the hyperbolic surface S, then, the metric completion of each connected component of S \ µ being an ideal triangle, we can equip it with its canonical horocyclic measured foliation. The collection of the horocyclic measured foliations associated to these various ideal triangles fit together compatibly and define a partial measured foliation of S, which we call the horocyclic measured foliation associated to µ. Collapsing each nonfoliated triangular region onto a tripod, we obtain a genuine (i.e. not partial) measured foliation on the surface, which is well-defined up to isotopy and which we denote by F µ (S).

The fact that the hyperbolic structures that we consider on S are complete and of finite area is equivalent to the fact that the horocyclic foliation F µ (S) associated to µ is trivial around the punctures, that is, each puncture of S has a neighborhood homeomorphic to an annulus on which the foliation induced by F µ (S) consists of closed leaves PSfrag replacements γ that are parallel to the puncture. Using the canonical map between measured foliations on S that are trivial around the punctures and (possibly empty) compactly supported measured geodesic laminations on S, we obtain a well-defined compactly supported measured geodesic lamination associated to the measured foliation F µ (S). We shall call it the horocyclic measured geodesic lamination associated to µ, and we shall denote it by λ µ (S).

In what follows, we establish some properties of Thurston's asymmetric metric L with respect to sequences in T(S) that tend to infinity, and we discuss the topology that this asymmetric metric induces on that space. Here, as usual, we say that a sequence (g n ) in T(S) tends to infinity (and we write g n → ∞) if for any compact subset K of T(S), we have g n ∈ T(S) \ K for all n large enough.

We shall use the following lemma (see [START_REF] Fathi | Travaux de Thurston sur les surfaces[END_REF] p. 147).

Lemma 1. For every sequence (g n ) of elements in T(S) that tends to infinity, we can find a finite set {γ 1 , . . . , γ k } ⊂ S such that k j=1 i(g n , γ j ) → ∞ as n → ∞ (or, equivalently, lim sup k j=1 i(g n , γ j ) = ∞). We prove the following Theorem 1. For any sequence (g n ) in T(S), the following three properties are equivalent:

(1) g n → ∞;

(2) for all h ∈ T(S), L(h, g n ) → ∞;

(3) for all h ∈ T(S), L(g n , h) → ∞.

Proof. Let us first note that from the triangle inequality (which is satisfied by the asymmetric metric), we can replace in Properties 2 and 3 the statement "for all h ∈ T(S)" by "there exists h ∈ T(S)".

We start by proving 1⇒2. If g n → ∞, then, by Lemma 1, for each n ≥ 0, we can find an element γ n which we can choose among a finite set of elements in S such that l gn (γ n ) → ∞ as n → ∞. Since the homotopy classes γ n are chosen among finitely many elements, for any fixed h in T(S), the value l h (γ n ) is bounded from above. Therefore, we have

L(h, g n ) = log sup λ∈ML 0 (S) l gn (λ) l h (λ) ≥ log l gn (γ n ) l h (γ n ) → ∞.
Now let us prove 2⇒1. Equivalently, we prove that if there exists h ∈ T(S) satisfying L(h, g n ) → ∞, then g n → ∞. We reason by contradiction. Assume that g n ∞. This means that there exists a subsequence of (g n ), which we also denote by (g n ), and a compact subset K of T(S) such that g n ∈ K for all large enough n. By compactness of K and, again, up to taking a subsequence of (g n ), we can assume that this sequence converges to some point g in K. By compactness of PL 0 (S), for every n ≥ 0, we can find an element η n ∈ ML 0 (S) satisfying sup λ∈ML 0 (S)

l gn (λ) l h (λ) = l gn (η n ) l h (η n ) .
Again by compactness of PL 0 (S) and up to taking a subsequence of (g n ), we can assume that the sequence of projective classes of η n converges to the projective class of some element γ ∈ ML 0 (S). This implies

L(h, g n ) = lim n→∞ sup λ∈ML 0 (S) l gn (λ) l h (λ) = l g (γ) l h (γ) < ∞,
which is a contradiction. The proof of 3⇒1 is analogous to the proof of 2⇒1.

So far, we have proved 1⇐⇒2⇐= 3. In order to prove 1=⇒ 3, we need the following Lemma 2. If (g n ) is a sequence in T(S) tending to infinity, then there exists a sequence (λ n ) n≥0 ∈ ML 0 (S) such that (1) the sequence l gn (λ n ) is bounded from above;

(2) for all h ∈ T(S),

l h (λ n ) → ∞ as n → ∞.
Proof. Let (g n ) n≥0 be a sequence in T(S) that tends to infinity. By Lemma 1, there exists a finite set Γ of homotopy classes of simple closed curves such that for each n ≥ 0, there exists γ n ∈ Γ such that l gn (γ n ) → ∞.

For each n ≥ 0, we complete γ n into a complete geodesic lamination µ n of stump γ n and we let λ n = λ µn (g n ).

We know that l gn (λ n ) is bounded. Indeed, by Lemma 3.9 and Proposition 3.3 of [START_REF] Papadopoulos | On Thurston's boundary of Teichmüller space and the extension of earthquakes[END_REF], this quantity is bounded by -6χ(S), where χ(S) is the Euler characteristic of S. (The proof is given there for closed surfaces, but the arguments work more generally for surfaces of finite type.)

Let h ∈ T(S). We show that there exists (h) > 0 such that l h (λ n ) ≥ (h)l gn (γ n ).

Let us fix an integer n ≥ 0. We can cover the surface S with a finite union of rectangles R 1 , . . . , R N (n) of disjoint interiors, such that λ n induces on each rectangle a lamination by geodesic segments whose endpoints are on the vertical sides of that rectangle and such that γ n crosses each such rectangle from one horizontal side to the other horizontal side (see Figure 5).

We can assume that the number N (n) of rectangles is bounded from above, by a constant that only depends on the topology of S. (We can use a train track to build the rectangular cover, and in that case the number N (n) is bounded by the maximal number of edges of a train track on S.)

For each j ∈ {1, . . . , N (n)}, let k j n = {γ n ∩ R j } and let w j n be the "width" of the rectangle R j , that is, the total measure of any of its vertical sides with respect to the transverse measure dλ n of λ n .

We have:

(

1) l h (λ n ) = N (n)
j=1 ∂R j ∩λn l h (x)dλ n , where {∂R j } j=1,...,N (n) denotes the set of vertical edges of the rectangles glued together and where l h (x) denotes the h-length of the segment contained in the leaf of λ n which crosses ∂R j at the point x;

(2) l gn (γ n ) =

N (n) j=1 k j n w j n .
Statement 1 above is clear from the definitions. We now prove 2. For this, it is useful, for each n ≥ 0, to replace the measured lamination λ n by a measured foliation F n having the same properties with respect to the rectangles R 1 , . . . , R N (n) , that is, inducing on each such rectangle a foliation by segments that join its vertical sides, such that the total F n -mass of the vertical side of each rectangle is equal to its total λ nmass. The closed geodesic γ n is in minimal position with respect to F n , that is, there is no closed disk in S whose boundary is the union of a segment in a leaf of F n and a segment in γ n . This follows from the fact that γ n , being a geodesic, was already in minimal position with respect to λ n . Thus, i(F n , γ n ) is equal to the total F n -mass of γ n . Therefore, we have

N (n) j=1 k j n w j n = i(F n , γ n ) = i(F µn (g n ), γ n ).
Now since γ n is the stump of µ n , the last quantity is equal to l gn (γ n ). (This is Lemma 3.12 of [START_REF] Papadopoulos | On Thurston's boundary of Teichmüller space and the extension of earthquakes[END_REF] adapted to the case where the lamination PSfrag replacements µ n does not necessarily have a transverse measure of full support, with γ n being its stump.) This completes the proof of 2.

The hyperbolic structure h being fixed, any geodesic segment in λ n that starts and ends at points on γ n has its length bounded below by a positive number (h) > 0 that is independent of n. This follows from the compactness of γ n and the fact that γ n is chosen among a finite set of homotopy classes of simple closed curves. Hence,

l h (λ n ) ≥ (h) N (n) j=1 k j n ∂R j ∩λn dλ n ≥ (h) N (n) j=1 k j n w j n = (h)l gn (γ n ). Therefore, lim n→∞ l h (λ n ) = ∞.
Now we can complete the proof of Theorem 1.

If g n → ∞, then we have

L(g n , h) = log sup λ∈ML 0 (S) l h (λ) l gn (λ) ≥ log l h (λ n ) l gn (λ n ) ≥ log l h (λ n ) C → ∞,
as n → ∞. (Here, C denotes a constant bounding l gn (λ n ) from above.)

Theorem 2. For any sequence (g n ) in T(S) and for any element g in T(S), the following three properties are equivalent:

(1) g n → g;

(2) L(g, g n ) → 0;

(3) L(g n , g) → 0.

Proof. We start with the implication 1=⇒ 2. If g n → g, then for all α ∈ S, r g,gn (α) = lg n (α) lg(α) → 1. This implies that L(g, g n ) → 0. Indeed, let us fix ε > 0. There exists α ∈ S such that L(g, g n ) -log r g,gn (α) ≤ ε. Now there exists N (α) such that, for all n ≥ N (α), | log r g,gn (α)| ≤ ε. Therefore, for all ε > 0, there exists N such that, for all n ≥ N , L(g, g n ) ≤ 2ε. This proves the claim.

The proof of 1=⇒ 3 is dealt with exactly as for 1=⇒ 2. So far, we proved the following implications

L(g, g n ) → 0 ⇐= g n → g =⇒ L(g n , g) → 0.
Before completing the proof of Theorem 2, we prove a result on the compactness of closed balls for Thurston's asymmetric metric.

Let g be a point in T(S) and let R be a positive real. Since L is asymmetric, there are two different notions of closed balls, called the left closed ball centered at g ∈ T(S) of radius R and the right closed ball centered at g ∈ T(S) of radius R, which we denote respectively by g B(R) and B g (R). They are defined by [START_REF] Imayoshi | An Introduction to Teichmüller Spaces[END_REF] g B(R) = {h ∈ T(S) | L(g, h) ≤ R} and

(5)

B g (R) = {h ∈ T(S) | L(h, g) ≤ R}.
We show that these balls are compact, for the usual topology on Teichmüller space. Proposition 3. For any g in T(S) and for any R > 0, the closed balls g B(R) and B g (R), centered at g ∈ T(S) and of radius R, are compact for the usual topology.

Proof. The proof is based on Theorem 1, and arguments concerning g B(R) and B g (R) are identical. We therefore only prove the compactness of g B(R).

First note that g is closed for the usual topology. Indeed, let (g n ) be a sequence in g B(R) converging to h ∈ T(S) for the usual topology. Then L(g, h) ≤ L(g, g

n ) + L(g n , h) ≤ R + L(g n , h). The implication g n → h =⇒ L(g n , h) → 0 gives L(g, h) ≤ R, that is, h ∈ g B(R). Therefore, g B(R) is closed for the usual topology.
Let (g n ) be a sequence of g B(R). By Theorem 1, g n ∞. Therefore, there exists an infinite subsequence of (g n ), which is contained in a compact subset K of T(S) for the usual topology. We also call (g n ) this subsequence. Up to taking another subsequence, we may assume that g n → h. Since g n ∈ g B(R) and since g B(R) is closed, h ∈ g B(R), which proves that g B(R) is a compact subset of T(S).

We now complete the proof of Theorem 2. We must prove that L(g, g n ) → 0 =⇒ g n → g. If L(g, g n ) → 0, then there exists R > 0 such that, for all n ∈ N, g n ∈ g B(R). Since g B(R) is compact, the sequence (g n ) has at least one cluster point h ∈ g B(R) (for the usual topology). Let (g n ) also denote a subsequence converging to h. We have L(g, h) ≤ L(g, g n ) + L(g n , h). Passing to the limit as n goes to infinity, we obtain L(g, h) = 0. By Theorem 3.1 of [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF], g = h. This implies that g is the cluster point of (g n ). Therefore, g n → g.

The proof of L(g n , g) → 0 =⇒ g n → g can be done in a similar way. This completes the proof of Theorem 2.

Consider the symmetrization σL : T(S)×T(S) → [0, ∞) of L, defined by the formula: σL(g, h) = max{L(g, h), L(h, g)}.

Thus, σL is a genuine metric on Teichmüller space, and the following is an immediate consequence of Theorem 2.

Corollary 4. For any sequence (g n ) in Teichmüller space and for any h in that space, we have L(g n , h) → 0 if and only if L(h, g n ) → 0 if and only if σL(h, g n ) → 0 if and only if g n converges to h in the usual topology of Teichmüller space.

Since we have an asymmetric metric on Teichmüller space, it is natural to consider two topologies on that space, the first one being the topology generated by the collection of right open balls, and the second one being the topology generated by the collection of left open balls in that space. Here, a left (respectively right) open ball is defined as in 4 (respectively 5) above, except that the weak inequality is replaced by a strict inequality. For any asymmetric metric δ : X × X :→ [0, ∞), we denote by δ * : X × X :→ [0, ∞) the asymmetric metric that is dual to δ, that is, the asymmetric metric defined by δ * (x, y) = δ(y, x) for every x and y in X. We consider the topology on Teichmüller space that is generated by the collection of right open balls as being the one that is associated to Thurston's asymmetric metric L. Then, the topology generated by the collection of left open balls is the one associated to the dual asymmetric L * . It is easy to see, from Axioms A1, A2 and A3 satisfied by a nonsymmetric metric, that the following (which is well-known for a genuine metric) holds: a sequence (g n ) of points in Teichmüller space converges to a point g in that space for the topology generated by the left (respectively right) open balls if and only if we have L(g, g n ) → 0 (respectively L(g n , g) → 0) as n → ∞. Therefore, we can state Corollary 4 in the following equivalent form Corollary 5. The topologies on Teichmüller space defined by Thurston's asymmetric metric and by its dual asymmetric metric concide with the usual topology of that space. Now from Proposition 3 and Corollaries 4 and 5, we obtain the following Proposition 6. Teichmüller space equipped with Thurston's asymmetric metric is proper. More precisely, left and right closed balls are compact for the topology defined by that asymmetric metric.

H. Busemann developed a theory of spaces (X, δ) satisfying axioms A1, A2 and A3 and the following axiom A4: δ(x, x n ) → 0 ⇐⇒ δ(x n , x) → 0 for any x and for any sequence (x n ) in X.

On such a space, there is a natural associated topology, which is the one associated to the genuine metric max{δ(x, y), δ(y, x)}. Theorem 2 guarantees that Thurston's asymmetric metric satisfies A4. We state this as follows:

Corollary 7. Thurston's asymmetric metric satisfies Busemann's axioms.

Busemann introduced a notion of completeness for such spaces (see [START_REF] Busemann | Recent synthetic differential geometry[END_REF] Chapter 1). The definition is as follows. The space (X, δ) is complete if and only if for every sequence (x n ) in X satisfying δ(x n , x n+m ) → 0 as n and m → ∞, the sequence converges to a point in X.

In that setting, the following generalization of the classical theorem of Hopf and Rinow holds (see [START_REF] Busemann | Recent synthetic differential geometry[END_REF] Theorem 8 p. 4):

If a locally compact space (X, δ) satisfies Axioms A1, A2 A3 and A4 and if this generalized metric δ is "intrinsic", then the following two properties are equivalent:

(1) left closed balls in X are compact;

(2) X is complete. Here, the word intrinsic means that for any x and y in X, the value δ(x, y) is equal to the infimum of the lengths of all curves joining x and y in X. In this setting of generalized metrics, the length of a curve is defined in a way similar to the case of a genuine metric space. We do not need to enter into the details here, because by a result of Thurston (see [START_REF] Thurston | Minimal Stretch maps between hyperbolic surfaces[END_REF] §6), Thurston' s asymmetric metric L is geodesic (that is, any two points can be joined by an L-geodesic), which implies that it is intrinsic (see [START_REF] Busemann | Recent synthetic differential geometry[END_REF] p. 3). We should also note that a geodesic is defined here as the isometric image of an interval, except that we have to be careful about the order of the variables. More precisely, a map γ : Thus, we can state the following consequence of Proposition 6.

Corollary 8. Thurston's asymmetric metric is complete in the sense of Busemann.

Figure 1 .

 1 Figure 1. An example (due to Thurston) of hyperbolic sutructures g and h satisfying L(g, h) = L(h, g).

Figure 2 .

 2 Figure 2. An example of distinct hyperbolic structures g

Figure 3 .Figure 4 .

 34 Figure 3. A complete lamination whose stump is a simple closed geodesic γ.

  γ

Figure 5 .

 5 Figure 5. A rectangular cover of the surface, used in the proof of Lemma 2. The leaves of λ n are represented in dotted lines and the intersection of the rectangles with γ n is represented in bold lines. The width of a rectangle R is the transverse measure of the vertical edges of R.

  [a, b] → T(S), (where [a, b] is a closed interval of R) is a geodesic joining the two points γ(a) and γ(b) in T(S) if for all t and t in [a, b] we have |t -t | = L γ(t), γ(t ) .