Casi independencia de las permutaciones y un límite polinómico casi seguro en el diámetro del grupo simétrico

Abordamos la conjetura de larga data que establece que todas las permutaciones tienen longitud de palabra acotada polinómicamente en términos de cualquier conjunto de generadores del grupo simétrico Sn. Esto equivale a un mezclado en tiempo polinómico (O(n c)) del paseo aleatorio (perezoso) en Sn donde un paso es la multiplicación por un generador o su inverso. Demostramos que la conjetura es verdadera para casi todos los pares de generadores. Específicamente, nuestro límite es O(n 7). Para casi todos los pares de generadores, se pueden construir palabras de esta longitud que representan cualquier permutación dada en tiempo polinómico de Las Vegas. El mejor límite previo sobre la longitud de palabra para un par aleatorio de generadores era n ln n(1/2+o(1)) (Babai–Hetyei, 1992). Nos basamos en importantes avances recientes por Babai–Beals–Seress (SODA, 2004), confirmando la conjetura bajo la suposición de que al menos uno de los generadores tiene grado ≥ 0.33n. La principal contribución técnica del presente documento es el siguiente resultado de casi independencia para permutaciones. El primer ciclo de una permutación es la trayectoria del primer elemento del dominio de la permutación. Para una permutación aleatoria, la distribución de la longitud del primer ciclo es uniforme. Mostramos que si τ ∈ Sn es una permutación dada de grado ≥ n 3/4 y σ ∈ Sn se elige al azar, entonces las distribuciones de la longitud del primer ciclo de σ y la longitud del primer ciclo en στ son casi independientes. La capacidad de una permutación esencialmente fijada arbitrariamente (τ) para "mezclar" otra permutación en este sentido técnico puede ser de interés independiente y sugiere nuevas direcciones en la teoría estadística de permutaciones pionera de Goncharov y Erdős–Turán.