Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

2 Answers 2

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.

share|improve this answer

See the paper "Brunnian links" by Gartside and Greenwood, published in Fundamenta Mathematicae. Theorems 8 and 7 imply that iterated commutators are optimal and the sequence you suggest gives the minimal length.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.