# The Collatz Problem in the Light of an Infinite Free Semigroup

Authors: Manfred Trümper
Journal: Chinese Journal of Mathematics
 (2014)

---

## Abstract

The Collatz (or3
m
+
1) problem is examined in terms of a free semigroup on which suitable diophantine and rational functions are defined. The elements of the semigroup, called T-words, comprise the information about the Collatz operations which relate an odd start number to an odd end number, the group operation being the concatenation of T-words. This view puts the concept of encoding vectors, first introduced in 1976 by Terras, in the proper mathematical context. A method is described which allows to determine a one-parameter family of start numbers compatible with any given T-word. The result brings to light an intimate relationship between the Collatz 3
m
+
1 problem and the 3
m
-
1 problem. Also, criteria for the rise or fall of a Collatz sequence are derived and the important notion of anomalous T-words is established. Furthermore, the concept of T-words is used to elucidate the question what kind of cycles—trivial, nontrivial, rational—can be found in the Collatz 3
m
+
1 problem and also in the 3
m
-
1 problem. Furthermore, the notion of the length of a Collatz sequence is discussed and applied to average sequences. Finally, a number of conjectures are proposed.


---

## Body

## 1. Introduction

The (3
m
+
1) problem, first posed by Lothar Collatz in 1937, concerns the behavior of natural numbers under the recurrence function n
=
3
m
+
1 for odd m and n
=
m
/
2 for even m. The Collatz conjecture says that, for any natural number, the iteration leads to thetrivial cycle 1, 4, 2, 1. Historical accounts of the Collatz problem have been given, for example, by Lagarias [1], Wirsching [2], and others.The application of the Collatz rules to a given start numberM will always result in a sequence of uniquely determined integers. It will be referred to as theCollatz sequence attached to M. Only start numbers which are odd will be considered. This simplifies the arguments while not restricting in any way the generality of the results.We also recall the simple fact that, for all integersm inside a Collatz sequence, it holds that 3
∤
m, i.e. m cannot be divided by 3. This is so because 3
m
+
1 is in the residue class 1
mod
⁡
3 and divisions by 2 cannot result in a number which has divisor 3. Integers which have a divisor 3 can occur only either as start numbers or as even ones preceding a start number.Since the Collatz operations have unique inverses, we can also consider a sequence going backwards. However, Collatzbackward sequences are not unique because there are branch points. The branch points are the integers n satisfying at the same time n
≡
0
(
mod
⁡
2
) and n
≡
1
(
mod
⁡
3
). To such n, one can either apply the inverse operation m
=
(
n
-
1
)
/
3 or one can multiply it by an even power of 2 (the reason being that n
≡
2
(
mod
⁡
3
) implies 2
n
≡
1
(
mod
⁡
3
)). Thus, in order to uniquely fix the backward sequence, one has to specify how to proceed at branch points.Consider, for example, the start number17 with the sequence 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Branch points are (from right to left) 4, 16, 10, 40. The backward sequence could branch from 4 down to 1 or up to 16 and from 16 up to 64 or 256 and so on.This situation calls for some encoding of a Collatz sequence. Terras [3] wrote the symbols 1 and 0 for the operations 3
m
+
1 and m
/
2, respectively, and listed them in the order in which they appear (from left to right), such as (
1,0
,
0,1
,
0,0
,
0,1
,
0,0
,
0,0
) for the example given above. He called this objectencoding vector. A “component” of this vector is also the parity of the integer which triggers the respective operation. Lagarias [1] modified the terminology and called the same objectparity vector. However, though one could go along with the terms “encoding” or “parity,” the object in question is not a vector but rather the element of a free semigroup.The symbols used in the present paper will beu (for “up”) to designate the operation 3
m
+
1 and d (for “down”) to designate the operation m
/
2. The sequence of operation symbols will be referred to asT-word. This is an acceptable terminology since the elements of a free group are usually called “words.” The prefix T is chosen in commemoration of Riho Terras who seems to have been first to have coded a Collatz sequence. For the start number 17, mentioned in the preceding paragraph, the T-word would be written as w
=
u
d
d
u
d
d
d
u
d
d
d
d or, shorter, w
=
u
d
2
u
d
3
u
d
4.Remark on Notation. Since any operation u results in an even integer, it is always followed by an operation d. Therefore, we will frequently use the abbreviation s
:
=
u
d. The letter “s” is taken from the termspike which is what it resembles in graphics. Use of this notation makes a T-word shorter. For example, the T-word resulting from the start number 17 would be written as w
=
s
d
s
d
d
s
d
d
d or s
d
s
d
2
s
d
3. In the following, both notations will be used. The reason is that key formulas and relations will be simpler and easier to memorize in the “u” notation.In fact, the T-words (with the concatenation of words as composition rule) form a semigroup𝒲.The typical element of𝒲 is a T-word of the general form
(1)
w
=
u
d
x
1
u
d
x
2
u
d
x
3
⋯
u
d
x
y
-
1
u
d
x
y
,
where y is the number of u-operations in w. The exponent x
3 is, for example, the number of d-operations following the third u-operation.The total number ofd-operations in a T-word is then
(2)
x
:
=
x
1
+
x
2
+
⋯
x
y
.
The corresponding number sequence, called arealization of the T-word, begins with an oddstart number  M and terminates with an oddend number  N. That sequence is composed of x even integers and of y
+
1 odd integers. To exclude triviality, we require thatstart numbers are odd. To allow seamless concatenation, we then must require also thatend numbers are odd.Note that eachu-operation yields an even integer and is thus followed by at least one d-operation. Therefore we have x
k
≥
1 for 1
≤
k
≤
y and thus x
≥
y.The generators of the semigroup are the T-wordsu
d
x with x
∈
ℕ and y
=
1, i.e. u
d, u
d
2, u
d
3
,
….Under the group operation, the concatenation of any two T-wordsw
a and w
b, a new T-word w
=
w
a
w
b is uniquely defined. The operation is not commutative, but it is associative; i.e.
(3)
w
a
(
w
b
w
c
)
=
(
w
a
w
b
)
w
c
.
The unit element is the empty string of characters, which will be denoted by  e. We have w
e
=
e
w
=
w.From the above, it follows that both the order of the semigroup𝒲 and the number of generators of 𝒲 are ℵ
0.It is easy to enumerate infinite sets of subsemigroups of𝒲. Consider all T-words ending in the same generator u
d
n, say. For any n
∈
ℕ, they form a countably infinite sub-semigroup. Of particular interest later in this paper will be the case n
=
1, i.e. the set of all T-words ending in u
d. They will be referred to asreduced  T-words.More generally, all T-words of the formw
w
f with fixed w
f form a sub-semigroup. Likewise, for all T-words of the form w
i
w with fixed w
i.In unique fashion, the semigroup can be extended to a full group. This is done by adding to𝒲 the inverses of all elements to the semigroup. The inverse w
-
1 of each element w is unique since the inverses of the Collatz operations are uniquely defined. However, when extending the semigroup to the full group, some of the elements can no longer be represented by integers but only by rational numbers. This item will be considered in Section 4.The present paper does not solve the Collatz problem but puts it into a new mathematical context which has already brought new insights. As Wirsching [4] noted, “the strategy for finding interesting things about an “intractable” problem is threefold: translate the conjecture into as many different contexts as you can, formulate weaker statements implied by the conjecture in question and try to prove some of them, and wait for flashes of genius giving new and interesting insights.”


## 2. Realizations of a T-Word. The Rescale Procedure

