3
$\begingroup$

I am once again asking more software-related questions, but I am happy to learn a general answer as well. I'm curious about how the is_infinite function works in SageMath (or in GAP). Does it simply check whether we input something that is already known to be infinite or not? Or does it print "infinite" after a specific number of elements? Or does it actually check if the group is infinite? I assume it's not a numerical answer to check if the group is infinite or not since the program can't count until infinity. So, I'm wondering what the method is for checking if a group is infinite or not (in SageMath and in general). Thank you for your answer.

$\endgroup$
7
  • 1
    $\begingroup$ See for example here. I suppose that the Todd-Coxeter coset enumeration procedure is used, to show that the group is finite (given a presentation). There are many posts saying that the size function did not work for an infinite group, see for example this post. $\endgroup$ Commented Jul 10, 2023 at 8:12
  • 1
    $\begingroup$ @DietrichBurde The Todd-Coxeter procedure can only prove that a group (or more generally the index of a given subgroup) is finite. It cannot prove that a group is infinite - it runs forever when given an infinite group. $\endgroup$
    – Derek Holt
    Commented Jul 10, 2023 at 8:15
  • 1
    $\begingroup$ @DerekHolt Yes, this is what I meant by saying "that the group is finite". $\endgroup$ Commented Jul 10, 2023 at 8:15
  • 3
    $\begingroup$ There are a few easy tests for infiniteness, which would be carried out by GAP of SageMath, such as does the group have infinite abelianization. If the tests fail, and quick attempts to prove finiteness also fail, then these functions return no answer. They should never return a wrong answer. If they do then there is a bug in the code! $\endgroup$
    – Derek Holt
    Commented Jul 10, 2023 at 8:18
  • 2
    $\begingroup$ I would add to the comment of @ahulpke that, unlike the situation for finitely presented groups, where finiteness is undecidable in general, the finiteness of a matrix group in characteristic zero is decidable by an algorithm of Detinko, Flannery and O'Brien, at least over fields that allow exact computation, such as number fields and function fields. $\endgroup$
    – Derek Holt
    Commented Jul 10, 2023 at 13:08

0

You must log in to answer this question.

Browse other questions tagged .