# Strong Shift Equivalence and Bialgebras in traced monoidal categories

Emmanuel Jeandel

► To cite this version:

Emmanuel Jeandel. Strong Shift Equivalence and Bialgebras in traced monoidal categories. The 5th International Conference on Applied Category Theory 2022, 2022, Strathclyde, United Kingdom. hal-04318123

HAL Id: hal-04318123

https://inria.hal.science/hal-04318123v1

Submitted on 1 Dec 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Strong Shift Equivalence and Bialgebras in traced monoidal categories

arXiv:2107.10734

E. Jeandel

Université de Lorraine, France
<figure><img src="image_2.png" /></figure>

Symbolic Dynamics

<figure><img src="image_3.png" /></figure>

Categories for symbolic dynamics

<figure><img src="image_4.png" /></figure>

Applications

<figure><img src="image_5.png" /></figure>

Conclusion
# Edge shift

An edge shift is the set of all biinfinite walks (on edges) in a finite graph

<figure><img src="image_6.png" /></figure>
# Edge shift

An edge shift is the set of all biinfinite walks (on edges) in a finite graph

<figure><img src="image_7.png" /></figure>
An edge shift is the set of all biinfinite walks (on edges) in a finite graph

<figure><img src="image_8.png" /></figure>

... actactactact. actactactact ...

... teamteam. teamteam ...

... eeeeeeee. eeeeeeee ...

... actactactact. eeeeeeee ...

... actamteacte. amtamteact ...
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_9.png" /></figure>
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_10.png" /></figure>

use different symbols for *a*
depending on the next symbol.

$ac \rightarrow ac$

$am \rightarrow bm$
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_11.png" /></figure>

use different symbols for *a* depending on the next symbol.

$$ac \to ac$$

$$am \to bm$$
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_12.png" /></figure>

use same symbols for $c$ and $m$

$$ac \to ac$$

$$bm \to bc$$
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_13.png" /></figure>

use same symbols for $c$ and $m$

$$ac \to ac$$

$$bm \to bc$$
Edge shifts are conjugate if they're isomorphic via local transformations

<figure><img src="image_14.png" /></figure>

More generally, choose a vertex to duplicate

* Duplicate the inputs

* Redistribute the outputs or vice-versa
This can be defined directly on adjacency matrices:

Definition

Two matrices $M$ and $N$ are 1-step equivalent if $M = RS$ and $N = SR$
for (nonnecessarily square) nonnegative integral matrices $R, S$
This can be defined directly on adjacency matrices:

## Definition

Two matrices *M* and *N* are 1-step equivalent if *M* = *RS* and *N* = *SR* for (necessarily square) nonnegative integral matrices *R*, *S*

Example:

$$ M = \begin{pmatrix} 0 & 2 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} \quad N = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 \end{pmatrix} $$

$$ R = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \quad S = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 1 \end{pmatrix} $$
This can be defined directly on adjacency matrices:

## Definition

Two matrices $M$ and $N$ are 1-step equivalent if $M = RS$ and $N = SR$ for (necessarily square) nonnegative integral matrices $R, S$

## Definition

Strong shift equivalence (SSE) is the transitive closure of 1-step equivalence.

Graphs $G_1$ and $G_2$ represent conjugate edge shifts iff their adjacency matrices are SSE.
Main open problem of symbolic dynamics: decide conjugacy/SSE

* Open since the 70s

* Decidable for matrices in $Z$ (Krieger, 1980)

* (almost the) same as conjugacy in $GL_n(Z)$

* Decidable for one-sided edge-shifts (Williams, 1973)

* The rewriting system on graphs is confluent.
# Invariants

## Definition

An invariant is a function $\psi$ s.t. $\psi(M) = \psi(N)$ if $M$ and $N$ are SSE.

* To prove that $M$ and $N$ are NOT SSE, just find an invariant that distinguishes them

Examples:

* Trace of the matrix

* More generally, number of cycles of size $k$

* The entropy (exponential growth of the number of paths of size $n$)

* ...

