2

given a finite permutation group $G$ and a list of subgroups of $G$ list1. I want to compute the fixed points of $U$ acting on $G/V$ via right multiplication, where $U, V \in$ list1 (i.e. a submatrix of the table of marks of $G$ ).

If the groups are not too big, one can use $ fix_X( G/V ) = | \{ Y^g : g\in G, X \leq Y^g \}|\cdot [ N_G( Y ) : Y ]$, where $Y^g = g^{-1}Yg$ is the right conjugacy operation of $G$ on its subgroups. My implementation in GAP using this formula works fine.

In my opinion $ | \{ Y^g : g\in G, X \leq Y^g \}| = | \{ ^gX : g\in G, ^gX \leq Y \}| $ holds; $^gX = gXg^{-1}$ being the left conjugcy operation. But using this formula in my GAP code the results are wrong.

Before posting my code: Is there any mistake in the above equality?

Dominik B.
  • 283

1 Answers1

2

The problem in your equality is the (dis-)counting of duplicates when looking at sets. Suppose e.g. that $Y=G$ and $X$ a non-normal subgroup. Then there is one conjugate of $Y$ but many of $X$, all contained in $Y$.

I would give the following two options a try -- not necessarily because they are fundamentally better, but they have tuned code behind them:

FactorCosetAction(G,V);

returns (a homomorphism) the (right) permutation action on the cosets of $V$ in $G$.You could calculate the image of $U$ and determine the number of fixed points. Alternatively, you could compute

DoubleCosets(G,V,U)

and check how many double cosets have size $|V|$. (The best algorithm would probably be to use the double coset calculation and discard any intermediate results that correspond to orbits of length $>1$. However this would require modifying the code.

ahulpke
  • 18,416
  • 1
  • 21
  • 38
  • Thanks for your answer. You're right, I should have figured that out by myself.. I want my code to work for fairly large groups, e.g. $S_{13}$ or bigger. I don't think using DoubleCosetsNC(G,V,U) is a good idea. My idea was to split the calculations into 3 parts: Small U, large U and the rest. Dealing with the first two should not be that big of a problem. Do you have any reference for the algorithm you used for calculating the double cosets in GAP because understanding the code itself without any additional information will be quite complicated after taking a short look at it.. – Dominik B. Jan 10 '15 at 17:07
  • 1
    My guess is that for symmetric groups of such degree the double coset calculations should work reasonably well. I would definitively give it a try first before looking at modifying the code. – ahulpke Jan 10 '15 at 19:48
  • 1
    The algorithm is the ``Leiterspiel'' by Schmalz (https://zbmath.org/?q=an:04154699) with a single up-step at the end. If you want to modify the code, it is line 542 of csetgrp.gi -- turn off the flipping, eliminate the up steps (all if'-cases which could setcano' to true), and (line 866, end of the for loop) discard those double cosets that already are to large. Email me directly if you want to do this and need help. – ahulpke Jan 10 '15 at 19:57
  • I experimented quite a lot with the double coset calculations and the combinations with the formula I mentioned in my first post. The best result I got was calculating the table of marks of $S_8$ in 15mins on the LBfM-Server at RWTH. This is not acceptable since calculating the table of marks for larger groups will be impossible with this algorithm. So I think I will have a look at the algorithm and your code.. – Dominik B. Jan 11 '15 at 15:51
  • 1
    Thinking about it, as you only want fixed points probably reimplementing from scratch is easier: Call AcendingChain(G,V) and then descend the chain and determine fixed cosets and their stabilizers iteratively. If the indices of the chain are too large, see whether one can use maximal subgroups to refine. – ahulpke Jan 11 '15 at 16:36