Порядки и ранги подгрупп

[B@R5uk]

Пусть $G$ — конечная группа ранга $R$.

Пусть $S_r$ — множество подгрупп $G$ ранга $r$. Будем рассматривать ранги $2\le r\le R-1$ (в группе $G$ могут быть подгруппы ранга большего $R$).

Пусть $N_r$ — максимальный порядок подгруппы в $S_r$.

Пусть $H$ — некоторая подгруппа из $S_r$, ранг которой равен $N_r$ (таких может быть несколько, в том числе не изоморфных между собой).

Утверждение: вне зависимости от выбора $H$, это подгруппа содержит в себе подгруппу $\widehat{H}$, порядок которой $N_{r-1}$ и ранг $r-1$. Другими словами, $\widehat{H}$ имеет максимальный ранг среди подгрупп в множестве $S_{r-1}$.

Вопрос: верно ли это утверждение? Если да, то с какой стороны подступиться к доказательству? Если нет, то с каких рангов/порядков группы $G$ ожидать нарушение этого утверждения? Заранее очень благодарен. Вопрос имеет практические последствия.

[mihaild]

Ответ сходу придумать не могу.
Есть идея взять что-то вроде $\mathbb Z_{12} \times S_{4}$ - у неё хочется в качестве самой большой подгруппы ранга $2$ взять $S_{4}$, а в качестве подгруппы ранга $1$ естественно $\mathhbb Z_{12}$. Но похоже что её всю можно породить двумя элементами, так что видимо совсем так не проходит.

[B@R5uk]

mihaild, вы сразу взялись за поиск контрпримера? Он может оказаться очень большим, если и существует. И мне кажется, что ранг группы $G$ как минимум должен быть 4 или больше. Во всяком случае, в группе 2-го ранга наибольший цикл (который является подгруппой наибольшего порядка на единицу меньшего ранга) всегда можно взять в качестве образующей (я для удобства дальше отождествляю один из порождающих элементов группы и соответствующую ему циклическую подгруппу) в паре с каким-нибудь подходящим вторым элементом.

[mihaild]

Да. Для начала можно попробовать поискать простой контрпример с какими-нибудь ограничениями, облегчающими его анализ, если не получится - доказать, что в таких ограничениях нет, и дальше смотреть что происходит при ослаблении ограничений.
Я пока продумывал две стратегии для контрпримера: два элемента, дающие вместе гигантскую подгруппу, но маленькую каждый по отдельности (так что подгруппа ранга 2 будет порождаться ими, а подгруппа ранга 1 - чем-то другим), и какой-нибудь эффект, подобный существованию подгруппы большого ранга у $S_n$ - т.е. когда требование получить именно маленький ранг сильно ограничивает размер подгруппы. Но пока что ни в одну сторону не придумал.
В сторону ограничений можно думать например верно ли, что если наша группа является прямой суммой нескольких групп, то для одной из них это свойство тоже выполнено. Но тут я плохо представляю, как вообще связаны ранг прямой суммы с рангом слагаемых.

[B@R5uk]

mihaild в сообщении #1549736 писал(а):

...два элемента, дающие вместе гигантскую подгруппу, но маленькую каждый по отдельности...

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

$S_n$ — ещё лучший пример. Её порядок $n!$ (гигантская величина), хотя она порождается элементов 2-го и $n$-го порядков. Однако, этот пример тоже не работает: в ней нет циклов порядка больше, чем $n$ (или я не прав?), а цикл этого (наибольшего) порядка является образующей по построению.

[mihaild]

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

Ну, за такой группой далеко ходить не надо: любая диэдрическая подгруппа может быть порождена двумя элементами второго порядка.

Да, плохо написал. Надо не просто чтобы каждый по отдельности давал маленькую подгруппу, а чтобы подгруппы ранга $1$ у этой группы были маленькие. Это тоже несложно - собственно $S_n$ имеет ранг $2$ и состоит из $\exp(n \ln 1 \cdot (1 + o(1)))$, а максимальная её подгруппа ранга $1$ состоит из $\exp(O(\sqrt{n\ln n}))$ элементов. Но проблема в том, что если рядом будет еще циклическая подгруппа какого-то промежуточного размера, то скорее всего её прямое произведение на $S_n$ всё равно будет иметь ранг $2$.

[B@R5uk]

mihaild в сообщении #1549738 писал(а):

а максимальная её подгруппа ранга $1$ состоит из $\exp(O(\sqrt{n\ln n}))$ элементов

Это что-то много. По определению группы всех перестановок из $n$ элементов длина цикла не может быть больше $n$. То есть, в группе $S_n$ есть всевозможные циклические подгруппы длины 2, 3, ... $n-1$ и $n$, но нет циклов длиной большей, чем $n$ (как ни парадоксально для группы такого размера).

-- 01.03.2022, 21:42 --

mihaild в сообщении #1549736 писал(а):

если наша группа является прямой суммой нескольких групп

В смысле прямое произведение?

[mihaild]

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

То есть, в группе $S_n$ есть всевозможные циклические подгруппы длины 2, 3, ... $n-1$ и $n$, но нет циклов длиной большей, чем $n$

