← rota-baxter-winning-games
DiffCatRIMS__AI-generated__DiffCat_semantic_colored.tex
\begin{filecontents*}{localrefs.bib}
@article{joyal1977remarques,
author = {Joyal, Andre},
title = {Remarques sur la theorie des jeux a deux personnes},
journal = {Gazette des sciences mathematiques du Quebec},
year = {1977}
}
@article{laird2013constructing,
author = {Laird, James and Manzonetto, Giulio and McCusker, Guy},
title = {Constructing categories and models of game semantics},
journal = {Mathematical Structures in Computer Science},
year = {2013}
}
@article{honsell2009conway,
author = {Honsell, Furio and Lenisa, Marina},
title = {Conway games and hypergames},
journal = {Electronic Notes in Theoretical Computer Science},
year = {2009}
}
@article{honsell2011conway,
author = {Honsell, Furio and Lenisa, Marina},
title = {Conway Games, algebraically and coalgebraically},
journal = {Preprint},
year = {2011}
}
@article{bavsic2024categories,
author = {Bavsic, Boro and others},
title = {Categories of impartial rulegraphs and gamegraphs},
journal = {Preprint},
year = {2024}
}
@article{blute2006differential,
author = {Blute, Richard and Cockett, Robin and Seely, Robert},
title = {Differential categories},
journal = {Mathematical Structures in Computer Science},
year = {2006}
}
@article{cockett2019integral,
author = {Cockett, Robin and Lemay, Jean-Simon Pacaud},
title = {Integral categories and calculus categories},
journal = {Mathematical Structures in Computer Science},
year = {2019}
}
@article{loregian2021differential,
author = {Loregian, Fosco and Trimble, Todd},
title = {Differential 2-rigs},
journal = {Preprint},
year = {2021}
}
@article{bouton1901nim,
author = {Bouton, Charles L.},
title = {Nim, a game with a complete mathematical theory},
journal = {Annals of Mathematics},
year = {1901}
}
@book{siegel2013combinatorial,
author = {Siegel, Aaron N.},
title = {Combinatorial Game Theory},
publisher = {American Mathematical Society},
year = {2013}
}
@article{joyal1981theorie,
author = {Joyal, Andre},
title = {Une theorie combinatoire des series formelles},
journal = {Advances in Mathematics},
year = {1981}
}
\end{filecontents*}
\documentclass[12pt,portrait,aspectratio=169]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{lmodern}
\usepackage{microtype}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb,mathtools}
\usepackage{array,booktabs}
\usepackage{pifont}
\usepackage{xcolor}
\usepackage{etoolbox}
\usepackage[style=authoryear,maxnames=3]{biblatex}
\addbibresource{localrefs.bib}
\usetikzlibrary{calc,positioning,arrows.meta,fit,backgrounds,decorations.pathreplacing,decorations.pathmorphing,shapes.geometric}
% ---- basic macros ----
\newcommand{\dq}[1]{``#1''}
\newcommand{\memo}[1]{{\color{red} #1}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\Gs}{\mathbf{Game}}
\newcommand{\Gsp}{\mathbf{Game}_{*}}
\newcommand{\Pf}{\mathcal{P}_{\mathrm{fin}}}
\newcommand{\Hf}{\mathbb{H}}
\newcommand{\oc}{\mathsf{Outcome}}
\newcommand{\G}[2]{\mathcal{G}_{#1}\left(#2\right)}
\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{\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{\RecCoalg}[1]{\mathsf{RecCoalg}_{#1}}
\newcommand{\Image}{\mathrm{Im}}
\newcommand{\Nim}[1]{\mathrm{Nim}_{#1}}
\newcommand{\ConAdd}{\otimes}
% ---- semantic 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}
\definecolor{mygray}{RGB}{95,95,95}
\definecolor{dcol}{RGB}{50,110,120}
\definecolor{icol}{RGB}{200,105,40}
\newcommand{\dcol}[1]{{\color{dcol}#1}}
\newcommand{\icol}[1]{{\color{icol}#1}}
\newcommand{\dop}{{\color{dcol}\partial}}
\newcommand{\iop}{{\color{icol}\int}}
\newcommand{\dd}{\dop}
\newcommand{\Int}{\iop}
\newcommand{\rel}{\mathrel{\dcol{\to}}}
% ---- beamer style ----
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{items}[default]
\setbeamertemplate{blocks}[rounded][shadow=false]
\setbeamertemplate{footline}[frame number]
\setbeamertemplate{bibliography item}{\raisebox{0.2ex}{\tiny\textbullet}}
% ---- theorem-like environments ----
\newcommand{\blocktitlemaybe}[2]{%
\ifstrempty{#2}{#1}{#1\ (#2)}%
}
\renewenvironment{theorem}[1][]{%
\begingroup
\setbeamercolor{block title}{fg=white,bg=myred}%
\setbeamercolor{block body}{fg=black,bg=mylightred}%
\begin{block}{\blocktitlemaybe{Theorem}{#1}}%
}{\end{block}\endgroup}
\renewenvironment{definition}[1][]{%
\begingroup
\setbeamercolor{block title}{fg=white,bg=myblue}%
\setbeamercolor{block body}{fg=black,bg=mylightblue}%
\begin{block}{\blocktitlemaybe{Definition}{#1}}%
}{\end{block}\endgroup}
\renewenvironment{example}[1][]{%
\begingroup
\setbeamercolor{block title}{fg=white,bg=mygreen}%
\setbeamercolor{block body}{fg=black,bg=mylightgreen}%
\begin{block}{\blocktitlemaybe{Example}{#1}}%
}{\end{block}\endgroup}
\newenvironment{proposition}[1][]{%
\begingroup
\setbeamercolor{block title}{fg=white,bg=myblue}%
\setbeamercolor{block body}{fg=black,bg=mylightblue}%
\begin{block}{\blocktitlemaybe{Proposition}{#1}}%
}{\end{block}\endgroup}
% ---- tikz styles ----
\tikzset{
>={Latex[length=2.3mm]},
gameedge/.style={->, draw=black!70, line width=0.7pt},
formulaarrow/.style={->, draw=myblue!85!black, line width=1pt},
state/.style={circle, fill=black, inner sep=2.2pt},
nstate/.style={circle, fill=myred, inner sep=2.3pt},
pstate/.style={circle, fill=myblue, inner sep=2.3pt},
bluepanel/.style={rounded corners=4pt, draw=myblue!75!black, fill=mylightblue, line width=0.8pt, inner sep=5pt, align=center},
greenpanel/.style={rounded corners=4pt, draw=mygreen!75!black, fill=mylightgreen, line width=0.8pt, inner sep=5pt, align=center},
redpanel/.style={rounded corners=4pt, draw=myred!75!black, fill=mylightred, line width=0.8pt, inner sep=5pt, align=center},
creampanel/.style={rounded corners=5pt, draw=black!20, fill=mycream, line width=0.8pt, inner sep=5pt, align=center},
browserbar/.style={rounded corners=4pt, draw=black!25, fill=black!4, line width=0.6pt},
searchbox/.style={rounded corners=6pt, draw=black!20, fill=white, line width=0.6pt},
heapcircle/.style={circle, draw=black!70, line width=0.9pt, fill=white, minimum size=8.5mm, inner sep=0pt}
}
% ---- helpers for figures ----
\newcommand{\heappile}[3]{%
\begin{scope}[shift={({#1},{#2})}]
\node[heapcircle] at (0,0) {};
\ifcase#3\relax
\or
\fill (0,0) circle (1.3pt);
\or
\fill (-0.12,0.12) circle (1.3pt);
\fill (0.12,-0.12) circle (1.3pt);
\or
\fill (0,0.15) circle (1.3pt);
\fill (-0.13,-0.10) circle (1.3pt);
\fill (0.13,-0.10) circle (1.3pt);
\fi
\end{scope}%
}
\newcommand{\heapstate}[4]{%
\heappile{#1}{0.92}{#2}
\heappile{#1}{0.00}{#3}
\heappile{#1}{-0.92}{#4}
}
\newcommand{\slantedgrid}[5]{%
\def\dx{0.8}
\def\dy{-0.8}
\def\ex{-0.8}
\def\ey{-0.8}
\foreach \i in {0,...,#1}{%
\foreach \j in {0,...,#2}{%
\coordinate (#5-\i-\j) at (#3+\i*\dx+\j*\ex, #4+\i*\dy+\j*\ey);
\node[circle, fill=black, inner sep=1pt] at (#5-\i-\j) {};
}%
}%
\ifnum#1>0
\pgfmathtruncatemacro{\imax}{#1-1}%
\foreach \i in {0,...,\imax}{%
\foreach \j in {0,...,#2}{%
\draw[->] (#5-\i-\j) -- (#5-\the\numexpr\i+1\relax-\j);
}%
}%
\fi
\ifnum#2>0
\pgfmathtruncatemacro{\jmax}{#2-1}%
\foreach \i in {0,...,#1}{%
\foreach \j in {0,...,\jmax}{%
\draw[->] (#5-\i-\j) -- (#5-\i-\the\numexpr\j+1\relax);
}%
}%
\fi
}
\AtBeginSection[]{%
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\title[A Rota--Baxter equation for winning games]{A Rota--Baxter Equation for Winning Games}
\subtitle{Games as recursive coalgebras and differential invariants}
\author[R. Hora]{Ryuya Hora}
\institute{Assistant professor at ZEN university}
\date{Differentiation in category theory and program semantics\\Kyoto University, April 6, 2026}
%AI suggestion: If this is for the actual 2026 talk, double-check the institute line on the title slide.
%AI suggestion: In a short talk, the short-survey slide can move to the appendix and you can start directly from the Nim phenomenon.
%AI suggestion: If you need one extra minute for the main theorem, merge the universal-example slide with the Nim-sum rig slide.
\begin{document}
\begin{frame}
\titlepage
\vspace{-0.4em}
\begin{center}
\small Partially based on joint work in progress with Ryo Suzuki.
\end{center}
\begin{center}
\small Keywords: \icol{Rota--Baxter equation}, combinatorial games, recursive \dcol{coalgebra}, \dcol{differential} $2$-rig
\end{center}
\end{frame}
\section{Front matter}
\begin{frame}{Where I come from}
\Large
I've been interested in toposes, \textbf{\dcol{games}, and \dcol{coalgebras}}.\\[0.7em]
\begin{figure}
\centering
\begin{tikzpicture}
\node[browserbar, minimum width=9.5cm, minimum height=3.8cm] (win) at (0,0) {};
\foreach \x in {-4.2,-3.9,-3.6} {
\fill[black!30] (\x,1.55) circle (1.2pt);
}
\node[anchor=west, font=\bfseries\small] at ($(win.north west)+(0.25,-0.32)$) {Search};
\node[searchbox, anchor=north, minimum width=7.9cm, minimum height=0.72cm] (search) at ($(win.north)+(0,-0.82)$) {};
\node[anchor=west, font=\normalsize] at ($(search.west)+(0.22,0)$) {recusion};
\draw[myred, line width=1.0pt, decorate, decoration={snake, amplitude=0.35mm, segment length=2.5mm}]
($(search.west)+(1.14,-0.18)$) -- ($(search.west)+(2.90,-0.18)$);
\node[anchor=west, text=mygray] at (-3.82,0.25) {I tried to check the spelling.};
\node[anchor=west, text=myblue, font=\bfseries] at (-3.82,-0.42) {Did you mean: recursion};
\node[anchor=west, text=mygray, font=\small] at (-3.82,-1.05) {So I kept the joke and moved on.};
\end{tikzpicture}
\end{figure}
\end{frame}
\begin{frame}{Where this talk comes from}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
\begin{itemize}
\item My motivation comes from \textbf{Combinatorial Game Theory}.
\item I am \textbf{not} a specialist in \dcol{differential} categories in the usual sense.
\item So this talk is partly a proposal about how game recursion should be organized categorically.
\end{itemize}
\end{column}
\begin{column}{0.40\textwidth}
\begin{proposition}[What I hope to learn here]
\begin{itemize}
\item the right map of prior work,
\item links to \dcol{differential} / Cartesian differential categories,
\item links to game semantics and linear logic,
\item where the \icol{Rota--Baxter} viewpoint fits.
\end{itemize}
\end{proposition}
\end{column}
\end{columns}
\vspace{0.3em}
\begin{center}
\emph{I am coming mainly from the game side, but trying to speak to this audience.}
\end{center}
\end{frame}
\begin{frame}{The dichotomy in this talk}
\begin{figure}
\centering
\begin{tikzpicture}[x=1cm,y=1cm,>=Latex,thick]
\node[text=dcol, font=\bfseries] at (-2,2.05) {Differentiation};
\node[text=mygray, font=\bfseries] at (0,2.05) {vs};
\node[text=icol, font=\bfseries] at ( 2,2.05) {Integration};
\node[text=dcol, font=\bfseries, align=center] (L1) at (-4.9, 1.20) {Play forward};
\node[text=dcol, font=\bfseries, align=center] (L2) at (-4.9, 0.00) {Coalgebra};
\node[text=dcol, font=\bfseries, align=center] (L3) at (-4.9, -1.20) {Leibniz rule};
\node[text=icol, font=\bfseries, align=center] (R1) at ( 4.9, 1.20) {Analyze backward};
\node[text=icol, font=\bfseries, align=center] (R2) at ( 4.9, 0.00) {Algebra};
\node[text=icol, font=\bfseries, align=center] (R3) at ( 4.9, -1.20) {Rota--Baxter\\equation};
\draw[<->, draw=gray!55, line width=0.8pt] (L1.east) -- (R1.west);
\draw[<->, draw=gray!55, line width=0.8pt] (L2.east) -- (R2.west);
\draw[<->, draw=gray!55, line width=0.8pt] (L3.east) -- (R3.west);
\draw[->, line width=1.5pt, draw=dcol] (-2,1.55) -- (-2,-1.95);
\draw[->, line width=1.5pt, draw=icol] ( 2,-1.95) -- ( 2,1.55);
\end{tikzpicture}
\end{figure}
\end{frame}
%AI suggestion: If you prefer a more aggressive opening, move this survey slide after the first section instead of before it.
\begin{frame}{Short survey: games $\times$ category theory is not new}
\footnotesize
\begin{proposition}[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{\dcol{differential} / \icol{Rota--Baxter} ideas}.
\]
\end{proposition}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.32\textwidth}
\begin{example}[Game semantics]
\begin{itemize}
\item strategies as morphisms,
\item linear logic / programming semantics.
\end{itemize}
\end{example}
\end{column}
\begin{column}{0.32\textwidth}
\begin{example}[\dcol{Coalgebraic} games]
\begin{itemize}
\item Conway games / hypergames,
\item recursive viewpoints on impartial games.
\end{itemize}
\end{example}
\end{column}
\begin{column}{0.32\textwidth}
\begin{example}[\icol{Differential} side]
\begin{itemize}
\item differential categories,
\item integral / calculus categories.
\end{itemize}
\end{example}
\end{column}
\end{columns}
\vspace{0.15em}
{\scriptsize Representative references: game semantics \parencite{joyal1977remarques,laird2013constructing}; coalgebraic games \parencite{honsell2009conway,honsell2011conway,bavsic2024categories}; differential side \parencite{blute2006differential,cockett2019integral,loregian2021differential}.}
\end{frame}
\section[Play forward $\leftrightarrow$ Analyze backward]{Play vs Analysis: Generalized Bouton's theorem is \texorpdfstring{\icol{Integration}}{Integration}!}
\subsection{Preliminaries: Winning Nim!}
\begin{frame}{Rule of $n$-heap Nim}
\small
\begin{itemize}
\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
\begin{tikzpicture}[scale=1]
\node[creampanel, minimum width=10.5cm, minimum height=3.7cm] (bg) at (0,0) {};
\heapstate{-3.9}{1}{2}{3}
\heapstate{-1.3}{1}{2}{1}
\heapstate{1.3}{1}{0}{1}
\heapstate{5.1}{0}{0}{0}
\node[text=myred, font=\large] at (-2.6,0.38) {$A$};
\node[font=\large] at (-2.6,-0.02) {$\rightsquigarrow$};
\node[text=myblue, font=\large] at (0.0,0.38) {$B$};
\node[font=\large] at (0.0,-0.02) {$\rightsquigarrow$};
\node at (3.0,-0.02) {$\cdots$};
\node[text=myred, font=\large] at (4.0,0.38) {$A$};
\node[font=\large] at (4.0,-0.02) {$\rightsquigarrow$};
\end{tikzpicture}
\end{figure}
\end{frame}
\begin{frame}[t]{Bouton's winning strategy (1/2) Nim sum}
\footnotesize
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.58\textwidth}
\begin{definition}[Nim-sum]
The \emph{Nim-sum} $\nimsum$ is bit-wise xor, i.e. the abelian group structure on $\N$ induced by the binary expansion
\[
\N \cong \bigoplus_{k=0}^{\infty} \Z/2\Z.
\]
\end{definition}
\begin{example}
$5\nimsum 7 = \left(101\right)_2 \nimsum \left(111\right)_2 = \left(010\right)_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 winning strategy (2/2)}
\small
\begin{theorem}[Bouton, 1901]
A state $\left(a_1,\dots,a_n\right)$ of $n$-heap Nim is winning for the previous player iff
\[
a_1\nimsum\cdots\nimsum a_n = 0.
\]
\end{theorem}
\begin{proposition}[Phenomenon]
The only non-trivial part of the proof is the identity
\[
\mex\left(S\right)\nimsum \mex\left(T\right)
= \mex\left(\left(\mex\left(S\right)\nimsum T\right)\cup \left(S\nimsum \mex\left(T\right)\right)\right).
\]
This already looks like an \icol{integration law}, namely a \icol{Rota--Baxter equation}.
\end{proposition}
\end{frame}
\subsection{Impartial Games}
\begin{frame}{Definition of games}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.78\textwidth}
\begin{definition}[(Impartial) game]
A game $\mathbb{X}=\left(X,\rel\right)$ is a pair of a (possibly infinite) set $X$ and a binary relation $\rel \subset X\times X$ satisfying:
\begin{enumerate}
\item \emph{finite options}: $\#\left\{x'\in X\mid x\rel x'\right\}$ is finite for every $x\in X$;
\item \emph{finite time}: there is no infinite path $x_0\rel x_1\rel x_2\rel \cdots$.
\end{enumerate}
\end{definition}
\begin{example}[$\Nim{n}$: $n$-heap Nim]
The game $\Nim{n}=\left(\N^n,\rel\right)$ is defined by
\[
\left(a_i\right)_{1\leq i\leq n} \rel \left(b_i\right)_{1\leq i\leq n}
\iff \exists i\, \left(a_i>b_i \land a_j=b_j\ \left(j\neq i\right)\right).
\]
\end{example}
\end{column}
\begin{column}{0.18\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[>=Latex, thick, scale=0.62]
\tikzset{edge/.style={->, draw=black}}
\node[circle, inner sep=3pt, fill=black] (Z1) at (-2,-7.2) {};
\node[circle, inner sep=3pt, fill=black] (Z2) at ( 0,-7.2) {};
\node[circle, inner sep=3pt, fill=black] (Z3) at ( 2,-7.2) {};
\node[circle, inner sep=3pt, fill=black] (Y1) at (-2,-5.8) {};
\node[circle, inner sep=3pt, fill=black] (Y2) at ( 0,-5.8) {};
\node[circle, inner sep=3pt, fill=black] (Y3) at ( 2,-5.8) {};
\node[circle, inner sep=3pt, fill=black] (X1) at (-2,-4.4) {};
\node[circle, inner sep=3pt, fill=black] (X2) at ( 0,-4.4) {};
\node[circle, inner sep=3pt, fill=black] (X3) at ( 2,-4.4) {};
\node[circle, inner sep=3pt, fill=black] (W1) at (-2,-3.0) {};
\node[circle, inner sep=3pt, fill=black] (W3) at ( 0,-3.0) {};
\node[circle, inner sep=3pt, fill=black] (W2) at ( 2,-3.0) {};
\node[circle, inner sep=3pt, fill=black] (V1) at (-1,-1.6) {};
\node[circle, inner sep=3pt, fill=black] (V2) at ( 1,-1.6) {};
\draw[edge] (Y1) -- (Z1);
\draw[edge] (Y2) -- (Z2);
\draw[edge] (Y2) -- (Z3);
\draw[edge] (Y3) -- (Z3);
\draw[edge] (X1) -- (Y1);
\draw[edge] (X1) -- (Y2);
\draw[edge] (X2) -- (Y2);
\draw[edge] (X2) -- (Z1);
\draw[edge] (X3) -- (Y3);
\draw[edge] (W1) -- (X1);
\draw[edge] (W1) -- (X2);
\draw[edge] (W2) -- (X2);
\draw[edge] (W2) -- (X3);
\draw[edge] (W3) -- (Y1);
\draw[edge] (W3) -- (Z3);
\draw[edge] (V1) -- (W1);
\draw[edge] (V1) -- (W2);
\draw[edge] (V1) -- (W3);
\draw[edge] (V2) -- (W2);
\draw[edge] (V2) -- (X2);
\draw[edge] (V2) -- (X3);
\end{tikzpicture}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{$\times$: Box product of games}
\small
\begin{definition}[Box product {\tiny a.k.a. Conway's addition}]
The box product of two games $\mathbb{X}=\left(X,\rel\right)$ and $\mathbb{Y}=\left(Y,\rel\right)$ is the game $\mathbb{X}\ConAdd\mathbb{Y}=\left(X\times Y,\rel_{\ConAdd}\right)$ with
\[
\left(x,y\right)\rel_{\ConAdd}\left(x',y'\right)
\iff \left(x\rel x' \land y=y'\right) \lor \left(x=x' \land y\rel y'\right).
\]
\end{definition}
\begin{figure}
\centering
\begin{tikzpicture}[>=Latex, scale=0.42]
\slantedgrid{3}{0}{-8}{0}{X}
\node at (-7,-4) {$\mathbb{X}$};
\node at (-4.3,-1) {$\ConAdd$};
\slantedgrid{0}{4}{0}{0.5}{Y}
\node at (-1.5,-4) {$\mathbb{Y}$};
\node at (2.3,-1) {$=$};
\slantedgrid{3}{4}{7}{2}{Z}
\node at (6.5,-4) {$\mathbb{X}\ConAdd\mathbb{Y}$};
\end{tikzpicture}
\caption{An example of box product.}
\label{fig:boxproduct}
\end{figure}
\end{frame}
\begin{frame}{$\iop$: \icol{Mex} and Grundy number}
\footnotesize
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.62\textwidth}
\begin{definition}[mex]
For a finite subset $S\subset \N$, its mex is
\[
\mex\left(S\right)=\min\left(\N\setminus S\right).
\]
\end{definition}
\begin{definition}[Grundy number]
For a game $\mathbb{X}=\left(X,\rel\right)$ and a state $x\in X$, its Grundy number is recursively defined by
\[
\G{\mathbb{X}}{x}=\mex\left(\left\{\G{\mathbb{X}}{x'}\mid x\rel x'\right\}\right).
\]
\end{definition}
\begin{proposition}[Grundy number is enough to win]
A state $x$ is winning iff $\G{\mathbb{X}}{x}=0$.
\end{proposition}
\end{column}
\begin{column}{0.34\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.78]
\node[state,label=above:$x$] (x) at (0,1.8) {};
\node[state,label=left:$x_1$] (x1) at (-1.45,0.85) {};
\node[state,label=above:$x_2$] (x2) at (0,0.85) {};
\node[state,label=right:$x_3$] (x3) at (1.45,0.85) {};
\node[pstate,label=left:$0$] (z1) at (-1.8,-0.7) {};
\node[nstate,label=below:$1$] (z2) at (-0.7,-0.7) {};
\node[pstate,label=below:$0$] (z3) at (0.7,-0.7) {};
\node[nstate,label=right:$2$] (z4) at (1.9,-0.7) {};
\draw[gameedge] (x) -- (x1);
\draw[gameedge] (x) -- (x2);
\draw[gameedge] (x) -- (x3);
\draw[gameedge] (x1) -- (z1);
\draw[gameedge] (x1) -- (z2);
\draw[gameedge] (x2) -- (z2);
\draw[gameedge] (x2) -- (z3);
\draw[gameedge] (x3) -- (z3);
\draw[gameedge] (x3) -- (z4);
\end{tikzpicture}
\caption{Recursive calculation from terminal positions.}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Generalized Bouton's theorem}
\small
\begin{theorem}[Generalized Bouton's theorem]
For two games $\mathbb{X}=\left(X,\rel\right)$ and $\mathbb{Y}=\left(Y,\rel\right)$, we have
\[
\G{\mathbb{X}\ConAdd\mathbb{Y}}{\left(x,y\right)}
=
\G{\mathbb{X}}{x}\nimsum \G{\mathbb{Y}}{y}.
\]
\end{theorem}
\begin{proof}[The only non-trivial part of the proof]
\[
\mex\left(S\right)\nimsum \mex\left(T\right)
= \mex\left(\left(\mex\left(S\right)\nimsum T\right)\cup \left(S\nimsum \mex\left(T\right)\right)\right).
\]
\end{proof}
This is already strikingly similar to the \icol{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[Coalgebras $\leftrightarrow$ Algebras]{Coalgebra vs Algebra: A locally finitely presentable category of games = recursive \texorpdfstring{\dcol{$\Pf$-coalgebras}}{Pfin-coalgebras}}
\subsection{Preliminaries: Coalgebra and recursion}
\begin{frame}{Algebra/Coalgebra of an endofunctor}
\small
\begin{definition}[$T$-algebras and $T$-coalgebras]
For a category $\mathcal{C}$ and an endofunctor $T\colon \mathcal{C}\to \mathcal{C}$:
\begin{itemize}
\item A \icol{$T$-algebra} is a pair $\left(A,\alpha\right)$ with a morphism $\alpha\colon TA \mathrel{\icol{\to}} A$.
\item A \dcol{$T$-coalgebra} is a pair $\left(X,\theta\right)$ with a morphism $\theta\colon X \rel TX$.
\end{itemize}
\end{definition}
\begin{example}
In this talk, the key case is $\mathcal{C}=\Set$ and $T=\Pf$, where
\[
\Pf\left(X\right)=\left\{S\subset X\mid \#S<\infty\right\}.
\]
\end{example}
\end{frame}
\begin{frame}{Coalgebra-Algebra morphism and Recursive coalgebra}
\footnotesize
\begin{definition}[Coalgebra-algebra morphism]
A coalgebra-algebra morphism from a \dcol{$T$-coalgebra} $\left(X,\theta\right)$ to an \icol{$T$-algebra} $\left(A,\alpha\right)$ is a morphism $f\colon X\to A$ such that
\[
\begin{tikzcd}[ampersand replacement=\&, row sep=large, column sep=large]
X \arrow[r,"f"] \arrow[d,"{\theta}"'] \& A \\
TX \arrow[r,"{Tf}"'] \& TA \arrow[u,"{\alpha}"']
\end{tikzcd}
\]
commutes.
\end{definition}
\begin{definition}[Recursive coalgebra]
A \dcol{$T$-coalgebra} $\left(X,\theta\right)$ is \emph{recursive} if, for every \icol{$T$-algebra} $\left(A,\alpha\right)$, there exists a unique coalgebra-algebra morphism $\left(X,\theta\right)\to \left(A,\alpha\right)$.
\end{definition}
\end{frame}
\subsection{Games as recursive coalgebras}
\begin{frame}{Games = Recursive $\Pf$-coalgebras}
\small
\begin{theorem}[Games as recursive coalgebras]
The category of games is equivalent to the category of recursive \dcol{$\Pf$-coalgebras}:
\[
\Gs \simeq \RecCoalg{\Pf}.
\]
\end{theorem}
\begin{figure}
\centering
\[
\begin{tikzcd}[ampersand replacement=\&, row sep=large, column sep=huge]
\text{game } \left(X,\rel\right) \arrow[r, rightsquigarrow] \arrow[d, mapsto]
\& \text{recursive \dcol{$\Pf$-coalgebra}} \arrow[d, mapsto] \\
\theta_X\colon X \rel \Pf\left(X\right),
\quad x \mapsto \left\{x'\mid x\rel x'\right\}
\arrow[r, rightsquigarrow]
\& \text{backward recursion against the flow of play}
\end{tikzcd}
\]
\end{figure}
\begin{proposition}[Two examples]
\begin{itemize}
\item One-heap Nim corresponds to $\nu\colon \N\to \Pf\left(\N\right)$, $\nu\left(n\right)=\left\{0,\dots,n-1\right\}$.
\item The terminal game is the game of hereditarily finite sets, with $A\rel B$ iff $B\in A$.
\end{itemize}
\end{proposition}
\end{frame}
%AI suggestion: If the audience is less familiar with locally presentable categories, move this slide after the main theorem or send it to the appendix.
\begin{frame}{Digression: Categorical structure of games}
\small
\begin{proposition}[The category $\Gs$ behaves very well]
\begin{itemize}
\item The category $\Gs$ is \textbf{locally finitely presentable}.
\item In particular, $\Gs$ is complete and cocomplete.
\item The box product $\ConAdd$ is a symmetric monoidal closed structure on $\Gs$.
\end{itemize}
\end{proposition}
\begin{proposition}[Game values are hylomorphisms]
Typical game values arise from \icol{$\Pf$-algebras}:
\[
\text{outcome } \oc,
\qquad
\text{Grundy number } \G{\mathbb{X}}{x},
\qquad
\text{birthday } \BirthDay.
\]
So a \dcol{coalgebraic} presentation of games naturally packages their recursive \icol{algebraic} values.
\end{proposition}
\end{frame}
\section[Differentiation $\leftrightarrow$ Integration]{Differentiation vs Integration: Calculus 2-rig of pointed game families}
\subsection{Differential $2$-rig of games}
\begin{frame}{Differentiation on families of pointed games}
\footnotesize
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.50\textwidth}
\begin{itemize}
\item A pointed game is a pair $\left(X,x\right)$ with a chosen starting position.
\item Let $\Gsp$ be the category of pointed games.
\item Let $\Fam\left(\Gsp\right)$ be the free finite-coproduct completion.
\end{itemize}
Think of an object of $\Fam\left(\Gsp\right)$ as a finite family of local game situations.
\vspace{0.3em}
\begin{definition}[\dcol{Differential} operator]
For a pointed game $\left(X,x\right)$, define
\[
\dd\left(X,x\right)\coloneqq \left\{\left(X,x'\right)\right\}_{x\rel x'}.
\]
\end{definition}
\end{column}
\begin{column}{0.46\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.84]
\node[bluepanel, minimum width=2.5cm, minimum height=0.75cm] (rootbox) at (0,2.05) {$\left(X,x\right)$};
\node[state] (x) at (0,1.15) {};
\node[state] (x1) at (-1.2,0.15) {};
\node[state] (x2) at (0,-0.05) {};
\node[state] (x3) at (1.2,0.15) {};
\draw[gameedge] (x) -- (x1);
\draw[gameedge] (x) -- (x2);
\draw[gameedge] (x) -- (x3);
\node[greenpanel, fit=(x1) (x2) (x3), inner sep=7pt] (fam) {};
\node[greenpanel, minimum width=3.1cm, minimum height=0.75cm] (d) at (0,-1.15) {$\dd\left(X,x\right)$};
\draw[formulaarrow] (rootbox) -- (d);
\draw[formulaarrow] (fam.south) -- (d.north);
\end{tikzpicture}
\end{figure}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Leibniz rule for Box product}
\small
For the box product, every move changes \emph{either} the left component or the right component.
\vspace{0.2em}
\begin{theorem}
In $\Fam\left(\Gsp\right)$ we have a categorified \dcol{Leibniz rule}:
\[
\dd\left(X\ConAdd Y\right)
\cong
\left(\dd X\right)\ConAdd Y
\;\sqcup\;
X\ConAdd \left(\dd Y\right).
\]
\end{theorem}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.82]
\node[bluepanel, minimum width=2.6cm, minimum height=0.8cm] (xy) at (0,0.05) {$X\ConAdd Y$};
\node[bluepanel, minimum width=2.7cm, minimum height=0.8cm] (dx) at (-3.05,-1.7) {$\left(\dd X\right)\ConAdd Y$};
\node[bluepanel, minimum width=2.7cm, minimum height=0.8cm] (dy) at (3.05,-1.7) {$X\ConAdd\left(\dd Y\right)$};
\draw[formulaarrow] (xy) -- (dx) node[midway,left] {move in $X$};
\draw[formulaarrow] (xy) -- (dy) node[midway,right] {move in $Y$};
\end{tikzpicture}
\end{figure}
{\scriptsize This is the differential structure emphasized here; compare with differential 2-rigs \parencite{joyal1981theorie,loregian2021differential}.}
\end{frame}
\subsection{Invariants in Rota-Baxter rig}
\begin{frame}[t]{Decategorification target: calculus / Rota--Baxter rigs}
\scriptsize
\begin{definition}[\dcol{Differential} rig]
A rig $\left(A,0,1,+,\times,\dd\right)$ with
\[
\dd\left(a+b\right)=\dd a+\dd b,
\qquad
\dd\left(ab\right)=\left(\dd a\right)b + a\left(\dd b\right).
\]
\end{definition}
\begin{definition}[\icol{Integral} rig]
A rig with an operator $\Int$ satisfying
\[
1 = \Int 0,
\qquad
\left(\Int f\right)\left(\Int g\right)
= \Int\left(\left(\Int f\right)g + f\left(\Int g\right)\right).
\]
\end{definition}
\begin{definition}[Calculus rig]
A rig carrying both structures, with the fundamental theorem
\[
\dd\,\Int f = f.
\]
\end{definition}
\begin{center}
{\footnotesize\emph{Game families can be sent to such algebraic \dcol{differential} / \icol{integral} structures.}}
\end{center}
\end{frame}
\begin{frame}[t]{Rota--Baxter valued invariants of games}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
Let $A$ be an \icol{integral} rig. For a pointed game $\left(X,x\right)$ define recursively
\[
F_{\left(X,x\right)}\coloneqq \Int\!\left(\sum_{x\rel x'} F_{\left(X,x'\right)}\right).
\]
For a finite family, define $F$ by finite sums.
\vspace{0.25em}
\begin{theorem}
This assignment preserves the rig operations:
\[
F_{\mathcal{X}\sqcup\mathcal{Y}} = F_{\mathcal{X}} + F_{\mathcal{Y}},
\qquad
F_{\mathcal{X}\ConAdd\mathcal{Y}} = F_{\mathcal{X}}\times F_{\mathcal{Y}}.
\]
\end{theorem}
\end{column}
\begin{column}{0.40\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.86]
\node[bluepanel, minimum width=2.7cm, minimum height=0.75cm] (fx) at (0,2.1) {$F_{\left(X,x\right)}$};
\node[greenpanel, minimum width=1.25cm, minimum height=0.68cm] (int) at (0,1.05) {$\Int$};
\node[bluepanel, minimum width=3.2cm, minimum height=0.78cm] (sum) at (0,-1.95) {$\sum_{x\rel x'} F_{\left(X,x'\right)}$};
\node[state] (x) at (0,-0.02) {};
\node[state] (x1) at (-1.15,-0.95) {};
\node[state] (x2) at (0,-1.12) {};
\node[state] (x3) at (1.15,-0.95) {};
\draw[gameedge] (x) -- (x1);
\draw[gameedge] (x) -- (x2);
\draw[gameedge] (x) -- (x3);
\draw[formulaarrow] (sum) -- (int);
\draw[formulaarrow] (int) -- (fx);
\end{tikzpicture}
\end{figure}
\end{column}
\end{columns}
{\scriptsize Why multiplication works: apply the \icol{Rota--Baxter} identity to the \dcol{Leibniz} rule for options of a box product.}
\end{frame}
\subsection{Examples}
\begin{frame}[t]{The universal example: game families themselves}
\footnotesize
The family of all pointed positions in the terminal game carries a calculus-rig-like structure:
\begin{center}
\renewcommand{\arraystretch}{1.08}
\begin{tabular}{@{}ll@{}}
\toprule
\textbf{\icol{analysis}} & \textbf{\dcol{game families}} \\
\midrule
$0$ & empty family \\
$1$ & the terminal pointed game \\
$+$ & disjoint union / union \\
$\times$ & gamewise box product \\
$\dd$ & take all immediate options \\
$\Int$ & adjoin a new root / braces $A\mapsto \left\{A\right\}$ \\
\bottomrule
\end{tabular}
\end{center}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.68]
\node[bluepanel, minimum width=1.2cm, minimum height=0.62cm] (A) at (-2.8,0) {$A$};
\node[greenpanel, minimum width=1.4cm, minimum height=0.62cm] (IA) at (0,0) {$\left\{A\right\}$};
\node[bluepanel, minimum width=1.7cm, minimum height=0.62cm] (dA) at (2.8,0) {$\dd A$};
\draw[formulaarrow] (A) -- node[above] {$\Int$} (IA);
\draw[formulaarrow] (A) -- node[above] {$\dd$} (dA);
\node[state] (a1) at (2.45,-0.82) {};
\node[state] (a2) at (3.12,-0.82) {};
\draw[gameedge] (dA.south) -- (a1);
\draw[gameedge] (dA.south) -- (a2);
\end{tikzpicture}
\end{figure}
\end{frame}
\begin{frame}[t]{Nim-sum gives a concrete Rota--Baxter rig}
\footnotesize
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.58\textwidth}
Start from the commutative monoid $\left(\N,\nimsum,0\right)$.
Its free idempotent rig is $\Pf\left(\N\right)$ with
\[
S+T \coloneqq S\cup T,
\qquad
S\times T \coloneqq \left\{s\nimsum t\mid s\in S,\ t\in T\right\}.
\]
Define the \icol{integral} operator by
\[
\Int\left(S\right)\coloneqq \left\{\mex\left(S\right)\right\}.
\]
\begin{theorem}
This makes $\Pf\left(\N\right)$ into an \icol{integral} (\icol{Rota--Baxter}) rig.
\end{theorem}
\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}{The key identity is exactly a Rota--Baxter equation}
\small
In the rig $\Pf\left(\N\right)$,
\[
\left(\Int S\right)\left(\Int T\right)
=
\Int\left(\left(\Int S\right)T + S\left(\Int T\right)\right)
\]
becomes
\[
\left\{\mex\left(S\right)\right\}\times \left\{\mex\left(T\right)\right\}
=
\Int\left(\left(\left\{\mex\left(S\right)\right\}\times T\right)\cup \left(S\times \left\{\mex\left(T\right)\right\}\right)\right).
\]
Unpacking the product gives exactly
\[
\mex\left(S\right)\nimsum \mex\left(T\right)
=
\mex\left(\left(\mex\left(S\right)\nimsum T\right)\cup \left(S\nimsum \mex\left(T\right)\right)\right).
\]
\begin{proposition}[Interpretation]
This \icol{integral} identity is the shadow of the \dcol{Leibniz rule} for the option operator of box product.
\end{proposition}
\end{frame}
\begin{frame}[t]{Recovering Bouton's theorem}
\scriptsize
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
Apply the construction to pointed Nim positions.
\begin{itemize}
\itemsep0.2em
\item One-heap Nim satisfies
\[
F_{\left(\mathrm{Nim}_1,n\right)} = \left\{n\right\}.
\]
\item Hence for the box product of $n$ heaps,
\[
F_{\left(a_1,\dots,a_n\right)} = \left\{a_1\nimsum\cdots\nimsum a_n\right\}.
\]
\item Therefore $\left(a_1,\dots,a_n\right)$ is a $P$-position iff
\[
a_1\nimsum\cdots\nimsum a_n = 0.
\]
\end{itemize}
\end{column}
\begin{column}{0.40\textwidth}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.75]
\node[bluepanel, minimum width=2.65cm, minimum height=0.68cm] (n1) at (0,1.5) {$\left(\mathrm{Nim}_1,n\right)$};
\node[greenpanel, minimum width=1.30cm, minimum height=0.64cm] (fn1) at (0,0.35) {$\left\{n\right\}$};
\node[bluepanel, minimum width=2.85cm, minimum height=0.68cm] (nn) at (0,-1.05) {$\left(a_1,\dots,a_n\right)$};
\node[greenpanel, minimum width=3.15cm, minimum height=0.68cm] (fnn) at (0,-2.25) {$\left\{a_1\nimsum\cdots\nimsum a_n\right\}$};
\draw[formulaarrow] (n1) -- node[right] {$F$} (fn1);
\draw[formulaarrow] (nn) -- node[right] {$F$} (fnn);
\end{tikzpicture}
\end{figure}
\end{column}
\end{columns}
\begin{proposition}[What changed conceptually?]
Instead of proving a mysterious xor identity by hand, we view it as the \icol{Rota--Baxter} image of a \dcol{differential} rule on games.
\end{proposition}
\end{frame}
\begin{frame}{Take-home messages}
\small
\begin{enumerate}
\item \textbf{Games are recursive \dcol{coalgebras}.} The basic game values come from hylomorphisms for $\Pf$.
\item \textbf{Box product has a \dcol{differential} flavor.} On pointed games / families, the option operator satisfies a \dcol{Leibniz} rule.
\item \textbf{Nim-sum is a \icol{Rota--Baxter} phenomenon.} The classical mex + xor identity is the \icol{integral} image of that Leibniz rule.
\end{enumerate}
\vspace{0.65em}
\begin{proposition}[Outlook]
Partisan / probabilistic variants, a genuine chain rule, and a systematic interface with differential categories remain open.
\end{proposition}
\end{frame}
\begin{frame}[allowframebreaks]{References}
\printbibliography[heading=none]
\end{frame}
\end{document}