arXiv:1703.09680v3 [] 9 Oct 2017

Certifying numerical estimates
of spectral gaps
Marek Kaluba* and Piotr W. Nowak†
October 11, 2017

Abstract
We establish a lower bound on the spectral gap of the Laplace operator
on special linear groups using conic optimisation. In particular, this provides
a constructive (but computer assisted) proof that these groups have Kazhdan property (T). Software for such optimisation for other finitely presented
groups is provided.

1 Introduction
Estimation of spectral gaps and Kazhdan constants for finitely presented groups
is a fundamental problem in analytic group theory. In particular, much work was
devoted only to establishing and then improving bounds for SL(n, Z), see [4, 8,
10, 18]. These estimates are analytical in nature, often providing a homogeneous
bound for all n. In this paper we obtain significantly better numerical bounds
for low dimensional special linear groups (n = 3, 4, 5) as well as for special linear
groups over certain finite fields.
It is known that property (T) is equivalent to the positivity of the operator
∆2 − λ∆ in the maximal group C ∗ -algebra, for some positive λ. This, in turn,
is equivalent, by the Positivstellensatz [17], to an approximation of ∆2 − λ∆ by
P
sums-of-(hermitian)-squares, i.e. elements of the form ξ∗i ξ i [13]. Ozawa in [16]
showed that this can be effectively checked, as the decomposition is attainable in
Q[G ], hence in a finite-dimensional subspace of the real group ring R[G ]. Moreover, he proved that the approximation error term can be modified to sum-ofsquares, at the expense of λ.
In [14] Netzer and Thom cast the problem into the language of semidefinite
(numerical) optimisation and, as a proof-of-concept, numerically improved the
existing bound for the spectral gap of ∆ (and thus for the Kazhdan constant) for
SL(3, Z) by three orders of magnitude. To achieve this they provide a constructive
estimation of residuals which inevitably arise in every numerical computation.
Here we improve the algorithm for computing the spectral gap and provide several new lower bounds for κ(SL(n, Z), E (n)) and κ(SL(n, F p ), E (n)), where E (n) is
* Author has been parially supported by the National Science Centre, under grant
2015/19/B/ST1/01458
† This project has received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement no. 677120-INDEX)

1

the set of elementary matrices (i.e. matrices which differ from identity by ±1 on
a single entry off the diagonal). Related results were recently obtained independently by Fujiwara and Kabaya [6].
The paper is organised as follows: in the remaining part of the introduction
we provide the necessary background and notation. In Section 2 we provide a
detailed description of the algorithm, Section 3 is devoted to implementation details, and in the last section we gather the results of numerical experiments.
Acknowledgements. We would like to thank Dawid Kielak and Taka Ozawa
for interesting comments.
Group Laplacian. Let G = 〈 S | R 〉 be a finitely presented group, with finite
generating set S and finite set of relations R . Usually the set S is assumed to
be symmetric, i.e. S −1 = S , where S −1 denotes the set of point-wise inverses of S .
The unnormalized Laplace operator1 ∆S ∈ R[G ], associated to S , is defined as

∆S =

X
1 X
g,
(1 − g)∗ (1 − g) = |S | −
2 g ∈S
g ∈S

where ∗ is the standard involution on R[G ] given by g∗ = g−1 for g ∈ G and a∗ = a
for a ∈ R. Throughout the paper we will drop the subsript S from ∆, whenever
it does not lead to confusion. Spectral properties of ∆S contain a great deal of
information on (G, S ), and thus have been intensely studied.
Kazhdan property (T) and spectral gap. For π : G → B (H ), an orthogonal
representation of G on a (real) Hilbert space H denote by H π = {v ∈ H : π g v =
v for all g ∈ G } the (closed) subspace of π-invariant vectors. We define
(
)
¡ π ¢⊥
κ(G, S, π) = inf sup kπ( g)ξ − ξkH : ξ ∈ H
, kξk = 1 .
g ∈S

