Which finitely presented groups can be distinguished by decidable properties? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:01:09Z http://mathoverflow.net/feeds/question/17157 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17157/which-finitely-presented-groups-can-be-distinguished-by-decidable-properties Which finitely presented groups can be distinguished by decidable properties? Joel David Hamkins 2010-03-05T03:40:02Z 2010-03-06T17:30:18Z <p>This question continues the line of inquiry of <a href="http://mathoverflow.net/questions/15957" rel="nofollow">these</a> <a href="http://mathoverflow.net/questions/16532" rel="nofollow">three</a> <a href="http://mathoverflow.net/questions/16565" rel="nofollow">questions</a>.</p> <p><b>Question.</b> Which finitely presented groups can be distinguished by decidable properties?</p> <p>To be precise, let us say that &phi; is a <em>decidable</em> property of finitely presented groups, if there is a class A of finitely presented groups, closed under group isomorphisms, such that { p | &lang;p&rang; &isin; A } is decidable, where &lang;p&rang; denotes the group presented by p. That is, we insist that the decision procedure give the same answer for presentations leading to the same group up to isomorphism.</p> <p>One extreme case, perhaps unlikely, would be that any two non-isomorphic finitely presented groups can be distinguished by decidable properties, so that for any two finitely presented non-isomorphic groups &lang;p&rang; and &lang;q&rang;, there is a decidable property &phi; where &phi;(p) holds and &phi;(q) fails. That would be quite remarkable. </p> <p>If this is not the case, then there would be two finite group presentations p and q, such that the groups presented &lang;p&rang; and &lang;q&rang; are not isomorphic, but they have all the same decidable properties. This also would be remarkable. </p> <p>Which is the case?</p> <p>Another way to describe the question is in terms of the equivalence relation &equiv;, which I introduced in <a href="http://mathoverflow.net/questions/16532" rel="nofollow">my previous question</a>, where p &equiv; q if &phi;(p) and &phi;(q) have the same answer for any decidable property &phi; of finitely presented groups. This is precisely the equivalence relation of "having all the same decidable properties". Of course, this includes the group-isomorphism relation, and the current question is asking: What is this relation &equiv;? In particular, is &equiv; the same as the group isomorphism relation? If it is, then any two non-isomorphic finitely presented groups can be distinguished by decidable properties; if not, then there are two finitely presented non-isomorphic groups &lang;p&rang;, &lang;q&rang; having all the same decidable properties.</p> <p>Henry Wilton has emphasized several times that there are relatively few truly interesting decidable properties of finitely presented groups. This may very well be true. Nevertheless, the answers to the previous MO questions on this topic have provided at least <em>some</em> decidable properties, and my question here is asking the extent to which these properties are able to distinguish any two finitely presented groups.</p> <p>In particular, in these previous MO questions, <a href="http://mathoverflow.net/questions/15957" rel="nofollow">Chad Groft</a> inquired whether there were any nontrivial decidable properties of finitely presented groups. <a href="http://mathoverflow.net/questions/15957#16122" rel="nofollow">John Stillwell's answer</a> was that one could decide many questions about the abelianization of the group. In a <a href="http://mathoverflow.net/questions/16532" rel="nofollow">subsequent question</a>, I inquired whether all decidable properties were really about the abelianization, and <a href="http://mathoverflow.net/questions/15957#16122" rel="nofollow">David Speyer's answer</a> was that no, there were questions about other quotients, such as whether the group had a nontrivial homomorphism into a particular finite group, such as A<sub>5</sub>. In a <a href="http://mathoverflow.net/questions/16565" rel="nofollow">third question</a>, David generalized further and inquired whether all decidable properties depended on the profinitization, and the answer again was no (provided by David and Henry). So at least in these cases we have been increasingly able to separate groups by decidable properties.</p> <p>A generalization of the question would move beyond the decidable properties. For example, if we consider the computably enumerable (c.e.) properties, then we have quite a lot more ability to distinguish groups. A property is c.e. if there is a computable algorithm to determine the positive instances of &phi;(p), but without requiring the negative instances to ever converge on an answer. For example, the word problem for any finitely presented group, or indeed, for any computably presented group, is computably enumerable, since if a word is indeed trivial, we will eventually discover this. Using the same idea as David's answer to my question, it follows that the question of whether a finitely presented group &lang;p&rang; admits a nontrivial homomorphism into the integers Z, say, or many other groups, is computably enumerable. One may simply try out all possible maps of the generators. A generalization of this establishes:</p> <p><b>Theorem.</b> The question of whether one finitely presented group &lang;p&rang; maps homomorphically onto (or into) another &lang;q&rang; is computably enumerable.</p> <p>The proof is that given p and q, one can look for a map of the generators of p to the words of q, such that all relations of p are obeyed by the image in q, and such that all the generators of q are in the range of the resulting map. This is a c.e. property, since one can look for all possible candidates for the map of the generators of p into words of q, and check whether the relations are obeyed and the generators of q are in the range of the map and so on. If they are, eventually this will be observed, and at the point one can be confident that &lang;p&rang; maps onto &lang;q&rang;. More generally, is the isomorphism relation itself c.e.? It is surely computable from the halting problem 0', since we could ask 0' whether the kernel of the proposed map was trivial or not, and it would know the answer. </p> <ul> <li>Where does the isomorphism relation on finitely presented groups fit into the hierarchy of Turing degrees? Is it c.e.? Is it Turing equivalent to the Halting problem?</li> </ul> <p>Once one moves to the c.e. properties, it is similarly natural to move beyond the finitely presented groups to the computably presented groups (those having a computable presentation, not necessarily finitely generated). In this context, the proof above no longer works, and the natural generalization of the question asks:</p> <ul> <li>Which computably presented groups are distinguished by c.e. properties?</li> </ul> <p>The isomorphism relation on finitely generated computably presented groups (given the presentations) seems to be computable from the halting problem for the same reason as in the proof above, but now one doesn't know at a finite stage that the proposed map of the generators will definitely work, since one must still check all the relations-yet-to-be-enumerated. But 0' knows the answer, so we get it computably in 0'. In the infinitely generated case, however, things are more complicated.</p> http://mathoverflow.net/questions/17157/which-finitely-presented-groups-can-be-distinguished-by-decidable-properties/17161#17161 Answer by Bjorn Poonen for Which finitely presented groups can be distinguished by decidable properties? Bjorn Poonen 2010-03-05T04:51:31Z 2010-03-06T17:30:18Z <blockquote> <p>The isomorphism relation for finitely presented groups is c.e., and in fact is Turing equivalent to the halting problem. </p> </blockquote> <p><strong>Proof:</strong> To check whether two finitely presented groups $G$ and $H$ are isomorphic, search for data that might describe maps $G \to H$ and $H \to G$ and for words that show that it is a consequence of the relations that the composition in either order maps each generator to itself, and verify that the relations of $G$ map to $1$ in $H$ and vice versa so that the maps are well-defined and that the remaining data shows that they are inverse isomorphisms. Thus the isomorphism relation is c.e. It is also no <em>easier</em> than the halting problem, because an algorithm even for deciding whether a finitely presented group is trivial could be used to solve the halting problem. (That is how it is known that triviality is an undecidable property, by reductions passing through the word problem along the way.) $\square$</p> <p><strong>EDIT:</strong> As for your "main question" asking whether decidable properties can distinguish every pair of non-isomorphic finitely presented groups, I'll prove the following negative result:</p> <blockquote> <p>There is no c.e. set $\mathcal{F}$ of decidable properties such that any two non-isomorphic finitely presented groups can be distinguished by some $\phi \in \mathcal{F}$.</p> </blockquote> <p>(Call a set $\mathcal{F}$ of decidable properties <em>c.e.</em> if there is a Turing machine that produces a sequence of algorithms, each of which is guaranteed to compute a decidable property, such that these decidable properties are exactly the ones in $\mathcal{F}$.)</p> <p><strong>Proof:</strong> Suppose that $\mathcal{F}$ exists. Then we could decide whether an arbitrary finitely presented group $G$ is trivial as follows: By day, search for an isomorphism between $G$ and <code>$\{1\}$</code> (this search is possible since the isomorphism relation is c.e.) By night, search for a decidable property $\phi \in \mathcal{F}$ such that $\phi$ distinguishes $G$ and <code>$\{1\}$</code>. If $\mathcal{F}$ does what it claims to, then one of these processes will terminate and tell you whether <code>$G \simeq \{1\}$</code>. But triviality is known to be an undecidable property. $\square$</p> <p>This leaves open the question of whether there is a non-c.e. $\mathcal{F}$ that does the job, but even if there were one, it wouldn't be of much use from the practical point of view!</p>