help annotate
Contents Next: Do divergent trajectories Up: The 3x+1 problem. Previous: Behavior of the


A first observation is that there are other cycles if negative integers are allowed in the domain of the function. There is a cycle of period 1 starting from n = -1, and there are cycles of length 3 and 11 starting from n = -5 and n = -17, respectively. Böhm and Sontacchi [13] conjecture that these cycles together with the cycles starting with n = 0 and n = 1 make up the entire set of cycles occurring under iteration of applied to the integers . Several authors have proposed the following conjecture ([13], [28], [41], [67]).


There are only a finite number of distinct cycles for the function iterated on the domain .

One can easily show that for any given length k there are only a finite number of integers n that are periodic under iteration by T with period k, in fact at most such integers, as observed by Böhm and Sontacchi [13]. To see this, substitute the equation (2.4) into


to obtain the equation


There are only choices for the 0-1 vector , and for each choice of the equation (2.24) determines a unique rational solution . Consequently there are at most solutions to (2.23). Böhm and Sontacchi also noted that this gives an (inefficient) finite procedure for deciding if there are any cycles of a given length k, as follows: Determine the rational number for each of the vectors , and for each which is an integer test if (2.23) holds.

The argument of Böhm and Sontacchi is a very general one that makes use only of the fact that the necessary condition (2.24) for a cycle has a unique solution when the values are fixed. In fact, considerably more can be proved about the nonexistence of nontrivial cyclic trajectories using special features of the necessary condition (2.24). For example, several authors have independently found a much more efficient computational procedure for proving the nonexistence of nontrivial cyclic trajectories of period ; it essentially makes use of the inequality

which must hold for satisfying (2.24). This approach also allows one to check the truth of the Coefficient Stopping Time Conjecture for all n with . The basic result is as follows.

Theorem H

(Terras). For each k there is a finite bound given by


such that implies that whenever . Consequently:
(i) If for all , then there are no non-trivial cycles of length .
(ii) If for all , then implies .


Theorem H can be used to show the nonexistence of nontrivial cycles of small period by obtaining upper bounds for the and checking that condition (i) holds. This approach has been taken by Crandall [28], Garner [34], Schuppar [61] and Terras [67]. In estimating , one can show that the quantities are never very large, so that the size of is essentially determined by how large

can get. The worst cases occur when is a very close approximation to , i.e., when is a very good rational approximation to . The best rational approximations to are given by the convergents of the continued fraction expansion of . Crandall [28] uses general properties of continued fraction convergents to obtain the following quantitative result.

Theorem I

(Crandall). Let be the minimal element of a purely periodic trajectory of period k. Then


where is any convergent of the continued fraction expansion of with .

As an application, use Yoneda's bound [2] that and choose j = 13 in (2.26), noting that and , to conclude that there are no nontrivial cycles with period length less than 275,000.

Further information about the nonexistence of nontrivial cyclic trajectories can be obtained by treating the necessary condition (2.24) as an nonexponential Diophantine equation. Davidson [29] calls a purely periodic trajectory of period k a circuit if there is a value i for which


i.e., the parity vector has the special form


where . The cycle starting with is a circuit. Davidson observed that each solution to the exponential Diophantine equation


gives rise to a circuit of length k = a + b with and , and conversely. (The equation (2.28) is the necessary condition (2.24) specialized to the vector (2.27). R. Steiner [64] showed that is the only solution of (2.28), thus proving the following result.

Theorem J

(Steiner). The only cycle that is a circuit is the trivial cycle.


The most remarkable thing about Theorem J is the weakness of its conclusion compared to the strength of the methods used in its proof. The proof of Theorem J does have the merit that it shows that the coefficient Stopping Time Conjecture holds for the infinite set of admissible vectors of the form (2.27).

help annotate
Contents Next: Do divergent trajectories Up: The 3x+1 problem. Previous: Behavior of the