Binomial lattice congruences
and flat dihomotopy types
Computational Logic and Applications
Kraków

Cameron Calk
& Luigi Santocanale
15th of December 2023

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

1 / 23

Introduction

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

2 / 23

Overview and context
Multinomial lattices were introduced by Bennett & Birkhoﬀ.
Study of the rewriting system associated to commutativity from alattice-theoretic perspective:
abbaa ! ababa ! aabba ! aabab ! aaabb

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

3 / 23

Overview and context
Multinomial lattices were introduced by Bennett & Birkhoﬀ.
Study of the rewriting system associated to commutativity from alattice-theoretic perspective:
abbaa ! ababa ! aabba ! aabab ! aaabb

These lattices and their congruences are strongly related toconcurrency.
The word abbaa represents interleaving actions of two agents.
Multinomial lattice congruences give rise to certain Parikh
equivalences central to scheduling problems in concurrency.
A geometric interpretation closely relates these lattices to asemantics of concurrent systems, namely directed topology.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

3 / 23

In this talk. . .
Goal: instantiate the link between dihomotopy and binomial
lattice congruences.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

4 / 23

In this talk. . .
Goal: instantiate the link between dihomotopy and binomial
lattice congruences.
Binomial lattices.
Define binomial lattices and describe their congruences.
Recall their interpretation as lattices of lattice paths.
Describe the geometric intuition of their congruences.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

4 / 23

In this talk. . .
Goal: instantiate the link between dihomotopy and binomial
lattice congruences.
Binomial lattices.
Define binomial lattices and describe their congruences.
Recall their interpretation as lattices of lattice paths.
Describe the geometric intuition of their congruences.

Directed algebraic topology.
Recall the notion of directed space, and define cubical complexes.
Introduce the binomial complex and describe the dihomotopy
types of its subcomplexes.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

4 / 23

In this talk. . .
Goal: instantiate the link between dihomotopy and binomial
lattice congruences.
Binomial lattices.
Define binomial lattices and describe their congruences.
Recall their interpretation as lattices of lattice paths.
Describe the geometric intuition of their congruences.

Directed algebraic topology.
Recall the notion of directed space, and define cubical complexes.
Introduce the binomial complex and describe the dihomotopy
types of its subcomplexes.

Result: the correspondence.
Congruences correspond to dihomotopy types of subcomplexes.
The congruence lattice of a binomial lattice is isomorphic to thelattice of subcomplex dihomotopy types.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

4 / 23

In this talk. . .
Goal: instantiate the link between dihomotopy and binomial
lattice congruences.
Binomial lattices.
Define binomial lattices and describe their congruences.
Recall their interpretation as lattices of lattice paths.
Describe the geometric intuition of their congruences.

Directed algebraic topology.
Recall the notion of directed space, and define cubical complexes.
Introduce the binomial complex and describe the dihomotopy
types of its subcomplexes.

Result: the correspondence.
Congruences correspond to dihomotopy types of subcomplexes.
The congruence lattice of a binomial lattice is isomorphic to thelattice of subcomplex dihomotopy types.

We will end by briefly describing ongoing work in this area.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

4 / 23

Binomial lattices and their congruences

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

5 / 23

Multinomial lattices
Given v 2 Nk , we denote by L(v) the set of words on the alphabet⌃ = {a1 , . . . , ak } such that:w ccontains vi occurrences of the letter ai .

