Timeline for How feasible is it to prove Kazhdan's property (T) by a computer?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 16, 2022 at 8:47 | history | edited | Martin Sleziak | CC BY-SA 4.0 |
http -> https (the question was bumped anyway)
|
| Oct 24, 2022 at 22:37 | answer | added | mahdi meisami | timeline score: 0 | |
| Jun 1, 2019 at 12:02 | answer | added | Uri Bader | timeline score: 55 | |
| May 22, 2014 at 2:44 | vote | accept | Narutaka OZAWA | ||
| May 21, 2014 at 16:30 | answer | added | Andreas Thom | timeline score: 61 | |
| Jan 30, 2014 at 14:48 | comment | added | Andreas Thom | The entire problem with this approach is that it is good to show that a group has property $(T)$, but it is not so good to show that it does not have property $(T)$. For fixed $n,m$, this can be done with semi-definite programming, but you have to check infinitely many pairs $(n,m)$. | |
| Jan 22, 2014 at 18:11 | comment | added | Narutaka OZAWA | I've just arrived at IHP to find it. sites.google.com/site/geowalks2014 | |
| Jan 21, 2014 at 20:42 | comment | added | Ian Agol | Just curious, does your result have an interpretation in terms of random walks? | |
| Jan 14, 2014 at 2:28 | comment | added | Timothy Chow | I see. I guess I was hoping that in specific cases, Ozawa might be able to bound these parameters. But it looks like that is not the case. | |
| Jan 13, 2014 at 23:33 | comment | added | François G. Dorais | 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). | |
| Jan 13, 2014 at 23:31 | comment | added | Narutaka OZAWA | @Timothy Chow: As HJRW observes, the problem is not decidable and so there is no a priori bound on $T=\bigcup_i\mathrm{supp}(\xi_i)$ (according to Speyer's answer below the other parameters shouldn't bother us). I have no intuition about the size of $T$. | |
| Jan 13, 2014 at 23:03 | comment | added | Timothy Chow | @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. | |
| Jan 13, 2014 at 20:07 | answer | added | David E Speyer | timeline score: 39 | |
| Jan 13, 2014 at 19:33 | comment | added | HJRW | @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). | |
| Jan 13, 2014 at 19:31 | comment | added | YCor | @HJRW: I don't have any other meaning in mind, but it does not mean there's none... I don't feel comfortable at understanding statements by projecting to the closest meaningful statement I can think of :) | |
| Jan 13, 2014 at 19:23 | comment | added | HJRW | @YvesCornulier - yes. What else would I mean? | |
| Jan 13, 2014 at 18:45 | comment | added | YCor | @HJRW: when you say "the class of fp groups with P is r.e.", do you mean "the class of finite presentations defining a group with P is r.e."? | |
| Jan 13, 2014 at 18:18 | comment | added | ACL | Just to check: If this equation has a solution, it can be found (by enumerating all elements of $\mathbb Z[\Gamma]$. If it does not, do you also claim that a computer can prove it? (In other words, are such systems of equations decidable?) | |
| Jan 13, 2014 at 15:43 | comment | added | John Wiltshire-Gordon | Very cool result! | |
| Jan 13, 2014 at 14:11 | comment | added | Narutaka OZAWA | @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. | |
| Jan 13, 2014 at 14:05 | comment | added | HJRW | I'd like to understand this better. Does it follow that the class of finitely presented groups with property (T) is recursively enumerable? (Note that its complement is certainly not recursively enumerable.) | |
| Jan 13, 2014 at 13:55 | history | asked | Narutaka OZAWA | CC BY-SA 3.0 |