An optimisation of Luo's paper

[Lhachimi]

After revising my closed question. i found that it’s an open problem due to Eric Roosendaal, namely the weak residue conjecture.

Digging a little bit into towards published results of the same nature, I found this paper, which was submitted on July , to Elsevier by Youchun Luo. He found an upper bound for which hasn’t been found in the literature, namely
$$\operatorname{Res}(N)<O(N)^{\frac{1}{9}}$$

which gives the corollary that when , it always holds that .

However, his method involved a lot of nasty sums and hairy calculations. And so, after reviewing his method, I found a better estimate: when , it always holds that .

So,

• Is what I found a new upper bound ?
• Could someone point me towards published papers like Luo’s paper?

Here is a proof of my estimate:

Given an odd positive integer , let , be the odd iteration steps and the even iteration steps when iterates to , respectively.

The residue of is given by $$\operatorname{Res}(N)=\displaystyle\frac{2^{E(N)}}{3^{O(N)} \cdot N}.$$

(These definitions are according to my notations - check this post.)

For an odd positive integer , if we let be the minimal number of steps such that , then , , and the residue is expressed as .

This motivates the definition of the -th residue of , denoted as or simply , for any :

$$R_k = \frac{2^{S_k} \cdot T^k(n)}{3^k n} = \prod_{i=0}^{k-1} \left( 1 + \frac{1}{3T^i(n)} \right)$$

Note that is not necessarily equal to 1 in this general definition. Furthermore, the sequence is strictly increasing, as:

$$\frac{R_{k+1}}{R_k} = 1 + \frac{1}{3T^k(n)} > 1$$

Proposed Estimate

We intend to demonstrate that if , then . This result remains valid regardless of the value of . This implies two significant consequences:

1. In the case of cycles (where ), if , then , which simplifies to .
2. For the standard Collatz trajectory (where and is minimal), it follows that when , .

Derivation

For the initial case , we have . We may therefore assume . The -th residue can be expanded as:

$$R_k = \prod_{i=0}^{k-1} \left( 1 + \frac{1}{3T^i(n)} \right) = \left( 1 + \frac{1}{3n} \right) \prod_{i=1}^{k-1} \left( 1 + \frac{1}{3T^i(n)} \right)$$

Given that for all , , it follows that must be an odd integer not divisible by 3. We can therefore bound as follows:

$$R_k \le \left( 1 + \frac{1}{3n} \right) \prod_{i=1}^{k-1} \left( 1 + \frac{1}{3a_i} \right)$$

where represents the sequence of integers greater than 1 that are odd and not divisible by 3 (specifically, , or the sequence ).

Applying the empirical result that the Collatz conjecture has been verified for all , we can safely assume . Consequently:

$$R_k < \left( 1 + \frac{1}{3 \cdot 10^6} \right) \prod_{i=1}^{k-1} \left( 1 + \frac{1}{3a_i} \right)$$

Numerical evaluation (via Desmos) confirms that this product remains less than for all .

[Lhachimi]

it’s my post (it was closed ) from https://math.stackexchange.com/questions/5117088/an-optimisation-of-luos-paper?noredirect=1#comment11026261_5117088

[Collag3n]

It seems that the double $$ don’t work well. Perhaps you should replace them by single $.

I’ll use heavy approximations just to highlight the idea (don’t take all the < sign bellow as rigorous).

In Luo’s paper we have roughly

\log(\operatorname{Res}(N))=\sum\limits_{i=0}^{k-1} \log\left( 1 + \frac{1}{3\cdot T^i(n)}\right)<\sum\limits_{i=0}^{k-1} \frac{1}{3\cdot T^i(n)}\leqslant \frac{1}{3}\sum\limits_{i=0}^{k-1}\frac{1}{a_i}
where the a_i are taken from the sequence of number starting from a_0=5 with \gcd(a_i,6)=1, and k=O(N)

Using \sum\limits_{i=0}^{k-1} \frac{1}{a_i}\sim\frac{1}{3}\log (k) we may find (with more precise bounds of course) that \log(\operatorname{Res}(N))<\frac{1}{3}\frac{1}{3}\log (k) or \operatorname{Res}(N)<O(N)^\frac{1}{9}

Now, if we take a_j, the smallest number of the Collatz trajectory which is not necessary 5, but is the j^{th} number of the sequence (of 6n\pm1 numbers) and take the k smallest of them from there, we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{1}{3}(\log (k+j)-\log (j))=\frac{1}{3}(\log (\frac{k}{j}+1)) and with a_j\sim 3j we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{1}{3}(\log (\frac{3k}{a_j}+1))

To keep \operatorname{Res}(N)<2 we find (with that 6n\pm1 optimisation) a bound like this: \log(\operatorname{Res}(N))<\frac{1}{3}\sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{1}{3}\frac{1}{3}(\log (\frac{3k}{a_j}+1))<\log(2) and from there \frac{3k}{a_j}+1<512 or

k<170a_j

and indeed, a quick check on the product of \prod\limits_{i=j}^{j+k-1} \left( 1 + \frac{1}{3a_i}\right) for various j shows that it starts to exceed 2 at k\sim 170 a_j (a_j being the smallest element of the trajectory and of the 6n\pm1 sequence). Note that for a_j=5 the product exceeds 2 at k>582 (here the 170 constant is less precise due to the heavy approximations)

Things are more complicated if the starting number is a multiple of 3

[Collag3n]

