# Essential clarifications on application of pigeonhole principle

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)$?

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

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.

• $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$. – user94040 Mar 5 '17 at 21:52
• 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]$. – user94040 Mar 5 '17 at 22:04
• What I wanted to say is that length of $I_1$ and $I_2$ are $37/6$. – i707107 Mar 5 '17 at 23:27
• In my example $|I_1'|=|I_2'|=37/6$. – user94040 Mar 6 '17 at 6:41
• 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$. – i707107 Mar 6 '17 at 16:47