Some mathematical problems are easy to describe but turn out to be
notoriously difficult to solve. In some instances, these difficulties may stem
from fundamental issues of provability, especially for mathematical problems apparently poised
between order and chaos.
In a provocative article titled "On
Unsettleable Arithmetical Problems," John H.
Conway (Princeton University) offers some remarkably simple assertions that
are true yet are neither provable nor disprovable. The article appears in the March 2013 American Mathematical Monthly.
"It is usually thought that they must necessarily be complicated," Conway
writes, but "these wild beasts may be just around the corner."
Conway bases his examples on the infamous Collatz 3n + 1 problem, which concerns a
sequence of positive integers.
Start with any positive integer n.
If n is even,
divide it by 2 to give n' = n/2.
If n is odd, multiply it by 3 and add 1 to give n' = 3n + 1.
If n is odd, multiply it by 3 and add 1 to give n' = 3n + 1.
For example, starting with 5, you get the following sequence: 5, 16, 8,
4, 2, 1, 4, 2, 1,. . .
Starting with 11, you get the sequence: 11, 34, 17, 52, 26, 13, 40, 20,
10, 5, 16, 8, 4, 2, 1, 4, 2, 1,. . .
The numbers generated by these rules are sometimes called
"hailstone numbers" because their values fluctuate wildly (as if
suspended in turbulent air) before they finally crash (to the ground) as the
repeating string 4, 2, 1.
Computational experiments suggest that such a sequence will always
eventually crash. However, for some starting integers, it takes a huge number
of steps to reach the repeating cycle.
Will you always end up in a repeating cycle? No one has yet
found a counterexample. Computations
by Tomás Oliveira e Silva have verified that no such counterexample can start
with an integer less than at least 5 x 1018.
Jeffrey C. Lagarias
(University of Michigan) has categorized the 3n + 1 problem and its ilk as tantalizing but dangerous, luring
mathematicians into weeks, if not years, of futile labor.
In his paper, Conway shows how simple assertions inspired by the
Collatz problem cannot be settled—neither proved nor disproved.
Then, in an intriguing postscript, Conway presents an argument that has
convinced him that the Collatz
conjecture is itself very likely to be unsettleable, rather than, as he
originally thought, having just a slight chance of being unsettleable. He uses
the fact that there are arbitrarily tall "mountains" in the graph of the Collatz
game.
"I don't want readers to take these words on trust but rather to
encourage those who don't find them convincing to try even harder to prove the
Collatz Conjecture!" Conway wryly concludes.
References:
Conway, J.H. 2013. On
unsettleable arithmetical problems. American
Mathematical Monthly 120(March):192-198.
Lagarias, J.C., editor. 2010. The Ultimate Challenge:
The 3x + 1 Problem. American Mathematical Society.
______. 1986. The
3x + 1 problem and its
generalizations. American
Mathematical Monthly 92(January):3-23.
Oliveira e Silva, T. 2010. Empirical verification of the 3x + 1 and related conjectures. In The Ultimate Challenge:
The 3x + 1 Problem, J.C. Lagarias, ed. American Mathematical Society.
A wide net has already been cast in the search of a resolution to Collatz conjecture.
ReplyDeleteNow the net will be cast even wider as discussion of Conway's recent article spreads via internet. More and more fish will be caught up in its net.
But a consequence of this has been little fish like me (i.e. non mathematicians) have also been caught up in the net.
However, I worked out the dynamics of 3n+1, n/2 in 10 mins...precisely because I didn't approach it like a mathematician. Erdos was correct in saying mathematics is not ready for such problems namely because the solution lies in very basic arithmetic.
The Collatz conjecture has been complicated way out of proportion by the application of sophisticated mathematics.