Aut(F5 ) has property (T )

arXiv:1712.07167v1 [] 19 Dec 2017

Marek Kaluba1, Piotr W. Nowak2 , and Narutaka Ozawa3
1 Adam Mickiewicz University, Poznań, Poland
1,2 Institute of Mathematics of the Polish Academy of Sciences, Warsaw, Poland
3 Research Institute for Mathematical Sciences, Kyoto, Japan

December 21, 2017
Abstract
We give a constructive, computer-assisted proof that Aut(F5 ), the automorphism group of the free group on 5 generators, has Kazhdan’s property (T ).

Kazhdan’s property (T ) is a powerful rigidity property of groups with many
applications. Few groups are known to have property (T ). The main classes
known to satisfy property (T ) are lattices in higher rank Lie groups, whose algebraic structure allows to deduce powerful rigidity properties such as property
(T ); groups acting on complexes whose links satisfy a certain spectral condition,
including groups acting on buildings; and certain hyperbolic groups, such as
lattices in Sp(n, 1) and some random hyperbolic groups in the Gromov density
model.
The main purpose of this article is to prove property (T ) for a new group
and give an estimate of its Kazhdan constant. Let SAut(F5 ) denote the special
automorphism group of the free group on 5 generators, with S being its standard
generating set consisting of transvections.
Theorem 1. The group SAut(F5 ) has property (T ) with Kazhdan constant
κ(SAut(F5 ), S ) > 0.173.

Part of the proof consists of providing explicit ξ i and λ > 0 such that

∆2 − λ∆ ≈

n
X

i =1

ξ∗i ξ i ,

up to a small, controlled error. The ξ i ’s are obtained via semidefinite optimization.
We describe in detail the theoretical aspects, the algorithm used to produce the
solution, as well as the certification that allows to obtain, out of this approximate
solution, a mathematically correct conclusion about the existence of an exact solution. This method of proving property (T ) was forseen by the third author in [27]
and used effectively by Netzer and Thom [24], Fujiwara and Kabaya [12] and the
first two authors [17] to reprove property (T ) and give new estimates for Kazhdan
constants for the groups SLn (Z), n = 3, 4, 5.
As an immediate consequence of Theorem 1 we obtain
Corollary 2. The groups Aut(F5 ) and Out(F5 ) have property (T ).
1

Questions whether any of the groups above has property (T ) is discussed in
many places, e.g. [6, Question 7], [20], [5, page 345], [4, page 4], [9, page 63], to
name a few. Applications to the product replacement algorithm were discussed
in [20].
The group Aut(Fn ) is known not to have property (T ) for n = 2 and n = 3
see [22] as well as [4, 15]. It was suspected nevertheless that Aut(Fn ) might have
property (T ) for n sufficiently large, with all n ≥ 4 being open. In the case of
n = 4 our approach – both the one in [17] and the symmetrized version presented
below – did not give a positive answer, in the sense that the solver was not able to
reach a solution on the ball of radius 2. There are three possible reasons for this
behavior. One possibility is that Aut(F4 ) does not have property (T ) (as somehow
anticipated by [4]). Another is that Aut(F4 ) has property (T ), however no ξ i as
above, supported on the ball of radius 2 exist. Search for ξ i s supported on the
ball of radius 3 is already too expensive (in memory and computation time ) to
be handled by our implementation. Finally, the third possibility is that again
Aut(F4 ) has property (T ), but the (computable) spectral gap is so small, that the
certification process does not yield a positive answer.
It is an interesting question whether the fact that Aut(F5 ) has property (T ) is
sufficient to deduce property (T ) for Aut(Fn ) for all n ≥ 5, similarly as in the case
of lattices in higher rank Lie groups. In Section 6 we show that Aut(Fn+1 ) has
a large subgroup with property (T ), if Aut(Fn ) has (T ). However, all attempts to
prove property (T ) for Aut(Fn ), n ≥ 6 using property (T ) for Aut(F5 ) seem to break
down at the currently open Question 12 in [6].
It was proved in [14] that for n ≥ 3 the group Out(Fn ) is residually finite
alternating and it is a consequence of Theorem 1 that the corresponding family
of alternating quotients of Out(F5 ) can be turned into a family of expanders. This
was proved earlier in greater generality by Kassabov [18], however in our case the
generating set is explicit and the same in all of these finite groups, in the sense
that it is the image of the generating set of Out(F5 ). In particular, this gives an
alternative and independent of [18] negative answer to question [19, Question
10.3.2].
Acknowledgements MK is partially supported by the National Science Centre grant 2015/19/B/ST1/01458.
NO is partially supported by JSPS KAKENHI, Grant Number 17K05277 and
15H05739.
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).
This research was supported in part by PL-Grid Infrastructure, grant ID:
propertyt2.

Contents
1 Property (T ), real algebraic geometry and semidefinite program3
ming
2 Problem symmetrization
2.1 Invariant SDP problems . . . . . . . . . . . . . . . . . . . . . . . . . .

2

6
6

2.2 Orbit symmetrization . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Block-diagonalization via the Wedderburn decomposition . . . . . .
2.4 Symmetrization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7
8
9

3 The group Aut(Fn )
10
3.1 Presentation for Aut(Fn ) . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Implementation of Aut(Fn ) . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 The symmetrizing group Σ . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Description of the algorithm
4.1 Multiplication table on E .
4.2 Symmetrization . . . . . . .
4.3 Certification . . . . . . . . .
4.4 Software details . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

12
13
13
13
14

5 Proof of Theorem 1

15

6 Extrapolation of property (T )

16

7 SL6 (Z) and SL4 (Z〈 X 〉)

17

8 Final remarks

18

1 Property (T ), real algebraic geometry and semidefinite programming
Recall that a group G generated by a finite set S has property (T ) if there exists
κ > 0 such that
sup kπs v − vk ≥ κkvk,
s ∈S

