Take the 2-minute tour ×
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.

Let $x \in \mathbb{R} \backslash \mathbb{Q}, x>0$ and $q \in \mathbb{N}, q>0$, prove that there is an $r \in \mathbb{N}, r>0$ with: $r \cdot x - \left\lfloor r \cdot x \right\rfloor < \frac{1}{q}$ or $1-(r \cdot x - \left\lfloor r \cdot x \right\rfloor) < \frac{1}{q}.$

I was given the hint to divide the sequence $a_r := r \cdot x - \left\lfloor r \cdot x \right\rfloor \in [0,1)$ into q intervals $[0,\frac{1}{q}),[\frac{1}{q},\frac{2}{q}),\ldots,[\frac{q-1}{q},1)$ and use the pigeonhole principle, but I cannot see how this would help to the problem.

share|improve this question
    
The pigeonhole principle tells you that if you take $k+1$ elements of the sequence $a_r$, two of them will end up in the same interval. These correspond to two distinct multiples of $x$ that end up "close together". What can you do with them...? –  Rahul Nov 14 '10 at 19:13
1  
Currently (until the next edit), $[0,1)$ has been divided up into $q$ intervals and not $k$ intervals. Maybe this is causing you some confusion. –  Derek Jennings Nov 14 '10 at 19:27
    
Yes thanks, I corrected this mistake –  Listing Nov 14 '10 at 19:30
    
I think the problem is not right. You cannot have a positive number $y$ such that $y<\frac{1}{q}\vee 1 -y<\frac{1}{q}$. Try $q=4$ for example. –  TCL Nov 15 '10 at 0:23
    
Ok. I guess the author meant $y<\frac{1}{q}$ or $1-y<\frac{1}{q}$. The way he wrote it, it looks like $y<(\frac{1}{q}\vee 1)-y<\frac{1}{q}$. –  TCL Nov 15 '10 at 1:50
show 1 more comment

2 Answers

up vote 2 down vote accepted

Write $\{ x\}$ for $x-\lfloor x\rfloor$.

  1. Prove that $\{ rx\}$ for $r=0,1,\cdots,q$ are all distinct. (Here is where you use the condition that $x$ is irrational.)
  2. Using pigeonhole principle, find integers $r,s, 0\le r<s,$ such that
    $\{ sx \},\{ rx\}$ belong to the same subinterval.
  3. Then prove that $s-r$ is your solution.
share|improve this answer
add comment

Let's use the notation $\{x\} = x - \lfloor x \rfloor$. We can think of $\{\cdot\}$ as a function $\mathbb{R} \longrightarrow \mathbb{R}/\mathbb{Z}$, indeed a homomorphism of groups (with addition as the group operator). That means that $\{x + y\} = \{x\} + \{y\}$, or what matters more in your case, $\{x - y\} = \{x\} - \{y\}$.

Now suppose $\{r_1x\},\{r_2x\}$ are close, what does this say about $\{(r_1-r_2)x\}$?

share|improve this answer
    
Well it tells us that $\{(r_1-r_2)x\} \approx 0$, right? –  Listing Nov 14 '10 at 19:24
    
Right, and that's exactly what you want to prove. –  Yuval Filmus Nov 14 '10 at 19:52
    
But I don't see where the case occurs that the result is $1-(r \cdot x - \left\lfloor r \cdot x \right\rfloor)$, nor do I think that $(a x-\lfloor a x\rfloor)-(b x-\lfloor b x\rfloor) = (a-b) x -\lfloor (a-b) x\rfloor$ –  Listing Nov 14 '10 at 20:48
    
@user3123 All the computations are modulo 1. A small negative number is physically a number very close to 1. –  Yuval Filmus Nov 15 '10 at 3:34
add comment

Your Answer

 
discard

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.