17
$\begingroup$

I've been recreatively working on the Collatz conjecture for a few months now, and I think I may have found something that could potentially prove at least half of the conjecture, which is the non-existence of non-trivial cycles. $\textbf{If you want to tl;dr}$, just check the framed equations. The first one is my conjecture, and the second one is a corollary which shows that if the conjecture is correct with all the conditions and everything, it would contradict the existence of non-trivial cyclic patterns. $\textbf{This is supposed to lead to a proof by contradiction}$ and so far, it seems to work. Otherwise, you could what I've done to get to this conjecture idea (because I'm narrating it chronologically so you can sort of get my process). I've not seen any peer-reviewed proof of their inexistence, so I guess it's still an open problem by itself. The fact is, I really think this conjecture is manageable, I just think I don't have the level required to tackle this kind of thing. Anyway, first things first, I didn't use the usual $$a_0\in\mathbb N,~a_{n+1}=\left\{\begin{array}{cc}(3a_n+1)/2&a_n~\rm odd\\a_n/2&\rm otherwise\end{array}\right.$$ but a more dynamical subsequence, which I randomly called $(e_n)$, defined with $$e_0=\frac{a_0}{2^{\nu_2(a_0)}},~e_{n+1}=\frac{3e_n+1}{2^{\nu_2(3e_n+1)}}$$ where $\nu_2$ is the 2-adic valuation. This basically chops off all the even numbers and basically keeps the core dynamics of the sequences. First off, I had to prove by induction that $$\begin{array}{ccccc} e_{n+1}&=&3^n\left(3e_0+1+\sum\limits_{k=1}^n\frac1{3^k}\prod\limits_{\ell=0}^{k-1}2^{\nu_2(3e_\ell+1)}\right)\prod\limits_{k=0}^n\frac1{2^{\nu_2(3e_k+1)}}&n\ge1&(1)\\ &=&3^n\left(3e_0+\left(\sum\limits_{k=0}^n\frac1{3^k}\prod\limits_{\ell=k}^n\frac1{2^{\nu_2(3e_\ell+1)}}\right)\prod\limits_{k=0}^n{2^{\nu_2(3e_k+1)}}\right)\prod\limits_{k=0}^n\frac1{2^{\nu_2(3e_k+1)}}&n\ge0&(2) \end{array}$$ However, $\nu_2(3e_k+1)$ has a very chaotic behaviour for $k\in\mathbb N$, so I had to bound it in some way or another. First obvious bound is that $\nu_2(3e_k+1)\ge1$, since from how the sequence is defined, $3e_k+1$ is even. Hence, I deduced that $$e_{n+1}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\le3^{n+1}e_0+\frac{3^n}{2^{n+1}}\left(\sum_{k=0}^n\left(\frac23\right)^k\right)\prod_{k=0}^n2^{\nu_2(3e_k+1)}$$ Since $\sum\limits_{k=0}^n\left(\frac23\right)^k<3$ for all $n\in\mathbb N$, I found out that $$e_{n+1}\prod_{k=0}^n2^{\nu_2(3e_k+1)}<3^{n+1}e_0+\frac{3^{n+1}}{2^{n+1}}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\\ \iff\frac1{e_0}\left(e_{n+1}-\left(\frac32\right)^{n+1}\right)\prod_{k=0}^n2^{\nu_2(3e_k+1)}<3^{n+1}$$ Now, I need to use a bit of a trick here. I'll assume $e_0$ to be minimal. In fact, for all $(e_n)$ which doesn't get to the trivial sequence, it can be shown that there are infinitely many $k\in\mathbb N$ such that for all $n\ge k$, $e_k\le e_n$, so this trick can describe literally any counterexample of the Collatz conjecture. Therefore, we get $$\prod_{k=0}^n2^{\nu_2(3e_k+1)}<\frac{3^{n+1}}{1-\frac1{e_0}\left(\frac32\right)^{n+1}}$$ if and only if $n+1 < \log_{3/2}e_0$. Since we know that for all $e_0\le87\times2^{60}$, $(e_n)$ is not a counterexample, we have $$\prod_{k=0}^n2^{\nu_2(3e_k+1)}<\frac{3^{n+1}}{1-\frac1{87\times2^{60}}\left(\frac32\right)^{n+1}}$$ for all $n+1 < \log_{3/2}(87\times2^{60})\approx113.58\ldots$ Hence, we got that $$\sum_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23-\log_2\left(1-\frac1{87\times2^{60}}\left(\frac32\right)^{113}\right)$$ for $n\le112$. So, to sum it up, we just bounded $\sum\limits_{k=0}^n\nu_2(3e_k+1)$ is bounded from above by $(n+1)\log_23+c$ for some constant $c$. Yet, we can also derive that for all $n\le107$, $$\sum_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23$$ (NB : The $107$ is here because $\left\lfloor(n+1)\log_23\right\rfloor=\left\lfloor(n+1)\log_23-\log_2\left(1-\frac1{87\times2^{60}}\left(\frac32\right)^{n+1}\right)\right\rfloor$ for all natural $n\le107$). Anyway, basically, here is my conjecture :

If $(e_n)$ doesn't converge to 1 and that for all $n\in\mathbb N$ we have $e_0\le e_n$, then for all $n\in\mathbb N$, $$\begin{array}{|c|}\hline\sum\limits_{k=0}^n\nu_2(3e_k+1)<(n+1)\log_23\\\hline\end{array}$$ I even have some numerical evidence supporting it. With a little algorithm which basically computes, for any $e_0$, the sum $\sum\limits_{k=0}^n\nu_2(3e_k+1)$ and checks whether or not it's below $(n+1)\log_23$ for as long as for all $k\le n$, we have $e_0\le e_k$. Checked all odd $e_0$ from $3$ to $29\;322\;479$ and it worked, so I'm pretty confident with that ! Now, how is this even related to the non-existence of cyclic sequences ? Well, if we assume this conjecture and using formula $(2)$, we'd have for minimal $e_0$ and $n\ge1$ $$\begin{array}{|c|}\hline e_{n+1}\ge 3^{n+1}\left(e_0+1/3+2/9\right)\frac1{3^{n+1}}=e_0+5/9>e_0\\\hline\end{array}$$ But this means that we could only reach $e_0$ once, which is a contradiction to cyclicity if it works for all minimal $e_0$. So basically, if my upper bound turns out to be correct for all minimal $e_0$ and $n\ge0$ (or $n\ge1$ to be cautious but anyway), this would essentially imply that there is no non-trivial cycle ! I'm putting this here so people could eventually work out a way to prove it. Obviously tried by myself, but I figured out I might not be good enough for this !

$\endgroup$
8
  • 2
    $\begingroup$ (+1) for the nice effort! (Perhaps I can come back to this later) $\endgroup$ May 3, 2019 at 13:27
  • 2
    $\begingroup$ Glad I stumbled across this! I don't have time to read right now, but skimming over it suggests that you should check out this paper: (deweger.xs4all.nl/papers/[35]SidW-3n+1-ActaArith[2005].pdf). $\endgroup$ May 4, 2019 at 10:14
  • 1
    $\begingroup$ Related, but I don't know if it really helps. At least it shows that weird patterns occur when $\log_23$ is brought up somehow, and it has the same goal which is to disprove existence of cyclic sequences. Maybe we could be taking some of those bounds and stuff could lead us to find an upper bound for the value of minimal elements of non-trivial cycles so we could computationally disprove the existence of nontrivial sequences ? I don't know, really, I still need to dig it a bit. Thanks for suggestion ! $\endgroup$ May 4, 2019 at 15:39
  • 1
    $\begingroup$ I already looked at this some time ago and got this formula $(3+\frac{1}{e_{max}})^{n+1}\leq\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\leq (3+\frac{1}{e_{min}})^{n+1}$ where $e_{min}$ and $e_{max}$ are min and max values taken by $e_j$ between $e_0$ and $e_{n+1}$. I played a bit by setting $e_{n+1}=e_0$ or $e_0=e_{min}$ or $e_{min}=87\cdot2^{60}$...but got nowhere at the time $\endgroup$
    – Collag3n
    May 5, 2019 at 20:00
  • $\begingroup$ Well, that's not as precise as where i got, but it's already an improvement if you managed to prove the second formula for all $n$ (I'm assuming you did but I just wanna be sure) ! $\endgroup$ May 5, 2019 at 21:04

4 Answers 4

6
$\begingroup$

$$\frac{3e_0+1}{2^{\nu_2(3e_0+1)}}=e_1$$ can be rewritten as $$(3+\frac{1}{e_0})=2^{\nu_2(3e_0+1)}\frac{e_1}{e_0}$$ Now you have

$(3+\frac{1}{e_0})=2^{\nu_2(3e_0+1)}\frac{e_1}{e_0}$

$(3+\frac{1}{e_1})=2^{\nu_2(3e_1+1)}\frac{e_2}{e_1}$

...

$(3+\frac{1}{e_n})=2^{\nu_2(3e_n+1)}\frac{e_{n+1}}{e_n}$

You multiply every LHS/RHS to get

$(3+\frac{1}{e_0})(3+\frac{1}{e_1})...(3+\frac{1}{e_n})=\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}$

From here you get

$$(3+\frac{1}{e_{max}})^{n+1}\leq\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}\leq (3+\frac{1}{e_{min}})^{n+1}$$

