47
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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 $\endgroup$
    – Sam Nead
    Feb 15, 2010 at 17:00
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2010 at 22:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Feb 17, 2010 at 14:15

2 Answers 2

21
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ If I understand correctly, this is oeis.org/A073121 $\endgroup$
    – YCor
    Feb 14 at 12:32
19
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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