MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 = <\tau_{0(2),1(2)}, \tau_{0(5),4(5)}, \tau_{1(4),0(6)}>$. 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 ( -- 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 ( Possibly the cycle length is also the orbit length $|173176^G|$.

Ad 2.: A hard case is $G = <\tau_{1(2),4(6)}, \tau_{1(3),2(6)}, \tau_{2(3),4(6)}>$. As the question whether this group acts transitively on $\mathbb{N} \backslash 0(6)$ is equivalent to Collatz' $3n+1$ conjecture (cf., 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 = <\tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{1(2),2(4)}>$. By means of computation it can be checked that this group acts at least 5-transitively on $\mathbb{N}_0$.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.