Notes of Koji Fujiwara’s Cambridge lecture 09-03-2017

Computing Kazhdan constants by computer

Joint with Yuichi Kabaya.

Experimental mathematics!

1. Mathematical problem

Let {\Gamma} be a group generated by a finite set {S}. Define {\kappa(\Gamma,S)} as the infimum over all unitary representations {\pi} of {\Gamma} without invariant vectors of displacement

\displaystyle  \begin{array}{rcl}  \kappa(\Gamma,S,\pi)=\inf_{|\xi|=1}\max_{s\in S}|\pi(s)\xi-\xi|. \end{array}

Let {\Delta=|S|-\sum_s\in S s\in{\mathbb R}[\Gamma]} denote the Laplacian of {S}. It satisfies {\Delta^*=\Delta}. For every unitary representation {\pi} of {\Gamma}, {\pi(\Delta)} becomes a bounded self-adjoint operator. Let {\epsilon} denote infimum of spectral gaps of {\pi(\Delta)} over all unitary representations {\pi} of {\Gamma} without invariant vectors. Then

\displaystyle  \begin{array}{rcl}  \sqrt{\frac{2\epsilon}{|S|}}\leq \kappa(\Gamma,S). \end{array}

Ozawa has given a useful characterization of property (T): {\Gamma} has Kazhdan’s property iff there exist {b_1,\ldots,b_n\in{\mathbb R}[\Gamma]} such that

\displaystyle  \begin{array}{rcl}  \Delta^2-\epsilon\Delta=\sum_{i=1}^n b_i^* b_i. \end{array}

The optimal {\epsilon} will be denoted by {\epsilon(\Gamma,S)}. Ozawa also shows that {b_i}‘s can be chosen in {{\mathbb Q}[\Gamma]} provided {\sum_{i=1}^n b_i^* b_i} is replaced with

\displaystyle  \begin{array}{rcl}  \sum_{i=1}^n r_i b_i^* b_i. \end{array}

with positive rationals {r_i}.

Finding a solution {(b_1,\ldots,b_n)} amounts to solving a semidefinite programming (SDP) problem. There exist software for this purpose, but they are limited to matrices of size {10^4 \times 10^4}. This limits the size of the supports of candidates {b_i} to a ball of radius 4 if {|S|=10}. Note that 10 is small. The classical generating system of {SL(3,{\mathbb Z})} has 12 elements.

Fortunately, the SDP algorithm does not require a solution of the word problem in {\Gamma}. It provides an approximate solution. A lemma due to Netzer-Thom guarantees that if an approximate solution exists, then a true solution exists.

2. Experiments

I have played with {\tilde A_2} buildings. The smallest one has links with 14 vertices (incidence graph of projective plane over {F_q}, {q=2}).

A classical theorem asserts that discrete cocompact isometry groups of such buildings have property (T). The proof in Bekka-de la Harpe-Valette’s proof gives a generating system {S} and an explicit lower bound on {\kappa(\Gamma,S)}.

The exact value of the Kazhdan’s constant has been obtained by Cartwright-Mlotowski-Steger.

{\tilde A_2} groups for {q=2} and {3} acting transitively on vertices have been classified (Cartwright-Mantero-Steger-Zappa). For {q=2}, there are 9 examples. I did run the software, and it produced figures equal to the CMS bound up to the 6th digit (applying Ntzer-Thom, I could guarantee only the first 4 digits). It also works with the first 8 {q=3} groups.

Ronan has exhibited 4 more groups with 1 triangle quotients, whose Kazhdan constant is unknown. These are triangles of groups with trivial face group, {{\mathbb Z}/3{\mathbb Z}}-edge groups, and order 21 Frobenius vertex groups. They are automatic (Gersten-Short), and they have exactly the same rational growth function (Floyd). Two of them are linear (Koehler-Meixner-Wester), the third has an index 3 normal subgroup which is linear, the fourth one is not linear (Bader-Caprace-Lecureux). On these 4 examples, the software gives the same value of the Kazhdan constant, which seems to be very close to {(\sqrt{2}-1)/\sqrt{3}}. Is this exactly true ?

For {Sl(3,{\mathbb Z})} and {Sl(4,{\mathbb Z})}, we get a slightly better bound that Netzer-Thom’s, roughly a third of Zuk’s upper bound. Unexpectedly, our bound for {Sl(4,{\mathbb Z})} is larger than that for {Sl(3,{\mathbb Z})}.

For finite Coxeter groups and finite complex reflection groups

Is the spectral gap achieved (its a sup)? Answer is yes for {\tilde A_2} groups.

Vdovina: how does spectral gap or Kazhdan constant behave when passing to an index 2 subgroup ? This would help for Ronan groups, which are commensurable to certain {\tilde A_2} groups. There seems to be no simple sharp mathematical answer, but perhaps the algorithmic method.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in seminar. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s