4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$.) $\endgroup$ – LSpice Aug 27 '19 at 13:17
  • 2
    $\begingroup$ 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$ ? $\endgroup$ – David E Speyer Aug 27 '19 at 13:23
  • $\begingroup$ @DavidESpeyer Yes that's correct thank you. I'll update the question to make this clearer. $\endgroup$ – Ivan Meir Aug 27 '19 at 13:44
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ivan Meir Aug 28 '19 at 9:11
  • $\begingroup$ 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\}$. $\endgroup$ – Ivan Meir Aug 28 '19 at 9:23
  • $\begingroup$ 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? $\endgroup$ – Ivan Meir Aug 29 '19 at 10:38
  • $\begingroup$ @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. $\endgroup$ – Seva Aug 29 '19 at 15:00
  • $\begingroup$ Thanks. I think this tells us that the extremal examples for this problem are not random. $\endgroup$ – Ivan Meir Aug 29 '19 at 16:58
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.