Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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]$.

share|improve this question
1  
@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 at 14:11
2  
Very cool result! –  John Wiltshire-Gordon Jan 13 at 15:43
3  
@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 at 19:33
2  
@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 at 23:03
2  
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 at 23:33

2 Answers 2

up vote 28 down vote accepted

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)$.

share|improve this answer
2  
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 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 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 at 8:08
    
Thanks, Andreas! –  Vladimir Jun 13 at 18:15

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.

share|improve this answer
2  
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 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 at 23:47
3  
@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 at 23:56
2  
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 Speyer Jan 14 at 0:30
    
David Speyer, thank you for your insight. François G. Dorais, thank you for your clarification. –  Narutaka OZAWA Jan 14 at 0:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.