The Kazhdan constant κ(G, S ) is defined as the infimum of κ(G, S, π) over all
orthogonal representations π of G . We say that G has Kazhdan property (T) if
and only if there exists a finite generating set S such that κ(G, S ) > 0. Proving
that a group G has property (T), and further estimating the Kazhdan constant of
(G, S ) is usually a difficult task.
Analogously to κ(G, S ) we define λ(G, S, π) as the spectral gap of π(∆S ); i.e.,
its first non-zero eigenvalue, and λ(G, S ) as the infimum of λs over all representations π without non-zero invariant vector. The spectral gap is related to Kazhdan
constant of (G, S ) by the inequality (see [1, Remark 5.4.7])
s

2λ(G, S )
≤ κ(G, S ).
|S |

The following characterization of property (T) is instrumental in our further
considerations.
1 Note that some authors ( [1, 16]) use normalised Laplace operator, (which differs from ∆ by 1
S
|S |
normalisation constant), while others ( [6, 14]), use ∆S as defined here.

2

Theorem 1 (Ozawa, [16]). A discrete group G = 〈S | ... 〉 has Kazhdan’s property
(T) if and only if there exists constant λ > 0 and ξ1 ,... , ξk ∈ R[G ] such that

∆2S − λ∆S =

k
X

i =1

ξ∗i ξ i .

(1)

It is clear that λ in the theorem is a lower bound for λ(G, S ), and in fact the
maximal such λ is equal to λ(G, S ), although we will not use the equality.
The possibility of obtaining certified (i.e. mathematically correct) estimate on
λ by numeric optimisation is a consequence of a lemma which controls residuals
bound to occur in the computer-based calculations. Let ω[G ] denote the kernel of
the augmentation homomorphisms ε : R[G ] → R, and for V < R[G ] let V h denote
the subspace of ∗ -invariant elements of V .
Lemma 2 (Ozawa). Suppose that r ∈ ω[G ]h . Then r + R ∆ ≥ 0, i.e. admits a sumof-squares decomposition for R large enough.
Netzer and Thom ( [14, Lemma 2.1]) gave an explicit bound on R in terms of
wl S , the word length in S :
R ≤ 2m krk1 ,
where

m = m(r, S ) = max 2wl S ( g) − χ(S ),
g ∈supp( r )

and χ(S ) = 1 if S contains elements of order 2, or χ(S ) = 2 otherwise.

2 The algorithm.
We provide only a bare minimum in the paragraphs below, as the theory and
the approach has been described in [14]. For general theory of convex (conic)
optimisation, we refer to excellent book [3, Chapter 4], or the survey [21]. For
the thorough discussion of the method explained below we suggest the very well
written survey [12].
Sum of squares and semidefinite programming Let x be a fixed, ordered
basis of a finite dimensional subspace V ⊂ R[G ]. A sum-of-squares decomposition
in V (as in (1)) is equivalent to the existence of semi-positive definite matrix (the
so called Gramm matrix) P satisfying

∆2 − λ∆ = x∗ P xT .
Indeed, by semi-positive difiniteness of P we can find a square matrix Q such
that P = QQ T . Matrix Q = [ q1 | ... | q k ] can be seen as change-of-basis operator, as
setting x q i = ξ i we obtain
x∗ P xT = (xQ )∗ (xQ )T =

k
X

i =1

ξ∗i ξ i .

Semi-definite optimisation is a subclass of conic optimisation, where (in the
primal form) the objective function is a linear functional minimised over a spectrahedron (i.e. the intersection of an affine space and the cone of semi-positive

3

definite matrices). The optimisation problem for our sum-of-squares decomposition can be described as a semidefinite optimisation problem (SDP)
minimise
subject to

−λ

x P xT = (∆2 − λ∆)
∗

λ≥0

(2)

