MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

What is the length of the shortest word $w\in F_2$ such that $w(x,y)$ is trivial for every $x,y\in S_n$?

There is a simple argument showing that we must have $\ell(w)\geq n$. See here for instance. It seems likely however that $\ell(w)$ must be super-polynomial in $n$.

What is the state of the art for lower bounds?

(As for upper bounds, the paper "Identical relations in symmetric groups and separating words with reversible automata" by Gimadeev and Vyalyi finds an upper bound of $\exp(\sqrt{n}\log n)$.)

share|cite|improve this question
Would it be possible to be a little more explicit? What is $S_n$? The symmetric group? What is $F_2$, and what is $w$ or $\mathcal{l}(w)$? – Christian Stump Apr 10 '13 at 11:23
$F_2$ is a free group in $x$ and $y$. Sean is asking about the shortest identity $w(x,y)$ such that $w(a, b)=1$ for any $a,b\in S_n$. – Alexey Kvashchuk Apr 10 '13 at 11:37
up vote 15 down vote accepted

As far as I know, the state of the art gives some improvements to those bounds, but they are not huge. For a better lower bound: given a nontrivial element $w \in F_2$ of word length $\ell$, using a result of Buskin (Economical separability in free groups, Sib. Math. J., 50 (2009), 603-608) there exists a subgroup, $H$, of index $\ell/2+2$ that does not contain $w$. By looking at the action of $F_2$ on $F_2/ H$ we get a representation of $F_2$ into $S_{\ell/2+2}$, that does not kill $w$. Therefore, in order for $w$ to be trivial in any representation of $F_2$ into $S_n$ we must have that $n \leq \ell /2 + 2$, or $2(n-2) \leq \ell$.

There are also better upper bounds known (see, for instance, Asymptotic growth and least common multiples in groups (me and Ben McReynolds), Bulletin of the LMS (2011)).

Your question is equivalent to quantifying residual finiteness of free groups (the non-normal case), for which the precise answer is still unknown (the best known bounds are from the papers above).

share|cite|improve this answer
Thank you, this is a great answer. I didn't know about either of these papers. – Sean Eberhard Apr 10 '13 at 14:39
It's amazing that the lower bound $10n$ is open! – Sean Eberhard Apr 10 '13 at 14:42

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.