# Groups generated by 3 involutions

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.

1. Is it algorithmically decidable whether all orbits on $\mathbb{Z}$ under the action of a group generated by 3 given class transpositions are finite?

2. Is it algorithmically decidable whether a group generated by 3 given class transpositions acts transitively on the set of nonnegative integers in its support (i.e. set of moved points)?

Added on Dec 11, 2013: This question will appear as Problem 18.47 in:

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

Remarks:

Ad 1.: A hard case is $G = \left\langle\tau_{0(2),1(2)}, \tau_{0(5),4(5)}, \tau_{1(4),0(6)}\right\rangle$. For example we have $|32^G| = 6296$ and $|25952^G| = 245719352$, and the largest point in the latter orbit is about $10^{5759}$. The finiteness of the orbit $173176^G$ is not known to the author so far.

EDIT: In the meantime, the length of the cycle of $g := \tau_{0(2),1(2)} \cdot \tau_{0(5),4(5)} \cdot \tau_{1(4),0(6)}$ containing 173176 has been computed by Jason B. Hill (http://mail.gap-system.org/pipermail/forum/2012/003948.html) -- it is 47610700792, and the largest point in the cycle is about $10^{76785}$. An earlier attempt of the same computation ended without success after one week of CPU time (http://mail.gap-system.org/pipermail/forum/2012/003915.html). Possibly the cycle length is also the orbit length $|173176^G|$.

Ad 2.: A hard case is $G = \left\langle\tau_{1(2),4(6)}, \tau_{1(3),2(6)}, \tau_{2(3),4(6)}\right\rangle$. As the question whether this group acts transitively on $\mathbb{N} \backslash 0(6)$ is equivalent to Collatz' $3n+1$ conjecture (cf. http://en.wikipedia.org/wiki/Collatz_conjecture), likely only a negative answer might be given without solving a known open problem. This will likely also not be easy -- at least unless someone has e.g. a good idea on how to encode arbitrary computations with just 3 class transpositions.

Added on Apr 24: An easy case is $G = \left\langle\tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{1(2),2(4)}\right\rangle$. By means of computation it can be checked that this group acts at least 5-transitively on $\mathbb{N}_0$.

• I can't claim to understand in any detail your question although I get the gist; but I may be able to mention an equivalence to the $G = \left\langle\tau_{1(2),4(6)}, \tau_{1(3),2(6)}, \tau_{2(3),4(6)}\right\rangle$ case which might be helpful for you. If you consider the positive integers $\equiv\pm1\pmod6$, i.e. the multiplicative monoid generated by primes greater than $3$, and complete the positive integers using the multiplicative cosets $\langle2\rangle\langle3\rangle$ then the function $f(x)=3x+2^{\nu_2(x)}\cdot3^{\nu_3(x)}$ acting on these cosets commutes with $3x$ and $2x$. – user334732 Oct 30 at 12:23
• Then 2-adically, the question of what these sets do in the vicinity of the maps from $-\frac{2^p}{3^q}\mapsto0$ and the assertion that sequences $S_n:x_{n+1}=f(x_n)$ can only approach $0$ by passing through the set $\frac{2^p}{3^q}$ is equivalent to the Collatz conjecture. I'm pretty sure $f$ is continuous in $\lvert\cdot\rvert_2$ given an appropriate treatment of the cosets. – user334732 Oct 30 at 12:23
• Your mention of involutions piqued my interest because this treatment of the Collatz conjecture has some interesting relationships between $x$ and $-x$ in that the sequence of positive integers which approaches $0$ via the map $x\mapsto 4x$ is reflected in a certain subset of the negative integers which approach $0$ via the map $-x\mapsto -2x$ – user334732 Oct 30 at 12:31