()


@ Appl. Gen. Topol. 19, no. 1 (2018), 85-90doi:10.4995/agt.2018.7721
c© AGT, UPV, 2018

Counting coarse subsets of a countable group

Igor Protasov and Ksenia Protasova

Department of Computer Science and Cybernetics, Kyiv University, Volodymyrska 64, 01033,

Kyiv, Ukraine (i.v.protasov@gmail.com, ksuha@freenet.com.ua)

Communicated by F. Lin

Abstract

For every countable group G, there are 2
ω

distinct classes of coarsely

equivalent subsets of G.

2010 MSC: 54E15; 20F69.

Keywords: ballean; coarse structure; asymorphism; coarse equivalence.

1. Introduction and results

Following [5], [6], we say that a ball structure is a triple B = (X, P, B), where
X, P are non-empty sets, and for all x ∈ X and α ∈ 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 . The set X is called the support of B, P is called the set
of radii.

Given any x ∈ X, A ⊆ X, α ∈ P , we set

B∗(x, α) = {y ∈ X : x ∈ B(y, α)}, B(A, α) =
⋃

a∈A

B(a, α),

B∗(A, α) =
⋃

a∈A

B∗(a, α).

A ball structure B = (X, P, B) is called a ballean if

• for any α, β ∈ P , there exist α′, β′ such that, for every x ∈ X,

B(x, α) ⊆ B∗(x, α′), B∗(x, β) ⊆ B(x, β′);

Received 31 May 2017 – Accepted 10 September 2017

http://dx.doi.org/10.4995/agt.2018.7721


I. Protasov and K. Protasova

• for any α, β ∈ P , there exists γ ∈ P such that, for every x ∈ X,

B(B(x, α), β) ⊆ B(x, γ);

• for any x, y ∈ X, there exists α ∈ P such that y ∈ B(x, α).

We note that a ballean can be considered as an asymptotic counterpart of a
uniform space, and could be defined [7] in terms of entourages of the diagonal
∆X in X ×X. In this case a ballean is called a coarse structure. For categorical
look at the balleans and coarse structures as ”two faces of the same coin” see
[2].

Let B = (X, P, B), B′ = (X′, P ′, B′) be balleans. A mapping f : X → X′

is called coarse if, for every α ∈ P , there exists α′ ∈ P ′ such that, for every
x ∈ X, f(B(x, α)) ⊆ B′(f(x), α′).

A bijection f : X → X′ is called an asymorphism between B and B
′

if f and
f−1 are coarse. In this case B and B

′

are called asymorphic.
Let B = (X, P, B) be a ballean. Each subset Y of X defines a subballean

BY = (Y, P, BY ), where BY (y, α) = Y ∩ B(y, α). A subset Y of X is called
large if X = B(Y, α), for α ∈ P . Two balleans B and B′ with supports X
and X′ are called coarsely equivalent if there exist large subsets Y ⊆ X and
Y ′ ⊆ X′ such that the subballeans BY and B

′
Y ′ are asymorphic.

Every infinite group G can be considered as the ballean (G, FG, B), where
FG is the family of all finite subsets of G, B(g, F) = Fg

⋃
{g}.

We note that finitely generated groups are finitary coarsely equivalent if and
only if G and H are quasi-isometric [3, Chapter 4].

A classification of countable locally finite groups (each finite subset generates
finite subgroup) up to asymorphisms is obtained in [4] (see also [5, p. 103]).

Two countable locally finite groups G1 and G2 are asymorphic if and only if
the following conditions hold:

(i) for every finite subgroup F ⊂ G1, there exists a finite subgroup H of
G2 such that |F | is a divisor of |H|;

(ii) for every finite subgroup H of G2, there exists a finite subgroup F of
G1 such that |F | is a divisor of |F |.

It follows that there are continuum many distinct types of countable locally
finite groups and each group is asymorphic to some direct sum of finite cyclic
groups.

The following coarse classification of countable Abelian groups is obtained
in [1].

Two countable Abelian groups are coarsely equivalent if and

only if the torsion-free ranks of G and H coincide and G and
H are either both finitely generated or infinitely generated.

In particular, any two countable torsion Abelian groups are coarsely equiv-
alent.

c© AGT, UPV, 2018 Appl. Gen. Topol. 19, no. 1 86



Counting coarse subsets of a countable group

Given a group G, we consider each non-empty subsets as a subballean of G
and say that a class of all pairwise coarsely equivalent subsets is a coarse subset
of G.

For a countable group G, we prove that there as many coarse subsets of G
as possible by the cardinal arithmetic.

Theorem 1.1. For a countable group G, there are 2ω coarse subsets of G.

