I'm trying to solve the following problem from a probabilistic method course:
Prove that there is a constant $c>0$, such that for every prime $p$ and every set $A\subset Z_p, |A|=k$, there is $x\in Z_p$ such that $\{xa(mod p) : a\in A\}$ intersects every interval of length at least $c \frac{p}{\sqrt{k}}$ in $Z_p$.
Any help would be much appreciated!
We shall use the second moment method:
First, let us define two independent random variables $a,b\sim\mathbb{U}(Z_p)$, we define the polynomial $f(x)=ax+b$. As two induced RVs, for $x\neq y\in Z_p$ $f(y)$ is independent of $f(x)$, since:$$P[f(x)=c,f(y)=d]=P[f(x)=c]P[f(y)=d]$$ for all arbitrary $c,d\in Z_p$, the proof for that is fairly simple.
Now, for a subset $I\subseteq Z_p$ and $a\in A$ we define the indicator $I_a=ind[f(a)\in I]$ and $I_A=\sum_{a\in A}I_a$. Trivially $E[I_a]=\frac{\vert I\vert}{p}$and $E[I_A]=\frac{k\vert I\vert}{p}$. Since $I_a$ are IRV with bernouli ditribution we get $Var[I_A]=k\frac{c}{\sqrt k}(1-\frac{c}{\sqrt k})\leq c\sqrt k$
Now for $\vert I\vert = \frac{cp}{\sqrt k}$:
Since $I_a$ are IRVs with Bernoulli distribution we get $Var[I_A]=k\frac{c}{\sqrt k}(1-\frac{c}{\sqrt k})\leq c\sqrt k$: $$P[f(A)\cap I=\emptyset]=P[I_A =0]\leq P[\vert I_A-E[I_A]\vert \geq E [I_A]]\leq\frac{Var[I_A]}{E[I_A]^2}\leq \frac{1}{c\sqrt k}$$ The last inequality holds from Chbishev.
For the final step, let us make partition of $Z_p$ into $\sqrt k/c$ non intersecting intervals of length $\frac{cp}{\sqrt k}$. We mark that set $\Pi$. $$P[\forall I\in \Pi: f(A)\cap I \neq\emptyset]=1-P[\exists I\in \Pi: f(A)\cap I =\emptyset]>1-\frac{1}{c\sqrt k}\#\Pi=1-\frac{1}{c^2}\geq0$$ for $c=1$ the inequality holds.
Q.E.D