How many residues mod p do you need to take to ensure that you can always find some multiple that contains 3 elements within ϵ of each other For $\epsilon<p$, let $N(\epsilon,p)$ be the smallest value of $n$ such that for any set $S \subset \mathbb Z_p$ of size $n$, there exists $\lambda\in \mathbb Z_p^{*}$, $\mu \in \mathbb Z_p$ s.t $\lambda S+\mu$ contains distinct $\{x,y,z\}$ with $0<x,y,z<\epsilon$, considered as positive integers in $[0,p]$.
I am interested in the dependence of $N(\epsilon,p)$ on $\epsilon$ and $p$.
In less formal language, how big a set of residues mod $p$ do you need to take to ensure that you can always find some multiple of the set that contains three elements within $\epsilon$ of each other?
A start could be made to set $\epsilon$ as a function of $p$ such as $\epsilon \approx c\ln(p)$ and look at possible bounds on N in terms of $p$.
Update: Thank you for such excellent responses!
For completeness I wanted to add an obvious generalisation which is to look at r>3 values:
For $\epsilon<p$, let $N_r(\epsilon,p)$ be the smallest value of $n$ such that for any set $S \subset \mathbb Z_p$ of size $n$, there exists $\lambda\in \mathbb Z_p^{*}$, $\mu \in \mathbb Z_p$ s.t $\lambda S+\mu$ contains r distinct values $x_i$ satisfying $0<x_i<\epsilon$, considered as positive integers in $[0,p]$.
Seva's calculation for the case $r=3$ generalises I believe to give an upper bound of $(r-2)p/\epsilon$ for $N_r(\epsilon,p)$. Similarly assuming a strong conjecture on arithmetic progressions we also get an upper bound of  about $C p/\ln p$ valid for all $\epsilon>r.$
For $\epsilon \approx \ln p$ we have both bounds roughly agreeing which suggests that better bounds in this case and for general $\epsilon$  should be obtainable. I suspect though this will be quite difficult.
 A: Something like $n>p/\epsilon$ should at least suffice (not sure how sharp this estimate is). Here is the argument.
Without loss of generality, assume that $0\in S$. With any element $s\in S\setminus\{0\}$ associate the set $\{-(\epsilon/2)/s,\dotsc,-1,1,\dotsc,(\epsilon/2)/s\}$, division by $s$ being carried in $\mathbb Z_p$. The total number of elements in all these sets is $\epsilon(n-1)$; hence, if $n>p/\epsilon$, then the sets cannot be pairwise disjoint. This means, there are $s_1,s_2\in S\setminus\{0\}$ ($s_1\ne s_2$) and $i_1,i_2\in\{\pm 1,\dotsc,\pm(\epsilon/2)\}$ such that $i_1/s_1=i_2/s_2$. Denoting this common value by $\lambda$, we will have $\lambda\{0,s_1,s_2\}\subset\{\pm 1,\dotsc,\pm(\epsilon/2)\}$, and it remains to apply an appropriate shift.
Notice also that if $n>r_3(p)$ (the largest size of a progression-free set in $[1,p]$, which is known to be $O(p(\ln\ln p)^4/(\ln p)$), then $S$ contains a three-term arithmetic progression. Therefore, $n\sim p(\ln\ln p)^4/(\ln p)$ works for any $\epsilon$, all the way down to $\epsilon=1$.
A: For simplicity, I'll assume nonstrict inequality: $x,y,z\leq \epsilon$.
For each integer $t\in [1,\epsilon]$, let $T_t := \{ (\lambda,\mu)\in \mathbb{Z}_p^\star\times \mathbb{Z}_p\mid t\in \lambda S+\mu\}$. It is easy to see that $|T_t| = n\varphi(p)$, where $\varphi(p)=|\mathbb{Z}_p^\star|$.
Existence of $(\lambda,\mu)$ such that $\lambda S+\mu$ contains a triple $x,y,z\in [1,\epsilon]$ is equivalent to having $T_x\cap T_y\cap T_z\ne\emptyset$.
Absence of such triple means that the sets $\{ T_t \mid t\in[1,\epsilon]\}$ cover each pair $(\lambda,\mu)$ at most twice, implying that $\lfloor\epsilon\rfloor n\varphi(p) \leq 2\varphi(p)p$, i.e., $n\leq \frac{2p}{\lfloor\epsilon\rfloor}$.
Hence, $n>\frac{2p}{\lfloor\epsilon\rfloor}$ is sufficient.
A: One can in fact pick $n$ that only depends on $\epsilon$ and not on $p$ and obtain a dilation that is $\epsilon$ dense.
See [1] and [2]. In particular, Proposition 2.1 in [1]  gives an upper bound of $4/\epsilon^2$ for this more challenging task.
[1]  Alon, Noga, and Yuval Peres. "Uniform dilations." Geometric and Functional Analysis GAFA 2, no. 1 (1992): 1-28.   https://pdfs.semanticscholar.org/0fb9/e7ad4a1cc2523365d7839b79ad4ad13df7bb.pdf
[2] Berend, Daniel, and Yuval Peres. "Asymptotically dense dilations of sets on the circle." Journal of the London Mathematical Society 2, no. 1 (1993): 1-17.
A: Here is a suggestion which I don't want to squeeze in a comment. To save typing, I fix $p$ and call the associated ring Z.
Consider T, the set of all subsets of  Z of size 3. You want an equivalence relation which partitions T into O(p) many classes, where two sets are equivalent of there is a linear transform between the two. Then you want to investigate each class and find out which ones "stay away from zero", meaning which sets transform only to sets (1,a,b) where b is larger than your epsilon.
You can rewrite your transform as $\lambda\cdot (x + \mu)$ and restrict attention to sets of the form (0,c,d), and find out which multiplicative transforms make the set small. Multiply d by 1/d, 2/d,... Epsilon/d, and see where c lands. The minimum of these values will help determine your n.
Once you have written a program to do this, you should find something like the minimum being of order cube root of p, perhaps a little larger. This should help you with your question.
Gerhard "Not Too Short For Signature" Paseman, 2019.08.27.
