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!

Improve this question
$\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$
    – Charles Matthews
    Commented 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$
    – Gerhard Paseman
    Commented 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
    Commented 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$
    – Gerhard Paseman
    Commented Jan 25, 2012 at 19:57
  • $\begingroup$ $\alpha$ and $\beta$ are also probabilities, but I'm not sure that is too important $\endgroup$
    – drewbarbs
    Commented Jan 25, 2012 at 19:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .