[Math] Larger cycle than 4, 2, 1 in Collatz iteration

collatz conjecturent.number-theoryreference-request

(Here I discuss the Collatz problem only for positive integers.)
It is possible, by computation, to find all cycles in the Collatz iteration of a fixed length.
It is clear that an increase must be followed by a decrease (for if $n$ is odd, then $3n+1$ is even) and a decrease can be followed by either an increase or decrease (for if $n$ is even, $\frac{n}{2}$ may be odd or even).
Using this, it is easy, for example, to show $4, 2, 1$ is the only cycle of length $3$:
Over the course of a cycle, we must have both increases and decreases. Position an increase at the beginning of the cycle. Then the changes of the cycle must be $IDD$ (where $I$ stands for increase and $D$ stands for decrease), for there is no other way to include an increase and avoid two consecutive increases. Then the cycle consists of $a, 3a+1, \frac{3a+1}{2}$, so that $a = \frac{3a+1}{4}$ and $a = 1$, leading to the familiar $1, 4, 2 = 4, 2, 1$ cycle.

For length $4$, there are two possibilities for a pattern of increase and decrease along a cycle which start with an increase: $IDID$ and $IDDD$.
The $IDID$ possibility leads to $a = \frac{9a+5}{4}$ so $a = -1$.
The $IDDD$ possibility leads to $a = \frac{3a+1}{8}$ so $a = \frac{1}{5}$. Neither of these values of $a$ is a positive integer, so there are no cycles of length $4$.

Likewise, for length $5$, there are only $3$ possibilities: $IDDDD$, $IDIDD$, and $IDDID$. Since last two are equivalent, this leads to $IDDDD$ and $IDIDD$.
$IDDDD$ leads to $a = \frac{3a+1}{16}$ so $a = \frac{1}{13}$.
$IDIDD$ leads to $a = \frac{9a+5}{8}$ so $a = -5$. So there are no cycles of length $5$.

There is more to be said for this way of considering cycles in the Collatz iteration. If a sequence of increases and decreases leads to the equation $a = Ta + U$, then $T$ is positive and $T \neq 1$, since $T = \frac{3^{m}}{2^{n}}$ for some positive integers $m, n$. The positivity of $T$ and the fact that $T \neq 1$ ensure that the solution of $a = Ta + U$ also solves (and therefore is the only solution to) $a = T(Ta + U) + U$ (or the equation for fixed points of higher-multiplicity iterates of the function $f(a) = Ta + U$), so that only cycles that form primitive circular words need to be considered (and $IDID$ was unnecessary, given how it reduces to $ID$). With this noted, it becomes very easy to handle cycles of length $6$:

The number of increases in a cycle is $1$, $2$, or $3$, since no two of them can be consecutive (and since there must be at least one increase). $3$ increases in a cycle can only be realized by $IDIDID$, which is not a primitive circular word. $2$ increases in a cycle can be realized by $IDIDDD$, $IDDIDD$, or $IDDDID$. $IDIDDD$ and $IDDDID$ are equivalent, while $IDDIDD$ is not a primitive circular word. So the only cases to consider are $IDDDDD$ and $IDIDDD$.
$IDDDDD$ leads to $a = \frac{3a+1}{32}$ so $a = \frac{1}{29}$.
$IDIDDD$ leads to $a = \frac{9a+5}{16}$ so $a = \frac{5}{7}$.
So there are no cycles of length $6$.

This is natural and simple enough that someone must have considered it before. Who has, and in what paper(s)? Also, has this been used to settle the question of whether or not there is a cycle in the positive integers larger (both in length, and in member-wise comparison) than the $4, 2, 1$ cycle?

Best Answer

The cycle problem is simple enough for an amateurish approach. It is easy to find out, that a cycle must be longer than some minimal length. However, the only proof so far, which shows, that a cycle cannot occur even if arbitrary length is assumed, was done by means of transcendental number theory and the concept of rational approximation. Also, this could only be used for a special simple type of cycles. R. Steiner succeeded around [1977][3] with the first proof of this type (disproving the "1-cycle"); J.Simons 1996 and later in cooperation with B.de Weger (since 2002)could extend this concept up to "68-cycles", a 68-fold concatenation of arbitrary long partial sequences of the same type. After that the currently best known bounds for that approximation are too weak, and Simons/deWeger assume, that finally some completely different method must be found to proceed fundamentally here.


