2
$\begingroup$

While trying to prove the Collatz conjecture I came across the following Lemma :

Lemma $1$ :

All variables are positive integers.

Define $Collatz(n)$ as the result of the (repeated) collatz iteration $x/2$ for even , $3x+1$ for uneven halt at $1$.

Define $Collatz2(n)$ as the result of the (repeated) iteration $x/2$ for even , $3x+3$ for uneven halt at $3$.

Lemma 1 says for each positive integer $n$ $:$ $Collatz(n) = 1 <=> Collatz2(n) = 3$

How to prove that ?

Edit : $n$ is the starting value for both $Collatz$ and $Collatz2$ , Imho its obvious but it seems it was not clear enough. $x$ is just used to describe the process of the iterations.

http://en.wikipedia.org/wiki/Collatz_conjecture

Edit : Bonus question ( not related to my attempt at proving Collatz )

On average in a race between $Collatz(n)$ and $Collatz2(n)$ which reaches its halting value( $1$ or $3$) first ( less iterations required = faster ) ?

Too clarify consider the hypothetical example :

We define $f(n) = 1$ if $Collatz$ wins the race and $= 0$ if $Collatz2$ wins the race.

Let $F(n) = f(1) + f(2) + ... + f(n)$.

Then the limit as $n$ goes to infinity of $F(n)/n$ gives for example $\pi/10$.

Edit : related question : What is known about Collatz like 3n + k?

  • 3
    Before you try to prove something, you should have some reason to think it's true. What's yours?2012-10-11
  • 0
    Intuition is not always correct. Statistically it is true. My reasons are to long and complicated to post here but lets just say both $collatz$ and $collatz2$ divide by 2 more than they multiply by 3 hence after a while they go down with speeds about $C * (3/4)^{C_2 n}$ for some $C$ and $C_2$ constants.2012-10-11
  • 0
    Let $x = 3$. Then, $Collatz(1) = 3$ and $Collatz2(1) = 3$. Counter example.2012-10-11
  • 0
    $Collatz(1)=1$ , it does not halt at $3$ and $3$ gives $1$ after a few iterations.2012-10-11
  • 0
    Then why is there an $n$? What does $n$ mean? Your notation is not at all clear. The way you write it, I take it to mean $n$ is the number of iterations, $x$ is the starting value. You are now telling me that $n$ is the starting value and $x$ is nothing??? I mean, I can't do $x/2$ if I don't have an $x$ to begin with. Tell us exactly what $n$ and $x$ mean if you want it to make sense2012-10-11
  • 0
    $Collatz(n)$ is a function of $n$ and hence $n$ is its starting value. the value of $x$ is not defined it is just to illustrate how the iteration works. Collatz(n) is just the regular wellknown collatz(n). Do you know collatz actually ?2012-10-11
  • 0
    Thanks for your comments all. I edited. Is everything clear now ?2012-10-11
  • 0
    Your notation could still be clearer, but it looks like you're saying: for all $n$, the original Collatz procedure, starting with $n$, terminates (reaches the $124$ cycle) if and only if your modified Collatz procedure, starting with the same $n$, terminates (reaches the fixed point $3$). This would obviously follow if both the Collatz *conjecture* and a modified *conjecture* were true (i.e., if both procedures always terminate), but no-one knows how to prove this. What makes you believe it's any simpler (a lemma!) to prove that every number's fate is the same for both procedures?2012-10-11
  • 1
    @mjqxxxx There is a difference. This is just saying, if one works, then both work. So, it doesn't prove that both work and thus is not guaranteed to be difficult. It's entirely possible there is a very simple proof.2012-10-11
  • 1
    @ mjqxxxx : equivalence relations and equivalent statements are very foundational in mathematics and occur often for hard intresting problems. As example it is easier to find an equivalent statement to the Riemann Hypothesis than to solve it. Also Lemma 1 as I described it , is not as hard as the Collatz conjecuture in the sense that it is a weaker statement.2012-10-11
  • 0
    @Graphth : thanks.2012-10-11
  • 0
    @Graphth: Of course I understand it's possible that there's a simple proof. The question was, what makes him think the lemma is true even if the conjectures are false? It is, in that case, a stronger statement: that both conjectures fail on the exact same values of $n$.2012-10-11
  • 0
    It is only a stronger statement if collatz is false which we believe is not. Hence we consider the possibility that it is easier. Of course we are optimistic that 'some' things can be proven related to Collatz otherwise we might not even bother to think about Collatz. As stated earlier I repeat that equivalence relations are TYPICAL in math and often has lead to first steps in proofs.2012-10-11
  • 0
    Btw it is in fact never possibly a stronger statement than collatz , since when we show it to be equivalent , it cannot be harder also. And if it is not equivalent , we have a statement of unknown strenght about Collatz2.2012-10-11