To find the T-word which is attached to a given start number is an easy task. To establish a relation between the start and end numbers of a given T-word is a matter of straightforward calculation which was first done by Böhm and Sontacchi [5].However, to find all start numbers to which a given T-word is attached is not quite obvious. This problem has been solved by Trümper [6]. The method and the results are described in the following. It will be seen that its solution will permit new and deep insights into the Collatz problem. Moreover, the method lends itself easily to numerical applications.A sequence of integers which follow the operations spelled out by a T-wordw will be called arealization of
w. The task of this section will be to describe a systematic procedure allowing to determine all realizations for any given T-word.Though, in general, it is impossible to give closed form expressions for the realizations of a T-word, it can be done for some simple T-words, with methods adapted to the particularity of the case. Two examples will be given below.Example 1.
To find the set of start numbers and end numbers for the simplest type of T-word, i.e. a generatorw
=
u
d
x. The task is simple, but it is of basic importance since the generators are the building blocks of all T-words.
We begin by writing the defining relation for a generator. It isN
=
(
1
/
2
x
)
·
(
3
M
+
1
). To every odd start number M this relation uniquely assigns a natural number x
≥
1 and an odd end number N. Since the Collatz operations have unique inverses, the equation can also be written as M
=
(
1
/
3
)
·
(
2
x
N
-
1
). But now we cannot say that a given end number N determines x and M in a unique way. The reason is that 2
x
N
-
1 has a divisor 3 only if 2
x
N
≡
1
(
mod
⁡
3
). To which residue class 2
x
N belongs depends on both x and N. If N
≡
1
(
mod
⁡
3
), then x
≡
0
(
mod
⁡
2
). If N
≡
2
(
mod
⁡
3
), then x
≡
1
(
mod
⁡
2
). Note that N
≡
0
(
mod
⁡
3
) cannot happen.
Thus, if we want to write the start numberM as a diophantine function of N, we must distinguish the two cases where x is even or odd.
Case  x
≡
0
(
mod
⁡
2
). It requires N
≡
1
(
mod
⁡
3
) and, since N must be odd, it takes the form
(4)
N
k
=
6
k
-
5
with k
∈
ℕ. Then we get
(5)
M
k
=
2
x
+
1
k
-
1
3
(
5
·
2
x
+
1
)
.
Case  x
≡
1
(
mod
⁡
2
). It requires N
≡
2
(
mod
⁡
3
) and, since N must be odd, it takes the form
(6)
N
k
=
6
k
-
1
with k
∈
ℕ. Then we get
(7)
M
k
=
2
x
+
1
k
-
1
3
(
2
x
+
1
)
.
The start numbers have now got an index k which labels the differentrealizations of the generator.Remark.
Forx
=
2, we have w
=
u
d
d, the T-word for thetrivial cycle. Indeed, with k
=
1, we get, from (4) and (5), M
1
=
1 and N
1
=
1.These results on the numerical realizations of the generators of𝔊
𝔰 are summarized as follows.Lemma 1.
A generatoru
d
x of 𝔊
𝔰 has realizations with start numbers M
k and end numbers N
k, k
∈
ℕ, which are determined by
(8)
M
k
=
A
M
·
k
-
M
¯
,
N
k
=
A
N
·
k
-
N
¯
,
with
(9)
A
M
=
2
·
2
x
,
A
N
=
2
·
3
y
,
k
∈
ℕ
and with y
=
1. The quantities M
¯ and N
¯ are given by
Case  x
≡
0
(
mod
⁡
2
). M
¯
=
(
1
/
3
)
(
5
·
2
x
+
1
), N
¯
=
5,
Case  x
≡
1
(
mod
⁡
2
). M
¯
=
(
1
/
3
)
(
2
x
+
1
), N
¯
=
1.Note thatM
¯ and N
¯ are natural numbers satisfying
(10)
M
¯
≡
1
(
mod
⁡
2
)
,
M
¯
<
2
·
2
x
,
N
¯
≡
1
(
mod
⁡
2
)
,
N
¯
<
2
·
3
y
.
The integers A
M
=
2
·
2
x and A
N
=
6 are, respectively, referred to as thestart period and theend period of the generator u
d
x.We will refer toM
¯ as thestart phase and to N
¯ as theend phase of the generator u
d
x.That the expressions (4), (5), (6), and (7) for the realizations of T-word generators can be obtained in closed form is due to the structural simplicity of generators. But even for this simplest of all T-words, the distinction between the parity of the parameter x comes into play, giving rise to two different expressions. In the next simplest case, one of two concatenated generators, w
=
u
d
x
1
u
d
x
2, we would have to deal with four cases, namely, those where (
x
1
,
x
2
) is (even, even), (even, odd), (odd, even), or (odd, odd).Example 2 (the T-word(
u
d
)
y).
It represents the steepest possible increase of a Collatz sequence. Withx
=
y, this T-word has the minimal number of d-operations. By one operation u
d, the start number M is changed to n
1
=
(
1
/
2
)
(
3
M
+
1
) which will be rewritten as n
1
=
(
3
/
2
)
M
+
3
/
2
-
1. Now the second operation u
d will result in n
2
=
(
3
/
2
)
n
1
+
3
/
2
-
1 which gives n
2
=
(
3
/
2
)
2
M
+
(
3
/
2
)
2
-
1. Therefore, after y operations u
d, the result will be n
y
=
(
3
/
2
)
y
M
+
(
3
/
2
)
y
-
1. Up to here, M could be any real number. The condition that M is an odd integer means M
=
2
k
-
1, k
∈
ℕ. With this expression, one gets n
y
=
2
(
3
/
2
)
y
·
k
-
1. In order that this end number is an odd integer for all natural numbers k, the re-scale substitution k
→
2
y
k needs to be done. It yields n
y
=
2
·
3
y
·
k
-
1, the end number N
k of the Collatz sequences belonging to the T-word.From here, the repeated application of the inverse operationm
=
(
1
/
3
)
(
2
n
-
1
) yields the start number
(11)
M
k
=
2
·
2
x
·
k
-
1
,
the end number being
(12)
N
k
=
2
·
3
y
·
k
-
1
,
with x
=
y and k
∈
ℕ. In this example, it is the structural simplicity of the T-word which permits a realization in closed form.To treat the general case, one needs a systematic procedure which is applicable to any T-word. It is best demonstrated for a relatively simple T-word, for example,w
=
u
d
u
d
d.The start numberM, required to be an odd integer, is written as M
=
2
k
-
1. The operation u will take it to the even integer 6
k
-
2 which, by the operation d, will give 3
k
-
1. This expression should be odd since, according to the T-word, the next operation will be u. It will be made odd for all values of k by rescaling k
→
2
k. The result will be the integer 6
k
-
1.Now the operationu yields the even integer 18
k
-
2 and d gives 9
k
-
1. This expression should be even since the next operation to be performed is d. It will be made even for all values of k by rescaling k
→
2
k
-
1. The result will be the integer 18
k
-
10. The operation d now yields 9
k
-
5. Since this integer must be odd, the rescaling k
→
2
k will be applied to give 18
k
-
5. We now got the end number N
=
18
k
-
5 for the T-word w.The start number will be obtained by applying iteratively toM
=
2
k
-
1 all 3 rescale substitutions which were done above. The result is M
=
16
k
-
5.Checking the result with the T-wordu
d
u
d
d gives the sequence 16
k
-
5, 48
k
-
14, 24
k
-
7, 72
k
-
20, 36
k
-
10, 18
k
-
5.The role of the rescale substitutions is summed up by saying that they are done to assure the correct parity of each integer which is obtained by the Collatz operation prescribed by the T-word.The re-scale procedure provides the means to numerically calculate the start and end numbers for any given T-word. The author of this paper has developed a computer program able to deal with T-words having a length of up to about32000 letters.For instance, the unusually long Collatz series with start numberM
=
27 and end number N
=
1 has the T-word (we are abbreviating s
:
=
u
d)
(13)
w
=
s
s
d
s
4
s
d
s
d
s
s
d
s
s
s
d
s
3
s
d
s
d
d
s
s
s
d
s
s
d
s
5
s
d
d
s
3
s
d
3
s
d
s
d
s
d
3
s
d
d
s
s
s
d
4
s
d
3
.
It is made up of 41 generators with a total of 70
d-operations. The number of steps is y
+
x
=
41
+
70
=
111. The start period is 2
·
2
70 and the end period is 2
·
3
41.The re-scale procedure yields the realizations(14)
M
k
=
2361183241434822606848
·
k
-
2361183241434822606821
,
N
k
=
72945992754341572806
·
k
-
72945992754341572805
with k
∈
ℕ. For k
=
1, this gives indeed M
=
27 and N
=
1.Using the computer program mentioned above, the calculation of these numbers takes just a fraction of a second.Since this sequence has attracted a certain amount of public attention—it figures in Hofstadter’s cult book “Gödel, Escher, Bach” [7]—we will carry it as an example throughout this paper and note it’s relevant properties and characteristics as they are conceptually developed.We will now describe an alternate method to calculate the start and end numbers for all realizations of a given T-word. It is based on a given T-word with already known start and end numbers which will be appended in either of the following ways. Either, replace the last (i.e., rightmost) generator by one with an additionald in it. Or, append the T-word by the generator u
d. All possible extensions of a T-word can be derived by combining these two operations.Theorem 1.
Letw be a T-word with y  up operations and x  down operations whose realizations have start and end numbers described by (8) and (9). Let w
′ be the T-word which is obtained from w by replacing the last (rightmost) generator u
d
x
y by u
d
x
y
′ where x
y
′
=
x
y
+
1.
Let the realizations ofw
′ have start and end numbers
(15)
M
k
′
=
A
M
′
·
k
-
M
′
¯
,
N
k
′
=
A
N
′
·
k
-
N
′
¯
.
Then the start periods and end periods of w and w
′ are related by
(16)
A
M
′
=
2
A
M
,
A
N
′
=
A
N
.
The start phase and end phase of w
′ are as follows.Case  (
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
)
is odd). Consider
(17)
M
′
¯
=
M
¯
+
1
2
A
M
,
N
′
¯
=
1
2
(
N
¯
+
1
2
A
N
)
,Case  (
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
)
is even). Consider
(18)
M
′
¯
=
[
M
¯
+
3
2
A
M
]
(
mod
⁡
2
A
M
)
,
N
′
¯
=
[
1
2
(
N
¯
+
3
2
A
N
)
]
(
mod
⁡
A
N
)
.Proof.
The operation “d” cannot be performed on N
k since this quantity is an odd integer. Therefore one has to go back to the integer (
1
/
2
)
A
N
·
k
-
N
¯ from which N
k had been obtained by the rescaling substitution k
→
2
k. That this is always the final re-scale step is shown in Table 1. This table describes the logic of the re-scale procedure which has the aim to assure that appropriate expressions of the form A
·
k
-
B are odd for any natural number k.
Now, by the re-scale substitutionk
→
2
k
-
1, the expression (
1
/
2
)
A
N
·
k
-
N
¯ will become A
N
·
k
-
(
N
¯
+
(
1
/
2
)
A
N
). This expression evidently is even since A
N is even and and both terms in the round bracket are odd. Performing the operation “d” now yields (
1
/
2
)
A
N
·
k
-
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
). The final re-scale substitution to be performed depends on the parity of the last term. Again, two cases have to be considered.
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
) is odd. Rescaling k
→
2
k yields N
k
′
=
A
N
·
k
-
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
). Applying the same rescaling substitutions to M
k
=
(
1
/
2
)
A
M
·
k
-
M
¯, one finds M
k
′
=
2
A
M
·
k
-
(
M
¯
+
(
1
/
2
)
A
M
). From these relations for M
k
′ and N
k
′, one gets (17).
(
1
/
2
)
(
N
¯
+
(
1
/
2
)
A
N
) is even. Rescaling by k
→
2
k
-
1 yields the expression A
N
·
k
-
(
1
/
2
)
(
N
¯
+
(
3
/
2
)
A
N
). Here it should be noted that, for sufficiently large N
¯, the last term, (
1
/
2
)
(
N
¯
+
(
3
/
2
)
A
N
), may come out to be ≥A
N
′. Therefore that term is rewritten as [
(
1
/
2
)
(
N
¯
+
(
3
/
2
)
A
N
)
]
(
mod
⁡
A
N
′
). Thus, in the present case, it holds N
k
′
=
A
N
·
k
-
[
(
1
/
2
)
(
N
¯
+
(
3
/
2
)
A
N
)
]
(
mod
⁡
A
N
) where we have made use of the relation A
N
′
=
A
N. Now, similar reasoning as in the previous case yields M
k
′
=
2
A
M
·
k
-
(
M
¯
+
(
3
/
2
)
A
M
)
(
mod
⁡
2
A
M
). From here, one gets (18).Table 1
Logic of the re-scale procedure.
Case
A
B
Action
Result
1
Even
Even
Divide by2
any case
2
Even
Odd
None
Ok
3
Odd
Even
k
→
k
-
1
Case  4
4
Odd
Odd
k
→
2
k
Case  2Note that the 3 equations (16), (17), and (18) can be used to verify Lemma 1.The second extension of a T-wordw to be investigated is the concatenation of a generator which is a true group operation. In contrast, the extension considered in Theorem 1, i.e. appending an operation “d”, does not qualify as a group operation since “d” is not an element of the semigroup.Theorem 2.
Letw be a T-word with y up operations and x down operations with start and end numbers described by (8) and (9). Then the possible start and end numbers of w
′
=
w
u
d, expressed by those of w, are given by
(19)
M
k
′
=
A
M
′
·
k
-
M
′
¯
,
N
k
′
=
A
N
′
·
k
-
N
′
¯
with
(20)
A
M
′
=
2
A
M
,
A
N
′
=
3
A
N
,
andif(
1
/
2
)
(
3
N
¯
-
1
) is odd:
(21)
M
′
¯
=
M
¯
,
N
′
¯
=
1
2
(
3
N
¯
-
1
)
,
if(
1
/
2
)
(
3
N
¯
-
1
) is even:
(22)
M
′
¯
=
M
¯
+
A
M
,
N
′
¯
=
1
2
(
3
N
¯
-
1
)
+
3
2
A
N
.Proof.
All that is to be done is to subject the end numberN
k of w to the group operation u
d. Thus N
k
=
A
N
·
k
-
N
¯ will be taken to N
k
′
=
(
3
/
2
)
A
N
·
k
-
(
1
/
2
)
(
3
N
¯
-
1
). Here, the first term is even or odd depending on the parity of k but can always be made even by a re-scale substitution. The second term may also be even or odd and needs to be made odd. Thus two cases have to be distinguished.
(
1
/
2
)
(
3
N
¯
-
1
) is odd. Rescaling k
→
2
k gives N
k
′
=
2
A
N
·
k
-
(
1
/
2
)
(
3
N
¯
-
1
) and M
k
′
=
2
A
M
·
k
-
M
¯ and thus yields (20) and (21).
(
1
/
2
)
(
3
N
¯
-
1
) is even. Rescaling k
→
2
k
-
1 gives N
k
′
=
3
A
N
·
k
-
(
1
/
2
)
(
3
N
¯
-
1
)
-
(
3
/
2
)
A
N and M
k
′
=
2
A
M
·
k
-
(
A
M
+
M
¯
) and thus yields (20) and (22).Theorems1 and 2 show that a T-word (1) has an infinite number of realizations whose start and end numbers are given by
(23)
M
k
=
A
M
·
k
-
M
¯
,
N
k
=
A
N
·
k
-
N
¯
,
with
(24)
A
M
=
2
·
2
x
,
A
N
=
2
·
3
y
,
k
∈
ℕ
.
By iteration, (16) through (22) allow to calculate the start and end numbers for the realizations of any given T-word under the Collatz rules. The iteration may be started with the simplest of all T-words, i.e. the generator u
d whose realizations have start numbers M
k
=
4
k
-
1 and end numbers N
k
=
6
k
-
1. For example, the formulas of Lemma 1 may be verified by use of Theorem 1.Knowing the start numbers of a given T-word gives an unprecedented control over the integers in the corresponding Collatz sequence.As an example, the T-wordw
=
[
(
u
d
)
7
d
4
)
]
16 will now be considered. Here we have x
=
11
·
16
=
176 and y
=
7
·
16
=
112.The start number of thekth realization, as obtained by the re-scale procedure, is given by
(25)
M
k
=
2
·
2
176
·
k
-
M
¯
,
where
(26)
M
¯
=
111629621232137587704160170143143025065753479223805569
.
The end number is
(27)
N
k
=
2
·
3
112
·
k
-
N
¯
with
(28)
N
¯
=
319213127260756942963527814105978335506079692252926759
.Figure1 shows the Collatz sequences for k
=
1
,
2
,
3, with all numbers (even and odd) pictured. The sequences end at step number 288 and from thereon the usual erratic behavior of the values appears.Figure 1Figure2 depicts the entire Collatz series. But, here, only the odd numbers are shown. This is done to avoid unnecessary clutter in the picture.Figure 2Figure3 shows, always for the same T-word, the odd values for the entire 3
m
+
1 and 3
m
-
1 sequences. The start number M
¯ for the 3
m
-
1 sequence is higher than the start number M for the 3
m
+
1 sequence.Figure 3In the next section, it will be shown that the phasesM
¯ and N
¯ are nothing else than the start and end number of the first realization of the same T-word under the 3
m
-
1 rule. Thus it will become clear to which extent the 3
m
+
1 problem and the 3
m
-
1 problem are interlaced and how some special features of the latter influence the former one.


