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)$.


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.

  • $\begingroup$ The first article is not publicly available. Could you somehow send it to me? $\endgroup$ – ilyaraz Sep 22 '10 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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