Are there non-trivial cycles?

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]).

FINITE CYCLES CONJECTURE. 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 .

[Proof]

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

and

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.

[Proof]

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).

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