imagen de un conjunto bajo un polinomio en $Z_p$ que interseca cada intervalo de longitud $p/k^{2/3}$

Question

Estoy tratando de resolver la siguiente pregunta:

Demostrar que existe una constante $c > 0$ para que: Para cada $p$ primo, y cualquier $A \subseteq \mathbb Z_p, |A| = k$ existe un polinomio $f$ de grado máximo 3, por lo que $\{f(a)| a\in A\}$ intercepta todo intervalo de longitud mínima $\frac{cp}{k^{2/3}}$ .

Ahora bien, ya he demostrado que podemos tener un polinomio lineal para que la imagen intersecte todo intervalo de longitud $\frac{cp}{\sqrt k}$ .
He intentado aplicar el mismo método aquí, tratando de aprovechar el hecho de que tengo más libertad para elegir los coeficientes. Este es mi intento de solución:
Elige al azar $x, y, z, w \in \mathbb Z_p$ y considerar el polinomio $f(a) = xa^3 +ya^2+za-w$ . Denote $A = \{a_1, a_2, \ldots , a_k\}$ y podemos suponer que $0\notin A$ . Para cada $1 \le i \ne j \le k$ dejar $X_{ij}$ sea la variable aleatoria indicadora del evento $f(a_i) \in [0,u] \land f(a_j) \in [u+1, 2u+1]$ donde $u \sim \frac{p}{k^{2/3}}$ . Sea $X = \sum_{i \ne j} X_{ij}$ . Ahora, $E[X] = \sum_{i \ne j} E[X_{ij}] = k(k-1)(u+1)^2/p^2 \sim k^{2/3}$ .
Usando la desigualdad de Chebyshev podemos acotar: $$\mathrm {Pr}(X=0) \le \frac{Var[X]}{E[X]^2} \le \frac{1}{E[X]} + \frac{1}{E[X]^2}\sum_{(i,j) \ne (i', j')}Cov(X_{ij}, X_{i'j'})$$
Si el término de covarianza fuera cero entonces obtendríamos $\mathrm {Pr}(X=0) \le \frac{1}{E[X]} \sim \frac{1}{k^{2/3}}$ .
Entonces el valor esperado de los intervalos perdidos por la imagen de $f$ sería $\sim\frac{p}{k^{2/3}} \sim u$ pero esto es una contradicción ya que si un intervalo de longitud $2u$ se pierde entonces $u+1$ de sus subintervalos también se pierden (no tengo en cuenta las constantes aquí para ahorrar tiempo).

Sin embargo, al calcular el término de covarianza obtengo $$Cov(X_{ij}, X_{il}) = \frac{(u+1)^3}{p^3} - \frac{(u+1)^4}{p^4} \sim \frac{(u+1)^3}{p^3} \sim \frac{1}{k^2}$$
La suma de todos los $i,j,l$ da el orden de magnitud de $k$ por lo que cuando se divide por $E[X]^2$ Tengo un término $\sim \frac{1}{k^{1/3}}$ que es mucho mayor que el $1/E[X]$ por lo que la prueba falla.
Ahora estoy atascado. Cualquier ayuda será apreciada :)

Answer 1

Esto no está totalmente resuelto, pero creo que el siguiente proceso funciona: demostramos que intersecamos cada intervalo consecutivo de longitud $\frac{cp}{2k^{2/3}}$ y luego cada intervalo de longitud $\frac{cp}{k^{2/3}}$ contendrá al menos un intervalo entero consecutivo.

Dibuja un polinomio eligiendo $a,b,c,d \in \mathbb{Z}_p$ uniformemente al azar, demuestre que el polinomio es $4$ -sensiblemente independiente y fijar un intervalo. Sea $I_{a,b,c,d}$ sea un indicador r.v. para $f(\cdot)$ golpear el intervalo, y considerar $I_{a,b,c,d}^2$ ( $I^2$ para abreviar), según mis cálculos: $\mathbb{E}(I^2)\approx \frac{pck^{2/3}}{16p}$ (más algunos términos de orden inferior en el numerador).

Ahora bien, esta es la parte de la que no estoy seguro, pero creo que se puede demostrar que $Var(I^2) \leq \mathbb{E}(I^2)$ y ahora se puede aplicar Chebyshev para conseguir que $\Pr[I^2 = 0] \leq \frac{1}{\mathbb{E}(I^2)}$ y una unión ligada a todos los $\frac{2k^{2/3}}{c}$ los intervalos le darán ese $\Pr[\exists \ interval \ with: I^2=0] < 1$ y por lo tanto se puede encontrar un polinomio que intersecte todos los intervalos.

Editar:

Mi cálculo para la expectativa: $ \newcommand{\Exp}[1]{\mathop{\mathbb{E}}\left [ #1 \right ]} \Exp{I_{a,b,c,d}^2} = \Exp{\sum_{x \in A}\sum_{s \in S}I_{a,b,c,d,x,s}\cdot \sum_{x' \in A}\sum_{s' \in S}I_{a,b,c,d,x',s'}} \\ = \underset{(*)}{\Exp{\sum_{x \in A}\sum_{s \in S}I_{a,b,c,d,x,s}^2}} + \underset{(**)}{\Exp{\sum_{x \neq x' \in A}\sum_{s \in S}I_{a,b,c,d,x',s} \cdot I_{a,b,c,d,x',s}}} \\ + \underset{(***)}{\Exp{\sum_{x \in A}\sum_{s \neq s' \in S}I_{a,b,c,d,x,s} \cdot I_{a,b,c,d,x,s'}}} +\underset{(****)}{\Exp{\sum_{x \neq x' \in A}\sum_{s \neq s' \in S}I_{a,b,c,d,x,s} \cdot I_{a,b,c,d,x',s'}}}$

Ahora: puedes demostrar que $\Exp{(*)}=k |S| 1/p^2, \Exp{(**)}=\tbinom{k}{2}|S|1/p^2, \Exp{(***)}=0, \Exp{(****)}=\tbinom{k}{2}\tbinom{|S|}{2}1/p^2$

y ahora suma para conseguir:

$\Exp{I_{a,b,c,d}^2} = k |S| 1/p^2 + \tbinom{k}{2}|S|1/p^2 + \tbinom{k}{2}\tbinom{|S|}{2}1/p^2 \\ \approx \frac{1}{p^2} \left(\frac{kcp}{2k^{2/3}} + \frac{k^2 cp}{4k^{2/3}} + \frac{k^2 c^2 p^2}{16 k^{4/3}}\right) \\ = \frac{8ck^{1/3}+4ck^{4/3}+pc^2 k^{2/3}}{16p} $

Para la segunda parte, eso es lo que no tengo claro. Creo que hay que justificar el hecho de que desde $I^2$ es el producto de las sumas de los v.r. indicadores se tiene $Var(I^2) \leq \Exp{I^2} + \sum_{i \sim j}\Pr[A_i \land A_j]$ , donde $A_i, A_j$ son dos eventos distintos que corresponden a los indicadores $I,I'$ . Ahora puede utilizar el $4$ -independencia de $f$ para demostrar que la suma es cero por lo que $Var(I^2) \leq \Exp{I^2}$