Transitivity on $\mathbb{N}_0$ -- a 42 problem

Question

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.

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: Unsolved Problems in Group Theory. Editors V. D. Mazurov, E. I. Khukhro. 19th Edition, Novosibirsk 2018.

Answer 1

Here's an extended comment, about (un)decidibility.

First the Mihailova fact should rather be understood as: undecidability of the subgroup membership problem (for f.g. subgroups) can occur even in well-behaved groups such as the product of two free groups. Actually, for arbitrary subgroups, undecibility of the membership problem occurs even in the free groups itself, just because there are uncountably many subgroups!

The main decidability issue is the word problem, and I claim that it is decidable in all f.g. groups made up of class permutations. Here's a proof.

We call a class, or semiperiodic self-map of $\mathbf{Z}$ a self-map which, for some $N$, is affine (with rational coefficients) in restriction to any coset $N\mathbf{Z}+n$. This means that the function $n\mapsto f(N+n)-f(n)$ is $N$-periodic, or also that there exists an $n$-periodic sequences $(a_n)$ and $(v_n)$ of rationals such that $f(uN+n)=uv_n+a_n$ for all $n,u$. Let's call this $N$-semiperiodic. If $f$ is $N$-semiperiodic and $g$ is $M$-semiperiodic then $f\circ g$ is $NM$-semiperiodic. Let $[f]$ be the minimal semiperiod of $f$: this shows $[fg]\le [f][g]$ for all $f,g$.

Therefore the set $E$ of semiperiodic self-maps is a submonoid of the monoid of selfmaps, and moreover given any finite subset $S\subset E$ generating a submonoid $G$ we have a simple algorithm to solve the word problem in $G$ (which for monoids means determine whether two words define the same element.

First, observe that any $f\in E$ is computable as a self-map: this is just because it is effectively determined by $[f]$ affine functions (thus encoded by $2[f]$ rational numbers).

Let $N\le\prod_{f\in S}[f]$ be a common semiperiod for all $f\in S$. Given $n$ and $f,g\in S^n$, the self-map $f-g$ is $N^{2n}$-semiperiodic, and moreover it is effectively computable. So computing $f-g$ on $\{1,\dots,N^{2n}\}$, which gives either identically zero or not, will determine whether $f=g$.

This applies in particular to the case of a finitely generated subgroup.

---

I should add that this algorithm is uniform in $S$, in the sense that you can input $S$ (each element being given as a semiperiod, and $2N$ rationals defining $N$ affine functions -- btw there is an obvious efficient way to check whether it indeed maps integers into themselves), and input two words in the alphabet over $S$ and the machine answers whether these are equal.

In decidibility problems here, it should be kept in mind that $S$ is part of the input, for instance one can wonder whether one can input three class transpositions and determine whether the action on the integers is transitive, resp. have all elements of $\{1,\dots,42\}$ in the same orbit.