Harmonic morphisms from cubic graphs of order 8 to a graph of order 4

There are five simple cubic graphs of order 8 (listed here) and there are 6 connected graphs of order 4 (listed here). But before we get started, I have a conjecture.

Let \Gamma_1 be a simple graph on n1 vertices, \Gamma_2 a simple graph on n2 vertices, and assume there is a harmonic morphism \phi:\Gamma_1 \to \Gamma_2. Call an n1-tuple of “colors” \{0,1,2,..., n2-1\} a harmonic color list (HCL) if it’s attached to a harmonic morphism in the usual way (the ith coordinate is j if \phi sends vertex i of \Gamma_1 to vertex j of \Gamma_2). Let S be the set of all such HCLs. The automorphism group G_1 of \Gamma_1 acts on S (by permuting coordinates associated to the vertices of \Gamma_1, as does the automorphism group G_2 of \Gamma_2 (by permuting the “colors” associated to the vertices of \Gamma_2). These actions commute. Clearly S decomposes as a disjoint union of distinct G_1\times G_2 orbits. The conjecture is that there is only one such orbit.

Note: Caroline Melles has disproven this conjecture. Still, the question of the number of orbits is an interesting one, IMHO.

Onto the topic of the post! The 6 connected graphs of order 4 are called P4 (the path graph), D3 (the star graph, also K_{3,1}), C4 (the cycle graph), K4 (the complete graph), Paw (C3 with a “tail”), and Diamond (K4 but missing an edge). All these terms are used on graphclasses.org. The results below were obtained using SageMath.

  1. We start with the graph \Gamma_1 listed 1st on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 2, -2, -2], 2). This graph \Gamma_1 has diameter 3, girth 3, and its automorphism group G is generated by (5,6), (1,2), (0,3)(4,7), (0,4)(1,5)(2,6)(3,7), |G|=16. This graph is not vertex transitive. Its characteristic polynomial is x^8 - 12x^6 - 8x^5 + 38x^4 + 48x^3 - 12x^2 - 40x - 15. Its edge connectivity and vertex connectivity are both 2. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw. However, there are 48 non-trivial harmonic morphisms to \Gamma_2=K4. For example,
    3regular8a-K4-32103210 (the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots), and 3regular8a-K4-01230213 (again, the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots). There are 8 non-trivial harmonic morphisms to \Gamma_2={\rm Diamond}. For example, 3regular8a-Diamond-12033201 and 3regular8a-Diamond-10233201Here the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3}, while the automorphism group of the graph \Gamma_1 acts by permuting some of the coordinates, for example, it can swap the 5th and 6th coordinates.Next, we take for \Gamma_1 the graph listed 2nd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -2, 4, 2], 2). This graph \Gamma_1 has diameter 3, girth 3, and its automorphism group G is generated by (1,7)(2,6)(3,5), (0,4)(1,3)(5,7), |G|=4 (obviously too small to act transitively on the vertices). Its characteristic polynomial is x^8 - 12x^6 - 4x^5 + 38x^4 + 16x^3 - 36x^2 - 12x + 9, its edge connectivity and vertex connectivity are both 3. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw or K4. However, it has 4 non-trivial harmonic morphisms to Diamond. They are:
    3regular8b-Diamond-32103210 3regular8b-Diamond-301230123regular8b-Diamond-123012303regular8b-Diamond-10321032Let \Gamma_1 denote the graph listed 3rd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 4, -2, 3, 3, 4, -3, -3], 1). This graph \Gamma_1 has diameter 2, girth 3, and its automorphism group G is generated by (4,6), (1,2)(3,5), (0,1)(5,7), |G|=12. It does not act transitively on the vertices. Its characteristic polynomial is x^8 - 12x^6 - 2x^5 + 36x^4 - 31x^2 + 12x and its edge connectivity and vertex connectivity are both 3.
    This graph has no non-trivial harmonic morphisms to P4 or C4 or Paw or K4 or Diamond. However, it has 6 non-trivial harmonic morphisms to D3, for example,
    3regular8c-D3-33302010
    The automorphism group of D3 (the symmetric group of degree 3) acts by permuting the colors {0,1,2,3} and so yields a total of 6=3! such harmonic color plots.Let \Gamma_1 denote the graph listed 4th on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -3, 3, 4], 2). This example is especially interesting. Otherwise known as the “cube graph” Q_3, this graph \Gamma_1 has diameter 3, girth 4, and its automorphism group G is generated by ((2,4)(5,7), (1,7)(4,6), (0,1,4,5)(2,3,6,7), |G|=48. It is vertex transitive. Its characteristic polynomial is x^8 - 12x^6 + 30x^4 - 28x^2 + 9 and its edge connectivity and vertex connectivity are both 3.
    This graph has no non-trivial harmonic morphisms to D3 or P4 or Paw. However, it has 24 non-trivial harmonic morphisms to C4, 24 non-trivial harmonic morphisms to K4, and 24 non-trivial harmonic morphisms to Diamond. An example of a non-trivial harmonic morphism to K4:


    3regular8d-K4-31230210 A few examples of a non-trivial harmonic morphism to Diamond:
    3regular8d-Diamond-23320110 and
    3regular8d-Diamond-33210210 A few examples of a non-trivial harmonic morphism to C4:
    3regular8d-C4-12332100 3regular8d-C4-03322110 3regular8d-C4-33012210

    The automorphism group of C4 acts by permuting the colors {0,1,2,3} cyclically, while the automorphism group G acts by permuting coordinates. These yield more harmonic color plots.

Duursma zeta function of a graph

I’m going to start off with two big caveats:

  1. This is not Duursma‘s definition, it’s mine.
  2. I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let C be an [n,k,d]_q code, ie a linear code over GF(q) of length n, dimension k, and minimum distance d. In general, if C is an [n,k,d]_q-code then we use [n,k^\perp,d^\perp]_q for the parameters of the dual code, C^\perp. It is a consequence of Singleton’s bound that n+2-d-d^\perp\geq , with equality when C is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function \zeta=\zeta_C:

\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},
where P(T)=P_C(T) is a polynomial of degree n+2-d-d^\perp, called the zeta polynomial of C. We next sketch the definition of the zeta polynomial.

If C^\perp denotes the dual code of C, with parameters [n,n-k,d^\perp] then the MacWilliams identity relates the weight enumerator A_{C^\perp} of C^\perp to the weight enumerator A_{C} of C:

A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).
A polynomial P(T)=P_C(T) for which

\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .
is a (Duursma) zeta polynomial of C.

Theorem (Duursma): If C be an [n,k,d]_q code with d\geq 2 and d^\perp\geq 2 then the Duursma zeta polynomial P=P_C exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let \Gamma=(V,E) be a graph having |V(\Gamma)| vertices and |E(\Gamma)| edges. We define the zeta function of \Gamma via the Duursma zeta function of the binary linear code defined by the cycle space of \Gamma.

Theorem (see [DKR], [HB], [JV]): The binary code B=B_\Gamma generated by the rows of the incidence matrix of \Gamma is the cocycle space of \Gamma over GF(2), and the dual code B^\perp is the cycle space Z=Z_\Gamma of \Gamma:

B_\Gamma^\perp = Z_\Gamma.
Moreover,
(a) the length of B_\Gamma is |E|, dimension of B_\Gamma is |V|-1, and the minimum distance of B_\Gamma is the edge-connectivity of \Gamma,
(b) length of Z_\Gamma is |E|, dimension of Z_\Gamma is |E|-|V|+1, and the minimum distance of Z_\Gamma is the girth of \Gamma.

Call Z_\Gamma the cycle code and B_\Gamma the cocycle code.

Finally, we can introduce the (Duursma) zeta function \Gamma:

\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},
where P=P_\Gamma=P_{Z_\Gamma} is the Duursma polynomial of \Gamma.

