47

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.

Question: Let $G < {\rm Sym}(\mathbb{Z})$ be a group generated by $3$ class transpositions, and assume that the integers $0, \dots, 42$ all lie in the same orbit under the action of $G$ on $\mathbb{Z}$. Is the action of $G$ on $\mathbb{N}_0$ necessarily transitive?

Remarks:

  • When replacing $42$ by $41$, the answer obviously gets negative since the finite group $$ G \ := \ \langle \tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{0(7),6(7)} \rangle $$ acts transitively on the set $\{0, \dots, 41\}$. Therefore if true, the assertion is sharp.

  • There is computational evidence suggesting that there is, say, "a reasonable chance" that the answer is positive.

  • A positive answer would mean that groups generated by $3$ class transpositions are "well-behaved" in the sense that for deciding transitivity, looking at very small numbers is sufficient, and that for larger numbers "nothing can happen any more".

    Added on Jun 20, 2015: A positive answer would however not imply that all questions on groups generated by $3$ class transpositions are algorithmically decidable.

  • A positive answer would imply the Collatz conjecture. On the other hand, if the Collatz conjecture holds, this would (by far!) not imply a positive answer to the question.

    Added on Jun 20, 2015: The reason why a positive answer would imply the Collatz conjecture is that the group $$ C := \langle \tau_{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{1(4),2(6)} \rangle $$ acts transitively on $\mathbb{N}_0$ if and only if the Collatz conjecture holds.

  • There is a related question here.

Added on Jun 20, 2015:

  • Example of a group which does act transitively: the group $$ G := \langle \tau_{0(2),1(2)}, \tau_{0(3),2(3)}, \tau_{1(2),2(4)} \rangle $$ acts at least $5$-transitively on $\mathbb{N}_0$.

  • Example of an infinite group $G$ such that the numbers $0, \dots, 25$ all lie in the same orbit under the action of $G$ on $\mathbb{Z}$, but which likely does not act transitively on $\mathbb{N}_0$: $$ G := \langle \tau_{0(2),1(2)}, \tau_{0(2),1(4)}, \tau_{0(6),5(9)} \rangle $$

  • (Easy case.) The answer is positive for groups generated by $3$ class transpositions which interchange residue classes with the same moduli (this is the case where no multiplications and no divisions occur). Transitivity on $\mathbb{N}_0$ obviously cannot occur in this case. More precisely, if we have a group generated by $k$ such class transpositions, the length of an orbit is bounded above by $a_k$, where $a_0 = 1$ and $a_{k+1} = a_k \cdot (a_k + 1)$.

  • Since HJRW suggested to look for "undecidability phenomena": so far I don't know any for groups generated by $3$ class transpositions, but there are groups generated by $4$ class transpositions which have finitely generated subgroups with unsolvable membership problem.

    For example, putting $\kappa := \tau_{0(2),1(2)}$, $\lambda := \tau_{1(2),2(4)}$, $\mu := \tau_{0(2),1(4)}$ and $\nu := \tau_{1(4),2(4)}$, the group $V := \langle \kappa, \lambda, \mu, \nu \rangle$ is isomorphic to Thompson's group V. Since the free group of rank $2$ and $V \times V$ both embed into $V$, it follows from a result of Mihailova that $V$ has subgroups with unsolvable membership problem.

    Side remark: $V$ is actually also the group generated by all class transpositions interchanging residue classes modulo powers of $2$; in general, groups may get a lot more complicated once the moduli of the residue classes interchanged by the generators are not all powers of the same prime.

Update of Nov 10, 2016:

Unfortunately the answer to the question as it stands turned out to be negative. -- These days I found a counterexample: put $$ G := \langle \tau_{0(2),1(2)}, \tau_{0(2),3(4)}, \tau_{4(9),2(15)} \rangle. $$ Then all integers $0, 1, \dots, 87$ lie in one orbit under the action of $G$ on $\mathbb{Z}$, but $G$ is not transitive on $\mathbb{N}_0$ since $88$ lies in another orbit.

The crucial feature of this example appears to be that intransitivity is forced by the existence of a nontrivial partition of $\mathbb{Z}$ into unions of residue classes modulo $180$ which $G$ stabilizes setwisely. The modulus $180$ happens to be the least common multiple of the moduli of the residue classes interchanged by the generators of $G$.

This suggests to reformulate the question as follows:

Question (new version): Let $G < {\rm Sym}(\mathbb{Z})$ be a group generated by $3$ class transpositions, and let $m$ be the least common multiple of the moduli of the residue classes interchanged by the generators of $G$. Assume that $G$ does not setwisely stabilize any union of residue classes modulo $m$ except for $\emptyset$ and $\mathbb{Z}$, and assume that the integers $0, \dots, 42$ all lie in the same orbit under the action of $G$ on $\mathbb{Z}$. Is the action of $G$ on $\mathbb{N}_0$ necessarily transitive?

Remarks:

  • If true, the assertion is still sharp in the sense that the bound $42$ cannot be replaced by $41$ (cf. the first remark on the original question).

  • It is conceivable that the assertion needs to be further weakened a little by assuming that $G$ does not setwisely stabilize any union of residue classes except for $\emptyset$ and $\mathbb{Z}$. (Also in this case a positive answer to the question would still imply the Collatz conjecture.)

Added on May 15, 2018: This question has appeared as Problem 19.45 in:

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

Stefan Kohl
  • 19,498
  • 21
  • 73
  • 136
  • 2
    Which instance of the problem implies 3n+1? This looks very interesting! – Adam Przeździecki Jun 15 '15 at 15:13
  • 3
    @AdamPrzeździecki: The group $C := \langle \tau_{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{1(4),2(6)} \rangle$ acts transitively on $\mathbb{N}0$ if and only if the Collatz conjecture holds. By the way, this group has the additional property that it shares the first two generators with the group $V := \langle \tau{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{0(2),1(4)}, \tau_{1(4),2(4)} \rangle$ which is isomorphic to Thompson's group V (where the generators correspond to Higman's generators $\kappa$, $\lambda$, $\mu$ and $\nu$). – Stefan Kohl Jun 15 '15 at 16:17
  • What is $N_0$? The non-negative integers? – Gerry Myerson Jun 15 '15 at 23:43
  • @GerryMyerson: Yes, it is. – Stefan Kohl Jun 16 '15 at 08:55
  • 1
    Do you have more information about the presentation of such a group? For instance, what is the order of the product of two of these involutions? Looking at the group $G$ in your counter-example for $n=41$, I'm seeing 2,3 and 7 and thinking Hurwitz group. I don't know if there really is a connection, though... If there were, then perhaps the theory of triangle groups might help... Do you even know that, under your supposition, the group $G$ is infinite? – Nick Gill Jun 16 '15 at 09:17
  • 1
    @NickGill: The group $G$ which acts transitively on ${0,\dots,41}$ is finite -- as I wrote. Its order is 384072192000. The group $C$ is infinite -- e.g. any product of two generators has infinite order. – Stefan Kohl Jun 16 '15 at 09:25
  • @NickGill: The finite group $G$ acts on the set ${0,\dots,41}$ like $\tilde{G} := \langle$ (0,1)(2,3)(4,5)(6,7)(8,9)(10,11)(12,13)(14,15) (16,17)(18,19)(20,21)(22,23)(24,25)(26,27)(28,29)(30,31)(32,33) (34,35)(36,37)(38,39)(40,41), (0,2)(3,5)(6,8)(9,11)(12,14)(15,17)(18,20)(21,23)(24,26)(27,29)(30,32) (33,35)(36,38)(39,41), (0,6)(7,13)(14,20)(21,27)(28,34)(35,41) $\rangle < {\rm S}_{42}$. – Stefan Kohl Jun 16 '15 at 09:35
  • 1
    Sorry, Stefan, my last question was not clear: I wanted to know if you can easily tell when $G=\langle a,b,c\rangle$ is infinite, for arbitrary choices of $a,b$ and $c$? – Nick Gill Jun 16 '15 at 10:27
  • @NickGill: In practice, yes -- I have done this e.g. for all 52394 triples of class transpositions interchanging residue classes with moduli $\leq 6$ -- of these, 21948 generate finite groups, and 30446 generate infinite groups. Though I don't know what the worst-case complexity is. – Stefan Kohl Jun 16 '15 at 10:37
  • @NickGill: That said, in case that no generator interchanges residue classes with different moduli, finiteness is immediate -- this makes up 6545 of the 21948 triples mentioned above for which the group is finite. As to possible orders of products of two class transpositions, see this question. – Stefan Kohl Jun 16 '15 at 22:32
  • Thanks for your replies Stefan. One last thing: can you prove your conjecture for the situation where no generator interchanges residue classes with different moduli? In light of your last comment, I guess you want to show that no such group can have an orbit containing {0,...,42}. This would already seem kind of surprising to me. (Although maybe that's just my ignorance...) – Nick Gill Jun 17 '15 at 09:55
  • @NickGill: I haven't explicitly written it down so far, but it is likely straightforward to show the following: Define the sequence $(a_n)$ by $a_0 := 1$ and $a_{n+1} := a_n(a_n + 1)$ for any $n \in \mathbb{N}_0$. Then there is a group generated by $n$ class transpositions each of which interchanges residue classes with the same moduli such that all integers $0, \dots, C$ lie in the same orbit if and only if $C < a_n$. (One direction is obvious.) – Stefan Kohl Jun 17 '15 at 10:21
  • That statement looks crucial to me! If you can write down a proof of that, then this would be a most illuminating addition to the question. To me, the number "42", despite Douglas Adam's assertions to the contrary, seems a rather random element in the set-up that you have in this question. Your comment changes all that, though (for me). – Nick Gill Jun 17 '15 at 10:25
  • Can you be a bit more precise about your assertion that 'A positive answer would mean that groups generated by 3 class transpositions are "well-behaved"'. Perhaps one could disprove the conjecture by exhibiting undecidability phenomena among these groups? – HJRW Jun 18 '15 at 13:49
  • 1
    @HJRW: "Well-behaved" here means only "well-behaved in the indicated sense", not more. It is quite possible that other questions on groups generated by 3 class transpositions are algorithmically undecidable, and this would not necessarily be incompatible with a positive answer to the question. For groups generated by 4 class transpositions, obtaining such results is a bit easier -- e.g. there are groups generated by 4 class transpositions which have finitely generated subgroups with unsolvable membership problem. I will soon update my question (also addressing Nick Gill's suggestions). – Stefan Kohl Jun 18 '15 at 22:41
  • 5
    The role of 41 is that if $1/p+1/q+1/r<1$ for natural numbers $p,q,r$, then $1/p+1/q+1/r\leq41/42$. It is clear that for moduli-preserving transformations to be transitive $1/p+1/q+1/r \geq 1$ is necessary, since otherwise a set of positive density is fixed. The case when moduli are not preserved is much more complicated. – Andreas Thom Jun 19 '15 at 05:33
  • @AndreasThom: Essentially yes, and this is what the number 41 here comes from -- though you need to be a bit careful since the support of a class transposition is not one, but two residue classes. Your last sentence is doubtlessly true! – Stefan Kohl Jun 19 '15 at 09:17
  • Stupid question -- why is transitivity in the "Added on June 20th" Collatz comment equivalent to Collatz? I can believe Collatz would imply such a statement, but equivalence seems to me to be harder because in the group theory formulation you can choose which move to make sometimes. For example if x is 1 mod 4 then in the group theory problem you have three choices for a move, whereas in Collatz you only have one. In particular I don't see why the conjecture implies Collatz (but maybe I'm just being dumb). – eric Jul 21 '15 at 17:04
  • @eric: You start from the group $G := \langle \tau_{1(2),4(6)}, \tau_{1(3),2(6)}, \tau_{2(3),4(6)} \rangle$, and look at its action on the Collatz tree. You can easily convince yourself that regardless of which of the three generators you apply, you cannot leave the tree, but that you can always pass on to adjacent vertices as long as these are not divisible by $6$ -- this means that $G$ acts transitively on $\mathbb{N} \setminus 0(6)$ if and only if the Collatz conjecture holds. (continued in next comment.) – Stefan Kohl Jul 21 '15 at 21:34
  • @eric: (continued.) Now getting from $G$ to the mentioned group $C$ (and getting rid of the fixed point set $0(6)$) is done via a suitable transformation of the tree and choosing appropriate class transpositions as generators of the group. -- This latter step is not obvious -- let me know if you are interested in details. – Stefan Kohl Jul 21 '15 at 21:36
  • I see. Rephrasing -- to get that the transitivity of $G$ implies Collatz you prove that $n$ terminates for the Collatz algo iff $g(n)$ does, as $g$ runs through the generators. – eric Jul 22 '15 at 21:28
  • @eric: Yes, exactly. – Stefan Kohl Jul 22 '15 at 21:52
  • 15
    It would be nice if no one upvotes this, because at the moment it has 42 upvotes. :-) – Joseph O'Rourke Nov 10 '16 at 20:44
  • 2
    @JosephO'Rourke I was about to! Last second I have realized this marvelous fact. – Wojowu Nov 10 '16 at 21:59
  • Just a query on a technicality. If the equivalence $C := \langle \tau_{0(2),1(2)}, \tau_{1(2),2(4)}, \tau_{1(4),2(6)} \rangle$ connects $1,4$ two ways, does this mean it fails to act transitively? – it's a hire car baby Jun 14 '19 at 17:54
  • @AndreasThom supposing precisely one pair of elements was connected two ways, how would this affect your finely balanced $41/42$ or e.g. $31/30$, as is the case for $1/2+1/3+1/5$? – it's a hire car baby Jun 14 '19 at 17:57
  • I am confused by the statement "The answer is positive for groups generated by 3 class transpositions which interchange residue classes with the same moduli. Transitivity on $\mathbb{N}0$ obviously cannot occur in this case." Look at the subgroup generated by $\tau{0(2), 1(2)}$ and $\tau_{1(2), 2(2)}$. This is the infinite dihedral group, and acts transitively on $\mathbb{Z}$. – David E Speyer Apr 05 '22 at 15:35
  • @DavidESpeyer In the first line of the question, it is said "Let $r(m)$ denote the residue class $r + m\mathbb{Z}$, where $0 \leq r < m$". -- This is to exclude $2(2)$, $7(3)$ and the like. -- And that condition is also very essential to ensure that the groups indeed act on $\mathbb{N}_0$ -- i.e. don't move nonnegative integers to negative integers and vice versa. – Stefan Kohl Apr 05 '22 at 15:59
  • Thanks, got it. – David E Speyer Apr 05 '22 at 16:07
  • If you're still interested in this question, this may be of interest to you: https://www.researchgate.net/publication/253568656_Infinite_covering_systems_of_congruences_which_don%27t_exist It's not that obviously related, but also I think the methods in it may be useful to you. Also, I think your approach in this question will fail because the things to exchange are $x,\frac12(3x+2^{\nu_2(x)})$ and then to show that this acts transitively, and I don't think this pair can be translated into a finite set of residue classes. – it's a hire car baby May 05 '22 at 08:49

1 Answers1

3

Here's an extended comment, about (un)decidibility.

First the Mihailova fact should rather be understood as: undecidability of the subgroup membership problem (for f.g. subgroups) can occur even in well-behaved groups such as the product of two free groups. Actually, for arbitrary subgroups, undecibility of the membership problem occurs even in the free groups itself, just because there are uncountably many subgroups!

The main decidability issue is the word problem, and I claim that it is decidable in all f.g. groups made up of class permutations. Here's a proof.

We call a class, or semiperiodic self-map of $\mathbf{Z}$ a self-map which, for some $N$, is affine (with rational coefficients) in restriction to any coset $N\mathbf{Z}+n$. This means that the function $n\mapsto f(N+n)-f(n)$ is $N$-periodic, or also that there exists an $n$-periodic sequences $(a_n)$ and $(v_n)$ of rationals such that $f(uN+n)=uv_n+a_n$ for all $n,u$. Let's call this $N$-semiperiodic. If $f$ is $N$-semiperiodic and $g$ is $M$-semiperiodic then $f\circ g$ is $NM$-semiperiodic. Let $[f]$ be the minimal semiperiod of $f$: this shows $[fg]\le [f][g]$ for all $f,g$.

Therefore the set $E$ of semiperiodic self-maps is a submonoid of the monoid of selfmaps, and moreover given any finite subset $S\subset E$ generating a submonoid $G$ we have a simple algorithm to solve the word problem in $G$ (which for monoids means determine whether two words define the same element.

First, observe that any $f\in E$ is computable as a self-map: this is just because it is effectively determined by $[f]$ affine functions (thus encoded by $2[f]$ rational numbers).

Let $N\le\prod_{f\in S}[f]$ be a common semiperiod for all $f\in S$. Given $n$ and $f,g\in S^n$, the self-map $f-g$ is $N^{2n}$-semiperiodic, and moreover it is effectively computable. So computing $f-g$ on $\{1,\dots,N^{2n}\}$, which gives either identically zero or not, will determine whether $f=g$.

This applies in particular to the case of a finitely generated subgroup.

I should add that this algorithm is uniform in $S$, in the sense that you can input $S$ (each element being given as a semiperiod, and $2N$ rationals defining $N$ affine functions -- btw there is an obvious efficient way to check whether it indeed maps integers into themselves), and input two words in the alphabet over $S$ and the machine answers whether these are equal.

In decidibility problems here, it should be kept in mind that $S$ is part of the input, for instance one can wonder whether one can input three class transpositions and determine whether the action on the integers is transitive, resp. have all elements of $\{1,\dots,42\}$ in the same orbit.

YCor
  • 60,149
  • The solvability of the word problem for finitely generated subgroups of groups generated by class transpositions is obvious, I'd say (I mentioned it in a line in this paper, and there is a concrete, practical algorithm implemented here). Though I'm not sure why you call it "the main decidability issue". – Stefan Kohl Jun 21 '15 at 10:46
  • OK I included it because there was no mention of it in the above discussion; I agree it is indeed obvious (but the remark that the algorithm is uniform in the generating subset is important although obvious as well). – YCor Jun 21 '15 at 10:49
  • By the way -- you write "If $f$ is $N$-semiperiodic and $g$ is $M$-semiperiodic then $f\circ g$ is $NM$-semiperiodic (or even $\mathrm{lcm}(M,N)$-semiperiodic)." The statement before the brackets is correct, but imagine what impact on the Collatz conjecture it would have if the one in brackets would hold ... – Stefan Kohl Jun 21 '15 at 13:02
  • OK, corrected. Indeed $f:2n\mapsto n,2n+1\mapsto 0$ satisfies $f\circ f: 4n\mapsto n$, (else)$\mapsto 0$. – YCor Jun 21 '15 at 14:13