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