Timeline for For which groups is (non-)left orderability decidable?
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 16, 2020 at 3:40 | history | edited | YCor |
edited tags
|
|
| May 24, 2017 at 10:14 | comment | added | HJRW | @YCor -- well that's correct. But of course the abstract knowledge that the word problem is solvable isn't enough; one needs to have access to the solution to the word problem. | |
| May 24, 2017 at 9:15 | comment | added | YCor | @HJRW Before Benjamin's comment I expected that the input was just a finite presentation and in case the word problem is solvable, the output is "NO" if the group is non-left-orderable. | |
| May 24, 2017 at 8:24 | comment | added | HJRW | @YCor, if you look up the asker, you'll see that he knows a lot about algorithms. Also, if you read the question carefully, you'll see that the given input is not a "group", but a "finitely presented group". As you know, a "finitely presented group" (as distinct from a finitely presentable group) is a group equipped with a finite presentation, which is clearly a perfectly acceptable input for an algorithm. I'm puzzled that you find it difficult to figure out what the question is asking for. It was quite clear to me. | |
| May 23, 2017 at 22:22 | comment | added | YCor | @HJRW I'm somewhat not convinced that I should be satisfied by phrasing of questions which (1) give a strong suspicion that the person who asked the question does not know exactly what (s)he's asking, namely is not aware that an algorithmic question involves an input, and that "a group" is not an acceptable input (2) given my best efforts, stay several potential interpretations which don't make the question senseless of trivial, and for which other users like Benjamin provide an interpretation distinct from any I could guess. | |
| May 23, 2017 at 19:46 | answer | added | HJRW | timeline score: 2 | |
| May 23, 2017 at 19:27 | comment | added | HJRW | @DerekHolt -- sure: the class of groups with solvable word problem is such a class! | |
| May 23, 2017 at 11:10 | comment | added | Derek Holt | I can imagine that there could be a class of groups for which you prove that they had solvable word problem, but for which you did not know an algorithm (or perhaps even you could prove that there was no such algorithm) to construct the algorithm that solved the word problem. | |
| May 23, 2017 at 10:41 | comment | added | HJRW | @YCor, the question is phrased in a way that is pretty standard (if slightly non-rigorous) when talking about these questions. Benjaming Steinberg already gave the way in which it is usually interpreted. In most practical situations, one is actually working in a class of finitely presented groups in which the word problem is uniformly decidable, at which point one can interpret it as asking for a decision procedure for presentations. | |
| May 23, 2017 at 8:59 | comment | added | YCor | Something more or less lurking behind Ian's argument is the following classical fact: a group is non-left-orderable iff there exists $k,\ell\ge 1$ and elements $x_1,\dots,x_k\neq 1$ and all $x_1\in\{x_1,x_1^{-1}\}\dots$, $x_k\in\{x_k,x_k^{-1}\}$ there exist $i_1,\dots,i_\ell\in\{1,\dots,k\}$ such that $y_{i_1}y_{i_2}\dots y_{i_\ell}=1$. So indeed if the solution to WP is part of the input then one can compute until we find such "$(k,\ell)$-torsion" and detect non-left-orderability. | |
| May 23, 2017 at 7:25 | comment | added | YCor | @HJRW I don't prefer anything, I'm trying to obtain from the OP a clarification, which is not made so far. | |
| May 23, 2017 at 5:12 | comment | added | HJRW | @YCor, if you prefer to work with presentations, you can restrict to some class of groups with uniformly solvable word problem. | |
| May 22, 2017 at 23:21 | comment | added | Benjamin Steinberg | @YCor, a group can be given by a Turing machine solving it's word problem. The generators are the input alphabet of the Turing machine and you get a recursive presentation by saying all accepted words are 1. If you want to use the decidability of the word problem the Turing machine for the word problem should be part of the input. | |
| May 22, 2017 at 22:30 | comment | added | YCor | I would have expected that the input is a group presentation of a group $G$, the output is Yes/No, in such a way if the word problem is solvable in $G$, then the program stops and outputs Yes/No according to whether $G$ is left-orderable. | |
| May 22, 2017 at 22:26 | comment | added | YCor | @BenjaminSteinberg I'm not sure what you mean. Solution of word problem for what? Where is the group? And what's the output then? | |
| May 22, 2017 at 22:15 | comment | added | Benjamin Steinberg | For the question to make sense presumably the solution to the word problem is the input. | |
| May 22, 2017 at 21:16 | comment | added | YCor | The question is unclear. What's the input? Starting with "let $G$ be a group" sounds like $G$ is fixed. There should be something like some presentiation is the input...! The title even sounds like it's senseless. For a given group, the veracity of left-orderability is a Boolean variable. | |
| May 22, 2017 at 20:55 | comment | added | Benjamin Steinberg | @IanAgol, I agree with the compactness argument. | |
| May 22, 2017 at 20:41 | comment | added | Ian Agol | @BenjaminSteinberg: Going from an ordering on balls to an ordering of the group is a compactness argument: If the R -ball is orderable for all R, then we can find an ordering on the R-ball for all R which restricts to the chosen ordering on the R-1-ball, since there are only finitely many orderings on each R ball for every R. This is not co-recursive, as you say, since we don't have a bound on how big the bad R is. But the hypothesis that the group is not orderable guarantees that some bad R exists, hence is recursive modulo an oracle that tells you the group is not orderable. | |
| May 22, 2017 at 20:08 | comment | added | Benjamin Steinberg | @IanAgol, I don't understand the comment. First of all how do you know that if each ball is orderable then you can find a consistent order for all balls? And granting that, you still seem to be arguing orderability is co-re unless you can bound how big the bad R is. | |
| May 22, 2017 at 18:56 | comment | added | Ian Agol | Given your assumptions, then there is an algorithm. Solvable word problem means that one may construct the Cayley graph to some radius. If there is a total order on the ball of radius R compatible with all multiplications that land in that ball, for all R, then the group is orderable. So by the contrapositive, if it is not orderable, then there is some R such that any ordering on a ball of radius R in the Cayley graph is inconsistent. The difficult thing is to show that groups (including 3-manifold groups) are orderable. Without the caveat that $G$ is non-orderable, then this is open. | |
| May 22, 2017 at 18:43 | history | asked | Neil Hoffman | CC BY-SA 3.0 |