## 3. The3
m
+
1 Rule, the 3
m
-
1 Rule, and the Link Function

The basic equations (23) and (24) give the start and end numbers of the realizations of a T-word described by (1). The start number M
k must yield the Collatz sequence described by the T-word. If the first generator of the T-word, u
d
x
1, is applied, the start number will be taken to the next odd integer by
(29)
A
M
·
k
-
M
¯
⟶
1
2
x
1
·
[
3
A
M
·
k
-
(
3
M
¯
-
1
)
]
.
This relation shows that, along the T-word, the phase M
¯ will evolve according to the 3
m
-
1 rule. It will follow the prescription of the T-word but with an operation “u” which now means the multiplication of an odd integer by the factor 3 and subsequentsubtraction of 1.Thus the Collatz sequence belonging to a realization of a T-word is mimicked by the3
m
-
1 sequence whose start number is the start phase of the Collatz sequence.From now on, integers which are obtained by the3
m
-
1 rule will be marked by an upper index “—” which is converted to a bar over the symbol. Equations (23) may now be rewritten in the more symmetric form
(30)
M
k
+
M
¯
=
2
·
2
x
·
k
,
(31)
N
k
+
N
¯
=
2
·
3
y
·
k
.
And, in particular for k
=
1 and with M
:
=
M
1 and N
:
=
N
1, we have
(32)
M
+
M
¯
=
A
M
,
N
+
N
¯
=
A
N
.
The last two equations tell us that for any T-word, it holds
(33)
M
≠
M
¯
,
N
≠
N
¯
.
The reason is that M
=
M
¯ would imply M
=
2
x, contradicting our assumption that M is odd. Similarly, N
=
N
¯ would imply N
=
3
y, contradicting the fact that 3 cannot divide N.Now, by reasoning perfectly analogous to the one of Theorems1 and 2, one may determine the realizations of a T-word under the 3
m
-
1 rule. This will result in the following.Theorem 3.
Under the3
m
-
1 rule, a T-word w having x down operations and y up operations uniquely determines the odd integer M
¯ such that, for any k
∈
ℕ,
(34)
M
¯
k
=
A
M
·
k
-
M
=
2
·
2
x
·
k
-
M
is the start number of the kth (
3
m
-
1
) realization of w where the integer M
(
:
=
M
1
) is the start number of the first (
3
m
+
1
) realization of w.
Likewise, the end numbers of this realization are(35)
N
¯
k
=
A
N
·
k
-
N
=
2
·
3
y
·
k
-
N
,
where N
(
:
=
N
1
) is the end number of the first (
3
m
+
1
) realization of w.
Realizations of Simple T-Words under the
3
m
-
1
RuleExample 3.
Realizations of a generatoru
d
x under the (3
m
-
1) rule.
Case where
x
is even. From (4) and (34) one gets M
¯
k
=
2
x
+
1
·
k
-
[
2
x
+
1
-
(
1
/
3
)
(
5
·
2
x
+
1
)
] which simplifies to(36a)
M
¯
k
=
2
x
+
1
·
k
-
1
3
(
2
x
-
1
)
.
Equations (5) and (35) yield
(36b)
N
¯
k
=
6
k
-
1
.
Case where
x
is odd. From (6), one gets M
¯
k
=
2
x
+
1
·
k
-
[
2
x
+
1
-
(
1
/
3
)
(
2
x
+
1
)
] which simplifies to(37a)
M
¯
k
=
2
x
+
1
·
k
-
1
3
(
5
·
2
x
-
1
)
,
while (7) and (35) yield
(37b)
N
¯
k
=
6
k
-
5
.Example 4.
Realizations of the T-word(
u
d
)
y under the 3
m
-
1 rule.
From (11) and (34), one gets
(38)
M
¯
k
=
2
·
2
x
·
(
k
-
1
)
+
1
=
2
·
2
x
·
k
-
(
2
·
2
x
-
1
)
,
while (12) and (35) imply
(39)
N
¯
k
=
2
·
3
x
·
(
k
-
1
)
+
1
=
2
·
3
y
·
k
-
(
2
·
3
y
-
1
)
,
with x
=
y and k
∈
ℕ.
Note that, fork
=
1, one gets M
¯
=
N
¯
=
1, i.e. the trivial cycle.Now, as shown by (30) to (35), there is perfect symmetry, on one hand, between the integers M
k, N
k which belong to the 3
m
+
1 implementation of a T-word and, on the other hand, the integers M
¯
k, N
¯
k which belong to the 3
m
-
1 implementation of the same T-word. If one eliminates k from these equations and uses some elementary algebra, one finds the relations
(40)
2
x
N
k
-
3
y
M
k
=
2
x
N
-
3
y
M
,
(41)
2
x
N
¯
k
-
3
y
M
¯
k
=
2
x
N
¯
-
3
y
M
¯
,
(42)
2
x
N
-
3
y
M
=
-
(
2
x
N
¯
-
3
y
M
¯
)
.
According to (40), the integer 2
x
N
k
-
3
y
M
k is independent of k and so is the integer 3
y
M
¯
k
-
2
x
N
¯
k, as shown by (41). And all the integers occurring in these equations can be expressed in terms of 2
x
N
-
3
y
M. Now, the evaluation of 2
x
N gives the expression
(43)
2
x
N
=
2
x
1
+
⋯
+
x
y
·
1
2
x
y
×
(
3
2
x
y
-
1
(
⋯
(
3
2
x
1
(
3
M
+
1
)
+
1
)
+
⋯
)
+
1
)
which can be rewritten as
(44)
2
x
N
-
3
y
M
=
L
,
where
(45)
L
(
w
)
:
=
3
y
-
1
+
ξ
1
·
3
y
-
2
+
⋯
+
ξ
k
·
3
y
-
k
-
1
+
⋯
+
ξ
y
-
2
·
3
+
ξ
y
-
1
with
(46)
ξ
k
:
=
2
x
1
+
x
2
+
⋯
x
k
,
1
≤
k
≤
y
-
1
.
More explicitly, in terms of the parameters x
1 to x
y
-
1 and y, the function L is written as
(47)
L
(
w
)
=
3
y
-
1
+
2
x
1
3
y
-
2
+
2
x
1
+
x
2
3
y
-
3
+
⋯
+
2
x
1
+
⋯
+
x
y
-
1
.The three equations (40), (41), and (42) can now be rewritten as(48a)
3
y
M
k
-
2
x
N
k
=
-
L
,
(48b)
3
y
M
¯
k
-
2
x
N
¯
k
=
L
.Note the difference in the sign of L between the two formulas. Also, since the two equations hold for all values of k, this index may just be dropped.L
(
w
) will be called thelink function of the T-word
w because for any T-word w
(i)
and for any realization ofw under whatever rule, 3
m
+
1 or 3
m
-
1, it links the start number to the end number,
(ii)
it links the integers derived from the3
m
+
1 rule to their analogues derived from the 3
m
-
1 rule.Equation (47) shows that the link function L is a sum of terms each of which is the product of a power of 2 and a power of 3. Terms of this kind have already attracted the interest of medieval mathematicians like Philippe de Vitry (cf. Carlebach [8]) who, with musical harmonies in mind, called themharmonic numbers.Equation (44) provides criteria for the existence of a cycle. The condition for a cycle, namely that the start number M equals the end number N, immediately yields
(49)
(
2
x
-
3
y
)
M
=
L
.
This condition shows, that for a cycle to exist under the (3
m
+
1) rule, the integer
(50)
D
:
=
2
x
-
3
y
must be positive and must divide L.On the other hand, for a cycle to exist under the (3
m
-
1) rule,
(51)
(
3
y
-
2
x
)
M
¯
=
L
has to be satisfied. Since M and L are positive, D must be negative and the positive quantity
(52)
D
¯
:
=
3
y
-
2
x
=
-
D
must divide L.The question of cycles will be discussed in greater detail in Section5.Equations which are equivalent to (44) and to the cycle conditions (49) and (51) have first been published by Böhm and Sontacchi [5] in 1978. These authors used negative integers under the 3
m
+
1 rule to describe what here is treated as positive integers under the 3
m
-
1 rule.The traditional view considers the3
m
-
1 problem as the application of the Collatz (
3
m
+
1
) rule to negative numbers.Both treatments are equivalent, as far as the calculation of the corresponding number sequences is concerned.The traditional view seems to have the advantage that there is only the3
m
+
1 rule which needs to be considered. However, it diverts attention from the fact that the 3
m
+
1 problem and the 3
m
-
1 problem—though related—are quite different from each other.The equation given by Böhm and Sontacchi applies indeed to both cases, i.e. positive and negative integers as start numbers. But it does not bring to light the important role played by the link functionL. In fact, Böhm and Sontacchi did not pay attention to the properties of L because the importance of this function was not visible in the context of the traditional view. To my knowledge, the properties of the link function have never been carefully investigated, nor the intriguing differences between the functions D and D
¯.In Section1, the diophantine functions x and y have been introduced. They are defined on the semigroup and they express summary information about the T-word. They are now joined by the link function which expresses detailed information about the T-word. As these functions are playing a key role in the discussion of the 3
m
+
1 and the 3
m
-
1 problem, their properties will be investigated more closely.Range of Values of
x
,
y
,
L
y: Number of generators in a T-word, y
≥
1.
x: Number of down operations in a T-word, x
≥
y.
D: Range is -
∞
<
D
<
+
∞, is odd, and is not divided by 3.
L: Link function, that yields a natural number which is odd and is not divided by 3. For the lower and upper value of the link function for given x and y, see (39) below.Here we want to give the value of the link function for two T-words treated as examples in Sections1 and 2 (remember that s
:
=
u
d).Example of Section1 (M
=
17), T-word w
=
s
d
s
d
d
s
d
d
d: One has x
=
9, y
=
3, D
=
485, and L
=
53.Example of Section2 (M
=
27), T-wordw
=
s
s
d
s
s
s
s
s
d
s
d
s
s
d
s
s
s
d
s
s
s
s
d
s
d
d
s
s
s
d
s
s
d
s
s
s
s
s
s
d
d
s
s
s
s
d
d
d
s
d
s
d
s
d
d
d
s
d
d
s
s
s
d
d
d
d
s
d
d
d:x
=
70,  y
=
41,D
=
1144118624340240517021 (
=
11.441
…
×
1
0
20
),L
=
195820718533800070543
(
=
1.958
…
×
1
0
20
).Composition Laws. For a T-word w
=
w
a
w
b, obtained from two T-words w
a and w
b by concatenation, it holds
(53)
x
(
w
)
=
x
(
w
a
)
+
x
(
w
b
)
=
x
a
+
x
b
,
(54)
y
(
w
)
=
y
(
w
a
)
+
y
(
w
b
)
=
y
a
+
y
b
,
(55)
D
(
w
)
=
3
y
b
D
(
w
a
)
+
2
x
a
D
(
w
b
)
,
(56)
L
(
w
)
=
3
y
b
L
(
w
a
)
+
2
x
a
L
(
w
b
)
.
While (53) and (54) are obvious, (55) is easily deduced from (50). Equation (56) is proved by writing the defining equation (47) and then dividing the sequence of terms into the two parts belonging to w
a and w
b.Attention is drawn to the truly remarkable similarity of the composition laws for the two key functions relating to T-word.Worth mentioning are these further properties of the functions defined on the semigroup. Consider(57)
x
(
e
)
=
0
,
y
(
e
)
=
0
,
L
(
e
)
=
0
,
D
(
e
)
=
0
,
(58)
L
(
u
d
x
)
=
1
∀
x
.
The last equation is obtained directly from (47).For another remark relating to the concatenation of T-words, see the end of this section.Further Remarks on
L
and
D. All of the quantities considered here, x, y, L, and D, are unique diophantine functions of a T-word w.Both functionsL
(
w
) and D
(
w
) are of similar structure, both being finite sums of powers of the integers 2 and 3. Both are nonzero, and neither D nor L have 2 or 3 as a divisor. However, while D can be either positive or negative, L is always positive.Further results about the functionD will be presented in Section 7.Equation (56) is of basic importance to the T-word approach. Together with (58), it may be considered as a definition of L. Indeed, for a given T-word (1), repeated application of (56) and (58) will result in (47).Similarly, (55) together with the relation D
(
u
d
x
)
=
2
x
-
3 may be taken as a definition of D.Clearly, those quantities which only express summary information about the T-word, such asx, y, and D, are maps of the semigroup into the set of natural numbers. For example, the T-words having the same number n of generators all have the same function y
=
n, and all T-words which are made up of the permutation of the generators of one given T-word have the same values of their functions x, y, and D.Multiple Link Function Values. As to the link function, (56) and (58) (or the definition (47)) show that L does not depend on the number of trailing “d” in the T-word.Moreover, in some rare cases, the same link function value may belong to T-words which differ in the number of their generators, i.e. in their value ofy.Table2 shows the lowest multiple link function values for the three lowest types of multiplicity, double, triple, or quadruple.Table 2
Multiple link function values.
L
T-word
x
y
D
19
u
d
d
d
d
u
d
5
2
23
u
d
u
d
u
d
3
3
-
19
259
u
d
8
u
d
9
2
503
u
d
3
u
d
2
u
d
u
d
7
4
47
u
d
u
d
u
d
u
d
3
u
d
7
5
-
115
4459
u
d
4
u
d
2
u
d
6
u
d
13
4
8111
u
d
u
d
u
d
4
u
d
6
u
d
13
5
7949
u
d
3
u
d
u
d
2
u
d
3
u
d
u
d
11
6
1319
u
d
u
d
u
d
u
d
u
d
5
u
d
u
d
11
7
-
139It appears that the pair (L, y), i.e. the value of the link function and the number of generators, uniquely determines the T-word (compare Section 9, Conjecture 5).Upper and Lower Value of the Link Function for Given
x
and
y. Consider the set Σ
x
y of T-words with fixed x and y. The number of T-words in this set is given by
(59)
z
(
x
,
y
)
:
=
(
x
-
1
)
!
(
y
-
1
)
!
(
x
-
y
)
!
.
We want to determine the lower and the upper bound of link function values for the T-words in Σ
x
y.The lowest value ofL will be obtained for a T-word w
min
⁡ in which the x
-
y “free” d-operations appear at the end (where they do not count). It has the form
(60)
w
min
⁡
=
(
u
d
)
y
-
1
u
d
x
-
y
+
1
.
Using (11), (12), (44), (55), and (58) one finds
(61)
L
min
⁡
=
3
y
-
2
y
.
The set of T-words with x
=
y has already been considered (with regard to its realizations) in example 3 of Section 2.The highest value ofL will be obtained for a T-word w
max
⁡ in which all x
-
y “free” d-operations are included in the first (leftmost) generator. This T-word has the form
(62)
w
max
⁡
=
u
d
x
-
y
+
1
(
u
d
)
y
-
1
.
Note that it is obtained from w
min
⁡ by reversing the order in which the two main constituent T-words are written.With (11), (12), (44), (55), and (58), one finds
(63)
L
max
⁡
=
3
y
-
1
+
2
x
-
y
+
1
(
3
y
-
1
-
2
y
-
1
)
.
Thus, for the T-words w
∈
Σ
x
y, the values of the link function are found in the interval
(64)
3
y
-
2
y
≤
L
≤
3
y
-
1
+
2
x
-
y
+
1
(
3
y
-
1
-
2
y
-
1
)
.
The basic results obtained that far are pictured in Figure 4. For a given T-word, it illustrates the symmetry in the realizations under the 3
m
+
1 and the 3
m
-
1 rule and shows the 2-fold role played by the link function L.Figure 4Can
M
be equal to
M
¯
or can
N
be equal to
N
¯
?In view of (30) and (31) which can be rewritten as M
-
2
x
+
M
¯
-
2
x
=
0 and N
-
3
y
+
N
¯
-
3
y
=
0, one may ask if the special case M
=
M
¯ or N
=
N
¯ exists. The answer is negative as seen from (31), (49), and (51).ForM
=
M
¯, they imply M
=
2
x which contradicts the assumption that M is an odd number.Similarly, in the caseN
=
N
¯, the above mentioned equations imply N
=
3
y which contradicts the fact that 3 cannot divide the end number of any Collatz sequence.Concatenation of T-Words. Here we will briefly resume the issue of concatenating two T-words. How does one find the (
3
m
+
1
)-realizations of the T-word w
=
w
a
w
b in terms of those for w
a and w
b?Consider two T-wordsw
a and w
b which are concatenated to form the T-word w
=
w
a
w
b. The 3 T-words w, w
a, and w
b come with their respective start numbers M, M
a, M
b, and with end numbers N, N
a, and  N
b.The most direct (and perhaps simplest) way to determineM and N would be to apply the re-scale procedure to w. This would be the most convenient way to get a numerical result. However, for the purpose of general investigations, it would be necessary to have general formulae.Clearly, the Collatz sequences belonging to the two T-words can only be joined together if the end number ofw
a equals the start number of w
b. This can be achieved by choosing suitable realizations k
a for w
a and k
b for w
b.We denote the start numbers ofw
a, w
b, and w by M
a
‍
k
a, M
b
‍
k
b, and M
k, and similarly we denote the end numbers by N
a
‍
k
a, N
b
‍
k
b, and N
k.The condition for joining the two T-wordsw
a and w
b is then
(65)
N
a
‍
k
a
=
M
b
‍
k
b
.
Using (23) and (24), (65) can be rewritten as
(66)
2
·
3
y
a
k
a
-
N
a
¯
=
2
·
2
x
b
k
b
-
M
b
¯
.
Rearranging terms, we get theconcatenation condition
(67)
3
y
a
k
a
-
2
x
b
k
b
=
1
2
(
N
a
¯
-
M
b
¯
)
;
k
a
,
k
b
≥
1
.
This is one inhomogeneous linear diophantine equation for the two unknowns k
a and k
b. Since the coefficients 2
x
b and 3
y
a are coprime, it has infinitely many solutions.A particular solution(
k
a
p, k
b
p
) can be obtained by one of the standard methods used for solving this type of diophantine equations. As is well known, it cannot be given in closed form.The general solution, given by the sum of a particular solution and the solution to the homogeneous equation, is(68)
k
a
=
k
a
p
+
2
x
b
k
,
k
b
=
k
b
p
+
3
y
a
k
.
The scale of k has to be fixed in such a way that k
a and k
b take their smallest allowed values for k
=
1. Once k
a and k
b are known, the start and end number of w can be written as a function of those of w
a and w
b, as shown below.In fact, fromM
=
M
a
‍
k
a and N
=
N
b
‍
k
b, one gets
(69)
M
=
M
a
+
2
·
2
x
a
(
k
a
-
1
)
,
N
=
N
b
+
2
·
3
y
b
(
k
b
-
1
)
.
The last two equations show how, under the 3
m
+
1 rule, the start number and the end number of the T-word w
=
w
a
w
b are obtained from those of the T-words w
a and w
b.For a T-word under the3
m
-
1 rule, analogeous results are obtained without further calculation. This simplicity is owed to the symmetry of the key equation (30) under an exchange of the start numbers M and M
¯ and (31) under an exchange of the end numbers N and N
¯, if both equations are taken for k
=
1.Under the(
3
m
-
1
) rule, theconcatenation condition will take the form
(70)
3
y
a
k
¯
a
-
2
x
b
k
¯
b
=
1
2
(
N
a
-
M
b
)
;
k
¯
a
,
k
¯
b
≥
1
.
Here, k
¯
a and k
¯
b mean the representation in which w
a and w
b enter the T-word w
a
w
b.In analogy to (68), the general solution to (70) is written as
(71)
k
¯
a
=
k
¯
a
p
+
2
x
b
k
,
k
¯
b
=
k
¯
b
p
+
3
y
a
k
.
Again, the scale of k has to be fixed in such a way that k
¯
a and k
¯
b take their smallest allowed values for k
=
1.From (69), we obtain, by placing a bar above the concerned quantities,
(72)
M
¯
=
M
¯
a
+
2
·
2
x
a
(
k
¯
a
-
1
)
,
N
¯
=
N
¯
b
+
2
·
3
y
b
(
k
¯
b
-
1
)
.
The 4 representation parameters k
a, k
b, k
¯
a, and k
¯
b have to be integers greater than zero. Moreover, they are not independent of each other. In fact, one shows that for k
=
1, they are related by the conditions
(73)
k
a
+
k
¯
a
=
2
x
b
+
1
,
k
b
+
k
¯
b
=
3
y
a
+
1
.
We finally show another way to prove the important composition formula (56).Write relation (48a) for the T-word w and for the two T-words w
a and w
b, keep in mind that M
=
M
a
‍
k
a, N
a
‍
k
a
=
M
b
‍
k
b, and N
b
‍
k
b
=
N.This yields the three equations(74)
L
a
b
:
=
L
(
w
a
w
b
)
=
2
x
a
+
x
b
N
b
‍
k
b
-
3
y
a
+
y
b
M
a
‍
k
a
,
L
a
:
=
L
(
w
a
)
=
2
x
a
N
a
‍
k
a
-
3
y
a
M
a
‍
k
a
,
L
b
:
=
L
(
w
b
)
=
2
x
b
N
b
‍
k
b
-
3
y
b
M
b
‍
k
b
.
Here we are using a simplified notation which hopefully renders some formulas less cumbersome.Using the last two equations to eliminate the terms2
x
b
N
b
‍
k
b and 3
y
a
M
a
‍
k
a in the first equation, one finds (56).Hopefully the relations of the preceding subsection on concatenation will be useful in a future treatment of the Collatz problem; see Section9, Conjecture 1.


