Kourovka Notebook Problem 18.47

Definitions and mathematical statement

Let $\mathcal C$ denote the class of permutations of ${\mathbb{Z}}$ called class transpositions in Kourovka Notebook Problem 17.57. The supplied record refers to that definition but does not include it. Consequently, the admissible inputs and their effective encoding remain unspecified in this draft; no definition of $\mathcal C$ is being inferred.

For three given elements $\tau_1,\tau_2,\tau_3\in\mathcal C$, let \[ G=\langle\tau_1,\tau_2,\tau_3\rangle\leq\operatorname{Sym}({\mathbb{Z}}). \] For $x\in{\mathbb{Z}}$, define its orbit by $Gx=\{g(x):g\in G\}$. Define the support of the action and its nonnegative part by \[ \operatorname{supp}(G)=\{x\in{\mathbb{Z}}:\exists g\in G,\ g(x)\neq x\}, \qquad S_G=\operatorname{supp}(G)\cap{\mathbb{Z}}_{\geq0}. \] The two algorithmic questions, asked separately, are:

1. (a) Is there an algorithm which, on every admissible encoded triple of class transpositions, halts and correctly decides whether \[ \forall x\in{\mathbb{Z}},\qquad |Gx|<\infty? \] There is no requirement here that the finite orbit sizes have a common finite bound.
2. (b) Is there an algorithm which, on every admissible encoded triple, halts and correctly decides whether $G$ acts transitively on the set $S_G$? If $S_G$ is nonempty and invariant under $G$, transitivity means \[ \forall x,y\in S_G\ \exists g\in G,\qquad g(x)=y. \] The supplied record does not explain whether the missing definition guarantees invariance of $S_G$, or how an empty $S_G$ is to be treated. Without invariance, the displayed orbit condition still makes sense, but does not itself define a restricted action on $S_G$. Thus the intended decision predicate on such inputs requires clarification.

The source identifies the following as a difficult case: \[ H=\left\langle \tau_{1(2),4(6)},\ \tau_{1(3),2(6)},\ \tau_{2(3),4(6)} \right\rangle. \] It asserts that $H$ acts transitively on ${\mathbb{N}}\setminus0(6)$ if and only if Collatz' $3n+1$ conjecture is true. With the usual interpretation of $0(6)$ as the multiples of $6$, the indicated set is \[ E=\{n\in{\mathbb{Z}}_{>0}:6\nmid n\}. \] For specificity, Collatz' conjecture states that, for \[ T(n)=\begin{cases} n/2,&n\equiv0\pmod2,\\ 3n+1,&n\equiv1\pmod2, \end{cases} \qquad n\in{\mathbb{Z}}_{>0}, \] one has $\forall n\in{\mathbb{Z}}_{>0}\ \exists k\in{\mathbb{Z}}_{\geq0}$ such that $T^k(n)=1$. The claimed equivalence is retained as a supplied source assertion, not as an independently verified result. The permutations denoted by the three displayed class-transposition symbols cannot be reconstructed precisely from this record alone.

Short English statement

For a group generated by three given class transpositions of ${\mathbb{Z}}$, ask separately whether an algorithm can decide that every orbit is finite, and whether the group acts transitively on the nonnegative integers in its support. The source connects a specific example with Collatz' conjecture. The definition and encoding of class transpositions are missing, and the restricted-action and empty-set conventions in part (b) need clarification.

Sources

• Local UnsolvedMath registry, supplied complete source record: permanent ID $701476$, exact source code catalogue entry, title Kourovka Notebook Problem 18.47; upstream revision d371ee917ac9647fbb06cd6fc529deec6f3dda82. The registry labels the problem open; this is supplied status metadata, not an independently verified assessment.
• The supplied attribution is to S. Kohl, proposed in 2014. The supplied bibliographic source is The Kourovka Notebook (Unsolved Problems in Group Theory), 18th issue (2014), Problem 18.47, as included in the stated 21st-issue edition (2026), arXiv:1401.0300v48. The registry describes the collection as edited by E. I. Khukhro and V. D. Mazurov.
• The statement refers to Kourovka Notebook Problem 17.57 for the definition of class transpositions. That definition is not included in the supplied record. The source attribution and the asserted Collatz equivalence have not been independently checked.