March 17, 2013

Wild Beasts around the Corner


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.

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.

The special, full-color March 2013 issue of the American Mathematical Monthly is available for purchase.

1 comment:

Tina said...

A wide net has already been cast in the search of a resolution to Collatz conjecture.

Now 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.