Grupo cuasialeatorio

En matemáticas , un grupo cuasialeatorio es un grupo que no contiene un subconjunto grande libre de productos. Estos grupos son precisamente aquellos que no tienen una representación irreducible pequeña y no trivial . El nombre de estos grupos proviene de su conexión con la teoría de grafos : los grafos de Cayley bipartitos sobre cualquier subconjunto de un grupo cuasialeatorio son siempre grafos cuasialeatorios bipartitos .

La noción de grupos cuasialeatorios surge al considerar subconjuntos de grupos para los cuales no hay dos elementos en el subconjunto que tengan un producto en el subconjunto; dichos subconjuntos se denominan libres de producto . László Babai y Vera Sós preguntaron sobre la existencia de una constante${\displaystyle c}$para el cual cada grupo finito${\displaystyle G}$con orden${\displaystyle n}$tiene un subconjunto libre de productos con un tamaño al menos${\displaystyle cn}$. ^{[ 1 ]} Un resultado bien conocido de Paul Erdős sobre conjuntos de enteros libres de sumas puede usarse para demostrar que${\textstyle c={\frac {1}{3}}}$es suficiente para grupos abelianos , pero resulta que tal constante no existe para grupos no abelianos . ^{[ 2 ]}

Ahora se conocen límites inferiores y superiores no triviales para el tamaño del subconjunto libre de producto más grande de un grupo con orden${\displaystyle n}$. Un límite inferior de${\textstyle cn^{\frac {11}{14}}}$se puede demostrar tomando un subconjunto grande de una unión de suficientes clases laterales , ^{[ 3 ]} y una cota superior de${\textstyle cn^{\frac {8}{9}}}$se obtiene considerando el grupo lineal especial proyectivo${\displaystyle \operatorname {PSL} (2,p)}$para cualquier primo${\displaystyle p}$. ^{[ 4 ]} En el proceso de demostrar la cota superior, Timothy Gowers definió la noción de un grupo cuasialeatorio para encapsular la condición libre de producto y demostró equivalencias que involucran cuasialeatoriedad en la teoría de grafos.

Formalmente, no tiene sentido hablar de si un solo grupo es cuasialeatorio o no. La definición estricta de cuasialeatoriedad se aplicará a secuencias de grupos, pero primero debe definirse la cuasialeatoriedad de grafos bipartitos. La motivación para considerar secuencias de grupos proviene de su conexión con los grafones , que se definen como límites de grafos en cierto sentido.

Fijar un número real${\displaystyle p\in [0,1].}$Una secuencia de grafos bipartitos${\displaystyle (G_{n})}$(aquí${\displaystyle n}$se permite omitir enteros siempre que${\displaystyle n}$tiende al infinito) con${\displaystyle G_{n}}$teniendo${\displaystyle n}$vértices, partes de vértices${\displaystyle A_{n}}$y${\displaystyle B_{n}}$, y${\displaystyle (p+o(1))|A_{n}||B_{n}|}$Los bordes son cuasialeatorios si se cumple alguna de las siguientes condiciones equivalentes:

• Para cada grafo bipartito${\displaystyle H}$con partes de vértice${\displaystyle A'}$y${\displaystyle B'}$, el número de copias etiquetadas de${\displaystyle H}$en${\displaystyle G_{n}}$con${\displaystyle A'}$incrustado en${\displaystyle A}$y${\displaystyle B'}$incrustado en${\displaystyle B}$es${\textstyle \left(p^{e(H)}+o(1)\right)|A|^{|A'|}|B|^{|B'|}.}$Aquí, la función${\displaystyle o(1)}$se le permite depender de${\displaystyle H.}$
• El número de recorridos cerrados y etiquetados de longitud 4 en${\displaystyle G_{n}}$comenzando en${\displaystyle A_{n}}$es${\displaystyle (p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.}$
• El número de aristas entre${\displaystyle A'}$y${\displaystyle B'}$es${\displaystyle p|A'||B'|+n^{2}o(1)}$para cualquier par de subconjuntos${\displaystyle A'\subseteq A_{n}}$y${\displaystyle B'\subseteq B_{n}.}$
• ${\displaystyle \sum \limits _{a_{1},a_{2}\in A_{n}}N(a_{1},a_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}}$, dónde${\displaystyle N(u,v)}$denota el número de vecinos comunes de${\displaystyle u}$y${\displaystyle v.}$
• ${\displaystyle \sum \limits _{b_{1},b_{2}\in B_{n}}N(b_{1},b_{2})^{2}=(p^{4}+o(1))|A_{n}|^{2}|B_{n}|^{2}.}$
• El mayor valor propio de${\displaystyle G_{n}}$La matriz de adyacencia de es${\textstyle (p+o(1)){\sqrt {|A||B|}}}$y todos los demás autovalores tienen magnitud como máximo${\textstyle {\sqrt {|A||B|}}o(1).}$

Es un resultado de Chung–Graham–Wilson que cada una de las condiciones anteriores es equivalente. ^{[ 5 ]} Dichos grafos se denominan cuasialeatorios porque cada condición afirma que la cantidad que se está considerando es aproximadamente la que se esperaría si el grafo bipartito se generara de acuerdo con el modelo de grafo aleatorio de Erdős–Rényi ; es decir, generado incluyendo cada posible arista entre${\displaystyle A_{n}}$y${\displaystyle B_{n}}$independientemente con probabilidad${\displaystyle p.}$

Aunque la cuasialeatoriedad solo puede definirse para secuencias de grafos, una noción de${\displaystyle c}$La cuasialeatoriedad se puede definir para un grafo específico permitiendo una tolerancia de error en cualquiera de las definiciones anteriores de cuasialeatoriedad de grafos. Para ser más específicos, dada cualquiera de las definiciones equivalentes de cuasialeatoriedad, la${\displaystyle o(1)}$El término puede ser reemplazado por una pequeña constante.${\displaystyle c>0}$y cualquier gráfico que satisfaga esa condición modificada particular puede denominarse${\displaystyle c}$-cuasialeatorio. Resulta que${\displaystyle c}$-la cuasialeatoriedad bajo cualquier condición es equivalente a${\displaystyle c^{k}}$-cuasiraleatoriedad bajo cualquier otra condición para alguna constante absoluta${\displaystyle k\geq 1.}$

El siguiente paso para definir la cuasialeatoriedad de grupo es el grafo de Cayley. Los grafos de Cayley bipartitos ofrecen una manera de trasladar la cuasialeatoriedad del contexto de la teoría de grafos al contexto de la teoría de grupos.

Dado un grupo finito${\displaystyle \Gamma }$y un subconjunto${\displaystyle S\subseteq \Gamma }$, el grafo de Cayley bipartito${\displaystyle \operatorname {BiCay} (\Gamma ,S)}$es el grafo bipartito con conjuntos de vértices${\displaystyle A}$y${\displaystyle B}$, cada uno etiquetado por elementos de${\displaystyle G}$, cuyos bordes${\displaystyle a\sim b}$están entre vértices cuya razón${\displaystyle ab^{-1}}$es un elemento de${\displaystyle S.}$

Con las herramientas definidas anteriormente, ahora se puede definir la cuasialeatoriedad de grupo. Una secuencia de grupos${\displaystyle (\Gamma _{n})}$con${\displaystyle |\Gamma _{n}|=n}$(de nuevo,${\displaystyle n}$se permite omitir enteros) es cuasialeatorio si para cada número real${\displaystyle p\in [0,1]}$y elección de subconjuntos${\displaystyle S_{n}\subseteq \Gamma _{n}}$con${\displaystyle |S_{n}|=(p+o(1))|\Gamma _{n}|}$, la secuencia de gráficos${\displaystyle \operatorname {BiCay} (\Gamma _{n},S_{n})}$es cuasialeatorio. ^{[ 4 ]}

Aunque la cuasialeatoriedad solo puede definirse para secuencias de grupos, el concepto de${\displaystyle c}$-la cuasialeatoriedad para grupos específicos puede extenderse a grupos utilizando la definición de${\displaystyle c}$-cuasiraleatoriedad para gráficos específicos.

Como demostró Gowers, la cuasialeatoriedad de grupo resulta ser equivalente a una serie de condiciones diferentes.

Para ser precisos, dada una secuencia de grupos${\displaystyle (\Gamma _{n})}$, los siguientes son equivalentes:

• ${\displaystyle (\Gamma _{n})}$es cuasialeatoria; es decir, todas las secuencias de grafos de Cayley definidas por${\displaystyle (\Gamma _{n})}$son cuasialeatorios.
• La dimensión de la representación no trivial más pequeña de${\displaystyle \Gamma _{n}}$es ilimitado.
• El tamaño del subconjunto libre de producto más grande de${\displaystyle \Gamma _{n}}$es${\displaystyle o(|\Gamma _{n}|).}$
• El tamaño del cociente no trivial más pequeño de${\displaystyle \Gamma _{n}}$es ilimitado. ^{[ 4 ]}

Los grafos de Cayley generados a partir de grupos pseudoaleatorios tienen fuertes propiedades de mezcla ; es decir,${\displaystyle \operatorname {BiCay} (\Gamma _{n},S)}$es bipartito${\displaystyle (n,d,\lambda )}$-gráfico para algunos${\displaystyle \lambda }$tendiendo a cero como${\displaystyle n}$tiende al infinito. (Recuerde que un${\displaystyle (n,d,\lambda )}$El gráfico es un gráfico con${\displaystyle n}$vértices, cada uno con grado${\displaystyle d}$, cuya matriz de adyacencia tiene un segundo valor propio más grande de como máximo${\displaystyle \lambda .}$)

De hecho, se puede demostrar que para cualquier${\displaystyle c}$-grupo cuasialeatorio${\displaystyle \Gamma }$, el número de soluciones a${\displaystyle xy=z}$con${\displaystyle x\in X}$,${\displaystyle y\in Y}$, y${\displaystyle z\in Z}$es aproximadamente igual a lo que cabría esperar si${\displaystyle S}$fue elegido al azar; es decir, aproximadamente igual a${\displaystyle {\tfrac {|X||Y||Z|}{|\Gamma |}}.}$Este resultado se deriva de una aplicación directa del lema de mezcla de expansores .

Existen varias familias notables de grupos cuasialeatorios. En cada caso, las propiedades de cuasialeatoriedad se verifican más fácilmente comprobando la dimensión de su representación no trivial más pequeña.

• Los grupos lineales especiales proyectivos${\displaystyle \operatorname {PSL} (2,p)}$para prime${\displaystyle p}$forman una secuencia de grupos cuasialeatorios, ya que un resultado clásico de Frobenius afirma que su representación no trivial más pequeña tiene dimensión al menos${\displaystyle {\tfrac {1}{2}}(p-1).}$De hecho, estos grupos son los grupos con la mayor representación mínima no trivial conocida, en función del orden del grupo.
• Los grupos alternos${\displaystyle (A_{n})}$son cuasialeatorios, ya que su representación no trivial más pequeña tiene dimensión${\displaystyle n-1.}$
• Cualquier secuencia de grupos simples no cíclicos con orden creciente es cuasialeatoria, ya que su representación no trivial más pequeña tiene dimensión al menos${\displaystyle {\tfrac {1}{2}}{\sqrt {\log n}}}$, dónde${\displaystyle n}$es el orden del grupo. ^{[ 4 ]}