MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the permutation of $\mathbb{Z}$ which interchanges $r_1+km_1$ and $r_2+km_2$ for every $k \in \mathbb{Z}$ and which fixes everything else.

The group $G := \langle \tau_{0(2),1(2)}, \tau_{1(2),4(6)}, \tau_{0(3),4(6)} \rangle$ has 3 orbits on $\mathbb{Z}$ -- one of them consists of the negative integers, and the other two form a partition of the nonnegative integers. The latter partition does look somewhat complicated.

There is computational evidence that the orbits have natural densities, where $0^G$ seems to have density about 0.685, and $2^G$ correspondingly seems to have density about 0.315. Also, both orbits seem to be approximately uniformly distributed on the residue classes (mod $m$), for every positive integer $m$. It seems that differences of consecutive members of an orbit are always odd.


  1. Is there an alternative description of the 2 orbits of the group $G$ on $\mathbb{N}_0$ (i.e. not just as "the orbits of $G$ on $\mathbb{N}_0$")?

  2. What are the natural densities of the orbits, if they exist? Are they rational, algebraic or transcendental?


The Collatz conjecture is equivalent to the assertion that the group $H := \langle \tau_{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{1(4),2(6)} \rangle$ acts transitively on $\mathbb{N}_0$.

Clearly the action of $G$ on $\mathbb{Z}$ is much easier to understand -- e.g. one can relatively easily count orbits. Nevertheless it is not a trivial case, thus one might hope that its investigation might provide some insights into the action of $H$ as well.


There are tables of the numbers less than 10000 in any of the 2 orbits of $G$ on $\mathbb{N}_0$: orbit1_10000.txt, orbit2_10000.txt. Larger versions with bound 1000000 rather than 10000 are available as well: orbit1_1000000.txt, orbit2_1000000.txt.

share|cite|improve this question

These are just an attempt to reformulate everything in a more convenient way.

  1. Let us define the following function on nonnegative integers (the definition can be simplified a bit, but I prefer to present it in this form): $$ f(n)=\begin{cases} 4n, & x=6n\; \text{ or }\;x=6n+1;\cr 4n+2, & x=6n+2\; \text{ or }\;x=6n+3;\cr 2n, & x=6n+4\; \text{ or }\;x=6n+5. \end{cases} $$ Then $f(x) < x$ for all $x>2$ and $x=1$, and $f(x)$ lies in the orbit of $x$. Moreover, it can be checked straightforwardly that for every two numbers interchanged by one of the generators, they have a common image under some iterations of $f$. This means that one orbit consists of all the numbers coming to $0$ after a sufficient number of iterations, and the other orbit consists of those coming to $2$.

  2. Now let us check what happens in this process. Surely one may concentrate only on the even numbers, since $f(2n)=f(2n+1)$ is always even. Thus we change the variable by $y=x/2$ and introduce the function $$ g(y)=\frac{f(2y)}2=\begin{cases} 2n, & y=3n;\cr 2n+1, & y=3n+1;\cr n, & y=3n+2\cr \end{cases} = \begin{cases} \lfloor y/3\rfloor, & 3\;\big|\; (y+1);\cr \lceil 2y/3\rceil, & \text{otherwise.} \end{cases} $$ Considering the preimages under $g$, we see that each $y$ generates the numbers $3y+2$ and $\lfloor 3y/2\rfloor$ lying in the $y$'s orbit, and all the numbers are generated by such process from $0$ and $1$ (or from $1$ and $2$), thus partitioning into two orbits.

  3. Now, if we denote by $\mu(n)$ the density of, say, elements of the first orbit on $[2n,3n)$, then we obtain $$ \mu(3n)=\frac{\mu(n)+2\mu(2n)}3. $$ It seems that this, together with the observation that $\mu(n)$ and $\mu(n+1)$ are close to each other, should suffice to see that the limiting density exists.

share|cite|improve this answer
+1. -- Thank you very much! -- Your function $f$ is notably nicer and easier to analyze than the one I had. -- My algorithms produced another such $f$, also with modulus 6, but one had to raise it to the 6th power in order to obtain a mapping which maps all sufficiently large $n$ to smaller numbers, which raised the modulus to 162. It would be nice to see a description of the orbits in an explicit way, i.e. not involving sequences (e.g. for some other such groups an orbit invariant is the parity of the sum of the binary digits, etc.). – Stefan Kohl Jun 8 '13 at 12:00
Your argument that the natural densities exist looks right to me, though I don't see so far from it whether their values are rational or not. – Stefan Kohl Jun 8 '13 at 12:00
1. Yes, I was looking for that, but it seems that the situation is harder here. 2. Yes, to find the density we need much more. – Ilya Bogdanov Jun 9 '13 at 5:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.