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 10¹⁸.

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.