P º 0,
where P º 0 denotes semi-positive definetness. Note that, in this formulation,
entries of P = ( p i j ) and λ are optimised variables, while the equality constraint
defines a set of linear constraints involving p i j and λ. Providing just one solution
(λ, P ) of the problem certifies property (T) for the group G (if λ > 0), however it
is known that deciding feasibility (non-emptiness of the set of solutions) of an
SDP is an NP-co-NP-hard problem [20, Theorem 2.30]. Nonetheless, there are
specialised languages (algebraic modeling languages) to specify SDP problems
and softwares (solvers) which obtain provably approximate values λ0 and P0 with
surprising efficiency.
The two key problems here are:
• the choice of subspace V , and
• turning the approximate solution (λ0 , P0 ) into exact one, i.e. dealing with
the residual of the numerical solution

r = ∆2 − λ0 ∆ − x∗ P0 x ≈ 0.
The choice of V . For classical sum-of-squares problem, in the (Laurant) polynomial algebra, the choice of V is straightforward. Given a polynomial f of (absolute) degree 2d in k variables, it is enough to take V spanned by all monomials
of (absolute) degree not exceeding d . However, in the case of optimisation in the
group algebra R[G ] it is not clear what is the optimal V , as the set of relations R
plays an important role in this choice.
Since ∆2 is supported on B2 ( e, S ) it seems natural to include 〈S 〉 in V . Feasibility of the problem for V = 〈B1 ( e, S )〉 is a decomposition as sum-of-squares of
elements of length 2 (and corresponds to the 1-st filtration in Lasserre’s hierarchy
of polynomial optimisation [11]). Taking V = 〈B2 ( e, S )〉 or V = 〈B3 ( e, S )〉 (length
≤ 4 or ≤ 6) may give additional degrees of freedom in the optimisation, and thus
lead to better (in terms of λ) solution to problem (2).
Indeed, in most cases the choice of larger V proved to be beneficial: see Tables 1 and 2. However, to specify constraints on the coefficients of P for V =
〈B d ( e, S )〉, we need the full multiplication table on B d ( e, S ), which requires generation of B2 d ( e, S ). Due to the growth of G , the dimension of V grows exponentially with d , thwarting any attempts of numerical solution, except for small
groups. Moreover, the error term grows exponentially with d as well obstructing bound certification, even if the numerical optimisation was successful. In
the last section we report our experiments for V = 〈B d ( e, S )〉 with d ≤ 5, i.e. the
decomposition, if obtained, is a sum of squares of elements of length at most 5.
We note also a basic fact for SL(2, p): for every d there exists a prime p such
that no decomposition
X
∆2 − λ∆ = ξ∗i ξ i
4

is attainable for ξ i ∈ 〈B d ( e, S )〉. In particular, for p > 7 it is not possible to obtain a positive estimate on λ(SL(2, p), E (2)) by a sum-of-squares decomposition of
∆2 − λ∆ over 〈B2 ( e, S )〉. Indeed, for a fixed d , the ball B2 d ( e, S ) is mapped isometrically by the modular projection SL(2, Z) → SL(2, p) for p large enough. Thus a
decomposition of ∆2 − λ∆ obtained for SL(2, p) would lift to a similar decomposition for SL(2, Z), which is a contradiction. This (partially) explains why a positive
estimate for SL(2, 7) over 〈B2 ( e, S )〉 is not obtainable by numerical optimisation
– the balls of radius 2 in SL(2, Z) and SL(2, 7) are very similar (they differ by
only 4 elements). On the other hand, the optimisation finishes successfully over
〈B3 ( e, S )〉 and 〈B4 ( e, S )〉 (which is all of R[SL(2, 7)]).
If G has property (T) and V = R[G ], then problem (2) has solutions for all
0 ≤ λ < λ(G, S ) and is thus strictly feasible. By Slater’s condition this implies
no duality gap and therefore the uniqueness of the optimum value (see [3, Chapter 5]). On the other hand, the spectral gap λ(G, S ) can be expressed as
X
©
ª
λ(G, S ) = sup λ : ∆2 − λ∆ = ξ∗i ξ i for some ξ i ∈ R[G ] ,
so in the case of finite group G the supremum is clearly attained on V . For a few
first primes p, we can extend V to the whole of R[SL(2, p)] and therefore obtain a
solution which should be relatively close to the actual λ(SL(2, p), E (2)).