2 Answers 2

4

To explain mercio's answer in greater detail: suppose that $n$ is a number of the form $3k$; then obviously $n$ and $k$ are either both odd or both even. Now, imagine running one step of Collatz2 on $n$: if $n$ is even, then $\mathrm{Collatz2}(n) = n/2 = 3k/2 = 3(k/2) = 3\cdot\mathrm{Collatz}(k)$. Similarly, if $n$ is odd, then $\mathrm{Collatz2}(n) = 3n+3 = 3(3k)+3 = 3(3k+1) = 3\cdot\mathrm{Collatz}(k)$. This means that the sequence of Collatz2 iterates for a number $n=3k$ is exactly the sequence of 'original' Collatz iterates for $k$, multiplied by $3$.

Now, suppose that we have some odd $n$ (if $n$ is even, then obviously we can divide out all the factors of 2 and eventually get an odd starting point); then the first Collatz2 step takes us to $3n+3$ — but this is a number of the form $3k$ (with $k=n+1$), and so now everything in the first paragraph applies. This means that for $n$ odd running Collatz2($n$) is exactly like running Collatz($n+1)$ — this is why you see Collatz2($31$) converging so quickly, because it's identical to running Collatz($32$).

At heart, this means that there's nothing to be gained by studying Collatz2, but there's nothing to be lost either; it is exactly equivalent to the original Collatz problem.

One further point that bears raising, though, is your Lemma 1: 'for all positive integers $n$, $\mathrm{Collatz}(n) \Leftrightarrow \mathrm{Collatz2}(n)$'. As it's stated, this is precisely equivalent to the Collatz conjecture itself - but this is a different statement from one saying that 'Collatz($n$) is true for all positive integers $n$ if and only off Collatz2($n$) is true for all positive integers $n$'. To see why, consider replacing Collatz($n$) with '$n$ is even' and Collatz2($n$) with '$n$ is odd'; then 'all positive integers are even if and only if all positive integers are odd' is true (since both sides are false!), but 'for all positive integers $n$, $n$ is even if and only if $n$ is odd' is false. Universal quantification (the 'for all' statement) doesn't distribute over 'if and only if' in the way that you're using here.

ADDED: To see how Lemma 1 implies the Collatz conjecture, we start by breaking down into cases. (For convenience here, I'm going to abbreviate 'the Collatz sequence starting from $n$ converges' as $C(n)$ and 'the Collatz2 sequence starting from $n$ converges' as $C_2(n)$.) First, if $n$ is even, then our first step of Collatz takes us to $n/2$, and so (almost trivially) $C(n)\Leftrightarrow C(n/2)$, and in particular $C(n/2)\Rightarrow C(n)$. On the other hand, if $n$ is odd, then we use our lemma: we know that $C_2(n)\Leftrightarrow C(n+1)$ by the equivalence shown above, and the lemma states that $C(n)\Leftrightarrow C_2(n)$; putting the two together, we get $C(n)\Leftrightarrow C(n+1)$. But since $n+1$ is even (because we're looking at the $n$ odd case), $C(n+1)\Leftrightarrow C((n+1)/2)$, so we have the equivalency $C(n)\Leftrightarrow C((n+1)/2)$ and in particular $C((n+1)/2)\Rightarrow C(n)$. Now we can induct, using the strong induction principle: suppose we have $\forall k\lt n C(k)$. Then by specializing we have (either) $C(n/2)$ or $C((n+1)/2)$; therefore $C(n)$ by (one of) the two implications we proved. Therefore, $(\forall k\lt n C(k))\Rightarrow C(n)$, and since we know $C(1)$ we get $\forall n C(n)$.

  • 0
    Thanks for the answer Steven. But I did miss your 'further point' ..2012-10-11
  • 0
    The statement $\forall{n}C_1(n) \equiv \forall{n}C_2(n)$ is true (as shown here). It is weaker than @mick's original lemma: $\forall{n}(C_1(n)\equiv C_2(n))$. That lemma is true if the Collatz conjecture is true, but the converse isn't obvious.2012-10-11
  • 0
    @ mjqxxx and Steven : Thanks got it.2012-10-11
  • 0
    @mjqxxxx I was thinking about expanding this answer with a proof of that converse, actually, showing that the lemma implies the Collatz conjecture - it sounds like it would be worthwhile.2012-10-11
  • 0
    @StevenStadnicki: If the lemma is equivalent to the Collatz conjecture, then that is worth proving (as it doesn't seem obvious). Is it (equivalent, and/or obvious)?2012-10-11
  • 0
    @mjqxxxx See the revision above.2012-10-11
  • 0
    Steven last add seems correct. Though I think it can be stated more clearly. Or I need more practice :)2012-10-11
  • 0
    I note that the following appears and appeals to me C2(6n+3) => C(2n+1) [division by 3] => C(6n+4) [3x+1] => C(3n+2) [division by 2] But also C2(6n+3) => C(6n+4) [C2(n)->C(n+1)] => C(3n+2) So we have 2 ways of obtaining C(3n+2). Also its intresting in reverse order. And it is as if we have free choice in our reductions. ( an Or rule ! ) This has implications on Collatz in reverse to ( building the integers ). (C2(6n+3) => C(3n+2)) => for odd n (C2(18n+12) => C(9n+7)) => (C2(9n+6)=>C(9n+7)) But <=> C(3n+2) (by /3 or above or reverse C) Fascinating. It even smells like infinite descent ! :).2012-10-12
  • 0
    @Steven : Besides I did not get the k argument you made however by C(n) <=> C(n/2) or C(n+1/2) Id say we get simple infinite descent to C(f) (or C2(f) ) with f<33 and hence the proof is complete.2012-10-12
  • 0
    Call me crazy but Im thinking about 3n+5. If we can relate 3n+5 with 3n+3 or 3n+1 that would be very intresting and promising imho. ( infinite descent ideas )2012-10-12
  • 0
    As another idea : I think it might be possible to prove a minimal gap between counterexamples to collatz ...2012-10-12
  • 0
    followup : the idea about 3n+5 is quite gone because it has to many cycles. (3n+7 is intresting too , but I see no connection). I had a talk about this with a friend (known as tommy1729) and he increased my understanding of collatz dramaticly. We are even thinking about having a proof although the odds are low and we are carefull with such claims. In all cases it seems we have gone beyond the simple statistical argument. I do not know if other people know ' accelerators ' to compute collatz but thats what Tommy might have and again that smells like infinite descent. Thanks for your help here !2012-10-18
