# Identification of Invariant Sets for Discrete Dynamical Systems on the Positive Integers

Let $\phi:\mathbb{N}\times \mathbb{N}^+\rightarrow \mathbb{N}^+$ be a dynamical system on the positive integers. Suppose we refer to the orbit of a periodic point of $\phi$ as an invariant set of the dynamical system (obviously because if $U$ is a periodic orbit then $\phi(U) = U$). I am interested in the literature available on identifying the number of such invariant sets for a given $\phi$. Does anyone have any leads?

As per the conversation below with Gerry Myerson, the ultimate goal is to better understand the existence/non-existence of $k$-cycles of the Collatz function. The original proofs for 1- and 2-cycles rely on very specialized results...

• Are you familiar with the Collatz problem? Given how hard it seems to be to find the number of invariant sets of such a simple system, I wonder how much can be known in general. Nov 16 '17 at 20:45
• @GerryMyerson Yes. In fact, trying to better understand the existence/nonexistence of nontrivial cycles lead me to generalize the question to this one!
– JMJ
Nov 16 '17 at 20:48
• I figured as much. You might have mentioned that in your post. Nov 16 '17 at 21:02
• @GerryMyerson OK. I will edit it.
– JMJ
Nov 16 '17 at 21:03
• @RodrigodeAzevedo the input of $\phi$ is only a positive integer. The extra term is a way of writing that we consider orbits of the form $\phi(x),\phi^2(x), \phi^3(x),\dots$. It's an abuse of notation that is common in the dynamical systems field.
– JMJ
Dec 13 '17 at 17:51

For the general focus of the question: "how many invariant sets" I don't remember any article dealing explicitely with this. Surely my readings are incomplete, but I also don't think that there is something mentioned in Lagarias' big reference/review list to that specific question.

But let me mention some own thoughts for a more general view on cycles in Collatz-type problems.
If we use the "syracuse"-notation for the Collatz problem (and similars) then the sequence of $3a_k+1$ steps followed by $2^{A_k}$ steps can economically be encoded by a notation $a_N = T(a_1; [A_1,A_2,...,A_N])$ where we denote the number of odd steps as $N$ and the number of even steps $S$ (equalling the sum of all exponents $A_k$). The expression $T(a;[A_1,...,A_N])$ has a numerator with a part free of $a_1$ which we denote as $$Q([A_1,A_2,...,A_N])=3^{N-1} + 3^{N-2}2^{A_1} + 3^{N-3}2^{A_1+A_2} + ... + 2^{S-A_N} \tag 1$$ Let us now write shorter $E_j(N,S)$ for some vector of exponents $[A_1,A_2,...,A_N]$.
Then the whole expression becomes $$a_n = T(a_1;E_j(N,S)) = {3^N\over2^S}a_1 + {Q(E_j(N,S))\over2^S} \tag 2$$ If we look at a given vector of exponents $E_j(N,S)$ as the independent part and the elements of the orbit $a_k$ as dependents, then we can determine a cycle by $a_n=a_1$ and $$a_1 = {Q(E_j(N,S)) \over 2^S - 3^N} \tag 3$$ If we demand that $a_1$ must be positive integer then we know, that for $N=1$ and $S=2$ there is the solution of the (trivial) cycle - which very likely is the only cycle.

However, in generalization, if we allow negative and rational $a_k$ then of course we have infinitely many solutions or infinitely many invariant sets, namely for each combination of $N$ and $S \ge N$ a collection of invariant set (depending of the composition of $E_j(N,S)$ by a vector of $A_k$). Trivially, if we ask for the generalized Collatz problem $3x+r$ then for $r=2^S-3^N$ we have a solution in the integers, so the set of $3x+r$-problems cover the set of integer solutions $$a_1 = r \cdot {Q(E_j(N,S)) \over 2^S - 3^N} \tag 4$$ and thus the (infinite) set of invariant sets analoguously to the generalized Collatz-problem with $a_k \in \mathbb Q$

The same is of course true for the second generalization of the Collatz problem to $m x +r$ : using $m x + 1$ and allowing $a_k \in \mathbb Q$ we find infinitely many "invariant sets" which can be recovered in $m x + r$ - problems with $r = 2^S - m^N$

However, the problem how many invariant sets for $m x +1$ for $a_k \in \mathbb Z$ I have not seen been handled in literature. My own heuristic is relatively short; I've recently posted the following table: $$\small \begin{array}{rr|r|l}\\ \text{base } m & & n \text{of cycles} & \text{transformations}& E(N,S)\\ \hline m=2^k-1 & 3 & 4 & [1;1;...] & [2,...] \\ &&& [-1;-1;...] & [1,...]\\ &&& [-5,-7;-5,...] & [1,2,...]\\ &&& [-17,-25,-37,-55,-41,-61,-19;-17,...] & [1,1,1,2,1,1,4,...] \\ \hline & 7 & 1 & [1;1;...] & [3,...] \\ & 15 & 1 & [1;1;...] & [4,...] \\ & 31 & 1 & [1;1;...] & [5,...] \\ & \vdots \\ & 16383 & 1 & [1;1;...] & [14,...]\\ & \vdots \\ \hline \phantom{asas} \\ \hline m=2^k+1 & 3 & 4 & \text{see above} \\ \hline & 5 & 4 & [1,3;1,...]& [1,4,...] \\ &&& [13,33,83;13,...] & [1,1,5,...]\\ &&& [17,43,27;17,...] & [1,3,3,...] \\ &&& [-1;-1;...] & [2,...]\\ \hline & 9 & 1 & [-1;-1;...] & [3,...] \\ & 17 & 1 & [-1;-1;...]& [4,...] \\ & 33 & 1 & [-1;-1;...]& [5,...] \\ & \vdots \\ & 16385 & 1 & [-1;-1;...] & [14,...]\\ & \vdots \\ \hline \phantom{aaaa} \\ \hline \text{other }m & 181 & 2 & [27,611;27,...] & [3,12,...]\\ & & & [35,99;35,...]& [6,9,...] \end{array} \tag 5$$ The first cycles for $m=5$ and for $m=181$ are already mentioned in Crandall's 1978 paper(and also the relation between the $a_k \in \mathbb Q$ of the $3x+1$ problem and the $a_k \in \mathbb N$ in the $3x+r$ problems) - but not in the sense of a quantification of the number of cycles for some of that dynamical systems. The "invariant sets" for $m=3$ and $m=5$ are also in wikipedia.

So what I've found for the integer solutions of the $m x +1$ are either $1$, $2$ or $4$ "invariants sets" (by that small heuristic), and only for three bases $m$ exactly two or four such sets.

Of course, this is not literature and not published - and likely needs more workout in the sense and in the focus of your question.

I've tested $m<20 000$, $|a_1| < 1000$ and $N \le 30$

This is a fairly substantial rewriting of my original answer.

Sharkovski's theorem, which unfortunately only applies to $\mathbb{R}$ is the definitive theorem in this field and one thing it states is that all cycles will be of order a power of 2, else there will be infinitely many.

If it could be extended to $2\mathbb{N}-1$ (or to some suitable extension of $2\mathbb{N}-1$) such that it applied to the Collatz conjecture then the existence of any nontrivial cycle would imply the existence of infinitely many nontrivial loops of certain orders; including a cycle of length 2, contradicting Lagarias (1985) result that there are no nontrivial cycles with length $<275000$ (and therefore proving the weakened Collatz Conjecture; that the are no non-trivial cycles).

ST states that a continuous interval to interval function having cycles on $\mathbb{R}$ of a certain order must also have cycles other orders. The orders which must exist are arranged in a hierarchy called Sharkovskii's ordering.

Only by talking of loops in the Collatz Conjecture directly from one odd number to the next, i.e. of the function $f(x)=\dfrac{3x+1}{2^{v_2(3x+1)}}$ is it possible for ST to apply. This is because the existence of the trivial $3$-cycle in the conventional formulation is immediately contradictory, while the $1$-cycle in the $2\mathbb{N}-1\to2\mathbb{N}-1$ formulation is not.

Since $\mathbb{R}$ is uncountable it seems likely such a proof would require a morphism from an interval of $\mathbb{R}$ to some uncountable superset $S$ of $2\mathbb{N}-1$ such that $f(x)$ in $S$ is a continuous function in $\mathbb{R}$.

Sequences and cycles in $2\mathbb{N}-1$ are of course isomorphic to a wide range of sequences and cycles which are isometric in some valuation $\lvert x\rvert_{2\times}$. The true, possible, extent of $S$ therefore is governed by our capacity to define some valuation $\lvert x\rvert_{2\times}$ which is sufficiently expressive in measuring powers of $2$ to project every $x\in S$ down to a unique element $n$ of $2\mathbb{N}-1$ and the valuation $\lvert x\rvert_{2\times}$ such that $x=n\lvert x\rvert_{2\times}^{-1}$. The 2-adic valuation over $\mathbb{N}$ is such an example. There's a high probability we require here some extension of the 2-adic valuation to some uncountable superset of $\mathbb{N}$ which is capable of measuring non-integer powers of $2$ to sufficient degree that it captures the full structure of $\mathbb{R}$.

The morphism to $\mathbb{R}\to S$ would probably require the property that numbers in $S$ of the form $x\times\lvert x\rvert_{2\times}\in(2\mathbb{N}-1)$ are mapped to an interval in $\mathbb{R}$.

This is necessary because proper fractions which are not dyadic, DO have nontrivial cycles in this extension of the Collatz conjecture. Therefore the morphism would need to isolate the integers, proper dyadic fractions, (and any extension thereof satisfying $x\times\lvert x\rvert_{2\times}\in(2\mathbb{N}-1)$ to some interval of $\mathbb{R}$ and map the other numbers to other segments of $\mathbb{R}$

Furthermore, for the function $f(x)$ to be well-defined $2^{v_2(x)}$ must be extended so as to retain isometry as measured by $\lvert x\rvert_{2\times}$ of all orbits of $f$ in $S$. The appropriate extension of $2^{v_2(x)}$ is of course the inverse of $\lvert x\rvert_{2\times}$ and the successor relation defined by the extended form of $f$ can be defined by:

$x_{n+1}=\lvert x_0\rvert_{2\times}^{-1}(3x_n+1)\lvert 3x_n+1\rvert_{2\times}$

• But Collatz has a 3-cycle: $1\to4\to2\to1$. Nov 30 '17 at 12:07
• I'm sure there are examples of Collatz-type maps that have 3-cycles by your definition, that don't obey Sharkovski. Nov 30 '17 at 12:31
• For example, the $3n+5$ problem has $19\to31\to49\to19$. It should be easy to check whether it has any 2-cycles or 4-cycles. Nov 30 '17 at 12:38
• The idea of a coset using powers of $2$ is not that difficult to come up with. I had look at a similar construction for a bit, but you don't make such major headway. I'm not sure Sarkovskii applies per Gerry's remarks.
– JMJ
Dec 1 '17 at 0:11
• OK, then: please clarify "changes in direction", "cyclic space", "go outside of a linear bound", "come back into that bound from its other end", "nowhere nullipotent between equivalence classes". Dec 4 '17 at 22:10