Oleg's Letter

Scaling in the Collatz Itineraries

The following is a nearly verbatim copy of a letter received from Oleg Dopertchouk on October 11, 2004, reproduced here with his permission.  I don't think my minor editing has spoiled anything in it.


I have noticed you looked at the (3x+3^n) sort of sequences,  here is a result which you might find useful in your further explorations.

Basically,  the 3x+3^n sequences are images of the basic (3x+1) sequence under scaling.

More specifically: We'll call a function f:Z->Z a Collatz function,  if it has a form: f(x)= x/2 if x is even and a*x+b otherwise.

Since I'll be referring to those a lot,  I'll denote such a function f(x)=[a,b].  I'll sometimes refer to a as the multiplication coefficient and b as the addition coefficient.

For example

[3,1] is the standard function x->(3*x+1)/2^n 
[3,5] is the function x->(3*x+5)/2^n and so forth.  

We'll consider transformations between Collatz functions,  a standard trick in math.  A function H:Z->Z is a Collatz-morphism  (or simply a morphism)  between Collatz-functions f and g iff

 g(H(x)) = H(f(x)) for all x

Some simple examples of Collatz-morphisms:   trivial function id:  x->x any power of a Collatz-function gives rise to a Collatz-morphism:

f^n(f(x))=f(f^n(x))

A particularly interesting case is a morphism:  Sk : x->k*x , where k is some positive integer.

Theorem:  For any odd integer k and any Collatz-function f=[a,b],  the function Skx->k*x is a morphism Sk:   f->g where g=[a,b*k]

Consider what f does to different sorts of numbers:

if x is even,   x=2*n then f(x)=x/2

And g(Sk(x))=x*k=(x/2)*k

and Sk(f(x))=k*(x/2)=g(Sk(x))

Note that g(Sk(x))=(x/2)*k is odd iff f(x)=x/2 is odd,  because k is odd   (by assumption).

On the other hand: if x is odd f(x)=a*x+b

g(Sk(x)) = a*k*x+k*b = k * (a*x+b) = Sk(f(x))

Again,  g(Sk(x)) is odd iff f(x) is odd.

In other words,  scaling by factor k transforms the Collatz function [a,b] into another Collatz function [a,b*k],  for instance

[3,1] produces a sequence:

10->5->16->8->4->2->1
while [3,5] produces a sequence
50->25->80->40->20->10->5

which is,  of course,  the same sequence multiplied by 5.

This theorem can help us explore the universe of Collatz-functions.  For example, if we consider a sequence [a,b] and at some point we encounter a number x that is a multiple of b:  x=y*b  , then we can immediately know how the sequence will behave later on.  It's the same way as the sequence [a,1] starting from the number y.  For an example let's take the sequence [3,3] starting from 22:

 22->11->36

Now,  36 is 12*3 and so we can tell that from now on the sequence will behave just like [3,1] starting from 12   (with an additional factor of 3).

[3,1]:
12->6->3->10->5->16->8->4->2->1
[3,3]:
36->18->9->30->15->48->24->12->6->3

In fact,  we can say even more than that.  Since 3x+3 = 3(x+1) it follows that we will reach a multiple of 3 the very first multiplicative step.  So,  if we disregard the first series of divisions by 2 and the initial multiplicative step,  then we can say that [3,3] is isomorphic to [3,1].  The same holds true,  of course,  for any Collatz-function of the form [3,3*k].

Slightly more generally,   if we take sequence [p*k,q*k]   (that is x->(x*p*k+q*k)/2^n)   then after the very first mutiplicative step we get x*p*k+q*k,  which is the image of x*p*k+q under Collatz morphism x->k*x.  From this point on the sequences [p*k,q*k] and [p*k,q] move in step.  This means that the only "interesting" functions are those where the coefficients are relatively prime.  All others can be converted to those using the scaling trick.

There is one more observation along these lines.  If a and b are relatively prime and odd,   then consider odd x  , such that x has a common factor with b (b>1),  x=p*k,  b=q*k.  As we have noted above,  subsequent values of x can be generated using the system [a,q] with scaling k,  but how could we get to such an x in the first place?   Division by 2 couldn't have produced it,   it only removes factors of 2.  The previous multiplicative step should have been:

a*y+b = x*2^n 
or
a*y+q*k = k*p*2^n
so
a*y = k*p*2^n-q*k=k*(p*2^n-q)

Since a and b are relatively prime,   the factor of k can only come from y.  So this means the common factor is "conserved" by the function.  In other words,  if b=k*q then {k*i}=kZ forms a set closed under the action of the function [a,b] and under the action of the inverse function [a,b]^-1.   (It is not really a function, since it has countably many values,  but all these values only differ by the factor of 2 and they all belong to the set).  This is an analog of a notion of a sub-group,   sub-algebra,  etc.   Everything that happens on that set can be derived from behavior of a Collatz-function [a,b/k] with smaller coefficients.  By throwing away such "uninteresting" subsets we are left with a set S all elements of which are relatively prime with b.  It is the only one worth investigating   (assuming we have already explored all functions with smaller coefficients).

Best regards,

Oleg Dopertchouk


In a separate e-mail on March 16, 2005 Oleg calls another transformation to our attention:

The Collatz system 3x+1 is linear conjugate  (meaning can be mapped via a linear transformation y=px+q)  to a collatz-like system:
f(y)={(ay+b)/2 if y is even,  (cy+d)/2 if y is odd)}, 
(where parameters a,c,d are assumed to be odd and b is assumed even,  because otherwise the function is rather trivial).

iff a=1, b=q, c=3 d=p-q
or a=3, b=p-q, c=1, d=q

The reference is to a paper by K. Monks.


Collaz Home Page       Index to Terms Used