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

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