Stop Staring and Compute! Automorphism Groups of Rational Curves

Let’s compute the automorphism groups of some curves. There are many ways to do this! We will be using 3 different algorithms for this.

Directly into your terminal using SageMath

Let’s start with the most straightforward one. Run sage and type this into your terminal, hitting enter after each line.

A.<x,y>=AffineSpace(QQ,2)
C=Curve(y^8-x*(x-1)^4)
S=C.riemann_surface(prec=100)
G=S.symplectic_automorphism_group()
print(G.gens()[0:15])
print(G.order())

Technical P.S.: For sufficiently high degree curves, this will throw a segmentation fault. One must then narrow down where it is coming from. There are three hidden steps before the endomorphism basis calculation, so look for which it is throwing an error:

S=C2.riemann_surface()
_ = S.homology_basis() # [1]
_ = S.cohomology_basis() # [2]
_ = S.period_matrix() # [3]

Sage Function for Rational Curves

Let’s start with the most straightforward one. Save this file, and start sage in the same folder. Then, load(“file.sage”) will run the program. This is just a rephrasing of the previous method.

from sage.schemes.riemann_surfaces.riemann_surface import RiemannSurface, RiemannSurfaceSum
R.<x,y> = QQ[]
def aut(f):
print(f)
S = RiemannSurface(f, prec = 100)
try:
G = S.symplectic_automorphism_group()
print("OH LAWD ITS COMING")
print(G.gens()[0:15])
print(G.order())
#check_order(G.gens())
except:
print(str(IOError))
pass
#any plane curve goes here
f = y^8 - x*(x-1)^4
aut(f)

Alternative code

We can also do:

f2 = any plane curve
f1 = hyperelliptic curve of same genus
S1 = RiemannSurface(f1, prec = 100)
T = RiemannSurfaceSum([ S1 ])
T.tau = S2.riemann_matrix()

Finding Group Structure of Output Set

We get the following matrix output. Then, we clean the matrix output, and declare it to be a group in GAP (gap-core as a linux package). GAP then returns a structure description.

([ 0 0 1 -1]
[ 0 0 -1 0]
[ 0 1 1 0]
[ 1 1 0 1], [ 1 0 -1 1]
[ 0 1 1 0]
[ 0 -1 0 0]
[-1 -1 0 0], [ 1 1 0 1]
[-1 0 1 -1]
[ 0 -1 -1 1]
[-1 -1 -1 0], [ 0 -1 -1 1]
[ 1 1 1 0]
[-1 -1 0 -1]
[-1 0 1 -1], [ 0 0 0 -1]
[ 0 0 -1 1]
[ 1 1 1 0]
[ 1 0 0 1], [ 1 0 0 1]
[ 0 1 1 -1]
[-1 -1 0 0]
[-1 0 0 0], [ 0 0 -1 1]
[ 0 0 0 -1]
[ 1 0 0 1]
[ 1 1 1 0], [ 0 0 -1 0]
[ 0 0 1 -1]
[ 1 1 0 1]
[ 0 1 1 0], [ 1 1 1 0]
[ 0 -1 -1 1]
[-1 0 1 -1]
[-1 -1 0 -1], [ 1 0 -1 1]
[-1 -1 0 -1]
[ 1 1 1 0]
[ 0 1 1 -1], [ 0 -1 -1 1]
[-1 0 0 -1]
[ 1 0 0 0]
[ 1 1 0 0], [ 0 1 1 0]
[ 1 0 -1 1]
[-1 -1 0 0]
[ 0 -1 0 0], [0 1 0 0]
[1 0 0 0]
[0 0 0 1]
[0 0 1 0], [-1 0 0 0]
[ 1 1 0 0]
[ 0 -1 -1 1]
[ 1 0 0 1], [ 1 0 0 1]
[-1 -1 -1 0]
[ 0 0 1 -1]
[ 0 0 0 -1])

We clean this output with regex, or manually as follows:

