Thread Arithmetics

We can represent the `3x+1` problem as a tree, in which the leaves are the `n_k`.

In this tree the leaves are connected downstream by one of the functions Up `U` and Down `D`, and upstream by one of the inverse functions Top `T` and Bottom `B`.


Notations and Definitions

Threads

A thread is a sequence of transformations chosen within `{U,D,B,T}`.
We note `tau=[t_1t_2cdotst_n]` such a thread of length `n`.

Forward Thread

A thread is a forward thread if only composed by `U` and `D`.

Backward Thread

A thread is a backward thread if only composed by `T` and `B`.

Characteristic Function

We note `F_tau` the characteristic function of the thread `tau` such that:
`F_tau=t_1@t_2@cdots@t_n`
We note `K_tau` and `I_tau` respectively the kernel and image of the function `F_tau`
We note `[dot p]_n` the equivalence class of `p` modulo `n`

Properties

General Case

Theorem:
Let `tau` be a thread of length `n`, with `n_u` transformations `U`, `n_d` transformations `D`, `n_b` transformations `B` and `n_t` transformations `T`:
`{(EE(lambda,mu,kappa,nu)in NN^4),(EE(p,q)in NN^2):}` , `{(K_tau=[dot p]_(2^lambda 3^mu) vv K_tau=NN vv K_tau=O/),(I_tau=[dot q]_(2^kappa 3^nu) vv I_tau=NN vv I_tau=O/),(AA k in NN", " F_tau(2^lambda 3^mu*k+p)=2^kappa 3^nu*k+q):}`
The demonstration is done by induction; the proof is given here.

Construction

The null thread verifies
`{((lambda,mu,kappa,nu) = (0,0,0,0)),(p = 0),(q = 0):}`
For any general thread we can build the characteristic function with the rules of construction summarized in the following Table

if then
`t_(n+1)` `kappa` `nu` `q` `lambda=` `mu=` `kappa=` `nu=` `p=` `q=`
`U` `=0` `` `-=0(2)` `lambda+1` `mu` `0` `nu+1` `2^lambda 3^mu+p` `(3^(nu+1)+3*q+1)/2`
`U` `=0` `` `-=1(2)` `lambda+1` `mu` `0` `nu+1` `p` `(3*q+1)/2`
`U` `!=0` `` `-=0(2)` ``
`U` `!=0` `` `-=1(2)` `lambda` `mu` `kappa-1` `nu+1` `p` `(3*q+1)/2`
`D` `=0` `` `-=0(2)` `lambda+1` `mu` `0` `nu` `p` `q/2`
`D` `=0` `` `-=1(2)` `lambda+1` `mu` `0` `nu` `2^lambda 3^mu+p` `(3^nu+q)/2`
`D` `!=0` `` `-=0(2)` `lambda` `mu` `kappa-1` `nu` `p` `q/2`
`D` `!=0` `` `-=1(2)` ``
`B` `-=0(2)` `=0` `-=0(3)` `lambda` `mu+1` `kappa+1` `0` `2^lambda 3^mu+p` `(2^(kappa+1)+2*q-1)/3`
`B` `-=0(2)` `=0` `-=1(3)` `lambda` `mu+1` `kappa+1` `0` `2^(lambda+1) 3^mu+p` `(2^(kappa+2)+2*q-1)/3`
`B` `-=0(2)` `=0` `-=2(3)` `lambda` `mu+1` `kappa+1` `0` `p` `(2*q-1)/3`
`B` `-=1(2)` `=0` `-=0(3)` `lambda` `mu+1` `kappa+1` `0` `2^(lambda+1) 3^mu+p` `(2^(kappa+2)+2*q-1)/3`
`B` `-=1(2)` `=0` `-=1(3)` `lambda` `mu+1` `kappa+1` `0` `2^lambda 3^mu+p` `(2^(kappa+1)+2*q-1)/3`
`B` `-=1(2)` `=0` `-=2(3)` `lambda` `mu+1` `kappa+1` `0` `p` `(2*q-1)/3`
`B` `` `!=0` `-=0(3)` ``
`B` `` `!=0` `-=1(3)` ``
`B` `` `!=0` `-=2(3)` `lambda` `mu` `kappa+1` `nu-1` `p` `(2*q-1)/3`
`T` `` `` `` `lambda` `mu` `kappa+1` `nu` `p` `2*q`

Restriction to Forward Threads

If we take only the forward threads into account, the construction gives:
`{(K_tau=[dot p]_(2^lambda)),(I_tau=[dot q]_(3^nu)),(AA k in NN", " F_tau(2^lambda*k+p)=3^nu*k+q):}`
with:
• `lambda = n_u + n_d` is the length of the thread,
• `nu = n_u` is the number of odd steps in the thread,
• `p` and `q` can be explicitly determined.
As a consequence, the `i` first steps of the trajectory of `n` are only determined by the congruence of `n` modulo `2^i` and each element of the same equivalence class follows a trajectory with the same `i` first steps.

Forward Threads Properties

Steps Manipulation

Empty Thread

Taking into account forward threads only, the characteristic functions follow a set of construction rules.

Empty Thread

`{((n,o)=(0,0)),(p=0),(q=0):}`

Add right steps

`tau=[t_1t_2cdotst_n] rarr tau'=[t_1 t_2 cdots t_n t_(n+1)], t_(n+1) in {U,D}`