The residual. Although our treatment of the residual is similar to that of [14],
we provide a short description as we will modify and explain some of the details
in the next section.
In numerical optimisation we are always left with residuals, i.e. for the problem of the decomposition of ∆2 − λ∆ into sum-of-squares, a numerical solution
(λ0 , P0 ) is a floating-point approximation

∆2 − λ0 ∆ − x∗ P0 x = r,

krk1 ≤ ε.

To turn the numerical solution to problem (2) into exact one, i.e. provide a certified bound on λ, we have to modify the solution as follows.
p
1. Compute Q = Re( P0 ): the real part of square root of P ;

2. Approximate Q by Q Q : project the floating-point matrix Q to a close, rationalvalued one;
ω
3. Correct Q Q to Q Q
: each column q i of Q Q is projected to qωi which represents
an element of the augmentation ideal, i.e. x qωi ∈ ω[G ];

4. Compute the decomposition

P

³ ´T
ω
ω
ξ∗i ξ i = x∗ Q Q
QQ
xT and the residual:

r = ∆2 − λ0 ∆ −

X

ξ∗i ξ i .

5. Obtain certified bound for the spectral gap:
X
X
∆2 − λ0 ∆ = ξ∗i ξ i + r ≥ ξ∗i ξ i + 2m(S ) krk1 ∆,
hence

´
³
X
∆2 − λ − 2m(S ) krk1 ∆ ≥ ξ∗i ξ i ≥ 0,

which certifies λ(G, S ) ≥ λ0 − 2m(S ) krk1 .
5

3 Implementation details.
It is clear that the difference between numerical λ0 and the certified lower bound
for λ(G, S ) grows with the approximation error. Thus, it may be favourable not
to simply maximize λ, but rather turn problem (2) into multi-objective optimisation with minimisation of krk1 as the second objective. We did not pursue this
direction, as the objective function
° ¡ ω ¢°
°
P −→ λ − 2m(S ) °r Q Q
1

outlined above is neither linear, nor differentiable, nor convex, making it very
hard - if not impossible - to execute efficiently an optimisation problem. We do,
however, introduce a few changes to the problem which will exploit the strong
dependence of the certified bound on krk1 . These changes lead to significant
increase in accuracy (hence better certified bound) while at the same time (surprisingly) decrease the time required to obtain the solution.

Problem modification. Several types of solvers are available for semidefinite
optimisation problems. Interior-point solvers are usually very accurate and converge quickly (in terms of iterations) on small to middle sized problems, but
require substanital computing resources. We used first-order solver (based on
alternating direction method of multipliers – ADMM) which, while achieving
moderate-to-poor accuracy [9], obtains an approximate solution (λ0 , P0 ) of problem (2) relatively quickly. Moreover, compared to interior-point solvers, firstorder solvers are memory efficient, which allows us to tackle much larger problems. At first glance, accuracy provided by an ADMM solver may seem counterproductive to our purposes. However, after obtaining an approximate solution,
we modify the original problem (2) by constraining additionally both λ and P =
( p i j ) and run the solver again on following problem (with increased requested
accuracy).
minimise
−λ
subject to

x∗ P xT = (∆2 − λ∆)
λ≥0
λ ≤ (1 − δ)λ0

(3)

P º0
X

p i j = 0.

i, j