Example: Using SageMath, when \Gamma = W_5, the wheel graph on 5 vertices, we have

P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.
All its zeros are of absolute value 1/\sqrt{2}.

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.

Harmonic morphisms to D_3 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the tree \Gamma_2=D_3. This graph is also called a star graph Star_3 on 3+1=4 vertices, or the bipartite graph K_{1,3}.
D3-0123

We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=D_3 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=D_3 (we let 3 be the numerical notation for the color red), the blue vertices in \Gamma_1 to the blue vertex of \Gamma_2=D_3 (we let 2 be the numerical notation for the color blue), the green vertices in \Gamma_1 to the green vertex of \Gamma_2=D_3 (we let 1 be the numerical notation for the color green), and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=D_3 (we let 0 be the numerical notation for the color white).

First, a simple remark about harmonic morphisms in general: roughly speaking, they preserve adjacency. Suppose \phi:\Gamma_1\to \Gamma_2 is a harmonic morphism. Let v,w\in V_1 be adjacent vertices of \Gamma_1. Then either (a) \phi(v)=\phi(w) and \phi “collapses” the edge (vertical) (v,w) or (b) \phi(v)\not= \phi(w) and the vertices \phi(v) and \phi(w) are adjacent in \Gamma_2. In the particular case of this post (ie, the case of \Gamma_2=D_3), this remark has the following consequence: since in D_3 the green vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a green vertex adjacent to a blue or red vertex. In fact, any colored vertex can only be connected to a white vertex or a vertex of like color.

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms Star_4 \to D_3, plus the “obvious” ones obtained from that below and those induced by permutations of the vertices:
Star4-D3-00321.

My guess is that the harmonic morphisms Star_5\to D_3 can be described in a similar manner. Likewise for the higher Star_n graphs. Given a star graph \Gamma with a harmonic morphism to D_3, a leaf (connected to the center vertex 0) can be added to \Gamma and preserve “harmonicity” if its degree 1 vertex is colored 0. You can try to “collapse” such leafs, without ruining the harmonicity property.

Example 2: For graphs like \Gamma_1=
C3LeafLeafLeaf-D3-000321
there are only the 4 trivial harmonic morphisms \Gamma_1 \to D_3, plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 2.5: Likewise, for graphs like \Gamma_1=
3C3-D3-0332211
there are only the 4 trivial harmonic morphisms \Gamma_1 \to D_3, plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 3: This is really a non-example. There are no harmonic morphisms from the (3-dimensional) cube graph (whose vertices are those of the unit cube) to D_3.
More generally, take two copies of a cyclic graph on n vertices, C_n, one hovering over the other. Now, connect each vertex of the top copy to the corresponding vertex of the bottom copy. This is a cubic graph that can be visualized as a “thick” regular polygon. (The cube graph is the case n=4.) I conjecture that there is no harmonic morphism from such a graph to D_3.

Example 4: There are 30 non-trivial harmonic morphisms \Gamma_1 \to D_3 for the Peterson graph (the last of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page). Here is an example:
petersen-D3-0330120021
Another interesting fact is that this graph has an automorphism group (isomorphic to the symmetric group on 5 letters) which acts transitively on the vertices.

Example 5: There are 12 non-trivial harmonic morphisms \Gamma_1=K_{3,3} \to D_3 for the complete bipartite (“utility”) graph K_{3,3}. They are all obtained from either
K_3_3-D3-321000
or
K_3_3-D3-000231
by permutations of the vertices with a non-zero color (3!+3!=12).

Example 6: There are 6 non-trivial harmonic morphisms \Gamma_1 \to D_3 for the cubic graph \Gamma_1=(V,E), where V=\{0,1,\dots, 9\} and E = \{(0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 9), (2, 3), (2, 7), (3, 6), (4, 5), (4, 9), (5, 8), (6, 7), (7, 8), (8, 9)\}. This graph has diameter 3, girth 3, and edge-connectivity 3. It’s automorphism group is size 4, generated by (5,9) and (1,8)(2,7)(3,6). The harmonic morphisms are all obtained from
random3regular10e-D3-1011031102
by permutations of the vertices with a non-zero color (3!=6). This graph might be hard to visualize but it is isomorphic to the simple cubic graph having LCF notation [−4, 3, 3, 5, −3, −3, 4, 2, 5, −2]:
random3regular10e2
which has a nice picture. This is the ninth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page.

Example 7: (a) The first of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10f
This graph has diameter 5, automorphism group generated by (7,8), (6,9), (3,4), (2,5), (0,1)(2,6)(3,7)(4,8)(5,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(b) The second of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10g
This graph has diameter 4, girth 3, automorphism group generated by (7,8), (0,5)(1,2)(6,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(c) The third of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10h
This graph has diameter 3, girth 3, automorphism group generated by (4,5), (0,1)(8,9), (0,8)(1,9)(2,7)(3,6). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 8: The fourth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10i
This graph has diameter 3, girth 3, automorphism group generated by (4,6), (3,5), (1,8)(2,7)(3,4)(5,6), (0,9). There are 12 non-trivial harmonic morphisms \Gamma_1\to D_3. For example,
3regular10i-D3-2220301022
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors. Another example is
3regular10i-D3-1103020111
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors.

Example 9: (a) The fifth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10j
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,2,-2,-2,5],2) There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(b) The sixth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10k
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2) There are no non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 10: The seventh of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10l-D3-3330222010
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2). Its automorphism group is order 12, generated by (1,2)(3,7)(4,6), (0,1)(5,6)(7,9), (0,4)(1,6)(2,5)(3,9). There are 6 non-trivial harmonic morphisms \Gamma_1\to D_3, each obtained from the one above by permuting the non-zero colors.

Example 11: The eighth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10m
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 3, 5, -4, -3, 5, 2, 5, -2, 4],1). Its automorphism group is order 2, generated by (0,3)(1,4)(2,5)(6,7). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 12: (a) The tenth (recall the 9th was mentioned above) of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10o
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[3, -3, 5, -3, 2, 4, -2, 5, 3, -4],1). Its automorphism group is order 6, generated by (2,8)(3,9)(4,5), (0,2)(5,6)(7,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(b) The 11th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10p
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, 2, 5, -2],2). Its automorphism group is order 4, generated by (0,1)(2,9)(3,8)(4,7)(5,6), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(c) The 12th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10q
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -2, 2, 4, -2, 5, 2, -4, -2, 2],1). Its automorphism group is order 6, generated by (1,9)(2,8)(3,7)(4,6), (0,4,6)(1,3,8)(2,7,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(d) The 13th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10r
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2, 5, -2, 5, 5],2). Its automorphism group is order 8, generated by (4,8)(5,7), (0,2)(3,9), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 13: The 14th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10s-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Another harmonic morphism \Gamma_1\to D_3 is depicted as:
3regular10s-D3-0302222201
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. And another harmonic morphism \Gamma_1\to D_3 is depicted as:
3regular10s-D3-1110302011
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). Its automorphism group is order 48, generated by (4,6), (2,8)(3,7), (1,9), (0,2)(3,5), (0,3)(1,4)(2,5)(6,9)(7,8). There are a total of 18=3!+3!+3! non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 14: The 15th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10t-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, -4, 4],2). Its automorphism group is order 8, generated by (2,7)(3,8), (1,9)(2,3)(4,6)(7,8), (0,5)(1,4)(2,3)(6,9)(7,8). There are a total of 6=3! non-trivial harmonic morphisms \Gamma_1\to D_3.

Example 15: (a) The 16th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10u
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, 5, 5],2). Its automorphism group is order 4, generated by (0,3)(1,2)(4,9)(5,8)(6,7), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(b) The 17th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10v
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 5, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,6)(3,7)(4,8)(5,9), (0,1)(2,5)(3,4)(6,9)(7,8), (0,2)(1,9)(3,5)(6,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(c) The 18th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph \Gamma_1 depicted as:
3regular10w
This is an example of a “thick polygon” graph, already mentioned in Example 3 above. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,5)(3,4)(6,9)(7,8), (0,1)(2,6)(3,7)(4,8)(5,9), (0,2)(1,9)(3,6)(4,7)(5,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms \Gamma_1\to D_3.
(d) The 19th in the list of 19 is the Petersen graph, already in Example 4 above.

We now consider some examples of the cubic graphs having 12 vertices. According to the House of Graphs there are 109 of these, but we use the list on this wikipedia page.

Example 16: I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is no harmonic morphism \Gamma_1\to D_3 then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.

  1. \Gamma_1=(V_1,E_1), where E_1=\{ (0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  2. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  3. \Gamma_1=(V_1,E_1), where E_1=\{(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  4. This example has 12 non-trivial harmonic morphisms.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.) We show two such morphisms:
    3regular12d-D3-110302011111
    3regular12d-D3-103020111111
    The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
  5. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)
  6. This example has 12 non-trivial harmonic morphisms. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 7), (5, 6), (5, 8), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}. (This only differs by one edge from the one above.)
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
    We show two such morphisms:
    3regular12f-D3-111103020111
    3regular12f-D3-111110302011
    And here is another plot of the last colored graph:
    3regular12f2-D3-111110302011
    The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
  7. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 4), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 11), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)
  8. This example has 48 non-trivial harmonic morphisms. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 9), (7, 8), (7, 10), (8, 9), (8, 11), (9, 10), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)
    This example is also interesting as it has a large number of automorphisms – its automorphism group is size 64, generated by (8,10), (7,9), (2,4), (1,3), (0,5)(1,2)(3,4)(6,11)(7,8)(9,10), (0,6)(1,7)(2,8)(3,9)(4,10)(5,11). Here are examples of some of the harmonic morphisms using vertex-colored graphs:
    3regular12h-D3-302010302010
    3regular12h-D3-333333302010
    3regular12h-D3-030201030201
    3regular12h-D3-103020111111
    I think all the other non-trivial harmonic morphisms are obtained by (a) permuting the non-zero colors, or (b) applying a element of the automorphism group of the graph.
  9. (list under construction)

NCF Boolean functions

I recently learned about a new class of seemingly complicated, but in fact very simple functions which are called by several names, but perhaps most commonly as NCF Boolean functions (NCF is an abbreviation for “nested canalyzing function,” a term used by mathematical biologists). These functions were independently introduced by theoretical computer scientists in the 1960s using the term unate cascade functions. As described in [JRL2007] and [LAMAL2013], these functions have applications in a variety of scientific fields. This post describes these functions.

A Boolean function of n variables is simply a function f:GF(2)^n\to GF(2). Denote the GF(2)-vector space of such functions by B(n). We write an element of this space as f(x_1,x_2,\dots,x_n), where the variables x_i will be called coordinate variables. Let
Res_{x_i=a}:B(n)\to B(n-1)
denote the restriction map sending f(x_1,x_2,\dots,x_n) to f(x_1,x_2,\dots,x_{i-1},a,x_{i+1},\dots, x_n). In this post, the cosets
H_{i,a,n}=\{x=(x_1,x_2,\dots,x_n) \in GF(2)^n\ |\ x_i=a\}
will be called coordinate hyperplanes (a \in GF(2), 1\leq i\leq n). A function in B(n) which is constant along some coordinate hyperplane is called canalyzing. An NCF function is a function f\in B(n) which (a) is constant along some coordinate hyperplane H_{i_1,a_1,n}, (b) whose restriction f_1 = Res_{x_{i_1}=a_1}(f)\in B(n-1) is constant along some coordinate hyperplane H_{i_2,a_2,n-1}\subset GF(2)^{n-1}, (c) whose restriction f_2 = Res_{x_{i_2}=a_2}(f_1)\in B(n-2) is constant along some coordinate hyperplane H_{i_2,a_2,n-2}\subset GF(2)^{n-2}, (d) and so on. This “nested” inductive definition might seem complicated, but to a computer it’s pretty simple and, to boot, it requires little memory to store.

If 1\leq i\leq n and x=(x_1,x_2,\dots,x_n) \in GF(2)^n then let x^i\in GF(2)^n denote the vector whose i-th coordinate is flipped (bitwise). The sensitivity of f\in B(n) at x is
s(f,x) = |\{i\ |\ 1\leq i\leq n, f(x)\not= f(x^i)\}|. Roughly speaking, it’s the number of single-bit changes in x that change the value of f(x). The (maximum) sensitivity is the quantity
s(f)=max_x s(f,x). The block sensitivity is defined similarly, but you allow blocks of indices of coordinates to by flipped bitwise, as opposed to only one. It’s possible to

  • compute the sensitivity of any NCF function,
  • show the block sensitivity is equal to the sensitivity,
  • compute the cardinality of the set of all monotone NCF functions.

For details, see for example Li and Adeyeye [LA2012].

REFERENCES
[JRL2007] A.S. Jarrah, B. Raposa, R. Laubenbachera, “Nested Canalyzing, Unate Cascade, and Polynomial Functions,” Physica D. 2007 Sep 15; 233(2): 167–174.

[LA2012] Y. Li, J.O. Adeyeye, “Sensitivity and block sensitivity of nested canalyzing function,” ArXiV 2012 preprint. (A version of this paper was published later in Theoretical Comp. Sci.)

[LAMAL2013] Y. Li, J.O. Adeyeye, D. Murrugarra, B. Aguilar, R. Laubenbacher, “Boolean nested canalizing functions: a comprehensive analysis,” ArXiV, 2013 preprint.

Harmonic morphisms to P_4 – examples

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph \Gamma_2=P_4.
path4-0123

First, a simple remark about harmonic morphisms in general: roughly speaking, they preserve adjacency. Suppose \phi:\Gamma_1\to \Gamma_2 is a harmonic morphism. Let v,w\in V_1 be adjacent vertices of \Gamma_1. Then either (a) \phi(v)=\phi(w) and \phi “collapses” the edge (vertical) (v,w) or (b) \phi(v)\not= \phi(w) and the vertices \phi(v) and \phi(w) are adjacent in \Gamma_2. In the particular case of this post (ie, the case of \Gamma_2=P_4), this remark has the following consequence: since in P_4 the white vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a white vertex adjacent to a blue or red vertex.

We first consider the cyclic graph on k vertices, C_k as the domain in this post. However, before we get to examples (obtained by using SageMath), I’d like to state a (probably naive) conjecture.

Let \phi:\Gamma_1 \to \Gamma_2=P_k be a harmonic morphism from a graph \Gamma_1 with n=|V_1| vertices to the path graph having k>2 vertices. Let f:V_2 \to V_1 be the coloring map (identified with an n-tuple whose coordinates are in \{0,1,\dots ,k-1\}). Associated to f is a partition \Pi_f=[n_0,\dots,n_{k-1}] of n (here [...] is a multi-set, so repetition is allowed but the ordering is unimportant): n=n_0+n_1+...+n_{k-1}, where n_j is the number of times j occurs in f. We call this the partition invariant of the harmonic morphism.

Definition: For any two harmonic morphisms \phi:\Gamma_1 \to P_k, \phi:\Gamma'_1 \to P_k, with associated
colorings f, f' whose corresponding partitions agree, \Pi_f=\Pi_{f'} then we say f' and f are partition equivalent.

What can be said about partition equivalent harmonic morphisms? Caroline Melles has given examples where partition equivalent harmonic morphisms are not induced from an automorphism.

Now onto the \Gamma_1 \to P_4 examples!

