4
$\begingroup$

This is something I discussed with Andrezj Zuk, but we didn't arrive to any conclusions. Let $B(d,n)$ be the Burnside group on $d$ generators of exponent $n$. Is there an algorithm to determined whether $B(d,b)$ is at least of size $k$ (or infinite)? If yes, then in theory it is possible to use the bounds for the restricted Burnside problem to determine whether $B(d,n)$ is finite. So in such case is it at all feasible computationally (the bounds of the RBP are of course huge)?

Edit: Following Yves' answer. I am not interested in the existence of an algorithm that we can only describe if we know whether $B(d,n)$ is finite. I would like an algorithm that takes the infinite presentation of $B(d,n)$ and say whether it is bigger than $k$ or infinite or something in that spirit. So an algorithm that if we'll have a fast enough computer, will determine whether $B(2,5)$ is finite.

$\endgroup$
8
  • $\begingroup$ What is the input? the pair $(n,d)$? the triple $(n,d,k)$? $\endgroup$
    – YCor
    Commented Aug 20, 2015 at 11:07
  • $\begingroup$ The triple $(n,d,k)$. $\endgroup$ Commented Aug 20, 2015 at 11:09
  • 4
    $\begingroup$ If $d$ is fixed, there is in principle an algorithm whose input is $n$ and the output is the cardinal of $B(d,n)$. This is just because this sequence is eventually infinite, hence computable, but this does not say what the sequence (nor the algorithm) is. $\endgroup$
    – YCor
    Commented Aug 20, 2015 at 11:09
  • 1
    $\begingroup$ Btw, as you probably observed, the set of $(n,d)$ such that $B(n,d)$ has cardinal $\le k$ is obviously recursively enumerable (with an explicit algorithm). So whether we can test the other inequality is equivalent to determining whether $(n,d)\mapsto |B(n,d)|$ is computable. $\endgroup$
    – YCor
    Commented Aug 20, 2015 at 11:13
  • $\begingroup$ Yves I am not sure I understand your claim. Isn't what you are saying is exactly what I am asking? If I understand correctly, you claim that for each $k$ you can check whether the size of $B(d,n)$ is k. Why? $\endgroup$ Commented Aug 20, 2015 at 20:38

1 Answer 1

6
$\begingroup$

Let $X$ be the set of $(d,n)\in\mathbf{N}_{\ge 2}\times\mathbf{N}_{\ge 2}$ such that $B(d,n)$ is finite, and $X_d=\{n\in\mathbf{N}_{\ge 2}:(d,n)\in X\}$ the set of $n$ such that $B(d,n)$ is finite (by the infiniteness of $B(2,n)$ for large $n$, due to Adian and possibly others in the case of powers of 2). Then $X_d\supset X_{d+1}$ for all $d$, and $X_d$ is finite for all $d\ge 2$. Hence $X_d$ is eventually independent of $d$, and $X$ is thus a recursive subset of $\mathbf{N}^2$. Hence its complement, the set of $(d,n)$ such that $B(d,n)$ is infinite, is recursive.

Also, for given $k<\infty$, the set of $(d,n)$ such that $B(d,n)$ has cardinal $k$ is finite (obvious, since its cardinal is $\ge n^d\ge\max(n,2^d)$), hence recursive.

Of course this gives no information: it just shows that the question is not whether there is an algorithm, but whether we can describe a reasonable one (of course an efficient one is a bit hopeless since it would answer well-known open question, such as the question whether $B(2,5)$ is infinite).


Edit: Related fact: there is an (explicit, but ineffective) algorithm computing the cardinal of the restricted Burnside group as a function of $(d,n)$: enumerate finite groups of exponent dividing $n$, and thus enumerate all homomorphism to those groups, and thus enumerate presentations of their kernels $K$. At some point, the kernel is aperiodic (i.e., has no nontrivial finite quotient), and we have to detect this: to do so, enumerate finite simple groups $S$ of exponent dividing $n$: there are finitely many and a list can be given (computably) in terms of $n$. We have to be careful because $K$ is only recursively presented, but the fact that there is no nontrivial homomorphism $K\to S$ is equivalent to the fact that some truncated presentation $K'$ of $K$ has no nontrivial homomorphism to $S$, so this will be eventually detected.

Now to go back to the initial question: I at least have: if the Burnside groups have uniformly solvable word problem (i.e. the input is $(d,n,w)$ with $w$ a group word in $d$ letters and the output is YES/NO according to whether $w\equiv 1$ in $B(d,n)$) then here's an explicit algorithm for infiniteness of $B(d,n)$: enumerate group words in $d$ and by the above word problem assumption, we can compute when they are distinct and thus compute an increasing sequence whose limit is the cardinal of $B(d,n)$. If $B(d,n)$ is infinite then this number will pass over the cardinal of the restricted $BR(d,n)$ which is also computable by the previous paragraph, so this will be detected; if $B(d,n)$ is finite this is detected also by standard means (enumerate all relations in $B(d,n)$ and stop if for some $k$ all elements of the $k$-ball belong to the $(k-1)$-ball.)

$\endgroup$
1
  • $\begingroup$ I think I now understand your answer. You claim that there is an algorithm, but to find it we need to know the answer. So indeed it is not useful in any sense. It would probably be better to ask whether we can describe an algorithm rather than is there an algorithm. $\endgroup$ Commented Aug 22, 2015 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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