Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 = <\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 (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 = <\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. 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 = <\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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.