In this talk: A systematic way to find invariants
<figure><img src="image_15.png" /></figure>

Symbolic Dynamics

<figure><img src="image_16.png" /></figure>

Categories for symbolic dynamics

<figure><img src="image_17.png" /></figure>

Applications

<figure><img src="image_18.png" /></figure>

Conclusion
Build a category where arrows can represent matrices and equivalence classes of SSE.
# Starting point

## Folklore

The bialgebra PROP is exactly the PROP of nonnegative integer matrices.
## Folklore

The bialgebra PROP is exactly the PROP of nonnegative integer matrices.

A commutative monoid ($\eta: 0 \to 1, \mu: 2 \to 1$)

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>
## Folklore

The bialgebra PROP is exactly the PROP of nonnegative integer matrices.

A commutative monoid ($\eta: 0 \to 1, \mu: 2 \to 1$)

<figure><img src="image_21.png" /></figure>

A cocommutative comonoid ($\epsilon: 1 \to 0, \Delta: 1 \to 2$)

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>
## Folklore

The bialgebra PROP is exactly the PROP of nonnegative integer matrices.

A commutative monoid ($η: 0 \to 1, μ: 2 \to 1$)

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

A cocommutative comonoid ($ε: 1 \to 0, Δ: 1 \to 2$)

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

Bialgebra rules

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>
## Folklore

The bialgebra PROP is exactly the PROP of nonnegative integer matrices.

arrows $n \to m$ are exactly matrices of size $m \times n$.

<figure><img src="image_34.png" /></figure>
Technically, our matrices represent graph, so with inputs = outputs

SSE states that $RS \equiv SR$, how can we simulate that ?
Technically, our matrices represent graph, so with inputs = outputs

SSE states that $RS \equiv SR$, how can we simulate that ?

With a trace!
Consider the traced bialgebra prop (the previous prop + a trace).
Consider the traced bialgebra prop (the previous prop + a trace).

<figure><img src="image_35.png" /></figure>
In this prop, we can associate a scalar $t(M)$ to each matrix $M$.

<figure><img src="image_36.png" /></figure>
In this prop, we can associate a scalar $t(M)$ to each matrix $M$. Is it true that $t(M) = t(N)$ iff $M$ and $N$ are SSE ?

<figure><img src="image_37.png" /></figure>
Flow equivalence

$M = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ and $N = (1)$ satisfy $t(M) = t(N)$ but are not SSE.

<figure><img src="image_38.png" /></figure>
Flow equivalence

$t(M) = t(N)$ iff $M$ and $N$ are flow-equivalent, another equivalence notion coming from symbolic dynamics

(First observed by David Hillman, 1995)

We have lost a notion of time, that we need to recover
Solution

We add a generator that is a morphism for both the monoid and the comonoid.

$$ \text{Generator} = \text{Comonoid} $$

$$ \text{Comonoid} = \text{Generator} $$
We add a generator that is a morphism for both the monoid and the comonoid.

<figure><img src="image_39.png" /></figure>

Note: this new prop represents matrices in $\mathbb{Z}_+[t]$ rather than $\mathbb{Z}_+$
# Solution

We add a generator that is a morphism for both the monoid and the comonoid.

## Theorem

*In this prop, $t(M) = t(N)$ iff $M$ and $N$ are SSE.*

Needs some new (easy) results in symbolic dynamics for the proof.

To recap: we need one bialgebra, a bialgebra morphism and a trace.
<figure><img src="image_40.png" /></figure>

Symbolic Dynamics

<figure><img src="image_41.png" /></figure>

Categories for symbolic dynamics

<figure><img src="image_42.png" /></figure>

Applications

<figure><img src="image_43.png" /></figure>

Conclusion
## What do we gain from it ?

* If one knows a concrete representation of this prop, one can decide conjugacy

* One can find invariants !
* Let $\mathcal{C}$ be our category.

* Let $\mathcal{D}$ be any traced category that contains a bialgebra

* By the universal property, there is a functor from $\mathcal{C}$ to $\mathcal{D}$

