Cubical Complexes Code

As an alternative to simplicial complexes, implemented here, we can base our topology on squares rather than triangles. I have tried to base this cubical complex code on the Computational Homology book (see box below). Books written for humans can leave some details of orientations and so on to the reader, but computer code needs to specify the details consistently so I have tried to make these choices explicit on this page.

Comparison with simplicial complex:
dimension Simplicial Complex Cubical Complex
0 point point
1 line (edge) line (edge)
2 triangle square (rectangle)
3 tetrahedron cube
n simplice hyper-cube

However we need to implement this in a different way, if we specified a square by its vertices then we could not be sure that the vertices were all in the same plane and we could not be sure that the squares aligned.

We therefore have separate indexes for each dimension and we specify these as an interval.

So if we wanted to specify a square with 'x' dimension having an interval from 1 to 2 and the 'y' dimension having an interval from 1 to 2, we would specify it like this:

Square

(1) -> SQUARE := cubicalFacet(1,[1..2,1..2])

   (1)  (1..2,1..2)
                               Type: CubicalFacet
square

If we want to specify a shape in a higher dimension than the shape itself then some of the intervals will be degenerate, that is, the start and end indexes will be the same. So, for instance, we could specify a line in a 2 dimensional space like this:

Line

(2) -> LINE := cubicalFacet(1,[1..1,1..2])

   (2)  (1..1,1..2)
                               Type: CubicalFacet
line

We go to higher dimensions by specifying more intervals like this:

Cube

(3) -> CUBE := cubicalFacet(1,[1..2,1..2,1..2])

   (3)  (1..2,1..2,1..2)
                               Type: CubicalFacet
cube

FriCAS implementation of Domains

The structures on this page are encoded in the CubicalFacet and FiniteCubicalComplex domains.

CubicalFacet holds individual facets. Its representation is as follows:

Rep := Record(mul:Integer,fac:List(Segment(Integer)))

In the Computational Homology book (see box below right) this is called an Elementary Cell, the elementary cell only allows each interval to be either: l..l or l..(l+1) however this restriction is not enforced in the representation or the code. I think it may be acceptable to allow a CubicalFacet to have a wider range, say l..(l+2), provided we are very clear that this represents multiple Elementary Cells, in this case l..(l+1) and (l+1)..(l+2).

FiniteCubicalComplex holds multiple factets. They can all be different dimensions but they should all have the same number of intervals. If the number of dimensions is less than the number of intervals then, some of those intervals will be degenerate.

Its representation is as follows:

Rep := Record(VERTSET:VS,CUBE:List(CubicalFacet))

Representation holds whole Cubical Complex. This consists of a vertex set, here represented as a vertex list so that we can index it. Also a list of hypercubes.

Vertex Coordinates

In the Computational Homology book potential applications are described such as analyzing images and 3D scans where the elements are pixels or their higher dimensional counterparts. For this type of application we don't really need to define absolute coordinates we can just think of it as an abstract array, so for most purposes we can work with types like this:

FiniteCubicalComplex(VertexSetAbstract)

It is very hard to think why we would ever need to specify coordinates but I would still like to have the possibility to do so for the following reasons:

If we do work in geometric terms and if we specify vertices as vectors then it is important to note the differences from simplicial complexes.

simplex coodinates cubical coordinates
In the case of a simplicial complex we can encode a square as two triangles and each of its vertices can index into a table of vectors. In the case of a cubical complex the indexes are separate and therefore the coordinates are not held as vectors.

Therefore the vertex set needs to hold a real (floating point) value for each index in each dimension.

One Dimensional Facets

Line segments (AKA edges) have a direction and we need to make an arbitrary decision about which direction is positive. Here I chose to make the line go from a negative point to a positive point.

(4) -> ACUBE := FiniteCubicalComplex(Integer)

   (4)  FiniteCubicalComplex(Integer)
                                     Type: Type
(5) -> vs1:List(Integer) := [1,2,3,4]

   (5)  [1,2,3,4]
                            Type: List(Integer)
(6) -> L1 := cubicalFacet(1,[1..2])

   (6)  (1..2)
                             Type: CubicalFacet
(7) -> L2 := cubicalFacet(1,[2..3])

   (7)  (2..3)
                             Type: CubicalFacet
(8) -> L3 := cubicalFacet(1,[3..4])

   (8)  (3..4)
                             Type: CubicalFacet
(9) -> ln1:=cubicalComplex(vs1,[L1,L2,L3])$ACUBE

   (9)
        (1..2)
        (2..3)
        (3..4)
            Type: FiniteCubicalComplex(Integer)
