Proposition of a formalism to talk about Collatz-like problems

General
1

Here what I call a “Collatz-like problem” would be something that could be framed like that:

Consider h a given natural number (nonzero), a set E, and F a collection of h functions: F=[f_0, f_1... f_{h-1}] from E to E.
Consider map a function from E to \{0, 1... h-1\} and reduce a function from E to E.
The flight of an element e of E is the infinite sequence [g^i(e), i \in \mathbb N] where g:x \rightarrow f_{map(x)}(reduce(x))

What are the behaviours of the flights, what do they look like towards infinity?

For example, the most well-known formulation of the Collatz problem is the one where:

  • E=\mathbb N^*,
  • h=2
  • F=[x \rightarrow x , x\rightarrow 6x+4]
  • map(x) = x\%2 (remainder of the euclidean division by 2)
  • reduce(x) = \lfloor x/2 \rfloor

The “reduced” problem only changes f_1:

  • F=[x \rightarrow x , x\rightarrow 3x+2]

On standard Collatz it is suspected that all flights end up with the period [4,2,1].
On reduced Collatz it is suspected that all flights end up with the period [2,1]. (both hypothesis are equivalent: either both true or both false)

I call trajectory of e \in E the sequence [map(x), x \in flight(e)].
A way to see it is the path e is taking on an automaton.
This is a way to study sequences with elements of \{ 0,1... h-1\} rather than elements of E.

Obviously, two different elements of E cannot have the same flight, but on some situation they could have the same trajectory. Take for example that following case:

  • E=\mathbb Z,
  • h=2
  • F=[x \rightarrow x , x\rightarrow x+2]
  • map(x) = x\%2 (remainder of the euclidean division by 2)
  • reduce(x) = x

Here, all the trajectories of odd numbers are an infinite sequence of 1s, while all the trajectories of even numbers are an infinite sequence of 0s.

I propose to say a Collatz problem is affine when:

  • h \geq 2
  • reduce=x \rightarrow \lfloor x/h \rfloor
  • map=x\rightarrow x\%h
  • and F is a collection of affine functions
    Most of the Collatz-like problem are compatible with this.

Notable example of a Collatz-like problem that is not affine: hyper-reduced Collatz

  • E= odd numbers,
  • h=1
  • F=[x \rightarrow oddfactor(3x+1)]
  • map(x) = 0
  • reduce(x) = x
    Here the application oddfactor takes an integer and divides it by 2 as long as it’s even, it stops when it becomes odd. I called it like that because that’s what remains when you write an integer as 2^n \times r.
    As with all the C-lps with h=1, despite all flights being uniques all trajectories are the same: obviously this formalism won’t the very useful to deal with this kind of problem and should rather be used for cases where h \geq 2.
2 Likes
2

Now, when I talk about a tricot as I did several times here, I am talking about one of those affine Collatz-like problems. A tricot is defined by a matrix M of width 2, in that case h is the height of that matrix and for any i \in \{0, 1 ... h-1\}, f_i(x)=M_{0,i}x+M_{1,i}

From a tricot T=tricot\begin{pmatrix} N_0 & a_0 \\ \vdots & \vdots \\ N_i & a_i \\ \vdots & \vdots \\ N_{h-1} & a_{h-1} \end{pmatrix}, we can extract the characteristic application:
App_T(x) = f_{map_T(x)}(reduce_T(x)) = f_{x\%h}(\lfloor x/h \rfloor) = N_{x\%h}\lfloor x/h \rfloor+a_{x\%h}
And thus, define the flight of x in T as:
flight(x,T)=[App_T^i(x)]_i
The trajectory can be deduced from it:
traj(x,T) = [map_T(App_T^i(x))]_i = [App_T^i(x) \% h]_i

For example, standard-Collatz is represented by tricot\begin{pmatrix} 1 & 0 \\ 6 & 4 \end{pmatrix}.

Reduced-Collatz is represented by tricot\begin{pmatrix} 1 & 0 \\ 3 & 2 \end{pmatrix}.

“5n+1” is represented by tricot\begin{pmatrix} 1 & 0 \\ 10 & 6 \end{pmatrix} for its standard version and tricot\begin{pmatrix} 1 & 0 \\ 5 & 3 \end{pmatrix} for the reduced one.

3

About those “reduced” versions, when framed like this it is clear where this is coming from: if the affine coefficient of one of the f_i is a multiple of h, then map(f_i(x)) doesn’t depends on x, it only depends on the constant part of f_i.
This means by replacing f_i with f_i \circ f_{map(f_i(x))} we get an equivalent problem, in the sense that “solving” one solves both. To state it more precisely, trajectories in the first problem are those in the second but with a map(f_i(x)) inserted after every i.

4

Extension to rationals

Until now, for tricots, E has tacitely been \mathbb{Z}, or a subset of it. Extending to \mathbb{Z} in those specific cases is never an issue. What about non-integer rationals?

If we keep map(x)=x\%h, we have a problem, as we need map to return an integer.
What feels to me like the most natural is to keep (x \rightarrow f_{map(x)}(reduce(x))) affine on any subset of E where map is constant.
We want the behaviour to stay the same for integers, so \forall n \in \mathbb Z, map(n) = x\%h
For integers, map(n)=n-h\times reduce(n) (or, equivalently, reduce(n) = (n-map(n))/h).

One simple idea may be to simply take the numerator of the fraction: map(p/q) = map(p) and reduce(p/q) = (p/q-map(p/q))/h = (p/q-map(p))/h = (p/q-p+h\times reduce(p))/h = reduce(p)-\frac {p(1-1/q)}{h}.
This works fine as long as h=2 and q is coprime with h: in that case reduce(2k/q) = reduce(2k)-\frac {2k(1-1/q)}{2} = k-k(1-1/q) = k/q,
while reduce((2k+1)/q) = reduce(2k+1)-\frac {(2k+1)(1-1/q)}{2} = k-k(1-1/q)-(q-1)/2q = \frac{k+(1-q)/2}{q} (as q is odd, (1-q)/2 is an integer)
For standard Collatz for example, this sends 2k/q on k/q and (2k+1)/q on 6\frac{k+(1-q)/2}{q}+4 = 3\frac{2k+1}{q}+1. This respect the intuitive principle “divide evens by 2, multiply odds by 3 and add 1”.

When h is bigger, that fails. Take h=3:

  • reduce(3k/q) = reduce(3k) - k(1-1/q) = k/q
  • reduce ((3k+1)/q) = reduce (3k+1)-\frac {(3k+1)(1-1/q)}{3} = k-k(1-1/q)-1/3-1/3q = (k-(q+1)/3)/q
  • reduce ((3k+2)/q) = reduce (3k+2)-\frac {(3k+2)(1-1/q)}{3} = k-k(1-1/q)-2/3-2/3q = (k-2(q+1)/3)/q

This doesn’t behave as intuitively: for example with tricot \pmatrix{3 & 0 \\ 3 & 1 \\ 3 & 2} (whose application is identity for integers): 3 \times reduce((3k+1)/q)+1 = 3(k-(q+1)/3)/q+1 = (3k-1)/q. We expect (3k+1)/q there!

(I’m not sure about my calculations for this specific example, but I know ultimately it doesn’t work and we need a better reduce. To be continued)