A proof of the Collatz conjecture -- or -- another failed attempt ;)

[roupam]

A proof of the Collatz conjecture
----------------------------------

My first attempt fell short, I didnt went deep enough...
Please, feel free to reply to any errors that you can see in this
proof...
Also if you have any queries feel free to email me...

Thanks
Roupam
roupam...@vsnl.net


Statement of the problem:
-------------------------
A problem posed by L. Collatz in 1937, also called the 3x+1 mapping, 3x
+1 problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm,
Syracuse problem, Thwaites conjecture, and Ulam's problem.
Let x be an natural number. Then the Collatz conjecture states, given
that
T(x) = 3x+1 when x is odd
T(x) = x/2 when x is even
if we start iterating from any natural number x, T(T(..T(x)...)), then
the value will always reach 1 in a finite
number of steps.

The reduced function G(x)
--------------------------
We reduce the problem to
G(x) = (3x + 1)/2^k
where k is the highest power of 2 that divides 3x+1
for only odd integers x
Then the Collatz Problem becomes:
For all positive odd integers x element of Z there exists d element
of N such that
G^d(x) = 1
where G^d(x) = G(G(G(....{d times}...(G(x))... )))
When G(x) is applied to odd numbers we get
1
3 5 1 1 1 ...
5 1 1 1 1 ...
7 11 17 13 5 1 ...
9 7 11 17 13 5 1 ...

Definition of limit and some lemmas
------------------------------------
Consider the function f : Z -> Z where Z denotes the set of integers
Then we define the limit ,
lim f^n(x0) = L as n -> infinity
for every d > 0, d element of N there exists S element of Z
such that
| fn(x0) - L | < d whenever n > S, x0, n element of Z
Lemma: If the limit
lim G^n(x) as n -> infinity
exists for starting values of x = x0, x1, ... xn
and if those limits are p0, p1, ... pn
Then p0, p1, ... pn are the solutions of the equation G(x) = x
Proof: Given a function, G : Z -> Z
Consider lim G^n(x0) = p0 as n -> infinity
Then, by our definition of limit, there exists S such that whenever
n > S, then | G^n(x0) - p0 | < d for each d > 0
Consider d = 1
Then there exists S such that whenever n > S
| G^n(x0) - p0 | < 1
But | G^n(x0) - p0 | is a non-negative integer
Hence, | G^n(x0) - p0 | = 0
Hence, G^n(x0) = p0, whenever n > S
Consider, m > S, and m+1 > S, m element of Z
Then we have
G^m(x0) = p0
G^(m+1)(x0) = p0
But G^(m+1)(x0) = G(G^m(x0))
Hence, p0 = G(p0)

Solution of G(x) = x and its implications
------------------------------------------
Now we try to find all possible solutions of G(x) = x
Consider the equation, G(x) = x
In case, of the Collatz problem
G(x) = (3x + 1)/2^k
we have, the equation as,
x = (3x + 1)/2^k
where k is the highest power of 2 that divides 3x+1
Simplifying we get,
x = 1/(2^k - 3)
Keeping in mind that x is an odd integer and k is a positive
integer
Then we get, possible solutions as
k=1 x = -1
k=2 x = 1
Hence, G(x) = x, has possible integer solutions as -1, 1
Hence for all odd integers x
if G^n(x) ends in a limit as n -> infinity, the possible values of
the limits are -1, 1
But since G(x) is a reduced form of the Collatz function, we can say,
if for the Collatz function T(x), T^n(x) ends in a cycle containing
only one odd integer then, the
possible cycles are (-1,-2) (1,4,2)
From G(x) = x we get the solutions for cycles containing 1 odd
integer.
But G(x) is just a special case. We will now instead try to find
solutions for a cycle with 2 odd numbers, 3 odd numbers and so on

Note that:
----------
* Problems similar to the Collatz conjecture can also be calculated
likewise,
ie., By finding solutions of the equations G(x) = x
* (-5,-7) and similar other cyclic trajectories do not have a limit
when
(1,4,2) cycle reduces to limit (1) because we are considering only
odd integers under G(x)

Solution for generalised cases G^m(x) = x and m > 1
-------------------------------------------------------
We now will try to extend our focus to generalised functions

G(x) = (3x + 1)/2^k
where k is the highest power of 2 that divides 3x+1
for only odd integers x
G(x) denotes an operation on an odd number that generates the next
odd number in the
Collatz sequence

Now,
G^2(a) denotes the second odd number generated from a
...
G^n(a) denotes the nth odd number generated from a
If we find an odd integer solution for G^m(x) = x
Then, it will be a member of a cycle of odd numbers of length m, for
m > 1
For example:
G^2(x) = x
->> G( (3x+1)/2^k1 ) = x
->> (3((3x+1)/2^k1)+1)2^k2 = x
->> x = (3+2^k1)/(2^(k1+k2) - 9)

