help annotate
Contents Next: What is the Up: The 3x+1 problem. Previous: A heuristic argument.

[Annotate][Shownotes]


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

[Annotate][Shownotes]


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.

[Annotate][Shownotes]


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]

[Annotate][Shownotes]


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]

[Annotate][Shownotes]


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]

[Annotate][Shownotes]


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 .

help annotate
Contents Next: What is the Up: The 3x+1 problem. Previous: A heuristic argument.