Elementary combinatorics and cryptanalysis

Why would a mathematician interested in combinatorics and cryptanalysis named lynne marie butler post the list below?

a lenient mulburry
tell riemann buyer
eat blurry linemen
eminent blurry ale
brainy menu teller
rumble realty nine
berlin realty menu
ninety mule barrel
mull binary entree
ninety marble rule
miller bunyan tree
eerily mental burn
I'm about to tell you the answer, so delay reading on if you want to figure it out yourself. Each row of the list is a permutation of the multiset of letters in her name, and both combinatorics and cryptanalysis start with the study of permutations. The multiset that is being permuted has type (3,2,2,2,2,1,1,1,1,1,1,1) because each row has 3 e's, 2 l's, 2 n's, 2 r's, 2 blanks, and 1 each of the other 7 letters. (Curtis Greene can do this to your name. You can read more about elementary combinatorics in Brualdi's Introductory combinatorics, and cryptanalysis in Sinkov's Elementary Cryptanalysis: a mathematical approach. My favorite advanced texts on these subjects are Stanley's Enumerative combinatorics, and Koblitz's A course in number theory and cryptography.)

Order analogues

The subsets of a multiset of type (2,2,1) may be visualized using the diagram shown below at right. (Under inclusion, these subsets form a partially ordered set; the diagram shown is its Hasse diagram.) Likewise, the subgroups of the group Z/4Z x Z/4Z x Z/2Z may be visualized using the diagram shown below at left. This group is a finite abelian p-group of type (2,2,1), for the prime p=2.

An order-preserving surjection that relates subgroups of a finite abelian p-group of type µ and subsets of a multiset of type µ is illustrated by the animation you'll see if you click anywhere on the subgroup lattice shown above. This surjection is defined in my paper Order analogues and Betti polynomials. The animation that illustrates the case µ = (2,2,1) and p=2 was produced with the help of Toby Orloff, using software developed by the Geometry Center. It suggests that if [µ,k] is the number of subgroups of order pk in a finite abelian p-group of type µ, then

[(2,2,1),5] = 1
[(2,2,1),4] = 1 + p + p2
[(2,2,1),3] = 1 + p + 2 p2 + p3
[(2,2,1),2] = 1 + p + 2 p2 + p3
[(2,2,1),1] = 1 + p + p2
[(2,2,1),0] = 1
because there is 1 subgroup at the top level 5, 1+2+4 subgroups at level 4, 1+2+2(4)+8 subgroups at levels 3 and 2, 1+2+4 subgroups at level 1, and 1 subgroup at the bottom level 0. In my first paper, A unimodality result in the enumeration of subgroups of a finite abelian group, I proved that [µ,k]≤[µ,k+1] if k < n/2 and µ is a partition of n. The subgroup lattice doesn't narrow as you move toward its middle level!

Student researchers

