Loops

Definition

A loop `Lambda` is a set of cyclic routes `obrace(m)` beginning with the integer `m`.
Each route has for length `n` the smallest number of steps such that the initial value is encountered.
`obrace(m)={m_0 ", " m_1=F(m_0) ", " cdots ", " m_n=F^((n))(m_0)=m_0}`
`Lambda={obrace(m-0), obrace(m_1), cdots, obrace(m_(n-1))}`

The loop is identified by `Lambda_m` by choosing `m` as the element of the routes whose absolute value is minimum:
`m=m_k ", " AA i in [0,n[ ", " |m_i|<=|m_k|`

The associated thread is then the trajectory of `m`:
`tau_(Lambda_m)= hat(T)(m)`

Known Loops

The known loops are:

Loop	Route	Thread
`Lambda_(-17)`	`{−17,−25,−37,−55,−82,−41,−61,−91,−136,−68,−34} `	`[UUUUDUUUDDD] `
`Lambda_(-5)`	`{−5,−7,−10} `	`[UUD] `
`Lambda_(-1)`	`{−1} `	`[U] `
`Lambda_0`	`{0} `	`[D] `
`Lambda_1`	`{1,2} `	`[UD] `

Properties

P1

A loop takes values on positive or negative integers depending only of the sign of `K = 2^n − 3^o`.

Demonstration:

A loop is a route and by the property (P1) of routes, all values taken have the same sign, by example the sign of the first number `m_0`.
Then `m_0` verifies:
`m_0=m_n=F^((n))(m_0)=(3^o*m_0+beta)/2^n`
`m_0=beta/(2^n-3^o)`
And as by construction, `beta>=0`, the sign of `m_0` and the sign of every `m_k` are the same than the sign of `K=2^n-3^o`
`square`

We can express that with the completeness of the loop:
`{(c_Lambda < ln(2)/ln(3) rArr AA k < n ", " m_k >=0),(c_Lambda > ln(2)/ln(3) rArr AA k < n ", " m_k <=0):}`

P2

If `Lambda` is a loop on positive integers and `tau` the thread associated, either for `theta=tau` or `theta` = a concatenation of a sufficiently large enough number of `tau`, every thread `theta_i` obtained by rotation of `theta` verifies `p_i − q_i = 0`

Demonstration:

Let`Lambda` be a loop of length `n`: `{m_0, m_1, cdots ,m_(n−1)}` with `o` odd steps, we choose `k` such as:
`AA i lt n, m_i lt 3^(k*o)`
By (P1), `3^o lt 2^n`, then:
`AA i lt n, m_i lt 2^(k*n)`

for each rotation `theta_i` of `theta`, the characteristic function verifies:
`F_(theta_i)(m_i)=m_i`
`m_i in K_(F_(theta_i))=[dot(p)_i]_(2^(k*n))`
`m_i in I_(F_(theta_i))=[dot(q)_i]_(3^(k*o))`
`(m_i in [dot(p)_i]_(2^(k*n))) ^^ (m_i<2^(k*n)) rArr m_i=p_i`
`(m_i in [dot(q)_i]_(3^(k*o))) ^^ (m_i<3^(k*o)) rArr m_i=q_i`

It follows that `p_i − q_i = 0`
`square`

P3

If `Lambda` is a loop on negative integers and `tau` the thread associated, either for `theta=tau` or `theta` = a concatenation of a sufficiently large enough number of `tau`, every thread `theta_i` obtained by rotation of `theta` verifies `p_i − q_i = K`

Demonstration:

Let`Lambda` be a loop of length `n`: `{m_0, m_1, cdots ,m_(n−1)}` with `o` odd steps, we choose `k` such as:
`AA i lt n, -m_i lt 2^(k*n)`
By (P1), `3^o gt 2^n`, then: `AA i lt n, -m_i lt 3^(k*o)`

for each rotation `theta_i` of `theta`, the characteristic function verifies:
`F_(theta_i)(m_i)=m_i`
`m_i in K_(F_(theta_i))=[dot(p)_i]_(2^(k*n))`
`m_i in I_(F_(theta_i))=[dot(q)_i]_(3^(k*o))`
`(m_i in [dot(p)_i]_(2^(k*n))) ^^ (-m_i<2^(k*n)) rArr m_i=p_i-2^(k*n)`
`(m_i in [dot(q)_i]_(3^(k*o))) ^^ (-m_i<3^(k*o)) rArr m_i=q_i-3^(k*o)`

It follows that `p_i − q_i = 2^(k*n)-3^(k*o)=K`
`square`

P4

In (P2) and (P3) the concatenation of two threads is always sufficient.

Demonstration:

First we note that:
`AA (u,v) in NN^2, |2^u-3^v|>=1`

The maximum value of the loop (in absolute value) is:
`m_(max)=max_i(|beta_i/K|)=1/|K|*max_i(beta_i)`
`rArr m_max <= max(beta_i) <= 2^(k*n-k*o)*(3^(k*o)-2^(k*o))`
`ln(m_max) <= k*(n-o)*ln(2)+k*o*ln(3))`
`ln(m_max) <= k*(n*ln(2)+o*(ln(3-ln(2)))`
`ln(m_max) <= k*n*ln(2)+k*o*ln(3)`

By (P1)
on positive integers `n*ln(2) > o*ln(3) rArr ln(m_max) < 2*k*ln(2)`,
on negative integers `n*ln(2) < o*ln(3) rArr ln(m_max) < 2*o*ln(3)`

Taking `k=2` is sufficient to satisfy (P2) and (P3)
`square`

P5

Except for `Lambda_0` there is at least one odd step in a loop.

Demonstration:

Let`Lambda` be a loop of length `n`: `{m_0, m_1, cdots ,m_(n−1)}` with `n` even steps
`m_n=m_0=m_0/2^n`

This can be solved only by either:
`n = 0`, `Lambda`cannot be a loop, or
`m_0 = 0`, `Lambda=Lambda_0`.
`square`

Behavior in `ZZ//6ZZ`

The forward steps are mapping the integers by:
`{:(2*k mapsto k,,[dot 0]_2 rarr NN),(2*k+1 mapsto 3*k+2,,[dot 1]_2 rarr [dot 2]_3):}`

Refining the “from” until all “to” are distributed amongst equivalence classes modulo 6, we have:

from	Step	to
`x=12*k in [dot 0]_(12) sub [dot 0]_6`	`D`	`x=6*k in [dot 0]_6`
`x=12*k+2 in [dot 2]_(12) sub [dot 2]_6`	`D`	`x=6*k +1 in [dot1]_6`
`x=12*k+4 in [dot 4]_(12) sub [dot 4]_6`	`D`	`x=6*k +2 in [dot2]_6`
`x=12*k+6 in [dot 6]_(12) sub [dot 0]_6`	`D`	`x=6*k +3 in [dot3]_6`
`x=12*k+8 in [dot 8]_(12) sub [dot 2]_6`	`D`	`x=6*k +4 in [dot4]_6`
`x=12*k+10 in [dot 10]_(12) sub [dot 4]_6`	`D`	`x=6*k +5 in [dot5]_6`
`x=4*k+1 in [dot 1]_4 sub ([dot 1]_6 uu [dot 3]_6 uu [dot 5]_6)`	`U`	`x=6*k +2 in [dot2]_6`
`x=4*k+3 in [dot 3]_4 sub ([dot 1]_6 uu [dot 3]_6 uu [dot 5]_6)`	`U`	`x=6*k +5 in [dot5]_6`

Summarizing the admissible backward steps from and to equivalence classes modulo 6, it comes:

