Expanding groups with large diameter

1. O Problema e o Contexto

O artigo aborda uma questão fundamental na teoria dos grupos e na teoria dos grafos de Cayley: a dependência das propriedades espectrais e métricas de um grupo em relação à escolha do conjunto gerador.

• Contexto: Para grupos infinitos, propriedades como o tipo de crescimento, hiperbolicidade e amenabilidade são invariantes sob a escolha do conjunto gerador finito. No entanto, para sequências de grupos finitos, a situação é diferente.
• A Questão de Pyber e Szabó (2013): Os autores investigam a seguinte pergunta: Se uma sequência de grupos finitos $(G_n)$ possui um conjunto gerador limitado $X_n$ tal que o grafo de Cayley $\text{Cay}(G_n, X_n)$ é um expansor (possui um spectral gap positivo), é verdade que todo conjunto gerador $Y_n$ produz um grafo com diâmetro polilogarítmico (ou seja, $\text{diam} \le C(\log |G_n|)^C$)?
• Hipótese Anterior: Acreditava-se que a propriedade de ser um expansor implicaria que o diâmetro do grupo seria pequeno (polilogarítmico) independentemente do gerador, especialmente no contexto de grupos simples finitos (conjectura de Babai).
• Objetivo do Artigo: Responder negativamente a essa questão, demonstrando que é possível ter grupos que são expansores sob um conjunto gerador, mas possuem diâmetro super-polilogarítmico (exponencial em raiz quadrada do logaritmo do tamanho do grupo) sob outro conjunto gerador.

2. Metodologia e Construção

Os autores constroem uma sequência de grupos finitos $(G_n)$ e dois conjuntos geradores distintos, $X_n$ e $Y_n$, com as seguintes características:

A. Estrutura do Grupo

O grupo é definido como um produto semidireto:
$$G_n = V_0 \rtimes S_n$$
Onde:

• $S_n$ é o grupo simétrico de grau $n$.
• $V = \mathbb{F}_p^n$ é um espaço vetorial sobre um corpo finito $\mathbb{F}_p$.
• $V_0$ é o "módulo de permutação deletado" (subespaço de dimensão $n-1$ onde a soma das coordenadas é zero), ou seja, $V_0 = \{v \in \mathbb{F}_p^n : \sum v_i = 0\}$.
• O primo $p$ é escolhido para ser exponencialmente grande em relação a $n$ ($p \approx e^{cn}$).
• O tamanho do grupo é $|G_n| = p^{n-1} n! \approx \exp(cn^2)$.

B. Os Conjuntos Geradores

Ambos os conjuntos geradores têm a forma $\{v\} \cup T$, onde $v \in V_0$ e $T \subset S_n$.

1. Conjunto $Y_n$ (Diâmetro Grande):

   • Escolha "ingênua": $v = (1, -1, 0, \dots, 0)$ e $T = \{(1, 2), (1, 2, \dots, n)\}$.
   • Resultado: O diâmetro é grande porque o elemento $v$ gera um subgrupo cíclico de ordem aproximada $p$. Como $p$ é exponencial em $n$, o diâmetro é pelo menos da ordem de $p$, ou seja, $\text{diam} \ge \exp(\delta \sqrt{\log |G_n|})$.

2. Conjunto $X_n$ (Expansor):

   • Escolha inteligente: $T$ é um conjunto gerador limitado de $S_n$ que já é conhecido por ser um expansor (baseado no trabalho de Kassabov).
   • O vetor $v$ é escolhido aleatoriamente em $V_0$.
   • Objetivo: Demonstrar que existe uma escolha de $v$ tal que $\text{Cay}(G_n, X_n)$ possui um spectral gap uniforme (é um expansor).

3. Análise Técnica e Resultados Principais

A prova divide-se em duas partes principais: a redução do problema de expansão para uma estimativa de soma exponencial e a prova dessa estimativa.

A. Redução para Somas Exponenciais Permutacionais

