1
$\begingroup$

In here Lemma $4$ using pigeonhole says:

For $T_1,\dots,T_s\in\Bbb R$ with $1\leq T_1,\dots,T_s<p$ and $\prod_{i=1}^sT_i > p^{s−1}$ and any integers $a_1,\dots,a_s$ there is an integer $t$ coprime to $p$ such that $$\min_{ k\in\Bbb Z}|ta_i − kp| \ll T_i,\quad\quad i = 1,\dots,s$$ holds.

First of all is this even true? Are we interpreting $(a_1,\dots,a_s)$ as a straight line in $\Bbb Z^s$?

Every integer $s$-tuple $a_1,\dots,a_s$ has $p$ mappings by $t(a_1,\dots,a_s)\bmod p$ where $t$ ranges from $\{0,1,\dots,p-1\}$. Unless we assume some uniformity in mapping I so not see how there is a $t$ such that $t(a_1,\dots,a_s)\bmod p\in[-T_1,T_1]\times[-T_2,T_2]\times\dots\times[-T_s,T_s]$ holds? If we had $p^s-p^{s-1}$ different choices of $t$ then pigeonhole works. Since $p\ll p^s-p^{s-1}$ is this some kind of randomized pigeonhole or just an argument assuming $(a_1,\dots,a_s)$ as a straight line in $\Bbb Z^s$?


Assuming we have the needed result as in Lemma $4$ then my main query is following (which satisfy pigeonhole):

(1) Can we replace real numbers $T_1,\dots,T_s$ by intervals $I_1=[T_0,T_1]$, $I_2=[T_1,T_2]$,$\dots$, $I_s=[T_{s-1},T_s]$ and now have following lemma?

For any real intervals $I_1=[T_0,T_1]$, $I_2=[T_1,T_2]$,$\dots$, $I_s=[T_{s-1},T_s]$ with $$0\leq T_0,T_1,\dots,T_s<p,\quad1\leq|I_1|,\dots,|I_s|<p,\quad\prod_{i=1}^s|I_i|> p^{s−1}$$ and any integers $a_1,\dots,a_s$ there is an integer $t$ coprime to $p$ such that $$\min_{ k\in\Bbb Z}|ta_i − kp|\in I_i,\quad\quad i = 1,\dots,s$$ holds.

My second query is following (which also allows pigeonhole combinatorics to work):

(2) Why cannot I replace $\min_{ k\in\Bbb Z}|ta_i − kp|$ by $\min_{\substack{ k\in\Bbb Z\\ta_i-kp\geq0}}(ta_i − kp)$ or $\min_{\substack{ k\in\Bbb Z\\ta_i-kp\leq0}}(-ta_i + kp)$?

$\endgroup$
  • $\begingroup$ I think you meant $||a_i t||$ as in the linked paper. $\endgroup$ – i707107 Mar 5 '17 at 0:59
  • $\begingroup$ Also, $a$ should be replaced by $a_i$, so that $\min_{t\in \mathbb{Z}} |a_i - tp|$ $\endgroup$ – i707107 Mar 5 '17 at 1:52
  • $\begingroup$ @i707107 thank you corrected. Is (1) possible and in (2) can we replace? $\endgroup$ – user94040 Mar 5 '17 at 16:39
1
$\begingroup$

First, we prove the Lemma 4. Considering the linked paper (that was in the previous version of this question), $p$ must be a prime number.

We apply the pigeon-hole principle in the following way:

Take $T_i'$ to satisfy $T_i\leq T_i'$ and $p/T_i' \in \mathbb{N}$. This is possible without changing $T_i$ too much (still satisfying $T_i\asymp T_i'$). Subdivide the interval $[0,p]$ into $p/T_i'$ equal pieces. Considering the subdivision in each component $i$, we have a subdivision of the $s$-cube $[0,p]^s$ into $N=\prod (p/T_i')$ equal boxes. Now given $\prod T_i > p^{s-1}$ gives $\prod T_i'> p^{s-1}$. Then the number of boxes inside $[0,p]^s$ with the subdivision is $<p$. Consider the following for $t=0, 1, \ldots, p-1$: $$ (a_1, \ldots, a_s) t \ \mathrm{mod} \ p, $$ Here comes the key argument in the pigeon-hole principle.

Since the number of boxes $N$ is $<p$, there must be two distinct $t_0, t_1 \in \{0, 1, \ldots p-1\}$ such that $(a_1, \ldots, a_s) t_0 \ \mathrm{mod} \ p$ and $(a_1, \ldots , a_s) t_1 \ \mathrm{mod} \ p$ lie in the same box. Take $t=|t_0-t_1|$, then $0<t<p$ so that $(t,p)=1$ and for each $i=1, \ldots, s$, $$ a_i|t_0-t_1| \ \mathrm{mod} \ p \textrm{ is in the interval } [-T_i' , T_i']. $$

Now for your questions, this argument does not guarantee the specific location of $(a_1, \ldots , a_s) t$ modulo $p$ other than just a box around the origin. So, in your setting of specified box, it might not be possible. With a little care, you can make a counterexample (e. g. with $s=2$, $p=37$, $a_1=1$, $a_2=2$, $|I_1|=37/6$, $|I_2|=37/6$ where $|I|$ is the length of the interval $I$).

For using $\min_{k\in \mathbb{Z} \\ a_i t - kp\geq 0} (a_i t - kp)$ or $\min{k\in\mathbb{Z}\\ a_i t - kp \leq 0 } (-a_i t + kp)$, we also see that the calculation modulo $p$ does not guarantee the specific sign of $a_i t - kp$. So, it is not possible to replace by those.

$\endgroup$
  • $\begingroup$ $s=2$, $p=37$, $a_1=1$, $a_2=2$, $T_1=37/6$, $T_2=37/6$ is not a valid example. I assume you choose $T_0=0$. Then intervals are $I_1=[0,37/6]$ and $I_2=[37/6,37/6]$ and so $|I_1|=37/6$ and $|I_2|=0$. So we have two violations $|I_2|=0<1$ and $|I_1||I_2|=0<37^{s-1}=37$. $\endgroup$ – user94040 Mar 5 '17 at 21:52
  • $\begingroup$ If you are saying $I_1'=[0,37/6]$ and $I_2'=[37/6,74/6]$ then we have $4(a_1,a_2)\bmod 37\equiv 4(1,2)\bmod 37\equiv(4,8)\in[0,37/6]\times[37/6,74/6]$. $\endgroup$ – user94040 Mar 5 '17 at 22:04
  • $\begingroup$ What I wanted to say is that length of $I_1$ and $I_2$ are $37/6$. $\endgroup$ – i707107 Mar 5 '17 at 23:27
  • $\begingroup$ In my example $|I_1'|=|I_2'|=37/6$. $\endgroup$ – user94040 Mar 6 '17 at 6:41
  • $\begingroup$ If the intervals are $I_1= [0, 37/6]$, $I_2 = [37 \cdot \frac 56, 37]$, then $I_1\times I_2$ does not contain any point of $(1,2)t$ mod $37$. $\endgroup$ – i707107 Mar 6 '17 at 16:47

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.