Great!
I’m not great with markdown, so I’ll try to keep the explanation not too calculatory while not hiding any tricky step…
I’m working with objects that I call tricots. A tricot is just a non-empty finite collection of functions from the set of integers to itself.
I note them as a two-columns matrix, each line corresponds to the affine factors of each function.
The height of the tricot is the number of those functions.
The tricot application is defined as follows: to get the image of x, do the euclidean division by the height. Take the function that corresponds to the module and apply it to the integer part of the quotient. I note it App(T).
More specifically I work on affine tricots, where all those functions also have to be affine, with height at least 2.
Under that formalism, the Collatz function would be noted as Tricot((1,0),(6,4)), and the reduced Collatz function would be Tricot((1,0),(3,2))
As an example, App(Tricot((1,0),(3,2))) (40) = 20
I also define the trajectory of a point on a Tricot by the (infinite) sequence of its modules (relative to the height). For example as 5 goes 5 → 16 → 8 → [4 → 2 → 1] under Tricot((1,0),(6,4)), its trajectory is 1,0,0,[0,0,1]. (here the brackets indicate that it repeats indefinitely).
Now my proof works for any affine tricot where all the linear coefficients are coprime with the height. It means it applies to 3n+1, but also 5n+1, and basically any kn+1 where k is odd.
So, let’s start with a lemma (that carries most of the job):
If
- T is an affine tricot where the linear coefficients are coprime with the height (noted h),
- n any positive integer,
- c any positive integer that is not a multiple of h,
- x any integer
then the trajectories of x and x+ch^n over T are the same on the n first items and differ on the *(n+1)*th.
Proof: by induction on n.
- If n=0, then x+ch^n = x+1. As h>1, x and x+1 can’t have the same mod.
- x+ch^(n+1) = x+h(ch^n), whose mod by h is x, thus the first term of the sequence is the same. Moreover, App(T)(x)=aq+b (where a and b are the affine coefficients on the line that corresponds to the module of x by h) and App(T)(x+h(ch^n)) = … = App(T)(x)+ach^n. As ac cannot be a multiple of h, we can apply the induction on the previous rank (using ac for c)
From this lemma, to prove the theorem let’s consider x and y, two different integers.
Let’s get the difference, x-y, and decompose it in base h. Because of all the interesting properties of a decomposition in a base, this yields a sequence that contains a non-zero but finite amount of non-zero elements. If there is only one of those elements we are precisely in the case of the lemma, so we’re good. If there are more, we just need to apply it several times, once for each non-zero elements of the decomposition.
(I know that part seems fuzzy, but it is very hard to explain textually, while it is very clear on a picture. Just imagine you are decomposing the step between x and y into steps whose lengths are a power of h)
I guess that between my non-native english and my redaction some point may look unclear. I’d be glad to answer if you have any question.