Anticoncentration of Random Sums in $\mathbb{Z}_p$

Resumen Técnico: Anticoncentración de Sumas Aleatorias en $\mathbb{Z}_p$

1. Planteamiento del Problema

El artículo aborda el problema clásico de Littlewood-Offord en el contexto de grupos cíclicos finitos, específicamente en $\mathbb{Z}_p$ (donde $p$ es un primo). El objetivo central es estudiar la anticoncentración de la suma $Y$ de $\ell$ variables aleatorias independientes e idénticamente distribuidas (i.i.d.), $Y_1, \dots, Y_\ell$, que toman valores en $\mathbb{Z}_p$.

El problema consiste en encontrar cotas superiores para la probabilidad máxima de que la suma caiga en un valor específico $x$:
$$\max_{x \in \mathbb{Z}_p} \mathbb{P}[Y = x]$$

El vacío de conocimiento:

• La literatura existente (como los resultados de Lev [15, 16]) ofrece resultados asintóticos muy fuertes cuando $\ell \to \infty$.
• Sin embargo, para valores pequeños y moderados de $\ell$ (específicamente $\ell < 24$), las cotas asintóticas existentes a menudo son triviales (es decir, no mejoran la cota trivial de $1/n$ o incluso son peores).
• El objetivo del trabajo es llenar este vacío proporcionando cotas no asintóticas, explícitas y no triviales para $\ell \geq 3$, incluso cuando las distribuciones no son uniformes.

2. Metodología

El autor emplea una combinación de técnicas de análisis combinatorio, teoría de números y transformadas de Fourier discretas.

• Caso Entero ($\mathbb{Z}$):

  • Se revisan y demuestran cotas para sumas de variables uniformes sobre un conjunto de enteros distintos.
  • Se utiliza el Teorema de Berry-Esseen para aproximar la distribución de la suma por una normal, obteniendo una cota del orden $O(1/(n\sqrt{\ell}))$.
  • Para el caso específico de $\ell=3$, se realiza un conteo combinatorio directo para obtener una cota explícita y no trivial: $\frac{3 + 1/n^2}{4n}$.

• Transición a Grupos Cíclicos ($\mathbb{Z}_k$ y $\mathbb{Z}_p$):

  • Se discuten los isomorfismos de Freiman para transferir resultados de $\mathbb{Z}$ a $\mathbb{Z}_k$, aunque esto requiere que los factores primos de $k$ sean muy grandes.
  • Para evitar restricciones en los factores primos, el autor desarrolla un enfoque directo en $\mathbb{Z}_p$ utilizando la Transformada Discreta de Fourier (DFT).

• Análisis Espectral y Descomposición:

  • Para $\ell=3$, la probabilidad se expresa mediante la convolución de funciones de densidad y su transformada de Fourier: $\mathbb{P}[Y=x] = \frac{1}{p} \sum \cos(2\pi xk/p) (\hat{f}(k))^2$.
  • Se introduce una estrategia de descomposición del conjunto de soporte ($A$) en subconjuntos donde la probabilidad es alta o baja.
  • Se utiliza un argumento de inducción iterativa: si se puede demostrar que la suma de 3 variables reduce la concentración por un factor constante $C < 1$, entonces para $\ell$ grande, la concentración decae exponencialmente.

3. Contribuciones Clave y Resultados Principales

A. Resultados para $\ell = 3$ en $\mathbb{Z}_p$:
El autor demuestra que si las distribuciones de las variables están acotadas uniformemente por $\lambda < 1$ (es decir, $\max_x \mathbb{P}[Y_i=x] \leq \lambda$) y $p > 2/\lambda$, entonces existe una constante absoluta $C_{3,\lambda} < 1$ tal que:
$$\max_{x \in \mathbb{Z}_p} \mathbb{P}[Y_1 + Y_2 + Y_3 = x] \leq C_{3,\lambda} \cdot \lambda$$

• Caso Uniforme: Si las variables son uniformes sobre un conjunto de tamaño $n$ (donde $\lambda = 1/n$), se obtiene una cota explícita $C_1/n$ con $C_1 < 0.99993$.
• Caso General: Se establece que para $\lambda \leq 9/10$, existe una constante $C_3 < 1$ (con una aproximación numérica $C_3 < 1 - 1.3 \cdot 10^{-12}$) tal que la probabilidad máxima se reduce en un factor $C_3$ respecto a la cota inicial $\lambda$.

B. Resultados para $\ell$ General (Iteración):
Mediante la iteración del resultado para $\ell=3$, se obtienen cotas para cualquier $\ell \geq 3$.

• Sea $\ell_0 = 3^k$ la mayor potencia de 3 menor o igual a $\ell$.
• Bajo las condiciones de $p$ y $\lambda$, se demuestra que:
  $$\max_{x \in \mathbb{Z}_p} \mathbb{P}[Y = x] \leq \lambda \left( \frac{3}{\ell_0} \right)^\nu$$
  donde $\nu = -\log_3(C_3)$ es una constante absoluta positiva (estimada en $\nu > 1.19 \cdot 10^{-12}$).

C. Comparación con Resultados Asintóticos:

• Mientras que los resultados de Lev son superiores para $\ell$ muy grande, las cotas de este artículo son no triviales ya para $\ell \geq 3$.
• La cota de Lev (Corolario 2.9) se vuelve trivial (mayor que $1/n$) cuando $\ell < 24$. El enfoque de Costa proporciona estimaciones útiles en este régimen de "pequeño $\ell$" donde los métodos asintóticos fallan.

4. Significado e Impacto

1. Régimen No Asintótico: El trabajo es pionero en proporcionar cotas efectivas y explícitas para la anticoncentración en grupos finitos cuando el número de sumandos es pequeño, un régimen que ha sido menos explorado que el caso límite.
2. Generalidad de la Distribución: A diferencia de muchos trabajos previos que asumen distribuciones uniformes, este resultado aplica a cualquier distribución acotada uniformemente por $\lambda$, lo que lo hace más robusto para aplicaciones en estructuras combinatorias donde la uniformidad no está garantizada.
3. Aplicaciones Potenciales: Los resultados son relevantes para problemas de secuenciabilidad de conjuntos y en el análisis de caminatas aleatorias y matrices aleatorias en grupos finitos, donde se necesitan estimaciones precisas en regímenes donde $p$ y $\ell$ no son necesariamente infinitos.
4. Método Constructivo: La prueba proporciona constantes explícitas (aunque conservadoras) y un marco metodológico basado en la descomposición de soporte y análisis de Fourier que puede ser refinado para clases específicas de distribuciones.

En conclusión, el artículo establece un nuevo estándar para la comprensión de la anticoncentración en sumas de variables aleatorias en $\mathbb{Z}_p$ para valores pequeños de $\ell$, demostrando que la concentración decae exponencialmente con $\ell$ incluso antes de alcanzar el régimen asintótico.