← Differential Calculus of Games
Ver1__Hensyuumain.tex
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{cleveref}
\usepackage{array}
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
% \addbibresource{biblio.bib}
\addbibresource{CommonBiblio20240922.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{question}[theorem]{Question}
\newtheorem{idea}[theorem]{Idea}
\newcommand{\dq}[1]{``#1"}
\newcommand{\suzukimemo}[1]{\textcolor{red}{suzuki: #1}}
\newcommand{\horamemo}[1]{\textcolor{orange}{hora: #1}}
\newcommand{\para}[1]{\paragraph{\textbf{#1}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textbf{#1}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\gS}{\mathbb{S}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\Pf}{\mathcal{P}_{\mathrm{fin}}}
\newcommand{\Gs}{\mathbf{Games}}
\newcommand{\nsum}{\oplus}
\newcommand{\Alg}[1]{\mathbf{Alg}_{#1}}
\newcommand{\Coalg}[1]{\mathbf{Coalg}_{#1}}
\newcommand{\RecCoalg}[1]{\mathbf{RecCoalg}_{#1}}
\newcommand{\PfAlg}{\Alg{\Pf}}
\newcommand{\PfCoalg}{\Coalg{\Pf}}
% \newcommand{\mex}[1]{\mathrm{mex}(#1)}
\newcommand{\mex}{\mathrm{mex}}
\newcommand{\xem}{\mathrm{xem}}
\newcommand{\hylo}{\mathrm{hylo}}
% \newcommand{\G}[2]{\mathcal{G}_{#1}(#2)}
\newcommand{\G}{\mathcal{G}}
\newcommand{\rel}{\to}
\newcommand{\red}{\mathrm{red}}
\newcommand{\cp}{\ast}
\newcommand{\acc}{\rightsquigarrow}
\newcommand{\str}{\theta}
\newcommand{\Image}{\mathrm{Im}}
\newcommand{\HF}{\mathbb{HF}}
\newcommand{\Nim}[1]{\mathrm{Nim}_{#1}}
\renewcommand{\H}{\mathbb{H}}
\newcommand{\epi}{twoheadrightarrow}
\newcommand{\mono}{rightarrowtail}
\newcommand{\RB}{\mathcal{R}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\rd}{\mathrm{rd}}
\newcommand{\Fam}{\mathbf{Fam}}
\newcommand{\Fgames}{\Fam(\Gs_*)}
\newcommand{\BS}{\mathcal{BS}}
\title{Differential Calculus of Games}
\author{Ryuya Hora, Ryo Suzuki}
\thanks{ZEN University. \url{ryuya_hora@zen.ac.jp}}
% \date{\today}
\subjclass[2020]{MSC}
\keywords{Keywords}
\begin{document}
\begin{abstract}
\end{abstract}
\maketitle
\tableofcontents
\begin{idea}
Our goal is to clarify the implicit differential structure behind combinatorial game theory and demystify the Nim-sum.
\end{idea}
\section{Differential operator on games }
\subsection{Differential 2-rig of game families}
\begin{definition}[Ryuya Hora]
A \demph{pointed game} is a pair $(\X,x)$ of a game $\X=(X, \to)$ (in the sense of \cite{hora2024games}) and an element $x\in X$.
The category of pointed games and point-preserving game morphisms is denoted by $\Gs_*$.
\end{definition}
\begin{definition}[Ryuya Hora]
Let $\Fgames$ denote the free coproduct cocompletion of $\Gs_*$.
\end{definition}
An object of $\Fgames$ is an indexed family of pointed games $\{(\X_\lambda,x_\lambda)\}_{\lambda\in \Lambda}$.
\begin{proposition}[Ryuya Hora]
The conway addition $\otimes$ on $\Gs$ is extended to a monoidal structure on $\Fgames$ by
\[
\{(\X_i, x_i)\}_{i\in I} \otimes \{(\Y_j, y_j)\}_{j\in J} \coloneqq \{(\X_i \otimes \Y_j, x_i \otimes y_j)\}_{(i,j)\in I\times J}.
\]
Furthermore, it defines a rig structure on $\Fgames$ with the categorical coproducts.
\begin{itemize}
\item $0= \{\} \text{ (empty family)}$
\item $1= \{(\{x\},x)\}_{*\in \{*\}}$
\item $X\otimes (Y+Z)= X\otimes Y + X \otimes Z$
\end{itemize}
\end{proposition}
\begin{definition}[Ryuya Hora]
The \demph{differential operator}
\[
\partial\colon \Gs_* \to \Fgames
\]
is defined by
\[
\partial (\X,x) \coloneqq \{(\X, x')\}_{x\to x'}.
\]
The unique coproduct-preserving extension
\[
\partial\colon \Fgames \to \Fgames
\]
is also denoted by the same symbol $\partial$.
\end{definition}
\begin{proposition}[Ryuya Hora]\label{prop:DifferentialStructureOfGameFamilies}
The differential operator $\partial$ satisfies the categorified Leibniz rule:
\[
\partial (X \otimes Y) \cong \partial X \otimes Y + X \otimes \partial Y
\]
\end{proposition}
This is quite similar to the situation of \cite[][Proposition 5]{joyal1981theorie}.
\horamemo{This should be a \demph{differential 2-rig} \cite{loregian2021differential}}
By microcosm principle, these differential structures on the category $\Fgames$ will be reflected on its terminal object $\{(\H,h)\}_{h\in \H}$.
\begin{question}
Is there a \dq{composition} of a game such that the categorified chain rule holds?
\end{question}
\begin{question}
Is $\Fgames$ a Grothendieck topos? \horamemo{$\Gs_*$ shares a lot of categorical structures with $\Set_*$, and $\Fam(\Set_*)$ is equivalent to the topos of idempotents.}
\end{question}
\subsection{Differential rigs and differential invariants of games}
\begin{definition}\label{def:differentialrig}
A \demph{differential rig} is a (possibly non-commutative) rig (= semiring) $(A, 0,1, +, \times)$ equipped with a unary operation called \demph{differential operator}
$
\partial \colon A \to A
$
such that
\begin{itemize}
\item $\partial (0) = 0$
\item $\partial (a+b) = \partial a + \partial b$
\item $\partial (1) =0$
\item $\partial (ab) = (\partial a )b + a(\partial b)$
\end{itemize}
\end{definition}
This is equivalent to assuming
\[
\partial \left(\sum_{i=1}^n a_i \right) = \sum_{i=1}^n \partial a_i
\]
and
% \[
% \partial \left(\prod_{i=1}^n a_i \right) = \sum_{i=1}^n\left( \partial (a_i)\prod_{j \neq i}a_j \right)
% \]
\[
\partial \left(a_1 \times \dots \times a_n \right) = \sum_{i=1}^n\left( a_1 \times \dots \times a_{i-1} \times (\partial a_i) \times a_{i+1} \times \dots \times \dots \times a_n \right)
\]
for every non-negative integer $n$.
\begin{definition}\label{def:differentialInvariant}
A \demph{differential invariant} of $\Fgames$, is a function\footnote{which is a proper-class large function}
$p\colon \ob(\Fgames)\to A$ to a differential rig $A$, that respects $0,1,+,\times, \partial$.
\end{definition}
\begin{example}[Differential rig of polynomial]
The commutative ring of polynomials $\Z[x]$ equipped with the usual notion of differentiation $\partial \colon \Z[x]\to \Z[x]$ is a differential rig. \Cref{def:RealValuedGeneratingFunctions} is an example of a differential invariant of games.
\end{example}
\begin{example}[max-plus algebra]\label{exmpl:Max-PlusAlgebra}
The max-plus algebra $\N\cup \{-\infty\}$ admits a unique differential rig structure such that ${\deg}\colon \N[x]\to\N\cup \{-\infty\}$ is a differential rig homomorphism. More concretely,
\[
\partial n \coloneqq
\begin{cases}
n-1 & (n>0)\\
-\infty &(n\leq 0)
\end{cases}
\]
\end{example}
\begin{example}[Trivial differential structure]
For any rig $A$, $\partial(a) \coloneqq 0$ defines a trivial differential structure regarding every element constant.
\end{example}
\begin{definition}
Let $\Omega =\{\bot, \top\}$ denote the rig of truth values. \horamemo{This is sometimes regarded as ``$\mathbb{F}_1$" by some authors, like Lawvere or Connes. \cite{lawvere2008core, connes2017geometry} Why...? Here might be some relationship with rig-(tropical-)geometry \cite{menni2021basis}. See also \cref{rmk:Max-plusAsGames}}
The addition is $\lor$ and the multiplication is $\land$. For a monoid $M$, let $\Omega[M]$ denote the free $\Omega$-rig generated by the monoid $M$, i.e., the left adjoint for the forgetful functor
\[
\begin{tikzcd}
\Omega/\mathbf{Rig} \ar[r,"U"'] &\mathbf{Rig} \ar[r, "U"']& \mathbf{Monoid}\ar[ll, bend right, "{\Omega[{-}]}"'].
\end{tikzcd}
\]
\end{definition}
\begin{lemma}\label{lem:RigInducedByMonoid}
For a monoid $(M, e, *)$, the resulting rig $\Omega[M]$ is isomorphic to $\Pf(M)$ equipped with
\begin{description}
\item[zero] $0\coloneqq \emptyset$,
\item[one] $1 \coloneqq \{e\}$,
\item[addition] $A+B \coloneqq A\cup B$, and
\item[multiplication] $A\times B \coloneqq \{a*b\mid a\in A, b\in B\}$
\end{description}
\end{lemma}
\begin{theorem}
For a monoid $M$, the following data are in one-to-one correspondence:
\begin{itemize}
\item Differential rig structure on $\Omega[M]$.
\item Monoid object in the monoidal category $(\PfCoalg, \otimes\footnote{conway addition})$ whose underlying monoid is $M$.
\end{itemize}
\end{theorem}
\begin{proof}
A differential rig structure
\[
\partial \colon \Omega[M] \to \Omega[M]
\]
is nothing other than a function (= $\Pf$-coalgebra structure)
\[
\delta \colon M \to \Omega[M] \cong \Pf(M)
\]
satisfying
\begin{enumerate}
\item $\delta(e) =\emptyset$ and
\item $\delta (ab) = \delta(a) \{b\} \cup \{a\}\delta(b) = \{a'b\mid a'\in \delta (a)\}\cup \{ab'\mid b' \in \delta (b)\}$.
\end{enumerate}
The first condition says that $1 \to M$ is a $\Pf$-coalgebra morphis, and the second says that $M\times M \to M$ is a $\Pf$-coalgebra morphism.
\end{proof}
\horamemo{this can be generalized to differential rig, like $\Z[x]$ or $\Omega[\H]$. The first provides the generating polynomial above, and the latter might provide Ryo Suzuki's pov. The commutative ring $\Z[\H]$ does not satisfy the Leibniz rule, but the ordered semiring $\N[\H]$ satisfies the lax version of the Leibniz rule.}
% \horamemo{To deal with Nim-sum, we should consider \demph{hereditarily finite sets}-valued generating function.}
If we want to consider $(\Gs, \otimes)$, (not $(\PfCoalg, \otimes)$), we need the notion of ``finite degree".
\begin{definition}[Finite degree differential rig]
For a differential rig $A$, we adopt the following terminology.
\begin{itemize}
\item The \demph{degree} of an element $a\in A$ is the minimum natural number $n\in \N$ such that $\delta^n (a) =0$, if such $n$ exists.
\item An element is said to be \demph{of finite degree} if it has a degree (in $\N$).
\item A differential rig $A$ is said to be \demph{of finite defree}, if every element is of finite degree.
\end{itemize}
\end{definition}
\begin{example}
For the differential rig $C^{\infty}(\R)$, an element $f\colon \R \to \R$ is of finite degree if and only if $f$ is a polynomial. While $C^{\infty}(\R)$ is not of finite degree as a differential rig, $\Z[x]$ is a typical example of a differential rig of finite degree.
\end{example}
\begin{theorem}
For a monoid $M$, there is a one-to-one correspondence between
\begin{description}
\item[Game enrichment] A monoid object in $(\Gs, \otimes)$ with the underlying monoid $M$.
\item[Differential str] Differential rig structure of finite degree on $\Omega[M]$
\end{description}
\end{theorem}
\begin{corollary}\label{cor:DifferentialRigOfGameFamilies}
Since the terminal monoid $\H$ in $(\Gs, \otimes)$ is obviously a monoid object, we obtain a differential rig $\Omega[\H]$ of finite degree. Via the bijection $\H = \Pf(\H)\cong \Omega[\H]$, this structure is written down as:
\begin{description}
\item[zero] $0\coloneqq \{\} = \emptyset$
\item[sum] $A+B \coloneqq A\cup B$
\item[one] $1 = \{\{\}\}$
\item[prod] $AB \coloneqq \{a\ast b \mid a\in A, b\in B\}$, where $a\ast b$ is the terminal monoid structure ($a*b \coloneqq \{a'*b\mid a'\in a\} \cup \{a*b'\mid b'\in b\}$).
\item[diff] $\partial A \coloneqq \bigcup_{a\in A} a = \{a_2\mid a_2 \in a_1 \in A\}$.
\end{description}
\end{corollary}
% For example, $n\coloneqq\{0,1,\dots n-1\}$ is an element of $\H$. Their addition is $n+m= \max(n,m)$, and its derivative is $\partial (n) = n-1$ except $\partial (0) = 0$.
% Their multiplication is a bit more complicated. It is not closed within natural numbers: $2\times 2 = \{0,1,\{1\}\}$.
\begin{remark} This differential rig structure shares the same idea with \cref{prop:DifferentialStructureOfGameFamilies}.
It is better to consider the differential rig $\H$ as an algebra of \demph{lists\footnote{it is more accurate to say families} of games} rather than an algebra of games. Each element of the rig is regarded as a finite list of (pointed impartial) games. The addition is a concatenation of the list of games, the multiplication is the game-wise Conway addition, and the differential is the list of all possible next states.
\end{remark}
\begin{remark}[Max-plus algebra in the differential rig of games]\label{rmk:Max-plusAsGames}
The max-plus algebra $\N\cup\{-\infty\}$ (\cref{exmpl:Max-PlusAlgebra}) is embedded into the rig of game families $\H$ respecting the differential structure!
% as follows:
First, we define $[n]\in \H$ by $[0]= \emptyset$ and $[n+1]=\{[n]\}$. We can recursively prove that $[n]*[m]=[n+m]$.
A function $\iota \colon \N\cup \{-\infty\} \to \H$ defined by
\[
\iota(n) \coloneqq
\begin{cases}
\{[0], \dots ,[n]\} & (n\geq 0)\\
\{\} & (n= -\infty)
\end{cases}
\]
is an embedding of differential rig.
\end{remark}
\horamemo{There should be a similar differential rig for Partizan games.}
\horamemo{We need to consider a lax morphism between differential rigs}
\subsection{Integral rigs}
\begin{definition}\label{def:IntegralRig}
An \demph{integral rig} is a rig $A$, equipped with an \demph{integral operator} $\int$, that is, a function $\int \colon A \to A$ satisfying
\begin{description}
\item[Nullary Rota-Baxter equation] $1 = \int 0$
\item[Binary Rota-Baxter equation] $(\int f)(\int g) = \int(f(\int g) + (\int f) g)$
\end{description}
\end{definition}
\begin{remark}[$n$-ary Rota-Baxter equations]
In the definition, we assume two Rota-Baxter equations, which can be unified to \demph{$n$-ary Rota-Baxter equation}
\[
\left(\int f_1\right) \times \dots \times \left(\int f_n\right) = \int \left ( \sum_{i=1}^n \left(\int f_1 \right) \times \dots \times \left(\int f_{i-1} \right) \times f_i \times \left(\int f_{i+1} \right) \times \dots \times \left(\int f_{n} \right)\right).
\]
% The binary Rota-Baxter equation is the what is ususally called Rota-Baxter equation. The nullary Rota-Baxter equation is $1= \int 0$.
Assuming the nullary and binary Rota-Baxter equations is equivalent to assuming all $n$-ary equations for $n\in \N$. This is an example of \href{https://ncatlab.org/nlab/show/too+simple+to+be+simple#relationship_to_biased_definitions}{[Biased definition]}.
% \[\textstyle
% \int f_1 \times \dots \times \int f_n = \int \sum_{i=1}^n \int f_1 \times \dots \times \int f_{i-1} \times f_i \times \int f_{i+1} \times \dots \times \int f_{n} .
% \]
\end{remark}
% We don't assume
% \begin{description}
% \item[lineality] $\int(f+g)=\int f + \int g$
% \item[Fundamental theorem of calculus'] $\int \partial f = f$
% \end{description}
\begin{example}
For a real number $\lambda \in \R$, the function
\[
\int\colon f(x)\mapsto \lambda+ \int_0^{x}f(t)dt
\]
% satisfies the first condition $\partial \int f=f$. This
satisfies the ($n$-ary) Rota-Baxter equations if and only if $\lambda = 1$.
\end{example}
\begin{lemma}[Bouton system in terms of integral rig]\label{lem:BoutonMonoidInducesAIntegralRig} For any monoid $M$, there is a one-to-one correspondence between
\begin{itemize}
\item Bouton system on a monoid $M$ (\cref{def:BoutonSystem}), and
\item An integral operator $\int \colon \Omega[M]\to \Omega[M]$ that factor through $\{\cdot\} \colon M \hookrightarrow \Pf(M)\colon m \mapsto\{m\}$,
\end{itemize}
via the composition
\[
\begin{tikzcd}
\Pf(M)\ar[r, "\mu"] \ar[rr, "\int"', bend right] &M\ar[r,"\{\cdot\}"]& \Pf(M).
\end{tikzcd}
\]
\end{lemma}
\begin{proposition}[Calculus rig of game families (Ryo Suzuki)]\label{prop:IntegralRigOfGameFamilies}
The rig $\H$ (\cref{cor:DifferentialRigOfGameFamilies}) equipped with the integral operator
\[
\int A \coloneqq \{A\}
\]
is an integral rig.
\end{proposition}
\begin{proof}
Since $\int$ factors through $\{\cdot\}\colon \H \to \Pf(\H)$
\[
\begin{tikzcd}
\Pf(\H) \ar[rr,"\int"', bend right]\ar[r, "="]&\H\ar[r,"\{\cdot\}"] &\Pf(\H),
\end{tikzcd}
\]
\cref{lem:BoutonMonoidInducesAIntegralRig} reduces the problem to prove that $\id_{\H}\colon \Pf(\H)= \H \to \H$ is a Bouton system. This is nothing other than the definition of the terminal monoid structure $*\colon \H \times \H\to \H$.
\end{proof}
\begin{proposition}\label{prop:NimSumIsIntegralRig}
For the monoid of Nim-sum $(\N, \nsum)$, the induced rig $\Omega[(\N, \nsum)] \cong \Pf(\N)$ with an integral operation
\[
\int A \coloneqq \{\mex A\}
\]
is an integral rig.
\end{proposition}
\begin{proof}
Since $\int$ factors through $\{\cdot\}\colon \N \to \Pf(\N)$
\[
\begin{tikzcd}
\Pf(\N) \ar[rr,"\int"', bend right]\ar[r, "\mex"]&\N\ar[r,"\{\cdot\}"] &\Pf(\N),
\end{tikzcd}
\]
\cref{lem:BoutonMonoidInducesAIntegralRig} reduces the problem to prove that $\mex\colon \Pf(\N) \to \N$ is a Bouton system. We have
\[
\mex \emptyset = 0,
\]
and
\[
\mex(\{\mex A \nsum b, a \nsum \mex B\mid a\in A, b\in B\} )= \mex A \nsum \mex B.
\]
\end{proof}
\begin{theorem}[Integral rig decategorifies the rig of games]\label{thm:IntegralRigDecategorification}
For an integral rig $A$, and a game $\X$, we recursively define a function $F_{(\X,{-})}\colon X \to A$ by
\[
F_{(\X,x)} \coloneqq \int \left(\sum_{x\to x'}F_{(\X,x')}\right).
\]
For a finite family of games $(\X_i,x_i)_{i \in I}$, where $ |I|<\infty$, we define
\[
F_{(\X_i,x_i)_{i\in I}} \coloneqq \sum_{i \in I} F_{(\X_i,x_i)}.
\]
This satisfies the followings:
\begin{description}
\item[zero] $F_{0} = 0$,
\item[one] $F_1=1$,
\item[addition] $F_{\mathcal{X}+\mathcal{Y}} = F_{\mathcal{X}}+F_{\mathcal{Y}}$,
% $F_{(\X_i,x_i)_{i\in I} + (\Y_j,y_j)_{j\in J}}= F_{(\X_i,x_i)_{i\in I}}+F_{(\Y_j,y_j)_{j\in J}}$
\item[multiplication] $F_{\mathcal{X}\otimes \mathcal{Y}} = F_{\mathcal{X}}F_{\mathcal{Y}}$, and
\end{description}
\end{theorem}
\begin{proof}
The construction in the statement preserves zero and binary addition, by definition.
It preserves $1$, by the nullary Rota-Baxter equation:
\[
F_{1} = F_{(1, \ast)} = \int \sum_{\ast \to x'}F_{(1, x')} = \int 0=1.
\]
Lastly, we prove that it preserves binary products.
% Notice that $F_{(\X,x)}$ is always normal for every game $(\X,x)$, while $F_{(\X_i,x_i)_{i\in I}}$ is not normal in general.
We prove that it preserves binary products by induction:
\begin{align*}
F_{(\X,x)\otimes (\Y,y)} &=\int\left(\sum_{x\to x'}F_{(\X,x')\otimes(\Y,y)}+ \sum_{y\to y'}F_{(\X,x)\otimes(\Y,y')}\right)\\
&=\int\left(\left(\sum_{x\to x'}F_{(\X,x')}\right) \times F_{(\Y,y)}
+
F_{(\X,x)}\times \left(\sum_{y\to y'}F_{(\Y,y')}\right)\right)\\
&=\int\left(\sum_{x\to x'}F_{(\X,x')} \times \int\sum_{y\to y'}F_{(\Y,y')}
+
\int\sum_{x\to x'}F_{(\X,x')}\times \sum_{y\to y'} F_{(\Y,y')}\right)\\
&=\left(\int\sum_{x\to x'}F_{(\X,x')}\right)\left(\int\sum_{y\to y'}F_{(\Y,y')}\right)
\\
&=F_{(\X,x)} \times F_{(\Y,y)}. \\
\end{align*}
This completes the proof.
\end{proof}
\begin{example}
If we apply \Cref{thm:IntegralRigDecategorification} to \cref{prop:NimSumIsIntegralRig}, we obtain the classical Bouton Theorem.
\end{example}
\subsection{Theory of calculus rig}
In this subsection, we aim to provide a way to decategorify the differential structure of $\Fgames$, defining a differential invariant \cref{def:differentialInvariant}. More concretely, we will define the notion of \demph{calculus rig} (\cref{def:CalculusRig}), and prove the followings:
\begin{enumerate}
\item Game families $\H \cong \Pf(\H)$ form a calculus rig. (\cref{thm:RotaBaxterRigOfGameFamilies})
\item Calculus rig $A$ provides a differential invariant.
\end{enumerate}
\begin{definition}\label{def:CalculusRig}
A \demph{calculus rig} is a rig $A$, equipped with
\begin{itemize}
\item a differential operator $\partial\colon A \to A$ (\cref{def:differentialrig}) and
\item an integral operator $\int \colon A \to A$ (\cref{def:IntegralRig}),
\end{itemize} satisfying
\begin{description}
\item[Fundamental theorem of calculus] $\partial \int f= f$.
% \item[Nullary Rota-Baxter equation] $1 = \int 0$
% \item[Binary Rota-Baxter equation] $(\int f)(\int g) = \int(f(\int g) + (\int f) g)$
\end{description}
\end{definition}
% \begin{definition}
% For a differential rig $A$, two elements $f,g$ are \demph{parallel}, written by $f~g$ if $\partial f = \partial g$.
% \end{definition}
% For the differential rig $C^{\infty}(\R)$, two elements $f,g$ are parallel, if and only if $f-g$ is constant.
% \begin{lemma}[Weak Rota-Baxter equation]
% \end{lemma}
\begin{theorem}[Calculus rig of game families (Ryo Suzuki)]\label{thm:RotaBaxterRigOfGameFamilies}
The rig $\H$ with the differential and integral operators (\cref{cor:DifferentialRigOfGameFamilies}\cref{prop:IntegralRigOfGameFamilies}) form a calculus rig.
\end{theorem}
\begin{proof}
\[
\partial \int A = \{a_2\mid a_2 \in a_1 \in \{A\}\} =A,
\]
completes the proof.
\end{proof}
\begin{table}[ht]
\centering
\begin{tabular}{cc}
Analysis& Game family\\ \hline
0& $\{\}$\\ \hline
1& $\{\{\}\}$\\ \hline
$+$& $\cup$\\ \hline
$\times$& $\{a*b\mid a\in A, b\in B\}$\\ \hline
$\partial$& $\partial A = \bigcup_{a\in A} a$\\ \hline
$\int$& $\int A = \{A\}$\\ \hline
\end{tabular}
\caption{List of the correspondence}
\end{table}
Lastly, we will prove that a calculus rig provides a differential invariant.
\begin{theorem}\label{thm:RotaBaxterInducesADifferentialGameInvariant}
For a calculus algebra $A$, and a game $\X$, we recursively define a function $F_{(\X,{-})}\colon X \to A$ by
\[
F_{(\X,x)} \coloneqq \int \left(\sum_{x\to x'}F_{(\X,x')}\right).
\]
For a finite family of games $(\X_i,x_i)_{i \in I}$, where $ |I|<\infty$, we define
\[
F_{(\X_i,x_i)_{i\in I}} \coloneqq \sum_{i \in I} F_{(\X_i,x_i)}.
\]
These data define a differential invariant of games (\cref{def:differentialInvariant}), i.e., we have
\begin{description}
\item[zero] $F_{0} = 0$,
\item[one] $F_1=1$,
\item[addition] $F_{\mathcal{X}+\mathcal{Y}} = F_{\mathcal{X}}F_{\mathcal{Y}}$,
% $F_{(\X_i,x_i)_{i\in I} + (\Y_j,y_j)_{j\in J}}= F_{(\X_i,x_i)_{i\in I}}+F_{(\Y_j,y_j)_{j\in J}}$
\item[multiplication] $F_{\mathcal{X}+\mathcal{Y}} = F_{\mathcal{X}}F_{\mathcal{Y}}$, and
\item[Differential] $F_{\partial \mathcal{X}}= \partial F_{\mathcal{X}}$.
\end{description}
\end{theorem}
% We need a little preparation to prove this theorem. In a calculus rig, $\int \partial a$ is not generally equal to $a$. We will give a name for such elements:
% \begin{definition}
% For a calculus rig $(A,0,1,+,\times,\partial, \int)$, an element $a\in A$ is said to be \demph{normal}, if it satisfies the following equivalent conditions:
% \begin{itemize}
% \item $\int \partial a = a$.
% \item There is an element $b\in A$ such that $a = \int b$.
% \end{itemize}
% \end{definition}
% \begin{lemma}\label{lem:ClosednessOfNormalElements}
% In a calculus rig $A$, every finite product of normal elements is again normal, i.e.,
% \begin{itemize}
% \item $1$ is normal.
% \item If $a$ and $b$ are normal, then $ab$ is normal.
% \end{itemize}
% \end{lemma}
% \begin{proof}
% This immediately follows from the $n$-ary Rota-Baxter equation.
% \end{proof}
\begin{proof}
% [Proof of \cref{thm:RotaBaxterInducesADifferentialGameInvariant}]
% The construction in \cref{thm:RotaBaxterInducesADifferentialGameInvariant} preserves zero and binary addition, by definition.
It preserves the derivative, due to the
\[
\partial F_{(\X,x)} = \partial \int \sum_{x\to x'}F_{(\X,x')} = \sum_{x\to x'}F_{(\X,x')} = F_{\partial(\X,x)}
\]
and the lineality of $\partial$.
% It preserves $1$, by the nullary Rota-Baxter equation:
% \[
% F_{1} = F_{(1, \ast)} = \int \sum_{\ast \to x'}F_{(1, x')} = \int 0=1.
% \]
% Lastly, we prove that it preserves binary products. Notice that $F_{(\X,x)}$ is always normal for every game $(\X,x)$, while $F_{(\X_i,x_i)_{i\in I}}$ is not normal in general.
% We prove that it preserves binary products by induction:
% \begin{align*}
% F_{(\X,x)\otimes (\Y,y)} &=\int\left(\sum_{x\to x'}F_{(\X,x')\otimes(\Y,y)}+ \sum_{y\to y'}F_{(\X,x)\otimes(\Y,y')}\right)\\
% &=\int\left(\left(\sum_{x\to x'}F_{(\X,x')}\right) \times F_{(\Y,y)}
% +
% F_{(\X,x)}\times \left(\sum_{y\to y'}F_{(\Y,y')}\right)\right)\\
% &=\int\left(\partial F_{(\X,x)} \times F_{(\Y,y)}
% +
% F_{(\X,x)}\times \partial F_{(\Y,y)}\right)\\
% &=\int \partial \left(F_{(\X,x)} \times F_{(\Y,y)}\right)\\
% &=F_{(\X,x)} \times F_{(\Y,y)}\\
% \end{align*}
% The last equation follows since $F_{(\X,x)} \times F_{(\Y,y)}$ is normal due to \cref{lem:ClosednessOfNormalElements}.
\end{proof}
\horamemo{Relationship with Bouton system}
\horamemo{We can categorify the integral operator. Does it satisfy the categorified Rota-Baxter equation? Possibly No. (Count the number of elements}
\begin{proposition}\label{prop:MexDoesNotHaveDifferential}
The integral rig $\Pf(\N)$ and $\int A = \{\mex A\}$ (\cref{prop:NimSumIsIntegralRig}) does not have calculus rig structure.
\end{proposition}
\begin{proof}
The integral operator of a calculus rig is injective since $\partial \int = \id$. However, $\int\{\} =\int \{1\} =\{0\}$ proves that $\int$ is not injective for $\Pf(\N)$.
\end{proof}
\subsection{Generating Polynomial}\horamemo{ToBeRemoved}
\begin{definition}[A generating function]\label{def:RealValuedGeneratingFunctions} \horamemo{modified}
Here, we can define a notion of \demph{real-valued generating function}. For an object $(\X, x)$ in $\Fgames$, let $g_{(\X, x)}(z)$ be the polynomial
\[
g_{(\X, x)}(z) = \sum_{n=0}^{\infty} p_n \frac{z^n}{n!},
\]
where $p_n$ denotes the number of \dq{plays of length $n$}
\[
p_n \coloneqq \#\{ (x_1, \dots, x_n) \in X^n\mid x\to x_1 \to \dots \to x_n\}.
\]
\end{definition}
\begin{proposition}\horamemo{modified}
We can extend this to a finite family of games in $\Fgames$, and we can prove that generating functions respect sum, multiplication, and derivative of games.
\end{proposition}
\begin{proof}
This is a special case of \cref{thm:RotaBaxterInducesADifferentialGameInvariant} for differential rig $C^{\infty}(\R)$ with
\[
\int \colon f(x) \mapsto 1+ \int_{0}^x f(t)dt
\]
\end{proof}
\begin{remark}[This is not informative]\horamemo{To be modified}
This is not very useful for studying game-winning strategy since $N, P$-games might share the generating function. For example, there are two games with the generating function \horamemo{wrong$\frac{x^3}{6} + x^2$,} one of which is $N$-game and the other is $P$-game.
\end{remark}
\begin{remark}\horamemo{To be modified}
Even for a non-pointed game $\X$, we can consider the generating function. Let $R$ be the right adjoint to the forgetful functor
\[
U \colon \Fgames\to \Gs \colon (\X_i,x_i)_{i \in I} \mapsto \coprod_{i\in I} \X_i.
\]
More explicitly, it is calculated by $R\X = (\X,x)_{x\in X}$.
We define $g_{\X}$ to be the (possibly non-convergent) generating function $g_{R\X}$. For example, let $S\in \Pf(\N\setminus \{0\})$ and $\X_S$ be the subtraction Nim (i.e., $n\to m$ iff $n-m\in S$). Its generating function is $e^{|S|z}$.
\end{remark}
\horamemo{similar, but essentially different function described \href{https://golem.ph.utexas.edu/category/2006/10/classical_vs_quantum_computati_3.html}{[here]} has the data of $N,P$.}
\subsection{Towrds the maximally informative invariant}
Both $C^\infty(\R)$ and $\H$ provide a calculus rig and, therefore, induce a differential invariant of games. $C^{\infty}(\R)$ has enumerative information, and $\H$ has game-theoretic information (like $P/N$ states). However, there is the maximally informative calculus rig: \demph{initial calculus rig}.
\begin{question}
What is the initial calculus rig?
\end{question}
\cite{ebrahimi2008free} describes the Rota-Baxter algebra of trees, which should be strongly related.
\horamemo{Possibly, the category of finite families of (one-element generated) games is equivalent to the free Rota-Baxter category...?}
\horamemo{For an algebraic theory (like semilattice, $\mathbb{F}_2$-vector spaces, and commutative monoids), let $T$ be the free algebra monad. The initial $T$-algebra, where $T$ is regarded as just an endofunctor, seems strongly related to game theory. It might be the semilattice of hereditarily finite sets, $\mathbb{F_2}$-vector space of Nim-sum, and the initial ROta-Baxter rig. }
\section{Bouton System}
\suzukimemo{To understand the Grundy number, it might be worth considering some monoidal structure on $\PfAlg$. (or Bouton monoid can be used to understand?) It seems to be worth considering that "Bouton system", which is defined below. }
\begin{definition}[Ryo Suzuki]\label{def:BoutonSystem}
A tuple $(A,\mu \colon \Pf A\to A, e\in A, *\colon A\times A\to A$ is called \demph{Bouton system} when
\begin{enumerate}
\item $(A,\mu)$ is a $\Pf$-algebra,
\item $(A,e,*)$ is a commutative monoid,
\item $\mu(\varnothing)=e$, and
\item For every $S,T \in \Pf A$,
$\mu(\{\mu(S)*t, s*\mu(t)\mid s\in S, t\in T\})
= \mu(S)*\mu(T)$.
\end{enumerate}
A morphism of Bouton systems $A,B$ is a morphism of $\Pf$-algebra which preserves the monoid structure of $A$.
We denote the category of Bouton systems by $\BS$
\end{definition}
For example, the terminal game, $(\N,\mex)$, and $(\N,\xem)$ can be
regarded as a Bouton system. \horamemo{how about \demph{remoteness}? Possibly it fails. How about "inverse quotient" for misere game?}On the other hand, although ${P,N}$ has
a $\Pf$-algebra structure and a commutative monoid structure,
it is not a Bouton system.
\suzukimemo{Can Bouton systems be regarded as monoid objects of $\PfAlg$ for certain monoidal structure? }
\begin{remark}[Bouton system in terms of calculus rig (without differentiation)] For any monoid $M$, we obtain a rig $\Omega[M]\cong \Pf(M)$. For a general rig, an \demph{integral operator} $\int \colon A \to A$ is a function that satisfies
\begin{description}
\item[Nullary Rota-Baxter equation] $1 = \int 0$
\item[Binary Rota-Baxter equation] $(\int f)(\int g) = \int(f(\int g) + (\int f) g)$
\end{description}
(See also \cref{def:CalculusRig}).
% For a (possibly non-commutative) monoid $M$, a function $\mu\colon \Pf(M) \to M$ is Bouton system, if and only if
% \[
% \begin{tikzcd}
% \Pf(M) \ar[r,"\mu"]&M \ar[r, ""]&\Pf(M)
% \end{tikzcd}
% \]
There is a one-to-one correspondence between
\begin{itemize}
\item Bouton system structure on a monoid $M$, and
\item An integral operator $\int \colon \Omega[M]\to \Omega[M]$ that factor through $\{\cdot\} \colon M \hookrightarrow \Pf(M)\colon m \mapsto\{m\}$,
\end{itemize}
via the composition
\[
\begin{tikzcd}
\Pf(M)\ar[r, "\mu"] \ar[rr, "\int"', bend right] &M\ar[r,"\{\cdot\}"]& \Pf(M).
\end{tikzcd}
\]
\end{remark}
\begin{remark}[Monoid structure w.r.t. the categorical product]
A monoid structure $\ast \colon A\times A \to A$ on a $\Pf$-algebra $\mu \colon \Pf (A) \to A$ is a monoid in the cartesian category $\PfAlg$, if and only if
\[
\mu(x_i)_{i\in I} \ast \mu (y_i)_{i\in I} = \mu(x_i \ast y_i)_{i \in I}
\]
holds for any finite set $I$ and a function $I \to A^2$. This is NOT Bouton system. For example, $(\N, \mex)$ does not satisfy this equation. (If $I$ is not empty and $x_i=y_i$, then the left-hand side is $0$, but the right-hand side is $1$.)
\end{remark}
\begin{proposition}[Ryo Suzuki]
Let $A$ be a $\Pf$-algebra.
Then the Bouton monoid $\B_{\otimes, A}$ has
a natural $\Pf$-algebra structure,
and become a Bouton system.
\end{proposition}
\begin{proof}
Let $B=\B_{\otimes,A}$. To induce a $\Pf$-algebra structure on $B$,
it suffice to show that,
if $S,T\in \Pf(\H)$ has a same image in $B$,
then $S,T\in \H$ has also a same image in $B$.
This is verified inductively as follows:
For any $U\in\H$,
\begin{align}
S*U &= \{s*U, S*u\mid s\in S, u\in U\}\\
&= \{t*U, T*u\mid t\in T, u\in U\}\\
&= T*U.
\end{align}
It immediately follows $B$ is a Bouton system.
\end{proof}
\suzukimemo{This proof is not well-written.
Someday I must rewrite this. }
\suzukimemo{I think this proposition can be generalized as follows: Let $X$ be a Bouton system ,$A$ a $\Pf$-algebra, and $X\to A$ be a $\Pf$-algebra map. Then the minimal quotient monoid of $X$ of $X\to A$ has a natural Bouton system structure. I also believe for any $\Pf$-algebra there exists a surjection from some Bouton system. I think these can be used to construct the right adjoint $R$ of the forgetful functor $F$ from the category of Bouton system to $\PfAlg$. }
\suzukimemo{Since $F$ commute with limits, there probably exists the left adjoint $L$ of the forgetful functor. These could be used to calculate the underlying set of (conjectual) $R(A)$. }
We construct the left adjoint of the forgetful functor
$F\colon \BS \to \PfAlg$.
\begin{proposition}[Ryo Suzuki]
\begin{enumerate}
\item For any diagram $I:J\to \PfAlg$, the limit of $I$ exists, and it is preserved by the forgetful functor $\PfAlg\to \Set$
\item For any diagram $I:J\to \BS$, the limit of $I$ exists,
and it is preserved by the forgetful functor
$F\colon \BS\to \PfAlg$.
\end{enumerate}
\end{proposition}
\begin{proof}
\suzukimemo{todo!}
\end{proof}
\begin{proposition}[Ryo Suzuki]
\begin{enumerate}
\item The forgetful functor $\PfAlg\to \Set$ has a left adjoint.
\item For any morphism $f:A\to A'$ of $\Pf$-algebras, $f(A)$ also has a
natural $\Pf$-algebra structure.
\end{enumerate}
Hence for any $\Pf$-algebra $A$ and a subset $S\subseteq A$, there exists the smallest $\Pf$-subalgebra of $A$ that contains $S$.
\end{proposition}
\begin{proof}
\suzukimemo{todo!}
\end{proof}
\begin{proposition}[Ryo Suzuki]
Let $A$ be a $\Pf$-algebra, $B$ a Bouton system,
$f\colon A\to B$ a morphism of $\Pf$-algebra.
Then there exists a Bouton system $B'$ of cardinality
$\max\{\#A,\omega\}$ such that $f$ factors through $B'$.
Hence solution set condition satisfied,
and the left adjoint of $F:\BS\to \PfAlg$ exists.
\end{proposition}
\begin{proof}
Let $B'_{i,0}$ be $f(A)\subset B$.
We inductively define $B_{i,{n+1}}$ be a $\Pf$-subalgebra of $B$ which is generated by $\{x*y\mid x,y\in B_{i,n}\}$.
We note that $B_{i,n}\subset B_{i,n+1}$.
Then $\bigcup_{n\in \N} B_{i,n}$ satisfies the requirement.
\end{proof}
\suzukimemo{Can we construct free Bouton systems explicitly (say, for one point set)?}
\section{Another presentation of the category of games}
Let $C$ be a category and let $T\colon C\to C$ be a monad.
Let $(X, X\to TX)$ be a $T$-coalgebra. Then we have a map $\partial = \mu_X\circ Tf:TX\to TX$. This is an endomorphism of the $T$-algebra $(TX,\mu_X:T^2X\to TX)$, here we regard $T$ as an endofunctor.
\[
\begin{tikzcd}
TTX\ar[d,"\mu_X"]\ar[r,"T \theta"]&TTTX\ar[r,"T \mu_X"]\ar[d, "\mu_{TX}"]&TTX\ar[d,"\mu"]\\
TX\ar[r,"\theta"]&TTX\ar[r,"\mu_X"]&TX
\end{tikzcd}
\]
Conversely, if we have a endomophism $\partial$ of the $T$-algebra
$(TX,\mu:T^2X\to TX)$, then we have a coalgebra $(X,\partial\circ \eta_X:X\to TX)$. This correspondence is one-to-one.
\suzukimemo{Does this reinterpretation help to understand the tensor product of games?}
\horamemo{Since $(TX, \mu_X)$ is the free $T$-algebra, we have $\Alg{T}(TX,TX) \cong \C(X, TX)$. I did not notice this!}
For the rig $\Omega$, we can consider the monoidal structure of the category of $\Omega$-modules. This tensor product carries $\Pf(X)$ and $\Pf(Y)$ to $\Pf(X\times Y)$.
Let $\Omega[\partial]$ be the polynomial rig of one variable $\partial$. For a game $\X$, we regard $\Pf(X)$ as a $\Omega[\partial]$-module.
The rig $\Omega[\partial]$ has a coaddition $\Delta^+:\Omega[\partial]\to \Omega[\partial]\otimes_\Omega \Omega[\partial]$, which sends $\partial$ to $\partial\otimes 1+1\otimes \partial$. Using this, we can regard $\Pf(X)\otimes_\Omega \Pf(Y) = \Pf(X\times Y)$ as $\Omega[\partial]$-module, and this is the $\Omega[\partial]$-module corresponding $\X\otimes \Y$.
\suzukimemo{How can we understand the relations between games and $\Pf$-algebras? Is there a categorified version of $\Omega[\partial]? $}
\horamemo{Can we rephrase `being games', (not only `being coalgebras')?}
\section{Related works}
\begin{description}
\item[1901] Bouton proved the famous winning strategy of Nim with \demph{Nim-sum} \cite{bouton1901nim}.
\item[1935, 1939] Sprague and Grundy independently find what's now called the Sprague-Grundy theorem. \cite{sprague1935mathematische} \cite{grundy1939mathematics}
\end{description}
\begin{description}
\item[1977] Joyal defined the compact closed category of combinatorial games. \cite{joyal1977remarques}
\item[1981] Joyal founds the category of species is the categorification of \dq{exponential generating functions} \cite{joyal1981theorie}
\item[1992]founds the game semantics. \cite{blass1992game}
\item[2006] Blute, Cockett, and Seely defined differential categories. \cite{blute2006differential}
\item[2009] \demph{Rota-Baxter categories} are defined in \cite{castillo2009rota}.
\item[2013] As far as I know, the first paper that deals with \dq{differential category of games} is \cite{laird2013constructing}.
\item[2021] Differential 2-rigs are defined \cite{loregian2021differential}
\item[2025] Hora will write a paper on a new category of games.
\end{description}
\printbibliography
\end{document}