Does $\frac{(3x+1)}{2^n}$ generate a partial ordering of the odd, positive integers?

Question

Taking $n,m\in\mathbb{N}$ and $n,m >0$ throughout.

Does the graph of the function $f(x)=\frac{(3x+1)}{2^n}$ generate a partial ordering of the odd integers? Because if it did, it would seem to me that this might imply no non-trivial loop in the Collatz conjecture.

More precisely:

If we define the idempotent function (excuse the brief/amateurish notation!):

$g(c.2^n)=c: c\in\{2m-1\}$

and the 2nd function:

$h(x)=3x+1$

and let $f(x)=h(g(x))$

Let us now define a relation $\leq$ by $x\leq y$ iff $f^n(x)=y$ for some $n\geq 0$. Now if this relation $\leq$ were a partial ordering of the odd integers then this would, would it not, mean for any two odd integers $a,b$ that any loop could only be of order $1$?

It would seem the known loop which fulfils $f^n(1)=1\forall n\in\mathbb{N}$ must be an identity, and therefore unique?

Posing the same question in an alternative approach way might be to change things up so that, instead of operating on integers, the function operates on equivalence classes of odd integers defined according to the number of applications of $f$ required to arrive at some arbitrary number (or class) - so for example $\{1, 5, 21, 85, 341, \ldots\}$ are all members of the same class one step away from $1$.

We see instantly that the odd numbers directly preceding $1$ are in the same class as $1$. And in fact it turns out, all numbers which lead after however long, to $1$, are also in the same class.

Perhaps therefore, this class forms an identity of some form in relation to the function $f$ and this equivalence class is therefore unique by virtue of being an identity, precluding the existence of any other loop?

Answer 1

The relation $\leq$ defined by $x\leq y$ iff $f^n(x)=y$ for some $n\geq 0$ is clearly reflexive and transitive, so it is a partial order iff it is antisymmetric. If it is not antisymmetric, then there exist distinct $x$ and $y$ such that $y=f^n(x)$ and $x=f^m(y)$ for some $y$, with $n,m>0$ since $x\neq y$. We then have $x=f^{n+m}(x)$. Since $x=1$ would imply $y=1$, this equation $x=f^{n+m}(x)$ thus gives a nontrivial loop in the Collatz function.

Conversely, if there is a nontrivial loop in the Collatz function, let $x\neq 1$ be some odd number in the loop. We then have $f^n(x)=x$ for some $n>0$. If $f(x)\neq x$, we have $n>1$ and then setting $y=f(x)$, we have $x\leq y$ and $y\leq x$, so $\leq$ is not antisymmetric. Otherwise, $f(x)=x$, so $3x+1=2^mx$ for some $m$. But $3x+1$ is relatively prime to $x$, so this can only happen if $x=1$, which we have assumed is not the case.

Thus the relation $\leq$ is a partial order iff there are no nontrivial loops in the Collatz function, and your question is just a slight restatement of the conjecture that there are no nontrivial loops in the Collatz function.

Answer 2

I'm not familiar with the term "partial ordering". But I think I understand what you mean, and that your idea is not solving the problem.

Actually, you start with the set of numbers, which transform to $1$ in one step: $\small 1 \leftarrow (1,5,21,85,\ldots\ {4^k-1\over 3 }, \ldots )$ Obviously there is another set which transforms $\small 5 \leftarrow (3,13,53,213,\ldots , {10 \cdot 4^k-1 \over 3}, \ldots )$, there is no such set $\small 21 \leftarrow ( ) $, but another one $\small 85 \leftarrow (113, 453, \ldots )$ all basing on the elements in the $\small 1 \leftarrow()$ set, and then this is recursively the same with the elements of the $\small 3 \leftarrow()$ set, of the $\small 113 \leftarrow ()$ set and so on infinitely.

The meaning of the Collatz conjecture can now be reformulated, that the complete tree, made from all those sets, contains all positive odd numbers (let's call this "pons").

But this is the crucial point: how do you know, that this tree does contain all pons?

Indeed, this lovely structure alone is not sufficient to ensure that all pons are contained; for instance, if you start with the negative numbers, you find three separate trees; one is rooting at $-1$ : $\small -1 \leftarrow (-1,-3,-11,-43,\ldots) $, one has a cyclic root $-5$ and $-7$ (I thought, perhaps "nest" like the bird's "nest"$\;^{1)}$ is a nice metapher) with the mutually linked sets $\small -5 \leftarrow (-7,-27,-107,-427,\ldots)$ and $\small -7 \leftarrow (-5,-19,-75, \ldots)$ with their two following subtrees of transforming sets, which are completely independent of the $\small -1 \leftarrow()$ set and its subtree.

The analoguous is btw. also valid for the 5x+1 problem, which has a similar tree, whose structure is the same as with the 3x+1-problem, but which needs at least $3$ independent trees to contain all positive odd numbers.

---

Well, this is a very unlucky situation, since the basic idea of this tree-construction looks very promising, and you're not the only one who slipped on this ice...

---

• $\;^{1)}$ Of course, for the original version of the Collatz transform these values are better known by the term "fixpoint" ($\small 1$ and $\small -1$) or "cyclic fixpoints" resp. "periodic fixpoints" ($\small (-5,-7)$) etc

• $\;^{2)}$ For the idea of defining equivalence-classes and an "height"-index of iteration-steps you may like the "bottlebrush-tree" image, which I have invented some years ago and shown in my older Collatz pages ( main-page and go then to "About numerical and graphical trees" ). The class- or in my notation: iteration-"height"- index is the nicely seen as the distance of one leaf to the root in the center.