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.

Improve this question
$\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
    Commented 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$
    – Andy Putman
    Commented 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
    Commented Feb 17, 2010 at 14:15

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ If I understand correctly, this is oeis.org/A073121 $\endgroup$
    – YCor
    Commented 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.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .