A Game on Noetherian Rings - MathOverflow

A Game on Noetherian Rings

2012-04-06T03:24:54Z

A friend suggested the following combinatorial game. At any time, the state of the game is a (commutative) Noetherian ring $\neq 0$. On a player's turn, that player chooses a nonzero non-unit element of the ring, and replaces the ring with its quotient by the ideal generated by that element. The player to make the last legal move wins, by passing the opponent a field.

So if the ring was $\mathbb C[x,y]/(x^2+y^2-1)$, and a player chooses $x$, the ring becomes $\mathbb C[y]/(y^2-1)$. This is a poor move, as his opponent can turn the ring into a field by choosing either $y+1$ or $y-1$, and win. A winning move would have been $x+iy+1$, which turns the ring into a field immediately and wins the game.

Problem: Given a ring, how can we tell if it is a winning position for the first player or for the second player?

(The game terminates since the original ring is Noetherian, and an unending game would be an infinite ascending chain in the original ring.)

Answer by Pat Devlin for A Game on Noetherian Rings

2012-04-06T12:56:13Z

The idea of a hierarchy on Noetherian rings as suggested earlier is good, but it doesn't reflect the structure of the problem. For example, a move need not reduce the "type" of a ring (it is clear from definition however, that a move cannot reduce the type by more than 1). For instance, the ring $\mathbb{C}[x,y] / (x^2 + y^2-1)$ is of "type 1" (as noted in the original post). If we mod out by $x$, we obtain the ring $\mathbb{C}[y]/(y^2 - 1)$, which is also of "type 1".

It is also not clear (at all!) that an optimal move "ought" to decrease the "type" by 1 if possible.

Here is a different idea that resolves this issue and creates a hierarchy of Noetherian rings preserving a "win/lose" structure:

First, slightly change the original game so that you are allowed to mod out by a unit element and the win conditions become "the first player to pass his opponent the zero ring loses" [this game is the same as the original one].

Then we construct the following rooted directed acyclic graph, $G$:

