In Topics in Algebraic Combinatorics, students are harnessing the power of algebra to count possibilities and describe symmetry.
How many ways can you color the faces of a cube with 8 crayons, if rotations of a given coloring are considered the same?
This problem would not look out of place in our entry-level combinatorics class, but to try it is to discover its devilish difficulty. Forget about testing all the possibilities—there are thousands. You can color the faces in 8×8×8×8×8×8 ways, but symmetry renders many of these colorings redundant. How many? It isn’t easy to say: a coloring with six different colors has been duplicated 24 times, while a coloring with all faces the same color has only been counted once (and these are just the extremes in a range of possibilities). An accurate census of all the types of colorings looks like a massive undertaking at best.
However, mathematics is resourceful. A branch of algebra called group theory, which at first glance has little to do with counting problems, turns out to provide exactly what we need here: a detailed description of the symmetries of a cube (or any other figure). With insights from group theory, we can work out in just a few minutes that the number of colorings is 11,712.
Borrowing from one branch of mathematics to solve hard problems in another is not the exception, but the rule. Now that our more advanced students have some algebra, geometry, number theory, combinatorics, and analysis under their belts, they can begin to hybridize their knowledge—and so the real fun begins!
As the title suggests, this course has mostly been a blend of algebra and combinatorics. Along with group theory, the other major tool we took from algebra is the power series—a gadget like a polynomial, but infinite in length. Here’s a power series that encodes the Fibonacci sequence:
The coefficients in front of each term (1, 1, 2, 3, 5, …) are the Fibonacci numbers themselves, and the exponents keep count of each term’s position in the sequence. This series “puts the Fibonacci sequence on display”, but its mathematical usefulness begins with the discovery that it can be simplified to x/(1–x–x2): a finite representation of an infinite sum. Such representations are known as generating functions because they can be used to generate lots of information about a sequence. Since operating on a power series can affect its every term, working with generating functions is like choreographing an infinite whirl of calculations. Like the concepts students are learning to wield in classes as disparate from ours as Literature 2 and World History, generating functions are a tool for taking hold of quantities of information that can seem unmanageably complex.
Generating functions are as flexible as they are powerful. Once students had some comfort with the basic “theme”, each student began a separate research project exploring one of its many variations. Carried out over four weeks, these projects culminated in an extravaganza of 20-minute mini-seminars in which each student taught the basics of their topic to the class. Even by Proof School standards, this was a very “grown-up” experience—most sources students read were meant for advanced undergraduates, and the presentation slides they created were written in the same LaTeX extension many mathematicians use when giving talks. But the class brought to the project all the youthful joy and enthusiasm I’ve come to expect from them, and took an ardent interest in one another’s projects. One student managed to connect his topic to a number theory problem he researched last year; as time goes on, I look forward to seeing students make more and more of these connections.
-- Austin Shapiro