Abstract:
We consider the set $V=\mathbb{Z}_{q}^{n}$, $n\geqslant 2$, represented by the Cartesian power of the residue ring $\mathbb{Z}_{q}=\{0,1,...\,,q-1\}$, and the integer $q \geqslant 2$.
We introduce special substitutions $\pi=\pi_{(i_{1},...\,,i_{r})}\in S_{V}$ of the set $V$.
Each of such substitutions is determined by a subset $\{i_{1},...\,,i_{r}\}\subseteq\{1,...\,,n\}$ and by linear order introduced on this subset, where $i_{1}$ is the low-order number and $i_{r}$ is the high-order number.
The power $r$ of a subset, $1 \leqslant r \leqslant n$, has an individual value for each such
substitution $\pi$ and belongs to the range specified above. Also, there are $r!$ possibilities to determine the linear order.
If $\pi_{(i_{1},...\,,i_{r})}(x_{1},...\,,x_{n})=(y_{1},...\,,y_{n})$ then $y_{i}=x_{i}$ for $i\notin\{i_{1},...\,,i_{r}\}$ and
$$
\sum\limits_{t=1}^{r}y_{i_{t}}q^{r-t}\,=\,1+\sum\limits_{t=1}^{r}x_{i_{t}}q^{r-t} \pmod{q^{r}\,}.
$$
With the set $\mathcal{S}=\{\pi_{1},...\,,\pi_{s}\}$ of such permutations, we associate the group $G=G_\mathcal{S}=\langle\pi_{1},...\,,\pi_{s}\rangle$ generated by this set, and the oriented graph
$\Gamma=\Gamma_\mathcal{S}$ on the set of vertices $\{1,...\,,n\}$.
If the permutations $\pi_{j}$ are determined by the sets of numbers
$\bigl(i_1^{(j)},...\,,i_{r_j}^{(j)}\bigr)$, $j=1,...\,,s$, then
the graph $\Gamma$ contains the edges $i_t^{(j)}\leftarrow i_{t+1}^{(j)}$, $t=1,...\,,r_j-1$,
$j=1,...\,,s$. Such edges are oriented from the low-order numbers to the high-order ones.
Theorem. Suppose that the graph $\Gamma=\Gamma_\mathcal{S}$ is strongly connected,
$\mathcal{S}=\{\pi_{1},...\,,\pi_{s}\}$, $ q \geqslant 2 $, then the
group $G=G_\mathcal{S}=\langle\pi_1,\,...\,,\pi_s\rangle$ contains the alternating group $A_{V}$ of the set $V$,
with the only exception for $q = 2$, $n \geqslant 3$, $r_{j} \leqslant 2$ for all $j=1,...\,,s$,
when $G_\mathcal{S}=AGL(n,2)$ is the affine group of the set $GF(2)^{n}$.
The group $G_ \mathcal {S}$ coincides with the symmetry group of the set $V$,
if $r_{j} = n$ for some $j\in\{1,...\,,s\}$, and $q$ is even.
The converse theorem is obvious. If the graph $\Gamma_\mathcal{S}$
is not strongly connected, then the group $G_\mathcal{S}$ is imprimitive.
A main combinatorial part of the theorem proof is devoted to establishing
of twice transitivity of the group $G_{\mathcal{S}}$.
The completion of the proof is possible due to the classification
of finite simple groups and the uniqueness theorem proved by P. Mihailescu in
2003 for a solution of the equation $x^{z}-y^{t}=1 $ in integers of large 1,
$3^{2}-2^{3} = 1 $, known as the Catalan hypothesis since 1884.
Application. A color monitor having a resolution $2^{10}\times2^{10}$ cells (pixels) is today's reality.
Each cell has $2^{8}$ shades. A total of $2^{23}$ “cubes” are allocated to the monitor.
Here $V=GF(2)^{2^3}$, $q=2$, $n=2^{23}$. The practice of working with images assumes the potential
possibility of obtaining any even substitution from $\bigl(2^{2^{23}}\bigr)!/2$
possible variants, and it is desirable to use simple machine operations.
