Полупрямые произведения циклических групп иногда изоморфны?

[B@R5uk]

Рассмотрим группы вида

$$\mathbb{Z}_m\overset{k}{\rtimes}\mathbb{Z}_n=\left\langle\;a,\;b\;|\;a^m=b^n=I,\;ba=a^kb\;\right\rangle$$

Иногда случается так, что при фиксированных m и n группы для разных обменных степеней k изоморфны. Я хочу понять, когда это происходит.

Во-первых, используя последнее соотношение с обменной степенью k, можно получить (строго это доказывается с помощью ММИ):

$$ba^x=a^kba^{x-1}=a^{2k}ba^{x-2}=\ldots=a^{xk}b$$

$$b^ya=b^{y-1}a^kb=b^{y-2}a^{k^2}b^2=\ldots=a^{k^y}b^y$$

$$b^ya^x=b^{y-1}a^{xk}b=b^{y-2}a^{xk^2}b^2=\ldots=a^{xk^y}b^y$$

То есть элемент с любой комбинацией образующих за счёт обменного соотношения можно привести к виду

$$(x,\;y)=a^xb^y$$

где x и y — целые числа, удовлетворяющие

$$m>x\ge 0,\quad n>y\ge 0$$

То есть уникальных элементов mn штук. Умножение двух элементов:

$$\left(x_1,\;y_1\right)\left(x_2,\;y_2\right)=a^{x_1}b^{y_1}a^{x_2}b^{y_2}=a^{x_1+x_2k^{y_1}}b^{y_1+y_2}=\left(x_1+x_2k^{y_1},\;y_1+y_2\right)$$

После чего степени сокращаются используя первые два соотношения.

Во-вторых,

$$a=Ia=b^na=a^{k^n}b^n=a^{k^n}I=a^{k^n}$$

$$a^{k^n-1}=I$$

Вместе с первым соотношением на образующую a это можно редуцировать к

