How to prove that there is no 2-cycle using the Rhin bound?

[Lhachimi]

My specific notations for collatz :

Firstly , I will always take n odd and deal only with odd numbers

and instead of doing the trivial rule if n is even we divide n by 2 ,

I will directly do this instead : T(n)=\displaystyle \frac{3n+1}{2^{p_1}} where p_1=v_2(3n+1)

skipping powers of two is much more convenient for me .

and S_i=\displaystyle \sum_{j=1}^k p_j where S_0=0 , hence we get the following formula :

• T^{k}\left(n\right)=\displaystyle \frac{3^{k}n+\displaystyle \sum_{i=1}^{k}3^{k-i}2^{S_{i-1}}}{2^{S_{k}}} ,

so T^k(n)=n (i.e n does a cycle of length k) iff :

• n=\displaystyle \frac{\displaystyle \sum_{i=1}^{k}3^{k-i}2^{S_{i-1}}}{2^{S_{k}}-3^k}, let k >m with n>1

a simple upper bound of S_k is S_k \le 2k,

an m-cycle is a cycle where p_1=p_2=\cdots=p_{k-m}=1 and p_{k-i} \ge2 , \forall i : 0 \le i\le m-1

so n=\displaystyle \frac{3^k-3^{m-1}2^{k-m+1}+\displaystyle\sum_{i=k-m+2}^{k}3^{k-i}2^{S_{i-1}}}{2^{k+q}-3^k} where q=\displaystyle\sum_{i=0}^{m-1}p_{k-i}-m\ge m since p_{k-i} \ge 2

(since S_k=k+q \le 2k \implies q \le k )

for m=1 (i.e 1-cycle) , the sum going from k-m+2 up to k is just 0 and q=p_{k}-1\ge1

so n=\displaystyle \frac{3^k-3^{1-1}2^{k-1+1}+0}{2^{k+q}-3^k} =\displaystyle \frac{3^k-2^k}{2^{k+q}-3^k} , which lead to 2^{k+q}-3^k \mid 2^q-1

Using the Rhin bound we get : 2^n<2^{\lceil n \log_23\rceil}-3^n as shown here by Collag3n ,

so 2^k<2^{k+q}-3^k\le 2^q-1<2^q \le 2^k which is clearly a contradiction !

Now , for m=2 we have :

n=\displaystyle \frac{3^k-3^{2-1}2^{k-2+1}+\displaystyle\sum_{i=k-2+2}^{k}3^{k-i}2^{S_{i-1}}}{2^{k+q}-3^k} where q=p_k+p_{k-1}-2 \ge 2

n=\displaystyle \frac{3^k-3\cdot2^{k-1}+3^{k-k}2^{S_{k-1}}}{2^{k+q}-3^k}=\displaystyle \frac{3^k-3\cdot2^{k-1}+2^{k+r}}{2^{k+q}-3^k} where r=p_{k-1}-2 \ge 1

Now, using that 3^k \equiv 2^{k+q} \pmod{N} , where N=2^{k+q}-3^k

we have by Rhin bound : N>2^k and 3^k \equiv 3\cdot2^{k-1} - 2^{k+r} \pmod{N}

so 2^{k+q} \equiv 3 \cdot 2^{k-1}-2^{k+r} \pmod{N} \implies 2^{q+1} \equiv 3 - 2^{r+1} \pmod{N} (since N is odd)

so N \mid 2^{q+1}+2^{r+1}-3 \implies 2^k < N \le 2^{q+1} + 2^{r+1}-3 which isn’t a contradiction yet

---

Hercher extended the method further and proved that there exists no m-cycle with m \le 92

• What method /tools he used to do so ?

I want to know just the main theorems he used in transcendental theory (like Rhin bound for m=1),
even assuming the weak residue conjecture which will lead to an explicit formula of S_k,

\bbox[1px,border:1px solid #0a0]{\bbox[8px,border:1px solid #0a0]{S_k = \left \lceil \displaystyle k\log_2(3) \right \rceil}}

So any attempt of him (Hercher) , to bound S_k or to compare it to \log_2(3) ect , isn’t my intereset

As we’re assuming that we already have the exact formula of S_k no need to bound it

but rather the divisibility techniques he should exploit to prove the non existence of m-cycles

is what i’m looking for , like what we did in the (1-cycle case) and almost in the (2-cycle case)

---

Finally , I would know why If you assume the Collatz conjecture, then you can derive a bound between powers of 2 and 3 similar in nature to the one you can derive with Baker’s theorem ?

tao has written about this (Informal sketch only) on his blog using Fourier-analytic computation involving Riesz products and more sophisticated tools

is there a simpler way to do so ?

Thanks for help !

[mathkook]

hi! on the very last question only, see this post

[Lhachimi]

Thanks , it’s a wonderful post but what i’m asking now is how to prove the non-existence of 2-cycles !

• My attempt : I can show that if m is so big , also k does !

Firstly , we have in general the following identity:

\displaystyle \frac{2^{S_k}T^k(n)}{3^kn}=\prod_{i=0}^{k-1}1+\frac{1}{3T^i(n)} , so useful in many places !

So if T^k(n)=n (i.e a cycle of length k) :

\displaystyle \frac{2^{S_k}}{3^k}=\prod_{i=0}^{k-1}1+\frac{1}{3T^i(n)}

As an m-cycle is a cycle where p_1=p_2=\cdots=p_{k-m}=1 and p_{k-i} \ge2 , \forall i : 0 \le i\le m-1

Note that T^{i}(n)>T^{i-1}(n) iff p_i=1 and since T^i(n) is odd we get T^i(n) \ge T^{i-1}(n)+2

so T^i(n) \ge n+2i, \forall i : 0 \le i\le k-m (As p_{k-m} is the last p_i which is equal to one) ,

\implies \displaystyle \frac{2^{S_k}}{3^k} \le \prod_{i=0}^{k-m}(1+\frac{1}{3(n+2i)}) \times \prod_{i=k-m+1}^{k-1}1+\frac{1}{3T^i(n)}

and T^i(n) \le T^{i-1}(n) iff p_i \ge 2 , so we get T^{k-i}(n) \ge n+2i , \forall i : 0 \le i\le m-1

so , T^i(n) \ge n+2(k-i) , \forall i : k-m+1 \le i\le k

\implies \displaystyle \frac{2^{S_k}}{3^k} \le \prod_{i=0}^{k-m}(1+\frac{1}{3(n+2i)}) \times \prod_{i=k-m+1}^{k-1}1+\frac{1}{3(n+2(k-i))}

Again using S_k \ge \lceil k \log_23\rceil or the weak residue conjecture itself (doesn’t matter right now) ,

i can show things like when m\ge \cdots \implies k \ge \cdots ,

for instance , for m=1 (i.e 1-cycles) : that product \prod_{i=k-1+1}^{k-1}1+\frac{1}{3(n+2(k-i))} is just 1

taking n>10^4 (collatz true more than that) , will yield to k>200

of course we can do more sharp estimates to that product like what Collag3n did here !

and Hercher already did so in this table :

that’s cool , but my question is how we can derive an upper bound of k ?

i.e : can you show things like : if a non trivial 2-cycle exists, then k < 86 000 ?

[Collag3n]

Sorry, I won’t have much time to translate the notations or go deep for now.
Lower bounds on k are mostly based on Crandall 1978 Theorem 7.2 which is based on continued fractions inequalities (I can detail if you need). You can find some examples in Simon and de Weger Corollary 11 which uses Lemma 10 based on Crandall (partially in Lemma 9) and Lemma 4/Corollary 5.
Hercher is using the same principles but in an iterative way (using m_2, but I have to dig to see how he did it) to refine the bounds.
Upper bounds on k can be found in the Simon/de Weger paper Lemma 14, and is using Rhin bounds and some complicated formula from Lemma 7 which can be simplified to be more understandable. I’ll try to simplify it when I find some time.

[Lhachimi]

Sorry for bothering you ! Thanks for the response

[Collag3n]

You are not bothering me. I wish I had more time for this. These are interesting topics and I am curious about that m_2 iterative process Hercher used. I’ll make a short post about Crandall continued fraction bounds though.

[oros]

@Lhachimi

an m-cycle is a cycle where p_1=p_2=\cdots=p_{k-m}=1 and p_{k-i} \ge2 , \forall i : 0 \le i\le m-1

Are you sure about this definition?
Take m=2, you get a parity vector of the form 1^{k-2}0^{p_{k-1}-1}10^{p_k-1}.
Not exactly the usual definition of a 2-cycle (from Simons, de Weger, Hercher).

[Lhachimi]

What is then an m-cycle with my p_i notations ? Sorry if it’s confusing

[oros]

For a 2-cycle, something like

• 0 \leq i_1 < i_2 < k
• p_{i} \geq 2 if i \in \{i_1,i_2\} and p_i = 1 otherwise.

[Collag3n]

(Shouldn’t you have i_2=k-1 ?)

Lower bounds for k (Crandall):

Using \log_23 and its convergents \frac{p_n}{q_n}, a well know inequality states that for any pair of integer S_k, k with k<q_n we have \lvert S_k - k\log_23 \rvert>\lvert p_n - q_n\log_23 \rvert. We also have the classical continued fraction inequality \lvert p_n - q_n\log_23 \rvert>\frac{1}{q_n+q_{n+1}}

From here you have \lvert 2^{S_k} - 3^k\rvert>3^k\lvert S_k\log2 - k\log3 \rvert>3^k\log2\lvert p_n - q_n\log_23 \rvert>\frac{3^k\log2}{q_n+q_{n+1}}

which plugged into a_0<\frac{k3^{k-1}}{2^{S^k}-3^k} from here gives X_0<a_0<\frac{k(q_n+q_{n+1})}{3\log2} or k>\frac{X_0\cdot 3\log2}{q_n+q_{n+1}} where X_0=2^{71}. The other option is k>q_n so that k>\min\{q_n,\frac{X_0\cdot 3\log2}{q_n+q_{n+1}}\}
To find the right q_n just search for the minimum one satisfying X_0<\frac{q_n(q_n+q_{n+1})}{3\log2} and verify that q_{n-1}<\frac{X_0\cdot 3\log2}{q_n+q_{n+1}} (if not, pick q_{n-1})
Here, with X_0=2^{71} we have q_{n}=65470613321 and k>2.4\cdot 10^{10}

[oros]

@Collag3n

(Shouldn’t you have i_2=k-1 ?)

That would be better, indeed, to ensure a parity vector of the form 1^*0^*1^*0^*.

[Lhachimi]

If no m-cycle exists then no such collatz cycle exists ?

let me call an m-round a cycle where p_1=p_2=⋯=p_{k−m}=1 and p_{k−i}≥2,∀i:0≤i≤m−1

can we prove no such m-round exist ?

For instance for m=2 , can some one show why N \not \mid 2^{q+1}+2^{r+1}−3 ?

Acceptable and permissible things to use :

• we can use N>2^k by Rhin’s bound or any similar type of approximations
• we can use the Weak residue conjecture (I’ve no problem with that)
• we can assume the Waring problem is true so 3^k -2^k \times \lfloor 1.5^k \rfloor < 2^k -1.5^k

[Collag3n]

A known fact about Collatz trajectories is that an odd (let’s call it “bottom”) number b=c\cdot2^j-1 will reach t=c\cdot3^j-1 in exactly j steps of the Collatz function \frac{3n+1}{2^p} with p=1 where t is an even “top” number if c is odd. There is a similar pattern when all p=2:

d\cdot4^j+1 will reach d\cdot3^j+1 in exactly j steps.
This can be useful if you want to calculate some bounds in your configuration with p\geqslant 2

Side note on m-cycles,

in a cycle
\cfrac{2^{S_k}}{3^k} = \prod\limits_{i=0}^{k-1} \left( 1 + \frac{1}{3a_i}\right)<\prod\limits_{i=0}^{k-1} \left( 1 + \frac{1}{3a_0}\right) leading to \lvert S_k\log2 - k\log3 \rvert<\frac{k}{3\cdot a_0}

similarly you have with t_i=2^{l_i}\cdot b_{i+1} the “top” and “bottom”'s of an m-cycle:

\cfrac{2^{S_k}}{3^k} =\prod\limits_{i=0}^{m-1} \cfrac{2^{j_i}2^{l_i}}{3^{j_i}} = \prod\limits_{i=0}^{m-1} \cfrac{c_i2^{j_i}2^{l_i}}{c_i3^{j_i}} = \prod\limits_{i=0}^{m-1} \cfrac{b_i+1}{\frac{c_i3^{j_i}}{2^{l_i}}} < \prod\limits_{i=0}^{m-1} \cfrac{b_i+1}{b_{i+1}} =\prod\limits_{i=0}^{m-1} \left( 1 + \frac{1}{b_i}\right)<\prod\limits_{i=0}^{m-1} \left( 1 + \frac{1}{a_0}\right) with a_0 the smallest b_i leading to \lvert S_k\log2 - k\log3 \rvert<\frac{m}{a_0}

[Lhachimi]

Can some one change the title to : How to prove that there is no 2-round using the Rhin bound ?

because I can’t change it , the pen button isn’t working anymore !

and because i’m now interested in rounds and not the cycles yet (I will read about them later on)