\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_*)} \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{Categorical differential operator} \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 rig and differential invariant of games} \begin{definition} A \demph{differential rig} is a (possibly non-commutative) rig (= semiring) $(A, 0,1, +, \times)$ equipped with a unary operation $ \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{Theory of Rota-Baxter 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{Rota-Baxter rig} (\cref{def:Rota-BaxterRig}), and prove the followings: \begin{enumerate} \item Game families $\H \cong \Pf(\H)$ form a Rota-Baxter rig. (\cref{thm:RotaBaxterRigOfGameFamilies}) \item Rota-Baxter rig $A$ provides a differential invariant. \end{enumerate} \begin{definition}\label{def:Rota-BaxterRig} A \demph{Rota-Baxter rig} is a differential rig $A$, equipped with an \demph{integral operator} $\int$, that is, a function $\int \colon A \to A$ 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{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 any $\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{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}[Rota-Baxter rig of game families (Ryo Suzuki)]\label{thm:RotaBaxterRigOfGameFamilies} The differential rig $\H$ (\cref{cor:DifferentialRigOfGameFamilies}) equipped with the integral operator \[ \int A \coloneqq \{A\} \] is a Rota-Baxter rig. \end{theorem} \begin{proof} The first two equalities are easily proven as \[ \partial \int A = \{a_2\mid a_2 \in a_1 \in \{A\}\} =A, \] and \[ \int 0 = \{0\} = 1. \] For the last equality, we have \begin{align*} \int A \times \int B &=\{A\ast B\}\\ &=\{\{a\ast B \mid a\in A\}\cup \{A\ast b\mid b\in B\}\}\\ &=\{A\times \{B\}\cup \{A\}\times B\}\\ &=\int\left(A\times \int B + \int A \times B\right) \end{align*} This 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 Rota-Baxter rig provides a differential invariant. \begin{theorem}\label{thm:RotaBaxterInducesADifferentialGameInvariant} For a Rota-Baxter 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 Rota-Baxter rig, $\int \partial a$ is not generally equal to $a$. We will give a name for such elements: \begin{definition} For a Rota-Baxter 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 Rota-Baxter 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} \subsection{Generating Polynomial} \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 Rota-Baxter 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 Rota-Baxter rig: \demph{initial Rota-Baxter rig}. \begin{question} What is the initial Rota-Baxter rig? \end{question} \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] 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} \end{definition} For example, the terminal game and $(\N,\mex)$ can be regarded as a Bouton system. 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 Rota-Baxter 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:Rota-BaxterRig}). % 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{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)$. } \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!} \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}