Metrizable ball structures
A ball structure is a triple (X, P, B), where X, P are nonempty sets and, for any x ∈ X, α ∈ P, B(x, α) is a subset of X, x ∈ B(x, α), which is called a ball of radius α around x. We characterize up to isomorphism the ball structures related to the metric spaces of different types and groups....
Gespeichert in:
| Datum: | 2002 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2002
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/157658 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Metrizable ball structures / I.V. Protasov // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 129–141. — Бібліогр.: 5 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157658 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1576582019-06-21T01:26:05Z Metrizable ball structures Protasov, I.V. A ball structure is a triple (X, P, B), where X, P are nonempty sets and, for any x ∈ X, α ∈ P, B(x, α) is a subset of X, x ∈ B(x, α), which is called a ball of radius α around x. We characterize up to isomorphism the ball structures related to the metric spaces of different types and groups. 2002 Article Metrizable ball structures / I.V. Protasov // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 129–141. — Бібліогр.: 5 назв. — англ. 1726-3255 2001 Mathematics Subject Classification 54E35, 05C75. http://dspace.nbuv.gov.ua/handle/123456789/157658 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
A ball structure is a triple (X, P, B), where X, P
are nonempty sets and, for any x ∈ X, α ∈ P, B(x, α) is a subset
of X, x ∈ B(x, α), which is called a ball of radius α around x. We
characterize up to isomorphism the ball structures related to the
metric spaces of different types and groups. |
| format |
Article |
| author |
Protasov, I.V. |
| spellingShingle |
Protasov, I.V. Metrizable ball structures Algebra and Discrete Mathematics |
| author_facet |
Protasov, I.V. |
| author_sort |
Protasov, I.V. |
| title |
Metrizable ball structures |
| title_short |
Metrizable ball structures |
| title_full |
Metrizable ball structures |
| title_fullStr |
Metrizable ball structures |
| title_full_unstemmed |
Metrizable ball structures |
| title_sort |
metrizable ball structures |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2002 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157658 |
| citation_txt |
Metrizable ball structures / I.V. Protasov // Algebra and Discrete Mathematics. — 2002. — Vol. 1, № 1. — С. 129–141. — Бібліогр.: 5 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT protasoviv metrizableballstructures |
| first_indexed |
2025-07-14T10:05:25Z |
| last_indexed |
2025-07-14T10:05:25Z |
| _version_ |
1837616359504084992 |
| fulltext |
V. Nekrashevych 125
Definition 5.4. Let G be a finitely generated group, acting on a set A.
Growth degree of the G-action is the number
γ = sup
w∈A
lim sup
r→∞
log |{g(w) : l(g) ≤ r}|
log r
where l(g) is the length of a group element with respect to some fixed
finite generating set of G.
One can show, in the same way as before, that the growth degree γ
does not depend on the choice of the generating set of G.
Proposition 5.10. Suppose that a standard action of a group G on X∗
is contracting. Then the growth degree of the action on Xω is not greater
than log |X|
− log ρ , where ρ is the contraction coefficient of the action on X∗.
Proof. The statement is more or less classical. See, for instance the
similar statements in [Gro81, BG00, Fra70].
Let ρ1 be such that ρ < ρ1 < 1. Then there exists C > 0 and n ∈ N
such that for all g ∈ G we have l(g|x1x2...xn) < ρn
1 · l(g) + C.
Then cardinality of the set B(w, r) = {g(w) : l(g) ≤ r}, where
w = x1x2 . . . ∈ Xω is not greater than
|X|n · |{B (xn+1xn+2 . . . , ρn
1 · r + C)| ,
since the map σn : x1x2 . . . 7→ xn+1xn+2 . . . maps B(w, r) into
B (xn+1xn+2 . . . , ρn
1 · r + C)
and every point of Xω has exactly |X|n preimages under σn. The map
σn is the nth iteration of the shift map σ(x1x2 . . .) = x2x3 . . ..
Let k =
[
log r
−n log ρ1
]
+1. Then ρnk
1 ·r < 1 and the number of the points
in the ball B(w, r) is not greater than
|X|nk ·
∣
∣
∣
B
(
σnk (w) , R
)∣
∣
∣
,
where
R = ρnk
1 · r + ρ
n(k−1)
1 · C + ρ
n(k−2)
1 · C + · · · + ρn
1 · C + C < 1 +
C
1 − ρn
1
.
But |B(u,R)| for all u ∈ Xω is less than K1 = |S|R, where S is the
generating set of G (we assume that S = S−1 ∋ 1). Hence,
|B(w, r)| < K1 · |X|
n
(
log r
−n log ρ1
+1
)
=
= K1 · exp
(
log |X| log r
− log ρ1
+ n log |X|
)
= K2 · r
log |X|
− log ρ1 ,
where K2 = K1 · |X|n. Thus, the growth degree is not greater than
log |X|
− log ρ1
for every ρ1 ∈ (ρ, 1), so it is not greater than log |X|
− log ρ .
126 Virtual endomorphisms of groups
Lemma 5.11. Let φ be a contracting virtual endomorphism of a φ-simple
infinite finitely generated group G. Then the contraction coefficient of its
standard action is greater or equal to 1/ ind φ.
Proof. Consider the standard action on the set X∗ for a standard basis
X, containing the element x0 = φ(1)1. Then the parabolic subgroup
P (φ) = ∩n≥0 Dom φn is the stabilizer of the word w = x0x0x0 . . . ∈ Xω.
The subgroup P (φ) has infinite index in G, otherwise ∩g∈Gg−1Pg = C(φ)
will have finite index, and G will be not φ-simple. Consequently, the G-
orbit of w is infinite. Then there exists an infinite sequence of generators
s1, s2, . . . of the group G such that the elements of the sequence
w, s1(w), s2s1(w), s3s2s1(w), . . .
are pairwise different. This implies that the growth degree of the orbit
Gw
γ = lim sup
r→∞
|{g(w) : l(g) ≤ r}|
log r
is greater or equal to 1, thus the growth degree of the action of G on Xω
is not less than 1, and by Proposition 5.10, 1 ≤ log |X|
− log ρ .
Proposition 5.12. If there exists a faithful contracting action of a fini-
tely-generated group G then for any ǫ > 0 there exists an algorithm of
polynomial complexity of degree not greater than log |X|
− log ρ + ǫ solving the
word problem in G.
Proof. We assume that the generating set S is symmetric (i.e., that S =
S−1) and contains all the restrictions of all its elements, so that always
l(g|v) is not greater than l(g).
We will denote by F the free group generated by S and for every
g ∈ F by ĝ we denote the canonical image of g in G.
Let 1 > ρ1 > ρ. Then ρ1 · |X| > 1, since by Lemma 5.11, ρ · |X| ≥ 1.
There exist n0 and l0 such that for every word v ∈ X∗ of the length n0
and every g ∈ G of the length ≥ l0 we have
l (g|v) < ρn
1 l(g).
Assume that we know for every g ∈ F of the length less than l0 if ĝ
is trivial or not. Assume also that we know all the relations g · v = u · h
for all g, l(g) ≤ l0 and v ∈ Xn0 .
Then we can compute in l(ĝ) steps, for any g ∈ F and v ∈ Xn, the
element h ∈ F and the word u ∈ Xn0 such that ĝ · v = u · ĥ. If v 6= u
then we conclude that ĝ is not trivial and stop the algorithm. If for all
v ∈ Xn0 we have v = u, then ĝ is trivial if and only if all the obtained
V. Nekrashevych 127
restrictions ĥ = ĝ|v are trivial. We know, whether ĥ is trivial if l(h) < l0.
We proceed further, applying the above computations for those h, which
have the length not less than l0.
But l(h) < ρn
1 l(g), if l(g) ≥ l0. So on each step the length of the
elements becomes smaller, and the algorithm stops in not more than
− log l(g)/ log ρ1 steps. On each step the algorithm branches into |X|
algorithms. Thus, since ρ1 · |X| > 1, the total time is bounded by
l(g)
(
1 + ρ1 · |X| + (ρ1 · |X|)2 + · · · + (ρ1 · |X|)[− log l(g)/ log ρ1]
)
<
l(g)
ρ1·|X|−1
(
(ρ1 · |X|)1−log l(g)/ log ρ1 − 1
)
=
l(g)ρ1·|X|
ρ1·|X|−1
(
(ρ1 · |X|)− log l(g)/ log ρ1 − (ρ1 · |X|)−1
)
=
C1l(g)
(
exp
(
log l(g)
(
log |X|
− log ρ1
− 1
))
− C2
)
=
= C1l(g)− log |X|/ log ρ1 − C1C2l(g),
where C1 = ρ1·|X|
ρ1·|X|−1 and C2 = (ρ1 · |X|)−1.
References
[AB94] N. A’Campo and M. Burger, Réseaux arithmétiques et commensurateur
d’après G. A. Margulis, Invent. Math. 116 (1994), no. 1–3, 1–25.
[Ale83] S. V. Aleshin, A free group of finite automata, Vestn. Mosc. Un. Ser. 1.
(1983), no. 4, 12–16, in Russian.
[BdlH97] M. Burger and P. de la Harpe, Constructing irreducible representations of
discrete groups, Proc. Indian Acad. Sci., Math. Sci. 107 (1997), no. 3, 223–
235.
[BG00] Laurent Bartholdi and Rostislav I. Grigorchuk, On the spectrum of Hecke
type operators related to some fractal groups, Proceedings of the Steklov
Institute of Mathematics 231 (2000), 5–45.
[BGN02] Laurent Bartholdi, Rostislav I. Grigorchuk, and Volodymyr V. Nekra-
shevych, From fractal groups to fractal sets, to appear, 2002.
[BSV99] Andrew M. Brunner, Said N. Sidki, and Ana. C. Vieira, A just-nonsolvable
torsion-free group defined on the binary tree, J. Algebra 211 (1999), 99–144.
[Fra70] John M. Franks, Anosov diffeomorphisms, Global Analysis, Berkeley, 1968,
Proc. Symp. Pure Math., vol. 14, Amer. Math. Soc., 1970, pp. 61–93.
[GNS00] Rostislav I. Grigorchuk, Volodymyr V. Nekrashevich, and Vitalĭı I.
Sushchanskii, Automata, dynamical systems and groups, Proceedings of the
Steklov Institute of Mathematics 231 (2000), 128–203.
[Gri80] Rostislav I. Grigorchuk, On Burnside’s problem on periodic groups, Fun-
tional Anal. Appl. 14 (1980), no. 1, 41–43.
[Gri83] Rostislav I. Grigorchuk, On the Milnor problem of group growth, Dokl. Akad.
Nauk SSSR 271 (1983), no. 1, 30–33.
[Gri00] Rostislav I. Grigorchuk, Just infinite branch groups, New horizons in pro-p
groups (Aner Shalev, Marcus P. F. du Sautoy, and Dan Segal, eds.), Progress
in Mathematics, vol. 184, Birkhäuser Verlag, Basel, etc., 2000, pp. 121–179.
128 Virtual endomorphisms of groups
[Gro81] Mikhael Gromov, Groups of polynomial growth and expanding maps, Publ.
Math. I. H. E. S. 53 (1981), 53–73.
[GS83a] Narain D. Gupta and Said N. Sidki, On the Burnside problem for periodic
groups, Math. Z. 182 (1983), 385–388.
[GS83b] Narain D. Gupta and Said N. Sidki, Some infinite p-groups, Algebra i Logika
22 (1983), 584–589.
[Mar91] G. A. Margulis, Discrete subgroups of semisimple Lie groups, Ergebnisse
der Mathematik und ihrer Grenzgebiete, 3. Folge, 17. Berlin etc.: Springer-
Verlag, 1991.
[MNS00] Olga Macedońska, Volodymyr V. Nekrashevych, and Vitalĭı I. Sushchansky,
Commensurators of groups and reversible automata, Dopovidi NAN Ukrainy
(2000), no. 12, 36–39.
[Neka] Volodymyr V. Nekrashevych, Cuntz-Pimsner algebras of group actions, sub-
mitted.
[Nekb] Volodymyr V. Nekrashevych, Iterated monodromy groups, preprint, Geneva
University, 2002.
[Nekc] Volodymyr V. Nekrashevych, Limit spaces of self-similar group actions,
preprint, Geneva University, 2002.
[Nek00] Volodymyr V. Nekrashevych, Stabilizers of transitive actions on locally finite
graphs, Int. J. of Algebra and Computation 10 (2000), no. 5, 591–602.
[NS01] Volodymyr V. Nekrashevych and Said N. Sidki, Automorphisms of the binary
tree: state-closed subgroups and dynamics of 1/2-endomorphisms, preprint,
2001.
[Röv02] Claas E. Röver, Commensurators of groups acting on rooted trees, to appear
in Geom. Dedicata, 2002.
[Sid97] Said N. Sidki, A primitive ring associated to a Burnside 3-group, J. London
Math. Soc. (2) 55 (1997), 55–64.
[Sid98] Said N. Sidki, Regular trees and their automorphisms, Monografias de
Matematica, vol. 56, IMPA, Rio de Janeiro, 1998.
[Sid00] Said N. Sidki, Automorphisms of one-rooted trees: growth, circuit structure
and acyclicity, J. of Mathematical Sciences (New York) 100 (2000), no. 1,
1925–1943.
[SW02] S. Sidki and J. S. Wilson, Free subgroups of branch groups, (to appear),
2002.
Contact information
V. Nekrashevych Kyiv Taras Shevchenko University, Ukraine
E-Mail: nazaruk@ukrpack.net
Received by the editors: 21.10.2002.
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 1. (2002). pp. 129–141
c© Journal ”Algebra and Discrete Mathematics”
Metrizable ball structures
I.V. Protasov
Communicated by V.M. Usenko
Dedicated to V. V. Kirichenko on the occasion of his 60th birthday
Abstract. A ball structure is a triple (X, P, B), where X , P
are nonempty sets and, for any x ∈ X , α ∈ P , B(x, α) is a subset
of X , x ∈ B(x, α), which is called a ball of radius α around x. We
characterize up to isomorphism the ball structures related to the
metric spaces of different types and groups.
Following [1, 2], by ball structure we mean a triple B = (X,P,B),
where X, P are nonempty sets and, for any x ∈ X, α ∈ P , B(x, α) is a
subset of X, which is called a ball of radius α around x. It is supposed
that x ∈ B(x, α) for all x ∈ X, α ∈ P .
Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be ball structures,
f : X1 → X2. We say that f is a ≻-mapping if, for every β ∈ P2, there
exists α ∈ P1 such that
B2(f(x), β) ⊆ f(B1(x, α))
for every x ∈ X1. If there exists a ≻-mapping of X1 onto X2, we write
B1 ≻ B2.
A mapping f : X1 → X2 is called a ≺-mapping if, for every α ∈ P1,
there exists β ∈ P2 such that
f(B1(x, α)) ⊆ B2(f(x), β)
for every x ∈ X1. If there exists an injective ≺-mapping of X1 into X2,
we write B1 ≺ B2.
A bijection f : X1 → X2 is called an isomorphism between B1 and
B2 if f is a ≻-mapping and f is a ≺-mapping.
Key words and phrases: ball structure, ball isomorphism, metrizablility.
2001 Mathematics Subject Classification 54E35, 05C75.
130 Metrizable ball structures
We say that a property P of ball structures is a ball property if a ball
structure B has a property P provided that B is isomorphic to some ball
structure with property P.
Example 1. Let (X, d) be a metric space, R+ = {x ∈ R : x ≥ 0}. Given
any x ∈ X, r ∈ R+, put
Bd(x, r) = {y ∈ X : d(x, y) ≤ r}.
A ball structure (X,R+, Bd) is denoted by B(X, d).
We say that a ball structure B is metrizable if B is isomorphic to
B(X, d) for some metric space (X, d).
To obtain a characterization (Theorem 1) of metrizable ball struc-
tures, we need some definitions and technical results.
A ball structure B = (X,P,B) is called connected if, for any x, y ∈ X,
there exists α ∈ P such that y ∈ B(x, α), x ∈ B(y, α).
Lemma 1. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be ball struc-
tures and let f be a ≺-mapping of X1 onto X2. If B1 is connected, then
B2 is connected.
Proof. Given any y, z ∈ X1, choose α ∈ P1 such that y ∈ B1(z, α),
z ∈ B1(y, α). Since f is a ≺-mapping, then there exists β ∈ P2 such that
f(B1(x, α)) ⊆ B2(f(x), β) for every x ∈ X1. Hence, f(y) ∈ B2(f(z), β)
and f(z) ∈ B2(f(y), β). Since f(X1) = X2, then B2 is connected.
Lemma 2. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be ball struc-
tures and let f be an injective ≻-mapping of X1 into X2. If B2 is con-
nected, then B1 is connected.
Proof. Given any y, z ∈ X1, choose β ∈ P2 such that f(y) ∈ B2(f(z), β)
and f(z) ∈ B2(f(y), β). Since f is a ≻-mapping, then there exists α ∈
P1 such that B2(f(x), β) ⊆ f(B1(x, α)) for every x ∈ X1. Since f is
injective, then z ∈ B1(y, α) and y ∈ B1(z, α). Hence, B1 is connected.
Let B = (X,P,B) be a ball structure. For all x ∈ X, α ∈ P , put
B∗(x, α) = {y ∈ X : x ∈ B(y, α)}.
A ball structure B∗ = (X,P,B∗) is called dual to B. Note that
B∗∗ = B.
A ball structure B is called symmetric if the identity mapping i : X →
X is an isomorphism between B and B∗. In other words, B is symmetric
if, for every α ∈ P , there exists β ∈ P such that B(x, α) ⊆ B∗(x, β) for
every x ∈ X, and vice versa.
I.V. Protasov 131
Lemma 3. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be ball struc-
tures, f : X1 → X2. If f is a ≺-mapping of B1 to B2, then f is a
≺-mapping of B∗
1 to B∗
2. If f is an isomorphism between B1 and B2,
then f is an isomorphism between B∗
1 and B∗
2.
Proof. Let f be a ≺-mapping of B1 to B2 and let α ∈ P1. Choose
β ∈ P2 such that f(B1(x, α)) ⊆ B2(f(x), β) for every x ∈ X1. Take
any element y ∈ B∗
1(x, α). Then x ∈ B1(y, α) and f(x) ∈ B2(f(y), β).
Hence, f(y) ∈ B∗
2(f(x), β) and f(B∗
1(x, α)) ⊆ B∗
2(f(x), β). It means that
f is a ≺-mapping of B∗
1 to B∗
2.
Suppose that f is an isomorphism between B1 and B2. By the first
statement, f is a ≺-mapping of B∗
1 to B∗
2 and f−1 is a ≺-mapping of B∗
2
to B∗
1. It follows that f is an isomorphism between B∗
1 and B∗
2.
Lemma 4. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be isomorphic
ball structures. If B1 is symmetric, then B2 is symmetric.
Proof. Let f : X1 → X2 be an isomorphism between B1 and B2. Denote
by i1 : X1 → X1 and i2 : X2 → X2 the identity mappings. Clearly, f−1 is
an isomorphism between B2 and B1. By Lemma 3, f is an isomorphism
between B∗
1 and B∗
2. By assumption, i1 is an isomorphism between B1
and B∗
1. Since i2 = fi1f
−1, then i2 is an isomorphism between B2 and
B∗
2.
A ball structure B = (X,P,B) is called multiplicative if, for any
α, β ∈ P , there exists γ(α, β) ∈ P such that
B(B(x, α), β) ⊆ B(x, γ(α, β))
for every x ∈ X. Here, B(A,α) =
⋃
a∈A B(a, α) for any A ⊆ X, α ∈ P .
Lemma 5. If a ball structure B = (X,P,B) is multiplicative, then B∗
is multiplicative.
Proof. Given any α, β ∈ P , choose γ(α, β) such that B(B(x, α), β) ⊆
B(x, γ(α, β)). Take any element z ∈ B∗(B∗(x, α), β) and pick y ∈
B∗(x, α) such that z ∈ B∗(y, β). Then x ∈ B(y, α) and y ∈ B(z, β),
so x ∈ B(B(z, β), α). Since B(B(z, β), α) ⊆ B(z, γ(β, α)), then x ∈
B(z, γ(β, α)). Hence, B∗(B∗(x, α), β) ⊆ B∗(x, γ(β, α)) and B∗ is multi-
plicative.
Lemma 6. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be isomorphic
ball structures. If B1 is multiplicative, then B2 is multiplicative.
132 Metrizable ball structures
Proof. Denote by f1 : X1 → X2 the isomorphism between B1 and B2.
Fix any β1, β2 ∈ P2. Since f is a bijection, it suffices to prove that there
exists β ∈ P2 such that
B2(B2(f(x), β1), β2) ⊆ B2(f(x), β)
for every x ∈ X1.
Since f is a ≻-mapping, then there exist α1, α2 ∈ P1 such that
B2(f(x), β1) ⊆ f(B1(x, α1)), B2(f(x), β2) ⊆ f(B1(x, α2))
for every x ∈ X1.
Since B1 is multiplicative, then there exists α ∈ P1 such that
B1(B1(x, α1), α2) ⊆ B1(x, α)
for every x ∈ X1.
Since f is a ≺-mapping, then there exists β ∈ P2 such that
f(B1(x, α)) ⊆ B2(f(x), β)
for every x ∈ X1.
Now fix x ∈ X1 and take any element f(z) ∈ B2(B2(f(x), β1), β2).
Pick f(y) ∈ B2(f(x), β1) with f(z) ∈ B2(f(y), β2). Then y ∈ B1(x, α1),
z ∈ B1(y, α2) and z ∈ B1(B1(x, α1), α2). Hence, z ∈ B1(x, α) and
f(z) ∈ B2(f(x), β).
For an arbitrary ball structure B = (X,P,B), we define a preodering
≤ on the set P by the rule
α ≤ β if and only if B(x, α) ⊆ B(x, β)
for every x ∈ X. A subset P
′
of P is called cofinal if, for every α ∈ P ,
there exists β ∈ P
′
such that α ≤ β. A cofinality cfB of B is a minimum
of cardinalities of cofinal subsets of P . Thus, cfB ≤ ℵ0 if and only if
there exists a cofinal sequence < αn >n∈ω in P such that α0 ≤ α1 ≤
. . . ≤ αn ≤ . . ..
Lemma 7. If the ball structures B1 = (X1, P1, B1) and B2 = (X2,
P2, B2) are isomorphic, then cfB1 = cfB2.
Proof. Let f : X1 → X2 be an isomorphism between B1 and B2 and let
P
′
1 be a cofinal subset of P1. Since f is a ≻-mapping, then there exists a
mapping h1 : P2 → P
′
1 such that B2(f(x), β) ⊆ f(B1(x, h1(β))) for any
x ∈ X1, β ∈ P2. Since f is a ≺-mapping, then there exists a mapping
h2 : P
′
1 → P2 such that f(B1(x, α)) ⊆ B2(f(x), h2(α)) for any x ∈ X1,
α ∈ P
′
1. From the construction of h1, h2 we conclude that h2(P
′
1) is a
cofinal subset of P2. Hence, cfB2 ≤ cfB1.
I.V. Protasov 133
Theorem 1. A ball structure B = (X,P,B) is metrizable if and only if
B is connected symmetric multiplicative and cfB ≤ ℵ0.
Proof. First suppose that B is isomorphic to B(X, d) for an appropriate
metric space (X, d). Obviously, B(X, d) is connected symmetric multi-
plicative and cfB ≤ ℵ0. By Lemma 1, 4, 6, 7 B has the same properties.
Now assume that B is connected symmetric multiplicative and cfB ≤
ℵ0. Let < αn >n∈ω be a cofinal sequence in P . Put β0 = α0 and choose
β1 ∈ P such that β1 ≥ α1, β1 ≥ β0, β1 ≥ γ(β0, β0), where γ is a
function from definition of multiplicativity. Suppose that the elements
β0, β1, . . . , βn have been chosen. Take βn+1 ∈ P such that
βn+1 ≥ αn+1, βn+1 ≥ βn, βn+1 ≥ γ(βi, βj)
for all i, j ∈ {0, 1, . . . , n}. Then < βn >n∈ω is a nondecreasing cofinal
sequence in P and B(B(x, βn), βm) ⊆ B(x, βn+m) for all x ∈ X, n,m ∈
N.
Define a mapping d : X × X → ω by the rule d(x, x) = 0 and
d(x, y) = min{n ∈ N : y ∈ B(x, βn), x ∈ B(y, βn)}
for all distinct elements x, y ∈ X. Since the sequence < βn >n∈ω is cofinal
in P and B is connected, then the mapping d is well defined. To show that
d is a metric we have only to check a triangle inequality. Let x, y, z be dis-
tinct elements of X and let d(x, y) = n, d(y, z) = m. Since y ∈ B(x, βn)
and z ∈ B(y, βm), then z ∈ B(B(x, βn), βm) ⊆ B(x, βn+m). Since
y ∈ B(z, βm) and x ∈ B(y, βn), then x ∈ B(B(z, βm), βn) ⊆ B(z, βn+m).
Hence, d(x, z) ≤ n + m.
Consider the ball structure B(X, d) and note that
Bd(x, n) = B(x, βn)
⋂
B∗(x, βn).
Since B is symmetric, then the identity mapping of X is an isomorphism
between B and B(X, d).
Remark 1. A metric d on a set X is called integer if d(x, y) is an integer
number for all x, y ∈ X. It follows from the proof of Theorem 1 that,
for every metrizable ball structure B = (X,P,B), there exists an integer
metric d on X such that B and B(X, d) are isomorphic.
Remark 2. Let B = (X,P,B) be an arbitrary ball structure. Consider
a metric d on X defined by the rule d(x, x) = 0 and d(x, y) = 1 for
all distinct elements of X. Then the identity mapping i : X → X is a
≺-mapping of B onto B(X, d). In particular, for every ball structure B,
there exists a metric space (X, d) such that B ≺ B(X, d).
134 Metrizable ball structures
Remark 3. Let B = (X,P,B) be a connected multiplicative ball struc-
ture, cfB ≤ ℵ0. Repeating arguments of Theorem 1, we can prove that
there exists a metric d on X such that the identity mapping i : X → X
is a ≺-mapping of B(X, d) onto B.
Question 1. Characterize the ball structure B = (X,P,B), which admit
a metric d on X such that the identity mapping i : X → X is a ≺-
mapping of B(X, d) onto B.
By Remark 2, every ball structure can be strengthened to some mer-
tizable ball structure, so Question 1 asks about ball structure, which can
be weekened to metrizable.
Example 2. Let Gr = (V,E) be a connected graph with a set of vertices
V and a set of edges E, E ⊆ V × V . Endow V with a path metric d,
where d(x, y), x, y ∈ V is a length of the shortest path between x and
y. Denote by B(Gr) the ball structure B(V, d). Obviously, B(Gr) is
metrizable.
Our next target is a description of the ball structures, isomorphic to
B(Gr) for an appropriate graph Gr.
Let B = (X,P,B) be an arbitrary ball structure, α ∈ P . We say that
a finite sequence x0, x1, . . . , xn of elements of X is an α-path of length
n if xi−1 ∈ B(xi, α), xi ∈ B(xi−1, α) for every i ∈ {1, 2, . . . , n}. A ball
structure B is called an α-path connected if, for every β ∈ P , there exists
µ(β) ∈ ω such that x ∈ B(y, β), y ∈ B(x, β) imply that there exists an
α-path of length ≤ µ(β) between x and y. Note that B(Gr) is 1-path
connected for every connected graph Gr.
A ball structure B = (X,P,B) is called path connected if B is α-path
connected for some α ∈ P .
Lemma 8. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be isomorphic
ball structures. If B1 is path connected, then B2 path connected.
Proof. Let f : X1 → X2 be an isomorphism between B1 and B2. Choose
α ∈ P1 such that B1 is α-path connected and fix a corresponding map-
ping µ : P1 → ω. Since f is a ≺-mapping, then there exists β ∈ P2 such
that
f(B1(x, α)) ⊆ B2(f(x), β)
for every x ∈ X1. Since f is a ≻-mapping, then there exists a mapping
h : P2 → P1 such that
B2(f(x), λ) ⊆ f(B1(x, h(λ))
for any x ∈ X1, λ ∈ P2.
I.V. Protasov 135
Fix any λ ∈ P2 and suppose that
f(x) ∈ B2(f(y), λ), f(y) ∈ B2(f(x), λ).
Since f is a bijection, then x ∈ B1(y, h(λ)), y ∈ B1(x, h(λ)). Since B1
is α-path connected, then there exists an α-path x = x0, x1, . . . , xm = y
of length ≤ µ(h(λ)). Then f(x) = f(x0), f(x1), . . . , f(xm) = f(y) is a
β-path of length ≤ µ(h(λ)) between f(x) and f(y).
Theorem 2. For every ball structure B, the following statements are
equivalent
(i) B is metrizable and path connected;
(ii) B is isomorphic to a ball structure B(Gr) for some connected
graph Gr.
Proof. (ii)⇒(i). Clearly, B(Gr) is metrizable and path connected.
Hence, B is metrizable and path connected by Lemma 8.
(i)⇒(ii). Fix a path connected metric space (X, d) such that B is
isomorphic to B(X, d). Then there exists m ∈ ω such that (X, d) is m-
path connected. Consider a graph Gr = (X,E) with the set E of edges
defined by the rule
(x, y) ∈ E if and only if x 6= y and d(x, y) ≤ m.
Since B(X, d) is path connected, then the graph Gr is connected.
Let d
′
be a path metric on the graph Gr. By assumption, for every
n ∈ ω, there exists µ(n) ∈ ω such that d(x, y) ≤ n implies that there
exists a m-path of length ≤ µ(n) in (X, d) between x and y. Hence,
d(x, y) ≤ n implies d
′
(x, y) ≤ µ(n). On the other side, d
′
(x, y) ≤ k
implies that d(x, y) ≤ km. Therefore, the identity mapping of X is an
isomorphism between the ball structures B(X, d) and B(Gr).
Example 3. Let X = {2n : n ∈ ω}, d(x, y) = |x − y| for any x, y ∈ X.
By Theorem 2, there are no connected graphs Gr such that B(X, d) is
isomorphic to B(Gr).
Example 4. Let d be an euclidean metric on Rn. By Theorem 2, there
exists a connected graph Grn = (Rn, En) such that B(Rn, d) is isomor-
phic to B(Grn).
By Remark 2, for every ball structure B = (X,P,B), there exists a
connected graph Gr = (X,E), E = {(x, y) : x, y ∈ X,x 6= y} such that
the identity mapping i : X → X is a ≻-mapping of B(Gr) onto B.
Question 2. Characterize the ball structure, which admit a ≻-bijection
to the ball structure B(Gr) for an appropriate graph Gr.
136 Metrizable ball structures
A metric d on a set X is called non-Archimedian if
d(x, z) ≤ max{d(x, y), d(y, z)}
for all x, y, z ∈ X. The following definitions will be used to describe the
ball structures isomorphic to B(X, d) for an appropriate non-Archimeian
metric space (X, d).
Let B = (X,P,B) be an arbitrary ball structure, x ∈ X, α ∈ P . We
say that a ball B(x, α) is a cell if B(y, α) = B(x, α) for every y ∈ B(x, α).
If (X, d) is a non-Archimedian metric space, then each ball B(x, r), x ∈
X, r ∈ R+ is a cell.
Given any x ∈ X, α ∈ P , denote
Bc(x, α) = {y ∈ X : there exists an α − path between x and y}.
A ball structure Bc = (X,P,Bc) is called a cellularization of B. Note
that each ball Bc(x, α) is a cell.
We say that a ball structure B is cellular if the identity mapping
i : X → X is an isomorphism between B and Bc. In other words, B
is cellular if and only if, for every α ∈ P , there exists β ∈ P such that
B(x, α) ⊆ Bc(x, β) for every x ∈ X and, for every β ∈ P , there exists
α ∈ P such that Bc(x, β) ⊆ B(x, α) for every x ∈ X.
A ball structure B = (X,P,B) is called directed if, for any α, β ∈ P ,
there exists γ ∈ P such that α ≤ γ, β ≤ γ.
Lemma 9. If B = (X,P,B) is a directed symmetric ball structure, then
the identity mapping i : X → X is a ≺-mapping of B onto Bc.
Proof. Given any α ∈ P , choose β, γ ∈ P such that
B(x, α) ⊆ B∗(x, β) ⊆ B(x, γ)
for every x ∈ X. Since B is directed, we may assume that β ≤ γ.
Take any element y ∈ B(x, α). Then x ∈ B(y, β) ⊆ B(y, γ). Thus,
y ∈ B(x, γ), x ∈ B(y, γ). Hence, there exists a β-path of length ≤ 1
between x and y. It means that y ∈ Bc(x, γ), so B(x, α) ⊆ Bc(x, γ).
Lemma 10. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be ball struc-
tures. If f : X1 → X2 is a ≺-mapping of B1 to B2, then f is a ≺-mapping
of Bc
1 to Bc
2. If f is an isomorphism between B1 and B2, then f is a
isomorphism between Bc
1 and Bc
2.
Proof. Given any α ∈ P1, choose β ∈ P2 such that f(B1(x, α)) ⊆
B2(f(x), β) for every x ∈ X. Take any y ∈ Bc
1(x, α) and choose an
α-path x = x0, x1, . . . , xn = y between x and y. Then
f(x) = f(x0), f(x1), . . . , f(xn) = f(y)
I.V. Protasov 137
is a β-path between f(x) and f(y). Hence, f(y) ∈ Bc
2(f(x), β) and
f(Bc
1(x, α)) ⊆ Bc
2(f(x), β) for every x ∈ X1.
Suppose that f is an isomorphism between B1 and B2. By the first
statement, f is a ≺-mapping of Bc
1 to Bc
2 and f−1 is a ≺-mapping of Bc
2
to Bc
1. Hence, f is an isomorphism between Bc
1 and Bc
2.
Lemma 11. Let B1 = (X1, P1, B1) and B2 = (X2, P2, B2) be isomorphic
ball structures. If B1 is cellular, then B2 is cellular.
Proof. Let f : X1 → X2 be an isomorphism between B1 and B2. Denote
by i1 : X1 → X1 and i2 : X2 → X2 the identity mappings. Clearly,
f−1 is an isomorphism between B2 and B1. By the Lemma 10, f is an
isomorphism between Bc
1 and Bc
2. By assumption, i1 is an isomorphism
between B1 and Bc
1. Since i2 = fi1f
−1, then i2 is an isomorphism
between B2 and Bc
2.
Theorem 3. For every ball structure B, the following statements are
equivalent
(i) B is metrizable and cellular;
(ii) there exists a non-Archimedian metric space (X,d) such that B
is isomorphic to B(X, d).
Proof. (ii)⇒(i). Clearly, B(X, d) is metrizable and cellular. Hence, B is
metrizable and cellular by Lemma 11.
(i)⇒(ii). Fix a metric space (X, d
′
) such that B(X, d
′
) is cellular and
isomorphic to B. Define a mapping d : X × X → ω by the rule
d(x, y) = min{m ∈ ω : y ∈ Bc(x,m)}.
Obviously, d(x, x) = 0 and d(x, y) = d(y, x) for all x, y ∈ X.
Let x, y, z ∈ X and let d(x, y) = m, d(y, z) = n, m ≤ n. Then
y ∈ Bc(x,m), z ∈ Bc(y, n). It follows that there exists a n-path between
x and z. Hence, z ∈ Bc(x, n) and d(x, z) ≤ n. Thus, we have proved
that d is a non-Archimedian metric on X.
Since d(x, y) ≤ d
′
(x, y), then the identity mapping i : X → X is a
≺-mapping of B(X, d) to B(X, d
′
). Since B(X, d
′
) is cellular, then there
exists a mapping h : ω → ω such that Bc(x,m) ⊆ B(x, h(m)) for all
x ∈ X,m ∈ ω. Hence, i is a ≻-mapping of B(X, d) to B(X, d
′
). Hence,
B(X, d) and B(X, d
′
) are isomorphic.
By Remark 2, for every ball structure B = (X,P,B), there exists a
non-Archimedian metric d on X such that the identity mapping of X is
a ≻-mapping of B(X, d) to B.
138 Metrizable ball structures
Lemma 12. For every metric space (X, d), there exists a family {Pn :
n ∈ ω} of partitions of X with the following properties
(i) every partition Pn+1 is an enlargement of Pn, i.e. every cell of
the partition Pn+1 is a union of some cells of the partition Pn;
(ii) there exists a function f : ω → ω such that, for every C ∈ Pn
and every x ∈ C, C ⊆ B(x, f(n));
(iii) for any x, y ∈ X, there exists n ∈ ω such that x, y are in the
same cell of the partition Pn.
Proof. Fix any well-ordering {xα : α < γ} of X. Choose a subset Y0 ⊆
X, x0 ∈ Y0 such that the family {B(y, 1) : y ∈ Y0} is disjoint and
maximal. For every x ∈ X, pick a minimal element f0(x) ∈ Y0 such that
B(x, 1)
⋂
B(f0(x), 1) 6= ∅. Put H(x, 1) = {z ∈ X : f0(z) = f0(x)} and
note that the family {H(y, 1) : y ∈ Y0} is a partition of X. If x, z ∈
H(y, 1), then d(x, y) ≤ 2, d(x, z) ≤ 2. Therefore, H(y, 1) ⊆ B(x, 4) for
every x ∈ H(y, 1). Put P0 = {H(y, 1) : y ∈ Y0}, f(0) = 4.
Assume that the partitions P0,P1, . . . ,Pn−1 have been constructed
and the values f(0), f(1), . . ., f(n− 1) have been determined. Choose a
subset Yn ⊆ X, x0 ∈ Yn such that the family {B(y, n + 1) : y ∈ Yn} is
disjoint and maximal. Define a mapping fn : X → Yn inductively such
that fn is constant on each cell of the partition Pn−1. Put fn(x) = x0
for every x ∈ X such that H(x, n)
⋂
B(x0, n + 1) 6= ∅. Then take the
minimal element x ∈ X such that fn(x) is not determined. Choose the
minimal element y ∈ Yn such that B(x, n + 1)
⋂
B(y, n + 1) 6= ∅. Put
fn(x) = y and fW (z) = y for every z ∈ H(x, n). After this transfinite
procedure, we denote H(x, n + 1) = {z ∈ X : fn(z) = fn(x)}. Put
Pn = {H(y, n + 1) : y ∈ Yn}. Then Pn is a partition of X and each cell
of Pn is a union of some cells of Pn−1. Thus, (i) is satisfied.
If z ∈ H(y, n + 1), then d(z, y) ≤ f(n − 1) + 2(n + 1). Hence, to
satisfy (ii), put f(n) = 2(f(n − 1) + 2(n + 1)).
At last, given any x, y ∈ X, choose m ∈ ω such that d(x0, x) ≤ m+1,
d(x0, y) ≤ m + 1. Thus x, y are in the same cell of the partition Pm and
we have verified (iii).
Theorem 4. For every metric space (X,d), there exists a non-Archime-
dian metric d
′
on X such that the identity mapping i : X → X is a
≺-mapping of B(X, d
′
) to B(X, d).
Proof. Fix a family {Pn : n ∈ ω} of partitions of X, satisfying (i), (ii),
(iii) from Lemma 12. Define a mapping d
′
: X × X → ω by the rule
d
′
(x, y) = min{n : x and y are in the same cell of Pn}.
I.V. Protasov 139
By (iii), d
′
is well defined. By (i), d
′
is a non-Archimedian metric.
By (ii), the identity mapping of X is a ≺-mapping of B(X, d
′
) onto
B(X, d).
Now we consider non-metrizable versions of Lemma 12 and Theorem
4.
Lemma 13. Let B = (X,P,B) be a directed symmetric multiplicative
ball structure. Then there exists a family {Pα : α ∈ P} of partitions of
X such that
(i) for every α ∈ P , there exists β ∈ P such that C ⊆ B(x, β) for
every C ∈ Pα and every x ∈ C.
Moreover, if B is connected then
(ii) for any x, y ∈ X, there exists α ∈ P such that x, y are in the
same cell of the partition Pα.
Proof. Fix any well-ordering of X and denote by x0 its minimal element.
Fix α ∈ P and choose a subset Y ⊆ X, x0 ∈ Y such that the family
{B(y, α) : y ∈ Y } is disjoint and maximal. For every x ∈ X, pick a
minimal element f(x) ∈ Y such that B(x, α)
⋂
B(f(x), α) 6= ∅. Put
H(x, α) = {z ∈ X : f(z) = f(x)}. Then the family Pα = {H(y, α) : y ∈
Y } is a partition of X.
Since B is directed and symmetric, then there exists α
′
> α such that
y ∈ B(x, α) implies x ∈ B(y, α
′
).
Fix x ∈ X and take x
′
∈ B(x, α)
⋂
B(f(x), α). Then x, x
′
, f(x) is
an α
′
-path. Hence, for every z ∈ H(x, α), we can find an α
′
-path of
length 4 between x and z. Using multiplicativity of B, choose β ∈ P
such that y4 ∈ B(y0, β) for every α
′
-path y0, y1, y2, y3, y4 in X. Then
H(x, α) ⊆ B(x, β).
Suppose that B is connected and x, y ∈ X. Since B is directed, then
there exists α ∈ P such that x0 ∈ B(x, α), x0 ∈ B(y, α). Hence, x, y
belong to the cell H(x0, α) of the partition Pα.
Theorem 5. If a ball structure B = (X,P,B) is directed symmetric and
multiplicative, then there exists a cellular ball structure B
′
= (X,P,B
′
)
such that the identity mapping of X is a ≺-mapping of B
′
onto B. More-
over, if B is connected, then B
′
is connected.
Proof. Use the family of the partitions {Pα : α ∈ P} from Lemma 13 and
put B
′
(x, α) = H(x, α). Clearly, each ball B
′
(x, α) is a cell. By (i), the
identity mapping of X is a ≺-mapping of B
′
onto B. If B is connected,
then B
′
is connected by (ii).
140 Metrizable ball structures
Example 5. Let G be a group and let Fine(G) be a family of all finite
subsets of G containing the identity e. Given any g ∈ G, F ∈ Fine(G),
put B(g, F ) = Fg. A ball structure B(G) = (G,Fine(G), B) is denoted
by B(G). It is easy to show, that B(G) is directed connected symmetric
and multiplicative.
Now we apply the above results to the ball structures of groups.
Theorem 6. Let G be a group. Then a ball structure B(G) is metrizable
if and only if |G| ≤ ℵ0.
Proof. Apply Theorem 1.
Theorem 7. For every group G, the following statements are equivalent
(i) G is finitely generated;
(ii) B(G) is isomorphic to B(Gr) for some connected graph Gr
Proof. (i)⇒(ii). Let S be a finite set of generators of G. Consider a
Cayley graph Gr = (G,E) of G determined by S. By definition, (x, y) ∈
E if and only if x 6= y and x = ty for some t ∈ S
⋃
S−1. Clearly, the
identity mapping of G is an isomorphism between B(G) and B(Gr).
(ii)⇒(i). By Theorem 2, there exists F ∈ Fin such that B(G) is
F -path connected. In particular, for every g ∈ G, there exists a F -path
between e and g. Hence, F generates G.
A group G is called locally finite if every finite subset of G generates
a finite subgroup.
Theorem 8. Let G be a group. Then a ball structure B(G) is cellular if
and only if G is locally finite.
Proof. Let G be locally finite. Denote by Fins the family of all finite
subgroups of G. Then Fins is cofinal in Fin and each ball B(g, F ),
F ∈ Fins is a cell. Hence, B(G) is cellular.
Assume that B(G) is cellular. Note that Bc(e, F ) = gpF for every
F ∈ Fin, where gpF is a subgroup of G generated by F . Since B is
isomorphic to Bc, then each ball Bc(g, F ) is finite. In particular, gpF is
finite for every F ∈ Fin.
Remark 4. Let G1, G2 be countable locally finite group. By [2, Theorem
4], B(G1) ≻ B(G2) and B(G1) ≺ B(G2). By [2, Theorem 5], B(G1) and
B(G2) are isomorphic if and only if, for every finite subgroup F of G1,
there exists a finite subgroup H of G2 such that |F | is a divisor of |H|,
and vice versa. A problem of classification up to an isomorphism of ball
structures of uncountable locally finite groups is open.
I.V. Protasov 141
Theorem 9. For every countable group G, there exists a non-Archime-
dian metric d on G with the following property
(i) for each n ∈ ω, there exists F ∈ Fin such that d(x, y) ≤ n implies
x ∈ Fy.
Proof. Apply Theorem 6 and Theorem 4.
Theorem 10. For every group G, there exists a cellular ball structure
B
′
= (G,Fin,B
′
) such that the identity mapping of G is a ≺-mapping
of B
′
onto B(G).
Proof. Apply Theorem 5.
Question 3. Characterize the ball structures isomorphic to the ball
structures of groups.
M.Zarichnyi has pointed out that Theorem 1 has a counterpart in
the asymptotic topology [3]. This theorem answers the Open Question
1 from [4]. The results of this paper was announced in [5].
References
[1] I.V. Protasov. Combinatorial size of subsets of groups and graphs// Algebraic sys-
tems and applications. Proc. Inst. math. NAN Ukraine, 2002.
[2] I.V. Protasov. Morphisms of ball’s structures of groups and graphs// Ukr. Math.
J. 53, 2002, 6, 847-855.
[3] G. Skandalis, J.L.Tu, G.Yu. Coarse Baum - Connes conjecture and groupoids//
Preprint, 2000.
[4] N. Nekrashevych. Uniformly bounded spaces// Voprosy algebry, 1999, 14, 47-67.
[5] I.V. Protasov. On metrizable ball’s structures// Intern. Conf. on Funct. Analysis
and its Appl. Book of abstracts, Lviv, 2002, 162-164.
Contact information
I.V. Protasov Kyiv Taras Shevchenko University, Ukraine
E-Mail: kseniya@profit.net.ua
Received by the editors: 24.09.2002.
|