Graphical Supersymmetry Algebras

Thanks to Dr. James Hughes, Matthew Lynn, Chris Walker, Chas Leichner, Alex Ray, Alex Zhu, Dr. Cornelia Van Cott, Paul Sebexen, Colin Aitken, Chuck Moulton, Sebastien Zany, and Nick for joining me in playing with this problem.

What is an adinkra?

Adinkras are colored connected simple graphs, that are bipartite and n-regular.

Adinkras are a graphical representation of supersymmetry algebras.

The prefix super- comes from the theory of supersymmetry in theoretical physics. Superalgebras and their representations, supermodules, provide an algebraic framework for formulating supersymmetry.

A superalgebra is a \(\mathbb{Z}_2\)-graded algebra. In other words, it is “an algebra over a commutative ring or field with decomposition into ‘even’ or ‘odd’ pieces and a multiplication operator that respects the grading.”

What is an odd adinkra?

An adinkra is odd if the sum of every 4-cycle in the adinkra is odd.
2
To create an odd adinkra: we assign 0 or 1 to every edge of an n-dimensional cube such that, for each face of the cube, the sum of the edges of the face is odd.

How many unique n-dimensional odd adinkras exist?

Before we attack this, let’s elaborate on the problem:

First some notation must be fixed. By \(E(G)\), we mean the edges of the graph \(G\), and by \(Q_n\), we mean the graph corresponding to the \(n\)-dimensional cube. The formal statement is then as follows.

How many edge 2-colourings \(\phi : E(Q_n) to {0,1}\) exist such that, for each 4-cycle \(C\) of \(Q_n\), the sum of the edge colours is odd: \(\sum_{e \in E(C)} \phi(e) = 1\) mod \(2\) ?

Note that we bastardize the term “edge n-colourings” \(\equiv\) assignment of \(x \in {0,1,..,n-1}\) to every edge.

Breaking Down The Problem: The Overture

Let \(e_n\) denote the number of edge colourings of \(Q_n\) for which the sum of the edge colours is even, and let \(o_n\) denote the number of edge colourings for which the sum is odd. As \(Q_0\) contains a single vertex and no edges, there are no edge colourings with either property, so we set \(e_0 = o_0 = 1\).

Now \(Q_1\) contains two vertices with a single edge between them, so \(e_1 = o_1 = 1\). The slightly more interesting graph \(Q_2\) corresponds to a square, which can have its edges 2-coloured in \(2^4\) ways. Half of which will correspond to an even sum, the other half to an odd, so \(e_2 = o_2 = 8\). The graph \(Q_3\) can be 2-coloured in \(2^{12}\) ways, half of which must be even and the other half odd, so \(e_3 = o_3 = 2^{11}\).

Conjecture: For all \(n\), \(e_n = o_n = 2^{|E(Q_n)| – 1}\).

When constructing \(Q_{n+1}\) from \(Q_n\) we are duplicating the graph \(Q_n\) and connecting every vertex of the duplicate to the original.

Combinatorial Approach

For a 2-cube: we have 2 different states [the sides sum to 1 or 3], and 4 unique rotational variants of each state. \(2*4 =8\)

Can we write this in a closed form? The set of all unique states of the cube is \(2^8\).

We have 8 different choosing points, one for each of the 8 edges.
For each of these choosing points, we have 2 different options: pick 0 or 1.

0

What about for higher dimensions?

Screenshot from 2014-07-26 17:31:21
Screenshot from 2014-07-26 17:31:40
Screenshot from 2014-07-26 17:31:10
Screenshot from 2014-07-26 17:30:53

For the front face of the cube, we have \(2^{2^{n-1}-1}\)

For the back face of the cube, we also have \(2^{2^{n-1}-1}\)

The state of this edge is completely determined by this edge [following an intuition we will confirm in the following section]. Therefore, instead of adding 4 more options, we only add 2.

This gives us \(2^{2^{(n−1)}} \cdot 2^{2^{(n+1)}} \cdot 2^1 = 2^{2^n-1}\). \(_\blacksquare\)

Visually Formalizing our Intuition

Until we prove our hunch is correct, there is a hole in the induction step where one would need to show that many ways to glue to n-1 dimensional hypercubes together exist.

Intuitively, as soon as you fill in 1 edge (0 or 1) that fixes the rest of them \(\rightarrow\) meaning that there are only 2 valid ways to connect any 2 \(n\)-dimensional cubes into a (\(n+1\))-dimensional cube.

This can be visually formalized and inductively proven:

We can add the corresponding edges of the (n-1)-cubes to get a new (n-1) cube, and then the old problem of coloring the edges between the two cubes becomes the problem of coloring vertices so that the sum of the colors of two vertices is the same as the number on the edge between them.

RinsProblem

Computational Attacks

Screenshot from 2014-07-26 17:31:56

All code used in this post is on my github.

generate_hypercube.py

The set-theoretic approach is just a cool way to think about graph generation.

# Hypercube Problem
from itertools import chain, combinations
# Create generator set for hypercube of dimension x
def S(x):
 return set(range(0,x)) 
# From http://stackoverflow.com/questions/18035595/powersets-in-python-using-itertools
def powerset(iterable):
 s = list(iterable) 
 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1)) 
