# Finding 'verbally smallest' element of a finitely generated group

Let $G = ({\Large\ast}^n\mathbb{Z})/K$ be a group, and for each $g \in G$ define $l(g)$ as the smallest positive integer $m$ such that $g = g_1 \ldots g_m$, where each $g_i$ is a generator of $G$. Now let $H < G$. The problem is finding $\operatorname{arg\,min}_{g \in H \setminus \{1\}} l(g)$.

My motivation is the commutator-based magic' puzzle posted by Gil Kalai here, which boils down to finding a non-trivial element of $\bigcap_{i=1}^n \operatorname{ker}p_i$, where $p_i: {\Large\ast}_{j = 1}^n \mathbb{Z}a_j \to {\Large\ast}_{j \neq i}\mathbb{Z}a_j$ is defined by $p_i(a_j) = a_j$ when $i \neq j$ and $p_i(a_i) = 1$. One non-trivial element is $[\ldots[a_1, a_2], a_3], \ldots], a_n]$, but I heard people complaining that it's too long and the corresponding loop will be too hard to draw, so I'm now interested in finding a smaller solution, if it exists.

Are there any known theorems concerning this kind of problems or any techniques I could try or any references I could read?

-
This is basically the content of this question. It didn't get far sadly. – Miha Habič Nov 8 '11 at 16:09
So you want $G$ to be abelian? – user641 Nov 8 '11 at 16:12
No, in fact I didn't write it down correctly, sorry :) – Alexei Averchenko Nov 8 '11 at 16:14
I am not sure what you mean by $(\coprod^n\mathbb{Z})/K$. Is your $\coprod^n\mathbb{Z}$ just the free group on $n$-generators? Also, $l(g)$ is basically the length of the geodesic between $1$ and $g$ in the Cayley graph. This is often a fruitful way to look at such problems (if you could, for example, prove that $G$ is relatively hyperbolic w.r.t. $H$ then you might be getting somewhere!). – user1729 Nov 8 '11 at 18:01
@user1729, yes, it is the free group. Thanks, I'll look into these topics! – Alexei Averchenko Nov 8 '11 at 18:39

I don't know any theorems, but simple search yields the given commutator is optimal for n ≤ 3:

• n = 1: $a_1$, a simple loop
• n = 2: $[a_1,a_2]$, the Pochhammer contour
• n = 3: $[[a_1,a_2],a_3]$, Poch-Loop-ReversePoch-ReverseLoop

I suspect this is optimal in general, since K is contained in the nth term of the lower central series, so elements of K are products of commutators of length n anyways.

I'm a little impressed at n = 5 though: that is a length of 46. It is not so bad to do recursively (at least for n=3), but I'm not sure I'd have the patience for 46 windings. The given commutator has length $3\cdot(2^{n-1})-2$, so this certainly gets unmanageable quickly.

I suggest drawing the loops more like braids, so have n horizontal sticks, start the loop on the left, and have it wind slowly to the right, showing whether it is over or under each stick as it goes. The very end on the far right connects back to the far left underneath (I guess that would be a good place for the picture to hang).

The tex is available too and uses Andrew Stacey's knots in tikz code.

-
Yes, this is indeed frightening. If you keep each loop 10 cm in length you'll need just $n = 28$ to reach the moon. – Alexei Averchenko Nov 8 '11 at 20:26