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

Question

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...

Answer 1

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$

Answer 2

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}$