`t_(n+1)` Condition `n'` `o'` `p'` `q'`
`U` `q-=0(2)` `n+1` `o +1` `2^n+p` `(3^(o +1)+3*q+1)/2`
`q-=1(2)` `n+1` `o +1` `p` `(3*q+1)/2`
`D` `q-=0(2)` `n+1` `o` `p` `q/2`
`q-=1(2)` `n+1` `o` `2^n+p` `(3^o +q)/2`

Add left steps

`tau=[t_1t_2cdotst_n] rarr tau'=[t_0 t_1 t_2 cdots t_n], t_0 in {U,D}`

`t_(n+1)` Condition 1 Condition 2 `n'` `o'` `p'` `q'`
`U` `n-=0(2)` `p-=0(3)` `n+1` `o +1` `(2^(n+2)+2*p-1)/3` `2*3^o +q`
`n-=1(2)` `p-=1(3)` `n+1` `o +1` `(2^(n+2)+2*p-1)/3` `2*3^o +q`
`n-=0(2)` `p-=1(3)` `n+1` `o +1` `(2^(n+1)+2*p-1)/3` `2*3^o +q`
`n-=1(2)` `p-=0(3)` `n+1` `o +1` `(2^(n+1)+2*p-1)/3` `2*3^o +q`
  `p-=2(3)` `n+1` `o +1` `(2*p-1)/3` `q`
`D`     `n+1` `o` `2*p` `q`

Remove right steps

`tau=[t_1t_2cdotst_(n-1) t_n] rarr tau'=[t_1 t_2 cdots t_(n-1)], t_(n) in {U,D}`

`t_(n+1)` Condition `n'` `o'` `p'` `q'`
`U` `p<2^(n-1)` `n-1` `o-1` `p` `(2*q-1)/3`
`p>=2^(n-1)` `n-1` `o -1` `p-2^(n-1)` `(2*q-3^o-1)/3`
`D` `p<2^(n-1)` `n-1` `o` `p` `2*q`
`p>=2^(n-1)` `n-1` `o` `p-2^(n-1)` `q-3^o`

Steps right to left rotation

`tau=[t_1t_2cdots t_(n-1) t_n] rarr tau'=[t_n t_1 t_2 cdots t_(n-1)], t_n in {U,D}`

`t_(n+1)` Condition 1 Condition 2 Condition 3 `n'` `o'` `p'` `q'`
`U`   `n-=0(2)` `p-=0(3)` `n` `o ` `(2^n+2*p-1)/3` `(3^o +2*q-1)/3`
  `n-=1(2)` `p-=1(3)` `n` `o ` `(2^n+2*p-1)/3` `(3^o +2*q-1)/3`
`p<2^(n-1)` `n-=0(2)` `p-=1(3)` `n` `o ` `(2^(n+1)+2*p-1)/3` `(2*3^o +2*q-1)/3`
`p<2^(n-1)` `n-=1(2)` `p-=0(3)` `n` `o ` `(2^(n+1)+2*p-1)/3` `(2*3^o +2*q-1)/3`
`p>=2^(n-1)` `n-=0(2)` `p-=1(3)` `n` `o ` `(2*p-2^n-1)/3` `(2*q-3^o -1)/3`
`p>=2^(n-1)` `n-=1(2)` `p-=0(3)` `n` `o ` `(2*p-2^n-1)/3` `(2*q-3^o -1)/3`
    `p-=2(3)` `n` `o ` `(2*p-1)/3` `(2*q-1)/3`
`D` `p<2^(n-1)`     `n` `o ` `2*p` `2*q`
`p>=2^(n-1)`     `n` `o ` `2*p-2^n` `2*q-3^o`

Other representation

The Characteristic Function of a forward thread can be written:
`F_tau(x)=(3^o*x+beta)/2^n`
`beta=2^n*q-3^o*p`
with:
• `n` is the number of steps,
• `o` is the numbers of odd steps,
• `p` and `q` defined as above.
For the empty thread, `beta=0`

Construction

Using this presentation, the construction rules for Forward Threads are summarized in the Table bellow:

  `n'` `o'` `beta'`
Add `U` `n+1` `o +1` `3*beta+2^n`
Add `D` `n+1` `o` `beta`

Composition

If we define a composition law `o+` on threads by:
`A=[a_1 a_2 cdots a_(n_A)]`
`B=[b_1 b_2 cdots b_(n_B)]`
`Ao+B=[a_1 a_2 cdots a_(n_A) b_1 b_2 cdots b_(n_B)]`
The Characteristic Functions verify:
`n_(Ao+B)=n_A+n_B`
`o_(Ao+B)=o_A+o_B`
`beta_(Ao+B)=2^(n_A)*beta_B-3^(o_B)*beta_A`

Minimum and maximum values for `beta` coefficients

The minimum and maximum values for `beta` verify:
`AA tau", "beta_tau in [3^o-2^o,2^(n-o)*(3^o-2^o)]`

Demonstration:
By construction rules, for any length `n` and any number of odd steps `o<=n`, the minimum value for `beta` is obtained when all the odd steps are encountered first:
`tau_0=[obrace(UU cdots U)^o obrace(DD cdots D)^(n-o)]`
`beta_min=beta_(tau_0)=beta([obrace(UU cdots U)^o])=3^o-2^o`
and the maximum value for `beta` is obtained when all the even steps are encountered first:
`tau_1=[obrace(DD cdots D)^(n-o) obrace(UU cdots U)^o]`
`beta_max=beta_(tau_1)=2^(n-o)*beta([obrace(UU cdots U)^o])=2^(n-o)*(3^o-2^o)`