How this kind of permutation is called in math?

161 Views Asked by At

Assume we have a set $\{a_0,a_1,a_2,...,a_{n-1}\}$. Our permutation maps each element $a_i$ to $a_{ki\bmod n}$, where n and k are relatively prime.

Geometrically it looks like if take a regular $n$-polygon, which vertices are numbered from $0$ to $n - 1$ clockwisely, then we start walking from vertex $a_0$ to another vertex $a_k$ that is shifted by $k$ positions, and then to another, ... until we make a cycle.

For example for $n=5, k=3$ we have $\{a_0, a_1, a_2, a_3, a_4\} \to \{a_0, a_3, a_1, a_4, a_2\}$.

The question is: Does this kind of permutation have special name?

1

There are 1 best solutions below

0
On BEST ANSWER

Permutations of the form $x\mapsto kx+a$, $x,a\in\Bbb{Z}_n$, $k\in\Bbb{Z}_n^*$, are sometimes called affine permutations modulo $n$, or affine transformations of $\Bbb{Z}_n$.

More typically an affine transformation concerns a vector space $V$ over some field $k$, when transformations of the form $x\mapsto T(x)+a$, $T$ a linear transformation, $a$ a fixed vector. Those can be described using $(n+1)\times(n+1)$-matrices, $n=\dim_kV$.

Similarly, the affine transformation $T_{k,a}:x\mapsto kx+a$ can be described with the matrix $$ M_{k,a}=\pmatrix{ k&a\cr0&1\cr} $$ with matrix entries viewed as elements of the ring $\Bbb{Z}_n$. The composition of such transformations then corresponds with the usual matrix product.

Anyway, all the affine transformations modulo $n$ form a group, we can call it $\operatorname{Aff}(n)$ for lack of better notation. The transformations you described, with $a=0$, form a subgroup isomorphic to $\Bbb{Z}_n^*$. The transformations with $k=1$ form another subgroup. In affine language they could be called "translations", in the case of permutations "cyclic shifts" is more common. The group of all affine transformations modulo $n$ is a semi-direct product of these two subgroups.