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.

Question: Let $G < {\rm Sym}(\mathbb{Z})$ be a group generated by $3$ class transpositions, and assume that the integers $0, \dots, 42$ all lie in the same orbit under the action of $G$ on $\mathbb{Z}$. Is the action of $G$ on $\mathbb{N}_0$ necessarily transitive?

Remarks:

• When replacing $42$ by $41$, the answer obviously gets negative since the finite group $$ G \ := \ \langle \tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{0(7),6(7)} \rangle $$ acts transitively on the set $\{0, \dots, 41\}$. Therefore if true, the assertion is sharp.

• There is computational evidence suggesting that there is, say, "a reasonable chance" that the answer is positive.

• A positive answer would mean that groups generated by $3$ class transpositions are "well-behaved" in the sense that for deciding transitivity, looking at very small numbers is sufficient, and that for larger numbers "nothing can happen any more".

  Added on Jun 20, 2015: A positive answer would however not imply that all questions on groups generated by $3$ class transpositions are algorithmically decidable.

• A positive answer would imply the Collatz conjecture. On the other hand, if the Collatz conjecture holds, this would (by far!) not imply a positive answer to the question.

  Added on Jun 20, 2015: The reason why a positive answer would imply the Collatz conjecture is that the group $$ C := \langle \tau_{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{1(4),2(6)} \rangle $$ acts transitively on $\mathbb{N}_0$ if and only if the Collatz conjecture holds.

• There is a related question here.

Added on Jun 20, 2015:

• Example of a group which does act transitively: the group $$ G := \langle \tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{1(2),2(4)} \rangle $$ acts at least $5$-transitively on $\mathbb{N}_0$.

• Example of an infinite group $G$ such that the numbers $0, \dots, 25$ all lie in the same orbit under the action of $G$ on $\mathbb{Z}$, but which likely does not act transitively on $\mathbb{N}_0$: $$ G := \langle \tau_{0(2),1(2)}, \tau_{0(2),1(4)}, \tau_{0(6),5(9)} \rangle $$

• (Easy case.) The answer is positive for groups generated by $3$ class transpositions which interchange residue classes with the same moduli (this is the case where no multiplications and no divisions occur). Transitivity on $\mathbb{N}_0$ obviously cannot occur in this case. More precisely, if we have a group generated by $k$ such class transpositions, the length of an orbit is bounded above by $a_k$, where $a_0 = 1$ and $a_{k+1} = a_k \cdot (a_k + 1)$.

• Since HJRW suggested to look for "undecidability phenomena": so far I don't know any for groups generated by $3$ class transpositions, but there are groups generated by $4$ class transpositions which have finitely generated subgroups with unsolvable membership problem.

  For example, putting $\kappa := \tau_{0(2),1(2)}$, $\lambda := \tau_{1(2),2(4)}$, $\mu := \tau_{0(2),1(4)}$ and $\nu := \tau_{1(4),2(4)}$, the group $V := \langle \kappa, \lambda, \mu, \nu \rangle$ is isomorphic to Thompson's group V. Since the free group of rank $2$ and $V \times V$ both embed into $V$, it follows from a result of Mihailova that $V$ has subgroups with unsolvable membership problem.

  Side remark: $V$ is actually also the group generated by all class transpositions interchanging residue classes modulo powers of $2$; in general, groups may get a lot more complicated once the moduli of the residue classes interchanged by the generators are not all powers of the same prime.