from \ to	`[dot0]_6`	`[dot1]_6`	`[dot2]_6`	`[dot3]_6`	`[dot4]_6`	`[dot5]_6`
`[dot0]_6`	`D`			`D`
`[dot1]_6`			`U`			`U`
`[dot2]_6`		`D`			`D`
`[dot3]_6`			`U`			`U`
`[dot4]_6`			`D`			`D`
`[dot5]_6`			`U`			`U`

Admissible steps for loops

Lemma 1:
Except 0, no number belonging to `[dot0]_3` can be part of a loop.

Proof:

The predecessor of `3*k in [dot0]_3` is `6*k in [dot0]_3`
To close a loop on `n=3*k` one must have `n=2^i*3*k` for some `i`
`{(3*k=2^i*3*k),(i>=1):} rArr k=0 rArr n=0`
`square`

The admissible backward steps from and to equivalence classes modulo 6 inside a loop are thus limited to:

from \ to	`[dot1]_6`	`[dot2]_6`	`[dot4]_6`	`[dot5]_6`
`[dot1]_6`		`U`		`U`
`[dot2]_6`	`D`		`D`
`[dot4]_6`		`D`		`D`
`[dot5]_6`		`U`		`U`

A graph representation is given bellow:

Number of steps

Let us count the number of these steps, and note `m_(ij)` the number of steps from the `i^(th)` equivalence class modulo 6 to the `j^(th)` equivalence class modulo 6

As we are in a loop, every step entering a node has to leave it, thus the total number of steps entering an equivalence class equals the total number of steps exiting it:
`{:(m_(15)+m_(12)=m_(21)),(m_(21)+m_(24)=m_(12)+m_(42)+m_(52)),(m_(45)+m_(42)=m_(24)),(m_(52)+m_(55)=m_(15)+m_(45)+m_(55)):}`

Choosing a reduced set of parameters, a loop can be represented by:

Values at nodes

Let us note `e_(ijk)` the `k^(th)` value exiting the `i^(th)` equivalence class modulo 6 to enter the `j^(th)` equivalence class modulo 6 and `s_(ijk)` the value upon destination.

And let us consider the summations:
`e_(ij)=sum_k(e_(ijk))`
`s_(ij)=sum_k(s_(ijk))`
`E_i=sum_j(e_(ij))`
`S_i=sum_j(s_(ij))`

As we are in a loop the total value entering a node has to leave it:
`AA i in {1,2,4,5}, E_i=S_i`

The transformations are known as forward steps, so for any `k`:
`{(s_(12k)=U(e_(12k))=(3*e_(12k)+1)/2),(s_(15k)=U(e_(15k))=(3*e_(15k)+1)/2),(s_(21k)=D(e_(21k))=e_(21k)/2),(s_(24k)=D(e_(24k))=e_(24k)/2), (s_(42k)=D(e_(42k))=e_(42k)/2),(s_(45k)=D(e_(45k))=e_(45k)/2),(s_(52k)=U(e_(52k))=(3*e_(52k)+1)/2),(s_(55k)=U(e_(55k))=(3*e_(55k)+1)/2):}`

For the summations and taking into account the number of steps, we have:
`{(s_(12)=(3*e_(12)+m_(12))/2),(s_(15)=(3*e_(15)+m_(15))/2),(s_(21)=e_(21)/2),(s_(24)=e_(24)/2), (s_(42)=e_(42)/2),(s_(45)=e_(45)/2),(s_(52)=(3*e_(52)+m_(52))/2),(s_(55)=(3*e_(55)+m_(55))/2):}`

then:
`{(S_1=s_(21)=e_(21)/2),(S_2=s_(12)+s_(42)+s_(52)=(3*e_(12)+m_(12))/2+e_(42)/2+(3*e_(52)+m_(52))/2), (S_4_=s_(24)=e_(24)/2),(S_5=s_(15)+s_(45)+s_(55)=(3*e_(15)+m_(15))/2+e_(45)/2+(3*e_(55)+m_(55))/2), (E_1=e_(12)+e_(15)),(E_2=e_(21)+e_(24)),(E_4=e_(42)+e_(45)),(E_5=e_(52)+e_(55)):}`

