What are the bounds on the frequency of divisions by 2 in the Collatz cycles of natural numbers?

200 Views Asked by At

If $T^n(x):\Bbb N\times\Bbb N\to\Bbb N$ is the $n^{th}$ iterate of the Collatz function $T(x)=\frac12(3x+1)$ if $x$ odd and $x/2$ if $x$ even. Then let $Q(x):\Bbb N\to2^{\Bbb N}$ be the parity vector function given by $$Q(x)=\sum_{n=0}^\infty2^n(T^n(x)\pmod2)$$

$Q(x)$ is an infinite binary string containing a $1$ every time $x$'s Collatz sequence is odd and a $0$ every time it is even, for any natural number $x$.

As an aside, $Q$ is a partial function of a larger $\Bbb Z_2\to\Bbb Z_2$ bijection which is a 2-adic isometry.

Let $0\leq r(x)\leq1$ denote the proportion of digits of $Q(x)$ which are zeroes, and equivalently the proportion of steps in $x$'s Collatz sequence which are even. Therefore for all integers whose Collatz sequences stabilise finitely to the well known cycle $(2,1\ldots)$ we have $r(x)=\frac12$

Let $\overline {\Bbb N}$ indicate the subset of natural numbers whose Collatz sequences eventually stabilise to a cyclic orbit. Now suppose $x\in\overline {\Bbb N}$ is a natural number greater than $2$ and $T(x)$ has an eventually cyclic orbit which is not $(2,1\ldots)$. Under these suppositions I have fairly easily shown that $r(x)=\frac12$ is an upper bound for $r(\overline {\Bbb N})$ - the proof is not too long to give, if required. In fact $$\log_6(2)<r(x)<\frac12$$

Question

Since the proof was so easy and my talent is so little, I presume this is known and that there are already sharper bounds on $r(\overline {\Bbb N})$. What bounds on $r(\overline {\Bbb N})$ are known or provable with current techology?

The larger the $x$, the greater the cycle length and the sharper the upper bound will need to be, with $r(x)$ approaching its lower bound $\log_6(2)$ as $x\to\infty$.

1

There are 1 best solutions below

3
On

Well, for me the massaging of the Collatz-formulae is easier if we assume the "Syracuse"-style notation of the Collatz-iteration $$ a_{k+1}= {3a_k+1\over 2^{A_1}} \qquad a_k \small \text{ from the odd integers} $$ and for a $N$-fold iterated transformation the short, vectorial, notation: $$ a_{N+1}=T(a_1;[A_1,A_2,...,A_N]) $$ So let $N$ denote the (N)umber of steps $3x+1$ and $S$ denote the (S)um of the exponents $A_k$, which is also the number of $x/2$-steps.


Then, to convert this into the more common version of $(3x+1)/2$ and $x/2$ -stepping, we introduce $E$ the number of even steps without the $(3x+1)/2$ steps, so $E=S-N$.

With that, I understand your $r(a_1)$ as $r(a_1)=E/(N+E) = (S-N)/S = 1- N/S$.


We can observe,

  • that the trival cycle $1 = T(1;[2,2,2,...2])$ to any length $N$, has the values $S=2N$ and $E=N$ and $r(a_1)= 1-N/S = 1-N/(2N)=1/2 $
  • that the first cycle in the negative numbers $-1= T(-1;[1,1,1,1,...,1])$ to any length $N$, has $S=N$, $E=0$, and $r(a_1)= 0$
  • that the second cycle in the negative numbers $-5=T(-5;[1,2,1,2,1,2,...,1,2])$ to any even length $N=2n$, has $S=3n$, $E=n$ and $r(a_1) = E/(N+E)= n/(3n) = 1/3 $

Now to have a cycle of any length, and other than $T(a_1;[2,2,2,...,2])$ we can use the well known multiplication-formula for the $N$ members of an expected cycle $a_k$ ($k=1..N$) $$ a_2 \cdot a_3 \cdot ... \cdot a_N \cdot a_1 = \left({3a_1+1\over 2^{A_1}}\right) \left({3a_2+1\over 2^{A_2}}\right) \cdots \left({3a_N+1\over 2^{A_N}}\right) \tag 1$$ This can be rearranged to $$ 2^S = 2^{A_1+A_2+...A_N} =\left(3+{1\over a_1}\right) \left(3+{1\over a_2}\right) \cdots \left(3+{1\over a_N}\right) \tag 2$$ We see, that the rhs must be at least as large as the smallest perfect power of $2$ larger than $3^N$, but at most as $4^N = 2^{2N}$ so we get for the lhs (writing $\gamma=\log_2(3)$, and further below $\gamma_1=\log_2(3)-1$): $$ 2^{\lceil N \cdot \gamma \rceil} \le 2^S \le 2^{2N} \tag 3$$ which in terms of $S$ means $$ \lceil N \cdot \gamma \rceil \le S \le 2N \qquad \text{where } S \in \mathbb N^+ \tag 4 $$ and in terms of $E$ instead $$ \lceil N \cdot \gamma \rceil -N =\lceil N \cdot \gamma_1 \rceil \le E \le N \tag 5$$

From this you have bounds for your $r(a_1)$-parameter: $$ r(a_1) = { E \over N+E } \implies \\ {\lceil N \cdot \gamma_1 \rceil \over N+E} \le \frac E{N+E} = r(a_1) \le \frac N{N+E} \tag 6 $$


Using (5) we denote $E_\min = \lceil N \gamma_1 \rceil$ and $E_\max = N$.

From this you have bounds for your $r(a_1)$-parameter:

$ \displaystyle \lim_{N \to \infty} r(a_1)_{E_{min}} = 1-{ 1 \over (1-\{N \gamma_1 \} + N \gamma_1 )/N+1 } = 1-\frac 1{\gamma_1+1} \\ \qquad = 1- \log_3(2) = \log_3(1.5) \approx 0.369070246429 \qquad \qquad \tag {7a}$

$ \displaystyle \lim_{N \to \infty} r(a_1)_{E_{max}} = { E_{max} \over N + E_{max} } = { N \over 2N } = \frac 12 \qquad \qquad \qquad \qquad \qquad \tag {7b} $ The latter is the ratio for the trivial cycle $r(1)$; the ratio $0$ is for $r(-1)$ and (7a) is the limit for any other cycle.

P.S: How did you get the sharper lower bound $\log_6(2)$?