There are no non-trivial harmonic morphisms C_5 \to P_4, so we start with C_6. We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: \phi:\Gamma_1\to \Gamma_2=P_4 sends the red vertices in \Gamma_1 to the red vertex of \Gamma_2=P_4 (we let 3 be the numerical notation for the color red), the blue vertices in \Gamma_1 to the blue vertex of \Gamma_2=P_4 (we let 2 be the numerical notation for the color blue), the green vertices in \Gamma_1 to the green vertex of \Gamma_2=P_4 (we let 1 be the numerical notation for the color green), and the white vertices in \Gamma_1 to the white vertex of \Gamma_2=P_4 (we let 0 be the numerical notation for the color white).

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms C_6 \to P_4, plus that induced by f = (1, 2, 3, 2, 1, 0) and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of P_4 induced by the transposition (0,3)(1,2) (so total = 10).cyclic6-123210

Example 2: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0) and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (2, 1, 0, 1, 2, 3, 3) and all 7 of its cyclic permutations (total = 7+11 = 18).
cyclic7-1232100
cyclic7-1233210

Example 3: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0) and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0) and all of its cyclic permutations (12+8=20). In addition, there is f = (1, 2, 3, 3, 2, 1, 0, 0) and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of (1, 2, 3, 3, 2, 1, 0, 0) is closed under the transposition (0,3)(1,2) (total = 28).
cyclic8-12321000
cyclic8-12333210
cyclic8-12332100

Example 4: There are only the 4 trivial harmonic morphisms, plus f = (1, 2, 3, 2, 1, 0, 0, 0, 0) and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 2, 1, 0, 0, 0) and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 2, 1, 0, 0) and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of P_4 induced by the transposition (0,3)(1,2), so one also has f = (1, 2, 3, 3, 3, 3, 2, 1, 0) and all 9 of its cyclic permutations (total = 9+31 = 40). cyclic9-123210000cyclic9-123321000cyclic9-123332100cyclic9-123333210

Next we consider some cubic graphs.

Example 5: There are 5 cubic graphs on 8 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. There are no non-trivial harmonic morphisms from any one of these 5 graphs to P_4.

Example 6: There are 19 cubic graphs on 10 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. The only one of these 19 cubic graphs \Gamma_1 having a harmonic morphism \phi:\Gamma_1\to P_4 is the graph whose SageMath command is graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). It has diameter 3, girth 4, and automorphism group of order 48 generated by (4,6), (2,8)(3,7), (1,9), (0,2)(3,5), (0,3)(1,4)(2,5)(6,9)(7,8). There are eight non-trivial harmonic morphisms \phi:\Gamma_1\to P_4. They are depicted as follows:
3regular10nn-P4-1112322210
3regular10nn-P4-1112223210
3regular10nn-P4-1012322211
3regular10nn-P4-1012223211
3regular10nn-P4-2321110122
3regular10nn-P4-2321011122
3regular10nn-P4-2221110123
3regular10nn-P4-2221011123
Note that the last four are obtained from the first 4 by applying the permutation (0,3)(1,2) to the colors (where 0 is white, etc, as above).

We move to cubic graphs on 12 vertices. There are quite a few of them – according to the House of Graphs page on connected cubic graphs, there are 109 of them (if I counted correctly).

Example 7: The cubic graphs on 12 vertices are listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is no harmonic morphism \Gamma_1\to P_4 then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.

  1. \Gamma_1=(V_1,E_1), where E_1=\{ (0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0,1), (0,2), (0,11), (1,2), (1,6),(2,3), (3,4), (3,5), (4,5), (4,6), (5,6), (7,8), (7,9), (7,11), (8,9),(8,10), (9,10), (10,11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  2. \Gamma_1=(V_1,E_1), where E_1=\{ (0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  3. \Gamma_1=(V_1,E_1), where E_1=\{(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)\}.
    SageMath command:
    V1 = [0,1,2,3,4,5,6,7,8,9,10,11]
    E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)]
    Gamma1 = Graph([V1,E1])

    (Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
  4. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)
  5. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 7), (5, 6), (5, 8), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
  6. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 4), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 11), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)
  7. \Gamma_1=(V_1,E_1), where E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 9), (7, 8), (7, 10), (8, 9), (8, 11), (9, 10), (10, 11)\}.
    SageMath command:
    Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)
  8. (list under construction)

Dodecahedral Faces of M12

 

Dodecahedral Faces of M12

 

by Ann Luers Casey

 

This post constitutes part of the math honors thesis written in spring 1997 at the USNA, advised by David Joyner. It is in the public domain.

Groups are objects in mathematics that measure symmetry in nature. A group is a set with a binary operation that has an inverse, an identity and is associative. For example, a clock has 12-fold symmetry. A more unusual group is a sporadic, non-abelian simple group. It can be very interesting to look more closely at such a group that arises naturally. One such group is M12. This post explores two different ways of creating M12 and then looks at twelve different ways M12 appears in mathematics, hence the pun the “dodecahedral faces” in the title. Specifically, this post relates M12 to the Mongean shuffle, hexads of a Steiner system, Golay codes, the Hadamard matrix of order 12, 5-transitivity, presentations, crossing the Rubicon, the minimog, the kitten, mathematical blackjack, sporadic groups, and the stabilizer in M24 of a dodecad.

Definitions:

Homomorphism: Let G1, G2 be groups with *1 denoting the group operation for G1 and *2 the group operation for G2. A function f : G1–>G2 is a homomorphism if and only if for all a,b, in Gwe have

f(a *1 b) = f(a) *2 f(b).

Isomorphism: If a homomorphism is bijective, then it is called an
isomorphism.

Automorphism: An isomorphism from a group G to itself is an automorphism.

Notation:

  • Let Fq denote the finite field with q elements, q is a power of a prime.
  • Z = the invertible scalar 2×2 matrices with entries in Fqx.
  • Let PGL2(Fq) = GL2(Fq)/Z = {A*Z | A is in GL2(Fq)}, with multiplication given by
    (A*Z)(B*Z) = (A*B)Z. This is the projective linear group over Fq.
  • LF(Fq) is the group of linear fractional transformations x–>(ax+b)/(cx+d).

Claim: There is a group theoretic isomorphism between PGL2(Fq) and LF(Fq). (See [11], Theorem 9.47 for a proof.)

Claim: LF(Fq) acts 3-transitively on the set P1(Fq) (q>3). I.e., one can send any triple to any other triple in P1(Fq) by using a suitable linear fractional transformation. (See [11], Theorem 9.48 for a proof.)

Theorem

PSL2(Fq) = < x–>x+1, x–>kx, x–>-1/x>, where k is any element in Fqthat generates the multiplicative group of squares.

For a proof, see [12], ch 10, section 1.

One way to construct the Mathieu group M12 is the following, accredited to Conway.

M12 = < PSL2(F11), (2 10)(3 4)(5 9)(6 7) >.More explicitly, let

  • f1 be a cyclic permutation = x–> x+1 = (0,1,2,…,10)(inf).
  • f2 = x–>kx = (0)(1 3 9 5 4)(2 6 7 10 8)(inf) when k=3.
  • f3 = x–>-1/x = (0 inf)(1 10)(2 5)(3 7)(4 8)(6 9).
  • f4 = (2 10)(3 4)(5 9)(6 7).

Then M12 = < f1, f2, f3, f4 >. Therefore, M12 is a subgroup of the symmetric group on 12
symbols, namely inf, 0, 1, …, 10.

Another way to construct M12 is given later under 5-transitivity.

