I am trying to solve the following question:
Prove that there exists a constant $c > 0$ so that: For every $p$ prime, and any $A \subseteq \mathbb Z_p, |A| = k$ there exists a polynomial $f$ of degree at most 3, so that $\{f(a)| a\in A\}$ intersects every interval of length at least $\frac{cp}{k^{2/3}}$.
Now, I have already proved that we can have a linear polynomial so that the image intersects every interval of length $\frac{cp}{\sqrt k}$.
I tried to apply the same method here, trying to utilize the fact that I have more freedom to choose the coefficients. This is my attempt at a solution:
Choose randomly $x, y, z, w \in \mathbb Z_p$ and consider the polynomial $f(a) = xa^3 +ya^2+za-w$. Denote $A = \{a_1, a_2, \ldots , a_k\}$ and we can assume that $0\notin A$. For every $1 \le i \ne j \le k$ let $X_{ij}$ be the indicator random variable for the event $f(a_i) \in [0,u] \land f(a_j) \in [u+1, 2u+1]$ where $u \sim \frac{p}{k^{2/3}}$. Let $X = \sum_{i \ne j} X_{ij}$. Now, $E[X] = \sum_{i \ne j} E[X_{ij}] = k(k-1)(u+1)^2/p^2 \sim k^{2/3}$.
Using Chebyshev's inequality we can bound:
$$\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'})$$
If the covariance term was zero then we'd get $\mathrm {Pr}(X=0) \le \frac{1}{E[X]} \sim \frac{1}{k^{2/3}}$.
Then the expected value of the intervals missed by the image of $f$ would be $\sim\frac{p}{k^{2/3}} \sim u$ but this is a contradiction since if an interval of length $2u$ is missed then $u+1$ of its subintervals are also missed (I disregard the constants here to save time).
However when calculating the covariance term I get
$$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}$$
The summation over all $i,j,l$ gives the order of magnitude of $k$ so when divided by $E[X]^2$ I get a term $\sim \frac{1}{k^{1/3}}$ which is much bigger than the $1/E[X]$ term so the proof fails.
Now I'm stuck. Any help will be appreciated :)
This is not fully worked out, but I think the following process works: we show that we intersect each consecutive interval of length $\frac{cp}{2k^{2/3}}$ and then each interval of length $\frac{cp}{k^{2/3}}$ will contain at least one whole consecutive interval.
Draw a polynomial by picking $a,b,c,d \in \mathbb{Z}_p$ uniformly at random, show that the polynomial is $4$-wise independent and fix an interval. Let $I_{a,b,c,d}$ be an indicator r.v. for $f(\cdot)$ hitting the interval, and consider $I_{a,b,c,d}^2$ ($I^2$ for short), by my calculation: $\mathbb{E}(I^2)\approx \frac{pck^{2/3}}{16p}$ (plus some lower order terms on the numerator).
Now this is the part I'm not certain about, but I think you can show that $Var(I^2) \leq \mathbb{E}(I^2)$ and now you can apply Chebyshev to get that $\Pr[I^2 = 0] \leq \frac{1}{\mathbb{E}(I^2)}$ and a union bound over all $\frac{2k^{2/3}}{c}$ intervals will give you that $\Pr[\exists \ interval \ with: I^2=0] < 1$ and therefore you can find a polynomial that intersects all intervals.
Edit:
My calculation for the expectation: $ \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'}}}$
Now: you can show that $\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$
and now sum to get:
$\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} $
For the second part, that's what I'm uncertain about. I think you need to justify the fact that since $I^2$ is the product of sums of indicator r.v. you have $Var(I^2) \leq \Exp{I^2} + \sum_{i \sim j}\Pr[A_i \land A_j]$, where $A_i, A_j$ are two distinct events corresponding to indicators $I,I'$. Now you can use the $4$-wise independence of $f$ to show that the sum is zero so $Var(I^2) \leq \Exp{I^2}$