Expanding groups with large diameter

Resumen Técnico: Grupos Expansores con Diámetro Grande

1. El Problema y el Contexto

El artículo aborda una cuestión fundamental en la teoría de grupos finitos y la teoría espectral de grafos: la dependencia de las propiedades de expansión y diámetro de los grafos de Cayley respecto a la elección del conjunto generador.

• Contexto: Para grupos infinitos, propiedades como el crecimiento, la hiperbolicidad o la amenabilidad son invariantes del grupo y no dependen del conjunto generador finito elegido. Sin embargo, para secuencias de grupos finitos, la situación es diferente.
• Antecedentes: Alon, Lubotzky y Wigderson (1991) demostraron que existen grupos cuyos grafos de Cayley son expansores para un conjunto generador acotado, pero no para otro. Kassabov (2005) extendió esto a grupos simétricos y grupos simples finitos.
• La Conjetura/Question: Pyber y Szabó (2013) plantearon la siguiente pregunta (Pregunta 1.1): Si una secuencia de grupos finitos $(G_n)$ tiene grafos de Cayley que son expansores para alguno conjunto generador acotado $(X_n)$, ¿es cierto que para cualquier otro conjunto generador $(Y_n)$, el diámetro del grafo de Cayley es polilogarítmico respecto al tamaño del grupo? Es decir, ¿es el diámetro polilogarítmico una propiedad intrínseca del grupo?
• Objetivo: Los autores responden negativamente a esta pregunta, demostrando que es posible tener un grupo que es un expansor con un conjunto generador, pero que tiene un diámetro "super-polilogarítmico" (incluso exponencial en la raíz del logaritmo del tamaño del grupo) con otro conjunto generador.

2. Metodología y Construcción

Los autores construyen una secuencia de grupos finitos $(G_n)$ que satisface las condiciones requeridas mediante una construcción algebraica específica y un análisis probabilístico combinado con técnicas de suma exponencial.

• Construcción del Grupo:

  • Se define el grupo como un producto semidirecto: $G_n = V_0 \rtimes S_n$.
  • $V_0$ es el módulo de permutación eliminado de dimensión $n-1$ sobre el campo finito $\mathbb{F}_p$, donde $V_0 = \{v \in \mathbb{F}_p^n : \sum v_i = 0\}$.
  • $S_n$ es el grupo simétrico de grado $n$.
  • El primo $p$ se elige de manera que sea exponencialmente grande en relación con $n$ (específicamente $p \sim e^{cn}$).
  • El tamaño del grupo es $|G_n| = p^{n-1} n! \approx \exp(c n^2)$.

• Conjunto Generador "Malvado" ($Y_n$):

  • Se elige un vector $v = (1, -1, 0, \dots, 0) \in V_0$ y un subconjunto $T \subset S_n$ generado por una transposición y un ciclo largo.
  • Este conjunto genera el grupo, pero debido a la estructura de $V_0$ y la elección de $v$, el diámetro del grafo de Cayley crece linealmente con $p$, es decir, $\text{diam}(G_n, Y_n) \ge p \sim e^{cn}$. Esto es mucho mayor que cualquier función polilogarítmica de $|G_n|$.

• Conjunto Generador "Bueno" ($X_n$):

  • Se busca un vector $v' \in V_0$ y un conjunto $T' \subset S_n$ (que ya se sabe es un expansor para $S_n$ por resultados de Kassabov) tales que el grafo de Cayley sea un expansor uniforme.
  • La clave es demostrar la existencia de un $v'$ que maximice el "gap espectral" (brecha espectral).

3. Análisis Matemático y Herramientas Clave

La prueba se divide en dos partes principales: la reducción al problema de suma exponencial y la demostración probabilística de la existencia del vector adecuado.

• Constante de Kazhdan y Expansión:

  • Utilizan la relación entre la constante de Kazhdan $\kappa(G, S)$ y el gap espectral. Para demostrar que $G_n$ es un expansor con $X_n$, deben acotar inferiormente $\kappa(G_n, X_n)$.
  • Mediante el Proposición 3.4, reducen el problema de la expansión del producto semidirecto $V_0 \rtimes S_n$ a la expansión de $S_n$ (que ya es conocida) y a la expansión de la acción de $S_n$ sobre $V_0$ mediante el vector $v$.

