Criticism of proof attempt: Collatz Conjecture

Question

I'm going to start out by saying I'm an amateur, I'm sure I missed something. I know there are lots of people who claim to have solved this. I just want to find out where I'm wrong and what I missed. There's been far more brilliant minds that have worked on this than me. That said, I've tried to write out as formal a proof as I can. It's 9 pages long. I'll link it here, I've saved it on my github.

To summarize it though. I start out by building a function that can give us some odd number down from a starting odd number. That equation is given by.

$$O_{1+m} = \frac{ 3^{m}O_{1}}{2^{p_{1} + p_{2} + \dots + p_{m-2} + p_{m-1} + p_{m}}} + \frac{ 3^{m-1}}{2^{p_{1} + p_{2} + \dots + p_{m-2} + p_{m-1} + p_{m}}} + \frac{ 3^{m-2}}{2^{p_{2} + \dots + p_{m-2} + p_{m-1} + p_{m}}} + ... + \frac{3^{1}}{2^{p_{m-1} + p_{m}}} + \frac{3^{0}}{2^{p_{m}}} $$

Where $O_{1+m}$ is the odd number m odd numbers out from where we started. $O_1$ is the odd number we start at. and $p_{i}$ is the number of times a number will have to be divided by two. For example, consider

$$7 \rightarrow 22 \rightarrow 11 \rightarrow 32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$

Then our starting odd number, $O_1$ is $7$, our second odd number $O_2$ is $11$, the number of times we had to divide by two to get from $7$ to $11$ is once, so $p_1 = 1$. The third odd number is $1$ so $O_3 = 1$, because we had to go through $11$ to get there and the number of times we had to divide from $11$ to get to $1$ is $4$, therefore $p_1 = 1, p_2 = 4$.

I then showed that we have three cases, the number increases indefinitely, it loops, or it decreases.

Case 1: Indefinitely Increasing

I showed that the only way we could have the number increase indefinitely from one odd number to some odd number down the line and then some odd number after that, is if our starting odd number $O_1$ is negative. But $O_1 \geq 1$, therefore there are no indefinitely increasing numbers.

Case 2: Looping Numbers

I showed that we can construct an equation which will give us our starting odd number after m transformations. That equation is given by.

$$O_{1+m} = \frac{3^{m-1}2^{0} + 3^{m-2}2^{p_{1}} + ... + 3^{1}2^{p_{1} + p_{2} + \dots + p_{m-2}} + {3^{0}2^{p_{1} + p_{2} + \dots + p_{m-2} + p_{m-1}}}}{(2^{p_{1} + p_{2} + \dots + p_{m-1} + p_{m}} - 3^{m})}$$

I then used prime decomposition and the fundamental theorem of algebra to show that $O_{1+m} = 1$ and $p_{i} = 2$ for all $i$. Therefore the only looping number is $1$.

Case 3: Decreasing numbers

This follows from case 2. Because $1$ is the only looping number and it's also the smallest usable number, any number which consistently decreases over $m$ transformations, must eventually end up at $1$, where it loops indefinitely.

Therefore the Collatz Conjecture is true. Every number will inevitably transform down to $1$.

Sorry for the difficult to read LaTeX, kind of a new user, but feel free to criticize away about anything! And thanks all for everyone's help.

Answer 1

Using the more general iterate $mx + a$, where $m,a$ are odd positive integers ($3x+1$ is the classic Collatz iterate), the next odd integer $x_i$ is given by $$x_i = \frac{mx_{i-1}+a}{2^{p_i}}$$ where $p_i$ is the unique positive integer such that $x_i$ is odd. Note that I am using $x_i$ instead of $O_i$ and that the $i$ index of the $p_i$ matches the index of the next odd integer and not the current odd integer. This makes things cleaner IMHO. If we define $P_i = \sum\limits_{k=1}^{i}p_k$ for $i\gt0$ and $P_0 = 0$ then we obtain the equation: $$x_n = {x_0 m^n + a \sum\limits_{i=0}^{n-1} m^{i}2^{P_{n - 1 - i}} \over 2^{P_n}}$$ Note that the sum can be written two ways: $$\sum\limits_{i=0}^{n-1} m^{i}2^{P_{n - 1 - i}} = \sum\limits_{i=0}^{n-1} m^{n - 1 - i}2^{P_{i}}$$ This is the equation you obtained with $m=3$ and $a=1$. A loop of length $n$ occurs when $x_n = x_0$ which gives the loop condition: $$x_0 = {a \sum\limits_{i=0}^{n-1} m^i 2^{P_{n-1-i}} \over {2^{P_n} - m^n}}$$ A loop occurs whenever there exist an $n$ and $p_i$ and hence $P_i$ such that the denominator divides the numerator. See Böhm and Sontacchi: https://mathscinet.ams.org/mathscinet-getitem?mr=551509 For $3x+1$ a sequence starting at $1$ has $p_i = 2$ so $P_i = 2i$ which gives a numerator: $$\sum\limits_{i=0}^{n-1}3^{n-1-i}2^{2i} = 2^{2n} - 3^n$$ which is equal to the denominator so $x_0 = 1$. So are there any other $n$ and $p_i$ and hence $P_i$ where the numerator is divisible by the denominator? So far not for $3x+1$ but definitely yes for $mx+a$ in general. For example $3x+5$ has several loops. $a \gt 1$ can supply some factors to help with the divisibility. I need to read your paper more carefully to comment further. Thought it might help to show you some better (IMHO) notation. You may also want to consult https://terrytao.wordpress.com/2011/08/25/the-collatz-conjecture-littlewood-offord-theory-and-powers-of-2-and-3/

