I’m pretty sure the etiquette of puzzle creation insists that a “good” puzzle has a unique solution—but bear with me! I promise I’m breaking the rules of etiquette for a good reason!

Applied Algebra

A Variety Show

Courtney Gibbons
Hamilton College

My interest in applied algebra was a long time coming. I’m not exactly a fan of living in reality, so the idea of taking something so lovely (to me) as algebra and applying it to things like disease modeling or phylogenetic trees seemed too, well, real. That’s not to say I didn’t realize how important these applications are, but those weren’t applications that captured my interest or imagination—at least, not right away!

Around 2010, I came across a paper by Elizabeth Arnold, Stephen Lucas, and Laura Taalman that described how to use algebra (particularly Groebner bases) to solve Sudoku (see reference [1]). The principles are the same as in many “real world” applied algebra settings, and thanks to this paper, I started to get interested in using algebra to help better understand the world we live in. At the same time, the 2010 Mathematics Subject Classification added “applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)” (13P25) to its list.

Today’s blog post will walk through some of the commutative algebra and algebraic geometry involved in solving a 4 by 4 Sudoku puzzle (called “shidoku”). The interested can play along by downloading this Macaulay2 file, shidoku.m2, and running computations on the University of Melbourne’s Macaulay2 web server: https://www.unimelb-macaulay2.cloud.edu.au/#home.

First off, let’s review the rules of the game. In a 4 by 4 grid, there are sixteen cells arranged into four rows, four columns, and four 2 by 2 cages that each take up a corner of the square.

Each cell can be populated with the numbers 1, 2, 3, or 4 in such a way that each row, column, and cage contains all four numbers exactly once.

Those rules describe everything you need to play on an empty board, but a board usually already has some cells filled in. Give it a whirl:

When you’ve finished, play it again—but get rid of the blue 4 and see how many solutions you can find. When you finish that one, put the blue 4 back, add an additional 4 to the fourth row and second column, and see what happens.

Regarding the variations, I’m pretty sure the etiquette of puzzle creation insists that a “good” puzzle has a unique solution—but bear with me! I promise I’m breaking the rules of etiquette for a good reason! Anyway, given how quickly you can mentally solve these puzzles, the natural question is: why bother with algebra? Aside from the obvious (and somewhat cheeky) answer, why NOT?, I often find it useful to understand mathematical ideas by seeing them applied to a situation I know pretty well. In this case, it’s solving a small logic puzzle.

The first step in applying algebra to a puzzle is figuring out how to model the game and its rules. If we take a big-picture look at what we’re doing, we’re trying to find a very special point in sixteen-dimensional space that satisfies the rules of the game. So, we could imagine setting up a bunch of polynomials in sixteen variables, one variable for each cell, that describe the rules and the clues so that a (hopefully unique!) zero of all the polynomials represents a (hopefully unique!) solution to our puzzle.

In other words, we’re going to start with the polynomial ring $\mathbb{C}[x_{11}, x_{12}, \ldots, x_{44}]$, and we’re going to make an ideal $I$ that represents our puzzle. Solutions to our puzzle will belong to the set $V(I) = \{(a_{11},a_{12},\ldots,a_{44}) \, : \, a_{ij} \in \mathbb{C} \text{ and } f(a_{11},a_{12},\ldots,a_{44}) = 0 \, \forall \, f \in I\}$.

As a reminder—or a teaser—an ideal $I$ in a (commutative) ring $R$ is a nonempty set that is closed under addition, subtraction, and the “multiplicative absorption” property (less poetically called “scalar multiplication” by some): for all $a$ in $I$ and $r \in R$, $ar \in I$. Its partner concept from geometry is that of a variety in an affine (or projective) space, which is a set of points that are simultaneous solutions to a set of polynomial equations. For instance, the set of polynomial equations could be the polynomials belonging to an ideal in a polynomial ring, in which case we call the variety $V(I)$.

Here’s a little example in a more familiar setting. Consider the polynomials $x+y$ and $y^3 – x^2$. They generate an ideal, $J = \langle x+y,y^3-x^2 \rangle$, which includes all linear combinations (with “scalars” from $\mathbb{R}[x,y]$) of the generators. Setting both generators equal to zero, we plot a line and a cusp, and their simultaneous solutions are the points $(1,-1)$ and $(0,0)$ in $\mathbb{R}^2$. That means $V(J) = \{(1,-1),(0,0)\}$.

You can read more about ideals and varieties, their interactions, and the algorithms that make them nice to work with in [2].

So, back to our games. Let’s build the ideal $I$ that represents the game. The clues on the board are easiest to encode because if we know that the cell in row one, column three must be 3, we must ensure that points in $V(I)$ satisfy $a_{13} = 3$. Since we insist (by definition of $V(I)$) that the polynomial $x_{13} – a_{13} = 0$ when we evaluate it at any point in $V(I)$, this means $x_{13} – 3$ is in our set of clues. You can work out the rest of the clues’ polynomials similarly.

The rules of the game are a little more complicated to model, but let’s muddle through. We know that we want each cell to be one of the numbers 1, 2, 3, or 4, which means for each cell, we have a polynomial $(x_{ij} – 1)(x_{ij} – 2)(x_{ij} – 3)(x_{ij} – 4)$. I suppose I could have tried fiddling with my coefficient ring or solution space to work modulo 4, but some of the algebra I want to use requires that we are working over an algebraically closed field. So I’ve chosen to work over the complex numbers (although if you’re playing with the code, you’ll notice I just picked a “big enough” finite field so that Macaulay2 wouldn’t gripe at me!).

We also know that we want each row (respectively, column; doubly respectively, cage) to contain the numbers 1, 2, 3, and 4 exactly once. In the case of the first row, this means solutions satisfy $x_{11} + x_{12} + x_{13} + x_{14} – 10$ and $x_{11}x_{12}x_{13}x_{14} – 24$. Alas, $1 + 1 + 4 + 4 = 10$ satisfies the addition rule if we leave off the multiplication rule, and $2\cdot 2\cdot 2 \cdot 3 = 24$ satisfies the multiplication rule if we leave off the addition rule. If we leave off the 1-through-4 rules for each cell, we get fun complex solutions like $a_{11} = 1+\sqrt{-5}, a_{12} = 1-\sqrt{-5}, a_{13} = 2, a_{14} = 2$; it’s an exercise for the reader to make sure these satisfy the addition and multiplication rules.

This set completely describes our game board: two rules for each row, two for each column, two for each cage, and a rule for each cell. Putting all these polynomials together along with the clues, and then closing them up under addition, subtraction, and multiplication by elements of $R$, we find the ideal $I$ we’re interested in. And the points in $V(I)$ are precisely the solutions to our game.

The connection between our ideal $I$ and our variety $V(I)$ is via one of the best theorems out there: Hilbert’s Nullstellensatz! One form of the Nullstellensatz states that, over an algebraically closed field, there’s a one-to-one correspondence between maximal ideals and varieties consisting of a single point.

Let’s think about this in the two-variable example. The variety $V(J)$ can be expressed a union of simpler varieties, $V(J) = \{(1,-1)\} \cup \{(0,0)\} = V(x-1,y+1) \cup V(x,y)$. In terms of the Nullstellensatz, the point $(1,-1)$ corresponds to the maximal ideal $\langle x-1,y+1\rangle$ and the point $(0,0)$ corresponds to the maximal ideal $\langle x,y \rangle$. We don’t quite have that $J$ is the intersection of these ideals, but it does satisfy $J \subseteq \langle x-1, y+1 \rangle \cap \langle x, y\rangle$. (Why not equality in general? If you think about varieties as sets of points, the points themselves don’t carry information about whether they’re single or double or triple roots of a polynomial. By working with ideals, we can factor polynomials and recover multiplicity information about roots that varieties aren’t fine enough to catch.)

Back to our game! If we’re looking for points that solve our game on the algebraic geometry side, we harness the power of the Nullstellensatz to look for all the maximal ideals that contain our ideal $I$ on the algebra side. And there’s an app for that! By app, I mean a technique called “primary decomposition” that can be done computationally. Emmy Noether played a big role in establishing the generality and usefulness of primary decompositions. She proved that in a Noetherian ring, every ideal can be decomposed as a finite intersection of primary ideals—giving us another kind of factorization. The curious reader will find primary decomposition covered in commutative algebra classics like [3] and [4].

If your Sudoku board doesn’t have a unique solution, calculating the primary decomposition of $I$ will let you find all the solutions—and if the board has incompatible clues, you’ll learn that through primary decomposition, too.

If you’re curious about the number of solutions to the empty board, you (by which I mean your computer or U. Melbourne’s) can calculate the primary decomposition of the game board with no clues to find that there are (spoiler!) 188 solutions to the blank board.

These tools—ideals, varieties, primary decomposition (among others)—form your starter kit for solving lots of real-world problems. In fact, these tools are so powerful that the 2020 Mathematics Subject Classification newly includes “statistics on algebraic and topological structures” covering algebraic statistics (62R01), statistical aspects of big data/data science (62R07), and topological data analysis (62R40), as well as new classes in 14Q for computational aspects of algebraic geometry. Applied algebra is a bustling and booming research area! For a charming introduction to algebraic statistics applied to computational biology, pick up [5].

References:

[1] Arnold, Elizabeth; Lucas, Stephen; Taalman, Laura. Groebner Basis Representations of Sudoku. The College Mathematics Journal, Vol. 41, No. 2, March, 2010.

[2] Cox, David A.; Little, John; O’Shea, Donald. Ideals, Varieties, and Algorithms: an introduction to computational algebraic geometry and commutative algebra. Fourth edition. Undergraduate Texts in Mathematics. Springer, 2015.

[3] Atiyah, M. F.; Macdonald, I. G. Introduction to Commutative Algebra. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. 1969.

[4] Matsumura, Hideyuki. Commutative Ring Theory. Translated from the Japanese by M. Reid. Second edition. Cambridge Studies in Advanced Mathematics, 8. Cambridge University Press, Cambridge, 1989.

[5] Algebraic Statistics for Computational Biology. Edited by Lior Pachter and Bernd Sturmfels. Cambridge University Press, New York, 2005.

–

Author’s Note: I wrote the first draft of this blog post before the US Supreme Court decision that gutted abortion rights (kicking off a season of decisions and opinions that also upended climate regulation, tribal law, and more). I hope readers found Sara Stoudt’s column last month timely! I also wish all readers of this blog the privilege and comfort of finding solace in mathematics, pure or applied, during turbulent times.

If your eyebrows quirked a bit at seeing “abortion” in an AMS feature column, I urge you to read Karen Saxe’s excellent piece over at the MAA’s Math Values Master Blog, Mathematicians’ Case for Preserving the Right to Abortion. As a mathematician and soon-to-be first-time mom, I have a redoubled commitment to (and new appreciation for) a person’s right to choose when and if to carry a pregnancy to term.