1. find ], [ replace ]],[[
2. find /n, replace ,
3. find doublespace, replace space
4. find [space, replace [
5. find space replace ,
6. find ,, replace ,
7. find [, replace [
8. change ([ and )] to ([[ and ]]) resp.
9. Open gap and plug in:
G := Group([[0,0,1,-1],[0,0,-1,0],[0,1,1,0],[1,1,0,1]],[[1,0,-1,1],[0,1,1,0],[0,-1,0,0],[-1,-1,0,0]],[[1,1,0,1],[-1,0,1,-1],[0,-1,-1,1],[-1,-1,-1,0]],[[0,-1,-1,1],[1,1,1,0],[-1,-1,0,-1],[-1,0,1,-1]],[[0,0,0,-1],[0,0,-1,1],[1,1,1,0],[1,0,0,1]],[[1,0,0,1],[0,1,1,-1],[-1,-1,0,0],[-1,0,0,0]],[[0,0,-1,1],[0,0,0,-1],[1,0,0,1],[1,1,1,0]],[[0,0,-1,0],[0,0,1,-1],[1,1,0,1],[0,1,1,0]],[[1,1,1,0],[0,-1,-1,1],[-1,0,1,-1],[-1,-1,0,-1]],[[1,0,-1,1],[-1,-1,0,-1],[1,1,1,0],[0,1,1,-1]],[[0,-1,-1,1],[-1,0,0,-1],[1,0,0,0],[1,1,0,0]],[[0,1,1,0],[1,0,-1,1],[-1,-1,0,0],[0,-1,0,0]],[[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]],[[-1,0,0,0],[1,1,0,0],[0,-1,-1,1],[1,0,0,1]],[[1,0,0,1],[-1,-1,-1,0],[0,0,1,-1],[0,0,0,-1]]); StructureDescription(G);

Check that this structure description matches the order claimed by this sage program. For context on how this works, see section 5.1 of this paper https://arxiv.org/pdf/1811.07007v2.pdf. The reason numerical approximation is sound is listed in 5.3.

If you’d like to go even further, and compute the period matrix as well, the code for that is here., and section 5.2 of this paper https://arxiv.org/pdf/1811.07007v2.pdf.

Sage Program for Superelliptic (only?) Curves

This is much faster than the previous code, was implemented by Bruin-Sijsling-Zotine, and is based on this algorithm from Molin-Neuhror https://arxiv.org/abs/1707.07249 . Unfortunately, I also find it quite finnicky sometimes, which is why I list it second.

Magma Program for Superelliptic Curves

Magma doesn’t throw segmentation faults as often. So, to use this, one must have magma on your machine (not just the magma calculation) as it is necessary to concurrently use must download this package of Edgar Costa. https://github.com/edgarcosta/endomorphisms

SetVerbose("EndoFind", 0);
SetVerbose("CurveRec", 0);
prec := 300;
F := RationalsExtra(prec);
CC := FCC;
R<x> := PolynomialRing(F);
p := x^4 - x;
e := 3;
// Construct superelliptic curve y^3 = x^4 - x
S := RiemannSurface(p, e : Precision := Precision(CC));
P := BigPeriodMatrix(S);
P := ChangeRing(P, CC);
GeoEndoRepCC := GeometricEndomorphismRepresentationCC(P);
GeoEndoRep := GeometricEndomorphismRepresentation(P, F);
print GeoEndoRep;

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.

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.”

An adinkra is odd if the sum of every 4-cycle in the adinkra is odd.

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.

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.

Computational Attacks

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:
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.

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):

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

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

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.

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:

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

Credit: Alex Ray

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.

Semi-Autonomous Robotics: (2012) My 1st Software Project

I’m experimenting with committing past projects to github.

Over the summer (2012) at George Washington University Robotics Lab – Positronics Divison (with Roxana Leonetie as my mentor and Gregory Colella as my research partner), we wrote a package for the PR2 using ROS stacks and Python. In short, the PR2 completes a task moving a dowel into a hole (using only force proprioception) as a response to dynamic stimuli.

If you are unfamiliar with the PR2:

Greg was relatively new to Python (an experienced Java coder), and I learned to code the same summer that we completed the project (previously, I had dabbled in mainly math and physics). Bear this in mind while viewing our project.

This is an early demo I simulated in gazebo of the PR2 learning to replicate arm movements (a major part of the project).

Generate CSV of Google Music Playlist

I recently switched my music vendor from Google Music to Spotify. To avoid manually searching for each song, I semi-automized the transition as follows.

1. Generate a CSV (artist, title) from your Google Music Playlist. Zoom your window out all the way (querySelectorAll will only load a static list of currently active rows).

// Run in Chrome's Developer Tools Console: Crtl+Shift+I
var playlist = document.querySelectorAll('.song-table tr.song-row');
for(var i =0; i<playlist.length ; i++) {
var l = playlist[i];
var title = l.querySelectorAll('td[data-col="title"] .content')[0].textContent;
var artist = l.querySelectorAll('td[data-col="artist"] .content')[0].textContent;
console.log(artist.replace(","," ") + ',' + title.replace(","," ")); //take out "," to clean up CSV
}

Scroll and rerun until you have all entries.

2. Open your CSV in vim to remove the VM290:8 at the end of each entry. For example:
Clamavi De Profundis,Far Over the Misty Mountains Cold VM290:8

:%s/.{8}//

Now you have a CSV file of arists, titles to do with what you wish.
To proceed with migrating this playlist to Spotify specifically, continue to steps 3 & 4.

3. Copy/paste into Ivy.

4. Paste Ivy results into desired playlist.

Terminal Hexagonal Lattice

Here: have a script to generate plaintext hexagonal lattices for you when you’re feeling blue.

import itertools
pattern1 = ". ."
pattern0 = "   "
def main(repeat,length):
for _ in itertools.repeat(None, length):
print (pattern1+pattern0)*repeat
print (pattern0+pattern1)*repeat
if __name__ == "__main__":
main(10,10)

. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .
. .   . .   . .   . .   . .   . .   . .   . .   . .   . .

SPOILERS: Using Simple Combinatorics

DISCLAIMER: This is the solution to Project Euler’s problem 15. Please attempt to solve the problem yourself before reading my solution.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

I like to use this problem to demonstrate the efficacy of using simple maths to improve code.

from itertools import permutations
def unique(iterable):
seen = set()
for x in iterable:
if x in seen:
continue
yield x
options = [1]*20 + [0]*20
counter = 0
for a in unique(permutations(options)):
counter = counter+1
print counter

Use simple combinatorics!

To find the number of unique routes through a 20×20 grid, use our friend: the concept of permutations with repeated elements:

$$\frac{\text{number of elements}!}{\text{repetitions of character}!*\text{repetitions of other character}!*…}$$

import math
print math.factorial(40)/(math.factorial(20)*math.factorial(20))

Even better – one line in Haskell:

product [1..40] div product[1..20]^2

HackMIT: Polyglass

I attended HackMIT 2013 and had an absolute blast! Kartik Talwar, Spencer Hewett and I make a fantastic team.

In the turmoil that followed the hackathon (taking a weekend off of schoolwork and research has consequences), it slipped my mind to post our project!

We created Polyglass. A Google Glass application that analyzes the video in slow motion using the Eulerian magnification algorithm to calculate the human pulse from a video frame in quasi-real-time. Using video alone, we achieve the same functionality as a polygraph.

The picture below is a demo of our project; it compares the original video frame to the frame processed by Eulerian Magnification. This processing is an implementation of the Eulerian Magnification framework published by MIT.

Portions of our source are on Kartik’s github.

Braille Cell with VPython

The internet went down at my house, and I decided to play with vpython again!

#type individual brl cell using numkeys
from visual import sphere
R = 0.2 #filled dot radius
r = 0.1 #empty dot radius
#corresponds to numkeys
dotdict = {
'7': [1,3], #dot 1
'4': [1,2], #dot 2
'1': [1,1], #dot 3
'8': [2,3], #dot 4
'5': [2,2], #dot 5
'2': [2,1] #dot 6
}
fulldot = dotdict.keys()
def draw(dots):
[sphere(pos=dotdict[dot], radius=r) for dot in fulldot] #create empty dot matrix to represent empty cell
[sphere(pos=dotdict[dot], radius=R) for dot in dots] #fill appropriate dots
string = raw_input()
if string.isdigit(): draw(str(string))


Let’s see it in action! The letter “j” (or “just” in G2):

Simple Cubic Lattice

Today, let’s have some fun playing with perspective rendering in Python! My graphics package of choice is VPython:

sudo apt-get install python-visual

Suppose we want to represent a simple cubic lattice: Using the visual package, we can create a collection of spheres at positions $$(i,j,k)$$ with $$i,j,k = -L…L$$.

from visual import sphere
L = 5
R = 0.3
for i in range(-L,L+1):
for j in range(-L,L+1):
for k in range(-L,L+1):
sphere(pos=[i,j,k],radius=R)

Resulting in this beautiful rendering:

But what if we want to change the color? Simply alter the last line:

sphere(pos=[i,j,k],radius=R).color = color.blue

Less atoms? Alter the value of L.

 L = 1

Same number of atoms with smaller radii? Alter the value of R.

 R = 0.2`

Want more advanced computational physics with Python?