Replication details for 1703.09680

This post documents replication details for paper Certifying numerical estimates of spectral gaps by M. Kaluba, P.W. Nowak.

This guide is rather outdated. All of the computations can be done (and much more effectively) by exploiting the symmetry of the Laplacian as is described in Replication Details for 1712.07167. For more details on the method see $\operatorname{Aut}(\mathbb{F}_5)$ has property (T).

Table of Contents

Installing

To run the code You need julia-v0.5 (should work on v0.6, but with warnings). You also need to install julia packages: Nemo-v0.6.3, ArgParse. To do so in julia’s REPL run:

Pkg.update()
Pkg.add("Nemo")
Pkg.add("ArgParse")

Then clone the main repository of Groups.jl, GroupRings.jl and PropertyT.jl:

Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/Groups.jl.git")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/GroupRings.jl.git")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/PropertyT.jl.git")
Pkg.resolve()

This should resolve all dependencies (e.g. install JuMP, SCS, IntervalArithmetic, JLD, Memento). Exit julia and clone GroupswithPropertyT

git clone https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT.git
cd GroupswithPropertyT

Running

To check that $\Delta^2-\lambda\Delta$ is not decomposable to a sum of hermitian squares of elements in the ball of radius $2$ in $SL(2,7)$ run

julia SL.jl -N 2 -p 7 --radius 2 --iterations 100000

(~30 seconds, depending on hardware). The monotonous decreasing $\lambda$ during the optimisation is in column pri obj (or dua obj) of solver.log.

Compare this to

julia SL.jl -N 2 -p 7 --radius 3 --iterations 100000

which finds $\lambda \geq 0.5857$ and decomposes $\Delta^2-\lambda\Delta$ into sum of $47$ hermitian squares in less than 20 seconds (including certification).

If You see in the output (or in full.log) that the upper end of the interval where $\lVert\Delta^2 - \lambda\Delta - \sum{\xi_i}^*\xi_i\rVert_1$ belongs to is too large (resulting in positive Floating point distance, but negative The Augmentation-projected actual distance), decrease the --tol parameter, e.g.

julia SL.jl -N 2 -p 7 --radius 3 --iterations 100000 --tol 1e-9

to achieve a better estimate (the residuals $\ell_1$-norm should be around $|B_d(e))|*tol$)

Help

julia SL.jl --help
usage: SL.jl [--tol TOL] [--iterations ITERATIONS]
             [--upper-bound UPPER-BOUND] [--cpus CPUS] [-N N] [-p P]
             [--radius RADIUS] [-h]

optional arguments:
  --tol TOL             set numerical tolerance for the SDP solver
                        (type: Float64, default: 1.0e-6)
  --iterations ITERATIONS
                        set maximal number of iterations for the SDP
                        solver (default: 20000) (type: Int64, default:
                        50000)
  --upper-bound UPPER-BOUND
                        Set an upper bound for the spectral gap (type:
                        Float64, default: Inf)
  --cpus CPUS           Set number of cpus used by solver (type:
                        Int64)
  -N N                  Consider elementary matrices EL(N) (type:
                        Int64, default: 2)
  -p P                  Matrices over field of p-elements (p=0 => over
                        ZZ) (type: Int64, default: 0)
  --radius RADIUS       Radius of ball B_r(e,S) to find solution over
                        (type: Int64, default: 2)
  -h, --help            show this help message and exit

Specific version of the article

To checkout the specific versions of packages used for Certifying Numerical Estimates of Spectral Gaps run (inside GroupswithPropertyT)

git checkout 1703.09680v1

You need to link ~/.julia/v0.5/GroupRings to ~/.julia/v0.5/GroupAlgebras due to change in the name of the package. Then run in julia

Pkg.checkout("GroupRings", "1703.09680v1")
Pkg.checkout("PropertyT", "1703.09680v1")
Pkg.resolve()
Avatar
Marek Kaluba
Assistant Professor

My research interests include computational algebra, geometric group theory (in particular: property (T)) and surgery aspects of manifolds.