# Collapsible group words

What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$?

For example, $f(2)=4$, with the commutator $[x_1,x_2]=x_1 x_2 x_1^{-1} x_2^{-1}$ attaining the bound.

For any $m,n \ge 1$, the construction $w_{m+n}(\vec{x},\vec{y}):=[w_m(\vec{x}),w_n(\vec{y})]$ shows that $f(m+n) \le 2 f(m) + 2 f(n)$.

Is $f(1),f(2),\ldots$ the same as sequence A073121: $$1,4,10,16,28,40,52,64,88,112,136,\ldots ?$$

Motivation: Beating the iterated commutator construction would improve the best known bounds in size of the smallest group not satisfying an identity.

-
Erik Demaine, in his paper "Puzzles, Art, and Magic with Algorithms" hints at a preprint "Picture-hanging puzzles" which might have a better (?) solution. A google search doesn't turn up the preprint. Here is another link, giving your solution: mathpuzzle.com/hangingpicture.htm –  Sam Nead Feb 15 '10 at 17:00
A question. Can one prove that such a word w_n must lie in the nth stage of the lower central series of the free group? Ten minutes of thinking yielded neither a proof nor a counterexample. –  Andy Putman Feb 15 '10 at 22:46
Andy: Proposition 2 of Johnson's "Towards a characterization of smooth braids" gives a positive answer to your question. I have not yet understood his proof. –  Sam Nead Feb 17 '10 at 14:15

In an unpublished manuscript "Picture-Hanging Puzzles" by Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, and Joseph S. B. Mitchell, we prove the $O(n^2)$ upper bound that comes from iterated commutator with a balanced split, same as sequence A073121. (Indeed, the manuscript cites that sequence.) We conjecture that there's an $\Omega(n^2)$ lower bound (and indeed that A073121 is exactly tight), but haven't proved it. If you come up with a proof, it might breath some life into that manuscript and we could consider joining forces.