(10) -> boundary(ln1)

   (10)
         -(1..1)
         (4..4)
            Type: FiniteCubicalComplex(Integer)
one dimensional boundary

When we take the boundary of these three lines we get -P1 and P4 so because the starting boundary is taken as negative and the finishing boundary as positive the intermediate points cancel out.

Two Dimensional Facets

In the same way the edges have an orientation so do two dimensional facets (AKA squares). This orientation is a direction of rotation around the square, I have taken a positive rotation as being:

  • [1..2,1] travel along the first dimension 'x'.
  • [2,1..2] travel along the second dimension 'y'.
  • -[1..2,2] travel along 'x' in reverse direction.
  • -[1,1..2] travel along 'y' in reverse direction.
two dimensional square

This direction of rotation is given by the left hand rule, which is: if the thumb of your left hand is pointing into the diagram then, the fingers curl in the direction of rotation.

(11) -> Sq1 := cubicalFacet(1,[1..2,1..2])

   (11)  (1..2,1..2)
                             Type: CubicalFacet
(12) -> Sq2 := cubicalFacet(1,[2..3,1..2])

   (12)  (2..3,1..2)
                              Type: CubicalFacet
(13) -> Sq3 := cubicalFacet(1,[3..4,1..2])

   (13)  (3..4,1..2)
                               Type: CubicalFacet
(14) -> ex1:=cubicalComplex(vs1,[Sq1,Sq2,Sq3])$ACUBE

   (14)
         (1..2,1..2)
         (2..3,1..2)
         (3..4,1..2)
            Type: FiniteCubicalComplex(Integer)
(15) -> boundary(ex1)

   (15)
         -(1..1,1..2)
         (1..2,1..1)
         -(1..2,2..2)
         (2..3,1..1)
         -(2..3,2..2)
         (4..4,1..2)
         (3..4,1..1)
         -(3..4,2..2)
            Type: FiniteCubicalComplex(Integer)
two dimensional boundary

Similar to the lines above, when we take the boundary operator of these three squares the adjacent lines cancel out and we get a rectangle going around the outside.

Two Dimensional Facets in Three Dimensional Space

If we continue with two dimensional facets (squares) but now embed them in three dimensional space things get a bit more complicated.

Lets look at some faces of a cube (but these are still individual faces, not a solid cube)

cube 2d in 3d

Two dimensional faces in 3 dimensions will each have 3 intervals one of which one will be degenerate. So lets look at the boundary of these. For instance:

δ[1..2,1..2,1]

green cycles on diagram

(16) -> boundary(cubicalFacet(1,[1..2,1..2,1]))

   (16)
   [-(1..1,1..2,1..1),(2..2,1..2,1..1),
   (1..2,1..1,1..1),-(1..2,2..2,1..1)]
                                 Type: List(CubicalFacet)
δ[1..2,1,1..2]

blue cycles on diagram

(17) -> boundary(cubicalFacet(1,[1..2,1,1..2]))

   (17)
   [-(1..1,1..1,1..2),(2..2,1..1,1..2),
   (1..2,1..1,1..1),-(1..2,1..1,2..2)]
                                 Type: List(CubicalFacet)

δ[1,1..2,1..2]

black cycles on diagram

(18) -boundary(cubicalFacet(1,[1,1..2,1..2]))

   (18)
   [-(1..1,1..1,1..2),(1..1,2..2,1..2),
   (1..1,1..2,1..1),-(1..1,1..2,2..2)]
                                 Type: List(CubicalFacet)
So a 'square' has two non-degenerate intervals and the direction of rotation around these are given by:
  • x first, y second
  • x first, z second
  • y first, z second

Again, the direction of rotation is given by the left hand rule, but this time the thumb of the left hand is pointing in the direction of the missing dimension then, the fingers curl in the direction of rotation.

Three Dimensional Facets in Three Dimensional Space

Now we treat the cube as a solid object.

A solid cube in 3D has three dimensions all of which are non-degenerate intervals.

So [1..2,1..2,1..2] is a solid cube.

orientation of cube faces

In order to find the boundary of this cube we replace each interval, in turn, with its endpoints. This gives the 6 faces.

The orientation of some of these faces is reversed, this is done in such a way that, if the boundary operator is applied twice, then the edges will cancel out. That is, each edge is common to two faces and each face winds round in such a way that the direction of the common edge cancels out.

This direction is given by the left hand rule: If your left hand thumb points from the inside to the outside of the cube then the fingers curl in the direction of the winding.

When we replace each interval we alternate signs like this:

