The unsolvability of efficiency for groups

Publication date 12 April 2000

Published in Southeast Asian Bulletin of Mathematics (Search for Journal in Brave)

algorithmically undecidable properties Cockroft properties efficiency finitely presented groups numbers of generators presentations spherical pictures

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Cancellation theory of groups; application of van Kampen diagrams (20F06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Review text

What is the ``smallest presentation of a given finitely presented group \(G\)? The notion of efficiency grew out of attempts to answer this question. If \(\langle x\mid r\rangle\) is a presentation for \(G\), then \(|x|-|r|\leq\text{rk}(H_1(G))-d(H_2(G))\) (here \(\text{rk}(-)\) and \(d(-)\) denote the torsion-free rank and the minimal number of generators, respectively). A group \(G\) is termed efficient if this bound is attained for some presentation. It is known that not all finitely presented groups are efficient. The main point of the paper is to show that efficiency is an algorithmically undecidable property for finitely presented groups (although it is not a Markov property). The elegant proof uses a translation of the efficiency property into a 2-dimensional topological setting (Cockroft properties) and spherical pictures (or diagrams).

Recommendations

Cited in

(4)

This page was built for publication: The unsolvability of efficiency for groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1307050)