* Using this functor, we can associate to each matrix $M$ an arrow $\psi(M)$ in $\mathcal{D}$ s.t. $\psi(M) = \psi(N)$ if $M$ and $N$ are SSE.
Good news/Bad news

Good news: There are a lot of bialgebras in the wild

Bad news:

* Some of them are in categories that are not traced

* Some of them are Hopf algebras

* Hopf algebras represent matrices with coefficients in $\mathbb{Z}$, not in $\mathbb{Z}_+$
Example from algebra 1/2

* If $\mathcal{M}$ is a finite abelian monoid, $\mathbb{K}[\mathcal{M}]$ has a structure of a bialgebra

* Product is the monoid product extended linearly

* Coproduct is the copy extended linearly

Theorem

Let $\mathcal{M}$ be an additive monoid, and $h$ an homomorphism. Then the number of solutions in $\mathcal{M}$ of the equation $h(Mx) = x$ is an invariant for SSE.
Example from algebra 2/2

• $K[X]$ has a structure of a bialgebra

◦ Product is the product of polynomials

* Coproduct is defined by $\Delta(X) = 1 \otimes X + X \otimes 1$

Problem: no trace!
Example from algebra 2/2

• $\mathbb{K}[X]$ has a structure of a bialgebra

● Product is the product of polynomials

* Coproduct is defined by $\Delta(X) = 1 \otimes X + X \otimes 1$

Solution: Replace $\mathbb{K}[X]$ by formal series in a complete semiring (like $\mathbb{R}_+ \cup \{+\infty\}$).

If we take the morphism $h(X) = tX$ we get:

Theorem

The quantity $f_M(t) = \frac{1}{\det(tI - tM)}$ is an invariant for SSE

This is the well-known Zeta function of a subshift.
## Example from Category Theory

Let $\mathcal{D}$ be a category with finite limits and colimits.

* Suppose one has a monoid $X$ in a $\mathcal{D}$ with a morphism $h$.

* It extends to a bialgebra using the diagonal map as a comonoid.

**Problem:** What if there is no trace in $\mathcal{D}$ ?
## Example from Category Theory

Let $\mathcal{D}$ be a category with finite limits and colimits.

* Suppose one has a monoid $X$ in a $\mathcal{D}$ with a morphism $h$.

* It extends to a bialgebra using the diagonal map as a comonoid.

Solution: Replace $\mathcal{D}$ with $\cospan(\mathcal{D})$ which is a compact category.
# Example from Category Theory

Let $\mathcal{D}$ be a category with finite limits and colimits.

* Suppose one has a monoid $X$ in a $\mathcal{D}$ with a morphism $h$.

* It extends to a bialgebra using the diagonal map as a comonoid.

## Theorem

Let $M$ be an $n \times n$ matrix.

The object that is the coequalizer of $X^n \underset{h^n \circ M}{\stackrel{id^n}{\longrightarrow}} X^n$ is an invariant for SSE.
# Example from Category Theory

Let $\mathcal{D}$ be a category with finite limits and colimits.

* Suppose one has a monoid $X$ in $\mathcal{D}$ with a morphism $h$.

* It extends to a bialgebra using the diagonal map as a comonoid.

## Theorem

Let $M$ be an $n \times n$ matrix.

The object that is the coequalizer of $X^n \xrightarrow{\text{id}^n} X^n$ is an invariant for SSE.

* Starting with the monoid $(\mathbb{Z}, +)$ in the category of abelian groups, we obtain the *Bowen-Franks group* (1977)

* Starting with the monoid $(\mathbb{Z}[t], +)$ in the category of $\mathbb{Z}[t]$-modules, we obtain the dimension group of Krieger (1977)
<figure><img src="image_44.png" /></figure>

Symbolic Dynamics

<figure><img src="image_45.png" /></figure>

Categories for symbolic dynamics

<figure><img src="image_46.png" /></figure>

Applications

<figure><img src="image_47.png" /></figure>

Conclusion
Where to go from here ?

* We have a systematic way to find invariants

* Investigate new bialgebras to find new invariants!