Logic Seminar

Jean-Camille BirgetRutgers University
The word problem and the evaluation problem of the Thompson group and the Brin-Thompson group

Friday, November 5, 2021 - 2:45pm
Malott 206

We prove that the word problem of the Brin-Thompson group $n V$ over a finite generating set is ${\sf coNP}$-complete, for $n \ge 2$. The groups $n V$ are the first examples of finitely presented simple groups with non-easy word problem. Unless ${\sf NP} = {\sf coNP}$, $\,n V$ is not embeddable in a finitely presented group with polynomially bounded Dehn function.

The groups $n V$ were introduced by Matt Brin as an $n$-dimensional generalization of the Thompson group $V$, which itself was the first known example of an infinite, finitely presented, simple group. It was proved by Brin and others that the groups $n V$ form an infinite family of infinite, finitely presented, simple groups.

We also look at the evaluation problem for $V$ and $2V$. This problem reduces to the word problem, and in the worst case (for certain ``short'' inputs) it is equivalent to the word problem; although easy to prove, this is surprising. For ``long'' inputs, the evaluation problem for $V$ is deterministic context-free, and it is ${\sf P}$-complete for $2V$.