Vol. 258, No. 1, 2012

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 314: 1
Vol. 313: 1  2
Vol. 312: 1  2
Vol. 311: 1  2
Vol. 310: 1  2
Vol. 309: 1  2
Vol. 308: 1  2
Vol. 307: 1  2
Online Archive
Volume:
Issue:
     
The Journal
Subscriptions
Editorial Board
Officers
Contacts
 
Submission Guidelines
Submission Form
Policies for Authors
 
ISSN: 1945-5844 (e-only)
ISSN: 0030-8730 (print)
Special Issues
Author Index
To Appear
 
Other MSP Journals
On the complexity of sails

Lukas Brantner

Appendix: Frederick Manners

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

This paper analyses stable commutator length (scl) in groups Zr Zs. 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 1
4m 1.

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

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
Authors
Lukas Brantner
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
Wilberforce Road
Cambridge
CB3 0WB
United Kingdom
Frederick Manners
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
Wilberforce Road
Cambridge
CB3 0WB
United Kingdom