for every unitary representation π of G with no non-zero invariant vectors. The
infimum of κ as above over all such κ’s that satisfy the above is called the Kazhdan constant of G with respect to the generating set S and is denoted κ(G, S ).
For an excellent overview of property (T ), its many descriptions and applications
see [2].
Let G be a discrete group generated by a finite set S = S −1 . Given a ring
R we consider the associated group ring RG , that consists of finitely supported
P
functions ξ : G → R . We will use the notation ξ = g ∈G ξ g g, where ξ g ∈ R for each
g ∈ G , to denote the elements of the group ring RG . The convolution in RG is
P
then defined as (ξη) g = h∈G ξh η h−1 g . Recall that the augmentation ideal IG is
P
the kernel of the augmentation map ω : RG → R , ξ 7→ g ∈G ξ g . The group ring
RG is equipped with an involution ∗ : RG → RG , induced by the inversion map
on G and defined explicitly as (ξ∗ ) g = ξ g −1 for any ξ ∈ RG .
The unnormalized Laplacian is an element of the real group ring RG defined
as
X
∆ = |S | −
s.
s ∈S

In [27] the following characterization of property (T ) for discrete groups was
proved.

3

Theorem 3 ( [27]). A finitely generated group G has Kazhdan’s property (T ) if
and only if there exist a positive number λ > 0 and a finite family {ξ1 ,... , ξn } of
elements of the real group ring RG such that

∆2 − λ∆ =

n
X

i =1

ξ∗i ξ i .

(1)

The characterization above can be used to prove property (T ) for a particular
group G by providing an explicit solution of the equation (1). In particular, the
fact that the right hand side is a finite sum of (hermitian) squares of finitely supported functions allows to try to obtain the ξ i ’s using semidefinite programing.
Let E ⊆ G be a finite subset. Although some of the following considerations
are true for arbitrary E , in this article we always use E = S ∪ S 2 = B2 ( e, S ) (or E =
B3 ( e, S )) in practice. Fix x, an ordered basis of the finite dimensional subspace
〈E 〉R ⊂ RG . Then (1) has a solution in 〈E 〉R ⊂ RG if and only if there exists a
semi-positive definite matrix P such that

∆2 − λ∆ = x∗ P xT .
Indeed, by positive semidefiniteness P can be written as P = QQ T and then
X
x∗ P xT = (xQ )∗ (xQ )T = ξ∗i ξ i ,