Constraining λ from above forces the solver to increase accuracy of P rather
than over-estimating λ (δ is a chosen small positive number). The additional
constraint on the sum of elements in P minimises the projection distance introP
duced in step 3: q i x ∈ ω[G ] implies i j p i j = 0. Note that although the constraint
was implicit in the original problem, making it explicit to the solver boosts the
accuracy of the (constrained) solution even further.
Validated Numerics. Netzer and Thom [14] (as well as Fujiwara and Kabaya
[6]) performed the whole validation step in rational (i.e. exact) arithmetic. However, calculations with rational numbers are expensive both in time and space:
additions require performing divisions and cause numerators and denominators
grow at an exponential rate. Especially step 4 is problematic as coordinates of
6

r get close to 0, but the space required to store r grows exponentially with the
dimension of V . Indeed, for large S , these steps take longer than the actual optimisation phase. While steps 2 and 3 must necessarily be performed in exact
rational arithmetic to apply Lemma 2 (or its quantitative version), there is no
need to continue calculations with rationals afterwards.
After making suitable adjustments of Q in rational arithmetic, we turn in step
4 to interval arithmetic [19]. This technique of computation does not produce as
result an exact number, but a real interval together with mathematical guarantee
that the exact result belongs to the interval. All calculations are carried out on
real intervals, and these intervals are propagated through every function. Such
computations are much easier for computer to perform than rational arithmetic,
as they consist of floating-point operations and directed rounding. As the the
aim of the procedure is to compute the lower bound for λ(G, S ), the left end of the
resulting interval can be used as such a bound. While interval arithmetic is inherently less precise than rational arithmetic, we can afford the loss of precision
in the step due to high accuracy of the solver.

4 Computed bounds
We report on the obtained numerical bounds and computation metrics in Tables 1
and 2. The dominating part of the computation is either the pre-solve phase or
the optimisation of the constrained SDP (3) (which is parallelisable), thus, in principle, bounds for larger groups could be obtained on a cluster computer. In the
pre-solve phase we stop the solver after the primal/dual objective has stabilised
(usually this happened after either accuracy of 10−5 , or 20000 iterations have
been reached). In some cases of smaller groups it is possible to obtain high accuracy even in the pre-solve phase. The choice of δ was based on the solvers rate
of convergence in the pre-solve phase in an ad-hoc manner. The certified bound
is not stable with respect to δ: e.g. for problem of SL(3, Z) with d = 2, changing
the upper bound on λ to 0.28 resulted in solvers stall and overall lower certified
bound due to larger norm of the residual. This may serve as an indicator that λ0
exceeds the maximal λ attainable on V .
An interesting case present numerical bounds for group SL(2, 19) in Table 1.
For d = 5 we obtain certified lower bound on the spectral gap of 0.245.... Even the
increase of d to 7, does not yield a better numerical estimate (the certified bound
becomes worse, as the SDP problem grows rapidy and the cost of the residual is
24 -times larger compared to d = 5). Note that products of elements in B14 ( e, E (2))
saturate the whole group SL(2, 19), hence no better decomposition of ∆2 − λ∆ into
sum of squares can be found by semidefinite programming.
We tried to employ our software to SOut(F4 ) (generated by transvections) for
d = 2: this resulted in a relatively large optimisation problem with n = 1959211
variables and m = 5937302 constraints. We compared the solvers behaviour to
the problems of SL(5, Z) (n = 1256642, m = 1756344) and SOut(F3 ) (n = 231362, m =
131300) which does not have property (T). While the solver on SL(5, Z) achieved
convergence (in 15 hours), on SOut(F3 ) the solver stalled, with accuracy oscilating around 5 · 10−5±1 and ever decreasing optimisation variable. Note that this
is different behaviour from the one observed for SL(3, Z) and λ0 = 0.28, where
the solver was unable to increase the accuracy, while maintaining the value of λ.
The solver on problem for SOut(F4 ) exhibited a similar behaviour to SOut(F3 )

7