# Generate a list of edges given a list of vertices
def edges(verts):
 return set(frozenset([x, y]) for x in verts for y in verts if len(x ^ y) == 1) 
# Run this to generate hypercube of specified number of dimensions
def Qgen(dimensions):
 genSet = S(dimensions) 
 print(genSet) 
 Verts = list(powerset(genSet)) 
 print(Verts) 
 sVerts = set(frozenset(x) for x in Verts) 
 print(sVerts) 
 print(len(sVerts)) 
 Edges = edges(sVerts) 
 print(Edges) 
 print(len(Edges)) 
 return
cube.py

Shiny Graphviz to generate n-dimensional Hamming cubes which falls apart around n=8.

import colorsys
import itertools
import sys
n = int(sys.argv[1])
bits = list(itertools.product([0, 1], repeat=n))
HSV_tuples = [(x*1.0/n, 0.5, 0.5) for x in range(n+1)]
tuples = map(lambda x: '#%02x%02x%02x' % tuple(map(lambda x: int(x*255), colorsys.hsv_to_rgb(*x))), HSV_tuples)
def diff(a, b):
    difference = 0
    for a0, b0 in zip(a, b):
        difference += a0 != b0
    return difference
def reprtag(t):
    return "".join(str(b) for b in t)
print 'graph cube {'
print '  ranksep=', n/2.0, ';'
print '  fontsize=8;'
seen = set()
for ((a, b), c) in zip(itertools.product(bits, bits), itertools.cycle(tuples)):
    if diff(a, b) == 1 and (b, a) not in seen:
        seen.add((a, b))
        print '  "', reprtag(a), '"',  '--', '"', reprtag(b), '" [color="',  c, '"]'
print '}'

Dependency:

sudo apt-get install graphviz

Make them all in one go:

for i in $(seq 1 8); do python cube.py $i > cube${i}.dot;
altcube.py

This program generates text files containing all unique n-cubes satisfying the properties described. This works in an arbitrary number of dimensions and takes a file of the previous dimension as input.

import string
dimension_start = 3
dimension_end = 4
# loop through the dimensions you care about
# (stored in files, so you don't have to start from scratch each time)
for dimension in range( dimension_start, dimension_end + 1 ):
	# initialize lists & dictionaries as empty
	vertices = []
	edges = []
	faces = {}
	# create a list of vertices in string binary form (e.g., '1001' = 9 ).
	for vertex_int in range( 2**dimension ):
		vertices.append( bin( vertex_int )[2:].zfill( dimension ) )
	# create a list of valid edges in string binary form (e.g., '10011011' = 9,11 ).
	for vertex in vertices:
		for i in range( len( vertex ) ):
			if vertex[i:i+1] == '0':
				edges.append( vertex + vertex[:i] + '1' + vertex[i+1:] )
	# create a list of valid edges in string binary form (e.g., '10011011' = 9,11 ).
	# create a list of valid faces as a lookup table of edges.
	for vertex in vertices:
		for i in range( len( vertex ) ):
			if vertex[i:i+1] == '0':
				edges.append( vertex + vertex[:i] + '1' + vertex[i+1:] )
				# create a list of valid faces as a lookup table of edges.
				for j in range( i + 1, len( vertex ) ):
					if not ( vertex + vertex[:i] + '1' + vertex[i+1:] in faces ):
						faces[ vertex + vertex[:i] + '1' + vertex[i+1:] ] = 
							[ vertex + vertex[:i] + '1' + vertex[i+1:], 
							vertex + vertex[:j] + '1' + vertex[j+1:], 
							vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:], 
							vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ]
					if not ( vertex + vertex[:j] + '1' + vertex[j+1:] in faces ):
						faces[ vertex + vertex[:j] + '1' + vertex[j+1:] ] = 
							[ vertex + vertex[:i] + '1' + vertex[i+1:], 
							vertex + vertex[:j] + '1' + vertex[j+1:], 
							vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:], 
							vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ]
					if not ( vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] in faces ):
						faces[ vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ] = 
							[ vertex + vertex[:i] + '1' + vertex[i+1:], 
							vertex + vertex[:j] + '1' + vertex[j+1:], 
							vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:], 
							vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ]
					if not ( vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] in faces ):
						faces[ vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ] = 
							[ vertex + vertex[:i] + '1' + vertex[i+1:], 
							vertex + vertex[:j] + '1' + vertex[j+1:], 
							vertex[:i] + '1' + vertex[i+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:], 
							vertex[:j] + '1' + vertex[j+1:] + vertex[:i] + '1' + vertex[i+1:j] + '1' + vertex[j+1:] ]
	# read in the n-1 dimension valid cubes
		cube_small_file = open( 'cube-' + str( dimension - 1 ) + '.txt', 'r' )
		cubes_small = []
		for line in cube_small_file:
			cubes_small.append( line.strip( 'n' ) )
		cube_small_file.close()
	# open the n dimension cube file for writing
		cube_big_file = open( 'cube-' + str( dimension ) + '.txt', 'w' )
	# open an error file for writing
		cube_error_file = open( 'cube_error.txt', 'w' )
	# combine every cube with every other cube
	for cube1_string in cubes_small:
		for cube2_string in cubes_small:
			# read in n-1 dimension cubes
			cube1_list = [ '0' + cube1[:dimension-1] + '0' + cube1[dimension-1:] for cube1 in cube1_string.split( ',' ) ]
			cube2_list = [ '1' + cube2[:dimension-1] + '1' + cube2[dimension-1:] for cube2 in cube2_string.split( ',' ) ]
			# combine cubes the two possible ways
			for binary_value in range( 0, 2 ):
				new_edges = []
				new_edges_track = []
				new_edges_face_order = []
				cube_big_edges = {}
				# add the edges of two n-1 dimension cubes to the edge list for the n cube
				for cube1_edge in cube1_list:
					cube_big_edges[ cube1_edge[:-1] ] = cube1_edge[-1:]
				for cube2_edge in cube2_list:
					cube_big_edges[ cube2_edge[:-1] ] = cube2_edge[-1:]
				# create a list of the new edges
				for edge in edges:
					if not ( edge in cube_big_edges ):
						new_edges.append( edge )
				# initialize one new edge (to 0 or 1 depending on the for loop)
				for edge in new_edges:
					cube_big_edges[ edge ] = str( binary_value )
					break
				# order the list of new edges so that only one edge will be unknown at any time
				new_edges_track = list( new_edges )
				for edge in new_edges:
					face = faces[ edge ]
					for face_edge in face:
						if face_edge in new_edges_track:
							new_edges_track.remove( face_edge )
							new_edges_face_order.append( face_edge )
				# go through the edges in that order, filling in new edges each time
				for edge in new_edges_face_order:
					odd_even_total = 0
					face = faces[ edge ]
					for face_edge in face:
						if face_edge in cube_big_edges:
							odd_even_total = odd_even_total + int( cube_big_edges[ face_edge ] )
					for face_edge in face:
						if not ( face_edge in cube_big_edges ):
							cube_big_edges[ face_edge ] = str( ( odd_even_total + 1 ) % 2 )
				# now that all edge values are filled in, doublecheck that every face is odd (quadruple-check actually -- inefficiently -- because I lookup by edges)
				for edge in edges:
					odd_even_total = 0
					face = faces[ edge ]
					for face_edge in face:
						if face_edge in cube_big_edges:
							odd_even_total = odd_even_total + int( cube_big_edges[ face_edge ] )
					if odd_even_total % 2 == 0:
						cube_error_file.write( 'EVEN FACE ERROR: ' )
						for face_edge in face:
							cube_error_file.write( face_edge + ':' + cube_big_edges[ face_edge ] + ',' )
						cube_error_file.write( 'n' )
						cube_error_file.write( 'CUBE1: ' + ','.join( cube1_list ) + 'n' )
						cube_error_file.write( 'CUBE2: ' + ','.join( cube2_list ) + 'n' )
				# output the n-dimensional cube
				cube_big_list = []
				for edge in edges:
					cube_big_list.append( edge + cube_big_edges[ edge ] )
				cube_big_file.write( ','.join( cube_big_list ) + 'n' )
	cube_big_file.close()