But it means that in a cylce where $e_{n+1}=e_0$ you have

$\prod_{k=0}^n2^{\nu_2(3e_k+1)}\gt 3^{n+1}$ or $\begin{array}{|c|}\hline\sum\limits_{k=0}^n\nu_2(3e_k+1)>(n+1)\log_23\\\hline\end{array}$

Unless I messed something in translating to your notations, it does not match what you get.

$\endgroup$
2
  • $\begingroup$ Well I did say that if my bound is correct for all $n$ and for all $e_0\le n$, then there would be no cyclic pattern. Your bound definitely is correct assuming $(e_n)$ is cyclic. However, my bound seems numerically more likely, so I don't know. (Also, I think we can at least say that nontrivial cycle lengths in $(e_n)$ last longer than $107$ iterations tho ? But since Lagarias proved that they last longer than $301\;994$ in $(a_n)$ I don't think it's very worthwhile...) $\endgroup$ May 6, 2019 at 7:45
  • 1
    $\begingroup$ Oh by the way, I've played around your formula a bit and actually, $\sum\limits_{k=0}^n\nu_2(3e_k+1)\le(n+1)\log_2\left(3+\frac1{87\times2^{60}}\right)+\log_2e_0-\log_2e_{n+1}\le(n+1)\log_2\left(3+\frac1{87\times2^{60}}\right)$ if $e_0=e_{min}$ as when i got this bound, so your result is actually an improvement since it works for all $n$ and not just $n\le107$. $\endgroup$ May 6, 2019 at 13:34
3
$\begingroup$

I am not sure if this helps: in our working paper we studied cycles in Collatz sequences for $3n+1$ and the generalized form $kn+1$. We empirically found out that cycles only occur, if the condition $\alpha=\lfloor n*log_2k\rfloor+1$ is met. That is close to the considerations above. The variable $\alpha$ is the number of divisions that is performed to get from the first odd number $v_1$ to the odd number $v_{n+1}$ that forms the cycle. The variable $n$ is the length of the cycle.

Example for $v_1=13$, $k=5$ and $n=3$:

  • $v_{n+1} = 5^3 * 13 * (1 + \frac{1}{5 * 13}) * (1 + \frac{1}{5 * 33}) * (1 + \frac{1}{5 * 83}) * 2^{-7}$ = 13
  • $\alpha = \lfloor 3*log_25\rfloor+1$ = 7

Our hypothesis holds for all known cycles. Maybe this information is usefull for your further analysis.

$\endgroup$
14
  • $\begingroup$ Indeed, if there is a cycle for $k=3$, the exponent of $2$ must be $j=\lceil n\cdot \log_23\rceil$ which is the first exponent where the fraction $\frac{3^n}{2^j}<1$. This is known for Collatz (I guess it is the same for other $k$ values). e.g. here where I talk about the specific inverse V-Shape cycles: math.stackexchange.com/questions/3338466/… ("not equal" means no cycle -> proved by Steiner in 1977) $\endgroup$
    – Collag3n
    Mar 24, 2020 at 10:17
  • 1
    $\begingroup$ @Collag3n - just a minor follow-up question: you write that $j = \lceil n \log_2 3\rceil$ . I've seen something like this formulation multiple times around last days. Has anywhere the proof been done, that not $j$ can be larger, for instance $j = 1+\lceil n \log_2 3\rceil$ ? I'm not sure I've done this once myself - years ago, if perhaps at all - but wouldn't remember today. $\endgroup$ Dec 27, 2020 at 13:22
  • 1
    $\begingroup$ @Gottfried Helms, no, this is well known but I don't think there is a proof of that (I have to dig in my notes, but seeing my comment above, I don't think so). If the accumulation of +1 is greater than the main term, You could have $j = 1+\lceil n \log_2 3\rceil$. For some special cases (Inverse V-shape or "1 cycle"), it is however easy to show. The proof from the paper is flawed so I guess the question is still open. $\endgroup$
    – Collag3n
    Dec 27, 2020 at 21:17
  • 1
    $\begingroup$ @Collag3n - ah, yes, thanks; because of the comments above I was as well confident this is only heuristic so far. I remember I had done tests about this and made some empirical table but I think I couldn't prove it, otherwise there should be some dust in my filesystem from the event.. ;-). $\endgroup$ Dec 27, 2020 at 21:24
  • 1
    $\begingroup$ Yes, thank you very much for your feedback. The alternative proof is based on the binary representation of odd Collatz numbers as well. It builds on a state machine (non-deterministic transducer) that models the leading three bits of odd Collatz numbers and shows that the above formulated limit holds. If you consider it interesting, we could publish it as a supplementary document to our paper $\endgroup$
    – c4ristian
    Dec 28, 2020 at 15:11