There are many occurrences of M12 in mathematics, but here I will list and explain twelve of them:

  1. Mongean Shuffle
  2. Steiner Hexad
  3. Golay Code
  4. Hadamard Matrices
  5. 5- Transitivity
  6. Presentations
  7. Crossing the Rubicon
  8. M12 and the Minimog
  9. Kitten
  10. Mathematical Blackjack or Mathieu’s 21
  11. Sporadic Groups
  12. Stabilizer in M24 of a dodecad

    1. Mongean Shuffle

     

    The Mongean shuffle concerns a deck of twelve cards, labeled 0 through 11. The permutation

    r(t) = 11-t

    reverses the cards around. The permutation

    s(t) = min(2t,23-2t)

    is called the Mongean Shuffle. The permutation group M12 is generated by r and s: M12 = < r,s >, as a subgroup of S12. (See [12], Chap. 11, Sec. 17 or [18])

    2. Steiner Hexad

     

    Jacob Steiner (1796-1863) was a Swiss mathematician specializing in projective goemetry. (It is said that he did not learn to read or write until the age of 14 and only started attending school at the age of 18.) The origins of “Steiner systems” are rooted in problems of plane geometry.

    Let T be a given set with n elements. Then the Steiner system S(k,m,n) is a collection S = {S1, … ,Sr} of subsets of T such that

    • |Si| = m,
    • For any subset R in T with |R| = k there is a unique i, 1<=i<=n such that R is contained in Si. |S(k,m,n)| = (n choose k)/(m choose k).

    If any set H has cardinality 6 (respectively 8, 12) then H is called a hexad, (respectively octad, dodecad.)

    Let’s look at the Steiner System S(5,6,12) and M12. We want to construct the Steiner system S(5,6,12) using the projective line P1(F11). To define the hexads in the Steiner system, denote

    • the projective line over F11 by P1(F11)={inf,0,1,…,10}.
    • Q = {0,1,3,4,5,9}=the quadratic residues union 0
    • G = PSL2(F11)
    • S = set of all images of Q under G. (Each element g in G will send Q to a subset of P1(F11). )

    There are always six elements in such a hexad. There are 132 such hexads. If I know five of the elements in a hexad of S, then the sixth element is uniquely determined. Therefore S is a Steiner system of type (5,6,12).

    Theorem:
    M12 sends a hexad in a Steiner system to another hexad in a Steiner system. In fact, the automorphism group of a Steiner system of type (5,6,12) is isomorphic to M12.

    (For a proof, see [11], Theorem 9.78.)

    The hexads of S form a Steiner system of type (5,6,12), so

    M12 = < g in S12 | g(s) belongs to S, for all s in S > .

    In other words, M12 is the subgroup stabilizing S. The hexads support the weight six words of the Golay code, defined next. (For a proof, see  [6].)

    3. Golay Code

     

    ” The Golay code is probably the most important of all codes for both practical and theoretical reasons.” ([17], pg. 64)

    M. J. E. Golay (1902-1989) was a Swiss physicist known for his work in infrared spectroscopy among other things. He was one of the founding fathers of coding theory, discovering GC24 in 1949 and GC12 in 1954.

    A code C is a vector subspace of (Fq)for some n >=1 and some prime power q =pk.
    An automorphism of C is a vector space isomorphism, f:C–>C.

    If w is a code word in Fqn, n>1, then the number of non-zero coordinates of w is called the weight w, denoted by wt(w). A cyclic code is a code which has the property that whenever (c0,c1,…,cn-1) is a code word then so is (cn-1,c0,…,cn-2).
    If c=(c0,c1,…,cn-1) is a code word in a cyclic code C then we can associate to it a polynomial g_c(x)=c0 + c1x + … + cn-1xn-1. It turns out that there is a unique monic polynomial with coefficients in Fq

    of degree >1 which divides all such polynomials g_c(x). This polynomial is called
    a generator polynomial for C, denoted g(x).

    Let n be a positive integer relatively prime to q and let alpha be a primitive n-th root of unity. Each generator g of a cyclic code C of length n has a factorization of the form g(x) = (x-alphak1)… (x-alphakr), where {k1,…,kr} are in {0,…,n-1} [17]. The numbers alphaki, 1≤ i≤ r, are called the zeros of the code C.

    If p and n are distinct primes and p is a square mod n, then the quadratic residue code of length n over Fp is the cyclic code whose generator polynomial has zeros
    {alphak | k is a square mod n} [17]. The ternary Golary code GC11 is the quadratic
    residue code of length 11 over F3.

    The ternary Golay code GC12 is the quadratic residue code of length 12 over F3 obtained by appending onto GC11 a zero-sum check digit [12].

    Theorem:
    There is a normal subgroup N of Aut(GC12) of order 2 such that Aut(GC12)/N is isomorphic to M12. M12 is a quotient of Aut(GC12) by a subgroup or order 2. In other words, M12 fits into the following short exact sequence:

    1–>N–>Aut(GC12)–>M12–>1

    Where i is the embedding and N in Aut(GC12) is a subgroup of order 2. See [6].

    4. Hadamard Matrices

     

    Jacques Hadamard (1865-1963) was a French mathematician who did important work in analytic number theory. He also wrote a popular book “The psychology in invention in the mathematical field” (1945).

    A Hadamard matrix is any n x n matrix with a +1 or -1 in every entry such that the absolute value of the determinant is equal to nn/2.

    An example of a Hadamard matrix is the Paley-Hadamard matrix. Let p be a prime of the form 4N-1, p > 3. A Paley-Hadamard matrix has order p+1 and has only +1’s and -1’s as entries. The columns and rows are indexed as (inf,0,1,2,…,p-1). The infinity row and the infinity column are all +1’s. The zero row is -1 at the 0th column and at the columns that are quadratic non-residues mod p; the zero row is +1 elsewhere. The remaining p-1 rows are cyclic shifts of the finite part of the second row. For further details, see for example [14].

    When p = 11 this construction yields a 12×12 Hadamard matrix.

    Given two Hadamard Matrices A, B we call them left-equivalent if there is an nxn signed permutation matrix P such that PA = B.

    The set {P nxn signed permutation matrix| AP is left equivalent to A} is called the automorphism group of A. In other words, a matrix is an automorphism of the Hadamard matrix, if it is a nxn monomial matrix with entries in {0,+1,-1} and when it is multiplies the Hadamard matrix on the right, only the rows may be permuted, with a sign change in some rows allowed.

    Two nxn Hadamard matrices A, B are called equivalent if there are nxn signed permutation matrices P1, P2 such that A = P1 *B *P2.

    All 12×12 Hadamard matrices are equivalent ([13][16] pg. 24). The group of automorphisms of any 12×12 Hadamard matrix is isomorphic to the Mathieu group M12 ([14] pg 99).

     

    5. 5-Transitivity

     

    Emile Mathieu (1835-1890) was a mathematical physicist known for his solution to the vibrations of an elliptical membrane.

    The fact that M12 acts 5-transitively on a set with 12 elements is due to E. Mathieu who proved the result in 1861. (Some history may be found in [15].)

    There are only a finite number of types of 5-transitive groups, namely Sn (n>=5), An (n>=7), M12 and M24. (For a proof, see [11])

    Let G act on a set X via phi : G–>SX. G is k-transitive if for each pair of ordered k-tuples (x1, x2,…,xk), (y1,y2,…,yk), all xi and yi elements belonging to X, there exists a g in G such that yi = phi(g)(xi) for each i in {1,2,…,k}.

    M12 can also be constructed as in Rotman [11], using transitive extensions, as follows (this construction appears to be due originally to Witt). Let fa,b,c,d(x)=(ax+b)/(cx+d), let

    M10 = < fa,b,c,d, fa’,b’,c’,d’ |ad-bc is in Fqx, a’d’-b’c’ is not in Fqx >,

    q = 9.

    pi = generator of F9x, so that F9x = < pi> = C8.

    Using Thm. 9.51 from Rotman, we can create a transitive extension of M10. Let omega be a new symbol and define

    M11 = < M10, h| h = (inf, omega)(pi, pi2)(pi3,pi7) (pi5,pi6)>.

    Let P1(F9) = {inf, 0, 1, pi, pi2, … , pi7}. Then M11 is four transitive on Y0 = P1(F9) union {omega}, by Thm 9.51.

    Again using Thm. 9.51, we can create a transitive extension of M11. Let sigma be a new symbol and define

    M12 = < M11, k>, where k = (omega, sig)(pi,pi3) (pi2,pi6)(pi5,pi7). M12 is 5-transitive on Y1 = Y0 union {sig}, by Th. 9.51.

    Now that we constructed a particular group that is 5-transitive on a particular set with 12 elements, what happens if we have a group that is isomorphic to that group? Is this new group also 5-transitive?

    Let G be a subgroup of S12 isomorphic to the Mathieu group M12. Such a group was constructed in Section 1.

    Lemma: There is an action of G on the set {1,2,…,12} which is 5-transitive.

    proof: Let Sig : G –> M12 be an isomorphism. Define g(i) = Sig(g)(i), where i = {1,2,…,12}, g is in G. This is an action since Sig is an isomorphism. Sig-1(h)(i) = h(i) for all g in M12, i in Y1. Using some h in M12, any i1,…,i5

    in Y1 can be sent to any j1,…,j5 in Y1. That is, there exists an h in M12 such that h(ik) = jk, k= 1,…,5 since M12 is 5-transitive. Therefore, Sig-1(h)(ik) = jk = g(ik). This action is 5-transitive. QED

    In fact, the following uniqueness result holds.

    Theorem: If G and G’ are subgroups of S12 isomorphic to M12 then they are conjugate in S12.

    (This may be found in [7], pg 211.)

    6. Presentations

     

    The presentation of M12 will be shown later, but first I will define a presentation.

    Let G = < x1,…,xn | R1(x1,…xn) = 1, …, Rm(x1,…,xn) = 1> be the smallest group generated by x1,…,xn satisfying the relations R1,…Rm. Then we say G has presentation with generators x1,…,xn and relations R1(x1,…xn) = 1, …, Rm(x1,…,xn) = 1.

    Example: Let a = (1,2,…,n), so a is an n-cycle. Let Cn be the cyclic group, Cn = < a > =
    {1,a,…,an-1}. Then Cn has presentation < x | xn=1 > = all words in x, where x satisfies xn.=1 In fact, < x | xn = 1 > is isomorphic to < a >. Indeed, the isomorphism
    < x | xn = 1 > –> < a > is denoted by xk –> ak, 0 <= k <= n-1. Two things are needed for a presentation:

    • generators, in this case x, and
    • relations, in this case xn = 1.

    Example: Let G be a group generated by a,b with the following relations; a2 = 1, b2 = 1, (ab)2 = 1:

    G = < a,b | a2 = 1, b2 = 1, (ab)2 = 1 > = {1,a,b,ab}.

    This is a non-cyclic group of order 4.

    Two presentations of M12 are as follows:

    M12 = < A,B,C,D | A11 = B5 = C2 = D2 = (BC)2 = (BD)2 = (AC)= (AD)3 = (DCB)2 = 1, AB =A3 >

    = < A,C,D | A11 = C2 = D2 = (AC)3 = (AD)3 = (CD)10 = 1, A2(CD)2A = (CD)2 >.

    In the first presentation above, AB = B-1AB. These are found in [6] and Chap. 10 Sec. 1.6 [12].

    7. Crossing the Rubicon

     

    The Rubicon is the nick-name for the Rubik icosahedron, made by slicing the icosahedron in half for each pair of antipodal vertices. Each vertex can be rotated by 2*pi/5 radians, affecting the vertices in that half of the Rubicon, creating a shape with 12 vertices, and six slices. The Rubicon and M12 are closely related by specific moves on the Rubicon.

    Let f1, f2, …,f12 denote the basic moves of the Rubicon, or a 2*pi/5 radians turn of the sub-pentagon about each vertex. Then according to Conway,

    M12 = < x*y-1 | x,y are elements of {f1, f2, …,f12 } >.

    Actually, if a twist-untwist move, x*y-1, as above, is called a cross of the Rubicon, then M12 is generated by the crosses of the Rubicon! ([1], Chap. 11 Sec. 19 of [12])

    8. M12 and the Minimog

     

    Using the Minimog and C4 (defined below), I want to construct the Golay code GC12.

    The tetracode C4 consists of 9 words over F3:

      0 000,     0 +++,    0 ---,         where 0=0, +=1, and -=2 all mod 3.
      + 0+-,     + +-0,    + -0+,
      - 0-+,     - +0-,    - -+0.
    

    Each (a,b,c,d) in C4 defines a linear function f : F3 –> F3, where f(x) = ax+b, f(0) = b, f(1) = f(+) = c, f(2) = f(-) = d, and a is the “slope” of f. This implies a + b = c (mod 3), b – a = d (mod 3).

    Minimog: A 4×3 array whose rows are labeled 0,+,-, that construct the Golay code in such a way that both signed and unsigned hexads are easily recognized.

    A col is a word of length 12, weight 3 with a “+” in all entries of any one column and a “0” everywhere else. A tet is a word of length 12, weight 4 who has “+” entries in a pattern such that the row names form a tetracode word, and “0” entires elsewhere. For example,

     
                 _________          _________
                 | |+    |          | |+    |
                 | |+    |          |+|  +  |
                 | |+    |          | |    +| 
                 ---------          ---------               
                 "col"              "tet"
    

    The above “col” has “+” entries in all entries of column 2, and “0” entries elsewhere.
    The above “tet” has a “+” entry in each column. The row names of each “+” entry are +, 1, +, – respectively. When put together, + 0+- is one of the nine tetracode words.

    Lemma: Each word belongs to the ternary Golay Code GC12 if and only if

    • sum of each column = -(sum row0)
    • row+ – row is one of the tetracode words.

    This may be found in [4].

    Example:

    |+|+ + +|      col sums: ----      row+ - row-: --+0
    |0|0 + -|      row0 sum: + = -(sum of each col)
    |+|+ 0 -|
    
    

    How do I construct a Golay code word using cols and tets? By the Lemma above, there are four such combinations of cols and tets that are Golay code words. These are: col – col, col + tet, tet – tet, col + col – tet.

    Example:

      col-col         col+tet      tet-tet       col+col-tet
    
     | |+   -|       | |+ +  |    |+|0 + +|      | |- + +|
     | |+   -|       |+|  -  |    |-|  -  |      |-|  0 +|
     | |+   -|       | |  + +|    | |    -|      | |  + 0| 
      ? ? ? ?         + 0 ? -      - ? - +        + 0 + -
    

    “Odd-Man-Out”: The rows are labeled 0,+,-, resp.. If there is only one entry in a column then the label of the corresponding row is the Odd Man Out. (The name of the odd man out is that of the corresponding row.) If there is no entry or more than one entry in the column then the odd man out is denoted by “?”.

    For example, in the arrays above, the Odd-Men-Out are written below the individual arrays.

    For the Steiner system S(5,6,12), the minimog is labeled as such:

                                  ______________
                                  |0  3 inf  2 |
                                  |5  9  8  10 |
                                  |4  1  6  7  |
                                  --------------
    

    The four combinations of cols and tets above that construct a Golay code word yield all signed hexads. From these signed hexads, if you ignore the sign, there are 132 hexads of the Steiner system S(5,6,12) using the (o, inf, 1) labeling discussed in Section 9 below. There are a total of 265 words of this form, but there are 729 Golay code words total. So, although the above combinations yield all signed hexads, they do not yield all hexads of the Golay code ([12] pg. 321).

    The hexad for the tet-tet according to the S(5,6,12) Minimog above would be (0, inf, 2, 5, 8, 7).

    The rules to obtain each hexad in this Steiner system is discussed in Section 9 below.

    A Steiner system of type (5,6,12) and the Conway-Curtis notation can be obtained from the Minimog. S12 sends the 3×4 minimog array to another 3×4 array. The group M12 is a subgroup of S12 which sends the Minimog array to another array also yielding S(5,6,12) in Conway-Curtis notation.

    9. Kitten

     

    The kitten is also an interesting facet of the Minimog. Created by R.T. Curtis,
    kittens come from the construction of the Miracle Octal Generator, or MOG, also created by R.T. Curtis. (A description of the MOG would be too far afield for this post, but further information on the MOG can be gotten from [3] or [6].)

    Suppose we want to construct a Steiner system from the set T = {0, 1, …, 10, inf}.
    The kitten places 0, 1, and inf at the corners of a triangle, and then creates a rotational symmetry of triples inside the triangle according to R(y) = 1/(1-y) (as in [2], section 3.1). A kitten looks like:

                                    infinity
    
                                       6
    
                                    2     10
    
                                 5     7      3
    
                              6     9      4     6
    
                           2    10     8      2     10
    
                     0                                    1
    
                                Curtis' kitten               
    

    where 0, 1, inf are the points at infinity.

    Another kitten, used to construct a Steiner system from the set T = {0, 1, …, 10, 11} is

                                       6
    
                                       9
    
                                    10     8
    
                                 7     2      5
    
                              9     4     11     9
    
                          10     8     3      10     8
    
                     1                                    0
    
                             Conway-Curtis' kitten
    

    The corresponding minimog is

                      _________________________
                      |  6  |  3  |  0  |  9  |
                      |-----|-----|-----|-----|
                      |  5  |  2  |  7  | 10  |
                      |-----|-----|-----|-----|
                      |  4  |  1  |  8  | 11  |
                      |_____|_____|_____|_____|
    

    (see Conway [3]).

    The first kitten shown consists of the three points at 0, inf, 1 with an arrangement of points of the plane corresponding to each of them. This correspondence is:

             6 |10 | 3              5 | 7 |3               5 | 7 | 3 
             2 | 7 | 4              6 | 9 |4               9 | 4 | 6 
             5 | 9 | 8              2 |10 |8               8 | 2 |10
     
            inf-picture             0-picture              1-picture
    

    A union of two perpendicular lines is called a cross. There are 18 crosses of the kitten:

                    ___________________________________________
                    |* * * |* * * |* * * |*     |  *   |    * |
                    |*     |  *   |    * |* * * |* * * |* * * |
                    |*     |  *   |    * |*     |  *   |    * |
                     -----------------------------------------
                     _________________________________________
                    |*     |  *   |* *   |*     |*   * |    * |
                    |*     |  *   |* *   |  * * |  *   |    * |
                    |* * * |* * * |    * |  * * |*   * |* * * |
                     -----------------------------------------
                     _________________________________________
                    |*   * |    * |  * * |  *   |  * * |* *   |
                    |*   * |* *   |*     |*   * |  * * |    * |
                    |  *   |* *   |  * * |*   * |*     |* *   |
                    ------------------------------------------
    
    

    A square is a complement of a cross. The 18 squares of a kitten are:

                    ___________________________________________
                    |      |      |      |  * * |*   * |* *  |
                    |  * * |*   * |* *   |      |      |     |
                    |  * * |*   * |* *   |* *   |*   * |* *  |
                     -----------------------------------------
                     _________________________________________
                    |  * * |*   * |    * |  * * |  *   |* *   |
                    |  * * |*   * |    * |*     | *  * |* *   |
                    |      |      |* *   |*     |  *   |      |
                     -----------------------------------------
                     _________________________________________
                    |  *   |* *   |*     |*   * |*     |    * |
                    |  *   |    * |  * * |  *   |*     |* *   |
                    |*   * |    * |*     |  *   |  * * |    * |
                     -----------------------------------------
    

    The rules to obtain a hexad in the {0,1,inf} notation are the following:

    • A union of parallel lines in any picture,
    • {0, 1, inf} union any line,
    • {Two points at infinity} union {square in a picture corresponding to omitted point at infinity},
    • {One point at infinity} union {cross in the corresponding picture at infinity}.

    (See [2])

    M12 is isomorphic to the group of automorphisms of the Steiner system S(5,6,12) in the Conway-Curtis notation.

    10. Mathematical Blackjack or Mathieu’s 21

    Mathematical Blackjack is a card game where six cards from the group {0,1,…,11} are laid out face up on a table. The rules are:

    • each player must swap a card with a card from the remaining six, that is lower than the card on the table;
    • the first player to make the sum of all six cards less than 21 loses.

    According to Conway and Ryba [8, section V, part (d)], the winning strategy of this game is to choose a move which leaves a Steiner hexad from S(5,6,12) in the shuffle
    notation, whose sum is greater than or equal to 21, on the table.

    The shuffle notation for the hexad, used in the Mathematical Blackjack game, is shown below (see also the description in the hexad/blackjack page):

                  8 |10 |3            5 |11 |3            5 |11 |3
                  9 |11 |4            2 | 4 |8            8 | 2 |4 
                  5 | 2 |7            7 | 9 |10           9 |10 |7 
             
                 0-picture          1-picture          6-picture
    

    Riddle: Assuming the strategy, player A just made a winning hexad move that will force player B to make the sum under 21 on his next turn. Joe Smith walks up to player B and offers to shuffle all 12 cards while player A isn’t looking, for a fee. Player B grabs at his chance thinking that a random shuffle will let him back in the game. How is it that player B still loses?

    Joe is actually working for Player A. Joe does not shuffle the cards randomly, but instead uses the M12 group generated by r, s (see section 1) to shuffle the cards. Since the M12 group preserves hexads, player A still has a winning game. (He and Joe split the money.)

    11. Sporadic Groups

     

    A simple group is a group with no normal subgroups except itself and {1}. Most simple groups are from a family such as PSL2(Fp), p>3 or An, n >= 5. However there exist some simple groups outside of such well known families. These are called sporadic simple groups. M12 is a sporadic simple group of order 95,040. The only smaller sporadic group is M11 of order 7,920. (See [10] pg. 211)

    12. Stabilizer in M24 of a dodecad.

     

    M24 is a sporadic simple group of order 244,823,040 containing M12 as a subgroup. The Steiner system S(5,8,24) is a collection of 8 element subsets, called octads, from a 24 element set X, with the property that any five elements in X determine a unique octad in the system. There are (24 choose 5)/(8 choose 5) = 759 of these octads. M24 is the subgroup of SX which sends the set of octads to itself. Two octads, O1, O2, intersect in a subset of X of order 0,2,4,6 or 8 [14]. If |O1 intersect O2| = 2 then O1 + O2 is order 12. Such a subset of X is called a dodecad. M12 is isomorphic to

    {g in M24 | g(O1 + O2) = (O1 + O2)} = the stablizer of the dodecad O1 + O2.
    (See [6] for details)

    Much more information can be received from the references below or from the hexad/blackjack page.

    References

     

    1. W. D. Joyner, Mathematics of the Rubik’s Cube (USNA Course notes), 1997.
    2. R. T. Curtis, “The Steiner System S(5,6,12), the Mathieu Group M12 and the ‘Kitten’ ,” Computational Group Theory, Academic Press, London, 1984.
    3. J. H. Conway, “hexacode and Tetracode- MOG and MINIMOG,” Computational Group Theory (ed. Atkinson), Academic Press, London, 1984.
    4. Vera Pless, “Decoding the Golay Code,” Transactions of Information Theory, IEEE, 1986, (pgs 561-567).
    5. R. T. Curtis, “A new Combinatorial approach to M24“, Mathematical Proceeding of the Cambridge Philosophical Society, Vol. 79, 1974.
    6. J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, “M12,”,
      Atlas of Finite Groups, Clarendon Press, Oxford, 1985.
    7. Robinson, A Course in the Theory of Groups, Springer, 1996.
    8. J. H. Conway, N. Sloane, “Lexicographic Codes: Error-Correcting Codes
      from Game Theory,” Transactions on Information Theory, IEEE, 1986.
    9. A .Adler, “The modular Curve X(11) and the Mathieu group M11“,
      Proc. London Math Society 74(1997)1-28.
      See also the paper X(11) and M11.
    10. T. Thompson, From Error-Correcting Codes Through Sphere
      Packings to Simple Groups
      , The Mathematical Association of
      America, 1983.
    11. Rotman, J, Introduction to the Theory of Groups, 4th ed.
      Springer-Verlag, 1995.
    12. J. Conway, N. Sloane, Sphere Packings, Lattices, and Groups,
      Springer-Verlag, 3rd ed., 1999.
    13. B. Kostant, “The Graph of the truncated icosahedron and the
      last letter of Galois.” Notices of the A.M.S. 42(1995)959-
      968.
    14. E. Assmus, “On the Automorphism Groups of Paley-Hadamard
      Matrices.” Combinatorial Mathematics and its Applications.
      University of North Carolina Press, 1969, (pgs 98-103).
    15. P. Greenberg, Mathieu Groups, Courant Institute of Math and
      Science, New York University, 1973.
    16. P. Cameron, J. Van Lint, Designs, Graphs, Codes, and Their
      Links
      , London Mathematical Society, Cambridge University
      Press, 1991.
    17. F. MacWilliams, N. Sloane, The Theory of Error Correcting
      Codes
      , North Holland Publishing Company, 1978.
    18. R. Graham, P. Diaconis, W. Kantor, “The Mathematics of
      Perfect Shuffles”, Advanced Applied Math, Vol. 4, 1985, (pgs
      175-196).

    Typed into html by wdj, 4-18-97.
    Corrections 4-27-2001.
    Last updated 2018-06-10.

     

