Является ли данный набор элементов группы набором представителей смежных классов?

Question

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

Если G группа (в смысле алгебраической структуры) и если g ₁ , ..., g _n являются элементами группы G, существует ли алгоритм ( или функция в какой-то специальной программе (например, GAP), чтобы определить, существует ли подгруппа группы G такая, что эти элементы образуют набор представителей для смежных классов этой подгруппы? (Можно предположить, что G - группа перестановок и, возможно, даже полная симметрическая группа.)

(Конечно, существует несколько алгоритмов для поиска классов заданных подгрупп, например алгоритм Тодда-Кокстера; это своего рода обратный вопрос.)

Спасибо, Даниэла

Answer 1

Вы пытаетесь определить, существует ли подгруппа H группы G такая, что {g ₁ , ..., g _n } является трансверсальной смежных классов H. т.е. множество представителей разбиения G смежными классами H.

Во-первых, по теореме Лагранжа , | G | = | G: H | * | G |, где | G: H | = | G | / | H | является индексом подгруппы H группы G. Если {g ₁ , ..., g _n } действительно является трансверсалью, то | G: H | = | {g ₁ , ..., g _n } |, поэтому первый тест в вашем алгоритме должен заключаться в том, делит ли n | G |.

Более того, поскольку g _i и g _j находятся в одном и том же правом классе, только если g _i g _j ^-1 находится в H, затем вы можете проверить подгруппы с индексом n, чтобы увидеть, избегают ли они g _i g _j ^-1 . Также обратите внимание, что (г _i г _j ^-1 ) (г _j г _k ^-1 ) = g _i g _k ^-1 , поэтому вы можете выбрать любую пару из g _i s.

Этого должно быть достаточно, если n мало по сравнению с | G |.

Другой подход состоит в том, чтобы начать с H, являющегося тривиальной группой, и добавить элементы множества H ^* = {h в G: h ^k ! = G _i g _j ^-1 , для всех i, j, k; i! = j} к генераторам H, пока вы не можете больше добавлять (то есть, пока он больше не является подгруппой). Тогда H максимальная подгруппа группы G такая, что H является подмножеством H ^*. Если вы можете получить все такие H (и иметь их достаточно большими), то подгруппа, которую вы ищете, должна быть одной из них.

Этот подход будет лучше работать для больших n.

В любом случае неэкспоненциальный подход не очевиден.

РЕДАКТИРОВАТЬ: Я только что нашел обсуждение этой самой темы здесь: http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2009_April_18#Is_a_given_set_of_group_elements_a_set_of_coset_representatives.3F

Answer 2

Единственное решение, которое я могу придумать, это наивно. В основном, если у вас есть элементы x1,...,xn, вы должны использовать GAP LowIndexSubgroupsFpGroup для перечисления всех подгрупп с индексом n (отбрасывая те, у которых индекс

Это все, что я мог придумать. Мне было бы очень интересно, если бы вы придумали лучший подход.

Answer 3

Немного менее грубый подход состоял бы в том, чтобы перечислить все подгруппы индекса n, как предложил Ил-Бхима, и затем для каждой подгруппы проверять каждую x _i * x _j ^-1 , чтобы увидеть, содержится ли оно в подгруппе.

Элементы x1, ..., xn будут представителями подгруппы тогда и только тогда, когда КАЖДЫЙ продукт

x _i * x _j ^-1 где (i! = J)

НЕ находится в подгруппе.

Этот тип проверки кажется более простым, чем генерация всех классов смежности, и вычислительно быстрее.