Did you mean k<582 ? because if I take the product of the first 581 “6n\pm1” numbers I get \left( 1 + \frac{1}{3\cdot 5}\right)\left( 1 + \frac{1}{3\cdot 7}\right)\left( 1 + \frac{1}{3\cdot 11}\right)...\left( 1 + \frac{1}{3\cdot1745}\right)<2, but if I take one more, it exceeds 2.

Anyway, to answer one of your question, yes, 582 is a valid bound.
If the trajectory do not start with a multiple of 3, than the product \operatorname{Res}(N))=\prod\limits_{i=0}^{k-1}\left( 1 + \frac{1}{3\cdot T^i(n)}\right) is bound by the above product of the k smallest “6n\pm1” numbers (and up to 581 of them, by 2).
If the trajectory starts with a multiple of 3, than either that multiple of 3 is greater than 1745 and all is fine, or it has already been manually checked.

Note that in a non-cyclic trajectory, the last element of the trajectory is not in the \operatorname{Res}(N))=\prod\limits_{i=0}^{k-1}\left( 1 + \frac{1}{3\cdot T^i(n)}\right) product, which allows to start from 5 even for trajectories reaching 1. This trick can also be used in trajectories not reaching 1 but with the last element being the smallest element of the trajectory. In a cyclic trajectory, the last element is already in the product as “first element”.

[Lhachimi]

I guess we can take k \le 582 , since 582.5 > 582

or maybe it’s just due to floating-point math precision in Desmos , anyway thanks for the response !

[Collag3n]

Ok I see, you take the product for the 581 first “6n\pm1” numbers and the starting number of the trajectory (which is set to be greater then 10^6, so does not change the product a lot).

[Collag3n]

You can even optimize more: If we define a “branch” as the set of odd numbers having the same number as “next odd” in a collatz trajectory (e.g. 7, 29, 117,… all have 11 as “next odd” in a trajectory), we know that a trajectory never have two numbers of the same branch (a trajectory can’t have 7 and 29 in its path to 1 or infinity), so we can bound all trajectories by the root (smallest odd number) of the branch. If the root is a multiple of 3, we just take the next smallest (which is root*4+1).
The roots are either of the form 8n+1 or 4n+3. This can be split into 24n+1, 24n+9 a multiple of 3 for which we take the next smallest or 96n+37, 24n+17 and 12n+3 for which we take 48n+13, 12n+7 and 12n+11. For 1 we take the next smallest which is 5.

This means that the bound can be extended from 582 to 1106 (all trajectories less or equal to 1106 have Res(N)<2)

PariGP code:

prod6n()=a0=5;a1=1;n=0;while(a1<2,if((a0%6==1||a0%6==5)&&(a0%24==1||a0%24==17||a0%12==7||a0%12==11||a0%96==37||a0%48==13||a0==5),n=n+1;a1=a1*(1+1/(3*a0)));a0=a0+1);return(n)

Here you can also take the starting number greater than 10^6

[Lhachimi]

1106 is a genuine improvement

[Collag3n]

The last optimisation can also be used for trajectories not reaching 1 (e.g. cycles)

It seems to work based on densities (but I am not sure it is correct, I need to dig, but it matches empirically)

In the classic 6n\pm1 optimisation you work with a denisty of \frac{1}{6}+\frac{1}{6}=\frac{1}{3}, but here we work with a density of \frac{1}{12}+\frac{1}{12}+\frac{1}{24}+\frac{1}{24}+\frac{1}{96}+\frac{1}{48}=\frac{9}{32}, so if we take our optimized a_i (only the roots) we work with

\sum\limits_{i=0}^{k-1} \frac{1}{a_i}\sim\frac{9}{32}\log (k) instead of \sum\limits_{i=0}^{k-1} \frac{1}{a_i}\sim\frac{1}{3}\log (k)

Now, if we take a_j, the smallest number of the Collatz trajectory which is not necessary 5, but is the j^{th} number of the sequence (of roots) and take the k smallest of them from there, we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{9}{32}(\log (k+j)-\log (j))=\frac{9}{32}(\log (\frac{k}{j}+1)) and with a_j\sim \frac{32}{9}j we have \sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{9}{32}(\log (\frac{32k}{9a_j}+1))

To keep \operatorname{Res}(N)<2 we find a bound like this: \log(\operatorname{Res}(N))<\frac{1}{3}\sum\limits_{i=j}^{j+k-1} \frac{1}{a_i}\sim\frac{1}{3}\frac{9}{32}(\log (\frac{32k}{9a_j}+1))<\log(2) and from there \frac{32k}{9a_j}+1<2^{\frac{32}{3}} or

k<457a_j

and indeed, a quick check on the product of \prod\limits_{i=j}^{j+k-1} \left( 1 + \frac{1}{3a_i}\right) for various j shows that it starts to exceed 2 at k\sim 457 a_j (a_j being the smallest element of the trajectory and of the roots sequence).

Since all numbers have been checked up to 10^{21} this means a cycle don’t exceed 2 as long as k<457\cdot 10^{21}

[Collag3n]

Note that when you use a sequence (of consecutive numbers like here, or consecutive 6n\pm1, or consecutive roots) ordered by ascending a_i, \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+i}\right)<\prod\limits_{i=0}^{k-1} \left( 1 + \frac{1}{3a_0}\right)=\left( 1 + \frac{1}{3a_0}\right)^k
It is better to use the first product since it gives a larger margin before reaching 2