1. Quasi-metric spaces

As everyone knows, a metric space is a set X together with a symmetric non-negative function d : X ×X → ℝ^{+} which is non-degenerate (thus d(x, y) = 0 if and only if x = y) and which obeys the triangle inequality

d(x, z) ⩽ d(x, y) + d(y, z)  (1.1) triangle

for all x, y, z ∈ Z.

There are also some variants of a metric space:

• A quasi-metric space with loss K, in which the triangle inequality is replaced by the variant d(x, z) ⩽ K(d(x, y) + d(y, z)) for some K ⩾ 1.

• An ultrametric space, in which the triangle inequality is replaced by the variant d(x, z) ⩽ max(d(x, y), d(y, z)).

• A quasi-ultrametric space with loss K, in which the triangle inequality is re-

placed by the variant d(x, z) ⩽ K max(d(x, y), d(y, z)). Clearly these concepts are all related; an ultrametric space is a metric space, and a

quasi-ultrametric space with loss K is a quasi-metric space with loss K. In the converse direction, every quasi-metric space with loss K is a quasi-ultrametric space with loss 2K; in particular, a metric space is a quasi-ultrametric space with loss 2. Also, if d is a quasi-ultrametric with loss K, then for any α > 0, d^{α} is a quasi-ultrametric with loss K^{α}.

It is of interest to see to what extent quasi-metrics or quasi-ultrametrics obey the triangle inequality. It turns out that quasi-ultrametrics behave almost like metrics as long as the loss is less than the golden ratio ϕ := \frac{1+\sqrt{5}}{2}.

tri Proposition 1.1. Let d be a quasi-ultrametric with loss K for some K ⩽ ϕ (in particular K < 2). Then for any x_{1}, …, x_{n} ∈ X we have

d(x_{1}, x_{n}) ⩽ K^{2}(d(x_{1}, x_{2}) + … + d(x_{n−1}, x_{n})).

Proof. We fix K and C_{K} and induct on n. For n ⩽ 2 the claim is trivial.Now suppose n > 2 and the claim has already been proven for smaller n.

Without loss of generality we may assume that d(x_{i}, x_{i+1}) is strictly positive for all 1 ⩽ i < n. Write A := d(x_{1}, x_{2}) + … + d(x_{n−1}, x_{n}); our task is to show that d(x_{1}, x_{n}) ⩽ K^{2}A. Let 1 ⩽ j < n be the largest integer such that

A_{−} := d(x_{1}, x_{2}) + … + d(x_{j−1}, x_{j}) < A/2

or equivalently the smallest integer such that

A_{+} := d(x_{j+1}, x_{j+2}) + … + d(x_{n−1}, x_{n}) ⩽ A/2.

Suppose first that A_{−} ⩾ A(1 − \frac{1}{K}). Then from the induction hypothesis we have

d(x_{1}, x_{j}) ⩽ K^{2}A_{−} ⩽ K^{2}A/2

and

d(x_{j}, x_{n}) ⩽ K^{2}(A − A_{−}) ⩽ K^{2}A/K

and then the claim follows from the quasi-ultratriangle inequality. Similarly if A_{+} ⩾ A(1 − \frac{1}{K}). Thus we may assume that

A_{+}, A_{−} < A(1 − \frac{1}{K}).

By symmetry we can assume A_{+} ⩾ A_{−}. From induction hypothesis we have

d(x_{1}, x_{j}) ⩽ K^{2}A_{+}; d(x_{j+1}, x_{n}) ⩽ K^{2}A_{−}

while

d(x_{j}, x_{j+1}) ⩽ A − A_{+} − A_{−}

so from two applications of the quasi-ultratriangle inequality

d(x_{1}, x_{n}) ⩽ K max(K max(K^{2}A_{+}, A − A_{+} − A_{−}), K^{2}A_{−})
⩽ K^{2} max(K^{2}A_{+}, A)
⩽ K^{2}A max(K^{2} − K, 1).

But since K ⩽ ϕ, then K^{2} − K ⩽ 1, and the claim follows.

It seems that the golden ratio is in fact sharp here, by looking at a Cantor set formed by removing the middle ϕ^{−2} of each interval and using the usual Euclidean metric (raised to a power 1 + ε); we omit the details.

As a consequence we see that quasi-ultrametrics (and hence quasimetrics) are comparable to powers of metrics (a result first observed by Aoki ^{\underline{aoki}} [1] and Rolewicz ^{\underline{rolewicz}} [3] for quasi-norms, and later by Macias and Segovia ^{\underline{macias}} [2] for quasi-metrics).

qum Corollary 1.2. Let d be a quasi-ultrametric with loss K. Then there exists a metric d′