(stall, even with very small λ0 ) for SOut(F3 ), i.e. we were not able to get certified positive λ. This suggests that ∆2 − λ∆ is not decomposable (for any λ) into
sum of squares of elements in 〈B2 ( e, S )〉. We consider this a (heuristic) argument
supporting a common belief that Aut(F4 ) does not have property (T).
Software details. The source code used to perform computations is licensed
under MIT license and accessible at https://git.wmi.amu.edu.pl/kalmar/.
The computation is divided into three steps.
• Computing basis of V = 〈B d ( e, S )〉 and the multiplication table;
• Defining and solving SDP problems (2) and (3);
• Estimating the certified bound on λ(G, S ).
These steps are mostly independent of each other, and it is possible to e.g. supply
basis and the multiplication table computed in other programs (e.g. GAP [7]) and
plug it into SDP routines of ours. A slight enhancement to the implementation
would be to provide (the primal and the dual) solutions of the pre-solver as a
warm-start for the constrained problem. In case of large problems (e.g SL(5, Z),
or SL(5, p)) this may decrease the time needed to solve the constrained SDP and
thus obtain a better bound in the same time-frame.
To credit the developers we provide a few details of the softwares used. The
implementation is written in J ULIA [2] programming language focused on scientific computations. The SDP solver employed is SCS [15] through the J U MP
modelling language [5].

References
[1] M. B. Bekka, P. de. La Harpe, and A. Valette. Kazhdan’s property (T). Cambridge University Press, 2008.
[2] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: A Fresh
Approach to Numerical Computing. SIAM Review, 59(1):65–98, jan 2017.
[3] S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[4] M. Burger. Kazhdan constants for SL(3, Z). Journal für die reine und angewandte Mathematik, 413:36–67, 1991.
[5] I. Dunning, J. Huchette, and M. Lubin. JuMP: A Modeling Language for
Mathematical Optimization. aug 2015, 1508.01982.
[6] K. Fujiwara and Y. Kabaya. Computing Kazhdan constants by semidefinite
programming. arXiv preprint, mar 2017, 1703.04555.
[7] The GAP Group. GAP – Groups, Algorithms, and Programming, Version
4.8.6, 2016.
[8] U. Hadad. Uniform Kazhdan constant for some families of linear groups.
Journal of Algebra, 318(2):607–618, dec 2007.

8

[9] B. He and X. Yuan.
On the O(1/n) Convergence Rate of the Douglas–Rachford Alternating Direction Method. SIAM Journal on Numerical
Analysis, 50(2):700–709, jan 2012.
[10] M. Kassabov. Kazhdan Constants for SL n (Z). International Journal of Algebra and Computation, 15(05n06):971–995, 2005.
[11] J. B. Lasserre. Global Optimization with Polynomials and the Problem of
Moments. SIAM Journal on Optimization, 11(3):796–817, jan 2001.
[12] T. Netzer. Real Algebraic Geometry and its Applications. arXiv preprint, jun
2016, 1606.07284.
[13] T. Netzer and A. Thom. Real closed separation theorems and applications to
group algebras. Pacific Journal of Mathematics, 263(2):435–452, may 2013.
[14] T. Netzer and A. Thom. Kazhdan’s Property (T) via Semidefinite Optimization. Experimental Mathematics, 24(3):371–374, jul 2015.
[15] B. O’Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic Optimization via
Operator Splitting and Homogeneous Self-Dual Embedding. Journal of Optimization Theory and Applications, 169(3):1042–1068, jun 2016.
[16] N. Ozawa. Noncommutative Real Algebraic Geometry of Kazhdan’s Property (T). Journal of the Institute of Mathematics of Jussieu, 15(01):85–90,
jan 2016.
[17] K. Schmüdgen. Noncommutative Real Algebraic Geometry Some Basic Concepts and First Ideas. In Emerging Applications of Algebraic Geometry,
pages 325–350. 2009.
[18] Y. Shalom. Bounded generation and Kazhdan’s property (T ). Publications
Mathématiques de l’IHÉS, 90:145–168, 1999.
[19] W. Tucker. Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press, Princeton, NJ, USA, 2011.
[20] L. Tuncel. Polyhedral and semidefinite programming methods in combinatorial optimization. American Mathematical Society, 2010.
[21] L. Vandenberghe and S. Boyd. Semidefinite Programming. SIAM Review,
38(1):49–95, mar 1996.

