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

This question continues the line of inquiry of these three questions.

Question. Which finitely presented groups can be distinguished by decidable properties?

To be precise, let us say that φ is a decidable property of finitely presented groups, if there is a class A of finitely presented groups, closed under group isomorphisms, such that { p | ⟨p⟩ ∈ A } is decidable, where ⟨p⟩ 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.

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 ⟨p⟩ and ⟨q⟩, there is a decidable property φ where φ(p) holds and φ(q) fails. That would be quite remarkable.

If this is not the case, then there would be two finite group presentations p and q, such that the groups presented ⟨p⟩ and ⟨q⟩ are not isomorphic, but they have all the same decidable properties. This also would be remarkable.

Which is the case?

Another way to describe the question is in terms of the equivalence relation ≡, which I introduced in my previous question, where p ≡ q if φ(p) and φ(q) have the same answer for any decidable property φ 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 ≡? In particular, is ≡ 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 ⟨p⟩, ⟨q⟩ having all the same decidable properties.

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 some decidable properties, and my question here is asking the extent to which these properties are able to distinguish any two finitely presented groups.

In particular, in these previous MO questions, Chad Groft inquired whether there were any nontrivial decidable properties of finitely presented groups. John Stillwell's answer was that one could decide many questions about the abelianization of the group. In a subsequent question, I inquired whether all decidable properties were really about the abelianization, and David Speyer's answer 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 A5. In a third question, 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.

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 φ(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 ⟨p⟩ 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:

Theorem. The question of whether one finitely presented group ⟨p⟩ maps homomorphically onto (or into) another ⟨q⟩ is computably enumerable.

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 ⟨p⟩ maps onto ⟨q⟩. 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.

  • 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?

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:

  • Which computably presented groups are distinguished by c.e. properties?

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.

share|improve this question
1  
No one has yet given a property which distinguishes Higman's group from the trivial group. terrytao.wordpress.com/2008/10/06/… –  David Speyer Mar 5 '10 at 12:03

1 Answer 1

The isomorphism relation for finitely presented groups is c.e., and in fact is Turing equivalent to the halting problem.

Proof: 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 easier 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$

EDIT: 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:

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

(Call a set $\mathcal{F}$ of decidable properties c.e. 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}$.)

Proof: 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 $\{1\}$ (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 $\{1\}$. If $\mathcal{F}$ does what it claims to, then one of these processes will terminate and tell you whether $G \simeq \{1\}$. But triviality is known to be an undecidable property. $\square$

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!

share|improve this answer
    
Very good! Thanks, Bjorn. I actually had this argument in an earlier version of my question, which I did not post, but I became suspicious of it, because I had a nagging thought that one really had to check that the kernel was trivial (which does not seem directly to be c.e.), and I had changed my theorem just to state the onto homomorphisms. But the way that you say it, it seems entirely fine! Please proceed next to my main question: can you display those two group presentations you think exist? –  Joel David Hamkins Mar 5 '10 at 5:01
3  
The classical way to show that two finitely presented groups are isomorphic is to use Tietze transformations, which are guaranteed to transform the presentation of G into the presentation of H if G and H are isomorphic. This, similarly, shows that the isomorphism relation is c.e. –  John Stillwell Mar 5 '10 at 5:05
    
Also, this argument does not seem to generalize to computably presented groups, even when they are finitely generated. Here, I guess the answer would be that it is Turing equivalent to 0', but not itself c.e. (It can't be c.e., since later relations may come in, destroying what you thought was happening.) –  Joel David Hamkins Mar 5 '10 at 5:07
    
The algorithm you give for the c.e. case is impractical too since there is no time for sleep! :) –  François G. Dorais Mar 6 '10 at 18:11
    
Bjorn, you new argument is excllent. And the same proof generalizes to rule out c.e. sets of c.e. properties, rather than just decidable properties. What you are observing is that the isomorphism relation is c.e., but not not decidable, so the complementary relation cannot be c.e. –  Joel David Hamkins Mar 6 '10 at 18:40

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.