Combining the equations, it comes:
`{(E_2=2*S_2+2*S_4),(3*E_1+E_2+E_4+3*E_5=2*S_1+2*S_2+2*S_4+2*S_5+m_(12)+m_(15)+m_(52)+m_(55)+):}`

With the condition `AA i in {1,2,4,5}, E_i=S_i` we obtain the following State Equations:
`E_2-2*E_1-2*E_4=0`
`E_5-E_1-3*E_4+a+2*b+c+d=0`

It can be summarized as:

Patterns in loops

Lemma 2:
The greatest integer (in absolute value) of a loop belongs to `[dot2]_3`.

Proof:

By Lemma 1, no integer from `[dot0]_3` can be part of a loop.

Let us suppose that an integer `m_i` from `[dot1]_3` is the greatest integer in absolute value of the loop. It is either part of `[dot1]_6` or `[dot4]_6`.

Both its successor `m_(i+1)` and its predecessor `m_(i-1)` are part of the loop.

If `m_i in [dot1]_6`
`m_i in [dot1]_6 rArr m_i in [dot1]_2 rArr m_(i+1)=(3*m_i+1)/2`
`|m_(i+1)|=(3*|m_i|+-1)/2>|m_i| if m_i !in [-1,1]`

If `m_i in [dot4]_6`
`m_i in [dot4]_6 rArr m_(i-1) in [dot2]_6 rArr m_(i-1)=2*m_i`
`|m_(i-1)|=(2*|m_i|>|m_i| if m_i!=0`

In both cases, the hypothesis is contradicted, `m_i` do not belong to `[dot1]_3`
Thus it has to belong to `[dot2]_3`
`square`

Values in `ZZ//pZZ`

Summation of the elements of a loop

Let `Lambda` be a loop of length `m, {x_1, x_2,cdots , x_m}`.

These `m` elements can be sorted in `m_o` odd and `m_e` even values.
`{(y_i=2*a_i", "i in [1,m_e]),(z_j=2*b_j-1", "j in [1,m_o]),(m_e+m_o=m):}`

The summation of all those elements is:
`{:(X,=sum_(k=1)^m x_k),(,=sum_(i=1)^(m_e) y_i+sum_(j=1)^(m_o) z_j),(,=2*sum_(i=1)^(m_e) a_i+2*sum_(j=1)^(m_o) b_j - m_o),(,=2*A+2*B-m_o):}`

Applying the Collatz function to each element:
`{:(y_i=2*a_i mapsto y'_i=a_i, i in [1,m_e]),(z_j=2*b_j-1 mapsto z'_j=3*b_j-1, j in [1,m_o]):}`

The summations of all those transformed elements is:
`{:(X',=sum_(k=1)^m x'_k),(,=sum_(i=1)^(m_e) y'_i+sum_(j=1)^(m_o) z'_j),(,=sum_(i=1)^(m_e) a_i+3*sum_(j=1)^(m_o) b_j - m_o),(,=A+3*B-m_o):}`

As `Lambda` is a loop, the two summations have the same value:
`X'=X rArr 2*A+2*B-m_o=A+3*B-m_o`
`rArr A=B`

Generalization

For any value `p`, let’s add the elements raised to the `p^th` power:
`{:(X_p,=sum_(k=1)^m (x_k)^p),(,=sum_(i=1)^(m_e) (y_i)^p+sum_(j=1)^(m_o) (z_j)^p),(,=sum_(i=1)^(m_e) (2*a_i)^p+sum_(j=1)^(m_o) (2*b_j - 1)^p):}`
`{:(X'_p,=sum_(k=1)^m (x'_k)^p),(,=sum_(i=1)^(m_e) (y'_i)^p+sum_(j=1)^(m_o) (z'_j)^p),(,=sum_(i=1)^(m_e) (a_i)^p+sum_(j=1)^(m_o) (3*b_j - 1)^p):}`

