Timeline for Quantitative word problem for 3-manifold groups
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2021 at 18:06 | comment | added | Ian Agol | For finitely generated subgroups of $GL_N(\mathbb{Z})$, I think one can improve the bound from $O(n^2)$ to $O(n\log^2n)$. The point is that for a word of length $n$, you can divide it into two subwords of length $\leq \lceil n/2\rceil$, which have length (in bits) bounded by $C n/2$. Multiplying these takes time $O(n/2 \log(n/2))$. en.wikipedia.org/wiki/… By induction, this gives $O(n \log^2n)$ I think. | |
| Dec 20, 2020 at 23:43 | comment | added | Moishe Kohan | @dodd: Afaik, linearity is an open problem (for graph-manifolds without metrics of nonpositive curvature). As for Dehn function, it provides only an upper bound on complexity of the WP, as I explain, one can do better. | |
| Dec 20, 2020 at 23:36 | comment | added | markvs | All fundamental groups of closed 3-manifolds are linear, so they have word problem in logspace. Sol has exponential Dehn function, Nil has Dehn function $\sim n^3$. | |
| Dec 20, 2020 at 19:41 | history | edited | Moishe Kohan | CC BY-SA 4.0 |
added 188 characters in body
|
| Dec 20, 2020 at 19:37 | comment | added | Ian Agol | Good point (and clearly stated in your answer). | |
| Dec 20, 2020 at 19:32 | comment | added | Moishe Kohan | @IanAgol: Graph-manifold groups are automatic (apart from Nil and Sol), hence, have quadratic Dehn function for this reason. | |
| Dec 20, 2020 at 19:15 | comment | added | Ian Agol | Some graph manifolds virtually fiber, and hence their fundamental groups are (virtually) the subgroup of a mapping class group, which is automatic. So they also have a quadratic time solution to the word problem. doi.org/10.2307/2118637 But I think that there are graph manifolds that are neither cubulated nor virtually fibered. | |
| Dec 20, 2020 at 16:23 | history | edited | Moishe Kohan | CC BY-SA 4.0 |
added 118 characters in body
|
| Dec 19, 2020 at 22:40 | comment | added | Moishe Kohan | @YCor: Right, I was careless. I will correct the answer once I am back to my computer. | |
| Dec 19, 2020 at 7:07 | comment | added | YCor | If you multiply $n$ bounded matrices in $SL(3,Z)$ you get matrices of exponential size, i.e., exponents have $\sim n$ digits. The multiplication of a single such matrix with a single bounded matrix takes time $\sim n$. So it looks like the total time is likely to be $O(n^2)$ rather than $O(n)$. | |
| Dec 19, 2020 at 3:29 | vote | accept | Ben Cooper | ||
| Dec 19, 2020 at 3:18 | comment | added | Ben Cooper | Thank you, this is helpful | |
| Dec 19, 2020 at 0:49 | history | answered | Moishe Kohan | CC BY-SA 4.0 |