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

This question is about an issue left unresolved by Chad Groft's excellent question and John Stillwell's excellent answer of it. Since I find the possibility of an affirmative answer so tantalizing, I would like to pursue it further here.

For background, Rice's Theorem asserts essentially that no nontrivial question about computably enumerable sets is decidable. If We is the set enumerated by program e, then the theorem states:

Rice's Theorem. If A is a collection of computably enumerable sets and { e | We ∈ A } is decidable, then either A is empty or A contains all computably enumerable sets.

In short, one can decide essentially nothing about a program e, if the answer is to depend only on what the program computes rather than how it computes it.

The question here is about the extent to which a similar phenomenon holds for finitely presented groups, using the analogy between programs and finite group presentations:

  • a program e is like a finite group presentation p
  • the set We enumerated by e is like the group ⟨p⟩ presented by p.

According to this analogy, the analogue of Rice's theorem would state that any decidable collection of finitely presented groups (closed under isomorphism) should be either trivial or everything. John Stillwell pointed out in answer to Chad Groft's question that this is not true, because from a presentation p we can easily find a presentation of the abelianization of ⟨p⟩, by insisting that all generators commute, and many nontrivial questions are decidable about finitely presented abelian groups. Indeed, since the theory of abelian groups is a decidable theory, there will be many interesting questions about finitely presented abelian groups that are decidable from their presentations.

My question is whether this is the only obstacle.

Question. Does Rice's theorem hold for finitely presented groups modulo abelianization?

In other words, if A is a set of finitely presented groups (closed under isomorphism) and the corresponding set of presentations { p | ⟨p⟩ ∈ A } is decidable, then does A completely reduce to a question about the abelianizations of the groups, in the sense that there is a set B of abelian groups such that G ∈ A iff Ab(G) ∈ B?

Of course, in this case B consists exactly of the abelian groups in A. The question is equivalently asking whether A respects the equivalence of groups having isomorphic abelianizations. In other words, must it be that G ∈ A iff Ab(G) ∈ A? The question is asking whether every decidable set of finitely presented groups amounts actually to a decidable set of abelian groups, extended to all finitely presented groups just by saturating with respect to abelianization.

In particular, the set A should contain either none or all perfect groups.

An affirmative answer would seem to provide a thorough explanation of the pervasive undecidability phenomenon in group presentations. But perhaps this may simply be too much to hope for...

In any event, I suppose that there is an equivalence relation on finite group presentations, saying that p ≡ q just in case ⟨p⟩ and ⟨q⟩ have the same answer with repsect to any decidable question about finitely presented groups. The question above asks whether this equivalence relation is just Ab(⟨p⟩) = Ab(⟨q⟩). If this turns out not to be true, then what can be said about ≡?

share|improve this question
1  
Here is an idea. McKenzie et. al. developed a structure theory for certain classes of varieties for some notion of first order decidability. (Memory fails me on whether it regards equational logic only or not.) In particular, varieties with some property involving decidability could be decomposed as a varietal product of two or three different kinds. I believe Valeriote, Jeong, and Idziak are some of the authors with results that pertain to the question in a varietal context, and those results may pull over to your case. Gerhard "Ask Me About System Design" Paseman, 2010.02.26 –  Gerhard Paseman Feb 26 '10 at 18:24
    
Your question inspired this one: mathoverflow.net/questions/16565/… –  David Speyer Feb 27 '10 at 0:00
    
And here is still another follow-up question at mathoverflow.net/questions/17157. –  Joel David Hamkins Mar 5 '10 at 3:59
add comment

4 Answers 4

up vote 12 down vote accepted

The question "Is there a nonzero homomorphism from your group to $A_5$?" is decidable. (Just write down all ways of sending the generators of your group to $A_5$, and see whether they satisfy the required relations.) The same is true with $A_5$ replaced by any finite group. I don't see how to reduce this to questions about the abelianization.

share|improve this answer
1  
Doesn't this only work if your group has a solvable word problem? –  Andy Putman Feb 26 '10 at 18:56
    
Andy, I think this is decidable. And it turns into a full proof simply by finding a group that does not map homomorphically into A_5, but the abelianization does. For example, some crazy perfect group. –  Joel David Hamkins Feb 26 '10 at 20:00
2  
Maybe I am missing something dumb. Say my group is generated by $g_1$, $g_2$, ... $g_m$, with relations $r_1$, $r_2$, ..., $r_n$. For every one of the $60^n$ ways of sending each $g_i$ to an element of $A_5$, I check whether all the $r_i$ are sent to $e$. If so, I have a map to $A_5$. It is nonzero if and only if not all the $g_i$ are sent to $e$. –  David Speyer Feb 26 '10 at 20:01
    
Whoops! You're right, I just wasn't thinking... –  Andy Putman Feb 26 '10 at 20:03
    
I guess A_5 itself completes the answer, since it has a nontrivial homomorphism into A_5, but its abelianization is trivial, so has no nontrivial homomorphism into A_5. So this is a decidable property of groups that does not respect abelianization. –  Joel David Hamkins Feb 26 '10 at 21:28
add comment

You can compute the representation variety from $G$ into $M_n(\mathbb C)$ or your favorite algebraic group. This contains much more information than the abelianization.

Similarly, and slimilar to David Speyer's response, you can count the subgroups of index $n$: Index $n$ subgroups in $G$ correspond to transitive permutation representations on $n$ elements by the action of cosets. Many of these do not factor through the abelianization.

share|improve this answer
    
Thank you, I like this very much! Counting the subgroups of index n. –  Joel David Hamkins Feb 26 '10 at 21:38
    
Or, more generally than the second paragraph, you can compute the set of all homomorphisms to any finite set of finite groups. –  HJRW Feb 27 '10 at 17:04
add comment

There are quotients you can take other than the abelianization. For instance, most questions about finitely generated nilpotent groups are easily decidable. If you have a finite presentation for a group $G$, then you can easily produce a finite presentation for $G/\gamma_k(G)$, where $\gamma_k(G)$ is the kth term of the lower central series for $G$. This will be a $k$-step nilpotent group canonically associated to $G$ (often called the $k$-step nilpotent truncation of $G$). For $k=1$, this reduces to taking the abelianization.

Be warned : things are much worse if you take SOLVABLE quotients. For example, Kharlampovich has produced a finitely presented 3-step solvable group with an unsolvable word problem...

EDIT : For a wealth of information about obtaining information about groups from their nilpotent quotients, I recommend reading Ralph Fox's classic series of papers on the free differential calculus.

share|improve this answer
    
But maybe consideration of central series "amounts to" a question about abelian groups? (I don't have much insight here; it just seems like a plausible interpretation of the question.) –  Pete L. Clark Feb 26 '10 at 18:37
    
Andy, thanks very much for this answer! Pete, I had meant "amounts to" in the precise sense I explain in the question, and so Andy's answer may very well be the answer for which I'm looking. About my question at the end, what can be said with precision about the relation between that equivalence relation and nilpotent quotients? –  Joel David Hamkins Feb 26 '10 at 19:21
    
I don't have a good answer to the question at the end. My intuition is that it is false, but no other procedure comes to mind right now. True or false, I suspect that it is a very difficult question. –  Andy Putman Feb 26 '10 at 19:28
    
Your answer, if correct, shows that the relation is not the same as Ab(p) = Ab(q). My question was, given this, what does your answer tell us about the relationship between equiv and nilpotent quotients? I suppose, in other words, that every time someone provides a new decision procedure, it shows that equiv is smaller than we thought. We can continually ask: are we at equiv yet? In other words, after your answer, we could could ask: does every decidable question about finitely presented groups amount to a question about a specific term in the lower central series? –  Joel David Hamkins Feb 26 '10 at 19:47
    
That's right. David's answer above shows that we also get info about finite quotients. You might ask if finite and nilpotent quotients are all you can do, but I suspect that the answer is "no". –  Andy Putman Feb 26 '10 at 20:06
show 1 more comment

One more counterexample. Makanin's algorithm solves systems of equations and inequations over any non-abelian free group F. The statement

'$G=\langle x_1,\ldots, x_m\mid r_1,\ldots,r_n\rangle$ surjects a non-abelian free group'

is equivalent to the negation of the system of equations and inequations

$ (r_i=1 \mid \forall i) \Rightarrow ([x_i,x_j]=1\mid\forall i,j) $

over F, where $x_i$ are now interpreted as variables and $r_j$ are now interpreted as equations.

Therefore, the statement is decidable. On the other hand, $F$ surjects a non-abelian free group, but its abelianisation does not.

share|improve this answer
add comment

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.