square.pl

Coded in desperation to test the conjecture for 3 & 4 dimensions. Conditional programming is cool! helper.scala autogenerated the legal 4cycles.

Dependency: Download the SWI-prolog package

sudo apt-get prolog

This can be run in the prolog console:

swipl -s square.pl

with the following commands.

findall([A,B,C,D,E,F,G,H,I,J,K,L], cube(A,B,C,D,E,F,G,H,I,J,K,L), List), length(List, Len).
findall([E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11, E12, E13, E14, E15, E16, E17, E18, E19, E20, E21, E22, E23, E24, E25, E26, E27, E28, E29, E30, E31, E32], dim4(E1, E2, E3, E4, E5, E6, E7, E8, E9, E10, E11, E12, E13, E14, E15, E16, E17, E18, E19, E20, E21, E22, E23, E24, E25, E26, E27, E28, E29, E30, E31, E32), List), length(List, Zen).
findall([E0000e, E0001e, E000e0, E000e1, E0010e, E0011e, E001e0, E001e1, E00e00, E00e01, E00e10, E00e11, E0100e, E0101e, E010e0, E010e1, E0110e, E0111e, E011e0, E011e1, E01e00, E01e01, E01e10, E01e11, E0e000, E0e001, E0e010, E0e011, E0e100, E0e101, E0e110, E0e111, E1000e, E1001e, E100e0, E100e1, E1010e, E1011e, E101e0, E101e1, E10e00, E10e01, E10e10, E10e11, E1100e, E1101e, E110e0, E110e1, E1110e, E1111e, E111e0, E111e1, E11e00, E11e01, E11e10, E11e11, E1e000, E1e001, E1e010, E1e011, E1e100, E1e101, E1e110, E1e111, Ee0000, Ee0001, Ee0010, Ee0011, Ee0100, Ee0101, Ee0110, Ee0111, Ee1000, Ee1001, Ee1010, Ee1011, Ee1100, Ee1101, Ee1110, Ee1111], dim5(E0000e, E0001e, E000e0, E000e1, E0010e, E0011e, E001e0, E001e1, E00e00, E00e01, E00e10, E00e11, E0100e, E0101e, E010e0, E010e1, E0110e, E0111e, E011e0, E011e1, E01e00, E01e01, E01e10, E01e11, E0e000, E0e001, E0e010, E0e011, E0e100, E0e101, E0e110, E0e111, E1000e, E1001e, E100e0, E100e1, E1010e, E1011e, E101e0, E101e1, E10e00, E10e01, E10e10, E10e11, E1100e, E1101e, E110e0, E110e1, E1110e, E1111e, E111e0, E111e1, E11e00, E11e01, E11e10, E11e11, E1e000, E1e001, E1e010, E1e011, E1e100, E1e101, E1e110, E1e111, Ee0000, Ee0001, Ee0010, Ee0011, Ee0100, Ee0101, Ee0110, Ee0111, Ee1000, Ee1001, Ee1010, Ee1011, Ee1100, Ee1101, Ee1110, Ee1111), List), length(List, Zen).
%Edges can be either 0 or 1
color(0).
color(1).
even(N) :-
  0 is N mod 2.
