I am going to continue my (naive) investigation into Collatz Conjecture. In sort, the conjecture says that repeated applications of the following function \[ f(n) = \begin{cases} 1 & \text{ if $n=1$ }\\ 3n+1 & \text{ if $n\neq 1$ is odd }\\ f(n/2) & \text{ if $n$ is even } \end{cases} \] will allways stabilize at 1.
A non-archimedian norm is a function which associates a length \(\|\|x\|\|\) for elements \(x\in X\) in an ablian group (assume \(X\) has addition) which satisfies \[ \|\|x+y\|\|\leq \max(\|\|x\|\|,\|\|y\|\|) \] as opposed to the classical triangle inequality.
Fix a prime number \(p\), then given a number \(n\in\mathbb{Z}\) define \(\nu_p(n)\) as the greatest natural number \(c\) such that \(p^c\) divides \(n\). Then \(\|\|n\|\|_p = 2^{-\nu(n)}\) is a non-archimedian norm on the ring of integers. In this post, I will use \(p=2\) and drop the subscript on the norm notation.
Let me split our function \(f(n)\) we defined above into composition of two functions: \[ a(n) = \begin{cases} 1 & \text{ if } n=1\\ 3n+1 & \text{ otherwise } \end{cases} \quad\text{ and }\quad b(n) = \begin{cases} b(n/2) & \text{ if $n$ is even }\\ n & \text{ otherwise } \end{cases} \] Then \[ f(n) = \begin{cases} a(n) & \text{ if $n$ is odd }\\ ab(n) & \text{ if $n$ is even} \end{cases} = ab(n) \]
Notice that the function \(b\) projects an element \(x\in\mathbb{Z}\) into the set of elements of norm 1 with respect to the 2-norm \(\|\|\cdot\|\|_2\), while the input and outputs have the same p-norm for other odd p’s. On the other hand, \(a\) sends an odd number \(x\) to an element of 2-norm strictly smaller that \(1\), i.e. if \(x\) is odd then we have \(\|\|x\|\|=1\) and \(\|\|a(x)\|\| < 1\). However, \(a\) behaves the same way as \(b\) in terms of other p-norms: it preserves p-norms for p different than 2.
I will give a similar example but from the realm of geometry: take the set of complex numbers and the complex norm. Fix a real number \(\epsilon \> 1\). Define a recursive sequence on the set of elements of norm 1 (the complex unit circle) as follows: let \(x_0\in S^1\), and let \[ x_{n+1} = \frac{x_n + \epsilon}{\|x_n + \epsilon\|} \] Then this sequence stabilizes at 1 for every starting point \(x_0\in S^1\). In this example \(a(x)\) is analogous to \(x\mapsto x+\epsilon\) and \(b(x)\) is analogous to \(x\mapsto x/\|x\|\). The proof of the fact that all sequences stabilize is straight-forward once one realizes that there is an inequality of the form \[ d(x_{n+1},1) \leq \frac{d(x_n,1)}{2} \] for every \(n\) and starting value \(x_0\in S^1\) where \(d(x,y)\) is the geodesic distance on \(S^1\) (fancy word for we measure the angle between the points \(x\) and \(y\) on the unit circle)
So, it is a good idea to check to see if there is a pattern in the p-norms of the elements appearing in the recursive sequence \(x_{n+1} = ab(x_n)\) and \(y_{n+1} = ba(y_n)\) for any starting point \(x_0\in\mathbb{Z}\) and \(y_0\in\mathbb{Z}\).
I need to measure the 2-part of a positive integer. I will write a more generic function to measure the p-part of an integer:
(defun p-part (n p)
(cond ((zerop n) nil)
((< n 0) (p-part (- n) p))
(t (do ((c 0 (1+ c))
(m n (/ m p)))
((not (zerop (mod m p))) c)))))
P-PART
(defun two-part (n) (p-part n 2))
TWO-PARTLet me test
(mapcar 'two-part (loop for i from -2 to 8 collect i))
(1 0 NIL 0 1 0 2 0 1 0 3)Next, the two pieces \(a\) and \(b\):
(defun a(n)
(if (equal n 1)
1
(1+ (* 3 n))))
A
(defun b(n)
(if (evenp n)
(b (/ n 2))
n))
Band the iterator function which iterates the sequence until it hits a cycle:
(defun iterate-collatz-ab(x)
(let ((res))
(do ((y x (a (b y))))
((member y res) (nreverse res))
(push y res))))
ITERATE-COLLATZ-AB
(defun iterate-collatz-ba(x)
(let ((res))
(do ((y x (b (a y))))
((member y res) (nreverse res))
(push y res))))
ITERATE-COLLATZ-BALet me test
(defvar *test-case-ab* (iterate-collatz-ab (+ 11 (random 22391))))
*TEST-CASE-AB*
*test-case-ab*
(8068 6052 4540 3406 5110 7666 11500 8626 12940 9706 14560 1366 2050 3076
2308 1732 1300 976 184 70 106 160 16 1)
(defvar *test-case-ba* (iterate-collatz-ba (+ 11 (random 22391))))
*TEST-CASE-BA*
*test-case-ba*
(13623 20435 30653 11495 17243 25865 19399 29099 43649 32737 24553 18415
27623 41435 62153 46615 69923 104885 9833 7375 11063 16595 24893 9335
14003 21005 7877 1477 277 13 5 1)and check their p-parts for \(p=2\), \(p=3\) and \(p=5\).
(mapcar 'two-part *test-case-ab*)
(2 2 2 1 1 1 2 1 2 1 5 1 1 2 2 2 2 4 3 1 1 5 4 0)
(mapcar (lambda (x) (p-part x 3)) *test-case-ab*)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(mapcar (lambda (x) (p-part x 5)) *test-case-ab*)
(0 0 1 0 1 0 3 0 1 0 1 0 2 0 0 0 2 0 0 1 0 1 0 0)
(mapcar (lambda (x) (p-part x 7)) *test-case-ab*)
(0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0)
(mapcar 'two-part *test-case-ba*)
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(mapcar (lambda (x) (p-part x 3)) *test-case-ba*)
(1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
(mapcar (lambda (x) (p-part x 5)) *test-case-ba*)
(0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 3 0 1 0 1 0 1 0 0 0 0 1 0)
(mapcar (lambda (x) (p-part x 7)) *test-case-ba*)
(0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0)I repeated the random iterations few many times. There isn’t much of a pattern to observe other than the obvious fact that 3-parts of the resulting numbers coming from \(a\) are all 0 because \(3n+1\) is not divisible by 3, and also even if \(n\) is divisible by \(p\) then \(3n+1\) is not divisible by \(p\). In order to make the geometric analogy to work, I will need a different norm on the resulting numbers.