Finiteness of the Burnside Group

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.

• What is the input? the pair $(n,d)$? the triple $(n,d,k)$?
– YCor
Commented Aug 20, 2015 at 11:07
• The triple $(n,d,k)$. Commented Aug 20, 2015 at 11:09
• 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.
– YCor
Commented Aug 20, 2015 at 11:09
• 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.
– YCor
Commented Aug 20, 2015 at 11:13
• 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? Commented Aug 20, 2015 at 20:38

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.)