6
$\begingroup$

A long time ago I was messing around with the Collatz problem and I stumbled across a "proof" that the iterations will converge. I was too embarrassed to show anyone, and I recently just remembered it. So I will put a sketch of it here and I want to know where it falls down. Define $C(n)$ as one iteration of the Collatz function on a positive integer $n$. Assume we start at a random positive even integer $n$. Define the probability that $C(n)$ is even by $P(C(n)\in Even)$, or just $P(C(n))$. For a random start number $P(C(n))=0.5$. (remember n is even)

But $P(C^{2}(n))=1/2\times P((C(n))+ (1-P(C(n)))$. (By simple probability tree)

And so on, in general $P(C^{k}(n))=1/2\times P(C^{k-1}(n))+(1-P(C^{k-1}(n)))$ $=1-1/2\times P(C^{k-1}(n))$ Which gives us a geometric progression (with multiple -1/2) as we work our way back into terms of $P(C(n))$.

As $k \to \infty $, $P(C^{k}(n))\to \frac{1}{1-(-1/2)}=2/3$.

So what? Well, this implies that as k gets bigger our iterations will settle down to something like an even,even,odd cycle (2/3 are even). Assume that on k iterations of the Collatz function, we end up at a larger number than our initial number. This implies (assuming WLOG we have an even number, x) $3\times \frac{x}{4}+1$ is greater than $x$. Or, $x<4$. But we have checked for all numbers less than four and the Collatz function converges, so there is no number that will diverge.

I know this is a very sketchy sketch of a "proof". I just want to know what you think. If it is nonsense please say so.

Edit: I also tried a different Collatz style iteration, with $3x-1$ instead of $3x+1$. As is observable this doesn't seem to converge. Using the same arguments as my original question, we can see why. $3\times \frac{x}{4}-1$ is greater than $x$ when $x<-4$.

I also tried similar other changes using $3x+a$ for $a\in {3,5,7,...}$. If the iterations converge for all integers less than $4\times a$ then it is convergent for all (assuming my "proof" makes sense)

Second Edit: I want to reply to some issues raised. Bare in mind this is not a formal proof, it's just an idea of a way of making a proof.

On the objection that, just because on average the iterations will yield a 2/3 chance of an even number, there may in fact be sequences that do not reduce to an even-even-odd sequence:

If a particular sequence doesn't end in a 2/3 chance of an even number, and in fact it contains more odd numbers, then (now I'm not sure how to say this mathematically) that sequence is as dense in the integers as the sequences that cycle to 1-4-2, as for any even number in the sequence there is an infinite number of even numbers that also join this sequence (i.e. just double any even number in the sequence again and again...).

Therefore since the average sequence ends in a 2/3 chance of an even number after $k\to \infty$ iterations, there must be a sequence that has a higher than 2/3 chance of yielding an even number. I cannot prove it yet but I think, just on considering it, that such a sequence cannot exist, because:

  • as the sequence progresses the numbers would get smaller and smaller (e.g. if the prob of an even number is 3/4 then we can consider a even-even-even-odd sequence, which is the same as a even-even-odd sequence but with an extra division by two, so it would necessarily be smaller than the starting number. Meaning (a) it couldn't cycle (b) it couldn't diverge to infinity. i.e. it is impossible.

(BTW the above type of proof I'm trying to make is based on a type of proof I forget the name of - if the average of something is x, but you can find something with a value less than x, then there must exist an object with a value greater than x.)

On the objection that I am abusing the term probability and that this is akin to saying "there are no primes, because as we get to bigger and bigger numbers the probability of a certain number being prime approaches zero:

I think that, although I haven't defined how I'm using probability axioms, I think saying $C(n)$ can either be even or odd, and given an arbitrary $n$ it is possible to talk about the probability of it being even. If $C(n)$ is even, then $C(n+2)$ is odd so it doesn't matter where you are in the integers, the probability is always 1/2. I'm not sure why this is controversial.

  • 0
    Two problems I see right off the bat: 1. The probability that $C^k(n)$ depends on $C^{k-1}(n)$ in a more complicated manner then simply on whether $C^{k-1}(n)$ is even or not. 2. Just because the probability that any given number will not enter some cycle other than 4-2-1 or diverge is low doesn't mean that no number will.2011-12-30
  • 0
    Thanks for the reply. (1) I dont think it does depend on anything more complicated. Assume arbitrary positive integer n. Draw a probability tree for yourself. SInce no other information about n is known, we don't need to consider anything else. I'll have a think about (2).2011-12-30
  • 0
    Looks like an original approach. But not sure whether probability helps us out in making claims like "so there is no number that will diverge".2011-12-30
  • 0
    BTW I am P_Q, my accounts need to be merged...2011-12-30
  • 0
    @Roupam Ghosh - yes the last few lines were a bit of a fudge. When I wrote this out properly years ago I had a slightly stronger way of arguing it. I've forgotten it though...2011-12-30
  • 0
    @JJG The thing is, if we look at the sequence $C^1(n),\ldots,C^{k-1}(n)$ which **is** known by the time we reach $C^k(n)$ we get much more information about $n$, and the probability that $C^k(n)$ is even depends very much on these prior values. For example, if we see that the sequence was alternately odd and even (or odd all the way if you use the reduced version where $n\to (3n+1)/2$ rather than $n\to 3n+1$ for odd $n$) we have learned something about the divisors of $n$, though what exactly is a very complicated question and is one of the primary difficulties in approaching this problem.2011-12-30
  • 3
    P_Q/JJG: I flagged for moderator attention. The merging of your accounts should be taken care of shortly.2011-12-30
  • 0
    @Roupam Ghosh. We only need assume $n$ is even. All possible paths (e.g. even, odd, even,even,even,odd...) are accounted for when caclulating the probability that $C^{k}(n)$ is even.2011-12-30
  • 0
    @Alex Becker I don't think the probability $C^{k}(n)$ is even depends on anything other than the fact that $n$ is even (and positive). The probability tree takes into account all possible paths the Collatz iterations have on $n$, so the probability is just the sum of all paths that end in a positive number, which can be found with a geometric sum.2011-12-30
  • 4
    When you're saying "probability" of an even number is $\frac{1}{2}$, in the same spirit the "probability" of a prime number is 0 (they occur less and less often), and yet there are _infinitely many_ prime numbers. In other words, low "probability" does not mean much. To talk about real probability, you need to define it with [probability axioms](http://en.wikipedia.org/wiki/Probability_axioms).2011-12-30
  • 1
    sdcvvc is right on point. What you have shown by $P(C^k(n)) \to 2/3$ is that, if you apply Collatz iterations to the whole ensemble of all $n \in \mathbb N$, eventually 2/3rds of all $n$ will map to even numbers. This is very different from the proposition that, for any *particular* $n$, 2/3rds of its Collatz orbit will consist of even numbers. For example, if exactly one $n$ diverged to infinity and all others eventually converged to the $1, 4, 2$ loop, your proposition would be valid but the Collatz conjecture would be false.2011-12-30

3 Answers 3