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.
> <b>Question:</b> 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][2].
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][1].
**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][3]. 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.
**Update of Nov 10, 2016:**
Unfortunately the answer to the question as it stands turned out
to be negative. -- These days I found a counterexample: put
$$
G := \langle \tau_{0(2),1(2)}, \tau_{0(2),3(4)}, \tau_{4(9),2(15)} \rangle.
$$
Then all integers $0, 1, \dots, 87$ lie in one orbit under the action
of $G$ on $\mathbb{Z}$, but $G$ is not transitive on $\mathbb{N}_0$
since $88$ lies in another orbit.
The crucial feature of this example appears to be that intransitivity
is forced by the existence of a nontrivial partition of $\mathbb{Z}$
into unions of residue classes modulo $180$ which $G$ stabilizes setwisely.
The modulus $180$ happens to be the least common multiple of the
moduli of the residue classes interchanged by the generators of $G$.
This suggests to reformulate the question as follows:
> **Question (new version):** Let $G < {\rm Sym}(\mathbb{Z})$ be
> a group generated by $3$ class transpositions, and let $m$ be
> the least common multiple of the moduli of the residue classes
> interchanged by the generators of $G$. Assume that $G$ does not
> setwisely stabilize any union of residue classes modulo $m$
> except for $\emptyset$ and $\mathbb{Z}$, 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:*
- If true, the assertion is still sharp in the sense that the
bound $42$ cannot be replaced by $41$ (cf. the first remark
on the original question).
- It is conceivable that the assertion needs to be further weakened
a little by assuming that $G$ does not setwisely stabilize any
union of residue classes except for $\emptyset$ and $\mathbb{Z}$.
(Also in this case a positive answer to the question would
still imply the Collatz conjecture.)
**Added on May 15, 2018:** This question has appeared as Problem 19.45 in:
[Kourovka Notebook][4]: *Unsolved Problems in Group Theory.* Editors V. D. Mazurov, E. I. Khukhro. 19th Edition, Novosibirsk 2018.
[1]: https://mathoverflow.net/questions/112527/groups-generated-by-3-involutions
[2]: https://en.wikipedia.org/wiki/Collatz_conjecture
[3]: https://en.wikipedia.org/wiki/Thompson_groups
[4]: https://kourovka-notebook.org/