Return to Question

Added on May 15, 2018: This question has appeared as Problem 19.45 in:

Kourovka Notebook: Unsolved Problems in Group Theory. Editors V. D. Mazurov, E. I. Khukhro. 19th Edition, Novosibirsk 2018.

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

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

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