MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 7 down vote accepted

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.

share|cite|improve this answer
The first article is not publicly available. Could you somehow send it to me? – ilyaraz Sep 22 '10 at 18:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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