9

Size

d

|B 2 d |

n

m

tpre [s]

SL(2, 3)

24

2

24

92

208

1·10−1

SL(2, 5)

120

2

91

154

340

3

120

947

2,014

2

111

154

419

3

326

1,129

4

336

3
4

SL(2, 7)

SL(2, 11)

SL(2, 13)

336

1,320

2,184

10
SL(2, 17)

SL(2, 19)

4,896

6,840

λ0

(1 − δ)λ0

tSDP [s]

prec

krk1 <

κn

κ

1.26794

1.26790

3.5·101

1·10−13

8.0·10−13

0.7961

0.79622

5.4·101

0.13672

0.13000

2.9·102

4·10−8

4.8·10−4

0.2580

0.25962

1.9·100

0.76393

0.76393

1·10−9

1.6·10−8

0.6145

0.61803

2,584

2.4·100

0.58578

0.58578

3·10−9

7.5·10−8

0.5387

0.54119

6,217

12,770

2.1·101

0.58578

0.58578

2·10−9

3.8·10−8

0.54119

532

1,129

2,790

1,234

6,671

14,576

6.5·101

0.38196

0.38196

6·10−9

1.9·10−7

0.43701

3

0.38196

0.38196

5·10

−9

−7

0.43698

2·10−8

1.4·10−7

0.40302

6·10−9

3.4·10−7

0.40297

5

1,320

34,192

69,704

1.8·10

3

556

1,129

2,814

4

1,622

6,671

14,964

1.8·102

0.32486

0.32486

5

2,184

34,717

71,618

4.3·103

0.32487

0.32486

4

2,268

6,671

15,610

5

4,690

34,717

74,124

9.1·102

0.29072

0.29072

8·10−9

3.9·10−7

0.38120

3

0.29072

0.29072

−9

−7

0.38116

0.10781

0.10700

1·10−9

4.2·10−9

0.23130

−9

−7

0.35022

4.2·102

2.1·10

6

4,869

154,847

314,590

6.8·10

4

2,144

6,671

15,487

3.2·102
2

0.24539

0.24539

0.24539

0.24539

7.5·103

7·10−9

5.5·10−7

0.34988

0.24539

2

−7

−6

0.34183

5

5,428

34,717

74,863

6.9·10

6

6,830

154,847

316,524

1.2·104

1,257,885

4

7

6,840

625,522

2.4·10

0.24539

5·10
1.5·102

8·10

3.9·10

1·10

1.4·10

3.3·10

2.9·10

Table 1: Computation metrics for SL(2, p): the size of generating set S is 4; |B2 d | = |B2 d ( e, S )| is the size of support of x∗ P xT ; n and m are the
number of variables and constraints, respectively, in SDP problems; tpre and tSDP are the time spent by solver in the pre-solve phase and in the
optimisation of the constrained problem (in seconds); in case the unconstrained solver achieved decent precision in the pre-solve optimisation
we set δ = 0 and tSDP = tpre ; the times reported are for Intel Sandy-Bridge 4-core desktop processor; prec is the numerical precision obtained
by the solver; blank lines are left when solver did not achieve convergence; krk1 is the upper bound on the ℓ1 -norm of the residual; κn is the
numerical bound obtained in [6]; κ is a down-rounded numerical approximation of our certified bound – due to numerical accuracy of the solver
we certify λ > (1 − δ)λ0 − prec − 2m(S ) krk1 ; Previously known (analytical) lower bound: 0.0013444 by [10]; the upper bound for κ(SL(2, p), E (n))
derived by Żuk ( [18]) is 1.

SL(3, 2)

SL(3, 3)

SL(3, 5)

SL(3, 7)

|S |

Size

d

