2
$\begingroup$

I have a group $G = \oplus_{\alpha} \mathbb{Z}/2$, where all the direct summands are indexed by the elements of a set (a list in GAP).

I want to define in GAP an action of this group on a vector space. I can easily describe how each generator (an element of the list) should act on a vector from this space (it should be enough to define the whole action).

How can I do it? It seems that there might be a natural and convenient way.


Originally my problem was formulated in a somewhat different way, so maybe there could be another approach.

I have the collection of all possible colourings of a polytope into two colours (0 and 1). I want to find the quotient set of the following equivalence relation: I can simultaneously inverse colours of all the facets containing a common vertex (and I can do that for all vertices) and I also consider to be equal any two colourings which differ by the action of an element of the automorphism group $Aut(P)$ of this polytope.

To do this, I intended to try the following. Firstly, to consider the dual polytope. Then I will have the set of all vertices {$1, \ldots, n$} and all colourings will be represented by the elements of $\oplus_{1}^n \mathbb{Z}/2$. Also one сan compute the automorphism group of a polytope and represent it just in terms of permutations.

So I wished to find the orbit space of the action of the group $G = \oplus_{\alpha} \mathbb{Z}/2$, summands of which are indexed by the facets (i.e., by the certain collections of vertices). The group is supposed to act in the obvious way: for example, the generator corresponding to the facet {1,2,3} will send a vector $(x_1, x_2, x_3, \ldots, x_n)$ to $(1-x_1, 1-x_2, 1-x_3, \ldots, x_n)$. I wanted to consider after that the action of the group $Aut(P)$ on the orbit space of the first action (it would be correct to just take representatives and act on them). I wanted whereby to reduce the problem to computation of orbits in GAP. I am sorry if the whole thing seems to be a little boring.


The following part is not about defining an action on generators but about an attempt to solve the original problem (for the 3-dimensional cube, for example). Firstly, I use the method proposed by Alexander Konovalov below (to deal with the first part of the equivalence relation in question):

gap> facets := [[1, 3, 5, 7], [2, 4, 6, 8], [1, 2, 5, 6], 
[3, 4, 7, 8], [1, 2, 3, 4], [5, 6, 7, 8]];;
gap> gps:=List([1..Length(facets)], i -> Group((1,2)));;
gap> G:=DirectProduct(gps);;
gap> action1:=function( v, g )
  local i, j, w;
  for i in [1..Length(facets)] do
    if not IsOne(Image(Projection(G,i),g)) then
      w := ShallowCopy(v);
      for j in facets[i] do
        w[j] := 1 - w[j]; 
      od;
    fi;
  od;
  return w;
end;;

gap> orb := Orbits(G,GF(2)^8,action1);;

Then I try to deal with the second part (it is correct to consider the action of the group $Sym(P)$ on representatives of classes of the orbit space, thereby $Sym(P)$ acts on the orbit space of the first action, I want to find the space of the second one). The following part is mine and is somewhere incorrect:

 action2 := function (v,g)
 local i;
    for i in [1..Length(orb)] do
      if (OnTuples(v[1],g) in orb[i]) then
     break;
     fi;
    od;
   return orb[i];
 end;

The group of the cube's symmetries:

 gap> sym := Group((3,5)(4,6), (2,3)(6,7),(1,2)(3,4)(5,6)(7,8));

While trying to find the orbits:

 gap> Orbits(sym, orb, action2);;
  Error, Panic: cannot convert <list> (is a object (data)) to a plain list in
   if OnTuples( v[1], g ) in orb[i]  then
    break;
   fi; called from 
 act( p, gen ) called from
 OrbitOp( G, D[pos], gens, acts, act ) called from
 op( G, D, gens, gens, act ) called from
 <function "unknown">( <arguments> )
 called from read-eval loop at line 72 of *stdin*

Question to the code above: what would you like to do in the line

   if OnTuples( v[1], g ) in orb[i]  then

I've inserted the line

Print( v[1], "  " , g, "\n");

just before it, and it prints [ 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2), 0*Z(2) ] as v[1] and g is (3,5)(4,6). But OnTuples( tup, g ) returns the list formed by the images of all points x of tup via the action function OnPoints applied to x and g. We haven't defined what OnPoints should do on elements of v[1], hence the problem.

