La expectativa de un Subconjunto Aleatorio de las Raíces de la Unidad.

Question

Deje $p$ ser una de las primeras. Si $1_A(x)$ denota la función de indicador de la set $A\subset\mathbb{Z}/p\mathbb{Z}$ y $$\hat{1}_A(t):=\frac{1}{p}\sum_{n=1}^p 1_A(n)e^{2\pi i \frac{nt}{p}}$$ denotes the Fourier transform of $1_A$, then what can be said about $$\mathbb{E}\left( \sup_{t\neq 0} |\hat{1}_A(t)|\right)?$$ Do we have an upper bound of the form $S\left(\frac{\log p}{\sqrt{p}}\right)$ as $p$ tiende a infinito?

Alternativa de redacción: Para cada subconjunto $A$ de la $p$ raíces, vamos a $Sum(A)$ para denotar la suma de los elementos en $A$, y ver el $A^t:=\{a^t:\ a\in A\}$ para los números enteros $0<t<p$. Entonces, ¿cuál es la expectativa de que el máximo de la suma de $t$? Cómo estamos obligados $$\mathbb{E}_A\left(\sup_{t} \ \left|Sum\left(A^t\right)\right|\right).$$

Observaciones: Esta pregunta se originó a partir de una tarea opcional problema en mi Aritmética de la Combinatoria de la clase. He probado algunos bastante largo y prolongado cosas que no funcionan. También, tenga en cuenta que desde $p$ es primo, tomando el poder para $0<t<p$ corresponde exactamente a la automorfismos.

Answer 1

Un simple probabilístico enfoque funciona. De hecho, tengo un límite de $O(\sqrt{p \log p})$ en la expectativa de $\sup_t |Sum(A^t)|$.

Paso 1: En este paso, vamos a suponer $t=1$, y la envolvente de la variable aleatoria $Sum(A)$ donde $A$ es de manera uniforme un subconjunto aleatorio de las raíces de la unidad $\{ 1, \zeta, \ldots, \zeta^{p-1} \}$. Deje $X_i$ ser el complejo de la variable aleatoria que cuenta la contribución de $\zeta^i$ a la suma; es decir, $X_i$ es igual a $\zeta^{i}$ si $A$ contiene, y cero en caso contrario.

Puesto que el $X_i$'s son independientes, se puede pensar en la delimitación de su suma usando el Chernoff-Hoeffding obligado. Hay una ligera molestia que nuestras variables aleatorias son valores complejos; una solución sencilla es obligado las partes reales e imaginarias por separado, y luego combinarlos con el triángulo de la desigualdad. Hacer este cálculo, encontramos que la probabilidad de que $|Sum(A) - E[Sum(A)]| = |Sum(A)|$ supera $2c \sqrt{p \log p}$ es en la mayoría de las $\exp \left(- \frac{2 c^2 p \log p}{4p} \right) = p^{-c^2/2}$.

Paso 2: Para cualquier fija $t$, la $B = A^t$ es de nuevo de manera uniforme un subconjunto aleatorio de las raíces de la unidad, puesto que el $t$-mapa de poder simplemente permutes las raíces. Por lo que el análisis anterior, se sostiene si se sustituye $A$ $A^t$ (donde $t$ es cualquier número fijo). Luego, por la unión vinculados, la probabilidad de que $\sup_t |Sum(A^t)| \geq 2c \sqrt{p \log p}$ es en la mayoría de las $(p-1) \cdot p^{-c^2/2} = o(1/p)$, la elección de $c$ lo suficientemente grande.

Esta cola de la desigualdad puede ser fácilmente convertido en un obligado en la expectativa.