Collatz Conjecture Remains Unproven Despite its Easy Arithmetic


Home / Collatz Conjecture Remains Unproven Despite its Easy Arithmetic

Approaches to Proving the Collatz Conjecture

Let’s keep the definitions of the functions and the series as shown earlier. The cumbersome but accurate question is ‘For any positive integer “m”, does setting a[1]=m always result in a[n]=1 where “n” is a finite integer’?

Avoid the Halting Problem

Unfortunately this question has the phrase “finite integer” in a problem about generating a series. That reminds me of the theory of computing problem called the “halting problem.” It asks whether a particular computer program, given finite input, would eventually finish a calculation or just keep going forever.

The Collatz series is very similar to a computer program that would stop when it produces the “1” result. Will this program stop?

Alan Turing had proven that, in general, one cannot write a computer program to determine whether any other arbitrary program would halt or keep running forever. I don’t know whether the program for the Collatz series would qualify as an “undecidable halting” instance.

According to Weisstein in “Collatz Problem“, it has been proven that “a natural generalization of the Collatz problem is undecidable”. That means the generalized form can neither be proven nor disproved. However, “this proof cannot be applied to the original Collatz problem”. So it is a safe bet that the “halting problem” does not cut through this Gordian knot.

Ask Another Question About the Collatz Function

Producing the “1” result in the series is the same as producing a power of two. That is because applying the Collatz function to a power of two will only invoke the “n/2″ rule until the series winds down to “1” and begins repeating.

So let’s examine “3*n + 1″ from that perspective. Certainly “3*n + 1″ always creates an even number. If the conjecture has been tested through 2^14, then there are many cases where 3*n + 1 = 2^m for some integer “m”. But there are many cases where it does not. This does not lead to a quick solution.

Can Set Theory Help with the Collatz Conjecture?

The “set version” of the Collatz conjecture could be described as: “There is a (large) set of numbers, C, to start the Collatz series that satisfy the conjecture. Is C the same as I, the set of positive integers?”

Another way of asking the same question is to define the set C’ as the initial numbers that disprove the Collatz conjecture. Is that set, C’, empty?

Does Assuming the Opposite Lead to a Contradiction?

Typically this approach would say, ‘Suppose there is a starting number, “n”, such that the Collatz series does not return to “1”. This would disprove the Collatz conjecture. The following discussion shows that this leads to a contradiction. That contradiction proves that the Collatz conjecture must be true’.

A previous article, “A Quick Explanation of Mathematical Induction“, showed how an incorrect assumption could lead to a contradictory result.

This is a terrific approach…if only we could prove that a contradiction does follow from such an assumption.

Current Status of the Collatz Conjecture

As noted, this conjecture has not yet been proven (as of June 27, 2011).  It is a live topic in mathematics, so the status could change at any time.

The Collatz Fractal Image

The Collatz series can be extended to negative integers, real numbers and complex numbers. “Pokipsy76″ created this fractal image and gives a brief description in the Wikipedia article “File:CollatzFractal.png“.

“Collatz Fractal” Image by Pokipsy76

A Quick Biography of Lothar Collatz

Lothar Collatz was born July 6, 1910 in Arnsberg, Westphalia, Germany. He studied at several German universities, gaining a doctorate with a thesis about the finite difference method applied to linear differential equations. He taught at the universities of Hanover and of Hamburg.

He wrote over two hundred papers, several important books and texts. He died in Bulgaria while attending a conference.

JOC/EFR, University of St Andrews, Scotland, “Lothar Collatz”, Nov. 2006, referenced June 26, 2011.
Esther Inglis-Arkell, io9, “The easiest math conjecture it took 74 years to prove“, published June 21, 2011, referenced June 26, 2011.
Gerhard Opfer, Hamburger Beitrage zur Angewandten Mathematik, “An analytic approach to the Collatz 3n + 1 Problem“, May 2011 (withdrawn June 17, 2011), PDF referenced June 26, 2011.
Weisstein, Eric W, MathWorld, “Collatz Problem“, referenced June 26, 2011.

Leave a Comment