# 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, 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, 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, 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, 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.

• I edited to fix TeX ($\mathbb{Z_p}$ $\mathbb{Z_p}$ should be $\mathbb Z_p$ $\mathbb Z_p$), but I think that there is also a quantifier issue: your set $S$, defined in terms of $n$, currently appears before $n$ is introduced. It seems easy enough to edit to fix, but I'm not sure I totally understood the question, so I didn't do it. (For example, you say you want an answer that depends on $\epsilon$ and $p$, but then you say to take $\epsilon$ as a function of $p$.) – LSpice Aug 27 '19 at 13:17
• I think there is only one reasonable order of quantifiers: Given $p$ a prime, and $\epsilon>0$, what is the smallest $n$ such that, for all $S \subset \mathbb{Z}/p \mathbb{Z}$ with $|S|=n$, there exists $\lambda \in (\mathbb{Z}/p \mathbb{Z})^{\times}$ and $\mu \in \mathbb{Z}/p \mathbb{Z}$ and $x$, $y$, $z \in \lambda S+ \mu$, such that $0 < x,y,z < \epsilon$ ? – David E Speyer Aug 27 '19 at 13:23
• @DavidESpeyer Yes that's correct thank you. I'll update the question to make this clearer. – Ivan Meir Aug 27 '19 at 13:44

## 4 Answers

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

• Thank you, I especially enjoyed the use of Szemeredi's theorem at the end. This made me think of a possible idea which is that the arithmetic progression case is $x-y=y-z$ but $x-y=r(y-z)$ with $r<\epsilon$ would also work. Is there a theorem that says there must exist a non-trivial solution to at least one of this set of $\epsilon$ equations but clearly with a better bound than Szemeredi's theorem? I think this problem is equivalent to such a theorem. – Ivan Meir Aug 28 '19 at 9:11
• This is obviously a special case of more general theorems concerning solutions to polynomial equations over restricted sets mod p. Our equation is $x−y=r(y−z)$ with $x, y, z\in S$ and $r\in E$ where $|S|=n$ and $E=\{1,\dots,\epsilon\}$. – Ivan Meir Aug 28 '19 at 9:23
• I have a question related to your response which is if we make the (highly dubious but simple) assume that your sets $\{-(\epsilon/2)/s,\dotsc,-1,1,\dotsc,(\epsilon/2)/s\}$ are randomly distributed in $\mathbb Z_p$ for many $s\in S\setminus\{0\}$, what sort of bounds do we obtain in this case and the more general case of $r>3$ values? – Ivan Meir Aug 29 '19 at 10:38
• @IvanMeir: if the sets were randomly distributed, then the expected size of the intersection of any two of them would be $(C\epsilon)^2/p$; hence, any two of them would intersect provided $\epsilon>C\sqrt p$. If your $\epsilon$ is smaller than $c\sqrt p$, then a subtler analysis may be needed. – Seva Aug 29 '19 at 15:00
• Thanks. I think this tells us that the extremal examples for this problem are not random. – Ivan Meir Aug 29 '19 at 16:58

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.

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.

• Thank you, that's very interesting - a related and beautiful problem! – Ivan Meir Aug 28 '19 at 9:31
• Note that $\epsilon$ in these 2 papers corresponds to $\epsilon/p$ in your formulation – Yuval Peres Aug 28 '19 at 14:41

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.