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

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.