$$a^{m'}=I,\quad m'=\operatorname{gcd}\left(m,\;k^n-1\right)$$

То есть, чтобы нормальная подгруппа в полупрямом произведении выше действительно имела порядок m необходимо, чтобы выполнялась делимость

$$m\;|\;k^n-1$$

Тогда порядок всей группы будет

$$\left|\mathbb{Z}_m\overset{k}{\rtimes}\mathbb{Z}_n\right|=mn$$

При этом на обменную степень k так же логично наложить ограничения, чтобы она была несократима:

$$m>k>1$$

Моя рабочая идея для решения сформулированной в первом абзаце задачи — попытаться найти различные элементы группы, порядок которых тоже равен n, но отличные от образующей b, и посмотреть на то, какая будет с ними обменная степень у образующей a. По идее, если группу можно задать различными способами, то внутри неё должны все эти способы встретиться с другими наборами образующих. Я правильно мыслю? И есть ли другой, возможно, более простой подход к решению?

[dgwuqtj]

Это 25 лет назад сделали, кажется: Metacyclic groups. Там чуть более общая ситуация, расширения циклических групп при помощи циклических.

[B@R5uk]

Пусть

$$c=a^xb^y=(x,\;y)$$

тогда

$$c^z=(x,\;y)^z=(x,\;y)^{z-2}\left(x\left(k^y+1\right),\;2y\right)=(x,\;y)^{z-3}\left(x\left(k^{2y}+k^y+1\right),\;3y\right)=\ldots$$

$$\ldots=\left(x\left(k^{y(z-1)}+k^{y(z-2)}+\ldots+k^y+1\right),\;yz\right)$$

Если

$$z=n$$

то после запятой число делится на n и, поэтому, сокращается до нуля. А число перед запятой в скобках можно представить

$$x\left(k^{y(n-1)}+k^{y(n-2)}+\ldots+k^y+1\right)=x\sum\limits_{l=0}^{n-1}\left(k^y\right)^l=\frac{x\left(k^{ny}-1\right)}{k^y-1}$$

Так как

$$m\;|\;k^n-1$$

означает, что

$$k^n=1\mod m$$

то получаем, что числитель дроби тоже делится на m и выражение до запятой тоже сокращается до нуля. То есть

$$c^n=I$$

для любого элемента, у которого

$$y\ne 0$$

Теперь, чтобы порядок элемента c был равен n необходимо, чтобы

$$\operatorname{gcd}(n,\;y)=1$$

В противном случае можно взять

$$z=n'=\frac{n}{\operatorname{gcd}(n,\;y)}<n$$

и так как

$$\frac{n'y}{n}$$

будет целым, то можно провернуть этот же трюк с нулями выше и получить

$$c^{n'}=I$$

Теперь бы новое обменное соотношение вывести.

dgwuqtj, а качнуть эту статью где-то можно? На сайте не видать ссылки.

[dgwuqtj]

B@R5uk в сообщении #1648920 писал(а):

а качнуть эту статью где-то можно?

Ну так sci-hub есть... Находите работающее зеркало и вводите там DOI-адрес. Я специально ровно такую ссылку и дал.

[B@R5uk]

$$ca=(x,\;y)(1,\;0)=(x+k^y,\;y)=a^{k^y}c=a^{k'}c$$

то есть

$$k'=k^y\mod m,\quad\operatorname{gcd}(n,\;y)=1,\quad m\;|\;k^n-1$$

и группа со штрихованной обменной степенью будет изоморфна исходной. Теперь большой вопрос: выше доказано "тогда", а будет ли верно "и только тогда"?

dgwuqtj, спасибо.

[B@R5uk]

Написал брутфорс-программку, чтобы посмотреть для каких пар m, n существуют k и в каком количестве (специально исключил единичные k, так как они существуют в любом случае):

Используется синтаксис Java

public class Test_Semiproduct_Powers {
    public static void main (String [] args) {
        int k, kk, l, m, n, rem, count;
        int [] coprimes;
        boolean flag;
        boolean [] flags;
        
        //m = 71;
        n = 4;
        
        flags = new boolean [n];
        for (k = 1, l = 0; n > k; ++k) {
            if (1 != gcd (k, n)) {
                continue;
            }
            flags [k] = true;
            ++l;
        }
        coprimes = new int [l];
        System .out .print (n + ": ");
        for (k = 1, l = 0; coprimes .length > l; ++k) {
            if (flags [k]) {
                if (0 != l) {
                    System .out .print (", ");
                }
                System .out .print (k);
                coprimes [l] = k;
                ++l;
            }
        }
        System .out .println ("\n");
        
        for (m = 3; 2000 > m;  ++m) {
            flag  = true;
            flags = new boolean [m];
            count = 0;
            for (k = 2; m > k; ++k) {
                rem = modPower (k, n, m);
                if (1 != rem) {
                    continue;
                }
                if (flags [k]) {
                    continue;
                }
                ++count;
                if (flag) {
                    flag = false;
                    System .out .println ("\n" + m + ":");
                }
                for (l = 0; coprimes .length > l; ++l) {
                    kk = modPower (k, coprimes [l], m);
                    if (flags [kk]) {
                        continue;
                    }
                    flags [kk] = true;
                    if (0 != l) {
                        System .out .print (", ");
                    }
                    System .out .print (kk);
                }
                System .out .println ();
                //System .out .println (String .format ("%4d %4d", k, ));
            }
            if (4 < count) {
                System .out .println (count + " !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
            }
        }
    }
    
    private static int modPower (int argBase, int argPower, int argMod) {
        int result = 1;
        while (0 < argPower) {
            if (0 != (argPower & 1)) {
                result *= argBase;
                result %= argMod;
            }
            argBase *= argBase;
            argBase %= argMod;
            argPower >>= 1;
        }
        return result;
    }
    
    private static int gcd (int a, int b) {
        int c;
        if (a < b) {
            c = a;
            a = b;
            b = c;
        }
        while (0 != b) {
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
}
 

Никаких групп, чистая арифметика. Для $n=2_{.}$ количество различных k может быть 1, 3, 7, 15, 31 и так далее, то есть степени двойки без единицы (так как единичную k я выкинул). Ни одна степень не входит в пары или тройки, так как взаимнопростых чисел с двойкой существует только одна штука: единица. Не знаю, почему тут возникли степени двойки (для чисел m ну никак не связанных со степенями двойки), поэтому решил составить табличку, когда какая степень появляется:

Используется синтаксис Text

Number                                                          
of groups                       m                               
Zm # Z2                                                         
3: 8, 12, 15, 16, 20, 21, 28, 30, 32, 33, 35, 36, 39, 42, 44, 45,
        51, 52, 55, 57, 63, 64, 65, 66, 68, 69, 70, 75, 76, 77, 78
        85, 87, 90, 91, 92, 93, 95, 99, 100, 102, 108, 110, 111, 114
        115, 116, 117, 119, 123, 124, 126, 128, 129, 130, 135, 138,
        141, 143, 145, 147, 148, 150, 153, 154, 155, 159, 161, 164,
        ...
7: 24, 40, 48, 56, 60, 72, 80, 84, 88, 96, 104, 105, 112, 132, 136,
        140, 144, 152, 156, 160, 165, ...
15: 120, 168, 240, 264, 280, 312, 336, 360, 408, 420, 440, 456, 480
        504, 520, 528, 552, 560, 600, 616, 624, 660, 672, 680, 696,
        720, 728, 744, 760, 780, 792, 816, 880, 888, 912, 920, 924,
        936, 952, 960, 984, 1008, 1020, 1032, 1040, ...
31: 840, 1320, ...

Строка для тройки — это вот эта последовательность (похожа на эту, но с числа 63 отличия), для 7 — вот эта, для 15 — вот эта и для 31 — вот эта. В вот эта последовательность указывает первое число в каждом абзаце. Как ни крути, а определение этих последовательностей завязано на группы: "Numbers n such that the multiplicative group modulo n is the direct product of {insert number here} cyclic groups". Какая у них связь с количеством уникальных чисел k и почему степени двойки — ума не приложу.

В общем случае, конечно, без групп объяснить тут вряд ли что-то получится. Даже пары $(m,\;n)_.$ с нетривиальными k существуют только тогда, когда наибольший общий делитель отличен от единицы:

$$1\ne\operatorname{gcd}\left(\left|\operatorname{Aut}\left(\mathbb{Z}_m\right)\right|,\;n\right)$$

А количество неприводимых друг к другу чисел k завязано на количество уникальных гомоморфизмов:

$$\varphi:\;\mathbb{Z}_n\to\operatorname{Aut}\left(\mathbb{Z}_m\right)$$

При этом, я не знаю, как для "циклических расширений", а в общем случае ситуация ещё хуже: бывает так, что "не изоморфные" гомоморфизмы ведут к одной группе. Как заранее отличить все эти случаи — непонятно.

[B@R5uk]

B@R5uk в сообщении #1649073 писал(а):

Как ни крути, а определение этих последовательностей завязано на группы: "Numbers n such that the multiplicative group modulo n is the direct product of {insert number here} cyclic groups". Какая у них связь с количеством уникальных чисел k и почему степени двойки — ума не приложу.

На самом деле связь легко просматривается через то, как именно строится полупрямое произведение. Группа

$$\mathbb{Z}_m\rtimes\mathbb{Z}_2$$

задаётся на множестве элементов

$$\mathbb{Z}_m\times\mathbb{Z}_2$$

с помощью гомоморфима

$$\varphi:\mathrm{Aut}\left(\mathbb{Z}_m\right)\to\mathbb{Z}_2$$

Когда мы говорим, что мультипликативная группа по модулю m представима в виде произведения t циклических групп, то тут молча подразумевается, что все эти группы чётного порядка. А это означает, что группа автоморфизмов нормальной подгруппы $\mathbb{Z}_m$ для такого m содержит в себе подгруппу

$$\mathbb{Z}_2^t\subset\mathrm{Aut}\left(\mathbb{Z}_m\right)$$

Эта подгруппа имеет ${}_{{}_{{}_.}}2^t$ элементов, каждый из которых (кроме нейтрального) совместно с нейтральным образуют подгруппу $\mathbb{Z}_2$ в количестве ${}_{{}_{{}_.}}2^t-1$ штук. Одну из этих подгрупп гомоморфизм, задающий полупрямое произведение, отображает в фактор-группу. Тут, конечно, ещё надо доказать, что различные гомоморфизмы дают неизоморфные полупрямые произведения, но мне теперь хотя бы понятно, откуда у моего экспериментального наблюдения ноги растут.

-- 17.08.2024, 10:07 --

Меня всё продолжает мучить вот этот вопрос:

B@R5uk в сообщении #1648928 писал(а):

то есть

$$k'=k^y\mod m,\quad\operatorname{gcd}(n,\;y)=1,\quad m\;|\;k^n-1$$

и группа со штрихованной обменной степенью будет изоморфна исходной:

$$\mathbb{Z}_m\overset{k}{\rtimes}\mathbb{Z}_n=\left\langle\;a,\;b\;|\;a^m=b^n=I,\;ba=a^kb\;\right\rangle\simeq\left\langle\;a,\;b\;|\;a^m=b^n=I,\;ba=a^{k'}b\;\right\rangle=\mathbb{Z}_m\overset{k'}{\rtimes}\mathbb{Z}_n$$

Теперь большой вопрос: выше доказано "тогда", а будет ли верно "и только тогда"?

Пока моей рабочей идеей проверки является только арифметический подход грубой силы: для фиксированных m, n и k будет брать всевозможные пары образующих порядка m и n (где первая даст нормальную подгруппу, а вторая — подгруппу, изоморфную фактор-группе) и будем смотреть какие получаются обменные степени. Если обменные степени получатся только из списка эквивалентности выше, то верно "и только тогда", а если нет, то нет, а так же получится новое правило эквивалентности.

-- 17.08.2024, 10:39 --

Пусть

$$d=a^x,\quad\gcd(m,\;x)=1$$

тогда

$$bd=(0,\;1)(x,\;0)=(kx,\;1)=a^{kx}b=d^kb$$

То есть при взятии любой другой образующей нормальной группы обменная степень не меняется. Это означает, что если брать всевозможные допустимые пары образующих d и c, то за счёт единичного НОДа можно установить (от d перейти к a, найдя степень d, равную a), что такая пара будет иметь ту же обменную степень, что и пара a и c, а такой случай уже рассмотрен выше. То есть, действительно, верно "и только тогда". Фух! Сразу полегчало. Теперь не нужно заморачиваться с проверкой на ВНЕЗАНУЮ изоморфность.

[B@R5uk]

B@R5uk в сообщении #1650400 писал(а):

...такая пара будет иметь ту же обменную степень, что и пара a и c, а такой случай уже рассмотрен выше.

Косяк-косяк, не всё так просто. Надо проверять обменную степень образующей d не с исходной образующей b, а с некоторой произвольной

$$c=a^xb^y=(x,\;y),\quad\gcd(n,\;y)=1$$

То есть, пусть

$$d=a^z,\quad\gcd(m,\;z)=1$$

тогда

$$cd=(x,\;y)(z,\;0)=(x+zk^y,\;y)=(zk^y,\;0)(x,\;y)=(zk',\;0)(x,\;y)=d^{k'}c$$

$$k'=k^y\mod m$$

где использовалось выведенное выше правило умножения элементов

$$\left(x_1,\;y_1\right)\left(x_2,\;y_2\right)=\left(x_1+x_2k^{y_1},\;y_1+y_2\right)$$

То есть группа в новых образующих имеет задание

$$\left\langle\;d,\;c\;|\;d^m=c^n=I,\;cd=d^{k'}c\;\right\rangle$$

и изоморфность с группами с другими обменными степенями, не рассмотренными выше, отсутствует.