Amusical Permutations and Unsettleable Problems

John Horton Conway (1937–2020) in 2009 [Photo (c) Denise Applewhite, Princeton University]

In a memorial tribute in the Notices of the American Mathematical Society (Ryba, et al, 2022), Dierk Schleicher wrote of how he convinced John Conway to publish a paper, “On unsettleable arithmetical problems”, which included a discussion of the Amusical Permutations. This paper, which discusses arithmetical statements that are almost certainly true but likely unprovable, was selected for the 2014 edition of “The Best Writing on Mathematics,” published by Princeton University Press [Pitici, 2014]. Amusical Permutations was an attempt to find a simple sequence whose behaviour was undecidable.

The Collatz Conjecture

The Collatz map is simply defined. It is a map on the natural numbers: an even number ${2n}$ is mapped to ${n}$ ; an odd number ${n}$ is mapped to ${3n+1}$ . It is popularly known as the HOTPO map (HOTPO = Half Or Triple Plus One). Since, for ${n}$ odd, the number ${3n+1}$ must be even, we can combine two steps and write the map in condensed form

$\displaystyle 2n \rightarrow n \,, \qquad 2n - 1 \rightarrow 3n - 1 \,. \ \ \ \ \ (1)$

This map, for arguments from 1 to 100, is illustrated in the Figure below.

The Collatz (condensed) map ${C:\mathbb{N}\rightarrow\mathbb{N}}$ for the first 100 numbers.

When the Collatz map is iterated, a sequence of numbers is obtained. Numerical experiments show that, in all cases, the sequence arising from the condensed map (1) enters the cycle ${1\rightarrow2\rightarrow1}$ , or simply ${(1,2)}$ . The Collatz Conjecture is that this cycle is reached from all starting values ${n}$ , but no proof has ever been found.

Conway (2013) speculated that the Collatz Conjecture is “unsettleable”. By that he meant that it can neither be proved or disproved from the basic axioms of set theory. It was shown by Kurt Gödel in 1931 that there are always such undecidable problems, and Conway, suspecting that such problems may be very common, asked what were the simplest true assertions that are neither provable nor disprovable. He discussed a number of candidates, including the Collatz function, and analysed a particular case, which he called the amusical permutation.

Amusical Permutation

An automorphism ${\Pi : \mathbb{N}\rightarrow\mathbb{N}}$ may be defined as follows:

$\displaystyle \begin{array}{rcl} 2n & \longleftrightarrow & 3n \\ 4n - 3 & \longleftrightarrow & 3n - 2 \\ 4n - 1 & \longleftrightarrow & 3n - 1 \,. \end{array}$

We note that, in contrast to the Collatz map, this function is invertable, so it can be “run” in both directions. The action of the function on the first ${100}$ numbers is shown in the following Figure:

The amusical permutation for the first 100 numbers.

Conway presented four finite cycles, which he believed to be the only such cycles for the map:

$\displaystyle (1) \quad (2,3) \quad (4,6,9,7,5 ) \quad (44,66,99,74,111,83,62,93,70,105,79,59) \,.$

He also listed some values of what are suspected to be infinite sequences. No proofs are available, but the numerical evidence is compelling. For example, the sequence starting from the number 8 was computed for 200,000 iterations, when the value exceeded ${10^{5000}}$ . It is virtually impossible to believe that a term with value 8 will ever recur.

A probabilistic argument supports the assertion that there are no more finite cycles. A number ${n}$ will be multiplied (approximately) by ${\frac{3}{2}}$ if even or by ${\frac{3}{4}}$ if odd. Let us assume that even and odd values of ${n}$ are equally likely. Then, on average, the number is multiplied by ${\sqrt{ \frac{3}{2}\times\frac{3}{4} } = \sqrt{ \frac{9}{8} }}$ . In twelve iterations of the map, the factor is

$\displaystyle \frac{3^{12}}{2^{18}} \approx 2.027 \,, \ \ \ \ \ (2)$

or an approximate doubling. Thus, once the number is large, it is very hard to imagine that it will return to a small value to complete the cycle. This is not a proof of anything, but it is “probabilistically obvious” or, as Conway has it, probvious.

Why “Amusical”?

In Pythagorean tuning, the entire chromatic scale is generated from a sequence of musical fifths, with notes having frequency ratio ${3:2}$ . When the product exceeds ${2}$ , moving to a higher octave, it is scaled down by one half. After twelve iterations, the factor is

$\displaystyle \frac{3^{12}}{2^{19}} \approx 1.0136 \,. \ \ \ \ \ (3)$

If this factor were equal to 1, the cycle would be closed, but it is impossible for a ratio of powers of 2 and of 3 to equal 1. The slight difference is known as enharmonic discrepancy, and the ratio in (3) is called the Pythagorean comma. This is the inspiration for Conway’s amusing name “amusical permutation”.

Conclusion

Conway suggested that not only is the assertion that 8 is in an infinite cycle unsettleable, but this unsettleability is itself unprovable, and so on, in an infinite stack of logical implications.

For the Collatz conjecture, as written in condensed form (1), the map is scaling by ${\frac{1}{2}}$ or ${\frac{3}{2}}$ with equal probability, so the expected growth factor is ${\sqrt{{3}/{4}} <1}$ . Thus, we may argue that the map should probviously cycle back to 1. Nevertheless, in a postscript, Conway wrote that the Collatz conjecture is very likely unsettleable.

Sources

${\bullet}$ Conway, John H., 2013: On Unsettleable Arithmetical Problems. Amer. Math. Monthly , 120 (3), 192–198.

${\bullet}$ Pitici, Mircea, 2014: The Best Writing on Mathematics, 2014. Princeton Univ. Press.

${\bullet}$ Ryba, Alex, et al., 2022: John Horton Conway (1937–2020) Notices Amer. Math. Soc., Vol. 69(7), 1171–1187.

${\bullet}$ Lynch, Peter, 2013: The Ups and Downs of Hailstone Numbers. ThatsMaths.

ThatsMaths