## 4. Some Link Function Algebra

Before continuing, the essentials of the preceding sections will be summarized. These essentials include both the concepts and the generic notation. The notion of T-wordsw was introduced to spell out what happens to a sequence of integers either under the Collatz (3
m
+
1) rule or under the (3
m
-
1) rule. The sequence has start and end numbers which are both odd. The T-words form a semigroup 𝒲 with countably infinite elements and countably infinite generators. On 𝒲 are defined: The three functions x
(
w
), y
(
w
), D
(
w
) containing summary information, and the link function L
(
w
) which contains almost complete information about the T-word.Under the3
m
+
1 rule, a T-word determines, for 1
≤
k
∈
ℕ, a set of odd start numbers M
k and odd end numbers N
k. Under the 3
m
-
1 rule, a T-word determines a set of odd start numbers M
¯
k and odd end numbers N
¯
k. Start numbers are linked to end numbers by L. Also, M
k is linked to M
¯
k and N
k is linked to N
¯
k by L.From the basic equation (56) for the link function, a number of useful and by no means obvious relations can be deduced. The results underline the importance of the functions L and D.First we mention the useful commutator relation(75)
L
a
b
-
L
b
a
=
D
a
L
b
-
D
b
L
a
,
where D
a
:
=
D
(
w
a
) and so forth.Next we want to know the link function of then-fold concatenation of a T-word.Lemma 2.
Letw be a T-word and let w
n denote the n-fold concatenation of w. Then
(76)
L
(
w
n
)
=
D
(
w
n
)
D
(
w
)
L
(
w
)
,
where D
(
w
n
)
=
2
n
x
-
3
n
y.Proof.
Withw
a
=
w
b
=
w, (56) yields
(77)
L
(
w
2
)
=
(
2
x
+
3
y
)
L
(
w
)
=
2
2
x
-
3
2
y
2
x
-
3
y
L
(
w
)
.
This proves the lemma for n
=
2. Supposing now that it holds true for n, then application of (56) to L
(
w
n
+
1
)
=
L
(
w
n
w
) shows that it holds for n
+
1.An immediate consequence of (76) and thus a corollary to Lemma 2 is as follows.Lemma 3.
For anyn
∈
ℕ, the positive rational functions, defined by
(78)
Φ
(
w
)
:
=
L
(
w
)
D
(
w
)
f
o
r
D
>
0
,
(79)
Φ
¯
(
w
)
:
=
L
(
w
)
D
¯
(
w
)
f
o
r
D
<
0
,
satisfy
(80)
Φ
(
w
n
)
=
Φ
(
w
)
o
r
Φ
¯
(
w
n
)
=
Φ
¯
(
w
)
.IfΦ  (Φ
¯) is an integer, M  (
M
¯
) belongs to a cycle. Therefore, Φ  (
Φ
¯
) will be called thecycle function.ForD
>
0, the cycle function Φ will follow the T-word under the 3
m
+
1 rule. For D
<
0, Φ
¯ follows the T-word under the 3
m
-
1 rule. If Φ  (
Φ
¯
) is rational, both numerator and denominator are odd integers and Φ  (
Φ
¯
) will be the rational start number of arational cycle.The cycle function also plays an important role in criteria for the direction (up or down) a sequence takes; see Section6.More about cycles in Section5.There is another way of looking at Lemmas2 and 3.Lemma 4.
Letw be a T-word and let w
′ denote the T-word obtained from w by moving the first generator to the end of w. Then it holds
(81)
L
′
=
1
2
x
1
(
3
L
+
D
)
or, equivalently,
(82)
Φ
′
=
1
2
x
1
(
3
Φ
+
1
)
f
o
r
D
>
0
,
Φ
′
=
1
2
x
1
(
3
Φ
-
1
)
f
o
r
D
<
0
.Proof.
The described cyclic one-step permutation changesw
=
w
a
w
b to w
′
=
w
b
w
a, where w
a
=
u
d
x
1 (with x
a
=
x
1, y
a
=
1, L
a
=
1) and w
b
=
u
d
x
2
⋯
u
d
x
y (with x
b
=
x
-
x
1, y
b
=
y
-
1, L
b). Evaluating w and w
′ by (56) yields L
(
w
)
=
3
y
-
1
+
2
x
1
L
(
w
b
) and L
(
w
′
)
=
3
L
(
w
b
)
+
2
x
-
x
1. Elimination of L
(
w
b
) from these two equations gives (81).Remark.
Despite the denominator in (81) the quantity L
′ is an integer. In fact, that the right hand side of (81) contains a factor 2
x
1 is seen when L is inserted from (47).
Lemma4 means that for D
>
0, a one-step cyclic permutation of the generators of w causes the cycle function Φ (or Φ
¯) to change according to the Collatz (
3
m
+
1
) rule, and for D
<
0, it changes according to the 3
m
-
1 rule.
In order to apply the Collatz rules to rational numbers with odd denominator, one has to adopt the following terminology. Thefraction is calledeven (odd) if thenumerator iseven (odd). Since the denominator D (or D
¯) is odd, the 3
m
+
1 (or 3
m
-
1) rule can be applied to the rational number Φ (or Φ
¯).
Rational cycles under the3
m
+
1 rule have been investigated by Lagarias [9].
Summing up the preceding remarks we note the following.(i)
Every T-word withD
>
0 gives rise to arational cycle whose (rational) start number is Φ (=L
/
D). This rational cycle is generated by the 3
m
+
1 rule.
(ii)
Every T-word withD
<
0, i.e. D
¯
>
0, gives rise to arational cycle whose (rational) start number is Φ
¯ (=L
/
D
¯). This rational cycle is generated by the 3
m
-
1 rule.
Inverse T-Words. In Introduction it has already been mentioned that the semigroup 𝒲 can be made a full group by adding to it the inverse of all elements. Note that the inverse of any T-word is uniquely determined. We denote the inverse of a T-word w by w
-
1. It is defined by w
w
-
1
=
w
-
1
w
=
e. For instance, the inverse of a semigroup generator w
=
u
d
x, corresponding to the operation n
=
(
1
/
2
x
)
(
3
m
+
1
), is w
-
1
=
d
-
x
u
-
1 corresponding to the operation m
=
(
1
/
3
)
(
2
x
n
-
1
).
The relevant functions ofw
-
1 are all obtained from
(83)
x
(
e
)
=
y
(
e
)
=
L
(
e
)
=
D
(
e
)
=
0
and the composition laws (55), (56), and (57). One gets
(84)
x
(
w
-
1
)
=
-
x
(
w
)
,
y
(
w
-
1
)
=
-
y
(
w
)
,
L
(
w
-
1
)
=
-
1
2
x
3
y
L
(
w
)
,
D
(
w
-
1
)
=
-
1
2
x
3
y
D
(
w
)
=
2
-
x
-
3
-
y
.
Now, applying (56) to L
(
w
-
n
w
n
)
=
0, one shows that
(85)
L
(
w
-
n
)
=
-
1
2
n
x
3
n
y
L
(
w
n
)
,
and, similarly,
(86)
D
(
w
-
n
)
=
-
1
2
n
x
3
n
y
D
(
w
n
)
=
2
-
n
x
-
3
-
n
y
.Remark 4.
As an example for the usefulness of these results, an alternate proof of Lemma4 is given. In the notation of Lemma 4, write w
′
=
(
u
d
x
1
)
-
1
w
u
d
x
1 which is equivalent to u
d
x
1
w
′
=
w
u
d
x
1. Evaluating both sides with (56) yields 3
y
+
2
x
1
L
′
=
3
L
+
2
x and thus 2
x
1
L
′
=
3
L
+
D. This gives (81).
Another interesting result is obtained from (85) and (86).Lemma 5.
For any T-wordw and n
∈
ℤ, it holds
(87)
Φ
(
w
n
)
=
Φ
(
w
)
.Proof.
By straightforward calculation using (85) and (86), one finds
(88)
Φ
(
w
-
n
)
=
L
(
w
-
n
)
D
(
w
-
n
)
=
-
L
(
w
n
)
2
n
x
3
n
y
(
2
-
n
x
-
3
-
n
y
)
=
L
(
w
n
)
D
(
w
n
)
=
Φ
(
w
n
)
=
Φ
(
w
)
.