• Reducción a Sumas Exponenciales Permutacionales:

  • El problema se reduce a encontrar un vector $v \in V_0$ tal que para todo vector no constante $w \in V$, la suma exponencial permutacional sea pequeña:
    $$\left| \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle) \right| \le 1 - \varepsilon$$
    donde $e_p(x) = \exp(2\pi i x / p)$.

• Argumento Probabilístico y Determinista (Teorema 1.3):

  • Desafío: Si $p$ es muy grande (exponencial en $n$), un argumento de unión (union bound) simple falla porque hay demasiados vectores $w$ para controlar.
  • Solución:
    1. Paso Probabilístico (Lema 4.1): Muestran que si $v$ se elige aleatoriamente en $V_0$, la suma exponencial es pequeña para vectores $w$ con soporte pequeño (específicamente, vectores con una sola coordenada no nula en la diferencia). Usan la desigualdad de Hoeffding.
    2. Paso Determinista (Lema 4.2): Utilizan un argumento de "conmutación" (switching argument) basado en la desigualdad de Cauchy-Schwarz. Demuestran que si la suma exponencial es pequeña para los vectores de soporte simple, entonces es pequeña para todos los vectores no constantes $w$.
  • Resultado: Demuestran que para $p \le e^{\delta n}$, existe un $v$ (de hecho, casi todos los $v$ aleatorios funcionan) que satisface la condición de expansión.

4. Resultados Principales

• Teorema 1.2 (Resultado Principal):
  Existen constantes $\delta, \varepsilon > 0$ y una secuencia de grupos finitos $(G_n)$ con conjuntos generadores acotados $X_n, Y_n$ tales que:

  1. $\text{Cay}(G_n, X_n)$ son grafos $\varepsilon$-expansores (tienen un gap espectral uniforme).
  2. $\text{diam}(\text{Cay}(G_n, Y_n)) \ge \exp(\delta \sqrt{\log |G_n|})$.

  Esto demuestra que el diámetro puede ser super-polilogarítmico (incluso exponencial en la raíz cuadrada del logaritmo del orden del grupo) a pesar de que el grupo admite una estructura de expansor.

• Teorema 1.3 (Lema Técnico):
  Establece la existencia de vectores $v$ en el módulo de permutación que acotan las sumas exponenciales permutacionales, permitiendo la expansión incluso cuando el primo $p$ es exponencialmente grande en $n$.

5. Significado e Impacto

• Respuesta Negativa a Pyber-Szabó: El trabajo resuelve definitivamente la pregunta de Pyber y Szabó (2013) y la pregunta relacionada de Sabatini (Oberwolfach 2024) en sentido negativo. Se demuestra que el diámetro polilogarítmico NO es una propiedad del grupo. Un grupo puede ser un "buen" expansor con una generación y tener un diámetro enorme con otra.
• Límites de la Propiedad de "Casi Plano" (Almost Flat): El artículo aclara que, aunque tener un diámetro polinomial es una propiedad del grupo (grupos "almost flat"), tener un diámetro polilogarítmico no lo es.
• Innovación Técnica: La capacidad de manejar primos $p$ exponencialmente grandes es una novedad técnica significativa. A diferencia de trabajos anteriores donde $p$ era acotado, aquí los autores evitan el uso de union bounds sobre todos los vectores mediante una combinación ingeniosa de probabilidad (para vectores simples) y álgebra lineal determinista (Cauchy-Schwarz) para extender el resultado a todo el espacio.
• Construcción Unificada: La construcción combina elementos de las obras de Alon-Lubotzky-Wigderson y Kassabov, pero introduce una nueva escala de parámetros ($p$ grande) que permite separar drásticamente las propiedades de expansión y diámetro.

En conclusión, este artículo establece una distinción fundamental entre la propiedad espectral (expansión) y la propiedad métrica (diámetro) en la teoría de grupos finitos, demostrando que la primera no implica la segunda bajo cambios de conjunto generador.