On the complexity of sails

Lukas Brantner

Vol. 258 (2012), No. 1, 1–30

DOI: 10.2140/pjm.2012.258.1

Abstract

This paper analyses stable commutator length (scl) in groups Z^r ∗ Z^s. We bound it from above in terms of the reduced word length (sharply in the limit) and from below in terms of the answer to an associated subset-sum problem. Combining both estimates, we prove that as m tends to infinity, words of reduced length m generically have scl arbitrarily close to m − 1.

We then show that, unless P = NP, there is no polynomial time algorithm to compute scl of efficiently encoded words in F₂.

All these results are obtained by exploiting the fundamental connection between scl and the geometry of certain rational polyhedra. Their extremal rays have been classified concisely and completely. However, we prove that a similar classification for extremal points is impossible in a very strong sense.

Keywords

stable commutator length, scl, complexity theory, sails, P = NP, generic behaviour, polyhedra, Calegari’s algorithm, bounded cohomology, NP-hard, NP-complete, computational geometry

Mathematical Subject Classification 2010

Primary: 20F12, 20F65, 52B15, 52C45, 57M07

Milestones

Received: 28 October 2011

Revised: 8 December 2011

Accepted: 14 December 2011

Published: 21 July 2012