\documentclass[report]{owrart}
\usepackage{amssymb}
\newtheorem{thm}{Theorem}
\newtheorem{conj}[thm]{Conjecture}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newcommand\NN{\mathbb{N}}
\newcommand\ZZ{\mathbb{Z}}
\newcommand\minus{\smallsetminus}
\newcommand\nothing{\varnothing}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{talk}[Alan Guo and Michael Weimerskirch]{Ezra Miller}%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{Potential applications of commutative algebra to combinatorial game theory}
{Miller, Ezra}
\subjclass{91A46, 91A05, 20M14, 06F05, 13F99, 20M25, 13-06}
% 91A46 Combinatorial games
% 91A05 2-person games
% 20M14 Commutative semigroups
% 06F05 Ordered semigroups and monoids
% 13F99 (In section "arithmetic rings and other special rings")
% 20M25 Semigroup rings
% 13-06 Proceedings, conferences, collections, etc.
\noindent
Finite combinatorial games involving two players taking turns on the
same game board are much more complex when the last player to move
loses (mis\`ere play, as in Dawson's chess) instead of winning (normal
play, as in Nim). The goal of Combinatorial Game Theory, in this
setting, is to describe---abstractly and algorithmically---the set of
winning positions for any given game, or any given class of games.
Recent developments by Plambeck \cite{Plambeck05}, and later also with
Siegel \cite{Plambeck-Siegel08}, have introduced certain commutative
monoids, called \emph{mis\`ere quotients}, as contexts in which to
classify winning positions in mis\`ere play; see \cite{Siegel06} for a
gentle introduction. Our aim is to develop \emph{lattice games},
played on affine semigroups, to place arbitrary impartial
combinatorial games---but particularly the historically popular notion
of octal game---in a general context where commutative algebra might
be brought to bear on periodicity questions. In this note, we state a
precise conjecture to the effect that sets of winning positions in
lattice games are finite unions of translates of affine semigroups,
drawing analogies and connections to the combinatorics of monomial
local cohomology and binomial primary decomposition.
In what follows, $C$ is a fixed \emph{affine semigroup} in~$\ZZ^d$;
thus $C$ is a finitely generated submonoid of~$\ZZ^d$. We
additionally require that $C$ be \emph{pointed}: its identity is its
only unit (i.e., invertible element). The games are basically played
on~$C$, with allowed lattice moves taken from a fixed set~$\Gamma$.
\begin{defn}\label{EM-d:ruleset}
A finite subset $\Gamma \subset \ZZ^d \minus \{0\}$ is a \emph{rule
set} if
\begin{enumerate}
\item[1.]%
$\NN\Gamma$ is pointed, and
\item[2.]%
$\NN\Gamma \supseteq C$.
\end{enumerate}
A \emph{game board}~$G$ is the complement in $C$ of a finite
$\Gamma$-order ideal in $C$ called the set of \emph{defeated
positions}. Elements in~$G$ are called \emph{positions}.
A~\emph{move} proceeds from a position $p \in G$ to a point $p -
\gamma$ for some $\gamma \in \Gamma$; the move is \emph{legal} if $p -
\gamma \in G$.
\end{defn}
\emph{Normal play} corresponds to the choice of $D = \nothing$; in
that case, the goal is to be the player whose move lands at the
origin. \emph{Mis\`ere play} corresponds to the choice of $D =
\{0\}$; in that case, the goal is \emph{not} to be the player whose
move lands at the origin. In this sense, mis\`ere play is ``normal
play in which one tries to lose''.
It is implicit in the definition that $\Gamma$ induces a partial order
on~$C$; the elementary proof is omitted. Conjecture~\ref{EM-conj}
will make sense with the above notion of rule set~$\Gamma$, but one or
more of the following stronger conditions on~$\Gamma$ might be
required.
\begin{enumerate}
\item[3.]%
$\Gamma$ is the minimal generating set for $\NN\Gamma$.
\item[4.]%
For each ray~$\rho$ of~$C$, there exists $\gamma_i \in \Gamma$ lying
in the \emph{negative tangent cone} $-T_\rho C = -\bigcap_{H \supset
\rho} H_+$ of~$C$ along~$\rho$, where $H_+ \supset C$ is the positive
closed half space defined by a supporting hyperplane~$H$ for~$C$.
\item[5.]%
Every $p \in C$ has a $\Gamma$-path to~$0$ contained in~$C$; that is,
given~$p$, there exists a sequence $0 = p_0, p_1, \ldots, p_r = p$
in~$C$ with $p_k - p_{k-1} \in \Gamma$ for all~$k > 0$.
\end{enumerate}
Condition~4 is precisely what is necessary to guarantee that from
every position there is a $\Gamma$-path ending in a neighborhood of
the origin. Thus condition~5 implies condition~4, though we omit the
proof.
\begin{defn}\label{EM-d:WL}
Fix a game board $G$ with rule set~$\Gamma$. Then $W \subseteq G$ is
the set of \emph{winning positions}, and $L \subseteq G$ is the set of
\emph{losing positions}, if
\begin{enumerate}
\item[1.]%
$W$ and $L$ partition $G$,
\item[2.]%
$(W + \Gamma) \cap G = L$, and
\item[3.]%
%$(W - \Gamma) \cap \NN^d \subset L \cup D$. Equivalently:
$(W - \Gamma) \cap W = \nothing$.
\end{enumerate}
\end{defn}
The last player to make a legal move wins; this holds both for normal
play and mis\`ere play, as well as the generalizations for larger~$D$.
A~position is winning if the player who just moved there can force a
win. Condition~1 says that every position is either winning or
losing. Condition~2 says that the losing positions are precisely
those positions possessing legal moves to~$W$: if your opponent lands
on a losing position, then you can always move to~$W$ to force a win.
Condition~3 says that it is impossible to move directly from one
winning position to another.
\begin{conj}\label{EM-conj}
If $W$ is the set of winning positions for a lattice game, then $W$ is
a finite union of translates of affine semigroups.
\end{conj}
The conjecture, if true, would furnish a finite data structure in
which to encode the set of winning positions. This would be the first
step toward effectively computing the winning positions. Note that
the mis\`ere octal game \emph{Dawson's chess}~\cite{Dawson34} remains
open; that game initiated and still motivates much of the research on
mis\`ere games, and one hope would be to use lattice games, along with
whatever computational commutative algebra might arise, to crack it.
According to the theory invented by Sprague and Grundy in the 1930s
\cite{Grundy39,Sprague36}, all normal play impartial games are
equivalent to the particularly simple game Nim under a certain
equivalence relation. For mis\`ere games, the analogous equivalence
relation is too weak (i.e., too many equivalence classes:\ not enough
games are equivalent to one another). That is why Plambeck invented
mis\`ere quotients \cite{Plambeck05}. In the setting of lattice
games, the equivalence relation is as follows.
\begin{defn}
Fix a game board $G = C \minus D$ with winning positions~$W$. Two
lattice points $p$ and~$q \in C$ are \emph{congruent} if $(p + C) \cap
W = p - q + (q + C) \cap W$. The \emph{mis\`ere quotient} of~$C$ is
the set $Q$ of congruence classes.
\end{defn}
Thus $p$ and $q$ are congruent if the winning positions in the
``cones'' above them are translates of one another. It is elementary
to verify that the quotient map $C \to Q$ is a morphism of monoids.
Plambeck and Siegel have studied mis\`ere quotients in quite a bit of
algebraic detail \cite{Plambeck-Siegel08}; as this is the proceedings
for a conference on commutative algebra, it is strongly recommended
that the reader have a look at their work, as it is filled with
commutative algebra of finitely generated monoids.
\begin{thm}
Conjecture~\ref{EM-conj} holds when the mis\`ere quotient is finite.
\end{thm}
\begin{proof}
Follows by properly interpreting the combinatorial description of
primary decomposition \cite{DMM08} of the binomial presentation ideal
of the semigroup ring for~$Q$ inside of the semigroup ring for~$C$.
\end{proof}
{}From discussions with Plambeck, Siegel, and others, as well as from
examples, it seems likely that binomial primary decomposition has a
further role to play in open questions about mis\`ere quotients. Such
questions include when finiteness occurs, and more complex ``algebraic
periodicity'' questions, which have yet to be formulated
precisely~\cite{Siegel06}.
There is another analogy with commutative algebra that is worth
bearing in mind. When $I$ is a monomial ideal in an affine semigroup
ring, and $M$ is a finitely generated finely graded (i.e.,
$\ZZ^d$-graded) module, then the local cohomology $H^i_I(M)$ is
supported on a finite union of translates of affine semigroups
\cite{Helm-Miller05}. If Conjecture~\ref{EM-conj} is true, then
perhaps one could develop a homological theory for winning positions
in combinatorial games that explains why.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{8}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Dawson34}
Thomas Dawson, \emph{Fairy Chess Supplement}, The Problemist: British
Chess Problem Society \textbf{2} (1934), no.~9, p.~94, Problem~No.~1603.
\bibitem{DMM08}
Alicia Dickenstein, Laura~Felicia Matusevich, and Ezra Miller,
\emph{Combinatorics of binomial primary decomposition},
Math. Zeitschrift, 19 pages. DOI:~10.1007/s00209-009-0487-x
\bibitem{Grundy39}
Patrick M. Grundy, \emph{Mathematics and games}, Eureka \textbf{2}
(1939), 6--8; reprinted \textbf{27} (1964), 9--11.
\bibitem{Helm-Miller05}
David Helm and Ezra Miller, \emph{Algorithms for graded injective
resolutions and local cohomology over semigroup rings}, Journal of
Symbolic Computation \textbf{39} (2005), 373--395.
\bibitem{Plambeck05}
Thane E.\ Plambeck, \textit{Taming the wild in impartial combinatorial
games}, Integers \textbf{5} (2005), no.~1, G5, 36~pp. (electronic)
\bibitem{Plambeck-Siegel08}
Thane E.\ Plambeck and Aaron N.\ Siegel, \textit{Mis\`ere quotients for
impartial games}, Journal of Combinatorial Theory, Series~A
\textbf{115} (2008), no.~4, 593--622.
\bibitem{Siegel06}
Aaron N.\ Siegel, \textit{Mis\`ere games and mis\`ere quotients},
preprint. \texttt{arXiv:math.CO/0612.5616}
\bibitem{Sprague36}
Roland P. Sprague, \emph{\"Uber mathematische Kampfspiele [On
mathematical war games]}, T\^ohoku Math. Journal \textbf{41}
(1935--1936) 438--444.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{thebibliography}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{talk}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%