## 5. Cycles

First a remark on the terminology to be used: the cycle conditions have already been given by (49) to (52). Though slightly different for the two cases 3
m
+
1 and 3
m
-
1, they suggest a simple classification which is applicable to both cases.Atrivial cycle (TC) is characterized by L
=
1 and D
=
1 or D
¯
=
1, asimple cycle (SC) by L
>
1 and D
=
1 or D
¯
=
1, and anamazing cycle (AC) by L
>
1 and D
>
1 or D
¯
>
1.Usually, the types SC and AC are callednontrivial cycles. However, a distinction between SC and AC is necessary since the situation is simple as long as the denominator D (or D
¯) is 1.The use of the adjective “amazing” expresses, of course, the author’s personal opinion that there is only one cycle whereD or D
¯ is greater than 1 and is also a common divisor of all the link function values.The present empirical knowledge about cycles is presented in Table3. For the two nontrivial cycles SC and AC, the respective T-words are listed in the order in which they appear under cyclic permutation of their generators, beginning with the lowest value of the start number M
(
=
Φ
).Table 3
Survey of known cycles.
Rule
T-word
L
D
Φ
Type
3
m
+
1
s
d
1
1
1
TC
3
m
-
1
s
1
-
1
1
TC
s
s
d
5
-
1
5
SC
s
d
s
7
-
1
7
SC
s
s
s
s
d
s
s
s
d
d
d
2363
-
139
17
AC
s
s
s
d
s
s
s
d
d
d
s
3475
-
139
25
AC
s
s
d
s
s
s
d
d
d
s
s
5143
-
139
37
AC
s
d
s
s
s
d
d
d
s
s
s
7645
-
139
55
AC
s
s
s
d
d
d
s
s
s
s
d
5699
-
139
41
AC
s
s
d
d
d
s
s
s
s
d
s
8479
-
139
61
AC
s
d
d
d
s
s
s
s
d
s
s
12649
-
139
91
ACPhenomenology of Cycles. As mentioned before, no cycle has been found for the 3
m
+
1 problem, except for the trivial one; see Table 3. According to the web page http://www.ieeta.pt/tos/3x+1.html (home page of Tomás Oliveira e Silva, Departamento de Electrónica, Telecomunicações e Informática, Universidade de Aveiro), this holds for start numbers of up to ~1.07
·
1
0
18.Sincex
=
2 and y
=
1 is the only solution to the (diophantine) equation D
=
1, there is no simple cycle under the 3
m
+
1 rule.In contrast, under the(
3
m
-
1
) rule, there is not only the trivial cycle, but there are also the simple and the amazing cycle. The simple cycle owes its existence to the fact that the condition D
¯
=
3
y
-
2
x
=
1 has not only the solution x
=
1, y
=
1 (giving rise to the trivial cycle), but also x
=
3, y
=
2. That is, the only solution with x
>
1 and y
>
1 had been conjectured by Philippe de Vitry (see, e.g., [8]) and proved around the year 1343 by Gerson (Gersonides) [10]. This result also follows, as a special case, from the theorem of P. Mihǎilescu [11] who proved the conjecture of E. C. Catalan (1844).It is noteworthy that the first order realizations of quite simple T-words are ending in cycles.Under the3
m
+
1 rule, the T-word u
d
d has start and end number 1 and describes the trivial cycle.Under the3
m
-
1 rule, the T-word u
d has start and end number 1 and describes the trivial cycle. In fact, any generator with odd x leads into the TC. The T-word u
d
d has start number 7 and end number 5 and describes the simple cycle. In fact, any generator with even x has end number 5 and thus leads into the SC.The T-wordu
d
u
d
d
d
d has start number 61 and end number 17 and thus leads to the amazing cycle.Some Properties of the Amazing Cycle and what can be learned from them.The T-words making up the amazing cycle are cyclic permutations of the generators inu
d
u
d
u
d
u
d
d
u
d
u
d
u
d
d
d
d, see Table 3.These7 T-words are a small subset of the set of T-words with x
=
11 and y
=
7. The number of elements in this set is determined by (59) which gives z
(
11,7
)
=
210.The 210 T-words are grouped in 30 subsets each of which is formed by 7 cyclic permutations of one T-word. Those of the A cycle form just one of these 30 subsets.Why are the 29 other subsets unsuited for being a cycle?Well, 28 of them do not qualify for the simple reason that one of their link function values is a prime number. Only one subset other than the A subset does not have a prime number among its link function values. But none of the divisors of the 7 link function values (of T-words in this subset) equalsD
¯
=
139.Where do sequences under the
3
m
-
1
rule end? Some empirical findings.For the (3
m
-
1) problem, one would like to know to which of the 3 types of cycles a range of start numbers will evolve. To answer this question, the destination of the lowest 16 million odd start numbers was calculated. The results are shown in Table 4.Table 4
Target cycles for 16 million start numbers under the3
m
-
1 rule. There are 1 million odd start numbers covered by each row.
Start numbers
Ending in target cycle
From
To
T
S
A
1
1999999
326900
324736
348364
2000001
3999999
326884
325061
348055
4000001
5999999
326520
325316
348164
6000001
7999999
326839
324933
348228
8000001
9999999
328911
323103
347986
10000001
11999999
324452
327260
348288
12000001
13999999
331941
320774
347285
14000001
15999999
321108
329481
349411
16000001
17999999
326177
326204
347619
18000001
19999999
330078
320150
349772
20000001
21999999
331659
328492
339849
22000001
23999999
317217
326425
356358
24000001
25999999
331616
328452
339932
26000001
27999999
331690
310810
357500
28000001
29999999
319822
330211
349967
30000001
31999999
322737
329915
347348
T
: trivial cycle;  S: simple cycle;  A: amazing cycle.Table4 shows that the distribution of start numbers over the three types of cycles is almost even at the scale of a million. The deviations from their respective mean values are less than 3% within each of the 16 samples.On the other hand, the deviation of numbers going to the amazing cycle from the two other cycles is remarkable. The numbers in the amazing cycle are consistently about 6.7% higher than those in the trivial cycle and about 7.1% higher than those in the simple cycle.This result is not totally unexpected. Since there are, respectively, 1, 2, and 7 entry numbers for the cycles T, S, and A (the respective number of generators), one would expect some bias towards the amazing cycle. But then it is somewhat surprising that there are slightly less start numbers going to the simple cycle than to the trivial cycle. It would be interesting to know the results for larger sampling of start numbers.However, the results of such statistical analysis are not overly trustworthy. If another range of start numbers is considered, the distribution looks different.The target cycles for another 8 million start numbers were calculated, this time in the range beginning with the number1
0
12
+
1. The results are given in Table 5.Table 5
Target cycles for 8 million start numbers under the3
m
-
1 rule. There are 1 million odd start numbers covered by each row.
Start numbers
Ending in target cycle
From
To
T
S
A
1000000000001
1000001999999
153678
489672
356650
1000002000001
1000003999999
159628
359741
480631
1000004000001
1000005999999
170029
223179
606792
1000006000001
1000007999999
109324
449753
440923
1000008000001
1000009999999
140250
276963
582787
1000010000001
1000011999999
233132
247190
519678
1000012000001
1000013999999
519287
142175
338538
1000014000001
1000015999999
416246
192398
391356
T
: trivial cycle;  S: simple cycle;  A: amazing cycle.Here, the distribution of start numbers over the three types of cycles defies any rational explanation.


