Separating words with automata is a longstanding open problem in combinatorics on words. In this paper we present a related algebraic problem. What is the minimal length of a nontrivial identical relation in the symmetric group S n ?
Our main contribution is an upper bound $2^{O(\sqrt n\log n)}$ on the length of the shortest nontrivial identical relation in S n . We also give lower bounds for words of a special types. These bounds can be applied to the problem of separating words by reversible automata. In this way we obtain an another proof of the Robson’s square root bound.