First Occurrence of Parity Vectors and the Regular Structure of k-Span Predecessor Sets in the Collatz Graph
share
We study finite paths in the Collatz graph, a directed graph with natural number nodes and where there is an edge from node x to node T(x) = T_0(x) = x/2 if x is even, or to node T(x) = T_1(x) = (3x+1)/2 if x is odd. Our first result is an algorithm that, when given a sequence of n parity bits p = b_0 b_1 ... b_n-1∈{ 0,1 }^n, called a parity vector, finds the occurrences of this parity vector in the Collatz graph which are all the paths o, of length n+1, where the first n nodes of o have exactly the parities given by p. In particular, our algorithm can be used to find the first occurrence of such parity vectors p (has smallest integer nodes out of all paths o), or indeed the i^th for any i ∈N. In order to give this algorithm, we introduce E(p), the "Collatz encoding" of a parity vector p, and the (α_0,-1)-tree, a binary tree which dictates the structure of first occurrence of parity vectors in the Collatz graph by using modular arithmetic in Z/3^kZ. Our main result, which generalizes Colussi [TCS 2011], exploits the properties of first occurrence of parity vectors via their encoding E(p) and the symmetries of the (α_0,-1)-tree in order to highlight some regular structure in the Collatz graph. We show that the k-span predecessor set of x∈N in the Collatz graph, which contains any ancestor y of x that uses exactly k times the map T_1 (and any number of times the map T_0) in order to reach x, can be defined, in binary, by a regular expression reg_k(x). Hence, we exhibit a general regular structure in the Collatz graph. Finally, throughout this work, we state three conjectures that are equivalent to the Collatz conjecture and are related to the objects we have introduced in this paper.
READ FULL TEXT