If we get integer solutions k1, k2 satisfying the above equations
such that we get an odd integer x
Then that odd integer represents an element of a cycle of length 2
Now we proceed to the function G^m(x)
Then it can be easily calculated that, it is equivalent to
x = Ax+B
where
A = 3^m/ 2^S(m)
B = Sum 3^i / 2^(S(m) - S(m - i - 1)) for all i = 0 to m-1
where S(i) = k1 + k2 + ... + ki and S(0) = 0
where ki is the highest power of two that divides 3G^(i-1)(x)+1
k1 is the highest power of 2 that divides 3x+1
Then, x = B/(1-A)
= ( Sum 3^i / 2^(S(m) - S(m - i - 1)) )/(1 - 3^m/ 2^S(m) ) for
all i = 0 to m-1
= ( Sum 3^i 2^S(m - i - 1))/(2^S(m) - 3^m) = P/Q (Suppose)
But now,
P = ( Sum 3^i 2^S(m - i - 1)) for all i = 0 to m-1
Q = (2^S(m) - 3^m) P,Q are both integers
P < Sum 3i 2^S(m) = 2^S(m) Sum 3i for all i = 0 to m-1
= 2^s(m)(3^m - 1)/2
= 2^(s(m)-1) ( 3^m - 1)
Therefore,
P/Q < 2^(s(m)-1) ( 3^m - 1) / (2^S(m) - 3^m) = (1/2) ( 3^m - 1)/(1
- 3^m/2^S(m))

Since P > 0, in case of positive odd solution P/Q we must have Q >
0
->> 2^S(n) > 3^n (inequality 1)

Now, for all positive integers i
ki >= 1
Hence, Sum ki >= n sum is taken over i = 1 to n
Hence, S(n) >= n
So the least value that S(n) can have is n
So in inequality 1, if we suppose that S(n) = n
We get
2^n >= 3^n
But this is not possible since, for all n >= 1
2^n < 3^n
So we can see that, for any given n
S(n) > n
Now let us suppose that the following inequality is true
S(n) >= n+1
->> 2^S(n) >= 2^(n+1)
But, we already know that
2^S(n) > 3^n

->> 2^(n+1) > 3^n
But
2^(n+1) < 3^n for all n >= 2
Hence, S(n) >= n+1 is also not valid
Lets consider
S(n) >= n + d n and d are positive integers, n >= 2
It satisfies,
2^(n+d) > 3^n for all positive integers n >= 2
then, d > n (log3/log2 - 1)
Hence least value of d would be
d = [ n (log3/log2 - 1) ] + 1
So that it satisfies,
2^S(n) > 3^n
Hence, least value of S(n) would be n + [ n (log3/log2 - 1) ] + 1
Therefore,
S(n) >= n + [ n (log3/log2 - 1) ] + 1 = [ n log3/log2 ] + 1 (Since
n is a positive integer)
->> S(n) > n log3/log2 - 1
->> 2^S(n) > (1/2)3^n
->> 1/(1 - 3^n/2^S(n)) < -1
Considering the case where S(n) takes the minimum value n+d
->> 1/(1 - 3^n/2^S(n)) takes the maximum value which is less than
-1
->> P/Q < (1/2) ( 3^m - 1)/(1 - 3^m/2^S(m)) < - (1/2) ( 3^m - 1)
->> P/Q < (1/2) (1 - 3^m) for m >= 2
->> P/Q is negative
Hence, there is contradiction
Hence, in case of the positive odd solution P/Q, no such solution
exists for m >= 2
Hence, if the maximum value of the solution of G^m(x) = x (for m >
1) is p
For positive solutions we shall have p < (1/2) (1 - 3^m)
which clearly means, no positive solution exists for m > 1
(Statement 1)
Similarly, in case of negative odd solution P/Q we must have Q < 0
->> 2^S(n) < 3^n
->> 2^S(n) < (2+1)^n
->> 2^S(n) - 2^n < nC1 2^n-1 + nC2 2^n-2 + ... + nCn-1 2 + nCn
(inequality 2)
->> 2^n(2^(s(n) - n) - 1) < nC1 2^n-1 + nC2 2^n-2 + ... + nCn-1 2 +
nCn
->> (2^(s(n) - n) - 1) < nC1 2^-1 + nC2 2^-2 + ... + nCn-1 2^1-n +
nCn 2^-n
< nC1 + nC2 + ... + nCn-1 + nCn = 2^n - 1
->> (2^(s(n)-n) - 1) < 2^n - 1
->> S(n) < 2n
Now, for all postivie integers i
ki >= 1 ->> Sum ki >= n sum is taken over i = 1 to n
Hence, S(n) >= n
Combining we get
n <= S(n) < 2n which gives us a value of S(n) for negative
solutions of G^n(x)
Hence, the maximum S(n) is limited by 2n for negative P/Q
Demonstration:
----------------
Consider the cycle (-5,-7)
-5 * 3 + 1 = -14 --> -14/2 = -7 (implies k1 = 1) --> -7 * 3 + 1 =
-20 --> -20/4 = -5 (implies k2 =2)
Hence, S(2) = k1 + k2 = 1 + 2 = 3
This holds, 2 < S(2) < 2*2=4
Similarly consider the cycle
(-17,-25,-37,-55,-41,-61,-91)
k1 = 1, k2 = 1, k3 = 1, k4 = 2, k5 = 1, k6 = 4
7 < S(7) = 10 < 2*7 = 14