odd(N) :-
  1 is N mod 2.
even(A, B) :-
  0 is A mod 2,
  0 is B mod 2.
evenSum(A, B, C, D) :- 
  Sum = A + B + C + D,
  even(Sum).
oddSum(A, B, C, D) :- 
  Sum = A + B + C + D,
  odd(Sum).
%Check that the sum of the edges of a 4-cycle is odd
square(E1, E2, E3, E4) :- 
    color(E1), color(E2), color(E3), color(E4),  %seperates the statements that must be satisfied
    oddSum(E1, E2, E3, E4).
%coordinates on the edge of the cube is a 3 tuple, (x,y,z) <=> Exyz
%Ee00, x = e, y = 0, z=0 
%where e is a place holder for the slot that is changing, the other 2 slots are fixed
%Prolog is a declaritive language, thus we will generate the legal 4 cycles in our friend, Haskell.
cube(Ee00, E0e0, E00e,
     Ee01, E0e1, E01e,
	 Ee10, E1e0, E10e,
	 Ee11, E1e1, E11e) :- 
	 square(Ee00, E0e0, Ee10, E1e0),
	 square(E00e, E0e0, E01e, E0e1),
	 square(E10e, E11e, E1e0, E1e1),
	 square(Ee00, E00e, E10e, Ee01),
	 square(E01e, Ee10, E11e, Ee11),
	 square(Ee01, Ee11, E0e1, E1e1).
%Count the number of cubes:	
%findall ([12 edges], cube(12 edges), list)
%name variables
name something that does things
%name where the elements go
%length(list name, length of list variable)
dim4(Ee110, E101e, E0e11, E00e1, E11e0, E11e1, E10e1, Ee010, E0e01, Ee100, Ee111, E00e0, E111e, E110e, E0e00, E011e, Ee101, Ee011, E001e, Ee000, E010e, E01e1, E100e, E1e00, E1e11, E000e, Ee001, E0e10, E10e0, E1e01, E1e10, E01e0) :-
	square(E000e, E001e, E00e0, E00e1),
	square(E0e00, E010e, E0e01, E000e),
	square(E01e0, E0e00, E0e10, E00e0),
	square(E100e, Ee001, Ee000, E000e),
	square(Ee000, E00e0, E10e0, Ee010),
	square(E0e00, E1e00, Ee000, Ee100),
	square(E01e0, E010e, E011e, E01e1),
	square(E001e, E0e10, E0e11, E011e),
	square(E0e01, E00e1, E0e11, E01e1),
	square(E101e, Ee011, E001e, Ee010),
	square(Ee001, Ee011, E10e1, E00e1),
	square(E1e01, E0e01, Ee001, Ee101),
	square(E100e, E101e, E10e1, E10e0),
	square(E100e, E1e01, E1e00, E110e),
	square(E1e00, E10e0, E1e10, E11e0),
	square(E010e, Ee101, E110e, Ee100),
	square(E01e0, Ee110, Ee100, E11e0),
	square(Ee110, E0e10, E1e10, Ee010),
	square(E110e, E11e1, E11e0, E111e),
	square(E101e, E1e11, E1e10, E111e),
	square(E1e01, E1e11, E10e1, E11e1),
	square(Ee110, Ee111, E111e, E011e),
	square(Ee101, Ee111, E11e1, E01e1),
	square(Ee011, E1e11, Ee111, E0e11).

The rest of this code is large amounts of vertices, extending this to higher dimensions: square.pl

generate_hypercube.py:: Graph / Set Theoretic Exploration
The (U,V,E) definitions of the graph by power set / Hamming distance edge enumeration is what we’ll focus on.

Here is the summary (delta operator in E is meant to be symmetric set difference):

Screenshot from 2014-07-24 01:08:53

Here was my earlier attempt at stating the method, which has written-out examples of \(Q_2\) and \(Q_3\):

Screenshot from 2014-07-24 01:37:48

altcube.py:: String typed n-dimensional cube (legal 4-cycles)

If you represent the vertices as strings, for a hypercube you have:

0000 = 0
0001 = 1
0010 = 2
0011 = 3
0100 = 4
0101 = 5
0110 = 6
0111 = 7
0000 = 8
0001 = 9
0010 = 10
0011 = 11
0100 = 12
0101 = 13
0110 = 14
0111 = 15
The valid edges change 1 bit. So a face changes 2 bits.

