Z12triangleD8 triangle

PascGalois Triangles & Hexagons and other Group-related Cellular Automata

Kathleen M. Shannon & Michael J. Bardzell
Support provided by the National Science Foundation award # DUE-0087644
and by the Richard A. Henson endowment for the School of Science at Salisbury University.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

The PascGalois Project: Visualizing Abstract Algebra

Abstract algebra has traditionally been one of the most difficult and least visual subjects in the undergraduate mathematics curriculum. Often it is the least popular course in the minds of many mathematics majors by the time they finish their degree. Books in the newest generation of modern algebra textbooks include more emphasis on symmetry and applications such as coding theory, Cayley graphs, crystallography, boolean algebras, etc. to help “repair” the image problem that abstract algebra has had (see [3] for example). With the rise of computers in the classroom and computer algebra systems, there has also been an increased interest in computational techniques for polynomial rings and their applications to algebraic geometry at the undergraduate level (see [2]). With the increased emphasis on symmetry, algebraic geometry, etc., some students are starting to see a focus on more visual connections to abstract algebra. Currently we are engaged in an NSF funded project, The PascGalois project, to introduce a new class of examples for undergraduate algebra that will also focus on visualization. But we are not just focusing on objects related to algebra, we are also interested in providing ways to visualize fundamental algebraic concepts as well - notions such as closure, subgroups, and even quotient groups.

The PascGalois project has its origin in a simple exercise with Pascal’s triangle. Take each entry in the triangle and replace it with its congruent value mod n, where n is a positive integer larger than 1. By assigning each of the values 0,1,...,n-1 a distinct color, patterns reminiscent of fractals appear. Our interest in this construction lies in the fact that addition mod n is the group multiplication of the cyclic group Zn and the patterns seen in the triangles are related to the structure of these groups. These patterns have been studied in the literature where the triangles are often treated as a type of 1-dimensional cellular automata (see [4] and [5]). A cellular automata consists of a discrete lattice of cells where each cell can take on values from some alphabet A. The cells are updated in discrete time steps according to some local rule - that is, the value of a given cell at time t is a function of the values of its neighboring cells at time t-1. In the case of Pascal’s triangle mod n, each successive row corresponds to the next time frame. The local rule in this case is simply “add the two entries above” for the current cell value. We can think of all the cells outside the triangle as being zero.

Now let us generalize this construction using other groups. If G is a group with a and b elements of G, then a PascGalois triangle is formed by placing a down the left side of the triangle and b down the right. An entry in the interior of the triangle is determined by multiplying the two entries above it using the group multiplication. Of course, if G is non-abelian then one must specify a left or right multiplication. We denote this PascGalois triangle by (PG , a, b). Like Pascal’s triangle mod n, PascGalois triangles can have self-similar properties. Furthermore, many of these properties can be described using subgroups, quotients, and automorphisms of the group G.

 

 

 

a

 

b

 

 

 

 

 

 

 

 

 

 

 

 

 

 

a

 

ab

 

b

 

 

 

 

 

 

 

 

 

 

 

 

a

 

aab

 

abb

 

b

 

 

 

 

 

 

 

 

 

 

a

 

aaab

aababb

abbb

 

b

 

 

 

 

 

 

 

 

PascGalois triangle generated by group elements a and b.

 

To see how these structures can be used to visualize algebraic concepts, let us consider the triangle (PG, a, b) where G=D3, the symmetry group of an equilateral triangle, a corresponds to a reflection and b to a 120 degree rotation. If we form the quotient group modulo the rotational subgroup of order three, we obtain a group isomorphic to Z2. We can visualize this by coloring all the rotations in the triangle one color and all the reflections a second color. This helps the student “see” how one can identify all the elements in a coset into a single point in a quotient group. Thinking of a composite structure such as an equivalence class as a point in a new abstract group can be difficult for many students. This exercise helps to visually reinforce the concept.

D3triangleD3triangle First 64 rows of the D3 (left) and Z2 (right) triangles. The Z2 triangle has 1 down the left side and 0 down the right. The quotient identification modulo the rotational subgroup of order 3 transforms the left triangle into the right triangle.
As a second example, consider the following images generated by dihedral groups where we place a reflection down the left side of the triangle and the minimal nonzero rotation down the right:

D4triangleD6triangleD8triangle
Triangles generated by the dihedral groups D4, D6, and D8 , respectively.

Students should notice that the images generated by dihedral groups whose orders are a power of two have some qualitative differences from the other images. The reason for this has to do with orders of group elements. The only dihedral groups Dn that are p-groups are those where p=2 and n=2m. In this case the order of each group element is a power of two. In the non 2-group cases one can always find group elements whose orders are relatively prime. The presence of group elements whose orders are relatively prime can have dramatic effects on the appearance the the corresponding triangles. Students can examine these effects and then the instructor may follow up with a discussion of subgroup lattices, cyclic subgroups, orders of elements, prime factorizations of group orders, and so on.

            As a third example let us consider PascGalois triangles generated by Zn × Zm where (0,1) is placed down the left and (1,0) is placed down the right. Students can reflect the images about the central vertical axis and examine what happens to each cell in the triangle.



z2xz2 trianglez2xz2 triangle -

The first 9 (left) and 16 (right) rows of triangles generated by
Z2 × Z2. (0,1) is down the left side of the triangle and (1,0) down the right.

Upon experimentation one sees that this reflection induces the automorphism given by (r,s) → (s,r) if and only if n=m. If n≠m, then reflection does not even induce a set map. That is, two different locations of the same group element (color) can be reflected to 2 distinct group elements. For a more detailed description of these and other exercises see [1] and our visualization exercises.


A related structure is a 2-dimensional cellular automata generated by a group multiplication. 2-D automata are rectangular grids of cells which take on various state values that change discretely over time according to some local rule. The 2-D automata from this project are multi-state variations of Conway’s Game of Life. The Game of Life is known to have interesting dynamical properties using two states (dead or alive) and using local rules to update the automata in the next time frame. Using groups as an alphabet and group multiplication for the various local rules, the long term behavior of these systems can often be understood in terms of the subgroup lattice of the underlying group and dimensions of the grid for the finite case.

The primary goal of this project is to develop exercises that will help undergraduate mathematics majors, including prospective secondary school teachers, to develop intuition about and visualize many of the fundamental concepts in Abstract Algebra. We are in the process of producing visualization materials that can be used for class demonstrations, student computer exercises, group projects, or even the starting point for an undergraduate research project. The focus will be on creating PascGalois triangles and other cellular automata generated using group and ring multiplication rules to aid in giving students a visual understanding of key concepts in abstract algebra. A secondary goal is to provide projects for undergraduate research.


For the text of the original article as published follow this link.

Soon we will be adding Java run cellular automata. We hope to add visualization exercises for dynamical systems, number theory and mathematics enrichment in the not too distant future. Please contact us if you have any questions or would like preprints of articles in review.

References: