{"id":1233,"date":"2022-08-01T00:01:36","date_gmt":"2022-08-01T04:01:36","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=1233"},"modified":"2022-08-02T10:16:52","modified_gmt":"2022-08-02T14:16:52","slug":"applied-algebra-a-variety-show","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2022\/08\/01\/applied-algebra-a-variety-show\/","title":{"rendered":"Applied Algebra: A Variety Show"},"content":{"rendered":"

I\u2019m pretty sure the etiquette of puzzle creation insists that a \u201cgood\u201d puzzle has a unique solution\u2014but bear with me! I promise I\u2019m breaking the rules of etiquette for a good reason!<\/em> <\/span><\/p>\n

Applied Algebra<\/h1>\n

A Variety Show<\/h2>\n

Courtney Gibbons<\/strong>
\nHamilton College<\/strong><\/p>\n

My interest in applied algebra was a long time coming. I\u2019m 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<\/em>. That\u2019s not to say I didn\u2019t realize how important these applications are, but those weren\u2019t applications that captured my interest or imagination\u2014at least, not right away!<\/p>\n

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 \u201creal world\u201d 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<\/a> added “applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)” (13P25) to its list.<\/p>\n

\"Laura
Laura Taalman makes mathematical models when she isn’t solving Sudoku!<\/figcaption><\/figure>\n

Today\u2019s 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<\/a>, and running computations on the University of Melbourne\u2019s Macaulay2 web server: https:\/\/www.unimelb-macaulay2.cloud.edu.au\/#home<\/a>.<\/p>\n

First off, let\u2019s 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.<\/p>\n

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.<\/p>\n

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:<\/p>\n

\"A
By the way, if you’re hooked on puzzles, don’t miss William Casselman’s recent column about Wordle<\/a>!<\/figcaption><\/figure>\n

When you’ve finished, play it again\u2014but 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.<\/p>\n

Regarding the variations, I\u2019m pretty sure the etiquette of puzzle creation insists that a \u201cgood\u201d puzzle has a unique solution\u2014but bear with me! I promise I\u2019m 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?<\/em>, I often find it useful to understand mathematical ideas by seeing them applied to a situation I know pretty well. In this case, it\u2019s solving a small logic puzzle.<\/p>\n

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\u2019re doing, we\u2019re 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.<\/p>\n

In other words, we\u2019re going to start with the polynomial ring $\\mathbb{C}[x_{11}, x_{12}, \\ldots, x_{44}]$, and we\u2019re 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\\}$.<\/p>\n

As a reminder\u2014or a teaser\u2014an ideal<\/strong><\/em> $I$ in a (commutative) ring $R$ is a nonempty set that is closed under addition, subtraction, and the \u201cmultiplicative absorption\u201d property (less poetically called \u201cscalar multiplication\u201d by some): for all $a$ in $I$ and $r \\in R$, $ar \\in I$. Its\u00a0partner concept from geometry is that of a variety<\/strong><\/em> 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)$.<\/p>\n

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)\\}$.<\/p>\n

\"A
The equations $x+y =0$ and $y^3-x^2 = 0$, when plotted in $\\mathbb{R}^2$, intersect at two points. These are their simultaneous solutions.<\/figcaption><\/figure>\n

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

So, back to our games. Let\u2019s 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\u2019 polynomials similarly.<\/p>\n

The rules of the game are a little more complicated to model, but let\u2019s 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\u2019ve chosen to work over the complex numbers (although if you\u2019re playing with the code, you\u2019ll notice I just picked a \u201cbig enough\u201d finite field so that Macaulay2 wouldn\u2019t gripe at me!).<\/p>\n

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\u2019s an exercise for the reader to make sure these satisfy the addition and multiplication rules.<\/p>\n

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\u2019re interested in. And the points in $V(I)$ are precisely the solutions to our game.<\/p>\n

The connection between our ideal $I$ and our variety $V(I)$ is via one of the best theorems out there: Hilbert\u2019s 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.<\/p>\n

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<\/em> 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.)<\/p>\n

Back to our game! If we\u2019re 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\u2019s an app for that! By app, I mean a technique called \u201cprimary decomposition\u201d 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\u2014giving us another kind of factorization<\/a>. The curious reader will find primary decomposition covered in commutative algebra classics like [3] and [4].<\/p>\n

\"A
Emmy Noether in 1930.<\/figcaption><\/figure>\n

If your Sudoku board doesn\u2019t have a unique solution, calculating the primary decomposition of $I$ will let you find all<\/em> the solutions\u2014and if the board has incompatible clues, you\u2019ll learn that through primary decomposition, too.<\/p>\n

If you\u2019re 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.<\/p>\n

These tools\u2014ideals, varieties, primary decomposition (among others)\u2014form your starter kit for solving lots of real-world problems. In fact, these tools are so powerful that the 2020 Mathematics Subject Classification<\/a> 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].<\/p>\n

References:<\/strong><\/p>\n

[1] Arnold, Elizabeth; Lucas, Stephen; Taalman, Laura. Groebner Basis Representations of Sudoku<\/a><\/em>. The College Mathematics Journal, Vol. 41, No. 2, March, 2010.<\/p>\n

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

[3] Atiyah, M. F.;\u00a0Macdonald, I. G.\u00a0Introduction to Commutative Algebra<\/em>.\u00a0Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. 1969.<\/p>\n

[4] Matsumura, Hideyuki.\u00a0Commutative Ring Theory<\/em>.\u00a0Translated from the Japanese by M. Reid. Second edition.\u00a0Cambridge Studies in Advanced Mathematics, 8.\u00a0Cambridge University Press, Cambridge,\u00a01989.<\/p>\n

[5] Algebraic Statistics for Computational Biology<\/em>. Edited by Lior Pachter and Bernd Sturmfels.\u00a0Cambridge University Press, New York,\u00a02005.<\/p>\n

–<\/p>\n

Author’s Note:<\/strong> 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<\/a> timely! I also wish all readers of this blog the privilege and comfort of finding solace in mathematics, pure or applied, during turbulent times. <\/em><\/p>\n

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<\/a>. 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.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

I\u2019m pretty sure the etiquette of puzzle creation insists that a \u201cgood\u201d puzzle has a unique solution\u2014but bear with me! I promise I\u2019m 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 timeRead More →<\/a><\/span><\/p>\n","protected":false},"author":5,"featured_media":793,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4,6,10],"tags":[95,84,93,94,92],"class_list":["entry","author-cgibbons","post-1233","post","type-post","status-publish","format-standard","has-post-thumbnail","category-4","category-algebra-and-number-theory","category-courtney-gibbons","tag-algebraic-geometry","tag-games","tag-groebner-bases","tag-ring-theory","tag-sudoku"],"jetpack_featured_media_url":"https:\/\/i0.wp.com\/mathvoices.ams.org\/featurecolumn\/wp-content\/uploads\/sites\/2\/2022\/03\/cropped-cropped-mathvoices-banner-feat-col-1.png?fit=1200%2C279&ssl=1","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1233","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/comments?post=1233"}],"version-history":[{"count":16,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1233\/revisions"}],"predecessor-version":[{"id":1278,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/posts\/1233\/revisions\/1278"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media\/793"}],"wp:attachment":[{"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/media?parent=1233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/categories?post=1233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathvoices.ams.org\/featurecolumn\/wp-json\/wp\/v2\/tags?post=1233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}