0
$\begingroup$

Hi all, I was wondering whether you could help me understand a part in a proof that is assumed to be an "obvious detail" by the author, but that I can't wrap my head around. Essentially, as far as I can understand, there are two values $A$ and $B$, and we want to prove that:

$\Bigg|A-B \; \Bigg| > \frac{1}{p}$

for some polynomial $p$ (the actual value of $p$ is unimportant).

We reach a point in the proof where we have shown that

$\Bigg |\alpha \cdot A- \beta \cdot B \; \Bigg| \geq \frac{2}{p}$

and that

$\Bigg|\; \alpha - \beta\; \Bigg| < \frac{1}{3p^2} $

The next line of the proof (where I stop understanding) concludes that

$\Bigg |\beta \cdot A- \beta \cdot B \; \Bigg| > \frac{1}{p}$

from which point we can make several conclusions.

Can anyone explain how to arrive at the last inequality from the previous ones? Is it possible, or am I missing some additional information somewhere?

Thanks!

$\endgroup$
9
  • $\begingroup$ I think there must be an upper bound for A somewhere. The step troubling you should be the triangle inequality applied, but to conclude that the term you discard is at most 1/*p* you do need something. $\endgroup$ Jan 25, 2012 at 19:48
  • $\begingroup$ You need some property of A. Knowing that A is an integer would help. Gerhard "Ask Me About System Design" Paseman, 2012.01.25 $\endgroup$ Jan 25, 2012 at 19:53
  • $\begingroup$ I'm sorry, probably an important detail is that A and B are probabilities, so they are bounded above by 1. I'm having trouble understanding how we could replace $\alpha$ in the 3rd to last inequality by $\beta$ (giving us the last inequality) $\endgroup$
    – drewbarbs
    Jan 25, 2012 at 19:53
  • $\begingroup$ Actually, Charles's suggestion is better than mine. Having A integral would work for a different system of inequalities, similar but not identical to what is given. Gerhard "Ask Me About System Design" Paseman, 2012.01.25 $\endgroup$ Jan 25, 2012 at 19:57
  • $\begingroup$ $\alpha$ and $\beta$ are also probabilities, but I'm not sure that is too important $\endgroup$
    – drewbarbs
    Jan 25, 2012 at 19:57

1 Answer 1

0
$\begingroup$

If we truly have (as you say in the comments) that $0 \leq \alpha,\beta, A, B \leq 1$ then $$ \frac2p \leq |\alpha A - \beta B| \leq 1 $$ implying that $p \geq 2$.

This in turn means that $\frac{A}{3p^2} \leq \frac1{3p^2} \leq \frac1{6p}$.

Letting $$ \epsilon=\beta-\alpha $$ and using $$ \left| \beta \cdot A - \beta \cdot B \right| = \left| \alpha \cdot A + \epsilon \cdot A- \beta \cdot B \right| $$ plus the triangle inequality shows that your condition is easily satisfied.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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