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.


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

  • $\begingroup$ 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$. $\endgroup$ – user334732 Oct 30 '18 at 12:23
  • $\begingroup$ 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. $\endgroup$ – user334732 Oct 30 '18 at 12:23
  • $\begingroup$ 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$ $\endgroup$ – user334732 Oct 30 '18 at 12:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.