4
$\begingroup$

Suppose we are given a group $G$ in terms of generators $t_1, ..., t_n$ which are order 2 in $S_m$ (however we don't assume anything other than that these elements generate $G$ and have order 2). What is the most efficient way to determine:

  1. If $G$ is abstractly isomorphic to a Coxeter group
  2. Assuming yes, a Coxeter system for $G$
  3. Assuming no, a presentation of $G$ as a quotient of a Coxeter group
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I don't get your question exactly: the $t_i$ having order 2 does not make them transpositions necessarily (viewed inside $S_m$ at least); and since they are not simple transpositions it's not clear that $(G,\{t_1,\ldots,t_n\})$ is in fact a Coxeter system. (Note that the abstract group structure of $G$ is not enough to necessarily recover its structure as a Coxeter group, in particular, its root system.) $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 2:05
  • $\begingroup$ I definitely don't want to assume that $(G, {t_1,...,t_n})$ is a Coxeter system, but if I understand correctly, $G$ should have some generators that form a Coxeter system. My question is how to find one choice of such generators. $\endgroup$
    – manzana
    Commented Oct 19, 2020 at 2:17
  • 1
    $\begingroup$ Why should it have generators like that? In general a group generated by involutions is just a quotient of a Coxeter group. $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 2:19
  • 1
    $\begingroup$ It'd be better for you to edit the question to reflect what you want to ask (or if you realize your question doesn't make sense, just delete it). $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 3:03
  • 1
    $\begingroup$ Thanks, I've edited the question so hopefully there are no errors now. If it still doesn't make sense I'll probably just delete it. $\endgroup$
    – manzana
    Commented Oct 19, 2020 at 3:08

2 Answers 2

Reset to default
3
$\begingroup$

There is a theoretical answer (as opposed to an algorithmic answer) found in Björner and Brenti's "Combinatorics of Coxeter groups", Section 1.5. (They seem to credit it to Matsumoto.) Their Theorem 1.5.1:

Suppose $W$ is a group generated by a subset $S$ consisting of elements of order $2$. Then TFAE:

  1. $(W,S)$ is a Coxeter system (i.e. $S$ generates $W$ as a Coxeter group)
  2. $(W,S)$ has the Exchange Property.
  3. $(W,S)$ has the Deletion Property.

These are properties written in terms of reduced words.

To talk about an actual algorithm, we need a precise meaning to the assumption that "we are given a group $G$ in terms of generators $t_1,\ldots,t_n$". The only reasonable interpretation I'm finding for that is that we have an oracle that tells you whether two words in the generators stand for the same element.

In principle, you could design a "partial" algorithm, by checking Exchange or Deletion. But if your group is infinite, it might run forever, and you would never know whether your algorithm is about to come up with a counterexample to Exchange or Deletion.

EDIT: Now that I have noticed that the question specifies that all this takes place inside some symmetric group $S_m$: The group $G$ is finite, so there are finitely many reduced words, and the Exchange Property can be checked in finite time.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I was almost finished with this answer, when I noticed the crucial piece of information in the question: $t_1,\ldots,t_n$ are assumed to be elements of order 2 in $S_m$, which I assume is the symmetric group. So this answer addresses a more general situation. But I think it's worth pointing out, so I'm keeping it. $\endgroup$
    – Nathan Reading
    Commented Oct 19, 2020 at 13:13
2
$\begingroup$

I don't think this is what the questioner means, so this is not really an answer. But it's worth mentioning and it's too long for a comment.

If we know that $t_1,\ldots,t_n$ are transpositions, then $G$ is a "reflection subgroup" of $S_m$ (a subgroup generated by reflections). Then a theorem of Deodhar ("A note on subgroups generated by reflections in Coxeter groups") and Dyer ("Reflection subgroups of Coxeter systems") tells us that $G$ is a Coxeter group. They also give a recipe for finding a simple system: Find all transpositions in $G$ and find the corresponding positive roots. Out of all these positive roots, find the unique minimal subset such that all positive roots are in the nonnegative span of the subset. The transpositions for that subset are the simple system.

In this case, $G$ will be a product of symmetric groups.

Improve this answer
$\endgroup$
5
  • $\begingroup$ In the comments I pointed out that in the question the $t_i$ are not necessarily assumed to be transpositions, which makes the question weird/unnatural, and the OP seemed to agree. So I think they really don't want to assume that the $t_i$ are transpositions. $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 13:37
  • 1
    $\begingroup$ Btw, regarding your last sentence: if the $t_i$ really are transpositions, it should be easy to see which product of symmetric groups we get if we just draw the "graph" of the transpositions- then the connected components of this graph tells us the product. $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 13:38
  • 1
    $\begingroup$ @SamHopkins: I agree that this is not what the OP wants. It just seemed worth mentioning, because the Dyer/Deodhar result is very important in more general situations. $\endgroup$
    – Nathan Reading
    Commented Oct 19, 2020 at 13:39
  • 1
    $\begingroup$ @SamHopkins: I don't think the question is weird or unnatural. Consider asking the OP's 3 questions for any finite group generated by elements of order 2. To me that seems very natural. But then, any finite group is a subgroup of some finite symmetric group, so the OP's question is the same. And the way that the OP phrases it is nice for actual computations. If we are given the elements as permutations, we can actually compute. $\endgroup$
    – Nathan Reading
    Commented Oct 19, 2020 at 13:45
  • $\begingroup$ Fair enough, that makes sense! $\endgroup$
    – Sam Hopkins
    Commented Oct 19, 2020 at 13:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .