1
$\begingroup$

In Hyperbolicity, CAT(-1)-spaces and the Ptolemy Inequality, there is a short proof of a simple statement:

Let $(X, d)$ be an arbitrary metric space. Then $(X, \sqrt{d})$ satisfies the Ptolemy inequality.

Where the Potlemy Inequality is

Let $w, x, y, z$ be points in a space. For a Ptolemaic Distance $d$, the following inequality holds: $d(w, y) \cdot d(x, z) \leq d(w, x) \cdot d(y, z) + d(w, z) \cdot d(x, y)$

See also on Wikipedia.

From here on, let $p_1 = d(w, y), p_2 = d(x, z)$ and $q_1 = d(w, x), q_2 = (x, y), q_3 = d(y, z), q_4 = d(z, w)$

Question 1:

The proof begins by stating that it only needs to show this property:

$\begin{equation} \sqrt{p_1p_2} \leq \sqrt{q_1 q_3} \sqrt{q_2 q_4} \end{equation}$

Now, you may notice that this almost equals the definitions for the ptolemaic inequality given above, except that the right hand side is now a product instead of a sum. Thus, in my mind, the implication

$ \sqrt{p_1p_2} \leq \sqrt{q_1 q_3} \sqrt{q_2 q_4} \implies \sqrt{p_1p_2} \leq \sqrt{q_1 q_3} + \sqrt{q_2 q_4}$,

where the latter inequality is actually the ptolemaic inequality, is only valid if
$ \sqrt{q_1 q_3} \sqrt{q_2 q_4} \leq \sqrt{q_1 q_3} + \sqrt{q_2 q_4}$, which is not true generally and only for restricted ratios of the two roots, visualized here. However, this restricted ratio does not apply here: If we fix $q_1$ and $q_2$ and grow $q_3$ arbitrarily large, $q_4$ also grows arbitrarily large. For a concrete example, if $q_i = 5$, the implication already doesn't work.

So why is it sufficient to show the inequality with products?

Interlude: Proof Details

To understand the proof, I broke it down into very simple steps:

  1. wlog, $p_1 \leq q_1 + q_2 \leq q_3 + q_4$ (From the triangle inequality)
  2. wlog, $p_2 \leq q_2 + q_3 \leq q_1 + q_4$ (From the triangle inequality)

  3. Define $p_1' = q_1 + q_2$.

  4. Now, $p_1' \geq p_1$ by definition (1).
  5. Define $p_2' = q_2 + q_3$.
  6. Now, $p_2' \geq p_2$ by definition (2).

  7. Choose (wlog) $q_4'$ such that:

    1. $q_3 + q_4' = q_1 + q_2$
    2. $q_2 + q_3 \leq q_1 + q_4'$
  8. By (1) and (7.1), $q_4' \leq q_4$

  9. Deduce:

    1. $q_1 - q_3 = q_4' - q_2$ by (7.1)
    2. $q_3 - q_1 \leq q_4' - q_2$ by (7.2)
    3. $-(q_1 - q_3) \leq q_4' - q_2$, identical to previos point.
  10. Deduce:

    1. $q_4' - q_2$ is positive, by (9.1) and (9.3).
    2. $q_4' q_2$ from previous point.
  11. Define $\epsilon := q_1 - q_3$.

  12. From (9.1) and (10.1), deduce

    1. $\epsilon \geq 0$
    2. $q_1 \geq q_3$
  13. Also, note that $q_1 = q_3 + \epsilon$, identical to (11).

  14. Furthermore, $q_4' = q_2 + \epsilon$ by (13) and (9.1).

From here, the proof is nearly done. From nowhere, it gives the (obviously correct) inequality

$2q_2q_3 \leq 2\sqrt{q_3(q_3 + \epsilon)q_2(q_2+\epsilon)}$

Question 2:

Then, the claim is made that the previous inequality implies ($\implies$)

$ \sqrt{(q_2+q_3+\epsilon)(q_2+q_3)} \leq \sqrt{q_3(q_3 + \epsilon)} + \sqrt{q_2(q_2+\epsilon)} $

Which I can't follow at all. Why does this follow from the previous inequality? Again, theres the strange change from addition to multiplication.

This happens once more when that inequality is said to be equivalent ($\Leftrightarrow$) to

$\sqrt{p_1'p_2'} \leq \sqrt{q_1 q_3} \sqrt{q_2 q_4}$

Now, I can see how the roots simplify individually, but there is, again, this change of operator. Since there is a claim of equivalence between those two, I believe this would imply that $\sqrt{q_1 q_3} \sqrt{q_2 q_4} = \sqrt{q_1 q_3} + \sqrt{q_2 q_4} $, wouldn't it? And that seems quite clearly nonsensical to me.

Finally, that last inequality implies the one I asked about in Question 1 - this is clear to me. It is those steps in between, particularly the change of operators, which confuses me greatly.

Thank you!

$\endgroup$
1
$\begingroup$

We suffice to consider the case where $p_i,\ 1\leq i\leq 4$ are in $\mathbb{S}^1$.

Assume that $|p_1-p_2|=\varepsilon,\ |p_2-p_3|=x,\ |p_3-p_4|=y,\ |p_4-p_1|=A$.

We will consider the case where $\varepsilon<x<y<A$ and $\varepsilon +A<x+y,\ \varepsilon+x<y+A$ :

We must show that $$ \sqrt{\varepsilon +A}\sqrt{\varepsilon +x}\leq \sqrt{\varepsilon y}+\sqrt{x A}, $$

which is equivalent to $$ \varepsilon +A+x\leq y +2\sqrt{\frac{x}{\varepsilon}}\sqrt{Ay} $$

which is followed from $ \varepsilon +A\leq x+y $

All remaining cases can be proved similarly.


[Add] Consider four points $p_i$ in general space $(X,d)$ s.t. $d_{ij} = d(p_i,p_j) $

So we must show that $\sqrt{ d_{13}d_{24} }\leq \sqrt{d_{23}d_{14}} +\sqrt{ d_{12}d_{34}} $

When $$d_{12}+d_{23} +d_{34} + d_{41}=2\pi l\ \ast,$$ then we let $D = \frac{1}{l}d$ so that $D$ is a metric

When $D_{ij}=\frac{d_{ij}}{l}$, then we have to prove $$\sqrt{ D_{13}D_{24} }\leq \sqrt{D_{23}D_{14}} +\sqrt{ D_{12}D_{34}} $$

Case 1 : $Q_i\in (\mathbb{S}^1,|\ |)$ s.t. $|Q_i-Q_{i+1}|=D_{i(i+1)},\ 1\leq i\leq 3$ and $|Q_4-Q_1|=D_{41}$

Here $$D_{13}\leq {\rm min}\ \{ D_{12}+D_{23} ,D_{14}+D_{43}\} =|Q_{1}-Q_{3}|$$ by triangle inequality

Hence the above argument holds.

Case 2 : Consider $\ast$. $D_{12}>\pi$, then $$D_{12}>D_{23}+D_{34}+D_{41}$$ which is a contradiction. Hence we have realization on circle.

$\endgroup$
  • 1
    $\begingroup$ I've accepted your answer a while back because it seemed sensible at first glance, but only now had the time to really get into the proof. I can see why the first inequality is sufficient to prove the statement and why it is equivalent to the second (which took me longer than I care to admit), and also why the second statement is correct, in the case you consider in your answer. However, I fail to see why: a) The restriction to S^1 is necessary, I did not use it while following your argument and b) how to generalize to points not on the unit circle if it truly is necessary. Thank you! $\endgroup$ – Kjeld Schmidt Jun 4 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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