Proving a statement about covered intervals

  • Thread starter Thread starter littlemathquark
  • Start date Start date
  • Tags Tags
    Interval problem
littlemathquark
Messages
204
Reaction score
26
New user has been reminded to always show their work on schoolwork problems.
Homework Statement
The rational number p/q in the inerval (0,1) covered by the closed interval [p/q-1/4q^2, p/q+1/4q^2]. How do I prove that none of these intervals cover the number (sqrt{2}) /2?
Relevant Equations
The rational number p/q in the inerval (0,1) covered by the closed interval [p/q-1/4q^2, p/q+1/4q^2]. How do I prove that none of these intervals cover the number (sqrt{2}) /2?
I need any idea. I haven't made any progress in solving the problem.
 
Physics news on Phys.org
The idea is that if ##0 < \frac p q < \frac {\sqrt 2}{2}##, then ##\frac p q + \frac 1 {4q^2} < \frac {\sqrt 2}{2}##. And, if ##1 > \frac p q > \frac {\sqrt 2}{2}##, then ##\frac p q - \frac 1 {4q^2} > \frac {\sqrt 2}{2}##.

Can you show that?
 
I used Dirichlet approximation theorem but I can't find any progression.
 
Looks tricky.
 
  1. ##\alpha := \sqrt{2}/2 ## is a root of ##f(x) = 2x^2-1##.
  2. For ## x\in (\alpha - 1/5, \alpha +1/5) ## we have ##(\frac{1}{2} <) f'(x) < \frac{40}{11} =: C < 4 ##.
  3. Conclude by Lagrange MVT that
    <br /> |x-\alpha| &lt; \frac{1}{5} \Rightarrow |f(x)-f(\alpha)| = |2x^2-1| &lt; C|x-\alpha|<br />
Claim. We have
<br /> \left\lvert \frac{m}{n}-\alpha \right\rvert &gt; \frac{1}{4n^2}<br />
for all ##m,n\in\mathbb N##. Then it follows that either
<br /> \alpha &gt; \frac{m}{n} + \frac{1}{4n^2}\quad\mbox{or}\quad \frac{m}{n}-\frac{1}{4n^2}&gt; \alpha.<br />

Proof of claim. The nontrivial case is ##|m/n - \alpha| < 1/5##. Then
<br /> \left\lvert f\left(\frac{m}{n}\right)\right\rvert = \left\lvert 2\frac{m^2}{n^2}-1 \right\rvert &lt; C\left\lvert \frac{m}{n}-\alpha \right\rvert \Rightarrow n^2\left\lvert 2\frac{m^2}{n^2}-1 \right\rvert &lt; Cn^2\left\lvert \frac{m}{n}-\alpha \right\rvert.<br />
Because ##f## has no rational roots, we conclude ## n^2\left\lvert 2\frac{m^2}{n^2}-1 \right\rvert \geqslant 1 ## and therefore
<br /> Cn^2\left\lvert \frac{m}{n}-\alpha \right\rvert &gt; 1 \Rightarrow \left\lvert \frac{m}{n}-\alpha \right\rvert &gt; \frac{1}{Cn^2} &gt; \frac{1}{4n^2}.<br />

This is an adaptation of a proof of Liouville's theorem. The trick is finding a small enough interval around ##\alpha## such that you get a suitable upper bound for the derivative.
 
Last edited:
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top