One face would have vertices:
1001 = 9
1011 = 11
1101 = 13
1111 = 15

The edges are the ones that change 1 bit:
10011011 = 9,11
10011101 = 9,13
10111111 = 11,15
11011111 = 13,15

You can represent an edge with its odd/even by adding a bit:

110111111 = 13,15 is 1
110111110 = 13,15 is 0

So I can represent a n-cube as a string of all edge values.

To create a higher dimension I would just copy the cubes each twice to get the valid cubes, adding 0 and 1 to all of their vertices respectively.

So that one edge could be:

01101011111 = 13,15 is 1
and
11101111111 = 29,31 is 1

The new edges are all 1 bit off as before.

square.pl:: Method of Computationally Generating Legal 4-cycles

00 01 10 11
insert e as a placeholder, (ex:e00, 0e0, 00e) original[:pos] + ins + original[pos:] Pick all possible combinations of 4 vertices
from vertices choose 4
Find legal 4 cycles:
check that n slots are the same for each element of the array
In the case of 3 dimensions, n=1

Example of a legal 4 cycle: (Ee00, E0e0, Ee10, E1e0)

We know it is legal because doing a columnwise AND

e00
0e0
e10
1e0
001 = 1 slot in common

Filtered Clifford Supermodules

What is Geometric Algebra?

The geometric algebra \(\mathbb{G}^n\) is an extension of the inner product space \(\mathbb{R}^n\). Each vector in \(\mathbb{R}^n\) is an associative algebra with a multivector in \(\mathbb{G}^n\), that is, it is a vector space that satisfied the following properties for all scalars \(a\) and \(A, B, C in \mathbb{G}^n\):

0. \(A(B+C) = AB + AC\), \((B + C)A = BA + CA\)

1. \((aA)B = A(aB) = a(AB)\)

2. \((AB)C = A(BC)\)

3. \(1A = A1 = A\)

4. The geometric product of \(\mathbb{G}^n\) is linked to the algebraic structure of \(\mathbb{R}^n\) by \(uu = u \cdot u = |u|^2 \forall u \in \mathbb{R}^n\)

5. Every orthonormal basis for \(\mathbb{R}^n\) determines a canonical basis for the vector space \(\mathbb{G}^n\).

Geometric algebra represents geometric operations on these objects with algebraic operations in \(\mathbb{G}^n\)

Coordinates are not used in these representations

What is a Clifford Algebra?

Clifford algebras as commutative superalgebras with odd and even parts generated by the odd and even degree monomials, respectively.

If you like, you can think of the real 3-D space as your vector space V with its regular inner product, and now imagine it sitting inside an algebra \(Cl(V)\). (I am omitting a lot of details in the interest of simplicity.) Since \(V\) is three dimensional, so you expect \(Cl(V)\) to have at least that many dimensions, but it turns out it will be \(2^3\) dimensional (and \(2^n\) dimensional for an \(n\) dimensional \(V\).)

Clearly there are many more elements in \(Cl(V)\) than just those in \(V\). The question is: do they have a useful interpretation? The answer is “yes”, because of the way things are set up. It turns out that subspaces of V can be represented as products of elements of \(V\) in \(Cl(V)\). Because multiplication is defined everywhere, you can now “multiply things in \(V\) with subspaces of \(V\)”.

How do we go between superalgebras and graphs?

We could call a ranking of a bipartite graph \(A\) a map \(h: V(A) \rightarrow \mathbb{Z}_2\) that gives \(A\) the additional structure of a ranked poset on \(A\) via \(h\) as the rank function.

If you have said ranked poset and rank function \(h\), then we can identify \(A\) as the Hasse diagram of the ranked poset.

Proof from Yan Zhang’s thesis

Screenshot from 2014-07-21 23:19:22

Instead of choosing 4 element sets as is outlined below in the Graph/Set theoretic approach, Yan defined an |E| element binary string (sort of like a bit mask) for each cycle with a 1 in each position where the corresponding edge belongs to that cycle (It’s easy to think about or draw in 2 / 3 / 4 dimensions). The become the rows of a matrix. You can define the coloring of edges as an |E| element 0/1 column vector and it is then possible to make the leap to say that the product of the matrix and the vectors will be a row vector of ones in the case of a successful odd dashing. Playing with that should make it clear that the rank of that matrix defines the dimensionality of the cycle space, which is equivalent to a number of similar linear algebra formulations.

Additional Insights

1

Recursive Generation of Faces and Edges

Credit: Chris Walker

\(v_n = 2^n\)
\(e_n = 2e_{n-1}+v_{n-1}\)
\(f_n = 2f_{n-1}+e_{n-1}\)

A Promising Method & Proven Bijection

\(\mathbb{Z}^E_2 \rightarrow \mathbb{Z}^F_2/\mathbb{Z}^1_1\)

In the case of n = 3, we have edges and 6 faces

\(12 \rightarrow 6+1\)

\(2^{edges – faces}\)

(Rank Nullity Theorem)

The preimage of a point under a linear map is always the size of the kernel, thus there are the same number of even and odd legal colorings, and the difference between 2 odd cubes is always even.

Alex’s Thoughts

A null connection and its inverse give a higher order null connection, where null connection means none of the edges connecting sub-cubes are value 1:

