On a proof that "there are at least $F_n$ Collatz permutations of length $n$".

Question

Let $n, k \in \Bbb{N}$ and $F_n$ be the $n$th term of the Fibonacci sequence.

Let $u$ be the map $x \to 3x+1$ and $d$ be the map $x \to \frac{x}{2}$.

Let a type be a sequence of $u$'s and $d$'s. Recall that a type must end with a mapping $d$ and that there cannot be two mappings $u$ consecutively.

Let $A = 2^a$ for some $a \in \Bbb{N}$ ($a$ is necessarily even).

Let a witness be of the form $U(A)$, where $U$ is the inverse of $u$.

Consider the following proposition:

If a type $σ$ contains $k$ $u$’s then there is a single congruence of the form $A = c \mod 3^k+1$ which must be satisfied in order that a trace of type $σ$ ends with witness $A$. Consequently, there is a least witness $A = 2^a$ with $a ≤ 2·3^k$, and a general witness is of the form $2^{a+jd}$ where $j$ is a nonnegative integer and $d = 2·3^k$.

This is a proposition from a paper on Collatz permutations. I am actually quite confused on how this proves that the proposition shows [...] that there are at least $F_n$ Collatz permutations of length $n$.

More straightforwardly, the following question on MSE seems to answer the question (for strings of length $\leq 14$) using induction of Fibonacci sequences.

Answer 1

The Collatz permutations of length $n$ are as in the linked paper the permutations of the numbers in the initial part, before the final descent upon reaching a power of $2,$ where the numbers occurring in this initial part have been ranked from $1$ to $n$ according to magnitude. The patterns of $u,d$ (up,down) are what give rise to Fibonacci numbers, and such patterns of length $n$ have to end with a $d$ and have no two adjacent $u$'s. That there are $F_n$ of these patterns can be shown by defining $G_n$ as the number of them, and looking at the last two terms, which must be $dd$ or $ud.$ In the first case, the last $d$ may be dropped and the contribution is $G_{n-1},$ while those ending $ud$ must have the term right before that as a $d$ (to avoid adjacent $u$) and so contribute $G_{n-2}.$ Thus $G_n=G_{n-1}+G_{n-2},$ and some base cases then show $G_n=F_n.$

Now the arguments in the paper are to show that each allowable pattern sequence of length $n$ actually occurs in the Collatz sequence, and it seems the paper shows any such sequence appears infinitely often.

The point about there then being "at least $F_n$ Collatz permutations of length $n$" is then a consequence of the fact that several Collatz permutations may correspond to a single pattern, but obviously different patterns have distinct Collatz permutations lying above them.

For example the two Collatz sequences $(5,3,4,2,1,7,6)$ and $(5,3,6,4,2,7,1)$ each correspond to the up down pattern $d,u,d,d,u,d.$