We equip this set with the partial order generated by(
w = u · ai aj · v
w  w0()9u, v
and i < j.
w 0 = u · aj ai · v

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

6 / 23

Multinomial lattices
Given v 2 Nk , we denote by L(v) the set of words on the alphabet⌃ = {a1 , . . . , ak } such that:w ccontains vi occurrences of the letter ai .

We equip this set with the partial order generated by(
w = u · ai aj · v
w  w0()9u, v
and i < j.
w 0 = u · aj ai · v
The poset (L(v), ) has the structure of a lattice.
These structures generalize permutations to permutations ofmultisets, called multipermutations.
Indeed, for v = (1, . . . , 1), we have L(v) = Sk .
The order  generalizes the weak Bruhat order defining the
permutohedron.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

6 / 23

Binomial lattices
Today, we will focus on binomial lattices:
Given n, m 2 N, we denote by L(n, m) the set of words on thealphabet ⌃ = {a, b} such that:w contains n occurrences of the letter a,and m occurrences of the letter b.

which we equip with the partial order generated by(
w = u · ab · v,
w  w0()9u, v
w0 = u · ba · v.
We will henceforth denote L(n, m) simply by L.

Proposition (L. Santocanale ‘05)
L is a distributive lattice.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

7 / 23

As lattices of lattice paths
The elements of L are interpreted as paths in an n by m grid:w2L!

fw : [n + m] ! [n] ⇥ [m]an occurrence of a is a step in the x-axis,
an occurrence of b is a step in the y-axis.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

8 / 23

As lattices of lattice paths
The elements of L are interpreted as paths in an n by m grid:w2L!

fw : [n + m] ! [n] ⇥ [m]an occurrence of a is a step in the x-axis,
an occurrence of b is a step in the y-axis.

The ordering is recovered as a point-wise ordering on paths.
The join and meet relations then become point-wise maxima andminima:Note that these paths are increasing in each coordinate.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

8 / 23

Distributive lattice congruences
Let L be a distributive lattice.
A congruence on L is an equivalence relation ✓ ✓ L ⇥ L which iscompatible with the lattice operations.
In distributive lattices, congruences are given by sets of join-primeelements.
j 2 L is join-prime if
j =u_v)

j = u or j = v.

The set of join-prime elements of L is denoted by J .

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

9 / 23

Distributive lattice congruences
Let L be a distributive lattice.
A congruence on L is an equivalence relation ✓ ✓ L ⇥ L which iscompatible with the lattice operations.
In distributive lattices, congruences are given by sets of join-primeelements.
j 2 L is join-prime if
j =u_v)

j = u or j = v.

The set of join-prime elements of L is denoted by J .

Given S ✓ J , the congruence ⌘S is defined by:u ⌘S v

Cameron Calk (LIS)()

8j 2 S,

Congruences & Dihomotopy

j  u iﬀ j  v.

15/12/2023

9 / 23

Join-prime elements of L(n, m)
What are the join-prime elements of L?

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

10 / 23

Join-prime elements of L(n, m)
What are the join-prime elements of L?

They are the paths that have exactly one north-east turn:Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

10 / 23

Join-prime elements of L(n,m)
C(m m),

What are the join-prime elements of L?

w = uvv-

They are the paths that have exactly one north-east turn:
(2 ,

Ne

1)8

As words, these are of the forma k bl a n k b m lThey are thus characterized by (k, l), with
Cameron Calk (LIS)

Congruences & Dihomotopy

(

0k<n
0<lm

15/12/2023

10 / 23

Geometric interpretation of congruences
Let us look at the particular case when S = {j}.
Recall thatw ⌘S w 0()

j  w iﬀ j  w0 .

Let (k, l) be the coordinate of the NE turn of j.
j  u means fu passes “above” (k, l),j 6 v means fv passes “below” (k, l).

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

11 / 23

Geometric interpretation of congruences
Let us look at the particular case when S = {j}.
Recall thatw ⌘S w 0()

j  w iﬀ j  w0 .

Let (k, l) be the coordinate of the NE turn of j.
j  u means fu passes “above” (k, l),j 6 v means fv passes “below” (k, l).

The same holds for arbitrary S ✓ J .
So, lattice congruences of L correspond to separating directed
paths by points. This reminds us of directed homotopy. . .
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

11 / 23

Directed homotopy and binomial complexes

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

12 / 23

Directed topology
Directed topology provides a geometric semantics for true
concurrency.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

13 / 23

Directed topology
Directed topology provides a geometric semantics for true
concurrency.
A directed space X consists of
A topological space X,
A set of directed paths dX.

We interpret directed paths as executions.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

13 / 23

Directed topology
Directed topology provides a geometric semantics for true
concurrency.
A directed space X consists of
A topological space X,
A set of directed paths dX.

We interpret directed paths as executions.
Today, we focus on a particular class of directed spaces, namely
cubical complexes. In two dimensions, these consist of:vertices, which may be related by. . .
edges, which may form the border of. . .
squares.

Such two-dimensional complexes model two-agent concurrent
systems:

Directed paths are those which increase in each coordinate.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

13 / 23

Binomial complexes
In particular, for n, m 2 N, we consider the binomial complex C:
C0 := {v(i,j) | 0  i  n and 0  j  m},
C1 := {e(i1 ,j1 ),(i2 ,j2 ) | i2 = i1 + 1 exor j2 = j1 + 1},
C2 := {F(k,l) | 0  k < n and 0 < l  m}.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

14 / 23

Binomial complexes
In particular, for n, m 2 N, we consider the binomial complex C:
C0 := {v(i,j) | 0  i  n and 0  j  m},
C1 := {e(i1 ,j1 ),(i2 ,j2 ) | i2 = i1 + 1 exor j2 = j1 + 1},
C2 := {F(k,l) | 0  k < n and 0 < l  m}.

This cubical complex corresponds to the n by m grid, with all“holes” filled by squares.
Note that we encode squaresby their upper-left corner.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

14 / 23

Binomial complexes
In particular, for n, m 2 N, we consider the binomial complex C:
C0 := {v(i,j) | 0  i  n and 0  j  m},
C1 := {e(i1 ,j1 ),(i2 ,j2 ) | i2 = i1 + 1 exor j2 = j1 + 1},
C2 := {F(k,l) | 0  k < n and 0 < l  m}.

This cubical complex corresponds to the n by m grid, with all“holes” filled by squares.
Note that we encode squaresby their upper-left corner.
Given S ✓ C2 , we denote by C S the cubical complex with thesame set of vertices and edges, but in which C2S := C2 \ S.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

14 / 23

Cubical homotopy
Given a concurrent system, which executions produce the same
output?

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

15 / 23

Cubical homotopy
Given a concurrent system, which executions produce the same
output?

We say that paths are dihomotopic if we can “slide” one onto theother through a sequence of directed paths, and if they start andend at the same point.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

15 / 23

Cubical homotopy
Given a concurrent system, which executions produce the same
output?

We say that paths are dihomotopic if we can “slide” one onto theother through a sequence of directed paths, and if they start andend at the same point.
In a cubical complex , it suﬃces to consider
combinatorial dipaths,
i.e. those which are containedin the set of edges 1 ,combinatorial homotopy,
i.e. dipaths are equivalent
when the space between themis filled by squares in 2 .
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

15 / 23

Dihomotopy quotients⇤

The combinatorial dihomotopy relation, denoted by !, is anequivalence relation on combinatorial dipaths with the same
beginning- and end-points.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

16 / 23

Dihomotopy quotients⇤

The combinatorial dihomotopy relation, denoted by !, is anequivalence relation on combinatorial dipaths with the same
beginning- and end-points.
!
Given the binomial complex C, we denote by mCP(C) the set ofcombinatorial dipaths from (0, 0) to (n, m).
!
!
Note that for any S ✓ C2 , we have mCP(C) = mCP(C S ).

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

16 / 23

Dihomotopy quotients⇤

The combinatorial dihomotopy relation, denoted by !, is anequivalence relation on combinatorial dipaths with the same
beginning- and end-points.
!
Given the binomial complex C, we denote by mCP(C) the set ofcombinatorial dipaths from (0, 0) to (n, m).
!
!
Note that for any S ✓ C2 , we have mCP(C) = mCP(C S ).
We are interested in the quotient by combinatorial dihomotopy:!
⇤mCP(C S ) !
.
In the particular case in which S = {F(k,l) }. . .

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

16 / 23

The correspondence

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

17 / 23

Correspondences

Elements of L.

!
Elements of mCP(C S ).
Lattice paths

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

18 / 23

Correspondences!
Elements of mCP(C S ).

Elements of L.

Lattice paths
Join prime elements of L.

Squares in C.

J ' {(k, l) | 0  k < n and 0 < l  m } ' C2

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

18 / 23

Correspondences!
Elements of mCP(C S ).

Elements of L.

Lattice paths
Join prime elements of L.

Squares in C.

J ' {(k, l) | 0  k < n and 0 < l  m } ' C2Congruences ⌘S of bilnm

Cameron Calk (LIS)

Subcomplexes C S (n, m).

Congruences & Dihomotopy

15/12/2023

18 / 23

Results!
Since L ' mCP(C S ) as sets, we can equip the latter with an
isomorphic ordering.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

19 / 23

Results!
Since L ' mCP(C S ) as sets, we can equip the latter with an
isomorphic ordering.
Dihomotopy quotients are then lattice morphisms, and we obtain:

Proposition
For any S ✓ J ' C2 , we have the lattice isomorphism!
⇤
L(n, m) ⌘ ⇠mCP(C S ) !
.
S =Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

19 / 23

Results!
Since L ' mCP(C S ) as sets, we can equip the latter with an
isomorphic ordering.
Dihomotopy quotients are then lattice morphisms, and we obtain:

Proposition
For any S ✓ J ' C2 , we have the lattice isomorphism!
⇤
L(n, m) ⌘ ⇠mCP(C S ) !
.
S =Moreover, the maps induced by inclusions S 0 ✓ S on each sidecorrespond, i.e. the following maps coincide:
! S0
! S
⇤
⇤
qS 0 ,S : mCP(C ) !
! mCP(C ) !
pS 0 ,S : L(n, m) /S 0 ! L(n, m) /S .
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

19 / 23

Ongoing work

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

20 / 23

Multinomial lattice quotients
We have established a concrete link between directed algebraic
topology and binomial lattices.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

21 / 23

Multinomial lattice quotients
We have established a concrete link between directed algebraic
topology and binomial lattices.
In the case of multinomial lattices L(v1 , . . . , vn ), for n 3. . .

L(v) is not distributive.
Because of this, its congruences are not as simple.
Indeed, here congruences correspond to subsets S ✓ J which areclosed under the join-dependency relation.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

21 / 23

Multinomial lattice quotients
We have established a concrete link between directed algebraic
topology and binomial lattices.
In the case of multinomial lattices L(v1 , . . . , vn ), for n 3. . .

L(v) is not distributive.
Because of this, its congruences are not as simple.
Indeed, here congruences correspond to subsets S ✓ J which areclosed under the join-dependency relation.

On the geometric side. . .
Join-dependency means that adding squares is no longer “free” inthe sense that adding a square may necessitate adding parallelsquares.
We can also consider higher homotopy groups - what is theirinterpretation?

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

21 / 23

Multinomial lattice quotients
We have established a concrete link between directed algebraic
topology and binomial lattices.
In the case of multinomial lattices L(v1 , . . . , vn ), for n 3. . .

L(v) is not distributive.
Because of this, its congruences are not as simple.
Indeed, here congruences correspond to subsets S ✓ J which areclosed under the join-dependency relation.

On the geometric side. . .
Join-dependency means that adding squares is no longer “free” inthe sense that adding a square may necessitate adding parallelsquares.
We can also consider higher homotopy groups - what is theirinterpretation?

In this direction, we are studying the higher dimensional
automata associated to the multinomial complexes.
Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

21 / 23

The continuous case
In what precedes, we have considered discrete paths.
The continuous analog of the binomial lattice is the quantale
Q_ (I) of sup-continuous endomorphisms of the unit interval I.

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

22 / 23

The continuous case
In what precedes, we have considered discrete paths.
The continuous analog of the binomial lattice is the quantale
Q_ (I) of sup-continuous endomorphisms of the unit interval I.
This is a mix ?-autonomous quantale,
all permutohedra and binomial lattices are sublattices,
elements have interpretation as directed continuous paths,
congruences are more complicated. . .

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

22 / 23

The continuous case
In what precedes, we have considered discrete paths.
The continuous analog of the binomial lattice is the quantale
Q_ (I) of sup-continuous endomorphisms of the unit interval I.
This is a mix ?-autonomous quantale,
all permutohedra and binomial lattices are sublattices,
elements have interpretation as directed continuous paths,
congruences are more complicated. . .

We have related the ordering to directed homotopy, but (it seems)
that congruences cannot be captured thereby.
We are currently exploring other topological techniques,i.e. Priestley duality, frame duality,. . . in order to characterize its
congruences.
There are also higher dimensional analogues of this lattice. . .

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

22 / 23

Thank you

Cameron Calk (LIS)

Congruences & Dihomotopy

15/12/2023

23 / 23