A null connection and its inverse give a higher order null connection
Credit: Alex Ray

Clean enumeration such that each unique \(2^n-1\) length binary string straightforwardly generates a unique solution.

Credit: Alex Ray

10566357_10202419629317565_1642026497_n

Conclusion

You know those problems which you know you shouldn’t be thinking about but keep bugging you so you occasionally work on them in desperation and then forcibly shove them to the backburner?

This is one of those problems. We’ve conquered it.

An Autodidact’s Topology Curriculum

My topology curriculum is an example of How To: Learn a New Discipline.

0. Build the map.

The map is a high level representation of important concepts and connections — the threads that compose the subject.

I started by working through these two:

Screenshot from 2014-07-25 18:43:02

Screenshot from 2014-07-25 18:44:32

Where “work through” \(\equiv\) read carefully and annotate the text, take notes on important concepts, and complete a few exercises from each chapter.

j

“Catherine, you said you’d teach me math. Why are you drawing squiggles?”

Screenshot from 2014-07-25 18:58:39
Screenshot from 2014-07-25 18:59:21

“Math is formalized art! I get to draw these squiggles on a page, describe them with symbols, and call it math.”

1. Learn by working through complementary perspectives in parallel.

Hatcher
May

2. Give weekly lectures on what you’ve learned.

I’m giving informal lectures to a small group of people on what I’m learning. These people ask questions and tolerate pauses to look things up.

Don’t forget to ask for help when you get stuck!

If you can’t find a satisfactory explanation online:

Respect Our Work.

Already, criticism has be thrown at me for deciding to focus on pure mathematics. I am often told (with the best intentions) that I should go back to doing applied math/engineering. I’m guessing that other people who’ve decided to study theoretical subjects suffer from a similar lack of respect.

Hopefully, this post will be helpful for you, my friends. Perhaps, to send to your families, engineers, etc. to save you time when you are sick of answering the same questions — laced with misunderstanding. Perhaps, to find consolation and recognize that you are not alone.

This post (admittedly written with the muses of frustration and maths evangelism) can be generalized to theoretical endeavors of any flavor.

Why do you want to study theoretical science/math?

Image Source
Image Source

Why do I want to study pure math? The same reason that the scientist is providing above.

There is an itch in minds of the analytic and aesthetically inclined that mathematics scratches like no other.

I encourage you to read A Mathematician’s Apology and What is it Like to Understand Advanced Mathematics?.

What if you aren’t good at math?

It doesn’t matter if you’re good at mathematics or not if you enjoy doing it and have people willing to help you learn.

You’ve picked something that you enjoy doing, and you’re rolling with it.
Thereafter, if you do it for long enough, you’ll become good at it.

Don’t you want to help people?

Because of its abstractness, mathematics is universal in a sense that other fields of human thought are not. It finds useful applications in business, industry, music, historical scholarship, politics, sports, medicine, agriculture, engineering, and the social and natural sciences. The relationship between mathematics and the other fields of basic and applied science is especially strong.

Source

Here’s an exploration of Which Mathematical Ideas Have Done The Most To Change History?.

How can math make you a better person?

10152501_10152050265458030_1235372241_n

Math provides you with powerful intuitions that can improve your daily life:

0. Maths develops the logical mindset, assiduous and aesthetic values needed to implement regular concise conversation and clear explanation. It teaches us to not accept hand-wavey proofs, but to derive them ourselves from first principles.

1. The ability to analyze a problem as a structure, work it out step by step and solve it generally translates between fields, allowing one trained in maths to easily move to other puzzle-based disciplines. For example, a maths person can transfer their skillset to computer programming by seeing code and programming languages as a collection of structures and rules governing their interactions.

2. An understanding of maths allows us to appreciate our environment by observing patterns and connections between objects that we wouldn’t otherwise see. After studying a field such as Model Theory, you begin to see deep connections (across fields of study) in the abstractions of seemingly unrelated concepts. Limiting yourself to the current ideas of one discipline makes original research unnecessarily difficult. I find that most original research is really just connecting past ideas into a new idea that is more than the sum of its parts.

3. Some visually oriented mathematicians overlay representations of abstract concepts on their environments as they go about daily life. This visual overlay of abstract stimuli increases the ability to appreciate things in their own right and builds visual intuition. However, overlaying mathematics on life differs significantly from making a mathematical model of your surroundings: the latter is far more concrete. Overlaying connections on stochastic stimuli is an enrichment to perception, whereas modeling stimuli is separate from it.

Visual intuition is important for research on the leading edge of science and mathematics (especially in geometry). Formalisms come after a topic is well understood.

4. The ability to describe mental pictures in a generalized symbolic fashion is incredibly powerful. The symbolic language of mathematics allows us to represent concepts generally without extraneous information, which permits each viewer to perceive the equations according to which mode of translation best suits their thought processes.

At this point, I’ll cease indulging my evangelism and go back my studies.

Basic Topology

Topological Maps in Robotic Navigation

The goal for an autonomous robot is to be able to construct (or use) a map or floor plan and to localize itself in it. The discipline of robotic mapping is concerned with map representation.

