## 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. The best available bound on the maximum required word length is exponential in √n log n. Polynomial bounds on the word length have previously been established for very special classes of generating sets only. In this paper we give a polynomial bound on the word length under the sole condition that one of the generators fix at least 67% of the domain. Words of the length claimed can be found in Las Vegas polynomial time. The proof involves a Markov chain mixing estimate which permits us, apparently for the first time, to break the "element order bottleneck." As a corollary, we obtain the following average-case result: for a 1 - δ fraction of the pairs of generators for the symmetric group, the word length is polynomially bounded. It is known that for almost all pairs of generators, the word length is less than exp(√n ln n(1 + o(1))).

Original language | English (US) |
---|---|

Pages | 1101-1105 |

Number of pages | 5 |

State | Published - 2004 |

Externally published | Yes |

Event | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States Duration: Jan 11 2004 → Jan 13 2004 |

### Other

Other | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | New Orleans, LA. |

Period | 1/11/04 → 1/13/04 |

## All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)