Every countable group G contains either countable finitely generated sub-
group or countable locally finite subgroup, so we split the proof into corre-
sponding cases.

2. Proof: finitely generated case

2.1. We take a finite system S, S = S−1 of generators of G and consider the
Cayley graph Γ with the set of vertices G and the set of edges {{g, h} : gh−1 ∈
S, g 6= h}. We denote by ρ the path metric on Γ and choose a geodesic ray
V = {vn : n ∈ ω}, v0 is the identity of G, ρ(vn, vm) = |n − m|.

Then the subballean of G with the support V is asymorphic to the metric
ballean (N, N

⋃
{0}, B), where B(x, r) = {y ∈ N : d(x, y) ≤ r}, d(x, y) =

|x − y|. Thus, it suffices to find a family F, |F| = 2ω of pairwise coarsely
non-equivalent subsets of N.

2.2. We choose a sequence (In)n∈ω of intervals of N, In = [an, bn], bn < an+1
such that

(1) bn − an > n an.

Then we take an almost disjoint family A of infinite subsets of ω such that
|A| = 2ω. Recall that A is almost disjoint if |W

⋂
W ′| < ω for all distinct

W, W ′ ∈ A.
For each W ∈ A, we denote IW =

⋃
{In : n ∈ W}. To show that F = {IW :

W ∈ A} is the desired family of subsets of N, we take distinct W, W ′ ∈ A and
assume that IW , IW ′ are coarsely equivalent. Then there exist large subsets
X, X′ of IW , IW ′ , and an asymorphism f : X −→ X

′. We choose r ∈ N such
that

IW ⊆ B(X, r), IW ′ ⊆ B(X
′, r)

and note that if an interval I of length 2r is contained in IW then I must
contain at least one point of X, and the same holds for the pair IW ′ , X

′.
Since f is an asymorphism, we can take t ∈ N such that, for all x ∈ X,

x′ ∈ X′,

