Kourovka Notebook Problem 21.73

Definitions and mathematical statement

For integers $m\ge1$ and $0\le r<m$, put $r(m)=\{r+km:k\in\mathbb Z\}$. Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, define a permutation $\tau$ of $\mathbb Z$ by interchanging $r_1+km_1$ with $r_2+km_2$ for every $k\in\mathbb Z$ and fixing all other integers. Each such permutation is an involution, called a class transposition. Set \[ \operatorname{CT}(\mathbb Z) =\langle\tau_{r_1(m_1),r_2(m_2)}: r_1(m_1)\cap r_2(m_2)=\varnothing\rangle \le\operatorname{Sym}(\mathbb Z). \] Products mean composition of permutations. Disjointness can be checked arithmetically: the two residues must differ modulo $\gcd(m_1,m_2)$.

An input element is encoded by a finite word in class transpositions, with each letter specified by its four integer parameters. Different words may represent the same permutation. The conjugacy decision problem takes two such words, representing $g,h$, and asks whether \[ \exists u\in\operatorname{CT}(\mathbb Z)\quad u^{-1}gu=h. \] Is there an algorithm that halts and gives the correct answer for every pair of valid input words?

The possible conjugator may use class transpositions and moduli that do not occur in either input; it is not restricted to the subgroup generated by the displayed letters. Conversely, conjugacy in the full symmetric group of $\mathbb Z$ is insufficient: the conjugator must belong to $\operatorname{CT}(\mathbb Z)$. No bound on running time or on the length of a conjugating word is requested.

Short English statement

Is conjugacy decidable for permutations of the integers expressed as finite products of class transpositions?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2582 (KOU-21.73), Kourovka Notebook - New Problems, Issue 21. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 The Kourovka Notebook, 21st edition, new problems, Problem 21.73. Expanded formulation of the supplied catalogue statement. https://arxiv.org/pdf/1401.0300v47.