Number of possible cycles in collatz conjecture

Question

I had been following all the blogs, but I would like to understand, whether an attempt has been made to understand how many cycles are possible apart from the 1-4-2-1 cycle in collatz problem

Answer 1

A cycle other than the $1-4-2-1$ cycle has not been found. If such a cycle was found, then the conjecture would be disproved.

If it was proven that no such cycles exist, then the conjecture would still not be solved, since there could be initial values of $n$ for which the recursion diverges.

---

This is an open problem. Some results regarding cycles of specific types have been proven.

Answer 2

Proofs which deal with the conjecture in terms of bounding the possible number of cycles are not known to me (for instance I've not seen such a concept referred to in Lagarias's survey), but you might take a deeper look (than me) at Kurt Mahler's work of z-numbers; he proves, that only finitely many z-numbers exist and this is known to be related to the cycle-problem in the Collatz-map. There is a bit about that z-numbers on mathworld, and the Mahler-article is available in some online digitized library.

Besides that it is with elementary means possible to prove, that cycles of some specific lengthes cannot exist, that means one could look at the length of a (virtual) list of excluded lengthes, but I doubt that someone would have tried to make an argument that such a list of excluded cycle-lengthes has some bound on its own length or is either finite or infinite. (for some finite lengthes to be excluded you can see into my amateurish article in the section of "general cycles").

It is a topic in already early articles (I think R. Terras was the first one) to prove that if one cycle exists at all, it must have a length of at least so-and-so-many steps (I think it is about 170000 or something - but again: this is about the length of possible cycles, not the upper/lower bound of the possible number of cycles)

Answer 3

Cycle Shapes

A cycle under the Collatz map is completely determined by its "shape", in the following sense: A cycle contains a certain number of odd elements, and between each odd element and the next, there are a certain number of divisions-by-2 that occur.

For example, the famous $(1,4,2)$ cycle contains 1 odd entry, followed by 2 halvings. This can be described by the vector $\langle 2 \rangle$. The cycle on negative integers: $(-5,-14,-7,-20,-10)$, contains two odd elements, with 1 and 2 halvings following them, so we get a shape vector: $\langle 1,2\rangle$. The other two known cycles on negative integers have shape vectors $\langle 1 \rangle$ and $\langle 1,1,1,2,1,1,4\rangle$.

Non-integer cycles

Now, for any shape vector you can write down, a cycle exists with that shape. In most cases, however, the numbers in such a cycle are not integers. The domain of the Collatz map naturally extends to rational numbers with denominators that are coprime to $6$. Suppose you want to see a cycle with shape $\langle 1,1,3\rangle$. It is straightforward to calculate (see below) that we will see this cycle by starting with $n=\frac{19}{5}$, thus:

$\left(\frac{19}{5}, \frac{62}{5}, \frac{31}{5}, \frac{98}{5}, \frac{49}{5}, \frac{152}{5}, \frac{76}{5}, \frac{38}{5}\right)$

(Equivalently, instead of extending the domain to certain rational numbers, one can study the "$3n+q$" function, where $q\equiv\pm 1\pmod6$. One finds then, for $q=5$, that we have the cycle $(19,62,31,98,49,152,76,38)$.)

Thus, the question of whether cycles exist is easy to answer, but that makes the really hard question into: Of all cycles, which ones have integer elements? To address this question, it helps to actually look at the calculation alluded to earlier.

Calculating a cycle from its shape

Suppose you want to see a cycle with shape vector $\langle a_1,\ldots,a_L\rangle$. First, we define $W=a_1+\cdots+a_L$ - each cycle is thought of as having a "length" and a "width", and we can call it a "$L\times W$ cycle". The above cycle, involving the number $\frac{19}{5}$, is a $3\times 5$ cycle. Our general $L\times W$ cycle begins with the number:$$\frac{3^{L-1}+2^{a_1}3^{L-2}+2^{a_1+a_2}3^{L-3}\cdots+2^{a_1+\cdots+a_{L-1}}}{2^W-3^L}.$$

Indeed, the number $\frac{19}{5}$ can be seen this way: $$\frac{19}{5}=\frac{9+6+4}{32-27}.$$