[update] Perhaps I should make the relation of your question to the method of Steiner/Simons (and my own) clearer here.

The mentioned Steiner and Simons/deWeger theorems concern cycles of the general form: (ID)(ID)(ID)...(ID) DD...DD with u occurences of ID and d occurences of D, so u upwards steps followed by d downwards steps. To make this simpler we would denote the Steiner description with one letter, say U, for the combination ID.
So the general form were U...U D...D which is called "1-cycle" if this describes a cycle.
Then first, Steiner showed 1977 there is no cycle how many (u and d) U's (or (ID)'s in your notation) and D's in that specific arrangement occur.
Now let's denote one of that U...U D...D-constructions by $C^{u,d}$ where u again denotes the number of U and d the number of D. John Simons showed then 2004 that no cycle of the twofold concatenated form U...U D...D U...U D...D = $C^{u_1,d_1}C^{u_2,d_2}$ exists (besides of the "trivial" cycle).
The relation of your notation to the 3-, 4-, and up to the 68-cycle is then the obvious, I think.

If you look at my own article you'll find, that I reduce, for instance I DDD I DD, similarly to $b=T(a;3,2)$ - just counting the number of D's after one I, and introducing a and b as formal start- and endvalues of the full sequence of transformations, and analyze this in terms of powers of 3 and 2 as exponential diophantine expressions. This leads to very interesting (and more general) properties of the relation of powers of 2 with powers of 3.


Appendix to avoid a frequent misunderstanding

What Steiner and Simons did call a "1-cycle" is not identical to the "1-step-cycle", but is of arbitrary length/steps, however with a nice analytically exploitable structure.

A disproof for the "1-step-cycle" is indeed as simple as Robert Frost in his comment mentions: Assume "1-step" as $b=(3a+1)/2^A$ and this being a cycle we must have $b=a$ and thus $a=(3a+1)/2^A$. This can be reformulated $$ a = {3a+1\over 2^A} \to a2^A = 3a+1 \to a = {1\over 2^A-3} $$ and indeed, there is only one solution for positive integer numbers $a$ possible, namely $A=2,a=1$ - giving the trivial cycle.

Moreover, this can be extended easily to disprove manually a small set of "$N$-step-cycles":

Let $N=2$ and $b=(3a+1)/2^A$, $c=(3b+1)/2^B$ and to make it a cycle, $c=a$. Then we can make the product $$ a \cdot b = \left( {3a+ 1\over 2^A}\right) \left( {3b+ 1\over 2^B}\right)\\ \to 2^{A+B} = \left( 3+{1\over a}\right) \left( 3+{1 \over b}\right) $$ Of course, the rhs can only be between $9$ and $16$, where if it is $16$ we must have $A+B=4$ and $a=b=1$ thus having the trivial cycle only.

Let $N=3$ and $b=(3a+1)/2^A$, $c=(3b+1)/2^B$ , $d=(3c+1)/2^C$ and to make it a cycle, $d=a$. Then we can make the product $$ \to 2^{A+B+C} = \left( 3+{1\over a}\right) \left( 3+{1 \over b}\right)\left( 3+{1 \over c}\right) $$ and now the rhs can only be between $27$ and $64$. Being equal to $64$ requires $a=b=c=1$ being the trivial cycle, which we are not interested in. Another solution to equal a perfect power of $2$ , namely $2^{A+B+C}$ it must equal $32$. But now, if $a,b,c \ne 1$ and all different and none divisible by $3$ we have at most $$ \to 2^{A+B+C} = \left( 3+{1\over 5}\right) \left( 3+{1 \over 7}\right)\left( 3+{1 \over 11}\right) $$ and we see, that this is smaller than the required $32$. But increasing $a,b,c$ doesn't help since then the rhs decreases even more, so no "3-step-cycle" is possible. (see some more examples in my small online-treatize)

In the same way a lot of attempted "N-step-cycles" with fixed, small and large $N$ can be disproved. However, the Steiner's and Simon's $1-cycle$ concept includes all arbitrary large $N$ - and to have a disproof in such a generality we need a more general method of disproof (and also the specific structure of the problem when we have a single "up--down" pattern in the $a_1,a_2,a_3,...,a_N$ elements of an assumed cycle only).


[3]: http://???/ Steiner, R.P.; "A theorem on the syracuse problem", Proceedings of the 7th Manitoba Conference on Numerical Mathematics ,pages 553–559, 1977.