Utilizando constantes de Kazhdan e propriedades de produtos semidiretos (Proposição 3.4), os autores mostram que o spectral gap de $G_n$ depende do gap do módulo $V_0$ sob a ação de $S_n$.
O problema reduz-se a provar o Teorema 1.3:

Existem constantes $\delta, \varepsilon > 0$ tais que, para todo $n$ e primo $p \le e^{\delta n}$, existe um vetor $v \in V_0$ tal que, para todo vetor não constante $w \in V$:
$$\left| \frac{1}{n!} \sum_{\sigma \in S_n} e_p(\langle v, w^\sigma \rangle) \right| \le 1 - \varepsilon$$
Onde $e_p(x) = \exp(2\pi i x / p)$ e $\langle \cdot, \cdot \rangle$ é o produto interno padrão.

Essa soma representa os autovalores do operador de adjacência do grafo de Cayley restrito a $V_0$.

B. Prova Probabilística e Argumento Determinístico

A prova do Teorema 1.3 (Seção 4) utiliza uma combinação de probabilidade e análise combinatória:

1. Probabilidade (Lema 4.1): Mostra-se que, para um vetor aleatório $v$, a soma exponencial para vetores $w$ com suporte pequeno (vetores do tipo $(u, 0, \dots, 0)$) é pequena com alta probabilidade, usando a desigualdade de Hoeffding.
2. Argumento de "Switching" (Lema 4.2): Para lidar com o número enorme de vetores $w$ (o que impediria um simples union bound), os autores usam uma desigualdade de Cauchy-Schwarz. Eles demonstram que o quadrado da soma para um $w$ arbitrário pode ser limitado pela média das somas para vetores com suporte pequeno.
   • Especificamente, eles mostram que $|\lambda_{v,w}|^2 \le \frac{1}{2} + \frac{1}{2} \max_{u} |\lambda_{v,u}|^2$.
3. Conclusão: Combinando os lemas, provam que a probabilidade de um vetor aleatório $v$ falhar em satisfazer a condição de gap é menor que 1, garantindo a existência de tal vetor.

4. Contribuições Chave

1. Resposta Negativa à Pergunta de Pyber-Szabó: O artigo estabelece que a propriedade de ser um expansor (com gerador limitado) não implica que o diâmetro do grupo seja polilogarítmico para todos os conjuntos geradores.
2. Construção de Contraexemplo: Apresentam uma família explícita de grupos $G_n = \mathbb{F}_p^{n-1} \rtimes S_n$ com $p$ exponencialmente grande.
3. Novidade Técnica: A capacidade de lidar com $p$ exponencialmente grande (em vez de limitado) é a inovação principal. Isso é feito evitando o union bound sobre todos os vetores $w$, focando apenas em vetores de suporte unitário e usando argumentos determinísticos para estender o resultado.
4. Limites de Diâmetro: Demonstram que o diâmetro pode ser tão grande quanto $\exp(c \sqrt{\log |G|})$, que é super-polilogarítmico, mas ainda sub-exponencial.

5. Significado e Impacto

• Separação de Propriedades: O trabalho clarifica a distinção entre propriedades espectrais (expansão) e propriedades métricas (diâmetro) em grupos finitos. Mostra que a expansão é sensível à escolha do gerador, mesmo quando o tamanho do gerador é limitado.
• Refinamento da Conjectura de Babai: Embora a conjectura de Babai (sobre o diâmetro de grupos simples finitos) permaneça aberta para geradores específicos, este resultado mostra que não se pode esperar um limite polilogarítmico universal para qualquer conjunto gerador de um grupo expansor.
• Métodos Analíticos: A técnica de combinar estimativas probabilísticas com desigualdades de Cauchy-Schwarz para lidar com somas exponenciais permutacionais oferece uma nova ferramenta para a análise de grafos de Cayley em grupos de produto semidireto.

Em resumo, Eberhard e Sabatini demonstram que a "expansividade" de um grupo não é uma propriedade intrínseca que garanta diâmetros pequenos sob todas as gerações, desafiando intuições anteriores sobre a relação entre espectro e geometria em grupos finitos.