How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable by computers (arXiv:1312.5431, explained below), but I'm quite lame with computers and have no idea what they actually can do. So, my question is how feasible is it to prove property (T) of a given group, say $\mathrm{Out}(F_{r>3})$ (a famous open problem), by solving the equation below by a computer? Even the case of $\mathrm{SL}_{r>2}({\mathbb Z})$ where property (T) is known is unclear.

A group $\Gamma$, generated by a finite subset $S$ and with its non-normalized Laplacian denoted by $$\Delta=\sum_{x\in S} (1-x)^*(1-x)=\sum_{x\in S} (2-x-x^{-1})\in{\mathbb Z}[\Gamma],$$ has property (T) iff the equation in ${\mathbb Z}[\Gamma]$, $$m \Delta^2 = n \Delta + \sum_{i=1}^k l_i \xi_i^*\xi_i$$ has a solution in $k,m,n,l_i\in{\mathbb Z}_{>0}$ and $\xi_i\in{\mathbb Z}[\Gamma]$.

• @HJRW: Yes, if I'm not mistaken. Given ${\mathbb F}_S\to\Gamma$, finite sequences $\xi_1,\ldots,\xi_k$ in ${\mathbb Z}[{\mathbb F}_S]$ are enumerable and if they satisfy the equation in ${\mathbb Z}[\Gamma]$ is semidecidable if $\Gamma$ is recursively presented. – Narutaka OZAWA Jan 13 '14 at 14:11
• Very cool result! – John Wiltshire-Gordon Jan 13 '14 at 15:43
• @ACL - this is certainly not possible. The class of groups without T is not recursively enumerable. For instance, $G*G$ has T if and only if $G$ is trivial. So if you could recognize T then you could recognize the trivial group (which, of course, you can't). – HJRW Jan 13 '14 at 19:33
• @Narutaka Ozawa: It would help if you were to take a concrete example, such as the famous open problem you mentioned, and work out exactly how big a system of equations you would need to solve. This would be very helpful for people who are computational experts but not experts in group theory. – Timothy Chow Jan 13 '14 at 23:03
• Actually, the size of $T$ might not be the only parameter. The size of the gap should matter too (see my comment to David's answer). – François G. Dorais Jan 13 '14 at 23:33

Using the $\Delta^2- \epsilon \Delta$ approach, Tim Netzer and I have verified Kazhdan's property (T) for ${\rm SL}(3,\mathbb Z)$. For the standard generators $e_{ij}$ ($i\neq j$) we can show a spectral gap of the normalized Laplace operator of $1/120$. There is a lot of room for further improvement.

To my knowledge, the best previously known lower bound was about $1/3500000$ (and the best upper bound $1/3$).

The approach uses a positive semi-definite programming package in MatLab, which we use to guess a large positive semi-definite matrix and Mathematica to verify symbolically (computing with fractions etc.) that this indeed yields a sum-of-squares decomposition + some easy theoretical argument that deals with the error terms. The final argument is purely symbolic and does not involve any numeric computation that could involve errors because of rounding etc.

We are planning to write a short note and make the computation available in the internet. Now, we attempt to see what we get for ${\rm Aut}(F_4)$.

Edit on November 11, 2014: We have now uploaded the preprint with an attached Mathematica notebook to the arXiv, http://arxiv.org/abs/1411.2488.

• Fantastic. I accept it as an answer (so unfortunately I cannot accept Speyer's) and wish you good luck on Aut($F_4$)! BTW, I learned sometime ago that semidecidability of property (T) had been observed by Silberman. metric2011.wordpress.com/2011/03/02/… – Narutaka OZAWA May 22 '14 at 2:43
• Why in particular $\mathrm{Aut}(F_4)$? is the answer known for $\mathrm{Aut}(F_2)$ and $\mathrm{Aut}(F_3)$? – Vladimir Jun 12 '14 at 14:12
• $Aut(F_2)$ and $Aut(F_3)$ are known not to have Kazhdan's property $(T)$. If $Aut(F_n)$ for high $n$ would have Kazhdan's property $(T)$, this would explain why the product replacement algorithm works so well -- this was explained in a paper by Alex Lubotzky and Igor Pak. – Andreas Thom Jun 13 '14 at 8:08

I can make a little progress here. One of your key subproblems is: Given a computable group $G$, a finite list of elements $T \subseteq G$ and an element $\alpha \in \mathbb{Q}[G]$, determine whether there exist $\xi_1$, $\xi_2$, …, $\xi_k$ in $\mathbb{R} T$ so that $$\alpha = \sum_{i=1}^k \xi_i \xi^{\ast}_i.$$

This problem can be solved by semidefinite programming, which is a field of numerical analysis with well developed toolkits. In particular, I will solve the above problem for all $k$ at once.

Write the elements of $T$ as $g_1$, $g_2$, ..., $g_t$ and write $$\xi_i = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T \cdot a_i$$ where $a_i \in \mathbb{R}^t$. Then the above equation is $$\alpha = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T \left( \sum_{i=1}^k a_i a_i^T \right) (g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} ).$$

Recall that a $t \times t$ real matrix $X$ can be written as $\sum a_i a_i^T$ if and only if $X$ is positive semidefinite. So your question is does there exist a matrix $X$ such that

(1) $X$ is positive semidefinite and

(2) $\alpha = (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T X(g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} )$

Note that condition (2) is an affine linear condition on $X$. Solving linear equations with the constraint that variables be positive semidefinite matrices is what SD programming is all about.

Working a little bit harder, you should be able to copy Peter Shor's trick here and maximize $r$ subject to the SD program $$\Delta^2 = r \Delta + (g_1 \ g_2 \ g_3 \ \cdots \ g_t)^T X(g_1^{-1} \ g_2^{-1} \ \cdots \ g_t^{-1} ),\ X \ \textrm{positive semi definite};$$ so you get a spectral gap if the optimal $r$ is positive.

I expect the hard part will be choosing the set $T$ to use; I have no ideas about this.

• The complexity of SDP depends on the size of the problem and the degree of accuracy desired. The first is correlated to the size of the set $T$ and the second depends on how far the "optimal $r$" is from zero. Is there a way to estimate how big $r$ would be if there is a positive one? – François G. Dorais Jan 13 '14 at 23:31
• @François G. Dorais: How does SDP work? First of all, $r\le0$ always solves the equation. When the computer says there's a solution $r>0$, does it really mean that? Or do we need enough margin between $r$ and $0$ to be sure? Anyway, we should be able to verify it working in ${\mathbb Z}[\Gamma]$, shouldn't we? – Narutaka OZAWA Jan 13 '14 at 23:47
• @NarutakaOZAWA: SDP will solve the problem to a prescribed accuracy $\varepsilon$. If the output is a positive number less than $\varepsilon$ then the true solution could still be $0$; more accuracy is needed to determine whether the true answer is positive or zero. It's only if the required precision is known in advance that this gives a decision procedure. – François G. Dorais Jan 13 '14 at 23:56
• Right. One should add that, by Tarski's theorem, it is decidable whether an SDP is solvable but, according to the Handbook of Semidefinite Programming books.google.com/… "Given an SDP ... there is no polynomial time algorithm to decide whether it is feasible or not." – David E Speyer Jan 14 '14 at 0:30
• David Speyer, thank you for your insight. François G. Dorais, thank you for your clarification. – Narutaka OZAWA Jan 14 '14 at 0:39

I think it is appropriate to let MO users know (the OP himself knows it well) that this question was recently solved: it is feasible to provide a computer based proof for property (T) using the Ozawa Equation and this method was applied successfully to the groups mentioned in the question. In particular, the famous open problem alluded to above is now solved. The computation is done via semidefinite programming, as suggested by David Speyer in his answer.

See Kaluba-Kielak-Nowak for a proof that $$\mathrm{Aut}(F_n)$$ has (T) for $$n\geq 5$$. The case $$n=5$$ was treated earlier in Kaluba-Nowak-Ozawa. Some earlier positive results were obtained in Netzer-Thom and Fujiwara-Kabaya.

We note that $$\mathrm{Aut}(F_2)$$ and $$\mathrm{Aut}(F_3)$$ are known not to have (T), and the case for $$\mathrm{Aut}(F_4)$$ is still open. This is all quite remarkable.