The vertices of $G$ are the "set" of Noetherian rings, where two rings are the same vertex iff they are isomorphic [to even discuss this collection of isomorphism classes requires the axiom of choice, and it's probably too big to be called a set, but I don't think that's too important].
The directed edges of $G$ are you draw an edge from $R$ to $S$ iff there is some $0 \neq r \in R$ such that $S \cong R/(r)$ [i.e., iff a player can get to $S$ from $R$ in one move].

Then the graph $G$ is acyclic and rooted (with root $0$) since any path in this graph must have finite length terminating in 0 (since all the rings are Noetherian).

Finally, to analyze the game, we just need to mark each vertex as "win for player 1" or "win for player 2" in the usual way.

Things to consider

I believe the "type" of a ring, $R$, as defined earlier is just the length of the shortest path from $R$ to a field.
To what extent can we algorithmically determine (pieces of) the graph $G$?
If we were magically given the graph $G$, to what extent can we use it to algorithmically determine who wins in each case?

-Pat Devlin

Answer by Kevin Buzzard for A Game on Noetherian Rings

2012-04-07T11:15:12Z

I computed the nimbers of a few rings, for what it's worth. I don't see any sensible pattern so perhaps the general answer is hopelessly hard. This wouldn't be surprising, because even for very simple games like sprouts starting with $n$ dots no general pattern is known for the corresponding nimbers.

OK so the way it works is that the nimber of a ring $A$ is the smallest ordinal which is not in the set of nimbers of $A/(x)$ for $x$ non-zero and not a unit. The nimber of a ring is zero iff the corresponding game is a second player win -- this is a standard and easy result in combinatorial game theory. If the nimber is non-zero then the position is a first player win and his winning move is to reduce the ring to a ring with nimber zero.

Fields all have nimber zero, because zero is the smallest ordinal not in the empty set. An easy induction on $n$ shows that for $k$ a field and $n\geq1$, the nimber of $k[x]/(x^n)$ is $n-1$; the point is that the ideals of $k[x]/(x^n)$ are precisely the $(x^i)$. In general an Artin local ring of length $n$ will have nimber at most $n-1$ (again trivial induction), but strict inequality may hold. For example if $V$ is a finite-dimensional vector space over $k$ and we construct a ring $k\oplus \epsilon V$ with $\epsilon^2=0$, this has nimber zero if $V$ is even-dimensional and one if $V$ is odd-dimensional; again the proof is a simple induction on the dimension of $V$, using the fact that a non-zero non-unit element of $k\oplus\epsilon V$ is just a non-zero element of $V$, and quotienting out by this brings the dimension down by 1. In particular the ring $k[x,y]/(x^2,xy,y^2)$ has nimber zero, which means that the moment you start dealing with 2-dimensional varieties things are going to get messy. But perhaps this is not surprising -- an Artin local ring is much more complicated than a game of sprouts and even sprouts is a mystery.

Rings like $k[[x]]$ and $k[x]$ have nimber $\omega$, the first infinite ordinal, as they have quotients of nimber $n$ for all finite $n$. As has been implicitly noted in the comments, the answer for a general smooth connected affine curve (over the complexes, say) is slightly delicate. If there is a principal prime divisor then the nimber is non-zero and probably $\omega$ again; it's non-zero because P1 can just reduce to a field. But if the genus is high then there may not be a principal prime divisor, by Riemann-Roch, and now the nimber will be zero because any move will reduce the situation to a direct sum of rings of the form $k[x]/(x^n)$ and such a direct sum has positive nimber as it can be reduced to zero in one move. So there's something for curves. For surfaces I'm scared though because the Artin local rings that will arise when the situation becomes 0-dimensional can be much more complicated.

I don't see any discernible pattern really, but then again the moment you leave really trivial games, nimbers often follow no discernible pattern, so it might be hard to say anything interesting about what's going on.

Answer by Martin Brandenburg for A Game on Noetherian Rings

2012-04-21T17:05:37Z

We could also play this game with groups. One starts with a group $G$. A move consists in replacing $G$ by $G/\langle\langle a \rangle\rangle$, i.e. we mod out the smallest normal subgroup containing $a \neq 1$. The ending condition holds iff the ascending chain condition with respect to normal subgroups holds (do these groups have a name?). When $G$ is abelian, this means that $G$ is finitely generated.

Actually we can play this game for every algebraic structure: Given a variety in the sense of universal algebra, start with with an algebra $A$. A move consists in replacing $A$ by $A/a \sim b$, where $a,b \in A$ with $a \neq b$. The game proposed by Will Sawin is the game on rings, including the zero ring, under the misère play rule, i.e. the last one moving loses (see Tom Goodwillie's comment).

I have tried to analyze this game for abelian groups, non-abelian groups, and rings in the article Algebraic games. There are lots of scattered examples, but for abelian groups the structure theorem makes it possible to give a general answer which ones are $\mathcal{P}$ (i.e. are losing positions):

Let $A$ be a finitely generated abelian group.

Under the normal play rule, $A$ is a $\mathcal{P}$-position if and only if $A$ is a square, i.e. $A \cong B^2$ for some finitely generated abelian group $B$.

Under the misère play rule, $A$ is a $\mathcal{P}$-position if and only if $A$ is either a square, but not elementary abelian of even dimension, or elementary abelian of odd dimension.

Now for something on-topic, some results about the game on rings:

If $R$ is $\mathcal{P}$, then $\mathrm{Spec}(R)$ is connected (Lemma 6.2). Let $R$ be a Dedekind domain. If $R$ has some principal maximal ideal, then $R$ is $\mathcal{N}$. Otherwise, $R$ is $\mathcal{P}$ (Prop. 6.3). It follows, for example, that $k[x,y]/(y^2-x^3+x-1)$ is $\mathcal{P}$. Hence, $k[x,y]$ is $\mathcal{N}$. Section 6.2 is devoted to zero-dimensional rings (whose complexity was already mentioned by Tom Goodwillie), finally showing that the cusp $k[x,y]/(y^2-x^3)$ is $\mathcal{P}$.

Many problems remain open, for example if $k[x_1,\dotsc,x_n]$ is $\mathcal{N}$ for all $n \geq 1$.