If you are looking for a cycle to contain integers, one of two things must happen:

1. $2^W-3^L=\pm 1$, or
2. That denominator divides that numerator for some vector of some length.

Integer case 1: Denominator is $\pm 1$

Considering option 1, we only have a few possibilities:

• $2^1 - 3^1 = -1$: The most trivial cycle, the $1\times 1$ cycle whose only odd element is $-1$.
• $2^2 - 3^1 = 1$: The only $1\times 2$ cycle is the famous $(1,4,2)$ cycle.
• $2^3 - 3^2 = -1$: There is only one possible $2\times 3$ cycle; its two odd elements correspond to the two ways of numbering its shape vector. Using $\langle 1,2\rangle$ we get $-5$, and using $\langle 2,1 \rangle$ we get $-7$.

These are the only instances where a power of $2$ and a power of $3$ differ by $1$; indeed, the difference $|8-9|=1$ is the only instance of any perfect powers $(n^p\text{ with }n,p\in\{2,3,4,\ldots\})$ differing by $1$. (See https://en.wikipedia.org/wiki/Catalan%27s_conjecture)

Integer case 2: The fraction reduces

The fact that option 2 is possible is made clear by the existence of the cycle beginning at $-17$. With shape vector $\langle 1,1,1,2,1,1,4\rangle$, it is an $11\times 7$ cycle, with initial entry: $$\frac{729 + 2\cdot 243 + 4\cdot 81 + 8\cdot 27 + 32\cdot 9 + 64\cdot 3 + 128}{2048-2187}=\frac{2363}{-139}=-17.$$

This kind of "coincidence", where the fraction reduces all the way down to an integer, is what has to happen for another cycle to exist in $\mathbb{Z}$. Unfortunately, the divisibility question seems intractable, but there is another consideration that is helpful: in order for a rational number $r$ to be an integer, it must satisfy $|r|\ge 1$. Indeed, for $r$ to be a counterexample to the Collatz conjecture, it must satisfy $r>2^{50}$, or whatever lower bound has been established by simply checking natural numbers.

This requirement turns out to imply a requirement on the shape vector, and more particularly on the length and width of such a cycle. Consider a cycle $C$, on positive numbers, with odd entries $n_1, \ldots n_L$. Define the cycle's "altitude", $\mathrm{Alt}(C)=\mathrm{HM}(n_1,\ldots,n_L)$, where $\mathrm{HM}$ indicates the harmonic mean, and its "defect" as $\mathrm{Def}(C)=2^{W/L}-3$. (This quantity is positive if and only if the entries in the cycle are positive.) Then we have the inequality: $$\mathrm{Alt}(C)\le\frac1{\mathrm{Def}(C)}$$ for all positive cycles. (This theorem can be proved via the method of Lagrange multipliers, with the central useful fact being the convexity of the logarithm function.)

Examples:

For the famous cycle $C=(1,4,2)$, we have $$\mathrm{Alt}(C)=1=\frac1{2^{2/1}-3}$$

For the $3\times 5$ cycle C above, with shape vector $\langle 1,1,3\rangle$, we have $$\mathrm{Alt}(C)=\mathrm{HM}\left(\tfrac{19}{5},\tfrac{31}{5},\tfrac{49}{5}\right)\approx 5.698<5.721\approx\frac1{2^{5/3}-3}$$

As a consequence of this inequality, any heretofore undiscovered cycle in the natural numbers, which must have a very large altitude, must also have a very small defect, so the positive number $\left(\frac{W}{L}-\frac{\log 3}{\log 2}\right)$ must be very small indeed.

Unfortunately, the current best results on Diophantine approximation of logarithms are not sufficient to bound such a cycle out of existence. Nevertheless, I believe that this answer addresses the OP's question, in this sense: The only cycles possible, other than the famous one, are ones with shapes that very closely approximate $\frac{\log 3}{\log 2}$, and in which the specific shape vectors produce numerators that are multiples of $2^W-3^L$.

If you are looking for such creatures, then I wish you Happy Hunting! Please let us know if you find any!