Identical Relations in Symmetric Groups and Separating Words with Reversible Automata

摘要

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(1)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.