The Collatz Conjecture

Question

I was discussing the Collatz Conjecture with a friend of mine who's an engineer and a physics nut, and he made an interesting point.

So I'll just assume we all know about choosing a positive integer n and then applying 3 n+1 to an odd integer and n/2 to an even integer.

My friend's point is, there is no upper limit to positive integers, so the rules for dealing with an initial n and its subsequent values become an infinite cycle, until we hit the 4-2-1 pattern that signals the end. But we know that as soon as we hit a value of n which is a power of 2, we're on track to reach that 4-2-1 cycle, because we're going to be reducing the exponent in unitary increments each time the rule is applied.

So my friend said, if the process is infinite, then the probability of reaching a value of n which is a power of 2 becomes 1; that is, it's an absolute certainty. If we're talking about an infinite process, then anything that can happen will happen; it's only a matter of time. Thus if we're definitely going to have a value for n which is a power of 2, then we're going to be able to reduce any positive integer we start with to 1, and the conjecture is proven.

There must be something logically wrong with this, because there's no way he's the first person to think of it, but I can't see what it is. I'm inclined to point out that, by the same logic, there must also be an infinite cycle of values of n which never 'land' on a power of 2.

So, my question is: is this a proof of the Collatz Conjecture? And if not, why not?

DISCLAIMER: I do not believe for one second that this is a proof of the Collatz Conjecture.

Answer 1

If we're talking about an infinite process, then anything that can happen will happen; it's only a matter of time.

This is not true. It's a common misunderstanding of infinity.

For example, there are infinitely many primes, but none of them are $2^n$ where $n > 1$ is a integer.

Answer 2

First of all, "anything that can happen will happen" is a very dubious proposition. It is true for some things, for example Markov processes, but consider a sequence of numbers generated by rolling a six-sided die and adding up the numbers rolled so far. So if the first few rolls are $3, 2, 5, 4, 4, 1,$ then the first few terms of the sequence are $3, 5, 10, 14, 18, 19.$ We can keep rolling numbers as long as we like, so this is an infinite processs; and it is certainly true that "the number $100$ will be one of the terms of the sequence" is something that can happen, but that doesn't mean it will happen.

Then again, the Collatz sequence is not random. So how can we be sure that it is possible for it to ever hit a power of two?

Answer 3

For a physicist or an engineer it is clear that probability 1 means certainty, since in the real life this is what happens. But you may tell them "let's suppose to select randomly an integer number with a uniform probability. The probability it is not 0 is 1, and the same holds for any integer. But one number will be actually chosen :-) (Ok, a mathematician would say that it is not possible to select an integer with a uniform probability: but there are other cases in which probability 1 does not mean certainty)

In general, if you look at the process 3n+5 instead of 3n-1 you will find a cycle starting with 38, even if there is a cycle 1-8-4-2-1 and therefore the same reasoning of your friends would hold. This shows that the reasoning has a fallacy somewhere :-)

Answer 4

The statement "anything that can happen will happen" is a little imprecise, particularly with respect to what "can" means. In your context, "can" is probably best translated as "Given infinite time, everything that is inevitable, will, ultimately happen."

However it does not mean; everything that is not, as yet, proven impossible, will ultimately happen. There are things which are impossible and have not yet been proven impossible. In fact there are things which are impossible and even in the full gamut of current standard theories of maths taken to their limits, we will never prove impossible.

The issue with Collatz is that any sequence which may exist, which progresses to infinity and never returns to the number $1$, may not ever be detectable, because even if we were to find it and follow it, it has no end, so there is no point we ever get to where we conclude, yes, this sequence is a counterexample.