5
$\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 \text{even})$, or just $P(C(n))$. For a random start number $P(C(n))=0.5$. (remember that $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 w.l.o.g. 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 iterations, with $3x-1$ instead of $3x+1$. As far qs it 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,\ldots\}$. 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-thanh2/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.

(B.t.w., 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.

$\endgroup$
11
  • $\begingroup$ 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. $\endgroup$ Commented Dec 30, 2011 at 4:44
  • $\begingroup$ 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). $\endgroup$
    – JJG
    Commented Dec 30, 2011 at 4:48
  • 3
    $\begingroup$ P_Q/JJG: I flagged for moderator attention. The merging of your accounts should be taken care of shortly. $\endgroup$
    – t.b.
    Commented Dec 30, 2011 at 5:02
  • 4
    $\begingroup$ 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. $\endgroup$
    – sdcvvc
    Commented Dec 30, 2011 at 5:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – user856
    Commented Dec 30, 2011 at 6:03

3 Answers 3

5
$\begingroup$

One problem with your approach is that a probabilistic argument doesn’t let you do much of anything with the statement about the behavior of all natural numbers as the Collatz rule is iterated. For example, there are infinite increasing sequences of natural numbers such that the probability that a natural number between $1$ and $n$ is among this sequence goes to $0$. But there is also another flaw in your approach, which is that you calculate $P(C^k(n))$ as if it only depended on $P(C^{k-1})$. According to your formula $$P(C^3(n)) = 1-1/2\times P(C^2(n)) = 1-1/2\times (1-1/2\times P(C(n))) = 1-1/2\times(1-1/4)=5/8$$ meaning that $P(C^3(n))$ does not depend on whether or not $C(n)$ is odd. This seems reasonable on the surface, as you would expect $\frac{3C(n)+1}{2}$ to be even just as often as it is odd (which is the assumption being made). However, this is not necessarily the case (I believe it to be false, and if it is true it certainly requires lots of justification), as the values produced by the Collatz iteration are not evenly distributed (for example, powers of two show up a lot), so we cannot use that this is true for evenly distributed $C(n)$ (note that since you are inducting, $C(n)$ may have gone through many Collatz iterations). If you are still not convinced, there is another stumbling block due to a property of the distribution of prime numbers called Chebyshev’s bias. $\frac{3C(n)+1}{2}\cong 0\bmod 2$ iff $C(n)\cong 1\bmod 4$, which requires that $C(n)$ has an even number of prime factors congruent to $3\bmod 4$. But Chebyshev’s bias indicates that more of its factors are probably congruent to $3\bmod 4$ than to $1\bmod 4$, meaning we would expect the probability that $\frac{3C(n)+1}{2}\cong 0\bmod 2$ not to conform nicely to $1/2$ (and it wouldn’t stick to one side either, but fluctuate) even if we appeal to a distribution based on factors rather than size. This is but one of the many examples of complications in the distribution of primes and factors that make any inductive statement like yours impossible to make. The sequence $C(n)\bmod 2$, $C^2(n)\bmod 2$, $\ldots$ simply gives too much information about the upcoming terms $\bmod 2$ to be ignored, yet the information is too subtle at present for us to account for.

$\endgroup$
2
  • $\begingroup$ I would like to offer a thought experiment: If you pick one thousand positive even integers randomly and do one iteration, $C(n)$ of each, then on average, half the results will be even. If you do this again $C^{2}(n)$ then 5/8 will be even, and so on. As you keep going, I think you will find that the average settles at 2/3. I don't think Chebyshev's inequality matters, as that is asking a different question. $\endgroup$
    – JJG
    Commented Dec 30, 2011 at 10:55
  • $\begingroup$ @JJG But if you randomly pick one thousand results of ten iterations of the $C$ function, the behave very very differently, which is the heart of my objection to your approach. The reason you need to consider numbers that have gone through the $C$ function many times is because you are using induction to prove your formula for $C^k$ for arbitrary $k$. $\endgroup$ Commented Dec 30, 2011 at 18:10
5
$\begingroup$

At first sight, this heuristic approach looks very similar to a “random walk argument” that has been proposed by Crandall, cf. paragraph 3 of this paper, or here for a short exposition.

$\endgroup$
1
$\begingroup$

Further, what can we do ? (of course, if your estimation of the asymptotic relative frequency of even numbers within Collatz sequence $\{ C^k(n):k \in N\}$ is valid for each $n \in N$) -This an idea why we must continue the proof: Let take any natural number $n$. Assume that we have that $$\lim_{m \to \infty}\frac{\#(\{C(n),C^2(n),\cdots, C^m(n)\}\cap 2N)} {m}=2/3.$$ Then there is a natural number $M$ such that $$\frac{\#(\{C(n),C^2(n),\cdots, C^M(n)\}\cap 2N)} {M} \approx 2/3.$$ The latter relation means that $C^M(n)$ approximately is obtained from $n$ multiplied on $(1/2)$ --${M\times (2/3)}$-times and on $(3)$-- ${M\times (1/3)}$-times, i.e. $$C^M(n)\approx n\times (1/2)^{M\times (2/3)}\times (3)^{M\times (1/3)}=n\times (1/4)^{M\times (1/3)}\times (3)^{M\times (1/3)}=n\times (3/4)^{M\times (1/3)}.$$ But this is valid for some increasing subsequence $(M_k)_{k \in N}$ which tends to infty. But $$ \lim_{k \to \infty} n\times (3/4)^{M_k\times (1/3)}=0.$$ Hence we can choose such $k_0$ that the number $n\times (3/4)^{M_k\times (1/3)}$, and correspondingly $C^{M_{k_0}}(n)$ will be in an interval $[1,A]$ for which the Collatz conjecture is checked and is valid.

$\endgroup$

You must log in to answer this question.

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