Question

It would be nice to find out what is known about the following problem.

First let us consider a free group $F$ with two generators $a$ and $b$. We are interested in its elements that are

1. not equal to identity,
2. of form $c_1 c_2 \ldots c_n d_1^{-1} d_2^{-1} \ldots d_n^{-1}$, where all $c_i$ and $d_i$ are either equal to $a$ or to $b$.

Let us denote all these elements by $W$.

Let us consider the group $S_k$ now. What is the shortest word from $W$ with the following property: whatever elements of $S_k$ we substitute for $a$ and $b$ we get identity (in $S_k$)?

The best bounds for the smallest $n$ I am aware of are $2^{O(k)}$ and $\Omega(k^2)$.

Answer 1

You are asking for the shortest balanced semigroup identity in $S_k$. Some info can be found here: Pöschel, R.; Sapir, M. V.; Sauer, N. W.; Stone, M. G.; Volkov, M. V. Identities in full transformation semigroups. Algebra Universalis 31 (1994), no. 4, 580--588. But the bound there is exponential. I believe the lower bound should be exponential too, but I do not think there were any more recent papers on the subject. You may also try to read this paper. It is also relevant: Cherubini, Alessandra; Kisielewicz, Andrzej; Piochi, Brunetto, On the length of shortest 2-collapsing words. Discrete Math. Theor. Comput. Sci. 11 (2009), no. 1, 33--44.