Scott Kravitz On a Theorem of Stanley Concerning the h-vector of a Simplicial Polytope, senior paper, Haverford College, 1999. Kravitz studied just enough algebraic geometry (Fulton's text on Toric Varieties) to understand Stanley's result that the h-vector of a simplicial polytope is unimodal. Kravitz went on to the Ph.D. program in mathematics at Michigan. Scott and Joslyn are pictured at right. Visit Scott's home page at Michigan.

The h-vector of a simplicial polytope is computed from its f-vector, which counts the number of faces in each dimension. So, for example, the f-vector of an octahedron is (6,12,8) because it has 6 vertices, 12 edges and 8 triangular facets. The h-vector of an octahedron is (1,3,3,1).
Noel Watson Subgroups of finite abelian groups, summer research paper, Haverford College, 1995. Watson devised a combinatorial proof of the fact, known to Steinitz in 1901, that the number of subgroups of order pk equals the number of subgroups of order pn-k in a finite abelian group of order pn. He employed the combinatorial description of the polynomials [µ,k] given in Butler's paper Subgroup lattices and symmetric functions . He majored in mathematics and concentrated in computer science at Haverford, then went on to Wharton.

For type (1,1,...,1), this result is the "p-analogue" of the fact that the number of subsets of cardinality k equals the number of subsets of cardinality n-k in a set of cardinality n. A combinatorial proof of this fact pairs each subset with its complement.
Anduin Touw Construction and Properties of Regular Four-Dimensional Polytopes, senior thesis, Haverford College, 1994. Touw's thesis exhibits the 24-cell as the convex hull of a subgroup of 24 unit quaternions. A project Miller Maley wrote for Butler's seminar on finite reflection groups, at the 1993 Summer Mathematics Institute, motivated Touw's thesis. Butler and Maley gave a 1994 SMI colloquium talk at Berkeley on Touw's work, and Touw went on to the Ph.D. program in mathematics at UCLA supported by a National Physical Sciences Consortium Fellowship.

The regular three-dimensional polytopes are the tetrahedron, the cube, the octahedron, the dodecahedron, and the icosahedron; three of these five Platonic solids have triangular facets. There are six regular four-dimensional polytopes; the one that has octahedral facets is called the 24-cell.
David Lippel Möbius function alternation in partially ordered sets, senior thesis, Haverford College, 1994. Lippel's thesis provides a beautiful exposition of the combinatorics and topology underlying the techniques used to obtain the main result of Butler's paper Order analogues and Betti polynomials. Lippel, who also studied logic with George Weaver at Bryn Mawr, was awarded an NSF Graduate Fellowship in Mathematics to pursue model theory at Berkeley. In 2001 he earned a Ph.D. in Mathematics from the University of California at Berkeley. His dissertation, entitled "Finitely axiomatizable omega-categorical theories", was guided by Leo Harrington. He is now a postdoc at McMaster University.

The Möbius function for partially ordered sets generalizes the Möbius function µ in number theory. If n is a product of k distinct primes, then µ(n) is 1 if k is even and -1 if k is odd. In Enumerative Combinatorics, Richard Stanley explains the topological significance of the Möbius function for partially ordered sets.
William Toll The Hall polynomial: Theoretical background and Macdonald's method for calculation, senior thesis, Haverford College, 1993. Toll's work led to the formulation of a conjecture generalizing the main result of Butler's paper Nonnegative Hall polynomials. Miller Maley later proved this conjecture by improving Macdonald's method for calculating Hall polynomials. Toll went on to the masters program in mathematics at Columbia University.

Laurie Rubel Noncooperative Zero and General Sum Games, senior thesis, Haverford College, 1992. Rubel's thesis was inspired by Butler's unpublished work on game-theoretic analyses of matching algorithms. This work, in turn, was initiated to study the auction algorithm that Butler invented and Maley implemented for Princeton University to place students into limited enrollment courses. Rubel went on to earn a masters degree at Tel Aviv University Graduate School of Education. In 2002 she earned a Ph.D. in Research in Mathematics Education from Teachers College of Columbia University. Her dissertation, entitled "Probabilistic Misconceptions: Middle and High School Students' Judgments Under Uncertainty" was guided by Henry Pollak. She is now a postdoc at the University of Wisconsin at Madison.

Eric Muhlheim Some computations on subgroup lattice embeddings, senior thesis, Princeton University, 1991. The computations in this thesis are acknowledged in Generalized flags in p-groups, a paper coauthored by Butler and Hales. Muhlheim went on to work for Morgan Stanley in New York.

Michael Aguilar Combinatorial properties of the lattice of subgroups of a finite abelian p-group, senior thesis, Princeton University, 1990. Aguilar proved that [µ,k]2≥[µ,k-1][µ,k+1] for µ=(2,1,...,1), a special case of Butler's conjecture in The q-log-concavity of q-binomial coefficients that the lattice of subgroups of any finite abelian group is rank-log-concave. Aguilar went on to the Ph.D. program in mathematics at The University of Chicago supported by an NSF Graduate Fellowship for Minorities.


Return to the home page of Lynne Butler.

Return to the home page of the Department of Mathematics at Haverford College.

This page was created by lbutler@haverford.edu. It was last updated 3/27/03.