The internal representation of a map can be “metric” or “topological”:

  • A metric framework (the most common for humans) considers a two-dimensional space in which it places the objects. The objects are placed with precise coordinates. This representation is very useful but is sensitive to noise and it is difficult to calculate the distances precisely.
  • A topological framework only considers places and relations between them.
    • This topological map is a graph-based representation of the environment where certain easily distinguishable places in the environment, labeled as landmarks, are designed as nodes.
    • The edges are deemed to represent navigable connections. In addition, the edges of the topological graph may be annotated with information relating to navigating the corresponding regions in the environment. This framework is more resistant to noise and generally easier to store internally.

example-15

The robot needs to know what room it’s in and what doors it needs to pass through to get to the required location. This does not require the dimensions and shape of the rooms.

This post highlights how the axioms governing the metric space naturally lead into its abstraction: the topological space.

The Metric Space

A metric space is:

  • a set of \(X\)
  • a distance function \(d(x,y)\) which defines the distances between all members of the set.

For example, the distance function on the real line \(\mathbb{R}^1\) is \(d(x,y) = |x-y|\).

This distance function takes a pair of 2 ordered numbers \((x,y)\) and gives us another real number (the distance between \(x\) and \(y\)). We can easily generalize this distance function from the real line \(\mathbb{R}\) to any n-dimensional space \(\mathbb{R}^n\):

\(d: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}^n\)

We can have two different distance functions on the same space \(\mathbb{R}^2\)

For each pair of points \((x_0, y_0)\) and \((x_1, y_1)\) \(\mathbb{R}^2\),

the normal distance function is derived from the Pythagorean therorem:

  • \(d ((x_0, y_0), (x_1, y_1)) = \sqrt{(x_0 – x_1)^2 + (y_0-y_1)^2}\)

