What is this?
Short answer: mathematical tools
Technical answer:
An LSV complex is a finite simplicial complex that is a quotient of an infinite simplicial complex known as an affine building of type
Features
The notation here refers to the draft linked above.
- Operations in the algebra
$\mathcal{A}(R)$ and group$\mathcal{G}(R)$ - Projective matrix calculations in
$\text{PGL}_3(\mathbb{F}_q)$ for$q = 4, 8, 16$ - Computing Cartwright-Steger generators for
$\mathcal{G}(R)$ and their projective matrix representations - Generation of Cayley graph for generators in
$\mathcal{G}(R)$ ,$\mathcal{G}(R/I)$ and$\text{PGL}_3(\mathbb{F}_q)$ - Computing 2-d clique complex of a graph
- Representation of two-dimensional simplicial complexes (including graphs) as boundary matrices of
$\mathbb{F}_2$ -chain complexes - Linear algebra with large sparse or small dense matrices over
$\mathbb{F}_2$ - Matrix reduction aka computing Smith normal form
- Computing dimension of first homology and cohomology (simplicial mod two homology) by rank considerations
- Computing generators for homology by computing an aligned basis of
$B_1$ inside of$Z_1$ - Finding the systole of
$L_2$ by computing the injectivity radius in the cover - A simplicial cosystole algorithm (works for small complexes, too slow for
$L_2$ )
Most of the code involved directly in the above features is well-tested, but be warned there is plenty of experimental code here as well. The reader is encouraged to email me if you want to use this code, and let's talk about it!
To build
source env.bash
make test
To use
See the comments in worksets/Makefile. We highlight a few recipes here.
Recipe A. Generate the Cayley complex of
mkdir worksets/aaa
cd worksets/aaa
echo 111 > modulus.txt
echo 8 > max-depth.txt
make -f ../Makefile dim-H1.txt
Recipe B. Construct the boundary maps for the
mkdir worksets/bbb
cd worksets/bbb
make -f ../Makefile pgl-cayley-F16
Profiling. Most of the programs are built with support for cpu profiling. Profiling is off by default and can be toggled on and off by sending a USR1 signal to the program. Profile data is written to cpu.out and will be overwritten, so rename the files if you want to capture more than one profiling session in the lifetime of a process.
Example:
P=`ps -o comm,pid |grep smith |awk '{print $2}'`
kill -USR1 $P; sleep 600; kill -USR 1
go tool pprof -http : # opens browser
To Do
A bunch of this code is not specific to LSV complexes. Factor out packages for mod two linear algebra, generic simplicial complexes, homology, Cayley expansion.
References
[EKZ] Shai Evra, Tali Kaufman, Gilles Zémor. Decodable quantum LDPC codes beyond the
[LSV] Alexander Lubotzky, Beth Samuels, Uzi Vishne. Explicit constructions of Ramanujan complexes of type