such that

K^{−2}d(x, y) ⩽ d′(x, y)^{log_{ϕ} K} ⩽ d(x, y)

for all x, y ∈ K, where log_{ϕ} K := log K/ log ϕ.

Proof. By replacing d by d^{log_{ϕ} K} we may take K = ϕ. The claim then follows by setting

d′(x, y) := inf{d(x_{1}, x_{2}) + … + d(x_{n−1}, x_{n}) : x_{1} = x, x_{n} = y, n ⩾ 2}

and using Proposition ^{\underline{tri}} 1.1 we obtain the result.

One can make the slight improvement of replacing the golden ratio ϕ with 2 if one works with translation-invariant metrics or quasi-ultrametrics on a vector space V.

Lemma 1.3. Let d be a translation-invariant quasi-ultrametric on a vector space V with loss 2. Let f_{1}, …, f_{N} ∈ V be such that d(0, f_{n}) ⩽ 2^{k_{n}}A for n = 1, …, N, some A > 0 and some integers k_{1}, …, k_{N}, and suppose that 2^{k_{1}} + … + 2^{k_{N}} ⩽ 2^{k}. Then d(0, f_{1} + … + f_{N}) ⩽ 2^{k}A.

Proof. We induct on N. The case N = 1 is trivial. Now suppose N > 1 and the claim has already been proven for N − 1. Then we order k_{1} ⩾ … ⩾ k_{N}, and normalise k_{N−1} = −1 and A = 1. Then d(0, f_{N−1}), d(0, f_{N}) ⩽ 1/2 and hence by the preceding discussion d(0, f_{N−1} + f_{N}) ⩽ 1. Now observe that 2^{k_{1}} + … + 2^{k_{N−2}} + 1 is equal to 2^{k_{1}} + … + 2^{k_{N}} rounded up to the nearest integer and is thus also less than 2^{k}. The claim now follows from the induction hypothesis.

Corollary 1.4. Let d be a translation-invariant quasi-ultrametric on a vector space V with loss K. Then there exists a translation-invariant metric d′ such that

K^{−1}d(x, y) ⩽ d′(x, y)^{log_{2} K} ⩽ d(x, y)

for all x, y ∈ K.

Proof. By replacing d with d^{1/ log_{2} K} we may take K = 2. Observe that for any f_{1}, …, f_{N}, if we set

A := d(0, f_{1}) + … + d(0, f_{N})

and then let 2^{k_{n}} be the least integer such that d(0, f_{n}) ⩽ 2^{k_{n}}, then 2^{k_{1}} + … + 2^{k_{n}} ⩽ 2, and so from the previous lemma we have

d(0, f_{1} + … + f_{n}) ⩽ 2A = 2(d(0, f_{1}) + … + d(0, f_{N})).

By translation invariance, this implies

d(x_{1}, x_{n}) ⩽ 2(d(x_{1}, x_{2}) + … + d(x_{n−1}, x_{n})).

The claim now follows as in Corollary ^{\underline{qum}} 1.2.

Specialising to quasinorms, we have

Corollary 1.5. Let ∥∥ be a quasinorm on a vector space V with loss K ⩾ 1, in the sense that ∥∥ is non-negative, non-degenerate, homogeneous, and obeys the quasitriangle inequality

∥x + y∥ ⩽ K(∥x∥ + ∥y∥).

Let p := 1/ log_{2}(2K). Then there exists a quasinorm ∥∥_{∗} with the bounds

(2K)^{−1}∥x∥ ⩽ ∥x∥_{∗} ⩽ ∥x∥

such that

∥x + y∥_{∗}^{p} ⩽ ∥x∥_{∗}^{p} + ∥y∥_{∗}^{p}.

Proof. Apply the previous corollary with d(x, y) := ∥x−y∥, which is a quasi-ultrametric with loss 2K, and then set ∥x∥_{∗} = d′(0, x)^{log_{2} 2K}. An inspection of the definition of d′ reveals that ∥x∥_{∗} is homogeneous, and the remainder of the claims are immediate.

References

aoki [1] T. Aoki, Locally bounded linear topological spaces, Proc. Imp. Acad. Tokyo 18 (1942), 588–594. macias [2] R. Macias, C. Segovia, Lipschitz functions on spaces of homogeneous type, Adv. Math. 33 (1979),

257–270.

rolewicz [3] S. Rolewicz, Metric linear spaces, P.W.N. Polish Scientific Publishers Warsawa, 1984.

Department of Mathematics, UCLA, Los Angeles CA 90095-1555, USA.

  E-mail address: tao@math.ucla.edu