Аннотация:
Рассматривается множество $V=\mathbb{Z}_q^n$, $n\geqslant 2$, представленное декартовой
степенью кольца вычетов $\mathbb{Z}_q=\{0,1,...\,,q-1\}$, целое $q\geqslant 2$.
На множестве $V$ вводятся специальные подстановки $\pi=\pi_{(i_1,...\,,i_r)}\in S_{V}$.
Каждая такая подстановка задаётся подмножеством $\{i_{1},...\,,i_{r}\}\subseteq\{1,...\,,n\}$
и введённой на этом подмножестве линейной упорядоченностью: $i_{1}$ будет старшим номером, $i_{r}$ – младшим.
Мощность $r$ подмножества, $1\leqslant r\leqslant n$, своя для каждой такой подстановки $\pi$ и может быть любой
из указанного диапазона. Упорядоченность тоже может быть любой из $r!$ возможных.
Если $\pi_{(i_{1},...\,,i_{r})}(x_{1},...\,,x_{n})=(y_{1},...\,,y_{n})$, то $y_{i}=x_{i}$ для $i\notin\{i_{1},...\,,i_{r}\}$, а
$$
\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}}.
$$
Множеству $\mathcal{S}=\{\pi_{1},...\,,\pi_{s}\}$ таких подстановок ставим в соответствие группу
$G=G_\mathcal{S}=\langle\pi_{1},...\,,\pi_{s}\rangle$, ими порождаемую, и ориентированный граф
$\Gamma=\Gamma_\mathcal{S}$ на множестве вершин $\{1,...\,,n\}$.
Если подстановки $\pi_{j}$ определяются соответственно наборами номеров
$\bigl(i_1^{(j)},...\,,i_{r_j}^{(j)}\bigr)$, $j=1,...\,,s$, то
дугами графа $\Gamma$ являются: $i_t^{(j)}\leftarrow i_{t+1}^{(j)}$, $t=1,...\,,r_j-1$, $j=1,...\,,s$.
Дуги направлены от младших номеров к старшим.
Теорема. Если граф $\Gamma=\Gamma_\mathcal{S}$ сильно связен,
$\mathcal{S}=\{\pi_{1},...\,,\pi_{s}\}$, $q\geqslant 2$, то
группа $G=G_\mathcal{S}=\langle\pi_{1},\,...\,,\pi_{s}\rangle$ содержит знакопеременную группу $A_{V}$ на множестве $V$,
за единственным исключением при $q=2$, $n\geqslant 3$, $r_{j}\leqslant 2$ для всех $j=1,...\,,s$,
когда $G_\mathcal{S}=AGL(n,2)$ – полная аффинная группа, действующая на пространстве $GF(2)^{n}$.
Группа $G_\mathcal{S}$ совпадает со всей симметрической группой на $V$, когда $r_{j}=n$ для некоторого
$j\in\{1,...\,,s\}$, а $q$ чётно. Обратное к теореме утверждение очевидно, при нарушении сильной связности графа
$\Gamma_\mathcal{S}$ группа $G_\mathcal{S}$ будет импримитивной.
Основная комбинаторная часть доказательства теоремы отводится установлению дважды транзитивности группы
$G_\mathcal{S}$. Завершение доказательства оказалось возможным благодаря классификации конечных простых групп и
доказанной в 2003 г. П. Михайлеску единственности решения уравнения $x^{z}-y^{t}=1$ в целых числах больших единицы:
$3^{2}-2^{}=1$, известной с 1884 года как гипотеза Каталана.
Приложение. Цветной монитор на $2^{10}\times2^{10}$ клеток (пикселей) – сегодняшняя реальность.
У клетки $2^{8}$ оттенков. Всего на монитор отводится $2^{28}$ “кубиков”. Здесь $V=GF(2)^{2^{8}}$, $q=2$, $n=2^{28}$.
Практика работы с изображениями предполагает потенциальную возможность получения любой чётной подстановки из
$\bigl(2^{2^{28}}\bigr)!/2$ возможных, причём желательно с помощью простых машинных операций.
Обратная связь: