Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

enter image description here

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.

share|cite|improve this question
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. – Andrés E. 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
up vote 3 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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