## 6. The Direction of a Collatz Sequence. Anomalous T-Words

What does a T-word tell about the direction a Collatz sequence is taking? Increasing, or decreasing, or cyclic? The answer to this question must be related to properties of the functionD
=
2
x
-
3
y. Intuitively, D
>
0 suggests that the down operations are preponderant, while D
<
0 suggests that the up operations prevail. However, we know that the diophantine equation D
=
0 has no solution, so that a cycle cannot be characterized by a property of D alone. Also, a Collatz sequence depends on the rule under which it was generated, the 3
m
+
1 or the 3
m
-
1 rule.Now, for any given T-wordw, we can calculate M, N, M
¯, and N
¯ and find out if the respective sequence goes up or down. However, here we are aiming at general statements.We first consider the Collatz sequence under the3
m
+
1 rule.The point of departure is the basic equation (44) which relates, for the 3
m
+
1 problem, the start and the end number to the link function and the functions x and y. In 2
·
3
y
M
=
2
·
2
x
N
-
2
L, we replace 2
M
=
(
M
+
N
)
+
(
M
-
N
) and 2
N
=
(
M
+
N
)
-
(
M
-
N
) and obtain
(89)
3
y
(
M
+
N
)
+
3
y
(
M
-
N
)
=
2
x
(
M
+
N
)
-
2
x
(
M
-
N
)
-
2
L
.
Slight rearrangement of terms and use of (50) then gives
(90)
(
2
x
+
3
y
)
(
M
-
N
)
=
D
(
M
+
N
)
-
2
L
.
This equation provides a necessary and sufficient condition for the direction a Collatz sequence takes under the 3
m
+
1 rule.Lemma 6.
For any T-word under the3
m
+
1 rule, M
>
N holds true if and only if the arithmetic mean of M and N is greater than the value of the cycle function. In short, M
>
N
⇔
(
1
/
2
)
(
M
+
N
)
>
Φ.Proof.
Use (78) to rewrite (90) in the form
(91)
(
2
x
+
3
y
)
(
M
-
N
)
=
2
D
·
[
1
2
(
M
+
N
)
-
Φ
]
.Another immediate consequence of (90) is the following.Lemma 7.
For any T-word under the3
m
+
1 rule, D
<
0 implies M
<
N, meaning that the sequence goes up. In view of Lemma 6,  D
<
0 also implies that the arithmetic mean of M and N is smaller than the value of the cycle function.Also, (90) says that D
>
0 is necessary for M
>
N, i.e. for the sequence to decrease. Now, numerical calculations have not brought to light one single T-word with D
>
0 and M
<
N. As much as one would like to know if D
>
0 is also a sufficient condition for M
>
N, there is no proof for such a statement (but see also Section 8, Conjecture 4).We now turn to the behavior of a number sequence under the3
m
-
1 rule. The two equations (48a) and (48b) show that all one has to do is to change the sign of L in (90). Then one gets
(92)
(
2
x
+
3
y
)
(
M
¯
-
N
¯
)
=
D
·
(
M
¯
+
N
¯
)
+
2
L
.
This equation provides a necessary and sufficient condition for the direction a number sequence takes under the 3
m
-
1 rule.Lemma 8.
For any T-word under the3
m
-
1 rule, M
¯
>
N
¯ holds true if and only if D
(
M
¯
+
N
¯
)
+
2
L
>
0.
In short,M
¯
>
N
¯
⇔
(
1
/
2
)
(
M
¯
+
N
¯
)
<
Φ
¯.An immediate consequence is the following.Lemma 9.
For any T-word under the3
m
-
1 rule, D
>
0 implies M
¯
>
N
¯, meaning that the sequence goes down.Another simple consequence of (90) is the following.Lemma 10.
For any T-word under the3
m
-
1 rule, D
<
0 is necessary for M
¯
<
N
¯, i.e. for the sequence to go up.Anomalous T-Words. However, though D
<
0 is a necessary condition for M
¯
<
N
¯, it is not sufficient. There exist some rare cases ofanomalous T-words for which D
<
0 and M
¯
>
N
¯, as shown in Table 6.Table 6
The anomalous T-words withx
=
11, y
=
7, (D
-
=
139).
T-word
L
M
-
N
-
M
N
u
d
2
(
u
d
u
d
2
)
3
5069
7
5
4089
4369
u
d
u
d
u
d
3
(
u
d
2
u
d
)
2
5347
9
7
4087
4367
u
d
5
(
u
d
)
6
22009
11
1
4085
4373All three cases in Table6 belong to the set of 210 T-words with x
=
11 and y
=
7. For 200 of them, it holds M
¯
<
N
¯, as expected because of the deficit in x (expressed by D
<
0). Further, for 7 of these T-words, it holds M
¯
=
N
¯, and these make up theamazing cycle; see Section 5 for details. However, for the 3 T-words shown in Table 6, we have M
¯
>
N
¯. The reason for this anomaly is that, for x
=
11 and y
=
7, the quantity D
(
11,7
)
=
-
139 is relatively small as compared to it’s neighbors. These are D
(
10,7
)
=
-
1163, D
(
12,7
)
=
1909, D
(
11,6
)
=
1319, and D
(
11,8
)
=
-
4513.The end numbersN
¯ show that, for the first two of these T-words, the (
3
m
-
1
) sequences end in the simple cycle. The third T-word has the highest possible value of the link function in the set characterized by x
=
11 and y
=
7. Its (
3
m
-
1
) sequence ends in the trivial cycle.Another example for anomalous T-words occurs in the set withx
=
19 and y
=
12. According to (59), there are 31824 T-words in this set. Out of these, 31817 T-words have M
¯
<
N
¯. None of them has M
¯
=
N
¯. There are only 7 anomalous cases for which M
¯
>
N
¯; they are listed in Table 7.Table 7
The anomalous T-words withx
=
19, y
=
12, (D
-
=
7153).
T-word
L
M
-
N
-
M
N
u
d
u
d
2
(
u
d
)
2
(
u
d
2
)
2
(
u
d
)
2
u
d
5
(
u
d
)
3
2228821
165
163
1048411
1062719
u
d
u
d
2
u
d
4
(
u
d
)
5
u
d
2
u
d
u
d
3
u
d
3258853
309
307
1048267
1062575
u
d
u
d
2
(
u
d
)
2
u
d
6
(
u
d
)
5
u
d
2
u
d
4975573
549
547
1048027
1062335
(
u
d
)
2
u
d
3
(
u
d
2
u
d
)
4
u
d
2
2161529
9
5
1048567
1062877
u
d
u
d
3
(
u
d
)
2
u
d
2
(
u
d
)
2
u
d
4
(
u
d
)
3
u
d
2
2419037
45
41
1048531
1062841
u
d
3
u
d
u
d
2
(
u
d
)
2
u
d
4
(
u
d
)
3
u
d
2
(
u
d
)
2
4902451
99
91
1048477
1062791
u
d
2
u
d
u
d
7
(
u
d
)
9
20201911
39
1
1048537
1062881For this set withx
=
19 and y
=
12, it holds D
¯
=
-
D
=
7153.Again, the appearance of these anomalous T-words is due to the relative smallness ofD
¯. They are an indicator for the possibility of a cycle, though there is none. Incidentally, the smallness of D
¯ in the case x
=
19 and y
=
12 is known since more than 2500 years and has proved to be of importance for the theory of harmonics in music. There, the basic acoustic intervals are thefifth which corresponds to a ratio of 3
/
2 for the frequencies of two sounds and theoctave which has a ratio 2
/
1. That 12 fifths amount approximately to 7 octaves was known to Pythagoras. In music, the ratio (
3
/
2
)
12
/
2
7
=
3
12
/
2
19
=
1.01364
… is known as thePythagorean comma. In terms of the quantities used in the present text, the Pythagorean comma is given by the expression 3
y
/
2
x
=
1
+
D
¯
/
2
x. For the set of T-words with x
=
11 and y
=
7 whose anomalous elements are depicted in Table 6, one finds for the corresponding “comma” the larger value 1
+
D
¯
/
2
x
=
1.0678
….Presumably there are more anomalous T-words for higher values ofx and y. They could possibly be found in the T-word classes with (
x
,
y
)
=
(
84,53
) (Jing Fang ≈
45 BC, N. Mercator ≈
1650 AD, W.A. Holder ≈
1690 AD), and (
x
,
y
)
=
(
569,359
) (M. Trümper 2011 AD). Holder’s comma is 3
53
/
2
84
=
1.002090
…, while Trümper’s comma is 3
359
/
2
569
=
1.001066
…. The post-Pythagorean cases have not attracted the attention of musicians for the simple reason that the corresponding frequencies are far outside the audible range of sounds.Note that theanomalies occur only in T-words under the 3
m
-
1 rule. They have not been seen in T-words under the 3
m
+
1 rule.Finally we note the equations(93)
M
-
N
+
M
¯
-
N
¯
=
2
D
,
(94)
M
+
N
+
M
¯
+
N
¯
=
2
(
2
x
+
3
y
)
.
They follow immediately from the two relations M
+
M
¯
=
2
·
2
x and N
+
N
¯
=
2
·
3
y.Equations (93) and (94) pose limits on the amount of increase (or decrease) of a 3
m
+
1 sequence and the corresponding 3
m
-
1 sequence. Equation (94) establishes a relation between the arithmetic means of the start and end numbers under both rules 3
m
+
1 and 3
m
-
1. For illustration, see the data in Tables 6 and 7.