With this distance function, \(d(x, a) \leq 1\) for a fixed point \(a \in \mathbb{R}^2\).

  • \(d'((x_0, y_0), (x_1, y_1)) =\) maximum \({|x_0-x_1|, |y_0 – y_1|}\).

The distance function of a Hilbert space is

  • \(d(u,v) = [\sum\limits_{i=1}^{\infty} (u_i – v_i)]^{1/2}\)

Neighboorhoods

The concept of a neighborhood is powerful, for it formalizes the concept at the heart of analysis: continuity.

An open neighborhood of a point \(p\) in a metric space \((X, d)\) is the set \(N_\epsilon = {x \in X | d(x, p) < \epsilon}\).

Example:

  • If \(p \in \mathbb{R}\) then the open-interval of \(p\) is \((p – \epsilon, p + \epsilon)\) of radius \(\epsilon\) centered at \(a\).
  • The open disc and open ball, which are the 2D and 3D analogues of the open interval. (I haven’t explained these yet, I’ll formally cover this example of a neighborhood later)

A function \(f\) is continuous over a space \(X\) iff \(\forall x, p \in X\) the following condition is satisfied:

\(\forall \epsilon \exists \delta\) \(|\) \(x \in N_\epsilon(p) \rightarrow f(x) \in N_\delta(f(p))\)

This formal understanding of continuity leads directly to the unifying concept of this lecture, the study of “closeness”: the open set.

A subset \(S\) of a metric space \(X\) is an open set iff every point of \(S\) has an open neighbourhood \(N_\epsilon\) that lies completely in \(S\). In precise terms:

\(S\) is open \(\Leftrightarrow \forall a \in S \exists \epsilon > 0 | N_\epsilon(a) \subseteq S\).

Properties of Open Sets

1. The union (of an arbitrary number) of open sets is open.

Proof

Let \(x \in \bigcup\limits_{i \in I} A_i = A\). Then \(x \in A_i\) for some \(i\). Since \(A_i\) is open, by the definition of an open set: \(x\) has an open neighbourhood lying completely inside \(A_i\) which is also inside \(A\). \(_{QED}\)

Proof

To check that finite intersections of open sets are again open, it suffices to check this for the intersection of two open sets. Suppose \(x \in A \cap B\).

Then \(x \in A\) and also has a neighbourhood, \(N_{\epsilon_A}\) lying in \(A\). Similarly, \(x\) has a neighbourhood \(N_{\epsilon_B}\) lying in \(B\). If \(\epsilon =\) min \({\epsilon_A, \epsilon_B}\), the neighbourhood \(N_\epsilon\) also lies in both \(A\) and \(B\) and hence in \(A \cap B\). \(_{QED}\)

Continuous Functon

In analysis, we examine the convergence of sequences, the continuity of functions, and the compactness of sets. Some types of convergence, such as the pointwise convergence of real-valued functions defined on an interval, cannot by expressed in terms of a metric on a function space.

Topological spaces provide a general framework for the study of convergence, continuity, and compactness. The fundamental structure on a topological space is not a distance function, but a collection of open sets.

A continuous function can be defined in terms of open sets.

If \(f: X \rightarrow Y\) is a continuous function between metric spaces and \(B \subset Y\) is open, then \(f^{-1}(B)\) is an open subset of \(X\).

Proof

Let \(x \in f^{-1}(B)\). Then \(f(x) = y in B\).

Since \(B\) is open, the point \(y\) has a neighbourhood \(N_\epsilon \subset B\).

By the definition of continuity, \(N_\epsilon\) contains the image of some neighbourhood \(N_\delta\) \(V\) of \(x\). Since \(f(V) \subset B\), we have \(V \subset f^{-1}(B)\) and so \(x\) has this nieghbourhood \(N_\delta \subset f^{-1}(B)\).

Hence, the definition of an open set, \(f^{-1}(B)\) is open in \(X\).

The converse also holds: If \(f: X \rightarrow Y\) is a function for which \(f^{-1}(B)\) is open for every open set \(B\) in \(Y\). Proving this here would only take the joy of proving this away from the reader: it’s a short proof, you can do it!

The Open Ball: Interior and Boundary Points

As we mentioned earlier: in \(\mathbb{R}^1\), the open neighbourhood is the open interval. In \(\mathbb{R}^2\) it is the open disc. In \(\mathbb{R}^3\) it is the open ball.

An \(n\)-dimensional open ball of radius \(r\) is the collection of points of a distance less than \(r\) from a fixed point in Euclidean \(n\)-space. Explicitly, the open ball with center \(p\) and radius \(r\) is defined by:

\(B_r (p)= {x \in \mathbb{R}^n | d(p,x) < r}\)

if \(X\) is a metric space with metric \(d\), then \(x\) is an interior point of \(S\) if there exists \(r > 0\), such that \(y\) is in \(S\) whenever the distance \(d(x,y) < r\).

Equivalently, if \(S\) is a subset of a metric space, then \(x\) is an interior point of \(S\) iff (there exists an open ball with a radius larger than 0 centered at \(x\) which is contained in \(S\)):

\(\exists r\) \(|\) \(x \subseteq B_r (x)\)

A friend of the interior point is the definition we’ve been dancing around: a boundary point.

Intuitively, a point is an interior point of it is not “right on the edge” of a set, and a boundary point if it is “right on the edge” of a set.

Formally, a point \(p\) is a boundary point of \(S\) iff for every \(\epsilon > 0\), the open neighbourhood of \(p\) intersects both \(S\) and the complement of \(S\): \(\bar{S}\). That is: \(x\) is a boundary point of \(S\) iff:

\(N_\epsilon(p) \cap S \neq \emptyset\) and \(N_\epsilon(p) \cap \bar{S} \neq \emptyset\)

Sidenote: The complement \(\bar{S}\) of \(S\) is \(U\) \(S\), the set of all things outside of \(S\). This can be rephrased as all things (in the universal set \(U\)) that are not in \(S\).

Topological Balls

We may talk about balls in any space \(X\), not necessarily induced by a metric.

An (open or closed) \(n\)-dimensional topological ball of \(X\) is any subset of \(X\) which is homeomorphic to an (open or closed) Euclidean \(n\)-ball. Topological \(n\)-balls are important in combinatorial topology, as the building blocks of cell complexes.

Toplogical Spaces

Recall that a metric space is just a set \(S\) with a metric defined on it.

A topological space is a set \(S\) with a geometric structure defined on it.

Abstractions of the properties of open sets are the axioms that define a topology \(T\). Moreover, we call an element of \(T\) is an open set.

top

1. The union (of an arbitrary number) of open sets is open.
=> The union of any set of members of \(T\) is in \(T\).

2. The intersection of finitely many sets is open.
=> The intersection of finitely many members of \(T\) is in \(T\).

For completeness, the whole set \(S\) and \(\emptyset\) are also in \(T\).

Notational aside: We call the pair \((S, T)\) a topological space; if \(T\) is clear from the context, then we often refer to \(S\) as a topological space.

3. If \(f: X \rightarrow Y\) is a continuous map between topological spaces and \(B \subset Y\) is open, then \(f^{-1}(B)\) is an open subset of \(X\).

Screenshot from 2014-09-29 15:55:36

Basis of a Topology

Let’s construct a topology of the reals.

We want to know the minimum data you need to specify a structure defined on a set. In many cases, this minimum data is called a basis and we say that the basis generates the structure.

The collection of open intervals of the form \((p – \epsilon, p + \epsilon)\) on \(\mathbb{R}\) is not a topology. The collection of such intervals doesn’t include the empty set, the whole line, or the union \((1,2) \cup (3,4)\).

The usual topology is not defined as the collection of such intervals. Instead, the topology is defined as the collection of all possible unions of such intervals. In other words, the intervals of the form \((p – \epsilon, p + \epsilon)\) are a basis for the topology. It’s important to not confuse the basis with the whole topology.

The metric topology is the topology on a set \(X\) generated by the basis \({B_\epsilon(x) | \epsilon > 0, x \in X}\).

In many areas of mathematics we would like to endow our sets with additional structures, such as a metric, a topology, a group structure, and so forth.

It is here that I will stop, this post, but I will give you some keywords to look up:

Linear Functionals and Bilinear Forms, Riesz Representation Theorem, Linear, Bounded, Continuous, comparing topologies: \((S, T’)\) has more open subset to separate 2 points in \(S\) than \((S, T)\).

Topology of Robot Motion Planning
Topological Robotics: Motion Planning in Projective Spaces
http://www.math.ucla.edu/~tao/preprints/compactness.pdf
Basic Facts About Hilbert Space
Consistent Observation Grouping for Generating Metric-Topological Maps that Improves Robot Localization
Mobile Robots Navigation, Mapping, & Localization: Part II
Alegbraic Topology for Computer Vision