3
$\begingroup$

I'm trying to count the unique orbits of a regular hexagon such that each vertex is either Black or White and each edge is either Red, Gree, or Blue. The group I've chosen to act on the hexagon is the dihedral group $D_7$, $$\{e,r,r^2,r^3,r^4,r^5,r^6,s,rs,r^2s,r^3s,r^4s,r^5s,r^6s\}$$ where $r$ is a rotation by $\frac{\pi}{3}$, and $s$ a reflection in the axis connecting two opposite vertices or the midpoints of two opposite edges. When chopped up, I get the following partition into conjugacy classes: $$\{e\} \hspace{0.5cm} \{r,r^6\}\hspace{0.5cm} \{r^2,r^5\}\hspace{0.5cm} \{r^3,r^4\}\hspace{0.5cm}\{s,r^2s,r^4s,r^6s\}\hspace{0.5cm} \{rs,r^3s,r^5s\}$$ Taking the first element of each conjugacy class as the representative, I then go about counting the permutations that are left fixed by that representative. Here's my count (note, $X^g$ denotes the set of all regular hexagons left fixed by group element $g$): $$\begin{align*} |X^e|&=3^6\times 2^6 & |X^r|&=3\times 2 & |X^{r^2}|&=3^2\times 2^2\\ |X^{r^3}|&=3^3\times 2^3 & |X^s|&=3^4\times 2^3 + 3^3\times 2^4 & |X^{rs}|&=3^3\times 2^4 + 3^4\times 2^3 \end{align*}$$

