Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
114
Chapter
9.
Metric
Transforms
of
LI-Spaces
We
are
interested
in
determining
some functions F preserving L
1
-embeddabi-
lity. For
this
purpose,
it
is convenient
to
introduce
the
class F consisting of
the
functions F :
~
---7
~
such
that
F(O)
= 0
and
F preserves
the
property
of
being
of
negative type;
that
is, F satisfies:
(X,
d)
is
of
negative
type
===?
(X, F(d)) is
of
negative
type
for
any
distance
space (X,
d).
Using Corollary 8.2.8,
we
can
prove
the
following
result
from
Assouad
[1979, 1980b]:
Theorem
9.0.3.
Let
(X,
d)
be
a distance space
and
let F
be
a
function
from
the
family:F.
Then,
(X,
d)
is
L1
-embeddable
===?
(X,
F(
d)) is L1-embeddable.
Proof.
Let
(X,
d)
be
a
distance
space which is L1-embeddable.
Then,
by Proposi-
tion
4.2.1, (X,
d)
is
an
isometric subspace
of
a
measure
semimetric
space
(AJ.L'
dJ.L)
for some
measure
space (fl, A,
f1-).
That
is,
there
is a
mapping
x
EX
.......
Ax
E
AJ.L
such
that
d(x,y) =
f1-(A
x
L'lAy)
for all
x,y
E
X.
Let
v:
AJ.L
---7
~
be
defined by
v(A)
:=
F(f1-(A))
for A E
AI-'"
We
apply
Corollary 8.2.8
to
the
pair
(AJ.L'
v). So, let d
v
,6
be
defined by (8.2.9);
that
is,
d
v
,6(A, B) = F(f1-(AL'lB)) for
A,
BE
AI-'"
Then,
the
distance
space
(AJ.L'
d
v
,6) is
the
metric
transform
of
(AJ.L'
dJ.L)
under
F
and
(X, F(d)) is
an
isometric subspace of
(AJ.L'
d
v
,6).
As
(AJ.L'
dJ.L)
is
of
negative
type
(because
it
is L
1
-embeddable)
and
as F E
F,
we
deduce
that
(AJ.L'
d
v
,6) is of negative type. Therefore, by Corollary 8.2.8,
(AJ.L,d
v
,6) is L1-embeddable and,
thus,
its isometric subspace
(X,F(d))
is L
1
-
embeddable
too. I
It
is therefore of crucial
importance
to
determine
which functions belong
to
:F.
Such functions have
been
completely characterized by Schoenberg [1938a];
we
will
mention
the
result
in
Theorem
9.1.4. For instance,
the
functions F(t) =
l~t'
10g(1 + t), 1 - exp(
-At)
(for A >
0)
(called
the
Schoenberg transform), t
a
(for
0<
Q
:::;
1) (called
the
power transform), all belong
to
:F.
It
turns
out
that
the
Schoenberg
transform
plays a
central
role in
the
description of
the
family
F.
We consider
the
Schoenberg
transform
in
detail
in Section 9.1. We show
that
it
preserves
the
negative
type
property
and,
thus,
L
1
-embeddability. More-
over,
we
describe all
the
functions preserving
the
negative
type
property
and,
as a consequence, several examples
of
functions preserving L1-embeddability.
In
Section 9.2,
we
consider
the
biotope
transform,
which is yet
another
way
of
9.1
The
Schoenberg Transform
115
deforming distances while retaining the property of being L
1
-embeddable.
In
Section 9.3,
we
consider
the
following question concerning
the
power transform:
Given an
arbitrary
semimetric space (X,
d),
determine
the
largest exponent a
for which
the
power transform (X,
dO)
enjoys some metric properties such
that
L
1
-
or L2-embeddability,
the
hypermetric property, etc.
9.1
The
Schoenberg
Transform
We
consider here
the
Schoenberg transform:
F(t)
1 exp(-.-\t)
fortEli4,
where ,\ is a positive scalar.
The
results presented here are based essentially on
the
work of Schoenberg.
In
a first step,
we
show
that
the
Schoenberg transform
preserves
the
negative
type
property; this fact was proved in Schoenberg [1938b].
Theorem
9.1.1.
Let
(X,
d)
be
a distance space. The following assertions are
equivalent.
(i)
(X,
d)
is
of
negative type.
(ii) The
symmetric
function p : X X X
llt,
defined by
p(x,y)
exp(-,\d(x,y»
forx,y
E
X,
is
of
positive type for all ,\ >
O.
(iii)
(X,I
- exp(
-'\d»
is
of
negative type for all ,\ >
O.
Proof. Note
that
the
properties involved in Theorem 9.1.1 are all of finite type,
they
hold if and only if they hold for any finite subset of
X.
Hence,
we
can
assume
that
X
is
finite, say X = {I,
...
, n}.
(i) (ii) Since (X,
d)
is of negative
type
then, by Theorem 6.2.2, (X,
Vd)
is
f
2
-embeddable, i.e., there exist x
(1
),
..•
,
x(n)
E
llt
m
(m
2:
1)
such
that
djk
=
(II
xU) - x
Ck
)
112)2
for all
j,
k
EX.
Let b
ll
...
, b
n
E
III
We
show
L
bjhexp
(-'\(11
x(j)
- x
Ck
)
112)2)
2:
O.
l::;j,k::;n
For this,
we
use the following classical identity:
116
Chapter
9.
Metric Transforms of LJ-Spaces
(Here,
i denotes
the
complex square root of unity.) Then,
m
L
bjble
exp (
-A(II
xU)
-
x(k)
112)2)
L bjbk
II
exp(
-A(X~)
-
X~k»)2)
:kE~
b
j
b
k
2-
m
1r-
T
IT
1
00
eXp(i...(5:.(X~EX
X~k»)::~
exp( _
u~
)duh
i,jEX
h=l
-=
4
= L b
j
b
k
2-
m
1r-
T
1""
...
1
00
exp(i...(5:.(x
Ul
X{kl)T
u)
U~)dUl'"
dUm
i,kEX
-00-00
is nonnegative.
(ii)
===}
(iii) Set
d~j
:=
exp(
-Ad
ii
) + exp(
-Ad
jj
) -
2exp(
-Adij» = 2(1 exp(
-Adi}))
for i, j
EX.
That
is,
d'
arises from p = exp( -
Ad)
by applying
the
inverse of
the
covariance mapping (defined
in
(5.2.5)). Applying
Lemma
6.1.14,
we
obtain
that
(X,
d') is
of
negative type, i.e.,
that
(X,
1 - exp( - Ad)) is
of
negative type.
(iii)
===}
(i) Let
b],
..
. , b
n
E
~
with
Li'=l
bi
=
O.
Then,
L
b;bj(1-exp(-Ad;j)~O,
lS,i<jS,n
since 1 exp( -
Ad)
is
of
negative type. By expanding in series the exponential
function,
we
obtain
for all
A >
O.
By dividing
by
A and, then, taking
the
limit when A
-+
0,
we
deduce
that
bibjd
ij
~
O.
This shows
that
(X,
d)
is of negative type. I
Remark
9.1.2.
The
equivalence (i)
¢=}
(ii) from Theorem 9.1.1 is a classical
result in linear algebra (see, e.g., Theorems 6.3.6
and
6.3.13 in Horn and Johnson
[1991
D.
The
proof
given above for
the
implication (i)
===}
(ii)
is
the
original proof
of
Schoenberg. Another proof can be given, which uses only the fact
that
(exp(aij))
to
for any
matrix
(aij)
It
goes as follows. Suppose
that
the distance space (X,
d)
is of negative type
and
let
xo,XJ,''',Xn
E
X.
Set aij d(XO,Xi) + d(xo,Xj) - d(Xi,Xj) for
i, j =
0,
1,
...
)
n.
Then,
the
matrix
A (aij)
is
positive semidefinite (as
it
coincides
with
the
image of d under
the
covariance mapping pointed
at
xo,
up
9.1
The
Schoenberg
Transform
117
to
a
factor
2). Therefore,
the
matrix
B
:=
(exp(aij)) is positive semidefinite.
Let
D
denote
the
diagonal
matrix
with
ith
diagonal
entry
exp(-d(xo,
Xi))
for
i
=
0,1,
...
,n.
Then,
the
matrix
DBD
is positive semidefinite
and
its
ijth
en-
try
is equal
to
exp(-d(Xi,Xj))
for all
i,j
= O,1,
...
,n. Therefore,
the
matrix
(exp(
-d(Xi,
Xj))i,j=o is positive semidefinite for all
Xo,
Xl,
...
,
Xn
E X
and
n
2':
1,
as required.
I
Corollary
9.1.3.
Let
(X,
d)
be
a distance space. Then,
(X,
d) is
Lrembeddable
¢=?
(X,1
- exp(
-Ad))
is Ll-embeddable
for
all
A>
O.
Proof.
The
"only
if"
part
follows from
Theorems
9.0.3
and
9.1.1.
The
proof
for
the
converse
implication
is analogous
to
that
of
Theorem
9.1.1 (iii)
===}
(i),
replacing
the
negative
type
inequality
by
an
arbitrary
inequality valid for
the
cut
cone
CUT(Y)
where Y is a finite
subset
of
X.
I
Remark
that
Theorem
9.1.1
remains
valid
if
we
assume only
that
(ii)
and
(iii) hold for a set of positive
A's
admitting
0 as
accumulation
point.
The
same
remark
also applies
to
Corollary 9.1.3.
By
Theorem
9.1.1,
we
know
that
the
function
F(t)
=
1-exp(
-At)
(for
A>
0)
belongs
to:F.
Schoenberg I [1938a]
has
described all functions
in
F
(assuming
that
all
their
derivatives exist). Namely,
Theorem
9.1.4.
Let
F :
lilt
----+
lilt
be
a
function
such
that
F(O) = 0
and
its
n-th
derivative F(n) exists
on
lilt
\
{O}
for
each n
2':
1. The following
assertions
are equivalent.
(i) F E F
(that
is, F preserves the negative type property).
(ii) F is
of
the
form:
(9.1.5)
F(t)
=
roo
1 - exp(
-tu)
d')'(u)
for
t
2':
0,
io
u
where,), is a positive measure
on
lilt
satisfying
roo
d')'(
u)
<
00.
i
l
U
(iii)
(_1)n-1
F(n)(t)
2':
0
for
all t > 0
and
n
2':
1.
I
Example
9.1.6.
We
mention
here some examples of functions
in
the
family
F.
'Schoenberg
characterizes,
in
fact,
the
metric
transforms
preserving
L2-embeddability.
Clearly,
G
preserves
L2-embeddability
if
and
only
if
F
preserves
the
negative
type
property,
where
F
and
G
are
linked
by
F(t)
= (G(
Jt))2
for t
~
O.
Further
results
concerning
metric
transforms
in
relation
with
embeddability
in
various
L2
and
Lp
spaces
have
been
established,
in
particular,
by
Schoenberg
[1937, 1938a, 1938b]'
von
Neumann
and
Schoenberg
[1941]. See
also
the
exposition
by
Wells
and
Williams
[1975].
118
Chapter
9.
Metric 'Transforms of
Ll-Spaces
(i)
It
can
be easily verified
that
every function
ofthe
form (9.1.5) belongs to
:F.
For instance,
the
power transform: F(t) =
t'"
belongs
to
:F
for 0 <
0:
~
1.
This
follows from
the
integral formula:
t'" =
e~l
lXJ
(1
- exp(
->h))A
-1-2"'dA for t
2:
0,
where
e",
:=
10
00
(1
- exp(
_U
2
))u-
1
-
2
"'du
(which
can
be checked by setting: u = Ay't in
the
first integral). Alter-
natively,
this
follows from
the
fact
that
(-1
)n-l
F(n)
2:
0 for all n
2:
1.
(ii)
Each
of
the
functions F(t) =
t'"
(0
<
0:
~
1),
l!t'
log(I + t) belongs
to
:F.
Therefore,
they
all preserve L1-embeddability. I
We
conclude
with
a result
of
Kelly
[1972]
on
metric transforms of
the
1-
dimensional £l-space.
Proposition
9.1.7.
Let
F : Il4
---+
Il4
be
a
monotone
nondecreasing concave
f1tnction s1tch
that
F(O)
=
O.
Then
the
metric
transform
of
the distance space
£t
= (E, dEl)
under
F is hypermetric. I
9.2
The
Biotope
Transform
We
mention
here
another
transformation
which preserves L1-embeddability.
It
does
not
belong
to
the
category
of
metric
transforms, as defined by (9.0.1).
Let d be a distance
on
a set X
and
let s be a point of
X.
We
define a new
distance
des)
on
X by
setting
d(S)C
.).=
d(i,j)
~,J
.
d(i,s)+d(j,s)+d(i,j)
for all
i,j
EX.
In
particular,
if (n,A,tL) is a measure space
and
if
(X,d)
is
the
measure
semimetric
space
(AI"
dl')'
then
its
transform
d~)
takes
the
form
(0) _ tL(A6.E)
dl' (A,
E)
-
tL(A)
+ tL(E) + tL(A6.E)
for
A,
E E
AI"
The
distance
tL(A6.E)
(A,
E)
E AI' X AI'
f-t
tL(A
U E)
is
called
the
Steinhaus
distance.
The
distance
(
A
E)
f-t
IA6.EI
,
IAUEI'
tL(A6.E)
2tL(A
U
E)
9.2
The
Biotope Transform
119
which is
obtained
in
the
special case
when
J-t
is
the
cardinality measure,
is
also
known
under
the
name
of
biotope distance.
This
terminology comes from
the
fact
that
this
distance
is
used in some biological problems for
the
study
of
biotopes
(see Marczewski
and
Steinhaus
[1958]). As a consequence
of
the
next
Proposi-
tion
9.2.1,
the
Steinhaus
and
biotope distances are L1-embeddablej (i) is given
in Marczewski
and
Steinhaus
[1958]
and
(ii) in Assouad [1980b].
Proposition
9.2.1.
(i)
If
d is a semimetric on
X,
then
des)
is a semimetric on
X.
(ii)
If
(X,
d)
is L1-embeddable, then
(X,
des))
is Ll-embeddable.
Proof.
(i) follows from (ii)
and
the
fact
that
a distance space on
at
most 4
points
is
L1-embeddable
if
and
only
if
it
is
a semimetric space (see
Remark
6.3.5 (i)).
(ii)
By
Lemma
4.2.5,
we
can
suppose
that
(X,
d)
is
an
isometric subspace
of
some
measure
semimetric
space
(AIL'
d
IL
),
i.e.,
d(i,j)
=
J-t(Ai6Aj)
where
Ai
E
AIL
for
all
i,
j
EX,
and
we
can
suppose
without
loss
of
generality
that
As =
0.
Hence,
as was already observed,
for all
i,j
E
X.
By
Lemma
5.3.2, showing
that
(X,d(s)) is L1-embeddable
amounts
to
showing
that
p
:=
~.(d(s))
is
a {O,l}-covariance.
From
(5.2.4), p is
defined by
p(i,j)
=
~(d(S)(i,
s) + d(s)(j, s) - d(s)(i,j))
for
i,j
E X \ {s}. Hence,
for
i,
j E X \ {s}. Therefore,
it
suffices to show
that
the
symmetric
function
.
(..)
(X
\ {
})2
t---;
J-t(Ai
n
Aj)
q.
Z,)
E s J-t(AiUA
j
)
is a {a, 1 }-covariance. For this,
we
use
the
identity
(which follows from
the
identity Li>O(1 -
u)i
=
~
for all ° < u
:s;
1). Therefore,
q is a {a, 1 }-covariance, i.e.,
belongsto
the
correlation cone
COR(X
\ {s}).
This
follows from
the
fact
that
{a, 1 }-covariances are preserved
under
taking
sums,
products
and
limits (for
the
product
operation, recall
Proposition
7.5.3). I
120
Chapter
9.
Metric Transforms
of
L1-Spaces
9.3
The
Power
Transform
We
return
here
to
the
study
of
metric transforms
and,
more specifically,
to
that
of
the
power transform:
F(t) = t
Q
for t 2
0,
where 0 < a
:::;
1.
We address
the
following question:
What
is
the
largest expo-
nent
a E [0,1] for which
the
metric
transform
(X,
d
Q
)
of
an
arbitrary
semimetric
space (X,
d)
can
be
embedded
in
a
certain
host space, say,
£1
or
£2?
As a
lies
within
[0,1],
we
are
at
least assured
that
(X,
d
Q
)
is a
semimetric
space (by
Lemma
9.0.2).
For instance,
(X,
d
Q
)
is
£2-embeddable for every a
:::;
1,
if
IXI
= 3 (recall
Remark
6.2.12).
Blumenthal
[1953]
shows
that
(X,
d
Q
)
is £2-embeddable for
every
a
:::;
~,
if
IXI
=
4;
moreover,
~
is
the
largest such exponent. Deza
and
Maehara
[1990]
consider
the
general case
of
a semimetric space
on
n 2 3 points.
They
give some range
of
values for a (depending
on
n) for which
(X,
d
Q
)
enjoys
some
metric
properties
such as hypermetricity,
£1
or
£2-embeddability for any
semimetric
space (X,
d)
with
IXI
=
n.
The
following function:
1
')'(s):= log2(1 + -) for s > 0
s
will be useful for formulating
the
results. Deza
and
Maehara
[1990]
show
the
following result.
Theorem
9.3.1.
Let
(X,
d)
be
a semimetric space with
IXI
=
n.
Then,
(X,
d
Q
)
is hypermetric for every
0 < a
:::;
')'(n - 1).
Corollary
9.3.2.
Let
(X,
d)
be
a semimetric space with
IXI
=
n.
Then,
(X,
d
Q
)
is £2-embeddable for every
0 < a
:::;
h(n
- 1).
Proof
of
Corollary 9.3.2.
If
a
:::;
h(n
-
1)
then,
by
Theorem
9.3.1,
(X,
d
2
D:)
is
hypermetric
and,
thus,
of
negative type. Therefore,
(X,
d
Q
)
is £2-embeddable. I
For
the
proof
of
Theorem
9.3.1,
we
need some
preliminary
lemmas.
Lemma
9.3.3.
Let 0 < a
:::;
')'(s) where s 2 1 and let
(X,d)
be
a semimetric
space. Then,
1
d(x,y):::;
d(y,z)
===?
d(x,z)Q:::;
-d(x,y)Q
+ d(y,z)Q.
S
Proof. As d(x,z)Q
:::;
(d(x,y)
+ d(y,z))Q, it suffices
to
show
that
(d(x,y)
+
d(y, z))Q
:::;
~d(x,
y)Q
+ d(y,
z)Q
or, equivalently,
(
1+
d(y,z))Q
<
~+
(d(y,z))Q
d(x,y)
- s
d(x,y)
9.3
The
Power
Transform
121
Let
f(t)
:=
~
+to
-
(1
+t)O
for t
::::
1.
It
remains
to
check
that
f(t)
::::
0 for t
::::
1.
Indeed,
f(t)
::::
f(l)
(as f is
monotone
nondecreasing)
and
f(l)
=
~
+ 1 -
2°
::::
0
as
Go:S
"(8). I
The
next
lemmas
deal
with
proving
that
(X,
dO)
is
hypermetric;
that
is,
that
(X,
dO)
satisfies
the
(2m
+ 1)-gonal inequality:
(9.3.4)
for every sequence:
(9.3.5)
Xl,.··
,Xm,Yl,
..
· ,Ym+l
EX
l<i<rn
l:SJ:S~+l
(with
possible
repetitions)
and
every m
::::
1. To simplify
notation,
let us
denote
d(x,y)O by
the
symbol
xy,
for any
X,Y
E
X.
We
can
suppose (after possibly
reordering
the
indices)
that
the sequence (9.3.5) satisfies:
(9.3.6)
XkYk
:S
XiYj
for all
i,j
::::
k,
k = 1,
...
,
m.
Then,
using
Lemma
9.3.3, we
obtain
that,
for 0 <
Go
:S
"(8)
and
k
:S
m,
i < k <
j,
(9.3.7)
XiXk
:S
~XkYk
+
XkYi,
XjXk
:S
~XkYk
+
XjYk,
YiYk
:S
~XkYk
+
XiYk,
YjYk
:S
~XkYk
+
XkYj'
Therefore, for any i, k
:S
m,
(9.3.8)
Lemma
9.3.9.
Let
0 <
Go
:S
,,(m)
and
let
(X,
d)
be
a
semimetric
space.
Then,
(X,
dO)
is
(2m
+ 1)-gonal. Moreover,
for
Go
>
,,(m),
there exists a
semimetric
space
(X,
d)
with
IXI
= 2m + 2 (resp.
IXI
= 2m +
1)
for
which
(X,
dO)
is
not
(2m
+
2)-gonal
(resp.
not
(2m
+ 1)-gonal.
Proof.
Consider
a sequence of
points
as (9.3.5)
and
suppose
that
it satis-
fies (9.3.6). Given
k
:S
m,
summing
(9.3.8) (applied
with
8
.-
m)
over i =
1,
...
,m,
i
=1=
k,
yields:
Summing
now over k = 1,
...
,m,
we
obtain:
m 2 m m
L
XiXk
+
YiYk
:S
--
L
XkYk
+ L
XkYi
+
XiYk·
i,k=l
m
k=l
i,k=l
122
Chapter
9.
Metric
'Transforms
of
LI-Spaces
Dividing
by
2
and
adding
the
inequality:
m 1 m m
L YkYm+l
:<:;
- L
XkYk
+ L
XkYm+l
k=l
m
k=l
k=l
(which follows using
Lemma
9.3.3),
we
obtain
the
desired
inequality
(9.3.4).
Suppose
now
that
a >
,(m).
Consider
as
distance
space
(X,
d)
the
graphic
metric
space
of
the
complete
bipartite
graphs
Km+l,m+l
and
K
m
+1,m'
Then,
dCl.
is
not
(2m
+ 2)-gonal
in
both
cases.
(This
is
immediate,
chosing for
the
Xi'S
the
points
in
one colour class
and
for
the
y;'s
the
points
in
the
other
colour class.)
I
Lemma
9.3.10.
Let
0 < a
:<:;
s
and
let
(X,
d)
be
a
semimetric
space
such
that
(X,
dCl.)
is
(2m
-I)-gonal.
Consider
a sequence as
in
(9.3.5) with
maximum
rep-
etition
number
greater
than
or
equal to
;~
(that
is,
at
least
one
member
of
the
sequence
is repeated
at
least
;~
times).
Then, (X,dCl.) satisfies the correspond-
ing
(2m
+
I)-gonal
inequality (9.3.4).
Proof.
Let
r
denote
the
maximum
repetition
number
in
the
sequence (9.3.5).
By
assumption,
r
2':
s2~.
We
can
assume
that
(9.3.6) holds.
If
some
Xi
coincides
with
some Yj, say,
Xm
= Ym+b
then
the
(2m
+
I)-gonal
inequality
follows from
the
fact
(X,
dCl.)
is
(2m
-
I)-gonal
(and,
thus,
satisfies
the
inequality
associated
with
the
sequence Xl,
...
,Xm-l,Yl,
...
,Ym). Hence,
we
can
suppose
that
the
two
sets
{Xl,
...
,
xm}
and
{Yl,
...
,
Ym+d
are
disjoint.
Let
k
denote
the
smallest
index
i
such
that
one
of
Xi
or
Yi
is
repeated
r
times
in
the
sequence (9.3.5).
Let
us
suppose
that
this
is
the
case for
Xk
(the
case
with
Yk
is
similar
and
omitted).
By
assumption,
(X,
dCl.)
satisfies
the
(2m
-
I)-gonal
inequality
associated
to
the
sequence
(9.3.5)
with
Xk
and
Yk
omitted;
that
is,
l<i<j<Tn
-i,ii'k
l<i<j<Tn+l
-
i,i#k
Therefore,
we
are
done
if
we
can
show:
(a) L
XiXk
+ L
YiYk
:<:;
L
XkYi
+ L
XiYk,
iEluJ
l::;i::;m+l,
icpk
l::;i::;m+l,
icpk
l::;i::;m
where
I
:=
{i
11
:<:;
i <
k,
Xi
i-
xd
and
J
:=
{i I k < i
:<:;
m,
Xi
i-
xd.
Note
that
III
+
IJI
+ r = m
and
I =
{I,
...
, k -
I}
by
the
choice
of
k.
Let
us
evaluate
the
left-hand
side
of
(a). Using (9.3.7),
we
have:
1 1
L
XiXk
+
LYiYk
:<:;
L(
-XkYk +
XkYi)
+
L(
-XkYk + XiYk)
iEluJ
icpk
iEI
s
iEJ
S
k-l
1 m 1
+ L
(-XkYk
+ XiYk) + L (-XkYk +
XkYi)
i=l
s
i=k+l
S
1 m
=
-xkYk(III
+
IJI
+ m) + L
XkYi
+
LXiYk
- rXkYk·
s
l::;i::;m+l,
icpk
i=l
9.3
The
Power Transform
123
But,
~(III
+
IJI
+
m)
r
which concludes
the
proof.
r S 0, because r
:2::
:~.
Therefore, (a) holds,
I
Proof
of
Theorem
9.3.1.
Let
0 < 0 S
')'(n-I).
We show
that
d'"
is
(2m+I)-gonal
for all m
:2::
1, by
induction
on
m.
If
m
1,
this is clear as
d'"
is a semimetric.
Suppose
that
m
:2::
2
and
that
d'"
is
(2m
1)-gona!. Clearly, a sequence
of
2m
+ 1
points
in
X
must
contain an element which
is
repeated
at
least
2r~±1
times
(as
IXI
= n). Applying
Lemma
9.3.10
(with
s
:=
n 1),
we
deduce
that
d
a
is
(2m
+ 1)-gonal. I
Corollary
9.3.11.
Let
(X,
d)
be
a
semimetric
space with
IXI
= 5,
or
6.
Then,
(X,
d"') is {I-embeddable
for
all 0 < 0 S ')'(2). Moreover, ')'(2) is the largest
such
value
of
OJ
that
is,
for
0 > ')'(2), there are distance spaces
on
5
and
6
points
fOT
which
de>
is
not
{I
-embeddable.
Proof.
In
the
case
IX
I =
5,
the
result follows from
the
fact
that
a distance
on
5
points
is {I-embeddable if
and
only
if
it
is
5-gonal (recall
Remark
6.3.5 (i».
Consider now
the
case
IXI
= 6.
If
0 S ')'(2)
then
d
a
is
5-gonal by
Lemma
9.3.9
and,
thus, 7-gonal by
Lemma
9.3.10. (We use
the
fact
that
a distance
on
6
points
is
{l-embeddable
if
and
only
if
it
is 7-gonal.) I
For
n:2::
3, let
us
consider
the
parameters
g(n), hen), cI(n),
and
c2(n) which
are
defined as follows:
g(
n) denotes
the
maximum
0 E [0,1] for which
(X,
d
a
)
is
n-gonal for every semimetric space
(X,d)
with
IXI
n.
Similarly, hen) (resp.
cI(n),
c2(n»
denotes
the
maximum
0 for which
(X,d
a
)
is hypermetric (resp.
{I-embeddable, f2-embeddable) for every semimetric space
(X,
d)
with
IXI
n.
Clearly,
1
c2(n) S CI(n) S
hen)
s g(n)
and
c2(n)
:2::
Zh(n).
We have shown
in
Theorem
9.3.1
that
hen)
:2::
')'(n 1); implying c2(n)
:2::
~')'(n
-1).
Using
Lemma
9.3.9 (together
with
Lemma
6.1.10 in
the
case when n
is
even),
one
can
give
the
exact value
of
the
parameter
g(n).
Lemma
9.3.12.
g(2m)
')'(m -
1)
faT m
:2::
2,
and
g(2m
+ 1)
m:2::l.
')'(m) faT
I
This
implies
that
h(5) h(6) ')'(2).
The
exact value
of
the
parameter
cI(n) is known
in
the
cases n S 6, by Corollary 9.3.11.
On
the
other
hand,
we
have:
c2(5)
:2::
~h(5)
h(2),
but
the
exact value
of
c2(5)
is not known.
The
value
of
c2(n)
is
known, however,
in
the case n =
6.
Lemma
9.3.13.
c2(6)
h(2).