Contents
Next: What is the
Up: The 3x+1 problem.
Previous: A heuristic argument.
It is Riho Terras's ingenious observation that although the behavior of the total
stopping time function seems hard to analyze, a great deal can be said
about the stopping time function.
He proved the following fundamental result ([67], [68]),
also found independently by Everett [31].
Theorem A
(Terras).
The set of integers has stopping time
has limiting asymptotic density , i.e., the limit
exists.
In addition,
as ,
so that almost all integers have a finite stopping time.
The ideas behind Terras's analysis seem basic to a deeper understanding
of the problem, so I describe them in detail.
In order to do this, I introduce some notation to
describe the results of the process of iterating the function .
Given an integer n, define a sequence of 0-1 valued
quantities by
where .
The results of first k iterations of T are completely described by the
parity vector
since the result of k iterations is
where
and
Note that in (2.5), (2.6) both and
are completely determined by the parity vector given by
(2.3); I sometimes indicate this by writing
(instead of .
The formula (2.4) shows that a necessary condition for is that
since is nonnegative.
Terras [67] defines the coefficient stopping time
to be the least value of k such that (2.7) holds,
and if no such value of k exists.
It is immediate that
The function plays an important role in the analysis of the
behavior of the stopping time function , see Theorem C.
The formula (2.2) expresses the parity vector
as a function of n.
Terra's idea is to reverse this process and express n as a function of .
Theorem B
The function defined by
is periodic with period .
The induced function is a
permutation, and its order is a power of 2.
[Proof]
The cycle structure and order of the first few permutations
are given in Table 2.
(One-cycles are omitted.)
It is interesting to observe that the order of the permutation
seems to be much smaller than the upper bound proved in
Theorem B.
Is there some explanation of this phenomenon?
TABLE 2. Cycle structure and order of permutation .
Theorem B allows one to associate with each vector of length k a unique congruence
class given by
The integer
with is the minimal element in and
is the arithmetic progression:
Now I consider the relation between a vector and stopping times for
integers .
Define a vector of length k
to be admissible if
- (1)
,
- (2)
, when .
Note that all admissible vectors of length k have
where
and denotes the largest integer .
The following result is due to Terras.
Theorem C
(Terras).
(a)
The set of integers with coefficient stopping time k are exactly
the set of integers in those congruence classes
for which there is an admissible vector of length k with .
(b) Let for some vector of length k.
If is admissible, then all sufficiently large integers congruent to
have stopping time k.
If is not admissible, then only finitely many integers
congruent to have stopping time k.
[Proof]
Theorem C asserts that the set of integers with a given coefficient
stopping time k is a set of arithmetic progressions
, which has the immediate consequence that has the
asymptotic density
which is given by
Furthermore Theorem C asserts that the set
differs from by a finite set, so that also has an asymptotic density
which is the same as that of .
Consequently, Theorem C implies the first part of Theorem A, that the set
of all integers with stopping time at most k have an asymptotic density
given by
where
Now the formula (2.16) can be used to prove the second part of Theorem A,
and in fact to prove the stronger result that approaches 1 at an exponential rate as .
Theorem D
For all ,
where
Here is the entropy
function and .
[Proof]
Theorem D cannot be substantially improved; it can be proved that for
any we have
for all sufficiently large k depending on .
Hence for any
holds for all sufficiently large k depending on .
Contents
Next: What is the
Up: The 3x+1 problem.
Previous: A heuristic argument.