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.



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
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$.