Notice that the order of the last two sets, $X^s$ and $X^{rs}$, are sums: one addend counts the reflections through opposite vertices and the other through midpoints of opposite sides. When I apply the Counting Theorem (aka Burside's Lemma?) I obtain $$\frac{1}{14}[3^6\times 2^6 + 2(3\times 2) + 2(3^2 \times 2^2) + 2(3^3\times 2^3) + 4(3^4\times 2^3 + 3^3 \times 2^4) + 3(3^3\times 2^4 + 3^4 \times 2^3)]$$ and it is here I stumbled when I saw this product is not an integer.

$\endgroup$
  • 1
    $\begingroup$ The group to act on a hexagon ($=6$ vertices?) is the dihedral group $D_6$ of order $12$, right? Also the size of a conjugacy class must always divide the group order, so $D_7$ can not have conjugacy classes of order $4$ or $3$. In fact, in $D_7$, all reflections are conjugate. $\endgroup$ – ladisch Jun 20 '16 at 11:05
  • $\begingroup$ Good points. What do you think then of my self-correction below? $\endgroup$ – Jacopo Stifani Jun 20 '16 at 18:12
  • 1
    $\begingroup$ I'm not sure whether it is right here to give the corrections in an answer instead of editing your question. Besides that, it is unclear to me what you think the conjugacy classes are, but judging from your formula below you are probably wrong about them: the rotations separate into the classes $\{e\}$, $\{r, r^5\}$, $\{r^2, r^4\}$ and $\{r^3\}$. Moreover, I do not understand why $|X^s|$ and $|X^{rs}|$ should be sums: If, for example, $s$ is a reflection in an axis connecting two vertices, then there are 4 orbits on the vertices and 3 on the edges, so $|X^s|= 3^3\times 2^4$. $\endgroup$ – ladisch Jun 21 '16 at 13:51
  • $\begingroup$ For the record: I get the same result as Marko Riedel below, namely $4183$. $\endgroup$ – ladisch Jun 21 '16 at 13:53
2
$\begingroup$

I now redo the calculation (correctly, I hope), using the notation of the original question. The symmetry group of the hexagon is the dihedral group $D_6$, $$ D_6 = \langle r,s \mid r^6 = s^2 = 1, r^s = r^{-1} \rangle, $$ where $r$ is a rotation by $\frac{2\pi}{6}$, and $s$ a reflection in an axis connecting two opposite vertices. The conjugacy classes of $D_6$ are $$ \{e\}, \hspace{0.5cm} \{r,r^5\}, \hspace{0.5cm} \{r^2,r^4\},\hspace{0.5cm} \{r^3\}, \hspace{0.5cm} \{s,r^2s,r^4s\},\hspace{0.5cm} \{rs,r^3s,r^5s\}.$$ For each conjugacy class, we have to count the vertex-and-edge-colored hexagons that are left fixed by a representative of the conjugacy classes. Let $X^g$ denote the set of all vertex-and-edge-colored regular hexagons left fixed by $g$. Then $$\begin{align*} |X^e| &= 3^6\times 2^6, & |X^r| &= 3\times 2, & |X^{r^2}| &= 3^2 \times 2^2 , \\ |X^{r^3}| &= 3^3 \times 2^3, & |X^s| &= 3^3 \times 2^4, & |X^{rs}| &= 3^4 \times 2^3 . \end{align*}$$ For example, $|X^s|= 3^3 \times 2^4$ because $s$ has $3$ orbits on the edges and $4$ orbits on the vertices and so we can choose the colors of $3$ edges and $4$ vertices, such that we get a hexagon that is fixed by $s$. (Recall that $s$ is a reflection in an axis connecting two opposite vertices. $rs$ is a reflection in an axis connecting midpoints of opposite edges.)
Thus the number of orbits is $$ \frac{1}{12} [3^6 \times 2^6 + 2 (3\times 2) + 2 (3^2 \times 2^2) + (3^3\times 2^3) + 3(3^3 \times 2^4) + 3(3^4 \times 2^3)] = 4183.$$

$\endgroup$
  • 1
    $\begingroup$ This looks good, thanks for posting, I hope the OP will find it useful. In my experience classifying the reflections according to the six possible axes makes mental factorization into cycles somewhat easier. (+1). $\endgroup$ – Marko Riedel Jun 23 '16 at 17:55
  • 1
    $\begingroup$ @MarkoRiedel: I agree. Of course, conjugate elements always yield the same cycle type, but not conversely (in general), and it seems usually more naturally to classify the elements of the group according to geometry or directly according to cycle type. But OP used conjugacy classes, and so did I... $\endgroup$ – ladisch Jun 24 '16 at 11:21
  • $\begingroup$ Thank you both for the help. My error comes from viewing $s$ as a reflection in an axis connecting two opposite vertices or in an axis connecting the midpoints of two opposite edges. The same goes for $rs$. What is the problem with this? For, say, $s$, can I not reflect the hexagon in either axis? $\endgroup$ – Jacopo Stifani Jun 27 '16 at 11:29
  • 1
    $\begingroup$ @JacopoStifani: Of course you could also take for $s$ a reflection in an axis connecting midpoints of opposite edges. Then $rs$ would be a reflection in an axis connecting opposite vertices. The point is that there are two different sorts of reflections, and the reflections in these two classes fix a different number of colored hexagons. The summands corresponding to these two classes of reflections must be computed separately. $\endgroup$ – ladisch Jun 27 '16 at 13:29
2
$\begingroup$

For future reference I would like to document how we can do this calculation using a cycle index. The key observation here is the following: the cycle structure of a rotation (but not a reflection) acting on the vertices and edges is the same for edges and vertices. So we may compute the cycle index by duplicating the cycle structure of the terms of the ordinary cycle index acting on the vertices. Do the rotations first. There is the identity which yield

$$a_1^6 b_1^6.$$

A rotation that takes zero to one or five yields

$$2 a_6 b_6.$$

A rotation that takes zero to two or four yields

$$2 a_3^2 b_3^2.$$

The rotation that takes zero to three yields

$$a_2^3 b_2^3.$$

For the reflections we get reflections about an axis passing through two opposite vertices to get (note the different cycle structure for the vertices and the edges)

$$3 a_1^2 a_2^2 b_2^3.$$

Then there are reflections about an axis passing through the midpoints of two opposite edges which yield (once again we have a different cycle structure for vertices and edges)

$$3 a_2^3 b_1^2 b_2^2.$$

Now we have two colors for the vertices and three for the edges which by Burnside must be constant on the cycles. This yields

$$\frac{1}{12} \left(6^6 + 2\times 6 + 2\times 6^2 + 6^3 + 3 \times 2^4 3^3 + 3 \times 2^3 3^4\right).$$

This yields for the desired end result the value

$$4183.$$

It was not practicable to verify this with Maple as resource consumption (time, space) was unacceptable. Perl seems to cope quite well.

#! /usr/bin/perl -w
#

sub convert {
    my ($val, $base, $len) = @_;

    my @res;

    for(my $pos = 0; $pos < $len; $pos++){
        my $digit = $val % $base;

        push @res, $digit;
        $val = ($val - $digit) / $base;
    }

    return \@res;
}

MAIN : {
    my ($idx2, $idx3, $d2, $d3);

    my %orbits;

    for(my $idx2 = 0; $idx2 < 2**6; $idx2++){
        $d2 = convert $idx2, 2, 6;
        for(my $idx3 = 0; $idx3 < 3**6; $idx3++){
            $d3 = convert $idx3, 3, 6;

            my @interl;

            for(my $pos = 0; $pos < 6; $pos++){
                push @interl, 
                $d2->[$pos], $d3->[$pos];
            }

            my (%orbit, $entry, $refent);

            for(my $rot=0; $rot<12; $rot+=2){
                $entry = 
                    [@interl[$rot..11],
                     @interl[0..$rot-1]];
                $orbit{join('-', @$entry)} = 1;
            }

            for(my $refl=0; $refl<12; $refl+=4){
                $entry = 
                    [@interl[$refl..11],
                     @interl[0..$refl-1]];

                $refent =
                    [$entry->[0], 
                     reverse(@$entry[1..11])];
                $orbit{join('-', @$refent)} = 1;

                $refent =
                    [$entry->[2], 
                     $entry->[1], 
                     $entry->[0],
                     reverse(@$entry[3..11])];
                $orbit{join('-', @$refent)} = 1;
            }

            $orbits{join('|', sort(keys %orbit))} = 1; 
        }
    }

    print scalar(keys %orbits);

    printf " (%d)\n",
    (6**6
     + 2 * 6
     + 2 * 6**2
     + 6**3
     + 3 * 2**4 * 3**3
     + 3 * 2**3 * 3**4)/12;

    1;
}

Remark. We could adapt the join statements above to use empty separators which however reduces readability of the data structure during debugging.

$\endgroup$
  • $\begingroup$ I don't know what a cycle index is or understand your solution, but will keep it in my back pocket. I re-did my calculation, and it was wrong, but my new value still doesn't match up with yours. Are you 100% certain of your final answer? $\endgroup$ – Jacopo Stifani Jun 22 '16 at 20:41
  • 1
    $\begingroup$ I am fairly certain as I verified it using enumeration of all orbits. However I am not the only user on MSE who solves Polya / Burnside. We may yet see another answer perhaps using a different notation. There is the comment by @ladisch who says he was able to confirm my result. $\endgroup$ – Marko Riedel Jun 22 '16 at 21:02
0
$\begingroup$

O negligence! Fit for a fool to fall by.

All credit to @ladisch for obviously making the obvious.

a) I should have used $D_6$ instead of $D_7$. So chop off the $r^6$ and $r^6s$ from the group and we get the dihedral group of order 12.

b) The conjugacy classes containing rotations only are adjusted acrodingly and $\{s,r^2s,r^4s,r^6s\}$ becomes $\{s,r^2s,r^4s\}$.

c) My counting of the elements of $X^g$, where $g$ is a representative of the conjugacy classes, remains the same...

d)... but the product $$\frac{1}{12}[3^6\times 2^6 + 2(3\times 2) + 3^2 \times 2^2 + 2(3^3\times 2^3) + 3(3^4\times 2^3) + 3(3^3\times 2^4)]=4183$$

$\endgroup$
  • $\begingroup$ There seems to be an error in the arithmetic. $\endgroup$ – Marko Riedel Jun 21 '16 at 0:44

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.