Exploring Groups and Codes


Cryptography provides a usefully practical application to go along with the more abstract concerns of a branch of mathematics known as group theory. Each topic casts light on the other which explains why they're frequently introduced in tandem  just as I'm doing here. Additionally, with a very high level language in the picture, namely Python, we gain access to an interactive environment within which to investigate both the theory and the application. I've become quite the evangelist for this "math through programming" approach to curriculum writing, having discovered that developing the material within the context of a command line interface (CLI) may provide that key "missing ingredient" which both catalyzes student understanding and motivates explorations of the concepts beyond what's presented in the text. I provide more background regarding my evolving approach to curriculum writing in the For Further Reading section at the bottom of this page. A Simple CipherA "clubhouse code" consists of simple letter substitutions. The shuffle method in random.py (part of the standard library) makes it easy and straightforward to generate a substitution dictionary: 
""" Set domain = string.digits if you want to work with integers instead of printable letters  or experiment with other domains """ _domain = string.printable def mkcode(): """ Return a string containing the elements in _domain randomly permuted """ targ = list(_domain) shuffle(targ) return string.join(targ,"") def mkdict(secretkey): """ Turns _domain + secretkey into a dictionary of substitution pairs """ keydict = {} j = 0 for i in _domain: keydict[i]=secretkey[j] j += 1 return keydict The above utility, mkcode( ), returns a shuffled _domain suitable for use the string.mktrans( ) to generate a translation table. Python translation tables are strings of 256 bytes in some new order. mkdict(key) pairs the _domain with the shuffled version to return a substitution dictionary. Were I dealing with playing cards, the resulting dictionary would randomly pair each card in Deck A with another in Deck B. Because both decks have an equal number of cards, no card is without its paired target  which just might be the same card. Usage: >>> _domain = string.printable So what's with _domain? It's a modulelevel variable intially defined as all printable charaters (= string.printable). But I might want to use integers or just uppercase letters as my domain. Integers are what the group theory people tend use when discussing permutations (i.e. substitution dictionaries). You can always have numbers serve as standins for letters, or for any other kind of object, so moving to integers doesn't really change the basic mechanics of the situation. Alternative usage: >>> ciphers._domain = string.digits Permutation NotationMathematicians have come up with an alternative notation for representing the same information as in mycode. Pick a number, any number to start, then worm your way through the dictionary, training each item to the one it maps to, e.g. using the above example, 8 maps to 7 which maps to 5 and so on through 4, 0, 1, 7 and finally back to 8. Now organize this loop into a tuple: ('8', '7', '5', '4', '0', '1', '6'), with the understanding that each member is followed by its pair, with the last member wrapping around to the first member, i.e. 6 maps to 8. We aren't finished yet though, as we didn't get to all members with this single loop. 9 maps to 2 maps to 3 maps to 9  another cycle (loop), with no members in common with the first (speaking more technically, we can say the cycles are 'disjoint' meaning their intersection is the empty set). Perhaps you will want to try writing a short Python routine that takes such a dictionary of unshuffled,shuffled pairs, as up top, and converts same to a list of cyclic tuples, as per the above example. The cycles2dict method included in the source module (ciphers.py) shows one possible solution. Usage: >>> p = cycles2dict(mkdict(mycode)) >>> p [('8', '7', '5', '4', '0', '1', '6'), ('9', '2', '3')] And you'd want to make it bidirectional: >>> dict2cycles(p) {'8': '7', '9': '2', '6': '8', '7': '5', '4': '0', '5': '4', '2': '3', '3': '9', '0': '1', '1': '6'} The thing to realize is that when a code pairs a letter with itself (or number with itself), you simply don't mention it in the cycles notation. Like, if it's the 'identity dictionary' (every letter is paired with itself), then the list of corresponding cyclic tuples is empty, and vice versa: >>> dict2cycles({1:1,2:2,3:3,4:4}) # identity dictionary returns [ ] [ ] >>> ciphers._domain = string.uppercase >>> cycles2dict([]) {'Z': 'Z', 'X': 'X', 'Y': 'Y', 'V': 'V', 'W': 'W', 'T': 'T' ... etc.} Symmetry GroupsGroup theory meets geometry when we consider symmetry groups. What rotations may we apply to a geometric shape such that it superimposes on itself? In other words, what rotations around what axes will permit you overlay the "before" and "after" pictures of a shape, and have them align perfectly? When you rotate a square flat on the table by 90 degrees, it looks just the way it did before. You might also flip it over, like a pancake, and yet still have it look the same (except maybe the two sides have different colors). The same ideas apply not just to polygons (flat shapes) but to polyhedra (spatial shapes). Think of colored spheres stuck on the four corners of a tetrahedron. We can use permutations to describe the ways these spheres might swap around with one another in ways consistent with rotation around various axes. The permutations act on the set of vertices. For example, suppose you put a tetrahedron on a table and hold the apex fixed with your thumb, while rotating the base triangle 120 degrees. Three base spheres move to adjacent positions, with the 3rd coming round to occupy the position formerly held by the first. If these spheres were labeled A,B and C, the permutation might be expressed as [('A','B','C')]. The apex sphere, D, does not move, and so does not get mentioned in the permutation. rotations.py contains a Tetrahedron class which does little more than write itself out to a file intelligible to POVRay, a free ray tracing program. Accompanying this class are the 12 possible permutations, including the identity permutation (every sphere stays as it is), which describe the tetrahedron's symmetry group. 
>>> otet = rotations.Tetrahedron() # tet object >>> otet.listp() # tet: 12 permutations Permutation: [('B', 'C', 'A')] Permutation: [('D', 'A', 'B')] Permutation: [('B', 'A', 'C')] Permutation: [('D', 'B', 'A')] Permutation: [('D', 'A', 'C')] Permutation: [('D', 'C', 'A')] Permutation: [('D', 'B', 'C')] Permutation: [('D', 'C', 'B')] Permutation: [('D', 'C'), ('B', 'A')] Permutation: [('D', 'B'), ('C', 'A')] Permutation: [('D', 'A'), ('B', 'C')] Permutation: [] >>> rotations.genpix(5,otet) # take random snap shots 

By applying these 12 permutations, or products of these permutations (multiplication is defined below), to our tetrahedron, we move its vertices around among fixed positions. Any product of these 12 permutations will likewise be one of the 12. This closure property, where the product of any two elements in a set gets another element in the set, is essential to any group, as are some other properties discussed in the next section. 
>>> oc = rotations.Cube() >>> rotations.genpix(10,oc) # cube: 24 permutations 
Key: A,B,C,D E,F,G,H 