## 7. The Discriminant Function

For the Collatz conjecture to be true, nontrivial cycles must not exist. Under the3
m
-
1 rule, they do exist, though only those having relatively small start numbers (up to 91) are known. In both cases, 3
m
+
1 and 3
m
-
1, the non-existence of cycles with higher start numbers remains to be shown. The question hinges on the cycle conditions which are, respectively, D
∣
L and D
¯
∣
L; see (49) to (52).The present section aims at approaching an understanding of the subtle differences between the3
m
+
1 and the 3
m
-
1 problem. Why are there nontrivial cycles in the 3
m
-
1 problem while they are absent in the 3
m
+
1 problem?There are good reasons to conjecture that no other than the known cycles exist. Generally, the bigger the start number, the smaller the chance that the cycle condition can be satisfied. For the3
m
+
1 case, the absence of nontrivial cycles is confirmed by numerical calculations for start numbers up to the order 1
0
18.On the other hand, for big start numbers, the distinction between the3
m
+
1 and 3
m
-
1 rules becomes more and more unimportant. In the first step of a calculation done according to these rules, i.e. after the operation u
d applied to the same start number, the difference in the resulting numbers is just one! And this for a number which may have “zillions” of digits.So it appears reasonable to have a closer look at the discriminant functionsD and D
¯ and, in particular, at their smallest values. The diophantine functions D
=
2
x
-
3
y and D
¯
=
3
y
-
2
x have already appeared in Sections 3, 4, 5, and 6. We are interested only in their positive values under the conditions 1
≤
y
≤
x.Though the investigation in the present section is motivated by the Collatz problem, it is devoted mainly to the discriminant function.We conjecture that the functionsD
(
x
,
y
) and D
¯
(
x
,
y
) define two sets of natural numbers which only intersect in the single values 1 and 5. The value D
=
1 is taken for (
x
,
y
)
=
(
2,1
), while the value D
=
5 is taken for (
x
,
y
)
=
(
5,3
). The value D
¯
=
1 is taken for (
x
,
y
)
=
(
1,1
) and for (
x
,
y
)
=
(
3,2
), while the value D
¯
=
5 is taken for (
x
,
y
)
=
(
2,2
).Figure5 shows the 100 smallest values of D and D
¯.Figure 5Note that the numerotation on the vertical axis gives the order of magnitude ofD and D
¯ (and not log
⁡
(
D
) and log
⁡
(
D
¯
)).Of particular interest is the border region between the areasD
>
0 and D
<
0. A heuristic, probabilistic argument tells us why. The smaller D (or D
¯), the higher the chance that it divides L. This is true since the probability P
(
i
) of an integer i to divide an arbitrary natural number is P
(
i
)
=
1
/
i. Thus the chance for the existence of a cycle decreases with increasing value of D (or D
¯).And, thoughP
(
i
)
=
1
/
i describes a decrease which is slow, both D and D
¯ increase rapidly, as seen in Figure 5 where the 100 smallest values of D and D
¯ are pictured on a logarithmic scale.Figure6 shows the x
y-plane with the areas D
>
0 and D
<
0, and thecritical line which separates them. The points (
x
,
y
) which are the closest to the critical line and are marking the border of the areas D
>
0 and D
<
0 will be referred to as theborder points. At these points, the functions D and D
¯ take their smallest (positive) values. The border points of the area D
>
0 have the coordinates x and
(95)
y
=
Int
(
x
·
log
⁡
2
log
⁡
3
)
.
The border points (
x
¯
,
y
¯
) of the region D
¯
>
0 are related to the border points (
x
,
y
) of the region D
>
0 by x
¯
=
x, y
¯
=
y
+
1.Figure 6In Figure7, we have plotted the distance of the border points from the critical line against x. This distance is denoted δ
(
x
,
y
). For border points in the area D
>
0, the distance coordinates are counted negative. It is remarkable that in this representation, the border points of both areas D
>
0 and D
<
0 form one single lattice. A simple geometric argument shows that the distance is given by
(96)
δ
(
x
,
y
)
=
1
ρ
·
(
y
·
log
⁡
3
-
x
·
log
⁡
2
)
=
1
ρ
·
log
⁡
(
3
y
2
x
)
,
where
(97)
ρ
:
=
(
log
⁡
2
)
2
+
(
log
⁡
3
)
2
.
In matrix notation, the transformation (
x
,
y
)
→
(
x
,
δ
) is
(98)
(
x
δ
)
=
(
1
0
-
1
ρ
log
⁡
2
1
ρ
log
⁡
3
)
(
x
y
)
.
The border points of the region D
¯
>
0 are related to those of the region D
>
0 by the displacement (
x
,
δ
)
→
(
x
,
δ
+
λ
) where
(99)
λ
:
=
1
ρ
·
log
⁡
3
=
0.84573
…
.
At the same time, the quantity λ is also the determinant of the above transformation matrix.Figure 7We remark in passing that the radicand of the denominator in the last formula can also be written as(
log
⁡
2
)
2
+
(
log
⁡
3
)
2
=
log
⁡
(
2
log
⁡
2
·
3
log
⁡
3
).The square root of this expression equals0,56414869
….The two horizontal linesy
=
±
λ mark the limits within which the border points are found. Of course, no point in the two infinitely long lattice strips lies on the critical line which separates them, neither on one of the lines y
=
±
λ.A typical lattice cell is spanned by the vectors(100)
a
→
=
(
1
1
ρ
log
⁡
3
2
)
,
b
→
=
(
2
-
1
ρ
log
⁡
4
3
)
.
Curiously, the area of such an elementary cell is
(101)
|
a
→
∧
b
→
|
=
λ
.
The points which belong to the known cycles are encircled. From the left to the right, their x-values are 1 (trivial cycle 3
m
-
1), 2 (trivial cycle 3
m
+
1), 3 (simple cycle 3
m
-
1), 11 (amazing cycle 3
m
-
1).Another point, close to the critical line and marked by a square in Figure7, has T-word parameters (
x
,
y
)
=
(
19,12
). Here it is mentioned because of its importance in the theory of musical harmony; see also the remarks in Section 6.


## 8. The Length of a Sequence, Cases3
m
+
1 and 3
m
-
1

Consider a T-word and the sequence determined by it. Let us defineΛ, thelength of the sequence, simply as the length of the T-word, i.e. the total of operations d and u. The length is thus
(102)
Λ
=
x
+
y
.
Since all tested start numbers lead to one of the cycles which have been discussed before, we will be interested in the length of sequences leading from a start number to the eventual cycle entry number.Experience shows that, generally, higher start numbers will lead to longer Collatz sequences. This holds true also for series under the3
m
-
1 rule.However, this length may vary widely, even for start numbers which are close to each other as shown by an example in Table8.Table 8
Length of sequence for 3 neighboring start numbers.
Start number
Length
Even
Odd
End number
1,431,655,763
452
289
163
1
1,431,655,765
33
32
1
1
1,431,655,767
191
129
62
1Obviously, the reason for such large variation in length lies in the fact that the start number in the second line of the table is of an exceptional nature; namely,M
=
(
1
/
3
)
(
2
32
-
1
).On the other hand, in the realm of higher start numbers, the lengths of series are surprisingly stable over large ranges of start numbers. For instance, all series belonging to the 1666 start numbers which are in the set{
M
=
1
0
170
+
5
+
6
k
,
0
≤
k
≤
1665
} have the same length 4065, each one with 2711 even integers and 1354 odd integers! This means that, for the T-words of all these sequences, one has x
=
2711 and y
=
1354. Note that the ratio r
:
=
x
/
y is r
≃
2.0022.In fact, tests with large sets of randomly chosen start numbers show that, for the resulting sequences, the average value ofr is close to 2.This fact leads us to the concept of anaverage Collatz sequence as one for which
(103)
ρ
:
=
r
-
2
satisfies the condition
(104)
|
ρ
|
≪
1
.
This quantity, defined for any T-word on the interval -
1
≤
ρ
<
∞, is related to the randomization of integers which are found in the corresponding sequence. Vanishing ρ means perfect randomization. Negative values of ρ mean a deficit of d-operations, while positive ρ mean an excess of d-operations.For instance, the 1666 start numbers in the example above give rise to well-randomized sequences withρ
≃
0.0022, showing a slight excess of d-operations.In contrast, the celebrated series with start number 27 hasx
=
70 and y
=
41 with ρ
≃
-
0.29268, being non-randomized with a large deficit in d-operations.Let us look at the Collatz rules as a mechanism which converts odd integers to even integers (byu-operations) and then reconverts the even ones to odd integers (by successive d-operations). This brings us to the question of the statistical behavior of even numbers under subsequent divisions by 2. The following analysis will justify that it is reasonable to define an average sequence by the property x
/
y
≃
2 and thus confirm the condition (93).The Decay of Even Numbers under Successive Divisions by 2. Consider a largeparent set ℳ of n random even integers m, all different from each other. Count the number of even and odd integers in thedescendent set which is obtained by successive divisions by 2. Since each decay chain ends in an odd integer, there are n odd numbers in thedescendent set.The number of even integers in the decay is derived by the following argument. Define theqthdescendant set
(105)
ℳ
q
:
=
{
m
q
=
m
2
q
,
m
q
∈
ℕ
,
m
∈
ℳ
}
.
To each integer in this set we assign the probability 1
/
2 to be even one. Thus, the number of integers in ℳ
q will be about n
/
2
q.The total number of even integers among the descendants ofℳ will then be
(106)
(
1
2
+
1
2
2
+
1
2
3
+
⋯
+
1
2
q
)
·
n
=
(
1
-
1
2
q
)
·
n
.
Together with the n integers in ℳ, the total number of even integers will be n
e
=
(
2
-
1
/
2
q
)
·
n and, since each integer of ℳ will give rise to exactly one odd integer, the total number of odd integers generated will be n
o
=
n.What can be said about the parameterq which limits the number of descendant generations? First of all, it depends on the magnitude of the even integers which are in the parent set ℳ. The higher these integers in ℳ are, the higher will be q. In fact, the number of factors 2 in an integer m
∈
ℳ can be at most q
=
INT
(
log
⁡
2
m
). This is the biggest integer which is equal to or smaller than log
⁡
2
m.The integerq gives the maximum of divisors 2 which even integers near m may have. Of course, m being a start number has no divisor 2 at all. Therefore, q may be considered as thepotential for decay.For instance,m
=
1
0
170
+
5 gives q
=
564.The total number of even integers in a Collatz series is the sum of the number of even integers in the parent set and those in the set of descendants; thus,(107)
x
=
y
+
(
1
-
1
2
q
)
·
y
=
(
2
-
1
2
q
)
·
y
.
This means that, in such a sequence y, odd integers give rise to about 2
y even integers, composed of exactly y even integers generated by the “up” operation and then about y even integers generated by the “down” operations(s).We are now in a position to derive approximation formulas for average sequences in both cases3
m
+
1 and 3
m
-
1.The starting points are the two equations (48a) and (48b) which will be combined with (103). It will be sufficient to treat only the case of rule 3
m
+
1. The equations for the case 3
m
-
1 will then be simply obtained by replacing L with -
L.To begin with, the first of (48a) and (48b) will be rewritten as
(108)
2
x
·
N
=
3
y
·
M
+
L
and (92) will be rewritten as
(109)
x
=
2
y
+
ρ
y
.
The latter equation will now be used to eliminate x in the previous one. We get
(110)
4
y
·
2
ρ
y
·
N
=
3
y
·
M
+
L
and, after division by 3
y, we have
(111)
(
4
3
)
y
·
2
ρ
y
·
N
=
(
1
+
L
3
y
M
)
·
M
.
Now, taking the logarithm, we can rewrite this equation as
(112)
y
=
1
log
⁡
(
4
/
3
)
·
{
log
⁡
(
M
)
-
log
⁡
(
2
ρ
y
N
)
+
log
⁡
(
1
+
L
3
y
M
)
}
.
Finally, with (102) and (103), we have Λ
=
(
3
+
ρ
)
y and then
(113)
Λ
=
3
+
ρ
log
⁡
(
4
/
3
)
·
{
log
⁡
(
M
)
-
log
⁡
(
2
ρ
y
N
)
+
log
⁡
(
1
+
L
3
y
M
)
}
.
The analogous expression for the length of the sequence under the 3
m
-
1 rule is obtained by making the replacements L
→
-
L, M
→
M
¯, N
→
N
¯.We get(114)
Λ
¯
=
3
+
ρ
log
⁡
(
4
/
3
)
·
{
log
⁡
(
M
¯
)
-
log
⁡
(
2
ρ
y
N
¯
)
+
log
⁡
(
1
-
L
3
y
M
¯
)
}
.
Equations (113) and (114) are identities. For a given T-word, both expressions yield the same value for the length of the sequence; namely, Λ
=
Λ
¯
=
x
+
y.From here, we turn to proper Collatz series, i.e. those under the3
m
+
1 rule which end in the trivial cycle (as they do for all known start numbers).SettingN
=
1 and expanding in powers of ρ, we get
(115)
Λ
=
3
log
⁡
(
4
/
3
)
·
{
log
⁡
(
M
)
+
log
⁡
(
1
+
L
3
y
M
)
+
1
3
[
log
⁡
(
M
)
+
log
⁡
(
1
+
L
3
y
M
)
-
3
y
log
⁡
(
2
)
]
·
ρ
-
y
3
log
⁡
(
2
)
·
ρ
2
(
1
+
L
3
y
M
)
}
.
Under the 3
m
-
1 rule, the analog of (115) can be obtained for the case where the sequence goes to the trivial cycle. As before, this is done by the replacements L
→
-
L, M
→
M
¯, N
→
N
¯. One gets
(116)
Λ
¯
=
3
log
⁡
(
4
/
3
)
·
{
log
⁡
(
M
¯
)
+
log
⁡
(
1
-
L
3
y
M
¯
)
+
1
3
[
log
⁡
(
M
¯
)
+
log
⁡
(
1
-
L
3
y
M
¯
)
-
3
y
log
⁡
(
2
)
]
·
ρ
-
y
3
log
⁡
(
2
)
·
ρ
2
(
1
-
L
3
y
M
¯
)
}
.
The negative sign in two of the terms indicates a tendency for smaller values of the length Λ
¯. However, one has to keep in mind the possibility that M
¯
>
M.Equations (115) and (116) give respectively the exact length of a 3
m
+
1 and a 3
m
-
1 series which reaches the end number 1.Crandall [12], by what he himself termed “an heuristic argument”, obtained for the 3
m
+
1 case the expression
(117)
height
=
1
log
⁡
(
4
/
3
)
·
log
⁡
(
M
)
.
He used the term “height” to designate the number of “up” operations, and this is our quantity y (which, in the case ρ
=
0, equals (
1
/
3
)
Λ).As seen from (115) his argument makes implicit use of the assumptions ρ
=
0 and log
⁡
(
1
+
L
/
3
y
M
)
≪
log
⁡
(
M
).As to the relative weight of the two terms remaining in (115) after setting ρ
=
0, it appears that Crandall’s implicit assumption log
⁡
(
1
+
L
/
3
y
M
)
≪
log
⁡
(
M
) is justified.This assumption is supported by numerical calculations which I have made for the special caseρ
=
0. In fact, for all of the 1236 specimen of cases ρ
=
0 which were found among a total of 50000 series, the term log
⁡
(
M
) contributes more than 98
% to the length while the term log
⁡
(
1
+
L
/
3
y
M
) amounts to less than 2%.The50000 start numbers for these numerical calculations were taken from within the interval [
100001
,
309999
]. It may be interesting to note that no one of the 1236 start numbers leading to series with ρ
=
0 was found in the interval [
300001
,
309999
].It would be of principal interest to find a general, non-numerical argument for the relationlog
⁡
(
1
+
L
/
3
y
M
)
≪
log
⁡
(
M
).In another approach to test the validity of Crandall’s approximation, I have calculated the Collatz series for 15 quite large start numbers. All start numbers are composed as, for example, shown in the first line of data;M
=
1234567890
·
(
1
0
0
+
1
0
10
+
1
0
20
+
⋯
+
1
0
80
+
1
0
90
)
+
3. Using a fast microprocessor, the full Collatz series have been calculated, with execution times ranging from 29 seconds to 9 h 26
′.Items Shown in Table9
First column: logarithm of start numberM.
Second column:x, the number of d-operations.
Third column:y, the number of u-operations.
Fourth column: The parameterρ
(
:
=
x
/
y
-
2
).
Fifth column: true lengthΛ
=
x
+
y of the series.
Sixth column: Rounded approximate values of length, calculated from (115) where only the first term in the curly bracket {
…
} is retained.
Last column: deviation [%] of the approximate length from the true length.Table 9
True and approximate length of(
3
m
+
1
)-series.
log
⁡
(
M
)
x
y
ρ
Λ
Λ
App.
Dev.
1000.0915
16045
8027
−0.001121
24072
24014
−0.24
2000.0915
32744
16467
−0.011538
49211
48026
−2.41
3000.0915
47904
23936
0.001337
71840
72037
0.27
4000.0915
64920
32576
−0.007122
97496
96049
−1.48
5000.0915
79595
39739
0.002944
119334
120061
0.61
6000.0915
97665
49044
−0.008625
146709
144073
−1.80
7000.0915
111332
55571
0.003419
166903
168085
0.71
8000.0915
128275
64165
−0.000857
192440
192096
−0.18
9000.0915
148675
74940
−0.016079
223615
216108
−3.36
10000.0915
162678
81679
−0.008325
244357
240120
−1.73
11000.0915
178873
89801
−0.008118
268674
264132
−1.69
12000.0915
190814
95239
0.003528
286053
288143
0.73
13000.0915
211049
105910
−0.007280
316959
312155
−1.52
14000.0915
227160
113979
−0.007001
341139
336167
−1.46
15000.0915
239987
119976
0.000292
359963
360179
0.06


## 9. The Collatz Conjecture as a Problem in Number Theory

Eleven years into the twenty-first century, the Collatz problem has not yet found its proper place in the wide field of mathematics. In2006, the scientific reviewers of the arXiv organization judged that it belongs to the subclass ofgeneral mathematics. Wikipedia says that it belongs toelementary number theory. Apparently, the termelementary does not refer to the degree of difficulty of the problem for the Goldberg conjecture is listed in the same category.Without doubt, the Collatz conjecture belongs to number theory. Not only because it deals exclusively with natural numbers, but also because it hinges on the divisibility of certain bilinear exponential forms, such as the link functionL.Conjecture 1 (Collatz conjecture;3
m
+
1 rule).
For every T-wordw with end number N
>
1, there exists another T-word w
′ such that w
′′
:
=
w
w
′ has end number N
′′
<
N.Conjecture 2 (absence of nontrivial cycles under the3
m
+
1 rule).
Letx
1, x
2, …
x
y, y be y
+
1 natural numbers, all
≥
1, let x
:
=
x
1
+
⋯
+
x
y, and let D
:
=
2
x
-
3
y
>
0. Then the quantity D divides
(118)
L
=
3
y
-
1
+
2
x
1
·
3
y
-
2
+
2
x
1
+
x
2
·
3
y
-
3
+
⋯
+
2
x
1
+
x
2
+
⋯
x
y
-
2
·
3
+
2
x
1
+
x
2
+
⋯
x
y
-
1
only in the case x
=
2 and y
=
1.Conjecture 3 (absence of others than the trivial, simple, and amazing cycle under the3
m
-
1 rule).
Letx
1
,
x
2
,
…
x
y, y be y
+
1 natural numbers, all ≥1, let x
:
=
x
1
+
⋯
+
x
y, and let D
¯
:
=
3
y
-
2
x
>
0. Then the quantity D
¯ divides
(119)
L
=
3
y
-
1
+
2
x
1
·
3
y
-
2
+
2
x
1
+
x
2
·
3
y
-
3
+
⋯
+
2
x
1
+
x
2
+
⋯
x
y
-
2
·
3
+
2
x
1
+
x
2
+
⋯
x
y
-
1
only in the cases
(120)
x
=
1
,
y
=
1
,
(
x
1
,
x
2
)
=
(
1,2
)
,
y
=
2
,
(
x
1
,
x
2
)
=
(
2,1
)
,
y
=
2
,
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
1,1
,
1,2
,
1,1
,
4
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
1,1
,
2,1
,
1,4
,
1
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
1,2
,
1,1
,
4,1
,
1
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
2,1
,
1,4
,
1,1
,
1
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
1,1
,
4,1
,
1,1
,
2
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
1,4
,
1,1
,
1,2
,
1
)
,
y
=
7
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
)
=
(
4,1
,
1,1
,
2,1
,
1
)
,
y
=
7
.Conjecture 4 (equivalence ofD
>
0 and M
>
N).
For any T-word under the3
m
+
1 rule, M
>
N holds true if and only if D
>
0.Conjecture 5 (reconstitution).
LetA
∈
ℕ with 2
∤
A and 3
∤
A. The equation L
(
x
1
,
x
2
,
…
x
y
-
1
,
y
)
=
A has either(a)
no solution (as, e.g., forA
=
13), or
(b)
one solution (as, e.g., forA
=
5), or
(c)
a finite number of solutions (as, e.g., orA
=
19), which all differ by the value of y.



---

*Source: 756917-2014-04-30.xml*