\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}

% ---- 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}{\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{\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}
}

% ---- 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}
    
\end{frame}

\section{Nim and nim-sum}

\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{example}
    $5\nimsum 7 = (101)_2 \nimsum (111)_2 = (010)_2 = 2$
\end{example}
\begin{theorem}[{[Bouton, Ann. of Math., 1902]}]
    A state of $n$-heap nim $(a_1, \dots ,a_n)$ is winning 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.
\end{example}
\end{frame}

\begin{frame}{Why xor in Nim?}
\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.6em}
\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}

\vspace{0.2em}
\[
\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
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}

\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}

\vspace{0.4em}
\begin{columns}[T]
\begin{column}{0.5\textwidth}
\textbf{Example 1: one-heap Nim}
\[
\nu\colon \N\to \Pf(\N),\qquad
\nu(n)=\{0,1,\dots,n-1\}.
\]
Then $\G_{\mathrm{Nim}_1}=\mathrm{id}_{\N}$.
\end{column}
\begin{column}{0.48\textwidth}
\textbf{Example 2: terminal game}
\begin{itemize}
  \item underlying set: hereditarily finite sets $\Hf$;
  \item move relation: $A\to B$ iff $B\in A$;
  \item every game admits a unique map
  \[
  \mathrm{rd}_X\colon X\to \Hf.
  \]
\end{itemize}
\end{column}
\end{columns}


\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}
\begin{frame}{Table of Contents}
    \tableofcontents
\end{frame}
\section{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}