Answer 2

May I first commend you on your approach. You wrote down a rather legible proof and then sought out criticism with an open mind. That's how it should be done.

Unfortunately, and as you probably feared, the proof doesn't seem to work. First, note that, if you are trying to prove there are no looping numbers except $1$, you must use the positivity of the starting number somewhere, because $-5$ also loops. I don't see, at first glance, where you use that, so that is a warning sign.

I immediately skipped to section 4 in your paper because, as you say yourself, that's where the meat of the matter is. Your jump from equation 27 to 28 & 29 seems dubious. Why can $1+3O_{3}$ and $2^{p_{2}}O_{3}-1$ not have some prime factors in common? In this case, you can probably still prove that that's impossible with some simple calculations, but when you make the analogous jump from 37 to 38 & 39, this becomes very much non-trivial.

Answer 3

I believe there is a problem in (14)-(15). Firstly I don't understand how the equation (14) holds. What do you mean by plugging in $_2O$ for $_1O$ ? The only equations you have so far are
$$ _iO = A_iO_1 + B_i$$ and I don't see how this enables you to deduce that equation 14 holds. When reading what you wrote it looks like you think that the following equality is true for all $m$ $$ _{m+1}O = {_n}O A_n + B_n$$ but you haven't proven this (and I don't believe that this equality actually holds). and even if it did hold it is not immediately clear that $(15)$ is correct. The statement "doing the same up to infinity" is vague. You can however do the procedure $m$ times $$O_1 = \underbrace{\text{negative terms}}_{:= N_m} + \frac{{_mO}}{A_1...A_m} $$
and take the limit for $m \to\infty$. However it does not look easy to show that the right hand side would converge to something negative since the term $\frac{{_mO}}{A_1...A_m}$ is positive with $_mO$ diverging to $+\infty$.

---

And important thing to note is that you in your proof of "Case 1 : odd numbers that transform up forever" you never use the hypothesis that the sequence $_1O,...,{_mO}$ is transforming up forever. That is suspicious and should lead you to believe that you've made a mistake somewhere.

Answer 4

I agree that some of the assumptions used in your algebra should be revisited, particularly the observation of Eric Shumard. I would also make a couple of observations and maybe suggest some simplifying assumptions.

If you look closely at the numerator of the equation contained in your paragraph for Case 2, you will note that its value depends only on the number of elements in the loop and the sequence of consecutive divisions by 2 that are encountered in traversing the loop. The number of multiplications by 3 and additions of 1 is equal to the number of elements in the loop. The values of these elements are limited by how many of them there are. So, for example, the maximum starting value for a loop with 3 elements is 3. The maximum value for the smallest element in a loop with four elements is 1; for a loop with five elements that value is 23. As the smallest possible value encountered in the loop increases, the number of elements must also increase. Obviously, there are no loops with 3, 4, or 5 odd elements. If we are talking loops containing odd elements with values on the order of 10⁷, there are going to be a whole lot of elements in those loops.

Here is a suggestion for a simplifying assumption: just consider the odd elements of the loop. Consider that there must be a smallest such element and take this as your O₁. If you do this, you will see that the second term of the numerator will be 3^m-12-- the exponent on the 2 will be 1.

Next, you might notice that the above-referenced numerator will always have the form 6X+1 or 6X+5, but the numerator can never be a prime number. No odd elements of a loop can be a multiple of 3. You can demonstrate this using mod6 arithmetic. Also, the O₂ will always be congruent to 5mod6, regardless of what the value of O₁ is. Any odd number that results from 3 times the previous number plus 1 divided by 2 will also be congruent to 5mod6.

A simpler problem that may give some insight is to prove that there are no loops with intermediate additional divisions by 2; i.e. every odd element is 3 times the previous element plus 1 divided by two until the last operation results a series of divisions by two that arrives back at the starting number. In this case, the numerator referred to above simplifies to

3^m - 2^m,

which is = 3^m-1 + 3^m-2(2) + 3^m-3(2)²...+(2)^m-1. (Proof: multiply the latter equation by 1, in the form (3-2). Multiply out and collect terms with like powers of 2. All will cancel except 3^m - 2^m.)

If you can find an m and p such that (3^m - 2^m)/(2^p - 3^m) = Integer, you will have disproven the non-existence of loops in the Collatz conjecture, beyond the trivial case, m = 1 and p = 2. The integer will be the value of the smallest odd element of a loop, and the loop will contain m odd elements, such that O₁ < O₂ < ...< O_m-1 < O_m.

If you really want to get off into the weeds, you can note that as the number of iterations increases, the ratio of the divisions by 2, p to the number of multiplications by 3, m approaches ln3/ln2. These can get very large for example p = 125743 and m = 79335.

Note that this describes a loop with 79335 elements, none of which can be a multiple of 3, and 79335 numerators none of which can be a prime number. Nonetheless, the maximum value of the smallest elements will only be on the order of 3¹⁴, or about 5 to 10 million. This is because of the rate that differences between powers of 2 and powers of 3 increase. One thing I have not considered is whether, for any number x such that 2^m - 3ⁿ = x, there is only one pair m and n that satisfy the equation.

Edit to add some additional observations:

1.) It is possible to derive an infinite number of sequences that produce loops containing an arbitrary number of elements. For any numbers n and m if we let D=(2^m-3ⁿ), then replace 1 in the 3x + 1 problem with D, this will produce a loop starting at a value of 3ⁿ-2ⁿ and will contain n odd integers. For example, if n=5 and m=8; D=13 and so 3x + 13 will produce a loop beginning at 3⁵-2⁵=211 :