$\endgroup$
  • $\begingroup$ If you want to define an action of a group, you have to specify on which domain it's acting - please edit your question to provide more details. Also, please show what are you doing in GAP, this would help to understand your settings and may ease answering. Finally, math.stackexchange.com/q/509769 may be of some help. $\endgroup$ – Alexander Konovalov Apr 4 '15 at 20:35
  • 1
    $\begingroup$ @AlexanderKonovalov The domain of the action in question is a vector space, and the list is just a collection of subsets of integers. The image of a vector under a generator depends on these integers (and, of course, everything commutes, so it is a correct definition). The point is that it would not be a problem to describe how a generator acts on this vector if I can treat it as an element of my list. I wanted to do define the whole action as a function of two variables but I do not know how $\endgroup$ – Hypsoline Apr 4 '15 at 22:20
  • 1
    $\begingroup$ @AlexanderKonovalov 1. to naturally represent in GAP a direct sum where all summands are indexed by the elements of a list; 2. to define an action only giving images for a set of group generators. So I am looking for something like GroupHomomorphismByImages for actions (though one possibly can define a homomorphism to $GL_n(\mathbb{Z}/2)$ and construct an action thereafter). Thanks a lot. $\endgroup$ – Hypsoline Apr 4 '15 at 22:20
  • $\begingroup$ Thanks for comments. What do you mean by $\mathbb{Z}/2$ - is it $\mathbb{Z}/2\mathbb{Z}$? $\endgroup$ – Alexander Konovalov Apr 5 '15 at 16:29
  • 1
    $\begingroup$ @AlexanderKonovalov Yes. I can describe the action in a more detailed way. My list is a certain collection of subsets of integers and I want the generator corresponding to a such subset to inverse signs of all coordinates with numbers from this subset. For example, [2,4] will send $(x_1,x_2,x_3,x_4,x_5)$ to $(x_1,-x_2,x_3,-x_4,x_5)$. I just thought that the nature of this particular action is not of importance and the key problem is to describe the group with summands indexed by the elements of a list and to define an action only describing how the elements of the list should act. $\endgroup$ – Hypsoline Apr 5 '15 at 17:17
2
$\begingroup$

First, let facet be a lists of lists representing facets:

gap> facets := [[1, 3, 5, 7], [2, 4, 6, 8], [1, 2, 5, 6], 
> [3, 4, 7, 8], [1, 2, 3, 4], [5, 6, 7, 8]];
[ [ 1, 3, 5, 7 ], [ 2, 4, 6, 8 ], [ 1, 2, 5, 6 ], [ 3, 4, 7, 8 ], 
  [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ] ]

Now we will form a direct product of as many copies of the group of order 2 as the number of elements in the list `facets:

gap> gps:=List([1..Length(facets)], i -> Group((1,2)));
[ Group([ (1,2) ]), Group([ (1,2) ]), Group([ (1,2) ]), Group([ (1,2) ]), 
  Group([ (1,2) ]), Group([ (1,2) ]) ]
gap> G:=DirectProduct(gps);
Group([ (1,2), (3,4), (5,6), (7,8), (9,10), (11,12) ])

Thus, we have one-to-one correspondence between components of the direct product and elements of facets. Of course, it would be possible to use another representation of $C_2$, but it seems that using the permutation representation works so far works sufficiently well.

The next step would be to figure out which components are used to form a given element of a direct product. For that, we have to use Projection as described here. For example, for some random element of $G$

gap> g:=Random(G);
(1,2)(5,6)(11,12)
gap> List([1..Length(facets)], i -> Image(Projection(G,i),g));
[ (1,2), (), (1,2), (), (), (1,2) ]

we see that 1st, 3rd and 6th components are involved, since the image of the projection onto these components is non-trivial (if one ever needs to embed an element of a component into a direct product, one should use Embedding as described here.

Now we may define the function to calculate the image of a vector v under the action of an element g:

action1:=function( v, g )
  local i, j, w;
  for i in [1..Length(facets)] do
    if not IsOne(Image(Projection(G,i),g)) then
      w := ShallowCopy(v);
      for j in facets[i] do
        w[j] := One(w[j]) - w[j];
      od;
    fi;
  od;
  return w;
end;

For example, now we may check calculated the orbits of the vector space $\mathbb{Z}_2^8$ under the action of the above defined group G:

gap> orb := Orbits(G,GF(2)^8,action1);
[ [ <an immutable GF2 vector of length 8>, <an immutable GF2 vector of length 
        8>, <an immutable GF2 vector of length 8>, 
... 
      <an immutable GF2 vector of length 8>, 
      <an immutable GF2 vector of length 8> ] ]
gap> Length(orb);
16
gap> List(orb,Length);
[ 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16 ]

Thus, we obtained 16 orbits, each with 16 elements. The output is completely usable but not fully informative, since GAP uses compressed representations for vectors over $GF(2)$. You may use Display (see more here) to produce more meaningful output where dots corresponds to zero and ones to identity elements of $GF(2)$:

gap> Display(orb[1]);
 . . . . . . . .
 1 . 1 . 1 . 1 .
 . 1 . 1 . 1 . 1
 1 1 1 1 1 1 1 1
 1 1 . . 1 1 . .
 . 1 1 . . 1 1 .
 1 . . 1 1 . . 1
 . . 1 1 . . 1 1
 1 1 1 1 . . . .
 . 1 . 1 1 . 1 .
 1 . 1 . . 1 . 1
 . . . . 1 1 1 1
 . . 1 1 1 1 . .
 1 . . 1 . 1 1 .
 . 1 1 . 1 . . 1
 1 1 . . . . 1 1

Remark: since action1 refers to global variables facets and G, a cleaner approach would be to have a function which performs the whole calculation and has action1 as its local variable:

OrbitsWithMyAction:=function( V, facets )
local gps, i, G, action1;
gps:=List([1..Length(facets)], i -> Group((1,2)));
G:=DirectProduct(gps);

    action1:=function( v, g )
      local i, j, w;
      for i in [1..Length(facets)] do
        if not IsOne(Image(Projection(G,i),g)) then
          w := ShallowCopy(v);
          for j in facets[i] do
            w[j] := One(w[j]) - w[j];
          od;
        fi;
      od;
      return w;
    end;

return Orbits(G,V,action1);

end;

One could call it then with e.g. OrbitsWithMyAction(GF(2)^8,facets); and then it's guaranteed that it will access proper facets (its argument) and G (its local variable) and not anything else. Otherwise imagine e.g. situation what one changed facets but forgot to construct new G, and nothing works then. One could perhaps even construct the vector space GF(2)^n inside OrbitsWithMyAction as well.

$\endgroup$
  • $\begingroup$ Thank you very much! The vector space on which the group acts is $\oplus_{1}^n \mathbb{Z}/2$, where {1,...,n} are the vertexes of the dual polytope. Then colourings of our polytope into two colours correspond to the elements of the space, and this part of the equivalence relation I tried to describe as "we can simultaneously inverse colours of all the facets containing a common vertex" will be realised by considering the orbit space of the action, by which a facet (a generator of G) substitutes a coordinate $x_i$ by $1-x_i$ (I am sorry I've mentioned $-x_i$ somewhere above) if $i$ is in it. $\endgroup$ – Hypsoline Apr 9 '15 at 17:16
  • $\begingroup$ Maybe it would be easier not to mention dual polytopes at all and just to say that we have colourings of the vertexes of a polytope and that we can simultaneously inverse the colours of all the vertexes belonging to a common facet. I would like to ask about realisation of the second part of the equivalence. I tried to do it and faced a problem (likely, it is just a consequence of my bad knowledge of GAP). I added the details to the original question (though it is quite far from the theme of the topic). $\endgroup$ – Hypsoline Apr 9 '15 at 17:33
  • $\begingroup$ Thanks. I've posted a question by editing the answer, please have a look. $\endgroup$ – Alexander Konovalov Apr 9 '15 at 18:34
  • $\begingroup$ Alexander, I am very sorry for this fault of mine. Actually I meant the action realised by the standard function Permuted, but after superficial examination of the GAP manual I supposed that OnTuples is what I need. I even tried to check it via OnTuples([1,2,3],(1,2)); and it was OK) Yet the whole thing works with Permuted and the answer for the cube (at least its order, namely 5) coincides with that I already knew! Thank you so much again! $\endgroup$ – Hypsoline Apr 9 '15 at 20:32
  • $\begingroup$ Fantastic! I will try to make the code more robust when I will have time. In the meantime, beware of the following: acting functions use global variables (facets, orb), so it's easy to make your results inconsistent if e.g. you will change them incidentally. Also, please use $\mathbb{Z}/2\mathbb{Z}$ or specify that you will denote it by $\mathbb{Z}_2$ - your style of writing $\mathbb{Z}/2$ may be very confusing :) $\endgroup$ – Alexander Konovalov Apr 9 '15 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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