# Computing commutator length is hard

@article{Heuer2020ComputingCL, title={Computing commutator length is hard}, author={Nicolaus Heuer}, journal={arXiv: Group Theory}, year={2020} }

The commutator length $cl_G(g)$ of an element $g \in [G,G]$ in the commutator subgroup of a group $G$ is the least number of commutators needed to express $g$ as their product.
If $G$ is a non-abelian free groups, then given an integer $n \in \mathbb{N}$ and an element $g \in [G,G]$ the decision problem which determines if $cl_G(g) \leq n$ is NP-complete. Thus, unless P=NP, there is no algorithm that computes $cl_G(g)$ in polynomial time in terms of $|g|$, the wordlength of $g$. This statement… Expand

#### One Citation

Stable commutator length in right-angled Artin and Coxeter groups.

- Mathematics
- 2020

We establish a spectral gap for stable commutator length (scl) of integral chains in right-angled Artin groups (RAAGs). We show that this gap is not uniform, i.e. there are RAAGs and integral chains… Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

Gaps in scl for Amalgamated Free Products and RAAGs

- Mathematics
- Geometric and Functional Analysis
- 2019

AbstractWe develop a new criterion to tell if a group G has the maximal gap of 1/2 in stable commutator length (scl). For amalgamated free products $${G = A \star_C B}$$G=A⋆CB we show that every… Expand

Computing commutator length in free groups

- Mathematics
- 2000

We study commutator length in free groups. (By a commutator lengthcl(g) of an element g in a derived subgroup G′ of a group G we mean the least natural number k such that g is a product of k… Expand

Spectral gap of scl in graphs of groups and $3$-manifolds

- Mathematics
- 2019

The stable commutator length scl_G(g) of an element g in a group G is an invariant for group elements sensitive to the geometry and dynamics of G.
For any group G acting on a tree, we prove a sharp… Expand

Stable commutator length is rational in free groups

- Mathematics
- 2008

For any group, there is a natural (pseudo-)norm on the vector space B^H_1 of real homogenized (group) 1 -boundaries, called the stable commutator length norm. This norm is closely related to, and can… Expand

The genus problem for one-relator products of locally indicable groups

- Mathematics
- 1991

A one-relator product of groups A and B is a natural generalisation of a onerelator group, and under suitable conditions (for example if A and B are locally indicable) one can extend much of the… Expand

On the complexity of sails

- Mathematics
- 2012

This paper analyses stable commutator length in groups Z^r * Z^s. We bound scl from above in terms of the reduced wordlength (sharply in the limit) and from below in terms of the answer to an… Expand

Using surfaces to solve equations in free groups

- Mathematics
- 1981

BECAUSE THERE exist groups like those described in [l], it is futile to attempt to study the solution of equations in an arbitrary group. It is reasonable, however, to do so for free groups. Results… Expand

The full spectrum of scl on recursively presented groups

- Mathematics
- 2019

We show that the set $SCL^{rp}$ of stable commutator lengths on recursively presented groups equals the set of non-negative right-computable numbers. Hence all non-negative algebraic or computable… Expand

The spectrum of simplicial volume

- Mathematics
- 2019

New constructions in group homology allow us to manufacture high-dimensional manifolds with controlled simplicial volume. We prove that for every dimension bigger than 3 the set of simplicial volumes… Expand

Computers and Intractability: A Guide to the Theory of NP-Completeness

- Computer Science, Mathematics
- 1978

Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge… Expand