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

Question

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

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

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

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

Answer 1

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

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

Answer 2

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

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

х _я * х _J ^-1 где (я! = J)

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

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

Answer 3

Что вы пытаетесь определить, если существует подгруппа Н G таких, что {г ..., г _п} является transversal из классов смежности H. т.е. набор представители разбиения G на смежные классы H.

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

Кроме того, поскольку г _я и г _J находятся в одной и той же правой смежного класса, только если г _я г _J^-1 в H, можно затем проверить подгруппы с индексом п, чтобы увидеть если они избегают g _i g _j^-1. Кроме того, обратите внимание, что (г _я г _J^-1) (г _J г _к^-1) = G _я г _К^-1, так что вы можете выбрать любое сопряжение g _i s.

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

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

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

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

EDIT: Я только что нашел обсуждение этой самой теме здесь: 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