where ξ i = x q i for q i the i -th column of Q . In what follows we will drop the
distinction and use ξ i for both a column of a matrix and the corresponding group
algebra element without mentioning the basis x.
Let ME denote the set of real matrices indexed by E . For t ∈ G define a matrix
δ t ∈ ME by setting
(
1 if x−1 y = t
(δ t ) x,y =
0 otherwise.
Equivalently, this is the element t ∈ G viewed inside RG and restricted to E . For
matrices A, B ∈ ME define
X
〈 A, B〉 =
A x,y B x,y = tr( A T B),
where tr( A ) =

P

x,y∈E

x∈E

A x,x is the standard trace on ME . Then
X
〈δ t , P 〉 =
P x,y ,
x−1 y= t

and for every t ∈ E −1 E the value (∆2 − λ∆) t at t can be expressed as
(∆2 − λ∆) t = 〈δ t , P 〉.
This reduces the problem of existence of a solution to equation (1) to the following semidefinite optimization problem in standard form (we use P º 0 to denote
positive semidefiniteness of P ):
minimize
subject to

−λ

P ∈ ME ,

(OP)

P º 0,

〈δ t , P 〉 = (∆2 − λ∆) t

4

for all t ∈ E −1 E.

There are solvers specialized in solving such problems numerically. Once a
solution (P, λ0 ) is obtained numerically (up to specified precision), the next step
is to certify its correctness. This is of utmost importance, as the numerical solution by itself does not provide mathematical certainty that (1) indeed has a
solution in RG . The solution (P, λ0 ) gives only ∆2 − λ0 ∆ ≈ xP xT , an approximate
equality. E.g. the “positive semidefinite” matrix P returned by the solver may
have negative eigenvalues which are very close to 0 (i.e. up to the requested
precision). Moreover, even though some solvers claim to certify the solution, it
is done in floating point arithmetic, which provides no mathematical certainty,
see [25]. Our certification process turns the approximate solution into a proof of
the existence of an exact solution, at the cost of decreasing λ0 .
The process consists of finding (the real part of) square root Q of P (i.e. QQ T ≈
P ), and projecting the obtained matrix Q onto the augmentation ideal, simply by
subtracting the mean value of the i -th column of Q from each entry in that column. This procedure, e.g. performed in rational (multiprecision) arithmetic, provides an explicit matrix Q , whose columns are now elements of the augmentation
ideal. In our case this is done in interval arithmetic as described
later.
³ in´detail
T
P ∗
∗
This process introduces additional error into each element of x Q xQ = i ξ i ξ i ,
which in general depends on the accuracy obtained by the chosen numerical
solver. However (and most importantly) after the projection, Lemma 4 below
P
allows to estimate r = ∆2 − λ0 ∆ − i ξ∗i ξ i , the remainder of the solution. Note
that r gathers both the inaccuracy of the solver and the error introduced by the
projection.
The following lemma allows to estimate the magnitude of errors involved in
our computations and makes certification possible. For more thorough treatment
of order units see [27], as well as [16, 28] for a more general context. For ξ ∈ RG
P
let kξk1 = g ∈G |ξ g | denote the norm of ξ in ℓ1 (G ).
Lemma 4 ( [27], [24]). ∆ is an order unit in IG , the augmentation ideal, i.e. for
all self-adjoint elements r ∈ IG and for all sufficiently large R ≥ 0 we have

r + R∆ ≥ 0

(2)

that is, r + R ∆ allows a sum-of-squares decomposition.
Moreover, if r is supported on ball of radius m in the word-length metric on G
induced by S then
R ≤ 2m−1 krk1 .
(If S contains no involution, then R ≤ 2m−2 krk1 suffices.)
This allows to conclude that r + ε∆ ≥ 0, for an appropriately chosen ε > 0 and
thus
X
∆2 − (λ0 − ε)∆ = ξ∗i ξ i + r + ε∆ ≥ 0.
i

When ε can be chosen sufficiently small in relation to λ0 (so that λ0 − ε > 0), we
can conclude that (1) indeed has a solution in RG .
Complexity of the problem
The size of the set E translates directly to the computational complexity of the
optimization problem (OP): while each element ξ i is (by its definition) supported

5

on E , the equality (1) defines |E −1 E | linear constraints and |E |2 variables in one
semidefinite block. It seems to be an interesting problem to understand the influence of the choice of the set E on the obtained bound λ0 and numerical properties
of the problem.
The problem (OP) has been solved numerically in several cases in [12, 17, 24]
yielding new estimates for λ. The computations were successful for E = B2 ( e, S )
e.g. for the group SL n (Z) with n = 3, 4, 5. Finding a numerical solution of the
problem on a computer may not be feasible if the size of the set E is too large,
and in fact this is the case for the group SL n (Z), n ≥ 6, or the groups SAut(Fn )
when n ≥ 4. For instance, the case of SAut(F5 ) results in 21 538 881 variables
and 11 154 301 constraints, making it a prohibitively large problem. In order
to remedy this and to be able to solve the optimization problem (OP) e.g. for
SAut(F5 ), we will use symmetries of the set E to reduce the problems size.

2 Problem symmetrization
The size and computational complexity of the optimization problem (OP) can be
significantly decreased by exploiting its rich symmetry derived from the group
structure. Roughly speaking, we will replace solving a large problem by solving many smaller problems and patching the solutions together to obtain a solution to the original, larger problem. While the number of variables in the
original problem is |E |2 , the number of variables of the symmetrized version is
m21 +· · ·+ m2k , where m k are the dimensions of the individual component problems.
Moreover using orbit constraints we will reduce the number of constraints significantly. In the case of SAut(F5 ) the result is a problem with 13 232 variables in
36 semidefinite blocks and 7 229 constraints, which can be realistically attacked
with a numerical solver. However, to be able to perform our computations we will
need to give a different parametrisation of the space of possible solutions by the
means of orbit reduction and the Wedderburn decomposition.
A somewhat parallel exposition of semidefinite programs size reduction using
its symmetry is discussed in detail in [1, 7]. We would like to point out that a
numerical approach to numerical symmetrization of optimization problems that
does not use group representation theory is described in [23], which may be applicable e.g. to finitely presented groups where the symmetry is not clearly visible.

2.1

Invariant SDP problems

Given an automorphism σ of G and ξ ∈ RG , denote by σ(ξ) the element of RG
defined by σ(ξ) g = ξσ( g ) . Let ΣE denote the group

ΣE := {σ ∈ Aut(G ) : σ(∆) = ∆ and σ(E ) = E } .
The group ΣE is finite, determined by its image in Sym(S ), the symmetric group
on S . Let Σ denote any subgroup of ΣE . The action of Σ on E induces an action of
Σ on ME by the formula
(σ(T )) x,y = Tσ−1 ( x),σ−1 ( y) .
The subspace of matrices invariant under this action will be denoted MΣ
.
E
Lemma 5. The expression ∆2 − λ∆ is invariant under Σ.
6

Proof. The verification is straightforward:
X
(∆ − λ I ) g ∆ g −1 σ( t)
(∆2 − λ∆)σ( t) =
g ∈G

=

=

X

g ∈G

X

g ∈G

(∆ − λ I ) g ∆σ(σ−1 ( g −1 ) t)

(∆ − λ I )σ−1 ( g ) ∆σ−1 ( g −1) t

= (∆2 − λ∆)( t),

since, in particular, σ−1 is a bijection.
Lemma 6. We have δσ( t) = σ(δ t ) and δ t−1 = δTt .
In [1] a semidefinite problem is said to be invariant with respect to an action
of a group G if for every solution P , gP is also a solution for every g ∈ G .
Proposition 7. The problem (OP) is Σ-invariant.
Proof. Let P ∈ ME be a solution to (OP). We need to show that σ(P ) is also a
solution to the same problem for every σ ∈ Σ; i.e.,
(∆2 − λ∆) t = 〈δ t , σ(P )〉,
for every t ∈ E . We have
〈 δ t , σ( P ) 〉 =
=
=

X

x−1 y= t

Pσ−1 ( x),σ−1 ( y)

X

σ( x′ )−1 σ( y′ )= t

X

σ( x′−1 y′ )= t

P x′ ,y′

P x′ ,y′

= 〈δσ−1 ( t) , P 〉.

The latter is equal to (∆2 − λ∆)σ−1 ( t) = (∆2 − λ∆) t , by Lemma 5.
In particular, convexity yields
Corollary 8. Let P ∈ ME be a solution for (OP) for some λ > 0. Then there exists
P ∈ MΣ
E that also solves (OP) for the same λ > 0.
The proposition above shows that we can search for an invariant solution.

2.2

Orbit symmetrization

±
Since ∆2 − λ∆ is Σ-invariant, it is well defined on the orbit space E −1 E Σ. While
we can decompose E and E −1 E into the orbits
± of Σ, it is impossible to naively
formulate problem (OP) in “orbit variables” E Σ, as the constraint matrices are
not well defined in ME/Σ . However, since the solution P is Σ-invariant, constraint
matrices can be averaged over orbits, yielding
δ[ t] =

1 X
δσ( t) ,
|Σ| σ∈Σ
7

which encodes the value of ∆2 − λ∆ at [ t]. This results in the orbit symmetrization
of problem (OP):
minimize
subject to

−λ

P ∈ ME , P º 0
­
®
¡ 2
¢
∆ − λ∆ [ t] = δ[ t] , P

for all [ t] ∈ E −1 E /Σ.

¯
¯
The¯ problem
reduces the number of constraints in problem (OP) from ¯ E −1 E ¯
¯
±
to ¯E −1 E Σ¯. However, since P constitutes just one semidefinite block of size
|E | × |E |, and each constraint is expressed by |E | × |E |-matrix multiplication, the
problem is still numerically hard to solve efficiently.

2.3

Block-diagonalization via the Wedderburn decomposition

b of a group G is the family of equivalence classes
Recall that the orthogonal dual G
of irreducible orthogonal representations of G . We will work under the assumption that all irreducible characters of Σ, the group of symmetries of E , are real.
By n1R we denote the n-fold direct sum of the trivial, 1-dimensional real representation.
Let ̺E denote the representation of Σ on ℓ2 (E ) induced by the permutation
L
action of Σ on E . We can decompose (up to unitary equivalence) ̺E ∼
= π∈Σb m π π
into π-isotypical summands, where each irreducible representation π occurs with
multiplicity m π . Since the matrix algebra C ∗ (̺E ) (generated by ̺E (σ) for σ ∈ Σ)
is semisimple, we can find its Wedderburn decomposition: an isomorphism of
C ∗ (̺E ) and a direct sum of simple matrix algebras:
M
Mdim π ⊗ 1mπ .
C ∗ (̺ E ) →
b
π∈Σ

¡
¢′
As Σ-invariant matrices in ME coincide with C ∗ (̺E ) , the commutant of the
algebra C ∗ (̺E ), we obtain
¡
¢′ M
∼ ∗
1dim π ⊗ Mmπ .
MΣ
E = C (̺ E ) →
b
π∈Σ

We show how to explicitly realize and block-diagonalize the Wedderburn isomorphism on MΣ
E by using a minimal projection system in RΣ. Denote by χπ the
central projection in RΣ defined by the character of an irreducible representation
π. Let { pπ }π∈Σb be a minimal projection system; i.e., a set of primitive, self-adjoint,
idempotent elements in RΣ satisfying pψ pπ = 0 for ψ 6= π and χψ pπ = δψ,π pπ ,
where δψ,π denotes the Kronecker delta.
It follows from the definition of pπ that the image of ̺E ( pπ ) is a subspace of
ℓ2 ( E ) of dimension m π .
Let Uπ be the matrix realizing the orthogonal projection from ℓ2 (E ) onto
im ρ E ( pπ ), followed by an isometric isomorphism from im ρ E ( pπ ) onto R mπ . For
π
T
A ∈ MΣ
E define A = dim π · Uπ AUπ . Under the Wedderburn isomorphism above
we have

A 7→

M

b
π∈Σ

1
· 1dim π ⊗ A π ,
dim π

8

and thus the map

A 7→

M

Aπ

b
π∈Σ

defines a block-diagonalizing linear isomorphism
M
Θ : MΣE → Mmπ ,

which satisfies tr( A ) =

2.4

P

π

b tr( A
π∈Σ

π

).

Symmetrization

For the purposes of numerical computation, instead of working with Θ and a
−1
basis of MΣ
and the standard bases of each
E it is advantageous to work with Θ
of Mmπ , and translate the constraints to the new basis via Θ. Let
δπ[ t] = dim π · Uπ δ[ t]UπT .

The following optimization problem is a counterpart of Problem (OP) combining
both the orbit symmetrization and the block-diagonalization reduction:
minimize
subject to

−λ
©
ª
Pπ ∈ Mmπ π∈Σb , Pπ º 0
E
XD π
¡ 2
¢
±
δ[ t] , Pπ for [ t] ∈ E −1 E Σ.
∆ − λ∆ [ t] =

(SOP)

b
π∈Σ

This allows for a reduction of the number of variables in problem (OP) from |E |2
P
to π m2π which turns out to be drastically smaller in practice. Moreover, as most
solvers can exploit the block-diagonal structure, the sizes of matrices the solver
needs to compute with are much decreased, at the cost of increasing numerical
complexity of the constraints.
Proposition 9. Let

P=

´
³
1 X X
dim π · σ UπT PπUπ .
|Σ| σ∈Σ π∈Σb

¢
¡
If λ0 , {Pπ }π∈Σb is a solution to problem (SOP), then (λ0 , P ) is a solution to problem
(OP).
¡
¢
Proof. All we need to check is that 〈δ t , P 〉 = ∆2 − λ0 ∆ t for all t ∈ E −1 E . We have
*
+
´
³
1 X X
T
〈δ t , P 〉 = δ t ,
dim π · σ Uπ PπUπ
|Σ| σ∈Σ π∈Σb
´E
D
³
1 X X
dim π δ t , σ UπT PπUπ
=
|Σ| σ∈Σ π∈Σb
´
³
1 X X
dim π · tr δσT−1 ( t)UπT PπUπ
=
|Σ| σ∈Σ π∈Σb
´
1 X X ³
=
tr dim π · Uπ δσT−1 ( t)UπT Pπ
|Σ| σ∈Σ π∈Σb
*
+
E
X
XD
1 X
T
=
dim π
Uπ δσ−1 ( t)Uπ , Pπ =
dim π · Uπ δ[ t]UπT , Pπ .
|Σ| σ∈Σ
b
b
π∈Σ
π∈Σ

9

Using the definition of δπ[ t] and the formulation of the costraints of (SOP) we can
continue as follows:
E
XD π
δ[ t] , Pπ
〈δ t , P 〉 =
b
π∈Σ
¡ 2

¢
= ∆ − λ0 ∆ [ t]
¡
¢
= ∆2 − λ0 ∆ t .

3 The group Aut(Fn )
3.1

Presentation for Aut(Fn )

Let n ∈ Z be positive and consider the corresponding free group Fn on n generators. Denote by Aut(Fn ) the group of automorphisms of Fn . The special automorphims group SAut(Fn ) is defined as the preimage of {1} under the map
det : Aut(Fn ) → {−1, +1},
obtained by the composition
Aut(Fn ) → Aut(Z n ) = GL n (Z) → Z.
The first arrow above is induced by the abelianization homomorphism Fn → Z n ,
and the second is the classical determinant. The group SAut(Fn ) is of index 2 in
Aut(Fn ). Denote by Inn(Fn ) ⊂ Aut(Fn ) the subgroup of inner automorphisms of
Fn . The outer automorphism group Out(Fn ) is defined as the quotient Out(Fn ) =
Aut(Fn )/Inn(Fn ).
Let (s1 ,... , s n ) be an ordered set of generators of Fn and consider the following
maps of Fn :
(
s k s±j 1 if k = i,
±
R i, j (s k ) =
sk
otherwise;
and

L±i, j (s k ) =

(

s±j 1 s k

if k = i,

otherwise.

sk

n
o
The set S = R ±
, L±i, j for 1 ≤ i, j ≤ n, i 6= j acts on generating n-tuples of Fn and
i, j
hence consists of automorphisms of Fn which generate the group SAut(Fn ) [13,20].
The group Aut(Fn ) is generated by automorphism in S together with automorphisms permutating and inverting generators of Fn . For a detailed description of
automorphisms in S (commonly known as Nielsen transformations) see [21, Section 3.2].

3.2

Implementation of Aut(Fn )

When computing in Aut(Fn ) one usually choses to represent elements either as
words in a finite presentation, or actual functions on Fn transforming free generating sets of Fn to free generating sets. The former aproach allows the group
10

operations to be purely mechanical operations on symbols, but the recognition of
the identity element (the word problem) is a major obstruction to effective computation. On the other hand, the functional approach provides an easy solution to
the recognition of the identity problem: two automorphisms are equal if and only
if their values on transform the standard generating set of Fn agree. To decide
this equality one needs only to perform trivial cancellation. However, the “functional” approach renders inverting an element a considerably harder problem.
Instead of using either of approaches we decided to produce our own implementation, where each element carries both the structure of a word in a finite
presentation, as well as functional information. Given two automorphisms f , g
(written as words in the alphabet S ), to decide the equality problem we compare
( f ( x1 ),... , f ( x n ))

and

( g( x1 ),... , g( x n )) ,

where f ( x i ) is its value on i -th (standard) generator of Fn , computed as the standard composition of letters in f . This comparison involves only checking equality
in free group which is a trivial problem. Effectively, we use all of the relations
(regardles of their length), in an indirect manner.

3.3

The symmetrizing group Σ

The group generated by the automorphisms permuting and inverting generators
of Fn is isomorphic to the group Z/2 ≀ S n (the signed permutation group). Consider
the action of Z/2 ≀ S n on Aut(Fn ) by conjugation. Clearly the action preserves the
set S of all Nielsen transformations and hence the group SAut(Fn ). Moreover
the action preserves the word-length metric on SAut(Fn ) induced by S (and thus
E = B2 ( e, S )), so we can set Σ = Z/2 ≀ S n in our considerations.
Minimal projection system for Σ
Since Σ ∼
= Z2 n ⋊ S n is a semi-direct product of S n acting in the natural fashion
on the n-fold direct product of Z2 , we may obtain a minimal projection system
for Σ from a minimal projection system of S n . It is a well known fact (see e.g.
[29, Section 8.2]) that irreducible representations of the semidirect product are
c2 n (which equals the character
formed in the following fashion. The dual group Z
group in this case) decomposes into (n + 1) orbits of the induced action of S n . Let
c2 n denote the character which evaluates to −1 on the non-trivial element
gi ∈ Z
in the first i coordinates and to 1 otherwise. Then { g i } ni=0 forms a complete set
of orbit representatives of the action, and the stabiliser of g i is H i = S i × S n− i ,
embedded naturally into S n (under the convention S0 = S1 = {id}). It is now
straightforward that every irreducible representation of Σ is of the form
θ i,π = indΣ
Z2 n ⋊ H g i ⊗ π,
i

ci are trivially extended to Z2 n ⋊ H i .
c2 n and π ∈ H
where g i ∈ Z
A minimal projection system for Z2 n ⋊ H i can be described as
©

χ i pπ

ª

ci
π∈H

,

where χ i denotes the central projection associated to g i and { pπ }π∈H
ci is a minimal
projection system for H i . Note that irreducible representations of H i = S i × S n− i
11

are tensor products of irreducible representations of the factors, thus a minimal
projection system for H i can be constructed from those of S i and S n− i , by taking
all possible products of minimal projections. Accordingly,
n©
on
ª
χ i pπ pψ π∈Sc ,ψ∈S
i

n− i

i =0

is a minimal projection system for Σ.

Minimal projection system for S n , n ≤ 6
We present a minimal projection systems for S n , n ≤ 6 which we used in our
computations. It is well known that irreducible representations of S n correspond
to integer partitions of n. For the trivial and the sign representations (partitions
n1 and 1n , respectively) we pick ε = (). For other representations π we fix the
element επ as in the table
n

Partition

3

21 11

4

21 12
31 11
22

5

21 13
31 12
22 11
41 11
31 21

6

21 14
31 13
22 12
41 12
31 21 11
51 11
23
41 21
32

επ
1¡

¢

2 () + (1, 2)
¢
1¡
2 () + (1, 2)
¡
¢
1
2 () − (1, 2)
¡
1 () + (1, 2)¢
2
¢
1¡
2 () + (1, 2)
¡
¢
1
4 () + (1, 4, 3, 2) + (1, 3)(2, 4) + (1, 2, 3, 4)
¡
¢
1 () + (1, 3, 2) + (1, 2, 3)
3
1 ¡() − (1, 2)¢
2
¢
1¡
3 () + (1, 3, 2) + (1, 2, 3)
¡
¢
1
2 () + (1, 2)
1 ¡() + (1, 2) + (1, 2)(3, 4) + (3, 4)¢
4
1 ¡() + (1, 3, 5, 2, 4) + (1, 4, 2, 5, 3) + (1, 5, 4, 3, 2) + (1, 2, 3, 4, 5)¢
5
¢
1¡
4 () − (1, 2) + (1, 2)(3, 4) − (3, 4)
¡
1
12 () + (1, 2) + (1, 2)(3, 4) + (3, 4) + (3, 4, 5) + (1, 2)(3, 4, 5)+

(1, 2)(3, 5) + (3, 5) + (1, 2)(4, 5) + (4, 5) + (3, 5, 4) + (1, 2)(3, 5, 4)
¢
1¡
2 () − (1, 2)
¡
¢
1
3 () + (1, 3, 2) + (1, 2, 3)
¡
1 () + (1, 3, 5, 2, 4) + (1, 4, 2, 5, 3) + (1, 5, 4, 3, 2) + (1, 2, 3, 4, 5)¢
5
¢
1¡
3 () + (1, 3, 2) + (1, 2, 3)

¢

Recall that χπ is the central projection corresponding to irreducible (character of)
representation π. By inspecting the appropriate table of characters one can check
that ϕπ (επ ) = 1 for the character ϕπ corresponding to π. Even though projections
επ are not necessarily mutually orthogonal, it follows from the orthogonality of
characters that
©
ª
pπ = χπ επ π∈Scn
constitutes a minimal projection system for S n .

4 Description of the algorithm
Given a group G generated by S :

12

1. generate E = B2 ( e, S ), E −1 E = B4 ( e, S ) and ∆ (stored in delta.jld as the
coefficients vector in E −1 E );
2. compute the multiplication table E −1 × E → E −1 E (stored in pm.jld);
3. compute the representation ̺E : Σ → ME as permutation matrices (stored
in preps.jld);
b compute
4. compute the Wedderburn decomposition of ME , i.e. for every π ∈ Σ
Uπ ’s (stored in U_pis.jld)

5. decompose E −1 E into orbits of Σ (stored in orbits.jld);

6. use ∆, the orbit structure, the multiplication table and Uπ ’s to construct the
constraints of the symmetrized optimization problem (SOP);
7. solve the symmetrized optimization problem to obtain (λ0 , {Pπ }π ) (stored in
lambda.jld, and SDPmatrix.jld);
8. reconstruct P according to Proposition 9 (stored in SDPmatrix.jld);
9. certify the solution (λ0 , P ) as described in Section 4.3.

4.1

Multiplication table on E

To perform quickly the multiplication ξ∗i ξ i we cache the multiplication table
M : E −1 × E → E −1 E , as a matrix M ∈ ME such that M g,h = g−1 h. To avoid indexing entries of M by group elements and storing them in M (due to technical
reasons) we fix the order x of elements in E −1 E , such that x0 = e, {x j }|jS=|1 = S ,
increasing with the word-length. Then we can store only the indices, i.e. if g ∈ E
is the i -th element of E −1 E , (i.e. g = x i , where E ⊂ E −1 E as the first |E |-elements)
and h ∈ E is the j-th element of E −1 E (i.e. h = x j ), then M i, j = k, where g−1 h = xk
is the k-th element of E −1 E . Thus once the full M has been populated, we no
longer need the actual group elements to perform (twisted) multiplication of elements of RG supported on E . In particular, given a solution (λ0 , P ), multiplication
table M and ∆ (as a coordinate vector in x), one can compute the sum-of-squares
P
decomposition i ξ∗i ξ i and compare it with ∆2 − λ0 ∆ without the need to access
group elements directly.
Note that the full multiplication table is also needed for producing the constraint matrices.

4.2

Symmetrization

The minimal projection system { pπ }π∈Σb for Σ is computed in QΣ as described in
Section 3.3. Then coefficients are converted to floating point numbers and ̺E ( pπ )
is evaluated, where ̺E is the permutation representation of Σ on E . Uπ for each
b are obtained using singular value decomposition.
π∈Σ

4.3

Certification

The certification process starts by converting the solution of problem (SOP) to a
solution (λ0 , P ) of problem (OP) using standard floating-point arithmetic. Then
certification of (λ0 , P ) follows mostly the procedure described in [17, Section 2].
13

p
However, instead of passing through rational approximation of Q = P , as described there, we use the interval arithmetic directly. We turn each entry of
Q into an interval of radius ε ∼ 2.2 · 10−16 which contains the computed value.
Then we shift those intervals so that the sum of each colum q i contains 0 (this
corresponds to the projection to the augmentation ideal). Setting ξ i = q i x, as
previously, we finally compute the residual
X
r = ∆2 − λ0 ∆ − ξ∗i ξ i .

Note that in this approach each ξ i as well as r is an element of the group ring over
real intervals. While by using the interval arithmetic we loose track of the actual
values of ξ i and r, however, we have a mathematical guarantee that there are ξ i ∈
ξ i , where ∈ denotes belonging on the coefficient level (with rational coefficients)
and that the result r of a similar computations performed in real coefficients on
ξ i ’s satisfies
kr k1 ∈ krk1 .

Although less precise than the rational arithmetic, the computation of krk1
from Q as described above is much faster, as it involves multiplication and addition of (machine) floating point numbers, and directed rounding. Performing
similar calculations in rational arithmetic is much slower (if possible in the case
of SAut(F5 ) at all), as the numerator of a sum of near-zero rationals grows exponentially.

4.4

Software details

Our implementation in Julia programming language [3] depends on the following
packages
• Nemo [11] package for group theoretical computations;
• JuMP [8] package for formulation of the optimization problem;
• SCS [26] solver for solving semi-definite problems.
The software used for computations is contained in the following git-repositories:
• package https://git.wmi.amu.edu.pl/kalmar/Groups.jl for computations in wreath products and automorphism groups of free groups;
• package https://git.wmi.amu.edu.pl/kalmar/GroupRings.jl for computations in group rings;
• package https://git.wmi.amu.edu.pl/kalmar/PropertyT.jl for computations of the spectral gap;
• repository https://git.wmi.amu.edu.pl/kalmar/GroupsWithPropertyT
contains the specific functions and routines related to the project, as well
as general manual on how to replicate the results.

14

Replication details
The ball of radius 4 in SAut(F5 ) consists of 11 154 301 elements. Generating
B4 ( e, S ), decomposing it into 7229 orbits of Z2 ≀ S5 action, computing (twisted)
multiplication table on B2 ( e, S ) and finding Uπ ’s for the Wedderburn decomposition took about 17h on a 12-core computer and requires a minimum of 64GB of
RAM. This part has been performed on the PL-Grid cluster. Once this has been
computed, the optimization step can be performed on a desktop computer, as the
actual optimization problem consists of 13232 variables in 36 semi-definite blocks
and 7230 constraints. The optimization phase had been running for ∼ 400 hours
(on a workstation computer with 4-core CPU) until the acuracy of 10−9 has been
reached. The reconstruction of P (according to Proposition 9) and its certification
take approximately 3.5h and 3h, respectively (on a workstation computer).
The pre-computed multiplication table, orbit decomposition, Uπ ’s, as well as
the solution P obtained can be found here.

5 Proof of Theorem 1
We are now in position to prove our main theorem.
¢
¡
Proof of Theorem 1. Given a solution λ0 , (Pπ )π∈Σb of the symmetrized optimization problem (SOP) we reconstruct (in floating point arithmetic) a solution to the
optimization problem (OP) according to Proposition (9). This solution P is in the
attached file.
Let Q denote the real part of the square root of P . Construct Q as described
in section 4.3. Let ξ i be the i -th column of Q . The residual is given by
X
r = ∆2 − λ0 ∆ − ξ∗i ξ i ,
and the certified spectral gap is now obtained by considering
X
X
∆2 − λ0 ∆ = ξ∗ ξ + r ≥ ξ∗i ξ i + 22 krk1 ∆,
i

hence

X
¡
¢
∆2 − λ0 − 22 krk1 ∆ ≥ ξ∗i ξ i ≥ 0.

This allows to conclude that the spectral gap satisfies
λ(G, S ) ≥ λ0 − 22 krk1 .

In the case of provided solution for SAut(F5 ) we have
λ0 = 1.2,

and krk1 = [0.00030484, 0.00030488],

which leads to certified estimate λ > 1.19878048. Since the generating set consists of 80 elements this results in
κ(SAut(F5 ), S ) > 0.173117.

15

6 Extrapolation of property (T )
In case of arithmetic groups, once we know SLn (Z) has property (T ) for some n, it
is rather easy to deduce from this fact that SLm (Z) has property (T ) for all m ≥ n,
because SL m (Z) is boundedly generated by finitely many conjugates of SLn (Z)
(see [30], particularly around Section 4.III.7).
However, in the case of Aut(Fn ) a similar approach seems break down at the
currently open Question 12 in [6]. Namely, it is not known whether a quotient
Q of Aut(Fn+1 ) must be finite provided that Aut(Fn ) has finite image in Q . If a
counterexample exists, property (T ) of Aut(Fn ) cannot, obviously, tell anything
about such an infinite quotient Q . We nevertheless make an effort to extrapolate
property (T ) of Aut(Fn ) to a larger group.
For a group G , a normal subgroup H ⊆ G and a unitary representation (π, H ),
let P H denote the orthogonal projection onto the space H H of vectors invariant
under π(H ). For a subset S ⊂ G put κ(G, S, π) to be the largest κ ≥ 0 that satisfies
κkv − P G vk ≤ max kv − π s vk
s ∈S

for all v ∈ H . Recall that a group G has property (T ) if and only if there is a finite
(necessarily generating) subset S such that the corresponding Kazhdan constant
κ(G, S, π) is strictly positive for every π.
Let α : G → Aut(H ), g 7→ α g , be an action and T ⊂ H be a subset such that

generates H . Put

©
ª
TG = α g ( t) : g ∈ G, t ∈ T

©
ª
−1
such that h = s1 · · · s k .
ℓ( h) = min k : ∃s1 ,... , s k ∈ TG ∪ TG

Proposition 10. Let G ⋉ H be the semidirect product by an action α : G → Aut(H )
and ℓ be as above. Assume that T is a finite generating subset of H , Inn(H ) ⊂ α(G )
and
©
ª
L = max ℓ( tm ) : t ∈ T, m ∈ N < ∞.
Then, for any unitary representation (π, H ) of G ⋉ H , one has
κ(G ⋉ H, S ∪ T, π) ≥

κ(G, S, π|G )

1 + 4|T |1/2 L

.

In particular, if G has property (T ) or (τ), then so does G ⋉ H .
Proof. Let v ∈ H be given and put κ := κ(G, S, π|G ) ≤ 2 and

C := max kv − π g vk.
g ∈S ∪ T

Then, w := P G v satisfies kv − wk ≤ κ−1 C . For every g ∈ G and t ∈ T , one has
°
¡
¢ ° °
¡
¢ °
°w − π α g ( t) w° = °w − π gtg−1 w° = kw − π( t)wk ≤ 4κ−1 C.

Thus, for every t ∈ T , one has

°
¡ ¢ °
sup ° w − π tm w° ≤ 4κ−1 LC,
m

16

which implies
k(1 − P t ) wk ≤ 4κ−1 LC,

for the orthogonal projection P 〈 t〉 onto H 〈 t〉. Since w is G -invariant and Inn H ⊂
α(G ), the linear functional τ( a) := 〈 aw, w〉 is a trace on the von Neumann algebra
M generated by π(H ). We note that for any orthogonal projections p, q ∈ M one
has
p − p ∧ q ∼ p ∨ q − q,

and hence

k( p − p ∧ q)wk2 = τ( p − p ∧ q) = τ( p ∨ q − q) = k( p ∨ q − q)wk2 ,

where p ∧ q (respectively, p ∨ q) is the orthogonal projection onto ran p ∩ ran q
(respectively, span(ran p ∪ ran q)). See [31, Proposition V.1.6] for a proof of this
fact. In particular,
k(1 − p ∧ q) wk2 = k(1 − p) wk2 + k( p ∨ q − q) wk2 ≤ k(1 − p) wk2 + k(1 − q) wk2 .
V
Since P H = t∈T P t , it follows that
!1/2
Ã
X
2
k(1 − P t ) wk
k(1 − P H ) wk ≤
≤ 4κ−1 |T |1/2 LC.
t ∈T

Since H
fore,

H

is G -invariant (by normality of H ), P H w is still G -invariant. Therekv − P G vk ≤ kv − P H wk ≤ κ−1 (1 + 4|T |1/2 L)C.

This proves the claim.

The above proposition applies to the action of Aut(Fn ) on Fn = 〈 g 1 ,... , g n 〉 for
n ≥ 2, since g m
= g−j 1 · g j g m
( j 6= i ) has ℓ( g m
) ≤ 2.
i
i
i
Corollary 11. If Aut(Fn ) has property (T ), then the subgroup

Γ = {θ ∈ Aut(Fn+1 ) : θ(Fn ) ⊂ Fn }
in Aut(Fn+1 ) has property (T ).

Proof. Any element θ as above satisfies θ( g n+1 ) = agǫn+1 b for some a, b ∈ Fn and
ǫ ∈ {−1, +1}. This means that the above subgroup is isomorphic to (Aut(Fn ) ×Z/2) ⋉
(Fn ×Fn ), where Aut(Fn ) acts on Fn ×Fn diagonally and Z/2 acts on Fn ×Fn by the flip.
Since Aut(Fn ) ⋉ Fn has property (T ) by the above proposition, Aut(Fn ) ⋉ (Fn × Fn )
has property (T ) as well.

7

SL6 (Z) and SL4 (Z〈 X 〉)

We have also applied the symmetrized algorithm to certain other groups, for
which the non-symmetrized approach such as in [12, 17, 24], was not available.
In the case of two linear groups, SL6 (Z), E (6)) and SL4 (Z〈 X 〉, E (4)), we obtained
new estimates for the Kazhdan constants. For the first group we obtained a certified bound
κ(SL6 (Z), E (6)) ≥ 0.3812;
for the second group the certified bound is

κ(SL4 (Z〈 X 〉), E (4)) ≥ 0.2327.

17

8 Final remarks
Smallest radius for existence of a solution As mentioned in the introduction, one of the reasons for our approach not producing an answer in the case of
Aut(F4 ) could be that the equation (1) does not have a solution on a ball of radius
2. It is in general unclear, for a group with property (T ), what is the smallest
radius r such that (1) has a solution on the ball of radius r. It is equally unclear
what is the radius r for which the optimal λ is attained.
We have not been able to reprove property (T ), using the method presented
here, for SL3 (Z[ X ]) on the ball of radius 2. Recall that for SL3 (Z[ X ]) property
(T ) was proved by Shalom [30] and Vaserstein [32], as well as by Ershov and
Jaikin-Zapirain [10].
Note also that the bound given in [12] on a ball of radius 2 was better for
SL4 (Z) than for SL3 (Z). All this suggests that to detect property (T ) (or estimate the Kazhdan constant) of SL(n, Z[ X 1 ,...X k ]) one needs larger ball as k increases and smaller ball as n increases (although the Kazhdan constant itself
gets smaller).

References
[1] C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin. Invariant semidefinite programs. In Handbook on semidefinite, conic and polynomial optimization, volume 166 of Internat. Ser. Oper. Res. Management Sci., pages
219–269. Springer, New York, 2012.
[2] B. Bekka, P. de la Harpe, and A. Valette. Kazhdan’s property (T), volume 11 of New Mathematical Monographs. Cambridge University Press,
Cambridge, 2008.
[3] 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.
[4] O. Bogopolski and R. Vikentiev. Subgroups of small index in Aut(F n ) and
Kazhdan’s property (T). In Combinatorial and geometric group theory,
Trends Math., pages 1–17. Birkhäuser/Springer Basel AG, Basel, 2010.
[5] E. Breuillard. Expander graphs, property (τ) and approximate groups. In
Geometric group theory, volume 21 of IAS/Park City Math. Ser., pages 325–
377. Amer. Math. Soc., Providence, RI, 2014.
[6] M. R. Bridson and K. Vogtmann. Automorphism groups of free groups, surface groups and free abelian groups. In Problems on mapping class groups
and related topics, volume 74 of Proc. Sympos. Pure Math., pages 301–316.
Amer. Math. Soc., Providence, RI, 2006.
[7] E. de Klerk, C. Dobre, and D. V. Ṗasechnik. Numerical block diagonalization
of matrix ∗-algebras with application to semidefinite programming. Math.
Program., 129(1, Ser. B):91–111, 2011.
[8] I. Dunning, J. Huchette, and M. Lubin. Jump: A modeling language for
mathematical optimization. SIAM Review, 59(2):295–320, 2017.

18

[9] J. S. Ellenberg. Superstrong approximation for monodromy groups. In Thin
groups and superstrong approximation, volume 61 of Math. Sci. Res. Inst.
Publ., pages 51–71. Cambridge Univ. Press, Cambridge, 2014.
[10] M. Ershov and A. Jaikin-Zapirain. Property (T) for noncommutative universal lattices. Invent. Math., 179(2):303–347, 2010.
[11] C. Fieker, W. Hart, T. Hofmann, and F. Johansson. Nemo/hecke: Computer
algebra and number theory packages for the julia programming language.
In Proceedings of the 2017 ACM on International Symposium on Symbolic
and Algebraic Computation, ISSAC ’17, pages 157–164, New York, NY, USA,
2017. ACM.
[12] K. Fujiwara and Y. Kabaya. Computing Kazhdan constants by semidefinite
programming. ArXiv e-prints, mar 2017, 1703.04555.
[13] S. M. Gersten. A presentation for the special automorphism group of a free
group. J. Pure Appl. Algebra, 33(3):269–279, 1984.
[14] R. Gilman. Finite quotients of the automorphism group of a free group.
Canad. J. Math., 29(3):541–551, 1977.
[15] F. Grunewald and A. Lubotzky. Linear representations of the automorphism
group of a free group. Geom. Funct. Anal., 18(5):1564–1608, 2009.
[16] G. Jameson. Ordered linear spaces. Lecture Notes in Mathematics, Vol. 141.
Springer-Verlag, Berlin-New York, 1970.
[17] M. Kaluba and P. W. Nowak. Certifying numerical estimates of spectral
gaps. Groups Complexity Cryptology, to appear, Mar. 2017, ArXiv e-prints
1703.09680.
[18] M. Kassabov. Symmetric groups and expander graphs.
170(2):327–354, 2007.

Invent. Math.,

[19] A. Lubotzky. Discrete groups, expanding graphs and invariant measures,
volume 125 of Progress in Mathematics. Birkhäuser Verlag, Basel, 1994.
With an appendix by Jonathan D. Rogawski.
[20] A. Lubotzky and I. Pak. The product replacement algorithm and Kazhdan’s
property (T). J. Amer. Math. Soc., 14(2):347–363, 2001.
[21] W. Magnus, A. Karrass, and D. Solitar. Combinatorial group theory: Presentations of groups in terms of generators and relations. Interscience Publishers [John Wiley & Sons, Inc.], New York-London-Sydney, 1966.
[22] J. McCool. A faithful polynomial representation of Out F3 . Math. Proc. Cambridge Philos. Soc., 106(2):207–213, 1989.
[23] K. Murota, Y. Kanno, M. Kojima, and S. Kojima. A numerical algorithm
for block-diagonal decomposition of matrix ∗-algebras with application to
semidefinite programming. Jpn. J. Ind. Appl. Math., 27(1):125–160, 2010.
[24] T. Netzer and A. Thom. Kazhdan’s Property (T) via Semidefinite Optimization. Experimental Mathematics, 24(3):371–374, jul 2015.
19

[25] A. Neumaier. Computer-assisted proofs. In 12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics (SCAN 2006), pages 5–5, Sept 2006.
[26] 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, June 2016.
[27] 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.
[28] K. Schmüdgen. Noncommutative real algebraic geometry—some basic concepts and first ideas. In Emerging applications of algebraic geometry, volume 149 of IMA Vol. Math. Appl., pages 325–350. Springer, New York, 2009.
[29] J.-P. Serre. Linear representations of finite groups. Springer-Verlag, New
York-Heidelberg, 1977. Translated from the second French edition by
Leonard L. Scott, Graduate Texts in Mathematics, Vol. 42.
[30] Y. Shalom. The algebraization of Kazhdan’s property (T). In International
Congress of Mathematicians. Vol. II, pages 1283–1310. Eur. Math. Soc.,
Zürich, 2006.
[31] M. Takesaki. Theory of operator algebras. I, volume 124 of Encyclopaedia of
Mathematical Sciences. Springer-Verlag, Berlin, 2002. Reprint of the first
(1979) edition, Operator Algebras and Non-commutative Geometry, 5.
[32] L. Vaserstein. Bounded reduction of invertible matrices over polynomial
rings by addition operations. preprint.

20

