Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a finite group $G < Sym(\Omega)$; $\Omega$ finite, and $X \subset \Omega$, I can define a by the function $H(g) = \{x^g \| x \in X\}$ for each $g \in G$. Of course, each $H$ has the same size as $X$. Two different elements of $G$, $g_1,g_2$ may generate the same set $H(g_1)=H(g_2)$. Taking the collection of all such sets, $\mathscr{H} = \bigcup_{g \in G} H(g)$

I need to find $\mathscr{H}$, so what is the fastest way to find $F \subset G$ such that $\mathscr{H}$ is the disjoint union over $F$?

(I'm more interested mathematically how to do so, but I also need to compute the result. I am using GAP currently, with the following script:

setToThe := function(set,g)
    local x, l, i, s;
    l := [];
    i := 1;
    for s in set do
        x := s^g;
        l[i] := x;
        i := i + 1;
    od;
    return l;
    end;

grp := ...;
set := ...;

unique := [];
unique[1] := set;

for g in grp do
    allGood := true;
    startUnique := Size(unique);

    for j in [1..startUnique] do
        newset := setToThe(set,g);
        Sort(newset);
        if newset = unique[j] then
            allGood := false;
            break;
        fi;
    od;

    if allGood then
        unique[Size(unique)+1] := newset;
    fi;
od;
share|improve this question
    
Forgive my ignorance: what's $x^g$? –  Dylan Moreland Jul 14 '11 at 3:44
3  
So if $g \in G$ is a permutation of $\Omega$ (a bijection of $\Omega$ to itself), and $x \in \Omega$ then $x^g=g(x)$, that is, what $g$ takes $x$ to –  Zeophlite Jul 14 '11 at 3:47
    
Does X have some nice properties, or is it an arbitrary subset? Is G some nice group (abelian? cyclic? :p), or is it some arbitrary finite group? –  ShreevatsaR Jul 14 '11 at 4:57
    
It may, but I'd have to find out. What would be "nice" properties, in regards to finding $F$? –  Zeophlite Jul 14 '11 at 5:30
3  
What makes you think you can find an $F$ such that the union defining $\mathcal{H}$ is a disjoint union? This seems hard to pull off if, for example, $X$ contains more than half of the elements of $\Omega$. Anyway, it seems like a more efficient way of calculating $\mathcal{H}$ is to union up the $G$-orbits of points in $X$. –  user83827 Jul 14 '11 at 9:57
show 1 more comment

1 Answer 1

up vote 0 down vote accepted

It's simple, I feel silly:

Orbits(grp,set,OnSets);

So the trick is instead of thinking $Sym(\Omega)$, think $Sym(\alpha)$ where $\beta \subset \mathscr{P}(\Omega)$ such that for all $\alpha \in \beta$, $|\alpha| = |X|$

share|improve this answer
1  
How does this answer the question you asked? –  user83827 Jul 14 '11 at 14:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.