Это неправда. Минимальный контрпример: группа $S_5$ содержит элемент порядка $6$.

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

В смысле прямое произведение?

Да (хотя вроде бы оба термина используются).

[B@R5uk]

Наткнулся тут на группу

$$G_{63}=\left\langle\;a,\;b\;|\;a^{21}=b^3=e,\;ab=ba^4\;\right\rangle$$

(Если что, эта группа имеет нетривиальный центр: $\operatorname{Z}\left(G_{63}\right)=\mathbb{Z}_3=\left\{\;e,\;a^{\pm 7}\;\right\}$ ). У этой группы есть группа автоморфизмов ранга 2, порядка 252 (с тривиальным центром) и сама себе являющаяся группой автоморфизмов:

$$G_{252}=\operatorname{Aut}\left(G_{63}\right)=\operatorname{Aut}\left(G_{252}\right)$$

Я пока не разобрался как в точности она устроена (в частности, без понятия, как выглядят групповые соотношения), но обнаружил следующий забавный факт. В группе есть элементы 21-го порядка и это максимальный порядок элемента в группе; все они содержатся в подгруппе $\mathbb{Z}_{21}\subset G_{252}$. Однако в группе нет ни единого элемента, которым можно было бы дополнить эту подгруппу до множества, замкнув которое относительно групповой операции до подгруппы, можно было бы получить всю группу $G_{252}$ целиком. Ещё раз замечу: эта группа имеет ранг 2. Это означает, что нашёлся контрпример, который я искал в первом посте (не совсем, правда такой, как я ожидал). Причём, и порядок его совсем небольшой ($252=2^2\cdot 3^2\cdot 7$), и ранг всего (!!!) 2.

-- 04.07.2022, 19:32 --

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

[mihaild]

Не понял, почему это контрпример к тому, что было в первом посте?
Там вы говорили о том, что максимальная по размеру группа ранга $r$ содержит какую-нибудь из подгрупп ранга $r - 1$ тоже максимального размера. У вас тут подгруппа ранга $1$ и размера $21$, и она конечно же содержит в себе подгруппу ранга $0$ максимально возможного размера (а именно $1$).

[B@R5uk]

mihaild в сообщении #1559468 писал(а):

Не понял, почему это контрпример к тому, что было в первом посте?

Ну, потому что это, наверно, не контрпример к тому, что я сформулировал в первом посте, а к тому, что я неудачно пытался сформулировать. Впрочем, как самостоятельная задача поставленный вопрос всё равно интересен.

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

Возможно, можно предложить какой-то иной подход к задаче. Буду очень рад таким предложениям, потому что сам ума не приложу как можно действовать по-другому.

[mihaild]

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

максимальная (по порядку) подгруппа предыдущего ранга не всегда расширяется описанным выше способом до максимальной подгруппы следующего ранга

Для этого и более простой пример есть: $\mathbb Z_6 \times S_3$.

[B@R5uk]

mihaild, нуууууу... Формально пример, конечно, подходит. То есть если говорить "среди максимальных подгрупп ранга 1 найдётся..." и так далее, то подходит. Ведь надо заметить, что в этой группе максимальный порядок элемента равен 6, а подгрупп $\mathbb{Z}_6$ в ней целых 10 штук. Все они относительно автоморфизмов разбиваются на 4 класса: центр группы, просто нормальная подгруппа, класс из 2-х подгрупп и класс из 6-ти. И только центр обладает искомым свойством.

А вообще, мне очень интересен ход вашей мысли в процессе поиска примера. Просто угадывание или какой-то последовательный подход?

[mihaild]

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

А вообще, мне очень интересен ход вашей мысли в процессе поиска примера. Просто угадывание или какой-то последовательный подход?

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

[B@R5uk]

Кто бы мог подумать, что

$$\mathrm{D}_8=\mathbb{Z}_2^2\rtimes\mathbb{Z}_2=\left\langle\;a,\;b,\;d\;|\;a^2=b^2=d^2=[a,\;b]=[a,\;d]=e,\;db=abd\;\right\rangle$$

То есть за счёт полупрямого произведения образующие кратных порядков слились в кольцо (по типу как $\mathbb{Z}_5\times\mathbb{Z}_3=\mathbb{Z}_{15}$ из-за взаимной простоты). Я так привык, что при произведении образующие кратных порядков стремятся разделиться и сохранить себя за счёт увеличения ранга группы или за счёт ещё чего-нибудь. А полупрямое произведение вообще стремится сохранить образующие даже без кратности (взять вон хотя бы ту же $\mathbb{Z}_7\rtimes\mathbb{Z}_3$). Но не в этом случае. Здесь

$$(bd)^2=b(db)d=b(abd)d=ab^2d^2=a$$

то есть элемент bd имеет порядок 4 (его квадрат имеет порядок 2 и является центром группы). Получается второе стандартное задание группы диэдра:

$$\left\langle\;b,\;d\;|\;b^2=d^2=(bd)^4=e\;\right\rangle=\mathrm{D}_8$$