Ring theory, via coding theory and cryptography

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

Calculus on graphs

In these notes, I tried to cover enough material to get a feeling for “calculus on graphs”, with applications to sports rankings and the Friendship Theorem. Here’s a list of the topics.

1 . Introduction
2. Examples
3. Basic definitions
3.1 Diameter, radius, and all that
3.2 Treks, trails, paths
3.3 Maps between graphs
3.4 Colorings
3.5 Transitivity
4. Adjacency matrix
4.1 Definition
4.2 Basic results
4.3 The spectrum
4.4 Application to the Friendship Theorem
4.5 Eigenvector centrality and the Keener ranking
4.6 Strongly regular graphs
4.7  Orientation on a graph
5. Incidence matrix
5.1 The unsigned incidence matrix
5.2 The oriented case
5.3 Cycle space and cut space
6. Laplacian matrix
6.1 The Laplacian spectrum
7  Hodge decomposition for graphs
7.1 Abstract simplicial complexes
7.2 The Bjorner complex and the Riemann hypothesis
7.3 Homology groups
8. Comparison graphs
8.1 Comparison matrices
8.2 HodgeRank
8.3 HodgeRank example

Gray codes

This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in GF(2)^n = \{0,1\}^n such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

  • solving puzzles such as the Tower of Hanoi and the Brain [G],
  • analog-digital-converters (goniometers) [S],
  • Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
  • capanology (the study of bell-ringing) [W],
  • continuous space-filling curves [Gi],
  • classification of Venn diagrams [R],
  • design of communication codes,
  • and more (see Wikipedia).

brain-puzzle

The Brain puzzle

Here's a SageMath/Python function for computing Gray codes.
def graycode(length,modulus):
    """
    Returns the n-tuple reverse Gray code mod m.


    EXAMPLES:
        sage: graycode(2,4)
        
        [[0, 0],
         [1, 0],
         [2, 0],
         [3, 0],
         [3, 1],
         [2, 1],
         [1, 1],
         [0, 1],
         [0, 2],
         [1, 2],
         [2, 2],
         [3, 2],
         [3, 3],
         [2, 3],
         [1, 3],
         [0, 3]]

    """
    n,m = length,modulus
    F = range(m)
    if n == 1:
        return [[i] for i in F]
    L = graycode(n-1, m)
    M = []
    for j in F:
        M = M+[ll+[j] for ll in L]
    k = len(M)
    Mr = [0]*m
    for i in range(m-1):
        i1 = i*int(k/m)
        i2 = (i+1)*int(k/m)
        Mr[i] = M[i1:i2]
    Mr[m-1] = M[(m-1)*int(k/m):]
    for i in range(m):
        if is_odd(i):
            Mr[i].reverse()
    M0 = []
    for i in range(m):
        M0 = M0+Mr[i]
    return M0


REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[S] Web page of T. Sillke

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

Sports ranking methods, 3

