0
$\begingroup$

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.

  • 0
    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...?2010-11-14
  • 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.2010-11-14
  • 0
    Yes thanks, I corrected this mistake2010-11-14
  • 0
    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.2010-11-15
  • 0
    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}$.2010-11-15
  • 0
    @TCL The notation $\lor$ means "or" (rather than "join" or "maximum").2010-11-15

2 Answers 2

2

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 $\{ sx \},\{ rx\}$ belong to the same subinterval.
  3. Then prove that $s-r$ is your solution.
0

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\}$?

  • 0
    Well it tells us that $\{(r_1-r_2)x\} \approx 0$, right?2010-11-14
  • 0
    Right, and that's exactly what you want to prove.2010-11-14
  • 0
    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$2010-11-14
  • 0
    @user3123 All the computations are modulo 1. A small negative number is physically a number very close to 1.2010-11-15