This is familiar from simplicial complexes where we remove each dimension, in turn, and alternate the sign.

  • x first, y second
  • -(x first, z second)
  • y first, z second

In addition to this: the face corresponding to the starting value, in each interval, is reveresed and the second value is not.

So both simplicial complexes and cubicial complexes have this structure where we get a boundary by removing each entry in turn and alternating the sign.

For simplicial complexes this happens with edges but with cubicial complexes it hapens with 2D faces.

simplicial complexes cubicial complexes
simplectical cubical
So the boundary of a cube is 6 square faces as expected.
(19) -> sc1 := sphereSolid(3)$CubicalComplexFactory

   (19)
         (1..2,1..2,1..2)
                      Type: FiniteCubicalComplex(Integer)
(20) -> sc2 := boundary(sc1)

   (20)
         -(1..1,1..2,1..2)
         (2..2,1..2,1..2)
         (1..2,1..1,1..2)
         -(1..2,2..2,1..2)
         -(1..2,1..2,1..1)
         (1..2,1..2,2..2)
                      Type: FiniteCubicalComplex(Integer)
Try delta again, this gives zero and applying the boundary operator twice always gives zero.
(21) -> sc3 := boundary(sc2)

   (21)  [empty]
                      Type: FiniteCubicalComplex(Integer)

Combinatorics of Cube

We can analyse a cube in pure combinatorics terms, rather than geometric terms, as follows:

A solid cube represented here as (1..2,1..2,1..2), we can then define subsets of this by making some of the intervals degenerate. cube volume

From this (1..2,1..2,1..2) cube we can then get the 6 faces by using all possible combinations with one degenerate interval.

cube faces
We can then get the 12 edges by using all possible combinations with two degenerate intervals. cube line

We can then get the 8 vertices by using all possible combinations with all three degenerate intervals.

cube vertices

Orientation of a Face

These n-dimensional faces all have orientations. In order to assign directions to the boundary of a face we need to have a consistent set of conventions, for instance, it would help to always start a the same vertex when going around the boundary.

If we are going from (1,1) to (2,2) on this face it should not matter if we go via (1,2) or (2,1) because it commutes.

So, on the diagram, we can go 'a' then 'b' or 'c' then 'd', that is:

a + b = c + d

which gives:

a + b - c - d = 0
or
c + d - a - b = 0

commute square

So we need to decide which of these to choose as a positive boundary direction. To do this go back to the earlier notation:

Given a face: [1..2,1..2]

To generate the boundary δ[1..2,1..2] we start at the minimum vertex [1,1]

  • from [1,1] we then apply [1..2,1] to get to [2,1].
  • from [2,1] we then apply [1,1..2] to get to [2,2].
  • from [2,2] we then apply -[1..2,1] to get to [1,2].
  • from [1,1] we then apply -[1,1..2] to get back to [1,1].
square border

So we start at the minimum coordinate indexes, apply the first (non-degenerate) interval, then the second, then minus the first, then minus the second.

The aim of these rules is so that the boundary operator works correctly when the faces are embedded in higher dimensional cubes:

Other Shapes/Spaces as Cubical Complexes

We can construct other common cubical complexes by using CubicalComplexFactory like this:

(22) ->tor := torusSurface()$CubicalComplexFactory

   (22)
         (1..1,1..2,1..1,1..2)
         (1..1,1..2,2..2,1..2)
         (1..1,1..2,1..2,1..1)
         (1..1,1..2,1..2,2..2)
         (2..2,1..2,1..1,1..2)
         (2..2,1..2,2..2,1..2)
         (2..2,1..2,1..2,1..1)
         (2..2,1..2,1..2,2..2)
         (1..2,1..1,1..1,1..2)
         (1..2,1..1,2..2,1..2)
         (1..2,1..1,1..2,1..1)
         (1..2,1..1,1..2,2..2)
         (1..2,2..2,1..1,1..2)
         (1..2,2..2,2..2,1..2)
         (1..2,2..2,1..2,1..1)
         (1..2,2..2,1..2,2..2)
                      Type: FiniteCubicalComplex(Integer)

cubical torus

For more shapes see page here.

Homology of Cubical Complexes

I have explaind how the homology is implemented on page here.

Next Steps for Cubical Type Theory

For more information about how this is used in cubical type theory see the page about simplicial sets first and then the page about cubical type theory (CTT).


metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flagComputational Homology - Tomasz Kaczynski, Konstantin Mischaikow, Marian Mrozek - Cubical homology and its potential applications .

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2024 Martin John Baker - All rights reserved - privacy policy.