This is the third of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the random walker ranking.

We follow the presentation in the paper by Govan and Meyer (Ranking National Football League teams using Google’s PageRank). The table of “score differentials” based on the table in a previous post is:

\begin{tabular}{c|cccccc} \verb+x\y+ & Army & Bucknell & Holy Cross & Lafayette & Lehigh & Navy \\ \hline Army & 0 & 0 & 1 & 0 & 0 & 0 \\ Bucknell & 2 & 0 & 0 & 2 & 3 & 0 \\ Holy Cross & 0 & 3 & 0 & 4 & 14 & 0 \\ Lafayette & 10 & 0 & 0 & 0 & 0 & 0 \\ Lehigh & 2 & 0 & 0 & 11 & 0 & 0 \\ Navy & 11 & 14 & 8 & 22 & 6 & 0 \\ \end{tabular}
This leads to the following matrix:

M_0=\left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ 2 & 0 & 0 & 2 & 3 & 0 \\ 0 & 3 & 0 & 4 & 14 & 0 \\ 10 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 11 & 0 & 0 \\ 11 & 14 & 8 & 22 & 6 & 0 \\ \end{array}\right) .

The edge-weighted score-differential graph associated to M_0 (regarded as a weighted adjacency matrix) is in the figure below.

sm261_baseball-ranking-application_teams-digraph2

This matrix M_0 must be normalized to create a (row) stochastic matrix:

M = \left(\begin{array}{cccccc} 0 & 0 & 1 & 0 & 0 & 0 \\ {2}/{7} & 0 & 0 /{7} /{7} & 0 \\ 0 /{7} & 0 /{21} /{3} & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ {2}/{13} & 0 & 0 /{13} & 0 & 0 \\ {11}/{61} /{61} /{61} /{61} /{61} & 0 \\ \end{array}\right) .

Next, to insure it is irreducible, we replace M by A=(M+J)/2, where J is the 6\times 6 doubly stochastic matrix with every entry equal to 1/6:

A=\left(\begin{array}{cccccc} {1}/{12} & 1/{12} & 7/{12} & 1/{12} & 1/{12} & 1/{12} \\ {19}/{84} & 1/{12} & 1/{12} & 19/{84} & 25/{84} & 1/{12} \\ {1}/{12} & 13/{84} & 1/{12} & 5/{28} & 5/{12} & 1/{12} \\ {7}/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} & 1/{12} \\ {25}/{156} & 1/{12} & 1/{12} & 79/{156} & 1/{12} & 1/{12} \\ {127}/{732} & 145/{732} & 109/{732} & 193/{732} & 97/{732} & 1/{12} \end{array}\right).

Let

{\bf v}_0 = \left( \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6} , \frac{1}{6}\right).

The ranking determined by the random walker method is the reverse of the left eigenvector of A associated to the largest eigenvalue \lambda_{max}=1 (by reverse, I mean that the vector ranks the teams from worst-to-best, not from best-to-worst, as we have seen in previous ranking methods).
In other words, the vector

{\bf r}^*=\lim_{n\to \infty}{\bf v}_0A^n.

This is approximately

{\bf r}^* \cong \left(0.2237\dots ,\,0.1072\dots ,\,0.2006\dots ,\,0.2077\dots ,\,0.1772\dots ,\,0.0833\dots \right).

Its reverse gives the ranking:

Army < Lafayette < Bucknell < Lehigh < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.