Thursday, September 27, 2018

Collatz conjecture, fractals, and \(p\)-adic numbers

Hermannus Contractus has told us that he likes the Collatz Conjecture, an open problem in mathematics. It is amusing, indeed.

The Collatz fractal (above) looks similar to the Mandelbrot set and they're obtained by analogous formulae but the shapes are different in details. The Mandelbrot set has rounder, apple-like pieces placed on each other. Try to look carefully.

I said "amusing" because I feel it is much less fundamental than the Riemann Hypothesis. The Riemann Hypothesis is linked to the basic properties or distribution of primes, and the most natural complex function associated with them. The Collatz Conjecture deals with a somewhat random sequence of integers. In this sense, the Collatz Conjecture looks much less unique to me – almost like a problem from the mathematical olympiad or a piece of recreational mathematics.

But I could be wrong.

The Collatz Conjecture – indicated by all the circumstantial evidence to be true, passing all the checks – says that a sequence always converges to 1 if it starts with a positive integer. What's the sequence? Take the previous number. If it i.e. \(n\) is even, divide it by two i.e. replace by \(n/2\). If it is odd, replace it with \(3n+1\). That's it.

The fractal at the top, the Collatz fractal, is obtained by generalizing the "if then" rule by a smooth linear function of the cosine, and applying it to all complex numbers.

Because \(3n+1\) is always even, you may replace it with \((3n+1)/2\) in the definition of the sequence, thus shortening it.

The sequences may be unbelievably long. If you start with 27, you get:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
So many steps... but it ultimately ends. For a while, I found the Collatz Conjecture analogous to Goodstein's Theorem and you should try to check whether you're capable of proving the former by similar tricks involving the ordinal numbers.

OK, you need an hour to fully understand the Wikipedia article, it's pretty straightforward. However, the proof is elusive – the problem seems hard. An explanation of the difficulty is that the numbers \(n,n+1\) have very different prime decompositions in general. So you don't know which factors of two or three you get if you change a number by one.

Another piece of mathematics that could be useful to prove it are the \(p\)-adic numbers, I think. Where do I see the analogy? Well, I think that if the Collatz Conjecture is true, then every integer may be expressed in a hybridized system that is somewhat analogous to base-2, base-3, or base-10 numbers we know but the details are more elaborate.

If you write a number, like 127, it means that you start with 1, multiply it by 10 and add 2, multiply the result by 10 and add 7.

Similarly, if every integer points to 1 through the Collatz sequence, you may read the sequence backwards and describe the reverse steps. At every point of the reverse trip, you either double the number, or divide it by three with some shift:\[

n \mapsto 2n\\
n\mapsto (n-1)/3

\] You assume that you start with one and use two symbols, e.g. A and B, for the two operations above. By a sequence of A and B, you must be able to get to any integer if the Collatz Conjecture is true. The implication works in this direction, I am not quite sure if it works in the opposite direction as well.

For a typical integer, however, one of the letters A,B may be expected to be more frequent than the other. This ABABABBABBA system of writing numbers differs from the usual base-10 and related systems because you don't just multiply by two. You multiply either by 2 or by 1/3, with some shift. So it's a mixed base-2-and-1/3 system. But it should be enough.

Because one of the "digits", B, reduces large numbers by a factor of three, but still is supposed to be needed to get all the numbers, it could have something to do with 3-adic numbers and the 3-adic metric. Is my intuition wrong?

I just noticed that the Blogspot non-com country codes have disappeared – and they've been gone for several months. Everyone is served Call my reactions slow. I hope that this return to the simple global URL scheme won't mean that the evil champions of global censorship will get a new powerful friend.

No comments:

Post a Comment