(2) f(BX(x, 2r + 2) ⊆ BX′(f(x), t);

(3) f−1(BX′(x
′, 2r + 2) ⊆ BX(f

−1(x′), t).

We use (1) to choose m ∈ W\W ′, m > max(W
⋂
W ′) such that

(4) bm − am > 2ram;

c© AGT, UPV, 2018 Appl. Gen. Topol. 19, no. 1 87



I. Protasov and K. Protasova

(5) bm − am > 2t.

2.3. We denote Z = X
⋂
[am, bm] and enumerate Z in increasing order

Z = {z0, . . . , zk}. Then d(zi, zi+1) ≤ 2r + 2 because otherwise the interval
[zi + 1, zi+1 − 1] of length 2r has no points of X.

If f(z0) < am then, by (2) and (5), f(Z) ⊆ [1, am − 1]. On the other hand,
k ≥ (bm − am)/2r − 1 and, by (4), (bm − am)/2r > am. Hence, k > am − 1
contradicting f(Z) ⊆ [1, am − 1] because f is a bijection.

If f(z0) > bm then we take s ∈ W
′ such that f(z0) ∈ Is. Since m >

max(W ∧ W ′) and s > m, we have s ∈ W ′ \ W , so we can repeat above
argument for f−1 and Is in place of f and Im with usage (3) instead of (2).

3. Proof: locally finite case

3.1. Let G be an arbitrary countable group and let X, A be infinite subsets
of G. Suppose that there exist an infinite subset Y of X, a partition A = B

⋃
C

and k, l ∈ N, k < l such that

(6) there exists H ∈ FG such that, for every y ∈ Y ,

|BX(y, H)| ≥ k;

(7) for every F ∈ FG, there exists Y
′ ∈ FG such that, for every y ∈ Y \Y

′,

|BX(y, H)| ≥ l;

(8) there exists K ∈ FG such that, for every b ∈ B,

|BA(b, K)| > l;

(9) for every F ∈ FG, there exists C
′ ∈ FG such that, for every c ∈ C\C

′,

|BA(c, F)| < k.

Then X and A are not asymorphic.
We suppose the contrary and let f : X −→ A be an asymorphism. We take

an infinite subset I of Y such that either f(I) ⊂ C or f(I) ⊂ B.
Assume that f(I) ⊂ C and choose F ∈ FG such that, for every x ∈ X,

f(BX(x, H)) ⊆ BA(f(x), F).

For this F , we use (9) to choose corresponding C′. We take y ∈ I such that
f(y) ∈ C \ C′. By (6), f(B(y, H)) ≥ k. By (9), BA(f(y), F) < k and we get a
contradiction because f is a bijection.

If f(I) ⊂ B then, by (8), BA(b, K) > l for every b ∈ f(I). Since f
−1 is

coarse, there is F ∈ FG such that, for every a ∈ A

f−1(BA(a), K) ⊆ BX(f
−1(a), F).

For this F , we choose Y ′ satisfying (7) and get a contradiction.

3.2. Now we assume that G is locally finite and show a plan how to choose
the desired family F, |F| = 2ω of pairwise coarsely non-equivalent subsets of G.

c© AGT, UPV, 2018 Appl. Gen. Topol. 19, no. 1 88



Counting coarse subsets of a countable group

We construct some special sequence (Yn)n∈ω of pairwise disjoint subsets of
G. Then we take a family A of almost disjoint infinite subset of ω, |F| = 2ω,
denote

(10) XW =
⋃
{Yn : n ∈ W}, W ∈ A,

and get F as {XW : W ∈ A}.

3.3. We represent G as the union of an increasing chain {Fn : n ∈ ω} of
finite subgroups such that

(11) |Fn+1| > |Fn|
2.

Then we choose a double sequence (gnm)n,m∈ω of elements of G such that

(12) FnFmgnm
⋂
FiFjgij = ∅ for all distinct (n, m), (i, j) from ω ×ω, and

put

Yn =
⋃

{Fmgnm : m ∈ ω}.

3.4. We take distinct W, W ′ ∈ A and prove that XW and XW ′ (see (10)) are
not coarsely equivalent. We suppose the contrary and choose large asymorphic
subsets ZW and ZW ′ of XW and XW ′. Then we take t ∈ ω such that

XW ⊆ FtZW , XW ′ ⊆ FtZW ′.

If n > t and either Fngnm ⊂ XW or Fngnm ⊂ XW ′ then

(13) |Fngnm
⋂
ZW | ≥

|Fn|
|Ft|

, |Fngnm
⋂
ZW ′| ≥

|Fn|
|Ft|

.

To apply 3.1, we choose s ∈ W \ W ′, s > t and denote

X = ZW , Y = Ys
⋂

ZW , A = ZW ′, B =
⋃

{Yi : i ∈ W
′, i > s},

C =
⋃

{Yi : i ∈ W
′, i < s}, k =

|Fs|

|Ft|
, l = |Fs|.

By (13) with s = n, we get (6). By (12) with s = n, we get (7).
If n > s then |Fn|/|Ft| > |Fn|/|Fs|. By (11), |Fn|/|Fs| > |Fs|, so |Fn|/|Ft| >

|Fs| and, by (13), we have (8).
If n < s then |Fn| < |Fs|/|Ft| and, by (12), we get (9).

4. Comments

A subset A of an infinite group G is called

• thick if, for every F ∈ FG , there exists g ∈ A such that Fg ⊂ A;

• small if L \ A is large for every large subset L of G;

c© AGT, UPV, 2018 Appl. Gen. Topol. 19, no. 1 89



I. Protasov and K. Protasova

• thin if, for every F ∈ FG , there exists H ∈ FG such that BA(g, F) = {g}
for each g ∈ A \ H.

A subset A is thick if and only if L
⋂
A 6= ∅ for every large subset L of G.

For a countable group G, in the proof of Theorem 1.1, we construct 2ω pairwise
coarsely non-equivalent thick subsets of G.

Every large subset L of G is coarsely equivalent to G, so any two large subsets
of G are coarsely equivalent. If G is countable then any two thin subset S, T
of G are asymorphic: any bijection f : S −→ T is an asymorphism. Every thin
subset is small. But a small subset S of G could be asymorphic to G: we take
a group G containing a subgroup S isomorphic to G such that the index of S
in G is infinite.

References

[1] T. Banakh, J. Higes and M. Zarichnyi, The coarse classification of countable abelian
groups, Trans. Amer. Math. Soc. 362 (2010), 4755–4780.

[2] D. Dikranjan and N. Zava, Some categorical aspects of coarse spaces and ballean, Topol-
ogy Appl. 225 (2017), 164–194.

[3] P. de la Harpe, Topics in geometric group theory, University Chicago Press, 2000.
[4] I. V. Protasov, Morphisms of ball structures of groups and graphs, Ukr. Mat. Zh. 53

(2002), 847–855.
[5] I. Protasov and T. Banakh, Ball structures and colorings of groups and graphs, Math.

Stud. Monogr. Ser., Vol. 11, VNTL, Lviv, 2003.
[6] I. Protasov and M. Zarichnyi, General asymptology, Math. Stud. Monogr. Ser., Vol. 12,

VNTL, Lviv, 2007.
[7] J. Roe, Lectures on coarse geometry, Amer. Math. Soc., Providence, R.I, 2003.

c© AGT, UPV, 2018 Appl. Gen. Topol. 19, no. 1 90