For negative P/Q no such contradiction exists, as that existed for
the positive solution P/Q
In fact if we try to proceed similarly (like that in positive P/Q)
for negative P/Q
by considering the maximum value of S(n) and then trying to derive
the minimum value of
the expression P/Q, no such interesting results arise, then we get
the result
P = ( Sum 3i 2^S(m - i - 1)) for all i = 0 to m-1
Q = (2^S(m) - 3^m) P, Q are both integers
Here Q < 0
and, P/Q >= ( Sum 3^i 2^S(m - i - 1))/(1 - 3^m/2^(2n-d))
where d = [n log3/log2]

Conclusion 1:
-------------

This means, that a cycle containing at least 2 odd positive
integers
does not exist.
Or,
In other words, for the Collatz function we have, no positive number
ends in
a cycle containing more than 1 odd integer.
And, we already know from the solution of G(x) = x that
1 is that single odd integer for any cycle containing 1 odd integer
Hence, if T^d(x) ends in a cycle, it will inevitably end into the
cycle (1,4,2)

Investigating the existence of a divergent trajectory
---------------------------------------------------------
We know that
If x=x0 exists such that
lim G^n(x0) = L as n -> infinity L being a odd integer
Then L is a solution of G(x) = x
Similarly, we can find solutions for G^m(x) = x, etc.
Now if suppose we have a trajectory that continues till infinity
Then
lim G^n(x0) = infinity as n -> infinity
Then, the equation
lim G^n(x) = x has no solution as n -> infinity
We construct the equation as follows:
lim G^n(x) = x as n -> infinity
is equivalent to
x = lim (Ax + B) as n -> infinity
where
A = 3^n/ 2^S(n)
B = Sum 3^i / 2^(S(n) - S(n - i - 1)) for all i = 0 to n-1
where S(i) = k1 + k2 + ... + ki and S(0) = 0
where ki is the highest power of two that divides 3G^(i-1)(x)+1
k1 is the highest power of 2 that divides 3x+1

The solution can be written as
x = lim (B/(1-A)) as n -> infinity
Hence, x = lim ( Sum 3^i 2^S(m - i - 1))/(2^S(m) - 3^m) as n ->
infinity
Now, lim ( Sum 3^i 2^S(m - i - 1))/(2^S(m) - 3^m)
But we know already that (2^S(m) - 3^m) doesn't yield positive
numbers for m >= 2 (already derived)
Hence, lim ( Sum 3^i 2^S(m - i - 1))/(2^S(m) - 3^m) < 0
Hence, even if there exists a solution for the equation
lim G^n(x) = x as n -> infinity
The solution is not positive, which means, even if the trajectory
goes on without any end
It will go to minus infinity rather than plus infinity

Conclusion 2:
--------------
This means, divergent trajectories, or unending cycles, do not exist
for positive integers for the Collatz function.

Final Conclusion:
-----------------
Combining conclusion 1 and 2 we can say that the Collatz conjecture
is
true for all positive integers.

[roupam]

Mensanator r u reading this???

[Mensanator]

On May 17, 9:42�pm, roupam <roupam.gh...@gmail.com> wrote:
> Mensanator r u reading this???

Yes, just saw it now. I'll see what I can make of it.
Won't be tonight.

[alfansome]

I don't think this works.

Al

[roupam]

On May 19, 8:28 am, alfansome <alfans...@yahoo.com> wrote:
> I don't think this works.
>

I also know this doesnt work...
But can you please post your reasons???

[alfansome]

All I can tell you is that I "know" the underlying pattern of this
function and your attempt at a proof does not address the key elements
of the way the function exhibit regular, albeit complex and disguised
behavior.

I should have this resolved within the next 6-8 months.

al