← rota-baxter-winning-games
DiffCatRIMS__AI-generated__nimsum_differential_games_beamer.tex
\documentclass[12pt,portrait,aspectratio=169]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb,mathtools}
\usepackage{array}
\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 ----
\newcommand{\dq}[1]{``#1''}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\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{\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}{\mathsf{I}}
\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{\rel}{\to}
\newcommand{\mono}{\rightarrowtail}
\newcommand{\epi}{\twoheadrightarrow}
\newcommand{\rd}{\mathsf{rd}}
\newcommand{\Id}{\mathrm{id}}
% theorem environments
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}
% ---- 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}
% ---- beamer style ----
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{items}[default]
\setbeamertemplate{theorems}[default]
\setbeamertemplate{blocks}[rounded][shadow=false]
\setbeamertemplate{footline}[frame number]
\setbeamercolor{title}{fg=myblue!85!black}
\setbeamercolor{frametitle}{fg=black,bg=myblue!10}
\setbeamercolor{block title}{fg=white,bg=myblue!85!black}
\setbeamercolor{block body}{bg=black!2}
\setbeamercolor{block title example}{fg=white,bg=mygreen!80!black}
\setbeamercolor{block body example}{bg=mylightgreen}
\setbeamercolor{block title alerted}{fg=white,bg=myred!80!black}
\setbeamercolor{block body alerted}{bg=mylightred}
\AtBeginSection[]
{
\begin{frame}
\frametitle{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
% ---- 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}
}
% ---- small helpers ----
\newcommand{\drawtwobits}[3]{%
\fill (#1+#2,#3) circle (1.7pt);
\fill (#1-#2,#3) circle (1.7pt);
}
\newcommand{\drawthreebits}[3]{%
\fill (#1-#2,#3+0.14) circle (1.7pt);
\fill (#1,#3-0.18) circle (1.7pt);
\fill (#1+#2,#3+0.14) circle (1.7pt);
}
\newcommand{\tinyheap}[3]{% x,y,stones 0..3
\draw[nimheap] (#1,#2) circle (0.28);
\ifnum#3=1
\fill (#1,#2) circle (1.8pt);
\fi
\ifnum#3=2
\drawtwobits{#1}{0.10}{#2}
\fi
\ifnum#3=3
\drawthreebits{#1}{0.11}{#2}
\fi
}
% ---- title ----
\title[A Rota--Baxter equation for winning games]{A Rota--Baxter Equation for Winning Games}
\subtitle{Why does nim-sum work?\\[0.15em]\small Because the category of games carries a differential structure.}
\author{Ryuya Hora}
\institute{Graduate School of Mathematical Sciences, The University of Tokyo}
\date{Differentiation in category theory and program semantics\\Kyoto University, April 6, 2026}
\begin{document}
\begin{frame}
\titlepage
\vspace{-0.55em}
\begin{center}
\small Partially based on joint work in progress with Ryo Suzuki.
\end{center}
\end{frame}
\begin{frame}{Where I come from}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.48\textwidth}
{\Large \textbf{Ryuya Hora}}\\[0.35em]
Recently I have been interested in\newline
\textbf{toposes, games, and coalgebras}.\\[0.8em]
\begin{itemize}
\item I come to this workshop mainly from \textbf{combinatorial game theory}.
\item My recurring question is:\newline
\emph{why does Nim know xor?}
\end{itemize}
\end{column}
\begin{column}{0.49\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=5.8cm, minimum height=3.55cm] (p) {};
\node[anchor=north west] at ($(p.north west)+(0.18,-0.18)$) {\scriptsize Generic search engine};
% Logo-ish letters
\node[font=\bfseries\Large, text=blue] at ($(p.north west)+(0.72,-0.75)$) {G};
\node[font=\bfseries\Large, text=red] at ($(p.north west)+(1.01,-0.75)$) {o};
\node[font=\bfseries\Large, text=orange!90!black] at ($(p.north west)+(1.26,-0.75)$) {o};
\node[font=\bfseries\Large, text=blue] at ($(p.north west)+(1.56,-0.75)$) {g};
\node[font=\bfseries\Large, text=green!70!black] at ($(p.north west)+(1.84,-0.75)$) {l};
\node[font=\bfseries\Large, text=red] at ($(p.north west)+(2.03,-0.75)$) {e};
\draw[rounded corners=8pt, draw=black!18, fill=white] ($(p.north west)+(2.45,-0.98)$) rectangle ($(p.north west)+(5.35,-0.48)$);
\node[anchor=west, text=black!70] at ($(p.north west)+(2.63,-0.73)$) {Recurison};
\foreach \x/\t in {1.35/Images,2.12/Examples,2.98/Formula,3.82/Videos,4.73/In programming} {
\draw[rounded corners=6pt, draw=black!16, fill=white] ($(p.north west)+(\x,-1.42)$) rectangle ++(0.78,0.31);
\node[font=\tiny] at ($(p.north west)+(\x+0.39,-1.265)$) {\t};
}
\draw[black!12] ($(p.north west)+(0.32,-1.80)$) -- ($(p.north west)+(5.48,-1.80)$);
\node[font=\scriptsize, text=black!55, anchor=west] at ($(p.north west)+(0.54,-2.08)$) {About 183,000,000 results (0.28 seconds)};
\node[font=\scriptsize, text=myred, anchor=west] at ($(p.north west)+(1.10,-2.46)$) {Did you mean:};
\node[font=\bfseries\scriptsize\itshape, text=myblue, anchor=west] at ($(p.north west)+(2.28,-2.46)$) {Recursion};
\node[note, anchor=south east, font=\scriptsize, text width=2.15cm] at ($(p.south east)+(-0.12,0.14)$) {Yes, that really happened while I was writing about recursion.};
\end{tikzpicture}
\end{column}
\end{columns}
\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.
\item I am one of the organizers of the \textbf{Japan Combinatorial Game Theory Workshop}.
\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.3em}
\begin{center}
\emph{So this talk is partly a mathematical proposal, and partly a request for orientation.}
\end{center}
\end{frame}
\begin{frame}{Short survey: games $\times$ category theory is not new}
\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}
\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.2em}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.48\textwidth}
\textbf{Part I (about 10 min)}
\begin{itemize}
\item games as \(\Pf\)-recursive coalgebras
\item game values as hylomorphisms
\item why backward recursion is well-defined
\end{itemize}
\end{column}
\begin{column}{0.48\textwidth}
\textbf{Part II (about 15 min)}
\begin{itemize}
\item a differential structure on pointed game families
\item Rota--Baxter valued invariants
\item \textbf{winning Nim with a Rota--Baxter equation}
\end{itemize}
\end{column}
\end{columns}
\vspace{0.3em}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=9.5cm, minimum height=0.95cm] (s) {};
\node at (s.center) {\emph{Key slogan: the Nim identity is an integral shadow of a Leibniz rule.}};
\end{tikzpicture}
\end{center}
\end{frame}
\section{Nim and nim-sum}
\begin{frame}{Rule of $n$-heap Nim}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.46\textwidth}
\begin{definition}[$n$-heap Nim]
An \emph{$n$-heap Nim position} is a tuple $(a_1,\dots,a_n)\in\N^n$.\newline
In one move, a player chooses \emph{exactly one} heap and removes \emph{one or more} stones from that heap.\newline
The player who cannot move loses.
\end{definition}
\vspace{0.5em}
\begin{block}{The point of the example}
Nim is the simplest place where the mysterious operation \(\nimsum\) already appears.
\end{block}
\end{column}
\begin{column}{0.52\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=5.85cm, minimum height=4.45cm] (panel) {};
\def\rowgap{0.78}
\def\cx{0.0}
\def\dx{1.0}
% row 0 (2,3,3)
\tinyheap{-1.85}{1.50}{2}
\tinyheap{-0.85}{1.50}{3}
\tinyheap{ 0.15}{1.50}{3}
\node[font=\scriptsize, anchor=west] at (0.60,1.50) {$(2,3,3)$};
% row1 (2,3,1)
\tinyheap{-1.85}{0.72}{2}
\tinyheap{-0.85}{0.72}{3}
\tinyheap{ 0.15}{0.72}{1}
\node[font=\scriptsize, anchor=west] at (0.60,0.72) {$(2,3,1)$};
\draw[heapedge] (-0.85,1.18) -- (-0.85,1.00) node[midway,right, font=\scriptsize, text=myred] {A};
% row2 (1,3,1)
\tinyheap{-1.85}{-0.06}{1}
\tinyheap{-0.85}{-0.06}{3}
\tinyheap{ 0.15}{-0.06}{1}
\node[font=\scriptsize, anchor=west] at (0.60,-0.06) {$(1,3,1)$};
\draw[heapedge] (-0.85,0.40) -- (-0.85,0.22) node[midway,right, font=\scriptsize, text=myblue] {B};
% row3 (1,0,1)
\tinyheap{-1.85}{-0.84}{1}
\tinyheap{-0.85}{-0.84}{0}
\tinyheap{ 0.15}{-0.84}{1}
\node[font=\scriptsize, anchor=west] at (0.60,-0.84) {$(1,0,1)$};
\draw[heapedge] (-0.85,-0.38) -- (-0.85,-0.56) node[midway,right, font=\scriptsize, text=myred] {A};
% row4 (1,0,0)
\tinyheap{-1.85}{-1.62}{1}
\tinyheap{-0.85}{-1.62}{0}
\tinyheap{ 0.15}{-1.62}{0}
\node[font=\scriptsize, anchor=west] at (0.60,-1.62) {$(1,0,0)$};
\draw[heapedge] (-0.85,-1.16) -- (-0.85,-1.34) node[midway,right, font=\scriptsize, text=myblue] {B};
% row5 (0,0,0)
\tinyheap{-1.85}{-2.40}{0}
\tinyheap{-0.85}{-2.40}{0}
\tinyheap{ 0.15}{-2.40}{0}
\node[font=\scriptsize, anchor=west] at (0.60,-2.40) {$(0,0,0)$};
\draw[heapedge] (-0.85,-1.94) -- (-0.85,-2.12) node[midway,right, font=\scriptsize, text=myred] {A};
\node[font=\scriptsize, text=black!65] at (0.0,2.02) {A typical play in $3$-heap Nim};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Bouton's theorem}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
\scriptsize
\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\overset{\simeq}{\longrightarrow}\bigoplus_{k\ge 0}\Z/2\Z.
\]
\end{definition}
\begin{theorem}[Bouton \parencite{bouton1901nim}]
For an $n$-heap Nim position $(a_1,\dots,a_n)$,
\[
(a_1,\dots,a_n)\text{ is a }P\text{-position}
\iff
a_1\nimsum\cdots\nimsum a_n=0.
\]
\end{theorem}
\vspace{0.15em}
\centering
\footnotesize Example: \(5\nimsum 7=(101)_2\nimsum(111)_2=(010)_2=2\).
\end{column}
\begin{column}{0.40\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.6cm, minimum height=4.55cm] (panel) {};
\node[font=\small\bfseries, text=myblue] at (0,1.65) {Binary xor};
\node[font=\normalsize, anchor=east] at (-0.55,0.95) {$5=$};
\node at (0.15,0.95) {$1$};
\node at (0.60,0.95) {$0$};
\node at (1.05,0.95) {$1$};
\node[font=\normalsize, anchor=east] at (-0.55,0.40) {$7=$};
\node at (0.15,0.40) {$1$};
\node at (0.60,0.40) {$1$};
\node at (1.05,0.40) {$1$};
\node[font=\normalsize, anchor=east, text=myred] at (-0.62,-0.15) {$\nimsum$};
\draw[line width=0.9pt] (-0.90,-0.33) -- (1.30,-0.33);
\node[font=\normalsize, anchor=east] at (-0.55,-0.70) {$2=$};
\node[text=myblue] at (0.15,-0.70) {$0$};
\node[text=myblue] at (0.60,-0.70) {$1$};
\node[text=myblue] at (1.05,-0.70) {$0$};
\node[font=\scriptsize, text width=3.7cm, align=center] at (0,-1.70) {Bouton's theorem says that this xor controls the winning and losing positions of Nim.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Why xor in Nim?}
\small
\begin{itemize}
\item Bouton's theorem says that an $n$-heap Nim position $(a_1,\dots,a_n)$ is a $P$-position iff
\[
a_1\nimsum \cdots \nimsum a_n = 0.
\]
\item Once the theorem is known, the proof is classical \parencite{bouton1901nim,siegel2013combinatorial}.
\item But conceptually, why should \emph{xor} appear at all?
\end{itemize}
\vspace{0.45em}
\begin{alertblock}{My answer today}
First isolate the \emph{recursive} nature of games, then reinterpret the key Nim identity as a \emph{Rota--Baxter equation}.
\end{alertblock}
\vspace{0.1em}
\[
\mex(S)\nimsum \mex(T)
= \mex\bigl((\mex(S)\nimsum T)\cup (S\nimsum \mex(T))\bigr).
\]
\end{frame}
\section{Games as recursive coalgebras}
\begin{frame}{Games are recursive objects}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.57\textwidth}
\begin{definition}[Game]
A \emph{(short impartial) game} is a directed graph $(X,\to)$ such that:
\begin{enumerate}
\item each position has finitely many options;
\item there is no infinite play.
\end{enumerate}
\end{definition}
\vspace{0.35em}
Typical quantities are defined \emph{backwards from the options}.
\begin{block}{Idea}
Games are exactly the graphs on which such backward recursions are always well-defined.
\end{block}
\end{column}
\begin{column}{0.40\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.5cm, minimum height=4.55cm] (p) {};
% nodes
\node[neutralstate] (a) at (-1.30,1.55) {};
\node[neutralstate] (b) at (-0.45,0.85) {};
\node[neutralstate] (c) at (0.45,0.95) {};
\node[neutralstate] (d) at (1.25,0.40) {};
\node[neutralstate] (e) at (-0.95,-0.05) {};
\node[neutralstate] (f) at (0.05,0.00) {};
\node[neutralstate] (g) at (0.95,-0.25) {};
\node[neutralstate] (h) at (-0.45,-1.05) {};
\node[neutralstate] (i) at (0.55,-1.15) {};
\node[neutralstate] (j) at (-1.20,-1.90) {};
\node[neutralstate] (k) at (0.00,-1.95) {};
\node[neutralstate] (l) at (1.10,-1.85) {};
\foreach \u/\v in {a/b,a/c,a/d,b/e,b/f,c/f,c/g,d/g,e/h,f/h,f/i,g/i,h/j,h/k,i/k,i/l,e/j,f/k,g/l}{\draw[gameedge] (\u) -- (\v);}
\node[font=\scriptsize, text width=3.8cm, align=center] at (0,-2.55) {A game is a finite-branching directed acyclic graph.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Outcome: winning and losing positions}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
\begin{definition}[Outcome]
For a game $(X,\to)$ and a position $x\in X$, define
\[
\oc(x)=
\begin{cases}
N & \text{if some option }x'\text{ has value }\oc(x')=P,\\
P & \text{otherwise.}
\end{cases}
\]
\end{definition}
\vspace{0.35em}
\begin{remark}
The definition is recursive, but it is well-founded because the game has no infinite play.
\end{remark}
\end{column}
\begin{column}{0.40\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.5cm, minimum height=4.55cm] (p) {};
% nodes
\node[nstate] (a) at (-1.30,1.55) {};
\node[pstate] (b) at (-0.45,0.85) {};
\node[pstate] (c) at (0.45,0.95) {};
\node[nstate] (d) at (1.25,0.40) {};
\node[nstate] (e) at (-0.95,-0.05) {};
\node[pstate] (f) at (0.05,0.00) {};
\node[pstate] (g) at (0.95,-0.25) {};
\node[nstate] (h) at (-0.45,-1.05) {};
\node[nstate] (i) at (0.55,-1.15) {};
\node[pstate] (j) at (-1.20,-1.90) {};
\node[pstate] (k) at (0.00,-1.95) {};
\node[pstate] (l) at (1.10,-1.85) {};
\foreach \u/\v in {a/b,a/c,a/d,b/e,b/f,c/f,c/g,d/g,e/h,f/h,f/i,g/i,h/j,h/k,i/k,i/l,e/j,f/k,g/l}{\draw[gameedge] (\u) -- (\v);}
\foreach \x/\lab/\dx/\dy in {a/N/0.12/0.10,b/P/-0.14/0.10,c/P/0.14/0.10,d/N/0.15/0.12,e/N/-0.18/0.10,f/P/0.15/0.12,g/P/0.16/0.10,h/N/-0.16/0.10,i/N/0.18/0.10,j/P/-0.12/0.12,k/P/0.14/0.12,l/P/0.16/0.10}{
\node[font=\scriptsize\bfseries, text=\ifx\lab P myblue\else myred\fi] at ($(\x)+(\dx,\dy)$) {\lab};
}
\node[font=\scriptsize, text width=3.7cm, align=center] at (0,-2.55) {Blue = $P$-positions, red = $N$-positions.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Grundy number}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.56\textwidth}
\begin{definition}[mex]
For a finite subset $S\subset\N$, its \emph{mex} is
\[
\mex(S)\coloneqq \min(\N\setminus S).
\]
\end{definition}
\begin{definition}[Grundy number]
For a game $(X,\to)$ and a position $x\in X$, its \emph{Grundy number} is
\[
\G(x)=\mex\{\G(x')\mid x\to x'\}.
\]
\end{definition}
\begin{proposition}
A position is a $P$-position if and only if its Grundy number is $0$.
\end{proposition}
\end{column}
\begin{column}{0.40\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.5cm, minimum height=4.55cm] (p) {};
% nodes
\node[neutralstate] (a) at (-1.30,1.55) {};
\node[neutralstate] (b) at (-0.45,0.85) {};
\node[neutralstate] (c) at (0.45,0.95) {};
\node[neutralstate] (d) at (1.25,0.40) {};
\node[neutralstate] (e) at (-0.95,-0.05) {};
\node[neutralstate] (f) at (0.05,0.00) {};
\node[neutralstate] (g) at (0.95,-0.25) {};
\node[neutralstate] (h) at (-0.45,-1.05) {};
\node[neutralstate] (i) at (0.55,-1.15) {};
\node[neutralstate] (j) at (-1.20,-1.90) {};
\node[neutralstate] (k) at (0.00,-1.95) {};
\node[neutralstate] (l) at (1.10,-1.85) {};
\foreach \u/\v in {a/b,a/c,a/d,b/e,b/f,c/f,c/g,d/g,e/h,f/h,f/i,g/i,h/j,h/k,i/k,i/l,e/j,f/k,g/l}{\draw[gameedge] (\u) -- (\v);}
\foreach \x/\lab/\dx/\dy in {a/3/0.12/0.12,b/1/-0.14/0.10,c/1/0.14/0.10,d/0/0.15/0.12,e/2/-0.18/0.10,f/0/0.15/0.12,g/0/0.16/0.10,h/1/-0.16/0.10,i/1/0.18/0.10,j/0/-0.12/0.12,k/0/0.14/0.12,l/0/0.16/0.10}{
\node[font=\scriptsize\bfseries] at ($(\x)+(\dx,\dy)$) {\lab};
}
\foreach \x/\dx/\dy in {d/0.15/0.12,f/0.15/0.12,g/0.16/0.10,j/-0.12/0.12,k/0.14/0.12,l/0.16/0.10}{
\node[font=\scriptsize\bfseries, text=myred] at ($(\x)+(\dx,\dy)$) {0};
}
\node[font=\scriptsize, text width=3.8cm, align=center] at (0,-2.55) {The numbers are computed backwards by repeated mex.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Conway addition of games}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.58\textwidth}
\begin{definition}[Conway addition]
For games $X=(X,\to_X)$ and $Y=(Y,\to_Y)$, the \emph{Conway sum} $X+Y$ is the game on $X\times Y$ defined by
\[
(x,y)\to_{+}(x',y')
\iff
(x\to_X x'\ \wedge\ y=y')\ \vee\ (x=x'\ \wedge\ y\to_Y y').
\]
\end{definition}
\begin{example}
\[
\mathrm{Nim}_n = \mathrm{Nim}_1 + \cdots + \mathrm{Nim}_1.
\]
\end{example}
\end{column}
\begin{column}{0.38\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.15cm, minimum height=4.45cm] (p) {};
% X chain
\node at (-1.25,1.75) {$X$};
\foreach \i/\y in {0/1.25,1/0.65,2/0.05} {
\node[neutralstate] (x\i) at (-1.25,\y) {};
}
\draw[gameedge] (x0) -- (x1);
\draw[gameedge] (x1) -- (x2);
% Y chain
\node at (1.25,1.75) {$Y$};
\foreach \i/\y in {0/1.25,1/0.65,2/0.05} {
\node[neutralstate] (y\i) at (1.25,\y) {};
}
\draw[gameedge] (y0) -- (y1);
\draw[gameedge] (y1) -- (y2);
\node[font=\large] at (0.0,0.75) {$+$};
% product grid
\node at (0,-0.55) {$X+Y$};
\foreach \i/\x in {0/-1.15,1/0,2/1.15} {
\foreach \j/\y in {0/-1.05,1/-1.75,2/-2.45} {
\node[neutralstate] (p\i\j) at (\x,\y) {};
}
}
% horizontal and vertical arrows in grid
\foreach \j in {0,1,2} {
\draw[gameedge] (p0\j) -- (p1\j);
\draw[gameedge] (p1\j) -- (p2\j);
}
\foreach \i in {0,1,2} {
\draw[gameedge] (p\i0) -- (p\i1);
\draw[gameedge] (p\i1) -- (p\i2);
}
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Coalgebra--algebra morphisms package the recursion}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.55\textwidth}
\begin{definition}[$\Pf$-coalgebra and $\Pf$-algebra]
A \(\Pf\)-coalgebra is a map
\[
\thetaf\colon X\to \Pf(X),
\qquad
x\mapsto \{x'\mid x\to x'\}.
\]
A \(\Pf\)-algebra is a map \(\alpha\colon\Pf(A)\to A\).
\end{definition}
\begin{definition}[Coalgebra--algebra morphism]
A map $f\colon X\to A$ is a \emph{coalgebra--algebra morphism} if
\[
f(x)=\alpha\bigl(\{f(x')\mid x\to x'\}\bigr)
\]
for every $x\in X$.
\end{definition}
\end{column}
\begin{column}{0.42\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.45cm, minimum height=4.55cm] (p) {};
\begin{scope}[shift={(0,0.15)}]
\node (px) at (-1.15,0.55) {$\Pf(X)$};
\node (pa) at (1.15,0.55) {$\Pf(A)$};
\node (x) at (-1.15,-1.00) {$X$};
\node (a) at (1.15,-1.00) {$A$};
\draw[formulaarrow] (x) -- node[left] {$\thetaf$} (px);
\draw[formulaarrow] (px) -- node[above] {$\Pf(f)$} (pa);
\draw[formulaarrow] (pa) -- node[right] {$\alpha$} (a);
\draw[formulaarrow] (x) -- node[below] {$f$} (a);
\node[text=myred, font=\scriptsize, align=center] at (0,-2.05) {This one square encodes\\all the backward recursions we use in game theory.};
\end{scope}
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}[t]{Main statement of Part I}
\small
\begin{theorem}[Games as recursive coalgebras]
The category of games is (isomorphic to) the category of recursive \(\Pf\)-coalgebras:
\[
\Gs \simeq \mathsf{RecCoalg}_{\Pf}.
\]
\end{theorem}
\vspace{0.35em}
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.47\textwidth}
\begin{example}[One-heap Nim]
\[
\nu\colon \N\to \Pf(\N),
\qquad
\nu(n)=\{0,1,\dots,n-1\}.
\]
Then
\[
\G_{\mathrm{Nim}_1}=\Id_{\N}.
\]
\end{example}
\end{column}
\begin{column}{0.49\textwidth}
{\scriptsize
\begin{example}[Terminal game]
\begin{itemize}
\item underlying set: \(\Hf\),
\item move relation: \(A\to B\) iff \(B\in A\),
\item every game has a unique map \(\rd_X\colon X\to \Hf\).
\end{itemize}
\end{example}
}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Game values are hylomorphisms}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.57\textwidth}
\begin{center}
\renewcommand{\arraystretch}{1.25}
\begin{tabular}{>{\raggedright\arraybackslash}p{0.42\textwidth}|>{\raggedright\arraybackslash}p{0.38\textwidth}}
\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.45em}
\begin{proposition}
A game morphism preserves every recursively defined invariant coming from a \(\Pf\)-algebra.
\end{proposition}
\end{column}
\begin{column}{0.39\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.25cm, minimum height=4.15cm] (p) {};
% left game
\node[nstate] (x0) at (-1.20,1.10) {};
\node[pstate] (x1) at (-1.60,0.20) {};
\node[pstate] (x2) at (-0.80,0.20) {};
\node[nstate] (x3) at (-1.20,-0.70) {};
\draw[gameedge] (x0)--(x1);
\draw[gameedge] (x0)--(x2);
\draw[gameedge] (x1)--(x3);
\draw[gameedge] (x2)--(x3);
% right game
\node[nstate] (y0) at (1.10,1.10) {};
\node[pstate] (y1) at (1.10,0.20) {};
\node[nstate] (y2) at (1.10,-0.70) {};
\draw[gameedge] (y0)--(y1);
\draw[gameedge] (y1)--(y2);
\draw[formulaarrow] (x0) -- node[above, font=\scriptsize] {$f$} (y0);
\draw[formulaarrow] (x1) -- (y1);
\draw[formulaarrow] (x2) -- (y1);
\draw[formulaarrow] (x3) -- (y2);
\node[font=\scriptsize, text width=3.7cm, align=center] at (0,-1.55) {If a map preserves the game structure, it preserves recursive game values.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\section{Differential structure and Rota--Baxter invariants}
\begin{frame}{Move to pointed games and finite families}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.55\textwidth}
\begin{definition}[Pointed games and finite families]
A \emph{pointed game} is a pair $(X,x)$ of a game and a chosen starting position.\newline
Let $\Gsp$ be the category of pointed games, and let $\Fam(\Gsp)$ be its free finite-coproduct completion.
\end{definition}
\vspace{0.35em}
An object of $\Fam(\Gsp)$ should be thought of as a
\[
\text{finite family of local game situations}.
\]
The two basic operations are
\[
\sqcup \quad\text{(disjoint union of families)},
\qquad
\otimes \quad\text{(gamewise Conway addition)}.
\]
\end{column}
\begin{column}{0.41\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.5cm, minimum height=4.5cm] (p) {};
% pointed game box 1
\node[familybox, minimum width=1.45cm, minimum height=1.3cm] (g1) at (-1.10,1.00) {};
\node[nstate] (a0) at (-1.10,1.28) {};
\node[pstate] (a1) at (-1.35,0.72) {};
\node[pstate] (a2) at (-0.85,0.72) {};
\draw[gameedge] (a0) -- (a1);
\draw[gameedge] (a0) -- (a2);
\draw[myorange, line width=1.5pt] (a0) circle (0.16);
% box 2
\node[familybox, minimum width=1.45cm, minimum height=1.3cm] (g2) at (1.05,1.00) {};
\node[nstate] (b0) at (1.05,1.28) {};
\node[pstate] (b1) at (1.05,0.72) {};
\draw[gameedge] (b0) -- (b1);
\draw[myorange, line width=1.5pt] (b0) circle (0.16);
\node[font=\Large] at (0,0.98) {$\sqcup$};
% family result
\node[familybox, minimum width=3.55cm, minimum height=1.45cm] (fam) at (0,-1.00) {};
\node[font=\scriptsize] at (0,-0.15) {$\Fam(\Gsp)$};
\node[font=\scriptsize, text width=3.6cm, align=center] at (0,-1.63) {A family remembers several local game situations at once.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{A differential operator on pointed game families}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.54\textwidth}
\begin{definition}[Differential operator]
For a pointed game $(X,x)$, define
\[
\dd(X,x)\coloneqq\{(X,x')\}_{x\to x'}.
\]
Then extend $\dd$ to finite families by finite coproducts.
\end{definition}
\vspace{0.4em}
\begin{block}{Interpretation}
The derivative of a local game situation is the \emph{family of all immediate options}.
\end{block}
\end{column}
\begin{column}{0.42\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.55cm, minimum height=4.5cm] (p) {};
% source pointed game
\node[familybox, minimum width=1.55cm, minimum height=1.45cm] (src) at (0,1.25) {};
\node[nstate] (s0) at (0,1.55) {};
\node[pstate] (s1) at (-0.35,0.95) {};
\node[pstate] (s2) at (0.35,0.95) {};
\draw[gameedge] (s0)--(s1);
\draw[gameedge] (s0)--(s2);
\draw[myorange, line width=1.5pt] (s0) circle (0.16);
\node[font=\Large, text=myblue] at (0,0.20) {$\dd$};
% result family
\node[familybox, minimum width=1.4cm, minimum height=1.1cm] (r1) at (-1.05,-1.15) {};
\node[pstate] (t1) at (-1.05,-0.95) {};
\draw[myorange, line width=1.5pt] (t1) circle (0.16);
\node[familybox, minimum width=1.4cm, minimum height=1.1cm] (r2) at (1.05,-1.15) {};
\node[pstate] (t2) at (1.05,-0.95) {};
\draw[myorange, line width=1.5pt] (t2) circle (0.16);
\draw[formulaarrow] (-0.20,0.55) -- (-0.83,-0.60);
\draw[formulaarrow] (0.20,0.55) -- (0.83,-0.60);
\node[font=\scriptsize, text width=3.6cm, align=center] at (0,-1.90) {Differentiate = list all one-step moves.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Leibniz rule for Conway addition}
\small
For the Conway sum, a move changes \emph{either} the left component \emph{or} the right component.
\vspace{0.35em}
\begin{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{theorem}
\vspace{0.35em}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=8.8cm, minimum height=3.6cm] (p) {};
% Left chain X
\node at (-3.10,1.15) {$X$};
\node[neutralstate] (x0) at (-3.10,0.55) {};
\node[neutralstate] (x1) at (-3.10,-0.15) {};
\node[neutralstate] (x2) at (-3.10,-0.85) {};
\draw[gameedge] (x0)--(x1); \draw[gameedge] (x1)--(x2);
% Right chain Y
\node at (3.10,1.15) {$Y$};
\node[neutralstate] (y0) at (3.10,0.55) {};
\node[neutralstate] (y1) at (3.10,-0.15) {};
\node[neutralstate] (y2) at (3.10,-0.85) {};
\draw[gameedge] (y0)--(y1); \draw[gameedge] (y1)--(y2);
% middle product board
\node at (0,1.15) {$X\otimes Y$};
\foreach \i/\x in {0/-0.90,1/0.0,2/0.90} {
\foreach \j/\y in {0/0.55,1/-0.15,2/-0.85} {
\node[neutralstate] (p\i\j) at (\x,\y) {};
}
}
\foreach \j in {0,1,2} {\draw[gameedge] (p0\j)--(p1\j); \draw[gameedge] (p1\j)--(p2\j);}
\foreach \i in {0,1,2} {\draw[gameedge] (p\i0)--(p\i1); \draw[gameedge] (p\i1)--(p\i2);}
% highlight one source point and outgoing moves
\draw[myorange, line width=1.5pt] (p11) circle (0.16);
\draw[myred, line width=1.45pt, ->] (p11) -- (p01);
\draw[myred, line width=1.45pt, ->] (p11) -- (p10);
\node[text=myred, font=\scriptsize] at (-0.38,0.18) {move in $X$};
\node[text=myred, font=\scriptsize] at (0.48,0.18) {move in $Y$};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Decategorification target: differential, integral, calculus rigs}
\small
\begin{definition}[Differential rig]
A \emph{differential rig} is a rig $(A,0,1,+,\times,\dd)$ such that
\[
\dd(a+b)=\dd a+\dd b,
\qquad
\dd(ab)=(\dd a)b+a(\dd b).
\]
\end{definition}
\begin{definition}[Integral / Rota--Baxter rig]
An \emph{integral rig} has an operator \(\Int\) satisfying
\[
1=\Int 0,
\qquad
(\Int f)(\Int g)=\Int\bigl((\Int f)g+f(\Int g)\bigr).
\]
\end{definition}
\begin{definition}[Calculus rig]
A \emph{calculus rig} has both structures, related by the fundamental theorem
\[
\dd\,\Int f=f.
\]
\end{definition}
\end{frame}
\begin{frame}{Rota--Baxter valued invariants of games}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.60\textwidth}
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.35em}
\begin{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{theorem}
\end{column}
\begin{column}{0.36\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=3.95cm, minimum height=4.3cm] (p) {};
\node[familybox, minimum width=1.35cm, minimum height=1.25cm] (gx) at (0,1.30) {};
\node[nstate] (u0) at (0,1.58) {};
\node[pstate] (u1) at (-0.28,1.00) {};
\node[pstate] (u2) at (0.28,1.00) {};
\draw[gameedge] (u0)--(u1);
\draw[gameedge] (u0)--(u2);
\draw[myorange, line width=1.5pt] (u0) circle (0.16);
\draw[formulaarrow] (0,0.68) -- (0,-0.05);
\node[font=\large, text=myblue] at (0,0.25) {$F$};
\node[draw=mygreen!70!black, fill=mylightgreen, rounded corners=4pt, minimum width=2.30cm, minimum height=0.90cm] (alg) at (0,-0.75) {$A$};
\node[font=\scriptsize, text width=3.1cm, align=center] at (0,-1.78) {Game families are sent to algebraic invariants satisfying a Rota--Baxter product rule.};
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{The universal example: game families themselves}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.50\textwidth}
\begin{block}{Dictionary}
\[
\begin{aligned}
0 &\leftrightarrow \text{empty family},\\
1 &\leftrightarrow \text{terminal pointed game},\\
+ &\leftrightarrow \text{disjoint union},\\
\times &\leftrightarrow \text{gamewise Conway sum},\\
\dd &\leftrightarrow \text{all immediate options},\\
\Int &\leftrightarrow \text{adjoin a new root}.
\end{aligned}
\]
\end{block}
\end{column}
\begin{column}{0.46\textwidth}
\centering
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=4.45cm, minimum height=4.45cm] (p) {};
% derivative picture
\node[familybox, minimum width=1.15cm, minimum height=1.05cm] (a) at (-1.05,1.20) {};
\node[nstate] (a0) at (-1.05,1.42) {};
\node[pstate] (a1) at (-1.27,0.98) {};
\node[pstate] (a2) at (-0.83,0.98) {};
\draw[gameedge] (a0)--(a1); \draw[gameedge] (a0)--(a2);
\draw[myorange, line width=1.5pt] (a0) circle (0.15);
\node[text=myblue, font=\small\bfseries] at (0.88,1.28) {$\dd$};
\node[familybox, minimum width=0.92cm, minimum height=0.78cm] (b) at (0.52,1.20) {};
\node[pstate] (b1) at (0.52,1.32) {};
\draw[myorange, line width=1.2pt] (b1) circle (0.14);
\node[familybox, minimum width=0.92cm, minimum height=0.78cm] (c) at (1.62,1.20) {};
\node[pstate] (c1) at (1.62,1.32) {};
\draw[myorange, line width=1.2pt] (c1) circle (0.14);
\draw[formulaarrow] (-0.42,1.08) -- (0.05,1.18);
\draw[formulaarrow] (-0.22,0.92) -- (1.16,1.08);
% integral picture
\node[text=mygreen!70!black, font=\small\bfseries] at (-1.40,-0.05) {$\Int$};
\node[familybox, minimum width=1.25cm, minimum height=0.95cm] (d) at (-0.45,-0.10) {};
\node[pstate] (d1) at (-0.68,-0.02) {};
\node[pstate] (d2) at (-0.22,-0.02) {};
\draw[myorange, line width=1.2pt] (d1) circle (0.14);
\draw[myorange, line width=1.2pt] (d2) circle (0.14);
\node[familybox, minimum width=1.35cm, minimum height=1.25cm] (e) at (1.05,-0.15) {};
\node[nstate] (e0) at (1.05,0.12) {};
\node[pstate] (e1) at (0.82,-0.38) {};
\node[pstate] (e2) at (1.28,-0.38) {};
\draw[gameedge] (e0)--(e1); \draw[gameedge] (e0)--(e2);
\draw[myorange, line width=1.5pt] (e0) circle (0.15);
\draw[formulaarrow] (0.18,-0.10) -- (0.38,-0.10);
% multiplication picture
\node[text=myred, font=\small\bfseries] at (-1.45,-1.62) {$\otimes$};
\node[familybox, minimum width=0.90cm, minimum height=0.70cm] (f) at (-0.80,-1.62) {};
\node[neutralstate] at (-0.80,-1.52) {};
\node[familybox, minimum width=0.90cm, minimum height=0.70cm] (g) at (0.10,-1.62) {};
\node[neutralstate] at (0.10,-1.52) {};
\node[familybox, minimum width=1.35cm, minimum height=1.05cm] (h) at (1.30,-1.62) {};
\foreach \i/\x in {0/1.05,1/1.55} {
\foreach \j/\y in {0/-1.42,1/-1.82} {\node[neutralstate] at (\x,\y) {};}
}
\draw[formulaarrow] (-0.28,-1.62) -- (0.55,-1.62);
\end{tikzpicture}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Nim-sum gives a concrete Rota--Baxter rig}
\small
\begin{definition}[A concrete integral rig from Nim]
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)\}.
\]
\end{definition}
\begin{theorem}
This makes $\Pf(\N)$ into an integral (Rota--Baxter) rig.
\end{theorem}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=8.7cm, minimum height=1.05cm] (p) {};
\node[text=myblue, font=\bfseries] at (-3.35,0) {$\Pf(\N)$};
\node[text=mygreen!70!black, font=\bfseries] at (-1.20,0) {$+$ = union};
\node[text=myred, font=\bfseries] at (1.25,0) {$\times$ = xor product};
\node[text=mypurple, font=\bfseries] at (3.50,0) {$\Int(S)=\{\mex(S)\}$};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{The key identity is exactly a Rota--Baxter equation}
\small
\begin{columns}[T,totalwidth=\textwidth]
\begin{column}{0.49\textwidth}
\begin{block}{Rota--Baxter identity in $\Pf(\N)$}
\[
(\Int S)(\Int T)
=
\Int\bigl((\Int S)T+S(\Int T)\bigr).
\]
\end{block}
\vspace{0.2em}
Expanding the product means xor-ing every element.
\end{column}
\begin{column}{0.49\textwidth}
\begin{alertblock}{Classical Nim identity}
{\footnotesize
\[
\begin{aligned}
\mex(S)\nimsum\mex(T)
&=\mex\Bigl((\mex(S)\nimsum T)\\
&\qquad\cup(S\nimsum\mex(T))\Bigr).
\end{aligned}
\]
}
\end{alertblock}
\vspace{0.2em}
This is exactly the same equation, after unpacking \(\Int(S)=\{\mex(S)\}\).
\end{column}
\end{columns}
\vspace{0.35em}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[panel, minimum width=8.2cm, minimum height=0.95cm] (p) {};
\node at (0,0) {\textbf{Leibniz rule on games} $\Longrightarrow$ \textbf{Rota--Baxter equation on invariants} $\Longrightarrow$ \textbf{nim-sum identity}};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Recovering Bouton's theorem}
\small
\begin{proposition}
Applying the previous construction to pointed Nim positions recovers Bouton's theorem.
\end{proposition}
\vspace{0.45em}
\begin{center}
\begin{tikzpicture}[x=1cm,y=1cm]
\node[draw=myblue!80!black, fill=mylightblue, rounded corners=4pt, minimum width=2.4cm, minimum height=0.9cm] (a) at (-3.45,0.25) {one-heap Nim};
\node[draw=mygreen!70!black, fill=mylightgreen, rounded corners=4pt, minimum width=2.0cm, minimum height=0.9cm] (b) at (-0.95,0.25) {$F(n)=\{n\}$};
\node[draw=myorange!85!black, fill=yellow!14, rounded corners=4pt, minimum width=2.6cm, minimum height=0.9cm] (c) at (1.80,0.25) {$n$ heaps = Conway sum};
\node[draw=myred!80!black, fill=mylightred, rounded corners=4pt, minimum width=2.6cm, minimum height=0.9cm] (d) at (4.55,0.25) {$a_1\nimsum\cdots\nimsum a_n$};
\draw[formulaarrow] (a) -- node[above, font=\scriptsize] {$\G=\Id_{\N}$} (b);
\draw[formulaarrow] (b) -- node[above, font=\scriptsize] {product rule} (c);
\draw[formulaarrow] (c) -- node[above, font=\scriptsize] {Rota--Baxter / xor} (d);
\node[draw=myblue!70!black, fill=mylightblue, rounded corners=6pt, minimum width=7.9cm, minimum height=1.05cm] (e) at (0.55,-1.35) {$P$-position $\iff a_1\nimsum\cdots\nimsum a_n=0$};
\end{tikzpicture}
\end{center}
\vspace{0.25em}
\begin{alertblock}{Conceptual answer}
It is not that xor magically appears from nowhere. It is the algebraic shadow of the differential structure satisfied by the game rules.
\end{alertblock}
\end{frame}
\begin{frame}{Take-home messages}
\small
\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 and finite families, the option operator satisfies a Leibniz rule.
\item \textbf{Nim-sum is a Rota--Baxter phenomenon.}
The classical \(\mex\) + xor identity is the algebraic image of that Leibniz rule.
\end{enumerate}
\vspace{0.45em}
\begin{alertblock}{Answer to the opening question}
\textbf{Q.} Why does Nim-sum work?\qquad
\textbf{A.} It comes from the differential structure satisfied by the game rules.
\end{alertblock}
\vspace{0.25em}
{\footnotesize \textbf{Outlook.} Partisan / probabilistic variants, a genuine chain rule, and a systematic interface with differential categories remain open.}
\end{frame}
\begin{frame}[allowframebreaks]{References}
\printbibliography[heading=none]
\end{frame}
\end{document}