|B 2 d |

n

m

tpre [s]

6

168

2

142

497

1,136

8·10−1

3

168

10,154

20,476

3.7·101
1

2.70849

2.70800

2.70849

2.70849

12

12

12

5,616

372,000

5,630,688

λ0

(1 − δ)λ0

tSDP [s]

prec

krk1 <

1.5858

1.58570

1.1·102

3·10−11

2.3·10−9

0.72703

1.58578

1.58578

1·10−9

3.0·10−8

0.72704

1.1·10

3

2

2,278

5,996

14,272

1.3·10

3

5,610

177,311

360,232

5.8·102
1

1.50201

1.49800

4·10

1.76749

1.76740

4.5·102
2

1·10−9
2

3

100,398

379,757

859,912

5.4·103
1

0.74233

0.73850

8.2·10

1.47272

1.47100

3.2·104

2·10−9

1.0·10−7

0.49514

4

−9

−7

0.35119

2

5,443

7,382

20,208

9.4·10

3

145,812

390,287

926,386

7.8·103
4

0.75341

0.74000

7.6·10

0.28174

0.27990

2.1·103
5

390,287

934,852

2·10

SL(3, Z)

12

2

5,455

7,382

20,220

4.2·102

390,287

935,021

2.8·10

4

0.54197

0.54050

9.2·10

5,996

14,702

2.4·102

2.22794

2.22700

4.3·102

83,846

216,472

2·10

3

4.30793

4.30000

7·10

3

93,962

261,826

2·103

2.80353

2.80000

2.3·104

3

1.72087

1.72000

4.3·10

4

1.31686

1.31500

1.9·104
4

3
11

SL(4, 5)

0.67187

9.1·10

2

154,446

3·10

2·10−7
1·10

1·10

−11

1·10−12

0.4981

3.5·10−6
4.7·10

3.8·10

−9

8.6·10−10

0.49967
0.54273

0.3508

0.2155

0.35083

0.21599

−7

0.30014

1·10−11

3.2·10−9

0.60923

−11

−8

0.5974

0.59861

3·10−11

3.1·10−8

0.4812

0.48305

−11

−8

0.3284

0.37859

3·10−11

5.2·10−8

0.3285

0.33103

−12

−9

0.54046

1·10

3·10

−9

1.2·10

−8

19,884

154,278

24

2.0·10−7

0.67181

7,382

3

SL(4, 3)

0.6716

5,119

12

12

−11

3.3·10

−9

κ

2

SL(3, 11)

SL(4, 2)

1·10

−11

κn

5.2·10

3.4·10

SL(4, 7)

93,962

263,098

2·10

SL(4, Z)

93,962

263,122

1.8·103
3

2.92148

2.92100

1.5·10

6.00595

6.00000

1.8·105

1·10−9

2.3·10−5

0.54772

5

−8

−4

0.46043

SL(5, 2)

20

39,622

101,776

2.1·10

SL(5, 3)

40

584,822

1,556,596

3.1·104
4

4.24441

4.24000

4.2·10

3·10

3·10

2.1·10

5.3·10

SL(5, 5)

628,882

1,754,106

3·10

SL(5, 7)

628,882

1,757,426

2.4·104

3.04647

3.04000

7.2·105

2·10−8

8.8·10−5

0.38987

SL(5, Z)

628,882

1,757,466

2.2·104

2.6877

2.65000

5.5·104

2·10−8

2.0·10−4

0.36400

2·10

1.4·10

Table 2: Computation metrics: For description see Table 1. The analytical lower bounds for κ(SL(k, •), E (n)) of [10] are: 0.0013268, 0.0013123 and 0.0012999
(for SL(k, p)) and 0.0010721, 0.0010593 and 0.0010483 (for SL(k, Z)) for k = 3, 4, 5, respectively; The upper bounds derived by Żuk ( [18]) are 0.81650, 0.70711
and 0.63246 for k = 3, 4, 5, respectively.