again, we must have:
`X'_p=X_p`

Let’s note:
`{:(A_k=sum_(i=1)^(m_e) (a_i)^k),(B_k=sum_(j=1)^(m_o) (b_j)^k):}`

We can develop `X_p` and `X'_p`
`X_p=2^p*A_p+sum_(k=0)^p ((-1)^(p-k)*2^k*((p),(k))*B_k)`
`X'_p=A_p+sum_(k=0)^p ((-1)^(p-k)*3^k*((p),(k))*B_k)`

The condition becomes:
`2^p*A_p+sum_(k=0)^p ((-1)^(p-k)*2^k*((p),(k))*B_k)=A_p+sum_(k=0)^p ((-1)^(p-k)*3^k*((p),(k))*B_k)`
`(2^p-1)*A_p=sum_(k=0)^p ((-1)^(p-k)*(3^k-2^k)*((p),(k))*B_k)`

All those conditions can be summarized in a matrix equation:
`[A]xx[alpha]=[B]xx[beta]`
where:
`[A]` is the vector composed of `[A_k]`
`[B]` is the vector composed of `[B_k]`
`[alpha]` is the matrix:
`{(i=j rArr alpha_(i,j)=2^i),(i!=j rArr alpha_(i,j)=0):}`
`[beta]` is the matrix:
`{(j<=i rArr beta_(i,j)=(-1)^(i-j)*(3^j-2^j)*((i),(j))),(j>i rArr beta_(i,j)=0):}`

Another formulation to represent those constraints is:
`[A]xx[alpha']=[B]xx[beta']`
with
`[beta']` is the matrix:
`{(i=j rArr beta'_(i,j)=(3^j-2^j)),(i!=j rArr beta'_(i,j)=0):}`
`[alpha']` is the matrix:
`{(i ge j rArr alpha'_(i,j)=2^(j-1)*((i),(j))),(i lt j rArr alpha'_(i,j)=0):}`

Considering the prime factors of `2^i − 1` and that the value of any `B_k` modulo `p` is only determined by the repartition of `b_j` amongst congruence classes modulo `p`, we can build necessary conditions.

The same can be done with prime factors of `3^k-2^k` and the repartition of `a_i` amongst congruence classes modulo `p`.

Example in `ZZ//5ZZ`

The condition which is the second line of `[A]xx[alpha']=[B]xx[beta']` is:
`(3^2-2^2)*B_2=(2^0-1)*((2),(0))*A_0+(2^1-1)*((2),(1))*A_1+(2^2-1)*((2),(2))*A_2`
`5*B_2=2*A_1+3*A_2`

If we note `a_p^k` the number of `a_i` such that `a_i-=k(p)`
`A_1-=0*a_5^0+1*a_5^1+2*a_5^2+3*a_5^3+4*a_5^4 (5)`
`A_2-=0*a_5^0+1*a_5^1+4*a_5^2+4*a_5^3+1*a_5^4 (5)`
`5*B_2=2*A_1+3*A_2 rArr 2*A_1+3*A_2-=0(5)`
`a_5^2+3*a_5^3+a_5^4 -=0 (5)`

For the fourth line it comes:
`65*B_4=4*A_1+18*A_2+28*A_3+15*A_4`
`rArr 4*A_1+3*A_2+3*A_3 -=0(5)`

with:
`A_3-=0*a_5^0+1*a_5^1+3*a_5^2+2*a_5^3+4*a_5^4 (5)`

The condition is:
`4*a_5^2+a_5^4 -=0 (5)`

Combining both we have:
`a_5^2 -=a_5^3 -=a_5^4 (5)`

Some properties

The conditions for primes up to 19 are given here.