2
$\begingroup$

Please forgive me if this question is ill-formed. I don't know much about decidability.

Some Background:

There are problems in combinatorial group theory that are undecidable, such as the word problem.

I don't know of any results either way in terms of the decidability of properties of sets of groups.

One property I'm working on for some finitely presented groups is the Tits Alternative (although I'm not looking at decidability).

Definition 1: A class $\mathcal{G}$ of groups satisfies the Tits alternative if for any $G$ in $\mathcal{G}$ either $G$ has a free, non-abelian subgroup or $G$ has a solvable subgroup of finite index.

Example 1: The class of finitely generated linear groups satisfies the Tits alternative.

The Question:

Is the Tits Alternative decidable for any given (suitably defined$^\dagger$) class $\mathcal{G}$ of groups?

Thoughts:

I'm not sure if the question even makes sense. There might be some technicalities I am unaware of that render it nonsense.

One thing I suspect is that

A hunch: If the problem of whether a given group is solvable is undecidable, then the Tits Alternative is undecidable.

This appears to be obvious but I'm not sure how to prove it.

(Edit: The hunch is wrong. See YCor's comment below.)


I doubt that this question has an answer yet. After a brief search through the literature, I couldn't find anything.

Perhaps I'm asking for too much then . . .

Nevertheless, I'm curious.

It's certainly not a question I think I could answer myself. It's outside the scope of my research.

Let me know what you think :)


$\dagger$ See the first comment for why I added this.

$\endgroup$
  • 1
    $\begingroup$ You would have to specify how you are describing a class of groups. For something to be reasonably said to be undecidable, you need to be able to feed the question into a Turing machine. So you need a finite description of the class of groups. $\endgroup$ – Matt Samuel Nov 11 '18 at 2:28
  • $\begingroup$ I see. Thank you, @MattSamuel. Does that mean my question is complete nonsense or can it be salvaged? $\endgroup$ – Shaun Nov 11 '18 at 2:35
  • 1
    $\begingroup$ Well, it's actually not too hard to fix. You can encode the definition as a ZFC formula. If it's possible to prove in ZFC that the groups described by the formula satisfy the Tits alternative, then there is an extremely inefficient Turing machine that will find this proof, or a proof of the negation if it's false and that can be proven in ZFC. Phrased in this generality, I'm 99.9999999999% certain it's undecidable. $\endgroup$ – Matt Samuel Nov 11 '18 at 2:43
  • 4
    $\begingroup$ A conjecture is meant to relate to a precise statement. Here, it's an expectation, or even rather an intuition. Anyway, the most usual way to input groups is to input presentations. Now consider the class of groups finitely presented groups $G\ast G$, i.e., we input a finite presentation (of a group $G$) and mean this to refer $G\ast G$. So the class of groups we can input is the class of $G\ast G$ for $G$ finitely presented groups. Solvability is undecidable, essentially because the triviality problem is undecidable. But all the groups $G\ast G$ satisfy the Tits alternative. $\endgroup$ – YCor Nov 11 '18 at 3:04
2
$\begingroup$

It is proved here that it is decidable whether a finitely generated linear group is solvable by finite, so the Tits alternative is decidable for this class of groups.

I think there is some underlying assumption here that the linear group is defined over a field in which exact computation is possible, such as a number field or a function field.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.