Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Related (math.SE): How does the base of a group determine the “sort” of the elements in the group

The help page for GroupActionBase says:

  • A base of a group is a list of points of its domain of action such that the only element in the group fixing them all is the identity.
  • Reordering the points in a base gives a different base.
  • The choice of base affects the ordering of group elements in the functions GroupElements and GroupElementPosition.
  • If the list of points given is not a base, Mathematica will add more points until obtaining a base. In particular, GroupActionBase -> {} will make Mathematica choose an appropriate base.

It doesn't explain how the order of points in a base affects the order of the elements in a group. Since this is pretty much exactly what you need to know in order to use GroupActionBase, at a minimum should have been included in the help file. ;-)

They do include a single example (that wasn't very illuminating for me), which I'll include below for easy reference.

So bullet 1 specifies that a base needs enough points such that only the group identity will fix all the points in the base, and bullet 4 says if you don't provide a full base, Mathematica will add points (via some unspecified methodology) until it's a base, but this doesn't explain how the order of the points in the base relates to the order of the elements of the group.

From bullet 1 and the example, it's apparent that a base is a flat list of the same positive integers that the Cycles notation operates on. However, the group $S_n$ (the example below is contained inside $S_4$) operates on a set of $n$ elements, and there are $n!$ ways to order them in a base. But $S_n$ itself has $n!$ group elements, meaning there are $(n!)!$ ways to order the elements of the group. Can anyone clarify how specification of a base via GroupActionBase effects the order of the group elements reported by GroupElements and GroupElementPosition?


Basic Examples (1)

Elements of a group in standard order:

In[1] := GroupElements[PermutationGroup[{Cycles[{{1, 2}, {3, 4}}], Cycles[{{1, 3}}]}]]
Out[1]:= {Cycles[{}], Cycles[{{2, 4}}], Cycles[{{1, 2}, {3, 4}}],
          Cycles[{{1, 2, 3, 4}}], Cycles[{{1, 3}}], Cycles[{{1, 3}, {2, 4}}],
          Cycles[{{1, 4, 3, 2}}], Cycles[{{1, 4}, {2, 3}}]}

In[2] := OrderedQ[%, Less]
Out[2]:= True

Sort them, specifying different priorities with a base:

In[3] := GroupElements[PermutationGroup[{Cycles[{{1, 2}, {3, 4}}], Cycles[{{1, 3}}]}], 
          GroupActionBase -> {4, 2}]
Out[3]:= {Cycles[{}], Cycles[{{1, 3}}], Cycles[{{2, 4}}], 
          Cycles[{{1, 3}, {2, 4}}], Cycles[{{1, 4}, {2, 3}}], 
          Cycles[{{1, 2, 3, 4}}], Cycles[{{1, 4, 3, 2}}], 
          Cycles[{{1, 2}, {3, 4}}]}
share|improve this question
    
This is not an official Wolfram Research site, so complaints concerning the inadequacy of Mathematica documentation, however valid, are not really appropriate. Perhaps you might do better by posting this on the Wolfram Community. As an alternative, you might edit the question to ask something specific about GroupActionBase. Someone may be able to answer a well-posed specific question. –  m_goldberg Apr 12 at 21:33
    
Apologies if my wry attempt to inject humor into a technical topic offended. I realize this isn't a Wolfram site, but I've noticed anecdotally that the SE communities are typically faster than corporate run support systems. (With the exception of XBox's Twitter Support, they impress me.) Come to think of it, Wolfram support in particular I've not been happy with. In the past, they've taken weeks or months to return my support emails. I was not aware of that forum, and if SE doesn't satisfy, I'll consider biting the bullet and registering yet another account in another community. –  Travis Bemrose Apr 13 at 2:06
    
How can I make the question more specific or more well-posed? I know nothing about GroupActionBase or how Mathematica decides the order of group elements. As a math PhD student I've never even heard of bases for groups before and was shocked when I looked it up to find it wasn't just a Mathematica term/convention. I felt the question was fairly narrowly focused. I'm not asking about groups or algebra in general, but specifically in Mathematica, how does a specified base determine the order of elements in the group it's applied to? –  Travis Bemrose Apr 13 at 2:11
    
Don't get me wrong, I'm not proposing you delete your question, nor am I going to vote to close it. I simply am pessimistic about your getting an answer to it in its current form. I sincerely hope that my pessimism is misplaced. –  m_goldberg Apr 13 at 3:51
    
One way you might improve your question is to add a one sentence paragraph at end. "Can anyone fill in the holes I have found in the documentation article?" –  m_goldberg Apr 13 at 3:58

1 Answer 1

up vote 2 down vote accepted

Let me try to explain this. The key idea with bases is that even when you work with a group action on a set of n objects numbered 1 to n, you actually can identify the individual group elements by how they act on the elements of a base, which is frequently much shorter.

For example, take the

In[1]:= group = DihedralGroup[6];

It has 12 elements, sorted by default as given by

In[2]:= elems = GroupElements[group];

You can see the base chosen by Mathematica using

In[3]:= base = GroupStabilizerChain[group][[-1, 1]]
Out[3]= {1, 2}

This means that we do not have to control how the group acts on the 6 points, but it is enough to keep track of how the group acts on {1, 2}. Note that these pairs of images are all different, and that they are sorted in standard order:

In[4]:= PermutationReplace[base, elems]
Out[4]= {{1, 2}, {1, 6}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 5}, {5, 4}, {5, 6}, {6, 1}, {6, 5}}

Imagine you want to use a different base, one that starts with {5, 2} for example. Use

In[5]:= GroupStabilizerChain[group, GroupActionBase -> {5, 2}][[-1, 1]]
Out[5]= {5, 2, 4}

Mathematica tells you that {5, 2} is not a base. That is because the images of {5, 2} do not uniquely identify the elements of the group. There are repeated pairs of images here:

In[6]:= PermutationReplace[{5, 2}, elems]
Out[6]= {{5, 2}, {3, 6}, {4, 1}, {6, 3}, {5, 2}, {1, 4}, {6, 3}, {2, 5}, {1, 4}, {3, 6}, {4, 1}, {2, 5}}

However, {5, 2, 4} is a base. Actually {5, 4} is a base (2 is redundant) so let us use {5, 4} in what follows:

In[7]:= newbase = {5, 4};

In standard {1, 2, 3, ...} order we give first priority to 1, then to 2, etc. With the base {5, 4} we worry first about what happens to 5, then to 4. Then the rest in standard order, so we have {5, 4, 1, 2, 3, 6}. A key fact is that we always want to have the identity sorted first. Because we have a base, we know that only one of our permutations maps 5 to 5 and 4 to 4, and that must be the identity. Check it:

In[8]:= PermutationReplace[newbase, elems]
Out[8]= {{5, 4}, {3, 4}, {4, 5}, {6, 5}, {5, 6}, {1, 6}, {6, 1}, {2, 1}, {1, 2}, {3, 2}, {4, 3}, {2, 3}}

Note that we have again different pairs of images, but now they are not sorted in any obvious way. The good way to sort them with the new base is

In[9]:= newelems = GroupElements[group, GroupActionBase -> newbase];

The identity is still the first one:

In[10]:= newelems[[1]]
Out[10]= Cycles[{}]

but the rest are sorted differently:

In[11]:= elems === newelems
Out[11]= False

To explain what has happened, look at this:

In[12]:= newimages = PermutationReplace[newbase, newelems]
Out[12]= {{5, 4}, {5, 6}, {4, 5}, {4, 3}, {1, 2}, {1, 6}, {2, 1}, {2, 3}, {3, 4}, {3, 2}, {6, 5}, {6, 1}}

Remember the priorities {5, 4, 1, 2, 3, 6}.

You can also compare the order of elems and the order of newelems:

In[13]:= order = Flatten[Position[elems, #] & /@ newelems]
Out[13]= {1, 5, 3, 11, 9, 6, 8, 12, 2, 10, 4, 7}

In[14]:= PermutationReplace[newbase, elems][[order]] === newimages
Out[14]= True

Or you can think about it in this alternative way:

In[15]:= PermutationReplace[{1, 2, 3, 4, 5, 6}, newelems] // Column
Out[15]= {1, 2, 3, 4, 5, 6}
         {3, 2, 1, 6, 5, 4}
         {2, 1, 6, 5, 4, 3}
         {6, 1, 2, 3, 4, 5}
         {5, 4, 3, 2, 1, 6}
         {3, 4, 5, 6, 1, 2}
         {4, 5, 6, 1, 2, 3}
         {6, 5, 4, 3, 2, 1}
         {1, 6, 5, 4, 3, 2}
         {5, 6, 1, 2, 3, 4}
         {2, 3, 4, 5, 6, 1}
         {4, 3, 2, 1, 6, 5}

First you try to put 5 in its place (look at the first two lists). Then you try to put 4 in its place. It will be possible in the first of those two (the identity), but not in the second one. Then you try to put 4 in the fifth place, and then you worry about what to put in the 4th place, etc.

This is all rather technical, though standard in computational group theory. Bases are not typically needed in standard operations with groups, but bases and strong generators are at the core of the internal algorithms. For example, if you want the stabilizer of a group by some point p then it helps to have p as the first element in the base. GroupStabilizer will do those changes of base internally for you. GroupActionBase can also be useful with large groups, because performance of various operations can be very different for different bases of the same group.

Hope that helps!

share|improve this answer
    
I follow until you use the pure function at In[13]. I haven't quite figured them out yet. I also forgot to link the related question on math.SE. We've figured out that the first several group elements given by GroupElements are the ones that fix the first point in the base, and then the next several group elements are the ones that also fix the second point, etc. It's within those elements that fix the next point, I don't see how those are sorted yet. –  Travis Bemrose Apr 16 at 2:59
    
BTW, I appreciate the thorough answer! I see what's happening at In[12], but I don't see how your comment "Remember the priorities {5, 4, 1, 2, 3, 6}" relates to it. –  Travis Bemrose Apr 16 at 3:16
    
For example, I ran elems=GroupElements[SymmetricGroup[4],GroupActionBase->{3,2,4,1}]; PermutationReplace[{1,2,3,4},elems]//Column and got {1,2,3,4}, {4,2,3,1}, {1,4,3,2}, {2,4,3,1}, .... I get the first two, but it seems to me the next 2 should be switched. It had to move 2, but instead of putting it in the lowest priority place first (1), it put the 2 in the 4th place, which had higher priority. –  Travis Bemrose Apr 16 at 3:39
    
Working with permutations there is always the feeling that you could/should reverse something. You would end up sorting the inverses, which typically gives a different result. In your example with base {3,2,4,1}, you first fill slot 3 with point 3, and then you can fill slot 2 with point 2 for the first two permutations, but not for the third. Hence in the second slot you put 4, which is the next point of the base. Then you have to fill slot number 4, and you have already used points 3 and 4, so you take 2, because it is before 1 in your base. That explains the third permutation. –  jose Apr 16 at 4:32
    
Concerning my comment after Out[12], take the first elements of all pairs. You get 554411223366. Compare with the list of priorities {5, 4, 1, 2, 3, 6}. Then for each pair of second elements, say 53 for first element 4, note that 5 is before 3 in that list. –  jose Apr 16 at 4:40

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.