211, 323, 491, 743, 1121, 211.

Because of the way the number b is calculated, we can add terms in the sequence that produces b to derive other values that loop under the same rules: 227, 251, 283, 323, 331. Note that the differences between these numbers are all multiples of 8.

This process is a sufficient condition to produce loops using linear operations, but I cannot prove that it is necessary. However it is interesting to note that this approach cannot produce a non-trivial loop under the conditions of the Collatz conjecture because the only numbers m and n that satisfy the equation 2^m – 3ⁿ = 1 are m=2 and n =1, according to the Catalan conjecture.

2.) There are restrictions on the values that the smallest element of a loop can have; obviously it cannot be even. It cannot be a multiple of 3. It cannot be any number of the form 4x+1, because any 3x + 1 for such a number will require 2 consecutive divisions by two. There are other forms of numbers that would violate the condition that the number chosen be the smallest number in the loop: numbers of the form 16x + 3; 32x + 23; 24x +5, etc. All numbers of this form eventually produce an odd number smaller than the starting number.

3.) The numerator containing the 3^m-1 + 3^m-2(2) +... will always be of the form 3^m -2^m + 2^dN, where N is some integer, for any starting number in the loop. If we look at the binary representation of the number, d is the number of right-most consecutive 1s in the binary representation minus 1. N is bounded by m somehow, but I have not tried to work out how. It looks hard.

4.) Whether the number, the numerator associated with that number, and the denominator are congruent to 1 mod 6 or 5 mod 6 depends on whether the number of elements is even or odd, and on whether the power of the last term in the numerator is even or odd. EDIT: There is an error. It is not the number of elements that are even or odd that determines whether the denominator is congruent to 1 mod 6 or 5 mod 6, it is the total number of times one would divide by two in traversing the loop.

5.) You can prove by brute force that there are no loops with any starting value that contain a particular number of elements. For example, the only permissible numerators that one may obtain for a loop with 3 elements is 19 (3³ - 2³) or 23 (the previously obtained 19 + 2^3-1). Both of these are prime numbers, so there are no loops with 3 elements. We can use the same process to prove that there are no loops with 4 elements, etc. I do not know if the process is generalizable, for example by induction.

Those are my observations anyway. Thanks for posting and good luck.