No Description

kalmarek fa326a147f add deprecation warning 3 months ago
groups c075b93313 split definitions of action to a separate file 11 months ago
positivity f1d0ff9c14 \lambda = 50.0 got certified! 10 months ago
.gitignore 9fc23c43d7 ignore python files 11 months ago
CPUselect.jl 788da99d82 separate set_parallel_mthread(N::Int, workers::Bool) 1 year ago
FPGroups_GAP.jl 6acdff2b70 increase O.maxstates to 1000*$maxeqns 1 year ago
LICENSE.md 256422cf1b license under GPL 1 year ago
README.md fa326a147f add deprecation warning 3 months ago
logging.jl b41f2ccdc8 add default log name 1 year ago
main.jl 7b06dc1eb2 fix upper-bound in Settings 1 year ago
run.jl 7dd061cdb7 fix typos 1 year ago
runtests.jl a1e4a917a6 include all groups in runtests.jl 1 year ago

README.md

DEPRECATED!

This repository has not been updated for a while! If You are interested in replicating results for 1712.07167 please check these instruction Also this notebook could be of some help. If everything else fails the zenodo dataset should contain the last-resort instructions.

This repository contains some legacy code for computations in Certifying Numerical Estimates of Spectral Gaps.

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 finally clone this repository:

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

Running

Naive implementation

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))|\cdot tol$)

Symmetrization enhanced implementation

A newer version of the software uses orbit and Wedderburn decomposition to effecitively find a (much) smaller optimisation problem to compute the spectral gap $\lambda$. In particular the solution to the original (naive) optimisation problem can be reconstructed from the solution of the symmetrised one.

E.g. Run

julia SL_orbit.jl -N 4 --radius 2 --upper-bound 1.3

to find (and certify) the spectral gap for $SL(4, \mathbb{Z})$ is at least 1.2999... in just under $2$ minutes time (for comparison this result requires over 5 hours in the old implementation on the same hardware).

To replicate the results of _$\operatorname{Aut}(\textbf{F}5)$ has property (T) You neet to run (on a 4-core CPU)

julia ../AutFN_orbit.jl -N 5 --upper-bound 1.2 --iterations 24000000 --cpus 4

Note that this computation took more than 12 days and required at least 32GB of ram (and possible more).

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 1703.09680

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

git checkout 1703.09680v1

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

Specific version of 1712.07167

You need to run julia-0.6.

Clone https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT and checkout the 1712.07167 branch:

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

In julias REPL execute

Pkg.add("ArgParse")
Pkg.add("Nemo")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/Groups.jl.git")
Pkg.checkout("Groups", "1712.07167")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/GroupRings.jl.git")
Pkg.checkout("GroupRings", "1712.07167")
Pkg.clone("https://git.wmi.amu.edu.pl/kalmar/PropertyT.jl.git")
Pkg.checkout("PropertyT", "1712.07167")
Pkg.checkout("SCS")
Pkg.build("SCS")

This should resolve all the dependencies. Quit julia and place the oSAutF5_r2 folder downloaded from here inside GroupsWithPropertyT folder. To verify the decomposition of $\Delta^2 - \lambda \Delta$ for the group run (if You have a 4-core CPU at Your disposal)

julia AutFN_orbit.jl -N 5 --upper-bound=1.2 --cpus 4

If You want to generate pm and other files on Your own delete everything from the oSAutF5_r2 folder but 1.2 folder and its contents and run the same command again.

Note: You need at least 32GB of RAM and spare 24h of Your CPU.