5

If $n$ is odd, then $3n+3$ is a multiple of $3$, and if $n$ is an even multiple of $3$, $n/2$ is still a multiple of $3$. So unless you happen to pick a number where every term in the sequence is even (which can only happen with $n=0$ but then $n$ is a multiple of $3$ too), you will eventually end up with a sequence containing only multiples of $3$.
And if you look closely, for $n$ even, $3n$ is sent to $3(n/2)$ and for $n$ odd, $3n$ is sent to $3(3n+1)$ so your sequence from $3n$ is simply the normal Collatz sequence starting from $n$ but multiplied by $3$.

You can think of the Collatz2 sequences as Collatz sequences that are allowed to start from numbers of the form $n/3$. Then those sequence always end up being sequences of integers, i.e. regular Collatz sequences (and conjecturally end up at $1$). There is no new branch in the Collatz graph if you add all the $n/3$ numbers.

  • 0
    Im sorry but I think I misunderstood or disagree. Let $n$ be 31. Then Collatz iteration of 31 goes up to 890 and takes many steps to arrive at 1 whereas Collatz 2 goes to 3 rapidly without taking high values. The ratio of 3 seems to small : inconsistant with iteration length and values.2012-10-11
  • 0
    A better example $n$ = 25. For collatz we *multiplied by 3* 7 times before we reached 1. But for collatz2 we *multiplied by 3* only 3 times before we reached 3. 3 and 7 are relatively prime so I do not see such a simple connection. Certainly not some sort of 3 ratio ?2012-10-11
  • 0
    The same problem occurs when we divide by 2 and count that.2012-10-11
  • 0
    @mick I think you misunderstand mercio's point. It is not that you use the _same_ $n$; it's that there is an _isomorphism_ between the two problems - that is to say, for every $n$ there is an $m$ such that starting the Collatz2 sequence at $n$ is equivalent to starting the Collatz sequence at $m$. If you start with $n=31$, then your $m=32$; that is, running Collatz2 from $n=31$ is equivalent to running 'original' Collatz from $m=32$.2012-10-11
  • 0
    So if Collatz is _true_ then your conjecture is true: 'for all $n$, Collatz($n$) converges' is true, so 'for all $m$, Collatz2($m$) converges' is also true, and so the equivalence 'for all $n$, Collatz($n$) converges iff Collatz2($n$) converges' is correct because both sides are simply true.2012-10-11
  • 0
    @mercio Typo: you meant to say $3n$ is sent to $3(3n+1)$.2012-10-11
  • 0
    @ Sean : Yes you're right, thanks.2012-10-11
  • 0
    @ mick : The collatz sequence for n behaves the same as the collatz2 sequence for 3n : the collatz sequence from 25 does 25, 76, 38, 19, 58, etc. the collatz2 sequence from 3*25 does 3*25, 3*76, 3*38, 3*19, 3*58, etc.2012-10-11