This is related to Problem $4.6$ in ``The Probabilistic Method'' by Alon and Spencer, where one essentially has to prove the following:

Let $p$ be a prime, and $A$ be any subset of $\mathbb{F}_p$. Then for a uniformly chosen $z \in \mathbb{F}_p$, we have that the dilate $z \cdot A$ intersects every interval of width $\frac{2p}{\sqrt{|A|}}$ with probability at least $0.1$. Here, `intervals' are with respect to the (cyclic) additive group.

My question: What is the correct order of $t$ such that $z\cdot A$ almost surely intersects every interval of width $t$?

For concreteness, let $A$ be any subset of $\mathbb{F}_p$ of size $p^{0.5}$. Then, for a uniformly chosen $z \in \mathbb{F}_p$, does $z \cdot A$ intersect every interval of width $p^{0.5 + \epsilon}$ with high probability?

Here, high probability means probability approaching $1$ as $p$ goes to infinity.

Of course, $p^{0.5}$ is arbitrary. A general statement would say something for intervals of width $\frac{p}{|A|} \cdot \omega(1)$, for some slow growing $\omega(1)$.

  • $\begingroup$ It seems that you may not quite grasp the notion of a random dilate. It is not some particular dilate which can intersect or not intersect some interval. One can only speak about the probability that a random dilate intersects every interval of given width etc. $\endgroup$ – Seva Jan 9 at 15:45
  • $\begingroup$ @Seva I am sorry, I meant that the probability approaches $1$ as $p$ approaches infinity, but forgot to type. I have edited accordingly. Thanks for pointing this out. $\endgroup$ – Aditya Jan 9 at 15:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.