# Intersection of intervals

Let $a\in\mathbb{N}_{\geq3}$.

How can one prove that $$\bigcap_{i = 1}^{a} \bigcup_{j = 0}^{i-1} \left[\frac{1+aj}{i},\frac{a(j+1)-1}{i}\right] = \varnothing,$$ where $\varnothing$ is the empty set?

Example for $a=5$:

Red is the interval, Yellow are the gaps between the intervals that cause the intersection to be a null set, white gaps do not effect the intersection.

-
What do you mean by "null set"? Do you mean an empty one? Or one with measure $0$? Or something else? –  dfeuer May 22 '13 at 5:34
null set=empty set –  Maazul May 22 '13 at 5:34
@Stromael $a$ is a fixed positive integer. –  Andres Caicedo May 22 '13 at 5:45
Shouldn't the intersection be from $1$ to $a$, then? –  Stromael May 22 '13 at 5:49
Well, we'll have to check with the original asker, but I think I got the formula to match the diagram (if my edit passes peer review, that is). –  dfeuer May 22 '13 at 6:56

First, a lemma. Let $a\ge 1$ be an integer and let $x\in[0,1]$. Then there exist integers $m$ and $n$ such that $1\le n\le a$ and $|n x - m| < \frac{1}{a}$. To prove this, let $z = \exp(2\pi i x)$ and consider the numbers $1, z,z^2,\ldots,z^a$ in the complex plane. Let $\phi_k = \arg(z^k)$ with $0\le \phi_k<2\pi$. Reorder $\phi_0,\ldots,\phi_a$ so that $\phi_{\pi(0)}\le \phi_{\pi(1)}\le\ldots\le\phi_{\pi(a)}$ for an appropriate permutation $\pi$ of $0,\ldots,a$. Observe

$\ \ \sum_{k=1}^a (\phi_{\pi(k)} - \phi_{\pi(k-1)}) < 2\pi$.

Since there are $a$ non-negative terms on the left hand side, at least one of these terms is bounded above by $\frac{2\pi}{a}$. Thus,

(*) $\ \ 0 \le \arg(z^{\pi(k)}) - \arg(z^{\pi(k-1)}) = \arg(z^{{\pi(k)}-{\pi(k-1)}}) < \frac{2\pi}{a}$

for some $k\in\{1,\ldots,a\}$. Let $n = |\pi(k)-{\pi(k-1)}|$. Note $1\le n\le a$. By definition of $z$ and (*) above, it follows $|n x - m| < \frac{1}{a}$ for some integer $m$.

Now the main theorem is easy. Let

$S = \cap_{i=1}^a \cup_{j=0}^{i-1} \left[\frac{1+aj}{i},\frac{a(j+1) -1}{i}\right].$

Suppose $\beta \in S$. With $i=1,j=0$, we see $1\le \beta \le a-1$. Let $x=\beta/a$ and apply the lemma above. Then there are integers $m,n$ with $1\le n \le a$ such that

(**) $\left| n \frac{\beta}{a} - m \right| < \frac{1}{a}$.

Thus, $n\frac{\beta}{a}$ is within $\frac{1}{a}$ of some integer.

Now focus on the union term with $i=n$ in the definition of $S$:

$T = \cup_{j=0}^{n-1} \left[\frac{1+aj}{n},\frac{a(j+1) -1}{n}\right]$.

Observe that $T \subset \{y\in\mathbb{R}: \left|n \frac{y}{a}\right| \ge \frac{1}{a}\}$. In other words, for every member $y$ of $T$, $n \frac{y}{a}$ is at least $\frac{1}{a}$ from the closest integer. Recalling (**), we see $\beta \notin T$. By definition of $S$ and $T$, $S\subset T$, so $\beta\notin S$.

-
Would appreciate some detail on how $\beta \in \left[ \frac{-1+am}{n}, \frac{1+am}{n}\right]$ implies $\beta \notin \cup_{j=0}^{n-1} \left[\frac{1+aj}{n},\frac{a(j+1) -1}{n}\right]$? –  Maazul May 22 '13 at 17:58
And forcing $i=n$ means that there exists some $m$ for any $n$ with the condition $1\le n\le a$. Is this true? or does the lemma hold for some combinations of $n$ and $m$? –  Maazul May 22 '13 at 18:01
I edited the final step for clarity. Stare at the definitions of $S$ and $T$. The set $T$ is carefully constructed so that if $y\in T$, then $n \frac{y}{a}$ is at least $\frac{1}{a}$ from the nearest integer. –  Will Nelson May 22 '13 at 20:25
Thanks mate... :) –  Maazul May 22 '13 at 21:31