← rota-baxter-winning-games
DiffCatRIMS__Older__20260403.tex
\documentclass[12pt,portrait,aspectratio=169]{beamer}
\usepackage[T1]{fontenc}
% \usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb,mathtools}
\usepackage{pifont}
\usepackage{xcolor}
\usepackage[style=authoryear,maxnames=3]{biblatex}
\addbibresource{Horabiblio.bib}
\usetikzlibrary{calc,positioning,arrows.meta,fit,decorations.pathreplacing,backgrounds,shapes.geometric}
% ---- macros adapted from the provided tex sources ----
\newtheorem{proposition}{Proposition}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{{\color{red} #1}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\X}{\mathbb{X}}
\newcommand{\Y}{\mathbb{Y}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\gS}{\mathbb{S}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\Gs}{\mathbf{Game}}
\newcommand{\Gsp}{\mathbf{Game}_{*}}
\newcommand{\Pf}{\mathcal{P}_{\mathrm{fin}}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\Hf}{\mathbb{H}}
\newcommand{\oc}{\mathsf{Outcome}}
% \newcommand{\G}{\mathsf{Grundy}}
\newcommand{\G}[2]{\mathcal{G}_{#1}(#2)}
\newcommand{\BirthDay}{\mathsf{BirthDay}}
\newcommand{\mex}{\mathsf{mex}}
\newcommand{\xem}{\mathsf{xem}}
\newcommand{\hylo}{\mathsf{hylo}}
\newcommand{\np}{\mathsf{np}}
\newcommand{\thetaf}{\theta}
\newcommand{\Fam}{\mathsf{Fam}}
\newcommand{\dd}{\partial}
\newcommand{\Int}{\intop}
\newcommand{\emptygame}{\mathsf{1}}
\newcommand{\nimsum}{\oplus}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\Alg}[1]{\mathrm{Alg}_{#1}}
\newcommand{\Coalg}[1]{\mathrm{Coalg}_{#1}}
\newcommand{\PfAlg}{\Alg{\Pf}}
\newcommand{\PfCoalg}{\Coalg{\Pf}}
\newcommand{\m}{\mathrm{mex}}
\renewcommand{\O}[2]{\mathcal{O}_{#1}(#2)}
\newcommand{\B}[2]{\mathcal{B}_{#1}(#2)}
\newcommand{\M}[2]{\mathcal{B}_{#1,#2}}
\renewcommand{\H}[3]{\mathcal{H}_{#1,#2,#3}}
\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}}
\newcommand{\Her}{\mathbb{H}}
\newcommand{\epi}{twoheadrightarrow}
\newcommand{\mono}{rightarrowtail}
\newcommand{\h}{\mathrm{h}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\ADJ}[4]
{
\begin{tikzcd}[ampersand replacement = \&, column sep = small]
{#1}
\ar[rr, shift right=1.3ex, "{#2}"']
\&\perp\&
{#3}
\ar[ll, shift right=1.3ex,"{#4}"']
\end{tikzcd}
}
\DeclarePairedDelimiter{\gen}{\langle}{\rangle}
% ---- beamer style from uploaded template ----
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{items}[default]
\setbeamertemplate{theorems}[default]
\setbeamertemplate{blocks}[rounded][shadow=false]
\setbeamertemplate{footline}[frame number]
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
% ---- colors ----
\definecolor{myblue}{RGB}{48,73,180}
\definecolor{mygreen}{RGB}{40,135,65}
\definecolor{myred}{RGB}{200,70,62}
\definecolor{myorange}{RGB}{224,146,40}
\definecolor{mypurple}{RGB}{134,88,190}
\definecolor{myteal}{RGB}{30,140,150}
\definecolor{mycream}{RGB}{250,247,238}
\definecolor{mylightblue}{RGB}{228,236,251}
\definecolor{mylightgreen}{RGB}{231,246,233}
\definecolor{mylightred}{RGB}{252,236,235}
% ---- tikz styles ----
\tikzset{
>={Latex[length=2.3mm]},
gameedge/.style={->, draw=black!70, line width=0.65pt},
heapedge/.style={->, draw=black!65, line width=0.85pt},
nimheap/.style={draw=black!70, line width=0.9pt, fill=white},
panel/.style={rounded corners=5pt, draw=black!10, fill=mycream, inner sep=5pt},
nstate/.style={circle, fill=myred, inner sep=2.2pt},
pstate/.style={circle, fill=myblue, inner sep=2.2pt},
neutralstate/.style={circle, fill=black, inner sep=2.0pt},
familybox/.style={rounded corners=4pt, draw=myblue!50!black, fill=mylightblue, line width=0.8pt},
formulaarrow/.style={->, draw=myblue!85!black, line width=1pt},
goodring/.style={draw=myblue, line width=1.5pt, rounded corners=3pt},
badring/.style={draw=myred, line width=1.5pt, rounded corners=3pt},
note/.style={rounded corners=4pt, fill=yellow!12, draw=yellow!30!black, inner sep=4pt}
}
% ---- title ----
\title[A Rota--Baxter equation for winning games]{A Rota--Baxter Equation for Winning Games}
\subtitle{Games as recursive coalgebras and differential invariants}
\author{Ryuya Hora}
\institute{Assistant professor at ZEN university}
\date{Differentiation in category theory and program semantics\\Kyoto University, April 6, 2026}
\begin{document}
\begin{frame}
\titlepage
\vspace{-0.5em}
\begin{center}
\small Partially Based on joint work in progress with Ryo Suzuki.
\end{center}
\end{frame}
\begin{frame}{Where I come from}
\Large
% {\Huge \textbf{Ryuya Hora}}\\
I've been interested in toposes, \textbf{games, and coalgebras}.\\
% Sorry for my poor English!
\begin{figure}
\centering
\includegraphics[width=1.1 \textwidth]{images/Recursion.png}
\caption{When I tried to check the spelling of “recursion”}
\end{figure}
\end{frame}
\begin{frame}{Where this talk comes from}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.57\textwidth}
\begin{itemize}
\item My motivation comes from \textbf{Combinatorial Game Theory}
% ,
% especially impartial games such as Nim.
% \\
% {\small I am an organizer of \textbf{Japan Combinatorial Game Theory Workshop}.}
% \item So I am coming to this workshop mainly \textbf{from the game side}.
\item I am \textbf{not} a specialist in differential categories in the usual sense.
\end{itemize}
\end{column}
\begin{column}{0.39\textwidth}
\begin{block}{What I hope to learn here}
\begin{itemize}
\item the right map of prior work
\item links to differential / Cartesian differential categories
\item links to game semantics and linear logic
\item where the Rota--Baxter viewpoint fits
\end{itemize}
\end{block}
\end{column}
\end{columns}
\vspace{0.4em}
\begin{center}
\emph{So this talk is partly a mathematical proposal.}
\end{center}
\end{frame}
% \begin{frame}{This Talk in One Slide}
% \begin{block}{Guiding question}
% Why does the winning theory of \emph{Nim} involve the strange operation
% \[
% a_1\nimsum \cdots \nimsum a_n \, ?
% \]
% \end{block}
% \vspace{0.3em}
% \begin{columns}[T]
% \begin{column}{0.48\textwidth}
% \textbf{Part I (about 10 min)}
% \begin{itemize}
% \item Games as $\Pf$-recursive coalgebras
% \item game values as hylomorphisms
% \end{itemize}
% \end{column}
% \begin{column}{0.48\textwidth}
% \textbf{Part II (about 15 min)}
% \begin{itemize}
% \item a "differential structure" on pointed games families
% % \item Rota--Baxter rig valued invariants
% \item\textbf{Winning nim with a Rota-Baxter equation!}
% \end{itemize}
% \end{column}
% \end{columns}
% \vspace{0.3em}
% \begin{center}
% \emph{Key slogan: the Nim identity is an integral shadow of a Leibniz rule.}
% \end{center}
% \end{frame}
\begin{frame}{Short survey: games $\times$ category theory is not new\memo{memo}}
\footnotesize
\begin{alertblock}{Important positioning}
I know that \textbf{games + category theory} is already a rich story.
This talk isolates the narrower interface between
\[
\text{impartial combinatorial games}
\qquad\text{and}\qquad
\text{differential / Rota--Baxter ideas}.
\]
\end{alertblock}
\vspace{0.2em}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.32\textwidth}
\begin{exampleblock}{Game semantics}
\begin{itemize}
\item strategies as morphisms
\item linear logic / programming semantics
\end{itemize}
\end{exampleblock}
\end{column}
\begin{column}{0.32\textwidth}
\begin{exampleblock}{Coalgebraic games}
\begin{itemize}
\item Conway games / hypergames
\item recursive viewpoints on impartial games
\end{itemize}
\end{exampleblock}
\end{column}
\begin{column}{0.32\textwidth}
\begin{exampleblock}{Differential side}
\begin{itemize}
\item differential categories
\item integral / calculus categories
\end{itemize}
\end{exampleblock}
\end{column}
\end{columns}
\vspace{0.1em}
{\scriptsize Representative references: game semantics \parencite{joyal1977remarques,laird2013constructing}; coalgebraic games \parencite{honsell2009conway,honsell2011conway,bavsic2024categories}; differential side \parencite{blute2006differential,cockett2019integral,loregian2021differential}.}
\vspace{0.12em}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=7.45cm, minimum height=0.90cm] (p) {};
\node[text=myred, font=\bfseries] at ($(p.center)+(-2.0,0)$) {Nim};
\node[text=mypurple, font=\bfseries] at ($(p.center)+(-0.35,0)$) {recursive coalgebras};
\node[text=myteal, font=\bfseries] at ($(p.center)+(2.30,0)$) {Rota--Baxter};
\draw[formulaarrow] ($(p.center)+(-1.55,0)$) -- ($(p.center)+(-0.83,0)$);
\draw[formulaarrow] ($(p.center)+(0.63,0)$) -- ($(p.center)+(1.66,0)$);
\end{tikzpicture}
\end{center}
\end{frame}
\section{Games: Nim and Integration}
\begin{frame}{Rule of $n$-heap Nim}
\begin{itemize}
% \item In the game \textbf{$n$-heap nim}, first,
\item $n$ heaps of stones are given.
\item Two players take turns choosing one heap and removing at least one stone from that heap.
\item The player who is unable to take a stone loses.
\end{itemize}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/NimSample.jpeg}
\end{figure}
% \memo{write}
\end{frame}
\begin{frame}{Bouton's theorem}
\begin{definition}[Nim-sum]
The \emph{Nim-sum} $\nimsum$ is \dq{bit-wise xor}, i.e., an abelian group structure on $\N$, induced by the binary expansion $\N \overset{\simeq}{\to} \bigoplus_{k=0}^{\infty} \Z/2\Z$.
\end{definition}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.58\textwidth}
\begin{example}
$5\nimsum 7 = (101)_2 \nimsum (111)_2 = (010)_2 = 2$
\end{example}
\end{column}
\begin{column}{0.38\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[thick,>=Latex,scale=0.85]
\node at (-1.0,0.65) {$3=$};
\node at (-0.2,0.65) {$0$};
\node at ( 0.4,0.65) {$1$};
\node at ( 1.0,0.65) {$1$};
\node at (-1.25,0.0) {$\nimsum$};
\node at (-1.0,-0.65) {$5=$};
\node at (-0.2,-0.65) {$1$};
\node at ( 0.4,-0.65) {$0$};
\node at ( 1.0,-0.65) {$1$};
\draw[very thick] (-1.2,-1.05) -- (1.3,-1.05);
\node at (-1.0,-1.7) {$6=$};
\node at (-0.2,-1.7) {$1$};
\node at ( 0.4,-1.7) {$1$};
\node at ( 1.0,-1.7) {$0$};
\end{tikzpicture}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Bouton's theorem}
\begin{theorem}[{[Bouton, Ann. of Math., 1902]}]
A state of $n$-heap nim $(a_1, \dots ,a_n)$ is a winning state
% \footnote{It is usually called a P-state.}
if and only if $a_1 \nimsum \dots \nimsum a_n =0$.
\end{theorem}
\begin{example}
$(1,2,3),(0,1,1), (2,2,0)$ are winning states of the $3$-heap nim.\memo{}
\end{example}
% \begin{block}{My answer today}
% First isolate the \emph{recursive} nature of games, then reinterpret the key Nim identity as a \emph{Rota--Baxter equation}.
% \end{block}
\begin{proof}[The only non-trivial part of the proof is:]
$
\mex(S)\nimsum \mex(T)
= \mex\bigl((\mex(S)\nimsum T)\cup (S\nimsum \mex(T))\bigr).
$
\end{proof}
This is similar to the Rota-Baxter equation.
\[
\left(\Int f\right)\left(\Int g\right )= \Int\left(\left(\Int f\right )g + f\left(\Int g\right )\right ).
\]
\end{frame}
\section{Category of games}
\begin{frame}{Definition of games}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}[Game]
A \emph{game} $\X=(X,\to)$ is a pair of a (possibly infinite) set $X$ and a binary relation $\to \subset X \times X$ that satisfies the following two finiteness conditions
\begin{enumerate}
\item (finite options) $\# \{x' \in X \mid x\rel x'\}$ is finite, for any $x \in X$.
\item (finite time) There is no infinite path. $x_0 \rel x_1 \rel x_2 \rel \dots$
\end{enumerate}
\end{definition}
% \begin{example}
% \begin{itemize}
% \item \cmark 21-game $(\{0,1, \dots 21\}, x\to x' \colon \iff x'-x \in \{1,2,3\})$
% \item \cmark $(\N,>)$ but \xmark $(\Z, >)$
% \item \cmark Nim (Stone-taking game) $(\N^n,\to)$
% \end{itemize}
% \end{example}
\begin{example}[$\Nim{n}$: $n$-heap nim]
The game $\Nim{n} = (\N^{n},\to)$ is
% a game whose underlying set is $\N^{n}$ and relation $\to \subset \N^{n} \times \N^{n}$ is
defined by
\[
(a_i)_{1\leq i \leq n} \to (b_i)_{1\leq i \leq n} \iff
\exists i (a_i> b_i \land a_j = b_j (j\neq i))
\]
\end{example}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/JPEG image-4B87-BA53-02-0.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Conway addition of games}
\begin{columns}
\begin{column}{0.8\textwidth}
\begin{definition}[Conway addition]
The Conway addition of two games, $\X= (X,\to_X)$ and $ \Y =(Y,\to_Y)$, is the game $\X+\Y = (X\times Y, \to_{+})$, where
\begin{itemize}
\item the underlying set is the cartesian product $X\times Y$, and
\item the relation $\to_{+}$ is defined by
$
(x,y)\to_{+} (x', y') \iff (x\to_{X} x' \land y= y') \lor (x= x' \land y\to_{Y} y')
$
\end{itemize}
\end{definition}
\begin{example}
$\Nim{n} = \Nim{1} + \dots + \Nim{1}$
\end{example}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/Conway-addition.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Generalized Bouton's theorem}
\begin{theorem}[{Generalized Bouton's theorem [see CGT, Siegel]}]
For two games $\X =(X, \to_X)$ and $\Y=(Y, \to_Y)$,
we have
\[
\G{\X+\Y}{x,y} = \G{\X}{x} \nimsum \G{\Y}{y}.
\]
\end{theorem}
\begin{example}[Original Bouton's theorem]
\begin{enumerate}
\item $\G{\Nim{1}}{a}=a$
\item $\G{\Nim{n}}{(a_i)_{1\leq i \leq n}} = \G{\Nim{1}}{a_1}\nimsum \dots \nimsum \G{\Nim{1}}{a_n} = a_1 \nimsum \dots \nimsum a_n$
\item $(a_i)_{1\leq i \leq n}$ is a winning state $\iff$ $ a_1 \nimsum \dots \nimsum a_n=0$
\end{enumerate}
\end{example}
Generalized Bouton's theorem allows us to decompose a game into smaller parts!\\
\pause
(And the game $\Nim{n}$ is not the essense of the nim-sum!)
\end{frame}
\begin{frame}{What is a morphism of games?: Historical Remarks}
Historically, morphisms of games have been (relative) \emph{strategies}:
\begin{itemize}
\item A. Joyal, Remarques sur la théorie des jeux à deux personnes, 1977
\item M. Hyland, Game semantics, 1997
\item J.Baez, Classical vs Quantum Computation (Week 3) (The n-Category Caf\'{e}), 2006.
\end{itemize}
However, we will adopt a more classical category-theoretic approach, which is to define a morphism as a \dq{structure-preserving function}.
\end{frame}
\begin{frame}{What is a morphism of games?: Our definition}
\begin{definition}[Game morphisms]
A \emph{game morphism} $f\colon (X,\to_{X})\to(Y,\to_{Y})$ is a function $f\colon X \to Y$ that satisfies the following two conditions:
\begin{enumerate}
\item (Graph map) if $x\to_{X} x'$ then $f(x) \to_{Y} f(x')$.
\item (Lifting property) if $f(x) \to_{X} y$, then there exists $x\to_{X} x'$ such that $f(x') = y$.
\end{enumerate}
\end{definition}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/GameMorphismsCorrected.jpeg}
\end{figure}
\end{frame}
\begin{frame}{Categorical structure of games}
The category of games $\Gs$ has good categorical properties, including:
\begin{proposition}[$\Gs$ is LFP.]
The category of games $\Gs$ is locally finitely presentable. In particular, it is complete and cocomplete.
\end{proposition}
% \memo{Terminal, subobject classifier}
Colimits are created by $U\colon \Gs \to \Set$, but limits are non-trivial!
\begin{example}[The terminal game: $T=(V_\omega, \ni)$]
The terminal game $T=(\N, \to_{\text{bin}})
% (\cong(V_\omega, \ni))
$ is the \emph{binary nim}.
% whose underlying set is $\N$ and
For $n,m\in \N$, $n\to_{\text{bin}}m$, if $m$ appears in the binary expansion of $n$. For example,
\[
10000=2^{4}+2^{8}+2^{9}+2^{10}+2^{13}\to_{\text{bin}} 4,8,9,10,13.
\]
\end{example}
\end{frame}
\section{Games as recursive coalgebras}
\begin{frame}{Algebra/Coalgebra of an endofunctor}
\begin{definition}[$T$-Algebras and $T$-Coalgebras]
For a category $\C$ and an endofunctor $T\colon \C \to \C$,
\begin{itemize}
\item A $T$-algebra is a pair $(A,\alpha)$ of an object $A$ of $\C$ and a morphism $\alpha\colon TA \to A$.
\item A $T$-coalgebra is a pair $(X,\theta)$ of an object $X$ of $\C$ and a morphism $\theta\colon X \to TX$.
\end{itemize}
\end{definition}
\begin{example}
We will consider the case where $\C=\Set$ and $T= \Pf\colon \Set \to \Set$.
\[
\Pf(X)=\{S\subset X\mid \# S <\infty\}
\]
\end{example}
\end{frame}
\begin{frame}{Coalgebra-Algebra morphism and Recursive coalgebra}
\begin{definition}[Coalgebra-algebra morphism]
% For a category $\C$ and an endofunctor $T$,
A \emph{coalgebra-algebra} morphism from a $T$-coalgebra $(X,\theta)$ to a $T$-algebra $(A, \alpha)$ is a morphism $f\colon X \to A$ such that the following diagram commutes.
\[
\begin{tikzcd}[ampersand replacement=\&]
X \ar[r,"f"]\ar[d,"\theta"]\&A\\
TX \ar[r,"Tf"]\&TA\ar[u,"\alpha"']
\end{tikzcd}
\]
\end{definition}
\begin{definition}[Recursive coalgebra]
A $T$-coalgebra $(X,\theta)$ is \emph{recursive} if for any $T$-algebra $(A,\alpha)$, there uniquely exists a coalgebra-algebra morphism $(X,\theta)\to (A, \alpha)$.
\end{definition}
\end{frame}
\begin{frame}{Games = Recursive $\Pf$-coalgebras}
\begin{theorem}[Games as Recursive coalgebras]
The category of games $\Gs$ is equivalent to the category of recursive $\Pf$-coalgebras.
\end{theorem}
% \begin{proof}
% We can check the following two claims by concrete calculations:
% \begin{itemize}
% \item A $\Pf$-coalgebra $(X, \theta)$ is recursive if and only if its corresponding graph
% % $(X, \{(x,x')\mid x' \in \theta(x)\})$
% $(X, x\to x' \iff x' \in \theta(x))$ is a game.
% \item For two recursive $\Pf$-coalgebras $(X,\theta),(X',\theta)$, a function $f\colon X \to X'$ is a $\Pf$-coalgebra morphism if and only if $f$ is a game morphism.
% \end{itemize}
% \end{proof}
\begin{figure}
\centering
\includegraphics[width=0.75\linewidth]{images/RecursiveIsGames.jpeg}
\caption{Idea of the correspondence}
\end{figure}
\end{frame}
\begin{frame}{Games are recursive objects}
\small
A (short impartial) game is a directed graph $(X,\to)$ such that:
\begin{itemize}
\item each position has finitely many options;
\item there is no infinite play.
\end{itemize}
\begin{figure}[ht]
\centering
\begin{tikzpicture}[>=Latex, thick]
% ===== Vertices =====
\node[circle, fill=black, inner sep=3pt, label=above:{}] (A) at (0,0) {};
\node[circle, fill=black, inner sep=3pt, label=above:{}] (B) at (2,0) {};
\node[circle, fill=black, inner sep=3pt, label=above:{}] (C) at (4,0) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (D) at (0.5,-1.2) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (E) at (2,-1.2) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (F) at (3.5,-1.2) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (G) at (1,-2.4) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (H) at (3,-2.4) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (T1) at (0.5,-3.6) {};
\node[circle, fill=black, inner sep=3pt, label=below:{}] (T2) at (3.5,-3.6) {};
% ===== Arrows =====
\draw[->] (A) -- (D);
\draw[->] (A) -- (E);
\draw[->] (B) -- (E);
\draw[->] (B) -- (F);
\draw[->] (C) -- (F);
\draw[->] (D) -- (G);
\draw[->] (E) -- (G);
\draw[->] (E) -- (H);
\draw[->] (F) -- (H);
\draw[->] (G) -- (T1);
\draw[->] (G) -- (T2);
\draw[->] (H) -- (T2);
% ===== Curved extra arrow =====
\draw[->] (A) to[bend right] (G);
\draw[->] (C) to[bend left] (T2);
\end{tikzpicture}
\caption{An example of a finite game}
\label{fig:FiniteGame}
\end{figure}
\vspace{0.2em}
Typical quantities are defined \emph{backwards from the options}:
\begin{align*}
\oc(x) &=
\begin{cases}
N & \text{if some option has value }P,\\
P & \text{otherwise,}
\end{cases}
\\[0.3em]
\G(x) &= \mex\{\G(x') \mid x\to x'\}.
\end{align*}
Birthday, remoteness, mis\`ere outcome, and many others are defined in the same recursive way.
\vspace{0.4em}
\begin{center}
\color{red!75!black}\textbf{Point:} games are graphs on which these backward recursions are always well-defined.
\end{center}
\end{frame}
\begin{frame}{Coalgebra-algebra morphisms package the recursion}
Write the neighborhood map as
\[
\thetaf\colon X\longrightarrow \Pf(X),\qquad x\longmapsto \{x'\mid x\to x'\}.
\]
A recursive game value with codomain $A$ is a map $f\colon X\to A$ determined by
\[
f(x)=\alpha\bigl(\{f(x')\mid x\to x'\}\bigr)
\]
for some $\Pf$-algebra $\alpha\colon \Pf(A)\to A$.
\vspace{0.4em}
\begin{itemize}
\item $\alpha=\np$ gives \textbf{outcome}.
\item $\alpha=\mex$ gives \textbf{Grundy number}.
\item $\alpha=\xem$ gives \textbf{birthday}.
\end{itemize}
\vspace{0.4em}
\begin{block}{Terminology}
This unique solution is the hylomorphism $\hylo_{\alpha,\thetaf}$.
\end{block}
\end{frame}
\begin{frame}[t]{Main statement of Part I}
\begin{block}{Theorem}
The category of games is (isomorphic to) the category of recursive $\Pf$-coalgebras:
\[
\Gs \simeq \mathsf{RecCoalg}_{\Pf}.
\]
\end{block}
\end{frame}
\begin{frame}{Game values are hylomorphisms}
\begin{center}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{c|c}
\textbf{game value} & \textbf{$\Pf$-algebra} \\
\hline
outcome & $\np\colon \Pf(\{N,P\})\to \{N,P\}$ \\
Grundy number & $\mex\colon \Pf(\N)\to \N$ \\
birthday & $\xem\colon \Pf(\N)\to \N$
\end{tabular}
\end{center}
\vspace{0.5em}
\begin{block}{Consequence}
A game morphism preserves every recursively defined invariant coming from a $\Pf$-algebra.
\end{block}
\vspace{0.3em}
\begin{center}
\emph{Next question: where is differentiation hiding in the game rules themselves?}
\end{center}
\end{frame}
\section{Differentiation: Differential structure and Rota--Baxter invariants}
\begin{frame}{Move to pointed games and finite families}
\small
\begin{itemize}
\item A pointed game is a pair $(X,x)$ with a chosen starting position.
\item Let $\Gsp$ be the category of pointed games.
\item Let $\Fam(\Gsp)$ be the free finite-coproduct completion.
\end{itemize}
Think of an object of $\Fam(\Gsp)$ as a \emph{finite family of local game situations}.
\vspace{0.3em}
Natural operations:
\[
\text{addition }\sqcup = \text{disjoint union of families},
\qquad
\text{multiplication }\otimes = \text{gamewise Conway addition}.
\]
\begin{block}{Differential operator}
For a pointed game $(X,x)$, define
\[
\dd(X,x)\coloneqq \{(X,x')\}_{x\to x'}.
\]
\end{block}
\end{frame}
\begin{frame}{Leibniz rule for Conway addition}
For the Conway sum, every move changes \emph{either} the left component \emph{or} the right component.
\vspace{0.4em}
\begin{block}{Theorem}
In $\Fam(\Gsp)$ we have a categorified Leibniz rule:
\[
\dd(X\otimes Y)\cong (\dd X)\otimes Y \;\sqcup\; X\otimes (\dd Y).
\]
\end{block}
\vspace{0.6em}
\begin{center}
\begin{tikzpicture}[>=Latex, thick, scale=0.9]
\node[draw, rounded corners, minimum width=2.6cm, minimum height=0.9cm] (xy) at (0,0) {$X\otimes Y$};
\node[draw, rounded corners, minimum width=2.6cm, minimum height=0.9cm] (dx) at (-3,-2) {$(\dd X)\otimes Y$};
\node[draw, rounded corners, minimum width=2.6cm, minimum height=0.9cm] (dy) at (3,-2) {$X\otimes(\dd Y)$};
\draw[->] (xy) -- (dx) node[midway,left] {move in $X$};
\draw[->] (xy) -- (dy) node[midway,right] {move in $Y$};
\end{tikzpicture}
\end{center}
\vspace{0.3em}
\small This is the differential structure that I want to emphasize today; compare with differential 2-rigs \parencite{joyal1981theorie,loregian2021differential}.
\end{frame}
\begin{frame}{Decategorification target: calculus / Rota--Baxter rigs}
A \textbf{differential rig} is a rig $(A,0,1,+,\times,\dd)$ satisfying
\[
\dd(a+b)=\dd a+\dd b,
\qquad
\dd(ab)= (\dd a)b + a(\dd b).
\]
\vspace{0.5em}
An \textbf{integral rig} (or Rota--Baxter rig of weight $0$ in this talk) has an operator $\Int$ with
\[
1 = \Int 0,
\qquad
(\Int f)(\Int g)= \Int\bigl((\Int f)g + f(\Int g)\bigr).
\]
\vspace{0.5em}
A \textbf{calculus rig} has both, with the fundamental theorem
\[
\dd\,\Int f = f.
\]
\vspace{0.2em}
\begin{center}
\emph{Game families can be sent to such algebraic differential / integral structures.}
\end{center}
\end{frame}
\begin{frame}[t]{Rota--Baxter valued invariants of games}
Let $A$ be an integral rig. For a pointed game $(X,x)$ define recursively
\[
F_{(X,x)}\coloneqq \Int\!\left(\sum_{x\to x'} F_{(X,x')}\right).
\]
For a finite family, define $F$ by finite sums.
\vspace{0.3em}
\begin{block}{Theorem}
This assignment preserves the rig operations:
\[
F_{\mathcal{X}\sqcup\mathcal{Y}} = F_{\mathcal{X}} + F_{\mathcal{Y}},
\qquad
F_{\mathcal{X}\otimes\mathcal{Y}} = F_{\mathcal{X}}\times F_{\mathcal{Y}}.
\]
\end{block}
\vspace{0.2em}
\begin{center}
\emph{Why multiplication works: apply the Rota--Baxter identity to the Leibniz rule for options of a Conway sum.}
\end{center}
\end{frame}
\begin{frame}[t]{The universal example: game families themselves}
The family of all pointed positions in the terminal game carries a calculus-rig-like structure:
\begin{center}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{c|c}
\textbf{analysis} & \textbf{game families} \\
\hline
$0$ & empty family \\
$1$ & the terminal pointed game \\
$+$ & disjoint union / union \\
$\times$ & gamewise Conway sum \\
$\dd$ & take all immediate options \\
$\Int$ & adjoin a new root / braces $A\mapsto \{A\}$
\end{tabular}
\end{center}
\end{frame}
\begin{frame}{Nim-sum gives a concrete Rota--Baxter rig}
Start from the commutative monoid $(\N,\nimsum,0)$.
Its free idempotent rig is $\Pf(\N)$ with
\[
S+T \coloneqq S\cup T,
\qquad
S\times T \coloneqq \{s\nimsum t\mid s\in S,\ t\in T\}.
\]
Define the integral operator by
\[
\Int(S)\coloneqq \{\mex(S)\}.
\]
\vspace{0.5em}
\begin{block}{Theorem}
This makes $\Pf(\N)$ into an integral (Rota--Baxter) rig.
\end{block}
\vspace{0.4em}
So the classical \emph{mex + xor} mechanism of impartial game theory is an instance of a general algebraic pattern.
\end{frame}
\begin{frame}{The key identity is exactly a Rota--Baxter equation}
In the rig $\Pf(\N)$,
\[
(\Int S)(\Int T)=\Int\bigl((\Int S)T + S(\Int T)\bigr)
\]
becomes
\[
\{\mex(S)\}\times \{\mex(T)\}
=
\Int\bigl((\{\mex(S)\}\times T)\cup (S\times \{\mex(T)\})\bigr).
\]
Unpacking the product gives
\[
\mex(S)\nimsum\mex(T)
=\mex\bigl((\mex(S)\nimsum T)\cup (S\nimsum \mex(T))\bigr).
\]
\vspace{0.5em}
\begin{alertblock}{Interpretation}
This is the integral shadow of the Leibniz rule for the option operator of Conway addition.
\end{alertblock}
\end{frame}
\begin{frame}{Recovering Bouton's theorem}
Apply the previous construction to pointed Nim positions.
\vspace{0.5em}
\begin{itemize}
\item For one-heap Nim,
\[
F_{(\mathrm{Nim}_1,n)} = \{n\}
\qquad\text{(equivalently, the Grundy value is $n$).}
\]
\item Therefore for the Conway sum of $n$ heaps,
\[
F_{(a_1,\dots,a_n)} = \{a_1\nimsum\cdots\nimsum a_n\}.
\]
\item Hence $(a_1,\dots,a_n)$ is a $P$-position iff
\[
a_1\nimsum\cdots\nimsum a_n = 0.
\]
\end{itemize}
\vspace{0.4em}
\begin{block}{What changed conceptually?}
Instead of proving a mysterious xor identity by hand, we view it as the Rota--Baxter image of a differential rule on games.
\end{block}
\end{frame}
\begin{frame}{Take-home messages}
\begin{enumerate}
\item \textbf{Games are recursive coalgebras.}
The basic game values come from hylomorphisms for $\Pf$.
\item \textbf{Conway addition has a differential flavor.}
On pointed games / families, the option operator satisfies a Leibniz rule.
\item \textbf{Nim-sum is a Rota--Baxter phenomenon.}
The classical identity for $\mex$ and xor is the algebraic image of that Leibniz rule.
\end{enumerate}
\vspace{0.8em}
\begin{alertblock}{Outlook}
Partisan / probabilistic variants, a genuine chain rule, and a systematic interface with differential categories remain open.
\end{alertblock}
\end{frame}
\begin{frame}[allowframebreaks]{References}
\printbibliography[heading=none]
\end{frame}
% \appendix
\section{Appendix}
\begin{frame}{Internal monoid games}
\end{frame}
\begin{frame}{Rota-Baxteer property on game values}
\end{frame}
\begin{frame}{SMCC open problem of classification}
\end{frame}
\end{document}
\section{Drafts}
\begin{frame}{Outcome: Winning/Losing state}
\begin{columns}
\begin{column}{0.75 \textwidth}
\begin{definition}[Outcome]
For a game $\X=(X,\to)$ and a state $x\in X$, its \emph{outcome} $\O{\X}{x}\in \{W,L\}$ is recursively defined by
\[
\O{\X}{x}\coloneqq
\begin{cases}
W & (x\to \forall x' , \O{\X}{x'}=L)\\
L & (x\to \exists x' , \O{\X}{x'}=W)
\end{cases}
\]
\end{definition}
% \begin{proposition}
% For a game $\X=(X,\to)$, a state $x$ is a winning state if and only if $\G{\X}{x}=0$.
% \end{proposition}
\end{column}
\begin{column}{0.25 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/W_L_sample.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Grundy number}
\begin{columns}
\begin{column}{0.8 \textwidth}
\begin{definition}[mex]
The \emph{mex} of a finite subset $S \subset \N$ is $\min{(\N\setminus S)}$.
\end{definition}
% \begin{example}
% $\mex{\{0,1,2,4,6}\} = 3$, \hspace{10pt}
% $\mex{\emptyset}
% % =\min{\N \setminus \emptyset}
% =0$
% \end{example}
\begin{definition}[Grundy number]
For a game $\X=(X,\to)$ and a state $x\in X$, its \emph{Grundy number} $\G{\X}{x}$ is recursively defined by
\[
\G{\X}{x}\coloneqq \mex{\{\G{\X}{x'}\mid x\to x'\}}
\]
\end{definition}
\begin{proposition}
For a game $\X=(X,\to)$, a state $x$ is a winning state if and only if $\G{\X}{x}=0$.
\end{proposition}
\end{column}
\begin{column}{0.2 \textwidth}
\begin{figure}
\centering
\includegraphics[width=1.1\linewidth]{images/Grundy_number_2.jpeg}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{}
We can prove that game morphisms preserve \dq{game-theoretic data}:
\begin{proposition}
Game morphisms preserve
\begin{itemize}
\item Winning/Losing states,
\item Grundy numbers,
% \item Birthday (= height = the length of the longest path),
\item (and any "recursive data.")
\end{itemize}
\end{proposition}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/GameMorphismsCorrected.jpeg}
\end{figure}
\end{frame}
\begin{frame}{Recursive values = $\Pf$-algebras}
% Any $\Pf$-algebra $(A,\alpha)$ defines \dq{recursive data} for games
% \[
% \{\h_{\A,\X}\colon X \to A\}_{(X,\to)\text{: game}}
% \]
For a $\Pf$-algebra $\A= (A, \alpha)$ and a game $\X= (X, \to)$, there exists a unique function $\h_{\A,\X}\colon X\to A$ such that
\[
\h_{\A,\X}(x) = \alpha(\{\h_{\A,\X}(x')\mid x\to x'\})
\]
\begin{example}
\[
\begin{tikzcd}[ampersand replacement = \&, row sep = 3pt]
\text{\dq{Recursive value}} \& \leftrightsquigarrow\& \hspace{1pt}\ar[r,phantom ,"\Pf\text{-algebra}"]\& \hspace{1pt}\\
\text{ W/L states} \& \leftrightsquigarrow\&\Pf(\{W,L\})\ar[r]\& \{W,L\}\\
\text{Grundy number} \& \leftrightsquigarrow\& \Pf(\N)\ar[r,"\mathrm{mex}"]\& \N
% \text{Birthday} \& \leftrightsquigarrow\& \Pf(\N)\ar[r,"1+ \max"]\& \N\\
\end{tikzcd}
\]
\end{example}
\begin{corollary}
% \item
Game morphisms preserve all \dq{recursive values.}
% }
% % including outcome ($W/L$ state), Grundy number, height(=Birthday), and ...
% \end{itemize}
\end{corollary}
% \memo{Write}
\end{frame}
\begin{frame}{Let's return to our original motivation!}
% Then, let's return to our original motivation!
\begin{block}{Motivation}
Where does nim-sum come from?
\end{block}
In this section,
\begin{itemize}
\item let $\ast$ be a monoidal structure on $\Gs$ such that the forgetful functor
\[
U \colon \Gs \to \Set
\]
is lax monoidal, and
\item let $\A= (A, \alpha)$ be a $\Pf$-algebra.
\end{itemize}
\begin{example}
The prototypical example is the Conway addition $\ast=+$ and the W/L algebra $\A = (\{W,L\}, \alpha)$.
\end{example}
\end{frame}
\begin{frame}{Bouton monoid}
\begin{definition}[Bouton monoid]
Then we can construct the \emph{Bouton monoid} $\M{\ast}{\A}$ by the following procedure:
\begin{enumerate}
\item The terminal game $T$ has the unique monoid structure w.r.t. $(\Gs,\ast)$.
\item The forgetful functor $U\colon \Gs \to \Set$, which is lax-monoidal, induces a monoid structure on the set $UT$.
\item Let $\M{\ast}{\A}$ be the maximum quotient monoid of $UT$ that the canonical map $\h_{\A, T}\colon UT \to A$ factors through.
\end{enumerate}
\end{definition}
The multiplication of $\M{\ast}{\A}$ is denoted by $\circledast$.
For any game $\X = (X, \to)$, there is a canonical function
\[
\H{\ast}{\A}{\X}\colon X= U\X \to UT \to \M{\ast}{\A}
\]
\end{frame}
\begin{frame}{Generalized generalized Bouton's theorem}
So far, from
\begin{itemize}
\item a monoidal structure $\ast$ on $\Gs$ such that $U$ is lax monoidal, and
\item a $\Pf$-algebra $\A$
\end{itemize}
we have obtained
\begin{itemize}
\item the Bouton monoid $(\M{\ast}{\A}, \circledast)$, and
\item a function $\H{\ast}{\A}{\X}\colon X \to \M{\ast}{\A}$ for each game $\X$.
\end{itemize}
\begin{theorem}[Generalized generalized Bouton's theorem]
\begin{enumerate}
\item For any game $\X=(X,\to)$, the function $\h_{\A,\X}$ factors through $\H{\ast}{\A}{\X}$.
\item For two games $\X$ and $\Y$, we have
\[
\H{\ast}{\A}{\X\ast \Y}(x,y) = \H{\ast}{\A}{\X}(x) \circledast \H{\ast}{\A}{\Y}(y)
\]
\end{enumerate}
\end{theorem}
\begin{proposition}
Consider the case where $\ast$ is the Conway addition $+$, and $\A$ is the W/L algebra.
\begin{itemize}
\item In this case, our generalized generalized Bouton's theorem coincides with the original Bouton's theorem.
\item That is, we have $\H{+}{W/L}{\X}(x) = \G{\X}{x}$, and
% is equal to $\mathcal{G}_{\X}\colon X \to \N$, and
\item the Bouton monoid $\M{+}{W/L}$ is isomorphic to the abelian group of nim-sum $(\N, \nimsum)$!!
\end{itemize}
\end{proposition}
Nim-sum comes from the Conway-addition and Winning/Losing algebra!
\end{frame}