• Abstract:   We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group S_n. This is equivalent to polynomial-time (O(n^c)) mixing of the (lazy) random walk on S_n where one step is multiplication by a generator or its inverse. We prove that the conjecture is true for almost all pairs of generators. Specifically, our bound is O^*(n⁷). For almost all pairs of generators, words of this length representing any given permutation can be constructed in Las Vegas polynomial time. The best previous bound on the word length for a random pair of generators was n^{(ln n)(1/2+o(1))} (Babai--Hetyei, 1992). We build on recent major progress by Babai--Beals--Seress (SODA, 2004), confirming the conjecture under the assumption that at least one of the generators has degree <0.33n. The main technical contribution of the present paper is the following near-independence result for permutations. The first cycle of a permutation is the trajectory of the first element of the permutation domain. For a random permutation, the distribution of the length of the first cycle is uniform. We show that if τ ∈ S_n is a given permutation of degree ≥n^3/4 and σ ∈ S_n is chosen at random, then the distributions of the length of the first cycle of σ and the length of the first cycle in στ are nearly independent. The ability of an essentially arbitrarily fixed permutation (τ) to ``scramble'' another permutation in this technical sense may be of independent interest and suggests new directions in the statistical theory of permutations pioneered by Goncharov and Erdos-Turan.

Versions available:

SODA Proceedings version (except page numbers)

PDF

Postscript

DVI