1
$\begingroup$

Visualizating non-cyclicity of eventual counterexamples of the Collatz conjecture

This is a matrix of n as a function of k = odd steps. The even numbers descend to an odd number (divided by 2) and the odd numbers jump to the left column (3n +1). It will be useful for visualizing because the cycle 1,4,2,1 is the only possible cycle. Otherwise,

$f\left ( n \right )= n$ , and this is only possible when n = 1, taking the odd n. This implies that the function takes a value from the form

$f_{0}^{k}\left ( n \right )= \frac{n\times 2^{x}}{2^{x}}$

and the even numbers of the form $n\times 2^{x}$ are the numbers where n comes from and therefore the function does not go through those numbers again. In the matrix, they are always above n and the function always moves downwards for even and to the left-up for the odd ones, looking for its corresponding pair number. It is easy to see that the function from n always leaves behind the numbers that would give rise to another cycle other than 4, 2.1. Mathematically, for now, I do not know how to express it, it’s as if the function had to do the reverse cycle for this to happen. P.D.: I do not know about your proof(correct or incorrect?) but I think it could be useful to prove the inexistence of another cycle than 1,2,4,1.

$\endgroup$
0
$\begingroup$

While the details of your "more dynamical subsequence" are different, I'm reminded of some work I've done with the result that if:

  • There exists a Collatz cycle with $\alpha$ even numbers (followed by $\frac{n}{2}$) and $\beta$ odd numbers (followed by $\frac{3n+1}{2}$).
  • The Collatz conjecture is true for all integers between 1 and $M$. (Perhaps because you've verified it with a brute-force computer program.

Then $\log_2 3 < 1 + \frac{\alpha}{\beta} < \log_2 (3 + \frac{1}{M})$

As $M$ increases, the bounds for $\frac{\alpha}{\beta}$ (a rational approximation of $\log_2{3}-1$) get tighter, and the lower bound on $\alpha + \beta$ (the number of steps in the cycle) gets higher.

The fundamental deficiency of this approach is that rational numbers are dense in the reals, meaning that no matter how tight you can make the upper bound on the inequality, there will always be some possible $\frac{\alpha}{\beta}$ reflecting some theoretically-possible Collatz cycle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .