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

Definition / Question

Definition: 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: Which integers occur as orders of products of 2 class transpositions?

Added on Dec 8, 2013: The question whether it is true that only finitely many integers occur as orders of products of two class transpositions will appear as Problem 18.48 in:

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

Known results

The known finite orders of products of 2 class transpositions are the divisors of 60 except for 5, as well as 8, 24, 40, 42, 84, 120, 168 and 420. I do not know whether there are further, or even only whether there are finitely or infinitely many.

Among the 409965 unordered pairs of distinct class transpositions which interchange residue classes with moduli $\leq 12$, there are

  • 179470 whose product has order 6,

  • 83298 whose product has order 12,

  • 60208 whose product has order $\infty$,

  • 38818 whose product has order 2,

  • 14127 whose product has order 3,

  • 13491 whose product has order 4,

  • 10407 whose product has order 60,

  • 8918 whose product has order 30,

  • 976 whose product has order 20,

  • 218 whose product has order 10,

  • 32 whose product has order 15, and

  • 2 whose product has order 8.

The orders 24, 40, 42, 84, 120, 168 and 420 appear to be still more "seldom", and occur only for products of class transpositions which interchange residue classes with larger moduli.

Remarks / Background

  1. I asked this question on the Nikolaus Conference 2012 in Aachen. In response, Michael Cuntz found some possible orders which were not known to me at that time (namely 8, 24 and 42). Afterwards, a more systematic search by myself revealed the further possible orders 40, 84, 120, 168 and 420. The question though remains open.

  2. Some products of 2 class transpositions have infinite order, but the length of the longest cycle which intersects nontrivially with a set $\{1, \dots, n\}$ grows only logarithmically with $n$. This may fool the naive approach of estimating the order by taking a number of cycles and computing the least common multiple of their lengths.

  3. The set of all class transpositions of $\mathbb{Z}$ generates the infinite simple group discussed in the article

    A Simple Group Generated by Involutions Interchanging Residue Classes of the Integers. Math. Z. 264 (2010), no. 4, 927-938.

Examples

Minimal examples for the known orders are as follows ("minimal" means in this context that the maximum of the moduli of the involved residue classes is the smallest possible):

  • Order $\infty$: $\tau_{0(2),1(4)} \cdot \tau_{0(2),1(2)}$

  • Order 2: $\tau_{0(4),1(4)} \cdot \tau_{2(4),3(4)}$

  • Order 3: $\tau_{0(3),1(3)} \cdot \tau_{0(3),2(3)}$

  • Order 4: $\tau_{0(3),1(3)} \cdot \tau_{0(2),1(2)}$

  • Order 6: $\tau_{0(3),2(3)} \cdot \tau_{0(2),1(2)}$

  • Order 8: $\tau_{0(2),5(6)} \cdot \tau_{2(9),8(9)}$

  • Order 10: $\tau_{1(2),2(4)} \cdot \tau_{0(3),4(6)}$

  • Order 12: $\tau_{1(4),3(4)} \cdot \tau_{1(3),2(3)}$

  • Order 15: $\tau_{0(3),2(3)} \cdot \tau_{0(2),1(4)}$

  • Order 20: $\tau_{1(4),3(4)} \cdot \tau_{0(3),1(6)}$

  • Order 24: $\tau_{0(3),1(6)} \cdot \tau_{1(8),19(20)}$

  • Order 30: $\tau_{0(3),1(3)} \cdot \tau_{0(2),3(4)}$

  • Order 40: $\tau_{0(10),3(15)} \cdot \tau_{2(4),12(24)}$

  • Order 42: $\tau_{0(4),9(10)} \cdot \tau_{0(3),4(15)}$

  • Order 60: $\tau_{3(4),4(6)} \cdot \tau_{1(5),2(5)}$

  • Order 84: $\tau_{0(8),6(20)} \cdot \tau_{0(3),26(30)}$

  • Order 120: $\tau_{0(4),10(24)} \cdot \tau_{1(15),10(30)}$

  • Order 168: $\tau_{0(8),6(20)} \cdot \tau_{2(3),6(30)}$

  • Order 420: $\tau_{0(8),6(20)} \cdot \tau_{6(15),26(30)}$

The GAP package RCWA contains

  • a database of pairs of class transpositions which interchange residue classes with moduli $\leq 32$ and whose product has finite order not dividing 60, i.e. the "seldom" ones -- see here (162KB), and

  • a database of all 409965 pairs of class transpositions which interchange residue classes with moduli $\leq 12$, sorted by the order of their product -- see here (18MB).

share|improve this question
    
Could you give some examples with order $15$? –  Douglas Zare May 6 '13 at 17:41
    
Examples with order 15 are e.g. $\tau_{0(3),2(3)} \cdot \tau_{0(2),1(4)}$, $\tau_{2(3),1(6)} \cdot \tau_{1(4),3(8)}$ and $\tau_{5(6),8(12)} \cdot \tau_{2(9),8(9)}$. –  Stefan Kohl May 6 '13 at 18:00
1  
Is there a nice expanation for why 5 is not seen as an order in small examples? Gerhard "Ask Me About System Design" Paseman, 2013.05.06 –  Gerhard Paseman May 6 '13 at 18:42
    
@Gerhard: at least none that I know. –  Stefan Kohl May 6 '13 at 19:52
    
four of the "seldom" orders, 24, 84, 168, 420, are yielded by a pair with $(m_1,m_2) =(8,20)$. Is that a coincidence or rather just a pair you have chosen in your search? Maybe searching with (8,28) or (12,20) and some random numbers for the rest yields more orders? or (9,15)? just a suggestion into the blue... –  Wolfgang Jun 11 at 15:14

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.