8
$\begingroup$

(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?

$\endgroup$
  • 1
    $\begingroup$ Some of the earliest Internet pages on the Collatz problem refer to work done on cycle lengths. One result had a cycle length over the positive integers as being either the known cycle or else having length be large (more than 100000). A net search/should help you find it. Gerhard "Email Me About System Design" Paseman, 2011.06.24 $\endgroup$ – Gerhard Paseman Jun 24 '11 at 17:12
  • $\begingroup$ See deweger.xs4all.nl/papers/… for up to date results on Collatz cycles. $\endgroup$ – Emil Jeřábek 3.0 Jun 24 '11 at 17:15
  • 2
    $\begingroup$ What Gerhard means is probably jstor.org/stable/2044308 . $\endgroup$ – Emil Jeřábek 3.0 Jun 24 '11 at 17:19
  • $\begingroup$ Emil, I don't actually recall the paper containing the result, and I have a feeling that I am thinking of a different one. Your citation though is a good one, and I am happy to let that be the example until my memory improves. Thanks for the reference. Gerhard "Thanks For The Memory Substitutes" Paseman, 2011.06.24 $\endgroup$ – Gerhard Paseman Jun 24 '11 at 17:49
  • $\begingroup$ You may want to check arxiv.org/abs/math.NT/0309224 and arxiv.org/abs/math.NT/0608208 for an extensive overview of literature on the Collatz conjecture. One of those lists includes the reference to Simons, De Weger mentioned in the answer below, and there may be other papers relevant to your question listed there as well. $\endgroup$ – TMM Jun 25 '11 at 13:59
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Strange that somebody bothered to prove the trivial cycle is the only 1-cycle by such complex means when it's easily shown with basic algebra that $x=1$ is the only positive integer solution to $2^mx=3x+1$ $\endgroup$ – samerivertwice Jan 10 '18 at 19:04
  • 1
    $\begingroup$ @Robert : "1-cycle" does not mean "only one step" (in the syracuse notation) but "arbitrarily many steps going up only and then arbitrarily many steps going down only arriving at the initial value again". This is often misunderstood (my own first take with this included...) and so I think it is somehow a misnomer. There should a better name be invented sometime... The "1-step-loop" which you describe in your comment is indeed easily disproved (and even the 2-step and 3-step cycle and a couple of such finite-step cycles) see my treatize go.helms-net.de/math/collatz/Collatz061102.pdf $\endgroup$ – Gottfried Helms Jan 10 '18 at 20:04
  • 1
    $\begingroup$ Ah okay; a cycle having only one division by $4$ or greater. A non-unitary down-step. Containing no more than one integer satisfying $\lvert\cdot\rvert_2\in\{\frac{1}{4},\frac{1}{8}\}$ $\endgroup$ – samerivertwice Jan 11 '18 at 10:32
3
$\begingroup$

Edit: Thanks to all for your comments. Because of the phrasing of the review of Eliahou's paper on MathSciNet, I was confused between the $3n+1$ and the $3n-1$ problems. But Eliahou's paper is indeed about the $3n+1$, hence is relevant to the OP. I edited my answer so that it should now make sense.

It is known that any non-trivial cycle must start after $2^{40}$, and have length $17 087 915b + kc$, where $b,c\in\mathbb{N}$ and $k\in\{301 994 , 85 137 581\}$: see Shalom Eliahou, {\it The $3x + 1$ problem: new lower bounds on nontrivial cycle lengths}. Discrete Math. 118 (1993), 45–56.

$\endgroup$
  • 1
    $\begingroup$ Hmm? What about 5,14,7,20,10,5,... ? Another one is at 17 or 19 (if I recall right). But these two are then the only additional known ones besides the "trivial" 1,2,1,... $\endgroup$ – Gottfried Helms Jun 24 '11 at 22:12
  • $\begingroup$ The second was 17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136, 68,34,17,... (thanks to wikipedia) en.wikipedia.org/wiki/Collatz_conjecture $\endgroup$ – Gottfried Helms Jun 24 '11 at 22:16
  • $\begingroup$ I guess Alain meant to write $3n+1$ there? As indeed, on the negative integers there are multiple known cycles and $\{1,2\}$ is not one of them. $\endgroup$ – TMM Jun 25 '11 at 13:27
  • $\begingroup$ Hmm, maybe the problem is already at Eliahou: I had a similar controverse in wikipedia, where someone stated the same idea, culminating in the sentence, that for 3n-1 the problem was solved. So there may be some urban legend around and I tried to look into the article of Eliahou. Unfortunately I can't get it online and our university-lib does not provide the "discrete mathematics" journal. So it is -unfortunately- too much hazzle for me to verify the origin of that statement at the moment - maybe someone else has the opportunity to look at "Eliahou/Discrete Math 118"? $\endgroup$ – Gottfried Helms Jun 25 '11 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.