# What does proving the Collatz Conjecture entail?

From the get go: i'm not trying to prove the Collatz Conjecture where hundreds of smarter people have failed. I'm just curious.

I'm wondering where one would have to start in proving the Collatz Conjecture. That is, based on the nature of the problem, what's the starting point for attempting to prove it? I know that it can be represented in many forms as an equation(that you'd have to recurse over): \begin{align*} f(x) &= \left\{ \begin{array}{ll} n/2 &\text{if }n=0\bmod2 \\ 3n+1 &\text{if }n=1 \bmod2 \end{array} \right.\\ \strut\\ a_i&= \left\{ \begin{array}{ll} n &\text{if }n =0\\ f(a_i-1)&\text{if }n>0 \end{array} \right.\\ \strut\\ a_i&=\frac{1}{2}a_{i-1} - \frac{1}{4}(5a_{i-1} + 2)((-1)^{a_i-1} - 1) \end{align*} Can you just take the equation and go from there?

Other ways I thought of would be attempting to prove for only odd or even numbers, or trying to find an equation that matches the graph of a number vs. its "Collatz length"

I'm sure there's other ways; but I'm just trying to understand what, essentially, proving this conjecture would entail and where it would begin.

-
You have to prove that if you start interating $f$, starting with any positive integer at all, you'll at some point get to $1$. What part of this do you not understand? – Chris Eagle Mar 23 '12 at 1:58
@ChrisEagle I get that, in theory. What I don't get is what that means technically/practically/mathematically. Or does the fact that we can't prove mean that we can't understand where we might start? – Thomas Shields Mar 23 '12 at 2:00
@ThomasShields It means, mathematically, that "if you start interating f, starting with any positive integer at all, you'll at some point get to 1". This is a perfectly mathematical statement. – Alex Becker Mar 23 '12 at 2:04
Sorry, was too quick on the close trigger! – Aryabhata Mar 23 '12 at 2:09
@ThomasShields Lots of different approaches have been tried. AFAIK, there is no agreement as to "where to start". If we knew that, it wouldn't be such a hard problem. – Alex Becker Mar 23 '12 at 2:11

Proving this conjecture indirectly would entail two things:

1. Proving that there is no number n which increases indefinitely

2. Proving there is no number n which loops indefinitely (besides the 4, 2, 1) loop

If one does these things then you have an answer to the collatz conjecture (and if you find a case of either of these things you have disproven the collatz conjecture obviously)

Of course this is just one approach that comes to mind, there are other possible methods which are beyond my own knowledge

-
this is pretty much what I was looking for - so, until/unless someone comes along with a better answer, check-mark for you :) – Thomas Shields Mar 23 '12 at 4:10

The way I interpret the problem is

For there not being cycles:

That Collatz (What else? Important question) iterations change the prime factors of some arbitrary number such that future (Collatz) iterations of that number can never return to the original, or any preceding, set of prime factors. In essence, that prime factors, through at least these specific functions, get "mangled beyond return." Or that the only path to a previous set of prime factors is by inverting your previous operations, though this is probably too strong.

For no diverging numbers:

The aforementioned set of prime factors converges to a set of solely {2^n}, and thus to the empty set.

-

Adding to @Adam B.'s answer: examinig the conditions of possible cycles leads to the relations of powers of 3 and powers of 2, focusing on problems which are still not solved either.

One can look at it in terms of approximation : what is the smallest difference between perfect powers of 3 and perfect powers of 2, relative to the magnitude of one of them or of the rational approximation of log(3)/log(2) where we find an unsolved detail in the Waring-problem (see mathworld, "power fractional parts"). Some first steps to the proof of nonexistence of cycles (in the positive integers, in the negative integers we have at least 3 additional cycles) were provided by Ray Steiner 1996 and later by John Simons and Benne de Weger who proved the nonexistence of a certain type of cycles using that rational approximation approach.

Or one can look at the problem of cycles in terms of modular conditions, and arrive at other unsolved properties of the relation of powers of 3 to powers of 2. There is, for instance, the formulation in terms of "z-numbers" done by Kurt Mahler.

Unfortunately, even if that 3/2-problems were solved, that would not mean that the Collatz-problem was also solved and vice versa; for instance the solution of the Waring-problem-detail would only solve the "1-cycle" problem but not the general "m-cycle" problem with m bigger than roughly 70 (using the notation of Simons/De Weger): the mentioned conditions are not including each other. (The Steiner/Simons/De Weger articles are linked in the wikipedia, a more basic, amateurish article of mine adressing these aspects a bit less cryptic can be found here )

-
Imho a very good answer but probably to complex for the OP - with respect -. – mick Sep 10 '13 at 21:17

The problem can be just those two points:

1) is there a loop? 2) is there a sequence that increases without bound?

However, another way to solve it would be to show there cannot be two distinct < families >. Up to quite high values of n, we know empirically that starting with any given n less than that value, repeatedly choosing n/2 for even n and 3n+1 for odd n gives a sequence ending in 1.

Call this set of sequences ending in 1 the < terminate-in-1 family >.

The task then amounts to testing if there can be a < deviant family > where either a loop or a sequence increasing without bound would amount to a deviant family. Then the challenge (in order to prove Collatz/Ulam/Thwaites correct) is to show that any other family of sequences must somewhere produce a number that is within the terminate-in-1 family.

The terminate-in-1 family contains, and if it existed any deviant family would contain, infinitely many natural numbers each.

-

My way of looking at collatz problem involved the following facts: 1. find whether 1-4-2-1 could be the only cycle. I tried researching with negative integers and hence found 4 such cycles and one amongst them was valid for positive integers 2. find whether the iterates upstream is bounded or not. i.e similar to all integers upon iteration coalesce to 1, can we find inverse collatz operations, which leads to a bounded integer(seed integer) not necessarily one number. thus proving the sequence of iterates are bounded. I was able to get this also 3. ultimately prove that all integers that form the seeds for iterates follow only one cycle.

I was able to do all these, but still my proof is not accepted. spend nearly 5 years in conceptualizing and arriving at a proof.

-