Український математичний вiсник
Том 7 (2010), № 2, 220 – 257
Selective survey on Subset
Combinatorics of Groups
Igor V. Protasov
Abstract. We survey recent results concerning the combinatorial size
of subsets of groups. For a cardinal κ, according to its arrangement in
a group G, a subset of G is distinguished as κ-large, κ-small, κ-thin, κ-
thick and Pκ-small. By analogy with topology, there arise the following
combinatorial cardinal invariants of a group: density, cellularity, resolv-
ability, spread etc. The paper consists of 7 sections: Ballean context,
Amenability, Ideals, Partitions, Packings, Around thin subsets, Color-
ings.
2010 MSC. 20A05, 20F99, 22A15, 06E15, 06E25.
Key words and phrases. Large, small, thin, thick subsets of groups,
density, cellularity, resolvability, spread, packing number, kaleidoscopical
configuration.
Introduction
Selectivity of the survey is in the choice of the subject: the combina-
torial size of subsets of groups. We leave outside (or touch a little bit)
the other aspects of the Subset Combinatorics of Groups, in particular,
the Additive Combinatorics [52] and the Ramsey Group Theory [22, 41].
By the combinatorial size of a subset A of a group G we mean some
(mainly, cardinal) characteristic which reflects an arrangement of A in
G. The main results under consideration concern the groups, however,
for our goal it is more convenient to use the terminology of G-spaces and,
sometimes, much more general context of balleans.
Let G be a group with the identity e, X be a G-space with the action
G ×X → X, (g, x) 7→ gx. For the subsets F ⊆ G, A ⊆ X, FA denotes
the subset {ga : g ∈ F, a ∈ A} of X. For a cardinal κ, [G]<κ denotes the
set {F ⊆ G : |F | < κ}.
Received 13.03.2010
ISSN 1810 – 3200. c© Iнститут математики НАН України
I. V. Protasov 221
Let κ be an infinite cardinal, κ 6 |G|. We say that a subset A of X is
• κ-large if there exists F ∈ [G]<κ such that X = FA;
• κ-small if L \A is κ-large for every κ-large subset L;
• κ-thick if, for every F ∈ [G]<κ, there exists a ∈ A such that Fa ⊆ A;
• κ-thin if |gA ∩A| < κ for every g ∈ G, g 6= e;
• Pκ-small if there exists a subset F , |F | = κ such that the subsets
{gA : g ∈ F} are pairwise disjoint.
In the case κ = ℵ0, we omit κ and write, say, large instead of ℵ0-large.
In what follows, a group G is considered as a left regular G-space with
the action G×G → G, (g, h) 7→ gh.
These definitions are coming from many different sources, sometimes
under different names, in particular, from group theory, topological al-
gebra and topologycal dynamics. In this paper, we consider a lot of
extensions, modifications and refinements of these basic notions.
The names large and small subset of a group were suggested by
A. Bella and V. Malykhin in [9] with the question whether every count-
able group can be partitioned in two large subsets. This question was
answered in [33]: every infinite group can be partitioned in countably
many large subsets. The syndedic and piecewise syndedic subsets of a
group from topological dynamics (see [22, Chapter IV]) are exactly large
and not small subsets.
The thick subsets were used in [31] and [29] to show that every infinite
group G can be partitioned in |G| subsets dense in every totally bounded
group topology on G.
The thin subsets play an important role in algebra of the Stone-Cˇech
compactifications [22]. By means of thin subsets, C. Chou [11] proved
that every infinite amenable group G admits 22|G| distinct Banach mea-
sures.
The P -small subsets were introduced by I. Prodanov [30] as a technical
tool in the study of the minimal topological groups.
In Section 1 we begin an exposition with some basic notions concern-
ing balleans. A ballean is a set X endowed with some family of subsets
which are called the balls. The properties of the family of balls are postu-
lated in such a way that the balleans can be considered as a counterparts
of the uniform topological spaces. Besides the metric spaces which have
the natural ball structures, for every infinite cardinal κ, a G-space X
determines a ballean if we call the set Fx∪{x}, F ∈ [G]<κ, x ∈ X a ball
of radius F around x. Then we classify the subsets of a ballean by their
222 Selective survey on Subset...
combinatorial size and, by analogy with topology, determine the ballean
cardinal invariants, namely, density, cellularity, resolvability, spread etc.
We conclude this section with a list of theorems which allow to calculate
or evaluate the cardinal invariants for a large class of balleans including
the balleans of G-spaces.
In Section 2 we characterize the large, small and thick subsets of an
amenable group. In particular, we show that a subset S of an amenable
group G is small if and only if µ(KS) < 1 for every Banach measure µ
on G and every finite subset K.
Section 3 is about the family Sκ of all κ-small subsets of a group G
and some its subfamilies, in particular, the family Tκ of all κ-thin subsets
and the family Nκ of all non-generative subsets of G. The family Sκ is
an ideal in the Boolean algebra PG of all subsets of G. The main topic
of this section is the group ideals. An ideal I in PG is called a group
ideal if I contains the ideal FG of all finite subsets and, for all A,B ∈ I,
we have AB ∈ I and A−1 ∈ I. We use a correspondence between the
left invariant ideals in PG and closed left ideals in the semigroup βG
(where βG is the Stone-Cˇech compactification of G) to describe the basic
closed ideal in βG. We conclude this section with characterization (in
the ballean context) of the ideal generated by the set of all thin subsets
of a countable group G.
In Section 4, we describe the filtration method and apply it to par-
tition of a group in large number of large and thick subsets, as well as,
in small number of small subsets. A raisin of this section is in two new
theorems on partitions of groups in thin subsets. In particular, one of
them says that the statement “The group (R,+) can be partitioned in
countably many thin subsets” is equivalent to the Continuum Hypothe-
sis. For the second part of this section we selected some 2-Ramsey type
theorems. More precisely, these theorems are true for any partition of a
group in two subsets, but fail to be true for partitions in > 2 subsets.
Section 5 is a survey of results obtained by T. Banakh and N. Lyaskov-
ska on packing numbers. A packing number of a subset A of a group G is
the cardinal pack(A) = sup{|F | : gA∩g′A = ∅ for all distinct g, g′ ∈ F}.
In Section 6 we consider some modifications and refinements of thin
subsets which appeared recently in [25]. The most interesting and delicate
of them are sparse subsets coming from characterization of strongly prime
ultrafilters in βG. Also, some results from this section show that every
infinite group G can be generated by “very” thin subset.
The last Section 7 is much more “kaleidoscopical” than the previous.
We survey briefly some recent cardinal invariants and configurations aris-
ing from the colorings of groups and G-spaces.
During the exposition we fix some open questions and problems. As
I. V. Protasov 223
a rule, all necessary references can be found in comments at the end of
each section.
Acknowledgements. I would like to thank Taras Banakh for much
helpful discussions on combinatorial size, and Ievgen Lutsenko and Olek-
sandr Petrenko for technical help in preparation of the manuscript.
1. Ballean context
1.1. Ball structures and balleans
A ball structure is a triple B = (X,P,B), where X, P are non-empty
sets and, for every 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 and α ∈ P . The set X is called the support of B, P is called the
set of radii.
Given any x ∈ X and A ⊆ X, we put
B∗(x, α) = {y ∈ X : x ∈ B(y, α)}, B(A,α) =
⋃
a∈A
B(a, α).
A ball structure B = (X,P,B) is called a ballean if
• for any α, β ∈ P , there exist α′, β′ ∈ P such that, for every x ∈ X,
B(x, α) ⊆ B∗(x, α′), B∗(x, β) ⊆ B(x, β′);
• for any α, β ∈ P , there exists γ ∈ P such that, for every x ∈ X,
B(B(x, α), β) ⊆ B(x, γ).
A ballean B is called connected if, for any x, y ∈ X, there exists α ∈ P
such that y ∈ B(x, α).
A subset A ⊆ X is called bounded if there exist x ∈ X and α ∈ P
such that A ⊆ B(x, α).
Given a ballean B = (X,P,B), we define a preordering 6 on P by the
rule: α 6 β if and only if B(x, α) ⊆ B(x, β) for every x ∈ X. A subset
P ′ ⊆ P is called cofinal if, for every α ∈ P , there exists α′ ∈ P ′ such that
α 6 α′. The cofinality cfB is the minimal cardinality of cofinal subsets.
A connected unbounded ballean B is called ordinal if there exists a
well-ordered by 6 cofinal subset of P .
Let B1 = (X1, P1, B1), B2 = (X2, P2, B2) be balleans. 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 f is
a bijection such that f and f−1 are ≺-mappings, we say that f is an
224 Selective survey on Subset...
asymorphism. If X1 = X2 and the identity mapping id : X1 → X1 is an
asymorphism, we identify B1 and B2, and write B1 = B2.
Every subset Y ⊆ X determines the subballean BY = (Y, P,BY ) of
B = (X,P,B), where BY (y, α) = Y ∩B(y, α) for all y ∈ Y , α ∈ P .
Two balleans B = (X,P,B) and B′ = (X ′, P ′, B′) are called coarsely
equivalent if there exist Y ⊆ X and Y ′ ⊆ X ′ such that BY , BY ′ are
asymorphic and B(Y, α) = X, B′(Y ′, α′) = X ′ for some α ∈ P , α′ ∈ P ′.
Every metric space (X, d) determines the metric ballean (X,R+, Bd),
where Bd(x, r) = {y ∈ X : d(x, y) 6 r}. Clearly, every metric ballean is
ordinal.
Theorem 1.1. For a ballean B = (X,P,B), the following statements
are equivalent
(i) B is connected and cfB 6 ℵ0;
(ii) B is asymorphic to some metric ballean;
(iii) B is coarsely equivalent to some metric ballean.
Let G be a group with the identity e. We recall that a G-space is a
set X endowed with an action G×X → X, (g, x) 7→ gx such that ex = x
and g(hx) = (gh)x for all x ∈ X and g, h ∈ G. A G-space X is transitive
if, for any x, y ∈ X, there exists g ∈ G such that gx = y.
Given an infinite G-space X and an infinite cardinal κ such that
κ 6 |G|, we consider the ballean Bκ(G,X) = (X, [G]<κ, B), where
B(x, F ) = Fx ∪ {x},
for all x ∈ X, F ∈ [G]<κ. In the case κ = ℵ0, we omit κ and write
B(G,X). In the case G = X and the regular left action of G on X, we
write Bκ(G) instead of Bκ(G,G).
By the definition, a ballean B = (X,P,B) has a bounded geometry if
there exist β ∈ P and a function h : P → ω such that capβB(x, α) 6 h(α)
for all x ∈ X, α ∈ P , where β-capacity of B(x, α) is
capβB(x, α) = sup{|S| : S is a β-separated subset of B(x, α)}
A subset S is called β-separated if B(x, β) ∩ B(y, β) = ∅ for all distinct
x, y ∈ S.
Clearly, B has a bounded geometry provided that, for every α ∈ P
there exists h(α) ∈ ω such that B(x, α) 6 h(α) for all x ∈ X, α ∈ P . In
particular, a ballean B(G,X) of a G-space X is of bounded geometry.
Theorem 1.2. Every ballean of bounded geometry is coarsely equivalent
to some ballean B(G,X) of G-space X.
I. V. Protasov 225
1.2. Subsets of balleans
Let B = (X,P,B) be a ballean. We say that a subset A of X is
• large if there exists α ∈ P such that X = B(A,α);
• small if L \A is large for every large subset L;
• thick if int(A,α) 6= ∅ for every α ∈ P , where int(A,α) = {x ∈ X :
B(x, α) ⊆ A};
• extralarge if int(A,α) is large for every α ∈ P ;
• piecewise large if there exists β ∈ P such that int(B(A, β), α) 6= ∅
for every α ∈ P ;
• pseudodiscrete if, for every α ∈ P , there exists a bounded subset Y
of X such that B(x, α) ∩A = {x} for every x ∈ A \ Y .
In the following propositions we keep together some relationships be-
tween the introduced types of subsets.
Proposition 1.1. For a ballean B = (X,P,B) and a subset S ⊆ X, the
following statements are equivalent
(i) S is small;
(ii) S is not piecewise large;
(iii) X \ S is extralarge;
(iv) (X \ S) ∩ L is large for every large subset L of X.
Proposition 1.2. Let B = (X,P,B) be a ballean. A subset T of X is
thick if and only if T ∩ L 6= ∅ for every large subset L of X.
We recall that a family I of subsets of a set X is called an ideal in the
Boolean algebra PX of all subsets of X if, for any A,B ∈ I and A′ ⊆ A,
one has A ∪ B ∈ I and A′ ∈ I. We note that the family of all bounded
subsets of a connected ballean with the support X forms an ideal in PX .
Proposition 1.3. For every ballean B = (X,P,B) the family S of all
small subsets of X is an ideal in PX . In particular, X cannot be parti-
tioned in finitely many small subsets.
226 Selective survey on Subset...
Each of above defined types of subsets of a ballean has its counterparts
in topology according to the following vocabulary:
large subset dense subset
small subset nowhere dense subset
thick subset subset with nonempty interior
extralarge subset subset with dense interior
piecewise large subset somewhere dense subset
pseudodiscrete subset discrete subset
Let G be an infinite group, X be a G-space, κ be an infinite cardinal
with κ ≤ |G|. A subset A ⊆ X is κ-large (resp. κ-small, κ-thick) if and
only if A is large (resp. small, thick) in the ballean Bκ(G,X).
Proposition 1.4. Let G be an infinite group, κ be an infinite cardinal
such that κ ≤ |G|, A ⊆ G. If A is pseudodiscrete in the ballean Bκ(G)
then A is κ-thin. If A is κ-thin and κ is regular then A is pseudodiscrete
in the ballean Bκ(G).
1.3. Cardinal invariants
Following the vocabulary, for every ballean B = (X,P,B), we intro-
duce some cardinal invariants, namely, density, crowdness, cellularity,
resolvability, coresolvability, extraresolvability and spread defined as
denB = min{|L|: L is a large subset of X},
crB = sup{κ : there exists α(κ) ∈ P such that |B(x, α(κ))| >
κ for every x ∈ X},
cellB = sup{|F|: F is a disjoint family of thick subsets of X},
resB = sup{|F| : F is a disjoint family of large subsets of X},
coresB = min{|F| : F is a partition of X into small subsets},
exresB = sup{|F| : F is a family of large subsets of X such that
F ∩ F ′ is small for all distinct F, F ′ ∈ F}.
spreadB = sup{|Y |B: Y is a pseudodiscrete subset of X}, where
|Y |B = min{|Y \ V | : V is a bounded subset of X}.
Theorem 1.3. For every ordinal ballean B = (X,P,B),
denB = cellB = spreadB.
Moreover, there exists a disjoint family F of thick subsets of X and a
subset Y of X such that cellB = |F| and |Y |β = |Y | = spreadB.
I. V. Protasov 227
Theorem 1.4. Let B = (X,P,B) be a ballean, |X| = κ and let |P | 6
κ. Then cellB = denB = κ and there exists a disjoint family F of
cardinality κ consisting of thick subsets of X provided that one of the
following conditions is satisfied
(i) there exists κ′ < κ such that B(x, α) 6 κ′ for all x ∈ X and α ∈ P ;
(ii) |B(x, α)| < κ for all x ∈ X, α ∈ P and κ is regular.
Theorem 1.5. For every ballean B,
crB 6 resB 6 crB · cf B.
Theorem 1.6. Let (X, d) be a metric space, B = B(X, d). Then resB =
crB and X can be partitioned in crB large subsets.
Theorem 1.7. Let B be a ballean such that crB < ℵ0. Then
crB = resB = exresB
Let B = (X,P,B) be a ballean. Given any α ∈ P and a cardinal κ,
we put
X(α, κ) = {x ∈ X : |B(x, α)| 6 κ}.
Theorem 1.8. Let (X, d) be an unbounded metric space, B = B(X, d).
Assume that crB = ℵ0 and, for every m ∈ N, there exists n ∈ N such
that X(m,n) is piecewise large. Then
resB = exresB = ℵ0.
In particular, resB = exresB = ℵ0 provided that for crB = ℵ0 and,
for every m ∈ N, there exists n ∈ N such that |B(x,m)| 6 n for every
x ∈ X. It follows that exresB(G) = ℵ0 for every countable group G.
Theorem 1.9. Let (X, d) be an unbounded countable metric space, B =
B(X, d). Assume that there exists n ∈ N such that X(n, k) is small for
each k ∈ N. Then exresB = 2ℵ0.
It follows from Theorems 1.7, 1.8 and 1.9 that, for a countable metric
space (X, d), exresB(X, d) could be either finite, or ℵ0, or 2ℵ0 . It is easy
to construct an example for each case.
The cardinal invariants density and crowdness are much more sim-
ple than others. For example, it is easy to see that denBκ(G) = |G|
and crBκ(G) = κ for every infinite group G and every κ. Thus, these
theorems allow us to calculate or evaluate more complicated cardinal
invariants cellularity, resolvability, coresolvability, extraresolvability and
spread. For coresolvability of group balleans, see Subsection 3.1.
228 Selective survey on Subset...
Comments. For balleans as the asymptotic counterparts of the uniform
topological spaces see [44]. A ballean with the support X can also be
defined in terms of the entourages of diagonal in X ×X. In this case, it
is called a coarse structure [48]. The proofs of results of this section can
be found in [44] and in the original papers [17, 35–37].
2. Amenability
We recall that a Banach measure µ : PG → [0, 1] is a function defined
on the family PG of all subsets of a group G such that
• µ(G) = 1;
• if A ∩B = ∅ then µ(A ∪B) = µ(A) + µ(B);
• µ(xA) = µ(A) for all x ∈ G, A ⊆ G.
A group G is called amenable if there exists a Banach measure on PG.
All results of this section were proved by means of the Folner criterion [20,
Theorem 3.61]: a group G is amenable if and only if, for every finite subset
H of G and every ε > 0, there exists a finite subset F of G such that
H ⊆ F and, for every x ∈ H,
|(xF \ F ) ∩ (F \ xF )|
|F | < ε.
Theorem 2.1. For a subset L of an amenable group G, the following
statements are equivalent:
(i) L is large;
(ii) µ(L) > 0 for every Banach measure µ on PG;
(iii) there exists ε > 0 such that µ(L) > ε for every Banach measure µ
on PG.
Theorem 2.2. A subset S of an amenable group G is small if and only
if µ(FS) < 1 for every Banach measure µ on PG and every finite subset
F of G.
Theorem 2.3. A subset T of an amenable group is thick if and only if
there exists a Banach measure µ on PG such that µ(T ) = 1.
A family I of subsets of a group G is called an ideal if, for any A,B ∈ I
and A′ ⊆ A, we have A ∪B ∈ I, A′ ∈ I. An ideal I is called translation
invariant if xA ∈ I for all x ∈ G, A ∈ I.
I. V. Protasov 229
Given a Banach measure µ on PG, we put
Nµ={A ∈ I : µ(A) = 0}, N = ∩{Nµ : µ is a Banach measure on PG}
Clearly, Nµ and N are translation invariant ideals. By Theorem 2.2, N
is contained in the ideal SG of all small subsets of G. A subset A ∈ N is
called an absolute null subset. Clearly, every P -small subset is an absolute
null subset.
Theorem 2.4. Let G be a countable amenable group, ε > 0. Then there
exists a small subset A ⊂ G such that µ(A) > 1 − ε for some Banach
measure µ on PG.
Theorem 2.5. Let G be an amenable group, I be a translation invariant
ideal in PG, I 6= PG. Then there exists a Banach measure µ on PG such
that I ⊆ Nµ.
Theorem 2.6. For every amenable group G, we have
SG = ∩{Nµ : SG ⊆ Nµ, µ is a Banach measure on PG}
Theorem 2.7. If a group G contains an isomorphic copy of the free
group F2 of rank 2, then G can be partitioned G = A1∪A2 such that A1,
A2 are large and P -small. In particular, there exists a P -small but not
small subset of G.
Question 2.1. Let G be a non-amenable group. Does there exist a
P -small not small subset of G?
Question 2.2 (T. Banakh). Give a combinatorial characterization of
the ideal N of absolute null subsets of an amenable group.
We say that a transitiveG-spaceX is amenable if there exists a finitely
additive measure µ : PG → [0, 1] such that µ(X) = 1 and µ(gA) = µ(A)
for all g ∈ G, A ⊆ X.
Question 2.3. Characterize the large, small and thick subsets of an
amenable G-space.
A function µ : P(G) → R+ is called subadditive if µ(A∪B) 6 µ(A)+
µ(B) for all A,B ∈ P(G). Let I be a (translation invariant) ideal in
P(G), I 6= P(G). Then there exists a (translation invariant) subadditive
function µ : P(G) → {0, 1} such that I = Nµ. Indeed, we put µ(A) = 0
if and only if A ∈ I.
230 Selective survey on Subset...
Given a subset A ⊆ G and a finite subset F ⊆ G, we put µF (A) =
|A∩FF | and
u(A) = inf
{
sup
g∈G
µF (gA) : F is finite and non-empty
}
.
By [51], the function u is subadditive for every amenable group G.
It is easy to verify (using the Folner criterion) that N ⊆ Nu for every
amenable group G.
Question 2.4. Is N = Nu for every amenable group G?
Comments. The results of this section from [2,24].
3. Ideals
3.1. κ-Small subsets and duality
Theorem 3.1. Let G be an infinite Abelian group, κ be a limit cardinal
such that κ 6 |G|. Then every Pκ-small subset of G is κ-small.
By Theorem 3.3, every P -small subset of an Abelian group G is small.
This statement does not hold for non-Abelian groups.
Example 3.1. Let F be a free group in an infinite alphabet A of car-
dinality κ, a ∈ A, Fa be the set of all group words whose first letter is
a. Since the subsets {xFa : x ∈ A \ {a}} are disjoint, Fa is κ-small. On
the other hand, F = Fa ∪ a−1Fa so Fa is large and Fa is not κ′-small for
every infinite cardinal κ′ 6 κ.
Question 3.1. Let G be an infinite Abelian group, κ be an infinite
cardinal such that κ 6 |G|. Is every Pκ-small subsets of G small? By
Theorem 3.1, this is so if κ is a limit ordinal.
Theorem 3.2. Let G be an infinite group, κ be an infinite cardinal such
that κ 6 |G|, A be a κ-thin subset of G. Then the following statements
hold
(i) if κ is regular then A is κ-small;
(ii) if κ′ is a cardinal such that κ < κ′ 6 G, then A is κ′-small;
(iii) if κ = ω then A is κ′-small for each κ′ such that ω 6 κ′ 6 |G|.
Theorem 3.3. In every infinite group G, there exist a subset A such
that A is κ-small for every κ, ω 6 κ 6 |G| but A is not P -small.
I. V. Protasov 231
If A is a Pκ-small subset of a group G then A is Pκ′-small for each κ′
such that ω 6 κ′ 6 κ. Surprisingly, this is not true for κ-small subsets.
For a group G and a cardinal κ, we denote by Sκ the ideal of all
κ-small subsets of G.
Theorem 3.4. Let G be an uncountable group, κ be a cardinal such that
ω < κ 6 |G|. Then the following statements hold
(i) if G is Abelian then Sω \ Sκ 6= ∅;
(ii) if κ = |G| and κ is regular then Sκ \ Sω 6= ∅.
Given a family F of subsets of a group G, we put
F⋆ = {X ⊂ G : X−1A 6= G for every A ∈ F}.
In [49], W. Seredin´ski asked if there exists in (ZFC) a family F of
subsets of R such that F⋆ = {countable subset of R}. In [50], Solecki
answered this question in the affirmative proving that, for every infinite
Abelian group G and every infinite cardinal κ with κ 6 |G|, there exists
a translation invariant ideal I in PG such that I⋆ = [G]<κ. This was
done as a byproduct of some very complicated construction.
Now we give much more elegant solution of the Seredinski problem
using the ideal Sκ.
Theorem 3.5. Let G be an infinite group of regular cardinality κ. Then
S⋆κ = [G]<κ.
Theorem 3.6. Let G be an infinite Abelian group and κ be a limit car-
dinal such that κ 6 |G|. Then S⋆κ = [G]<κ.
Theorem 3.7. Let G be an divisible Abelian group and κ be an infinite
cardinal such that κ 6 |G|. Then S⋆κ = [G]<κ.
Question 3.2. Is S⋆κ = [G]<κ for every infinite group G and every infinite
cardinal κ such that κ 6 |G|?
Theorem 3.8. For every infinite group G of regular cardinality κ, there
does not exist a family F of subsets of G such that Sκ = F⋆.
Comments. This section is selection from [39].
232 Selective survey on Subset...
3.2. Counting Ω-ideals
Let A be a universal algebra of signature Ω = ⋃n∈ω Ωn, Ωn is the set
of n-ary functions in Ω, PA be the Boolean algebra of all subsets of A, FA
be the family of all finite subsets of A. A non-empty family I of subsets
A is called an ideal in PA if, given any A,B ∈ I and A′ ⊆ A, one has
A ∪B ∈ I and A′ ∈ I.
We say that an ideal I in PA is an Ω-ideal, if FA ⊆ I and, for any
A ∈ I and f ∈ Ωn, we have f(An) ∈ I. Given a subset A ⊆ A, we denote
by I(A) the smallest by inclusion Ω-ideal in PA containing A, and say
that I(A) is the monogenic Ω-ideal generated by A.
Theorem 3.9. Let A be a countably infinite universal algebra of count-
able signature Ω. Then there exist 2ℵ0 monogenic Ω-ideals and 22ℵ0 Ω-
ideals in PA.
A proof of this statement is based on the following combinatorial
lemma.
Lemma 3.1. Let X,Y be infinite sets, Z be an infinite subsets of Y ,
n ∈ ω, f : Xn → Y be an arbitrary function. Given any V ∈ [X]ω and
Z ∈ [Y ]ω there exists an infinite subset U of V such that Z \ f(Un) is
infinite.
Let B = (X,P,B) be a ballean. Suppose that the support X of B has
a structure of an Ω-algebra. We say that B is an Ω-ballean if, for every
f ∈ Ωn, the mapping
Xn → X, (x1, . . . , xn) 7→ f(x1, . . . , xn)
is a ≺-mapping, where Xn is the support of the product of n copies of
B. Thus, an Ω-ballean is a counterpart of a topological Ω-algebra. If B
is a connected Ω-ballean, then the family I of all bounded subsets of X
is an Ω-ideal. In some cases, this ideal I uniquely determines B. For the
case of groups see [44, Chapter 6] and the next section.
Let Ω = {+, ·} and let an Ω-algebra X be a ring. For every Ω-ideal I
in PX , the ball structure B = (X,P,B), where P = {A ∈ I : 0 ∈ A} and
B(x,A) = x + A, is an Ω-ballean. Since FX ⊆ I, B is connected. Thus,
we get a bijective correspondence between the connected Ω-balleans on X
and the Ω-ideals in PX . Under this correspondence, our theorem states
that every countably infinite ring admits 22ℵ0 ballean structures which
respect with its algebraic structure. This is a counterpart of Theorem 1.3
from [14] stating that every countable ring admits 22ℵ0 Hausdorff ring
topologies.
Comments. This section is a summary of [40].
I. V. Protasov 233
3.3. Group ideals
We say that an ideal I in the Boolean algebra PG is a group ideal if
I contains the ideal of all finite subsets of G, and
A,B ∈ I ⇒ AB ∈ I, A−1 ∈ I.
Given a subset A of G, we denote by gp(A) the smallest group ideal in
PG containing A, and say that gp(A) is monogenic group ideal generated
by A.
We have at least two motivation to study group balleans. On one
hand, every group ideal in PG determines a ball structure on G which re-
spect with the algebraic structure of G (see [44, Chapter 6]). On the other
hand, every group ideal induces a closed two-side ideal in the semigroup
βG (see Section 3.4).
Theorem 3.10. For every countable group G, there exists 2ℵ0 monogenic
group ideals and 22ℵ0 group ideals in PG.
Theorem 3.11. Let G be an infinite Abelian group of cardinality κ.
Then there exists 2κ monogenic group ideals and 22κ group ideals in PG.
We say that a subset A of a group G is non-generative if, for any
n ∈ ω and F ∈ FG, G 6= X(F,A, n), where
X(F,A, n) = (FA)±1 . . . (FA)±1︸ ︷︷ ︸
n
.
Clearly, A is non-generative if and only if gp(A) 6= PG. If I is a group
ideal and I 6= PG then every subset A ∈ I is non-generative.
Following [42], we say that a sequence (an)n∈ω of elements of a group
G is a T-sequence if there exists a Hausdorff group topology on G in
which (an)n∈ω converges to the identity e of G.
Theorem 3.12. For every infinite group G, the following statements
hold
(i) if (an)n∈ω is an injective T-sequence then the subset {an : n ∈ ω}
is non-generative;
(ii) there exists an injective sequence (bn)n∈ω such that the subset {bn :
n ∈ ω} is non-generative but (bn)n∈ω is a not a T -sequence.
Corollary 3.1. Let (an)n∈ω be an injective sequence in Z such that either
limn→∞ an+1an = ∞ or limn→∞
an+1
an = r and r is transcendental. Then
the subset {an : n ∈ ω} is non-generative in Z.
234 Selective survey on Subset...
By [42, Theorems 2.2.4 and 2.2.6], for every algebraic number r > 1,
there exist two injective sequences of positive integers such that
lim
n→∞
an+1
an
= lim
n→∞
bn+1
bn
= r
and (an)n∈ω is a T -sequence in Z but (bn)n∈ω is not a T -sequence. By
Theorem 3.12 the subset {an : n ∈ ω} is non-generative. We do not
know whether, for every algebraic number r > 1, there is an injective
sequence (an)n∈ω of integers such that limn→∞ an+1an = r and the subset
{an : n ∈ ω} is generative.
For a group G, we denote by NG the minimal ideal in PG containing
all non-generative subsets of G. Thus, NG is the family of all finite unions
of non-generative subsets.
Question 3.3. Given a group G and n ∈ N, how to detect whether given
subset A of G is a union on n non-generative subsets.
Theorem 3.13. For every countable group G, NG is not a group ideal.
We recall that partially ordered set (L,6) is a lattice if any two el-
ements a, b ∈ L have the exact lower bound (denoted by a ∧ b) and the
exact upper bound (denoted by a∨b). A lattice L is called complete if any
subset S of L has the exact lower bound (denoted by ∧S) and the exact
upper bound (denoted by ∨S). In this case, by minL and maxL we
denote ∧L and ∨L. An element a ∈ L is called an atom (resp. coatom)
if the interval (minL, a) (resp. (a,maxL)) is empty.
A lattice L is called modular if (a∨b)∧c 6 a∨ (b∧c) for all a, b, c ∈ L
such that a 6 c.
For a group G, we denote by LG the set of all group ideals in PG
partially ordered by inclusion. Given any subset S ⊂ LG,
⋂
S is the
exact lower bound of S and
⋂
{I : I is a group ideal, I ′ ⊆ I for every I ′ ∈ S}
is the exact upper bound of S, so LG is a complete lattice with minLG =
FG and maxLG = PG. It is easy to show that LG is modular for every
Abelian group G.
Example 3.2. Let L be a free group with the free generators a, b. To
show that the lattice LF is not modular, we put
A = {an : n ∈ Z}, B = {bn : n ∈ Z}, C = {an, bnanbn : n ∈ Z},
and I1 = gp(A), I2 = gp(B), I3 = gp(G). Then I1 ⊆ I3 and
(I1 ∨ I2) ∧ I3 = I3, I1 ∨ (I2 ∧ I3) = I1,
but I1 6= I3.
I. V. Protasov 235
Theorem 3.14. If an infinite group G is either countable or Abelian
then LG has no atoms.
In contrast to Theorem 3.14, by the Zorn Lemma, every group ideal
I ∈ LG, I 6= PG is contained in some coatom of LG.
Theorem 3.15. Let G be a countable group, C be a set of all coatoms
in LG. Then ∧C = FG, ∨C = PG.
Theorem 3.16. For every countable group G, there exists a sublattice
R of LG isomorphic to the lattice (R,6).
Comments. All results of this section from [16]. For vector ideals see
[25].
3.4. Applications to βG
Let X be a discrete space, βX be the Stone-Cˇech compactification of
X, X∗ = βX \ X. We take the points of βX to be the ultrafilters on
X identifying X with the principal ultrafilters. For every subset A ⊆ X,
we put A = {q ∈ βX : A ∈ q}. The topology of βX can be defined by
stating that the family {A : A ⊆ X} is a base for the open sets. For
every filter ϕ on X, the subset ϕ = ⋂{A : A ∈ ϕ} is closed in βX, and
for every non-empty closed subset δ ⊆ βX, there exists a filter ϕ on X
such that δ = ϕ. To our purposes, it is more convenient to determine the
closed subsets of βX by means of the ideals in the Boolean algebra PX
of all subsets of X.
Given a ideal I in PX and a closed subset δ ⊆ βX, we put
Iˆ = {q ∈ βX : X \A ∈ q for every A ∈ I}, δˇ = {A ⊆ X : δ ⊆ X \A}.
Thenˆis a bijection between the set of all ideals in PX and the set of all
non-empty closed subsets of βX, andˇis its inverse mapping.
The universal property of βX says that every mapping f : X → Y ,
where Y is a compact Hausdorff space, can be extended to the continuous
mapping fβ : βX → Y .
We note (see [41, Corollary 3.6]) that, for every infinite discrete space
X of cardinality κ, |βX| = 22κ .
Now let G be a discrete group with identity e. Using the universal
property of the space βG, we extend the group multiplication from G to
βG in two steps. Given g ∈ G, the mapping
x 7→ gx : G → βG
236 Selective survey on Subset...
extends to the continuous mapping
q 7→ gq : βG → βG.
Then, for each q ∈ βG, we extend the mapping g 7→ gq, defined from G
into βG, to the continuous mapping
p 7→ pq : βG → βG.
The product pq of ultrafilters p, q can also be defined by the rule:
given a subset A ⊆ G,
A ∈ pq ⇔ {g ∈ G : g−1A ∈ q} ∈ p.
Let P ∈ p and Qx, x ∈ P . Then
⋃{xQx : x ∈ P} is a neighbourhood
of pq in βG, and the family of all subsets of this form is a base of the
neighbourhoods of pq. It is easy to verify that the binary operation
(p, q) 7→ pg is associative, so βG is a semigroup, and G∗ is a subsemigroup
of βG. It follows from the second step of the extension that, for every
q ∈ βG, the mapping p 7→ pq is continuous, so the semigroup βG is right
topological. For the structure of compact right topological semigroup
βG and its combinatorial applications see [22, 41]. For application of
βG to topologies on groups see [45] and [I. V. Protasov. Algebra in
the Stone-Cˇech compactification: applications to topologies on groups,
Algebra Discrete Math, No 1, 2009, 83–110].
An ideal I in PG is called left invariant if gA ∈ I for all g ∈ G, A ∈ I.
We note thatˆis a bijection between the set of all left invariant ideals
in PG and the set of closed left ideals in βG.
Let G be an infinite group, SG be the ideal of all small subset of G,
µG the minimal closed (two-side) ideal of βG, so
µG =
⋂
{µ : µ is a closed ideal of βG}.
Theorem 3.17. For every infinite group G, we have SˆG = µG.
Theorem 3.18. Let I be a group ideal in PG. Then Iˆ is an ideal in the
semigroup βG.
For an infinite group G, we consider the ideal NG of all finite union
of non-generative subsets of G, and put
νG =
⋂
{Iˆ : I is a group ideal in PG}.
By Theorem 3.18, νG is an ideal. If G is countable, by Theorem 3.13,
νˆG is not a group ideal.
I. V. Protasov 237
Theorem 3.19. For every infinite group G, we have N̂G = νG.
Let G be an amenable group, ZG be the ideal of all absolute zero-
subsets of G. Then NG ⊆ ZG ⊆ SG. If G is countable then SG \ZG 6= ∅.
It follows that νG 6= µG.
Question 3.4. Is νG 6= µG for every (countable) group G?
For any infinite group G, the subset G∗G∗ and G∗G∗ are ideals of the
semigroup βG. We say that an ultrafilter p ∈ G∗ is prime if p /∈ G∗G∗,
and strongly prime if p /∈ G∗G∗
We do not know a characterization of prime ultrafilter through its
members. To give a characterization of strongly prime ultrafilters, we
say that a subset P ⊆ G is sparse if, for any infinite subset R of G, there
exists a finite non-empty subset F ⊆ R such that ⋂x∈F xP is finite.
Theorem 3.20. An ultrafilter p ∈ G∗ is strongly prime if and only if
there exists a sparse subset P ∈ p.
Question 3.5. Let G be an infinite amenable group, p ∈ G∗ be a prime
ultrafilter. Does there exists an absolute zero-subset P ∈ p?
Comments. All results of this section from [16].
3.5. Ideals generated by thin subsets
Let G be an infinite group, κ be an infinite cardinal such that κ 6 |G|,
Tκ be a family of all κ-thin subsets of G. Then the smallest ideal T ∗κ in
the Boolean algebra PG is the family of all finite unions of κ-thin subsets.
Thus, to characterize T ∗κ , we need some test which, for given A ⊆ G and
m ∈ N, detect whether A can be represented as a union of 6 m thin
subsets. We consider this question in the ballean context, taking in mind
that, by Proposition 1.4, for every a regular cardinal κ, a subset A ⊆ G
is κ-thin if and only if A is pseudodiscrete in the ballean Bκ(G).
For a ballean B = (X,P,B), we use the following notation:
T (B) is the family of all pseudodiscrete subsets of X;
⋃
m T (B) is the family of all unions of 6 m pseudodiscrete subsets
of X;
T ∗(B) is the ideal generated by T (B).
Clearly, T ∗(B) = ⋃m∈N(
⋃
m T (B)). We use also the notation Tm(B)
for a family of subsets of X putting A ∈ Tm(B) if and only if, for every
α ∈ P , there exists a bounded subset Yα of X such that |B(x, α)∩A| 6 m
for every x ∈ A \ Yα.
238 Selective survey on Subset...
Theorem 3.21. For every ballean B, we have ⋃m T (B) ⊆ Tm(B).
The following theorem gives a characterization of T ∗(B) in the case
of an ordinal ballean.
Theorem 3.22. For every ordinal ballean B and m ∈ N, we have Tm(B)
= ⋃m T (B).
Theorem 3.23. Let G be an infinite group of regular cardinality κ, m ∈
N. A subset A ⊆ G can be partitioned in 6 m κ-thin subsets if and only
if, for every subset F ∈ [G]<κ, there exists a subset Y ∈ [G]<κ such that
|A ∩ Fx| 6 m for every x ∈ A \ Y .
Comments. This section is a summary of [26].
4. Partitions
4.1. Filtrations
Let G be an infinite group with the identity e. A filtration of G is a
family {Gα : α < |G|} of subgroups of G such that
(i) G0 = {e} and G =
⋃{Gα : α < |G|};
(ii) Gα ⊂ Gβ for all α < β < |G|;
(iii) ⋃{Gα : α < β} = Gβ for every limit ordinal β;
(iv) |Gα| < |G| for every α < |G|.
We note that every uncountable group admits a filtration {Gα : α <
|G|} such that |Gα| = |α| for every infinite ordinal α < |G|, were |α| =
|{β : β < α}|.
For each α < |G|, we decompose Gα+1 \ Gα in right cosets by Gα
and fix some system Xα of representatives so Gα+1 \Gα = GαXα. Take
an arbitrary element g ∈ G \ {e} and choose the smallest subgroup Gα
with g ∈ Gα. By (iii), α = α1 + 1 for some ordinal α1 < |G|. Hence,
g ∈ Gα1+1\Gα1 and there exist g1 ∈ Gα1 , xα1 ∈ Xα1 such that g = g1xα1 .
If g1 6= e, we choose the ordinal α2 and the elements g2 ∈ Gα2+1 \ Gα2
and xα2 ∈ Xα2 such that g1 = g2xα1 . Since the set of ordinals < |G| is
well-ordered, after finite number s(g) of steps, we get the representation
g = xαs(g)xαs(g)−1 . . . xα2xα1 , xαi ∈ Xαi .
We note that this representation is unique and put
γ1(g) = α1, γ2(g) = α2, . . . , γs(g)(g) = αs(g),
I. V. Protasov 239
Γ(g) = {γ1(g), . . . , γs(g)(g)}
and, for every natural number n, put
Dn = {g ∈ G : s(g) = n},
so G = ⋃n∈ω Dn, where D0 = {e}.
Theorem 4.1. Every infinite group G can be partitioned in ℵ0 subsets
which are κ-small for every cardinal κ such that ω 6 κ 6 cf |G|.
Proof. If G is countable, the statement is trivial because every singleton
is κ-small. We suppose that G in uncountable, use above filtration {Gα :
α < |G|} of G and note G \ {e} = ⋃∞n=1 Dn. We fix a natural number
n and show that Dn is κ-small. Take an arbitrary F ∈ [G]<κ. Since
κ 6 cf |G|, there exists β < |G| such that F ⊆ Gβ so FDn ⊆ GβDn. Now
it suffices to prove that G \ GβDn is ω-large. We choose the elements
a1, a2, . . . , an+1 in G such that
a1 ∈ Gβ+1 \Gβ , a2 ∈ Gβ+2 \Gβ+1, . . . , an+1 ∈ Gβ+n+1 \Gβ+n.
We take an arbitrary element g ∈ GβDn and put g = g0. If β+n ∈ Γ(g),
we put ǫ0 = 0, otherwise ǫ0 = 1. Note that β + n ∈ Γ(aǫ0n+1g0) and put
g1 = aǫ0n+1g0. If β +n− 1 ∈ Γ(g1), we put ǫ1 = 0, otherwise ǫ1 = 1. Note
that {β + n− 1, β + n} ∈ Γ(aǫ1n g1) and put g2 = aǫ1n g1. After n+ 1 steps
we get
{β, β + 1, . . . , β + n} ⊆ Γ(aǫn1 a
ǫn−1
2 . . . aǫ0n+1g).
If follows that aǫn1 a
ǫn−1
2 . . . aǫ0n+1g /∈ GβDn and put A = {e, a1, a2, . . . ,
an+1}, K = An. We have shown that GβDn ⊆ K−1(G \GβDn). Hence,
G ⊆ K−1(G \GβDn). This shows that G \GβDn is ω-large.
Theorem 4.2. Let G be an infinite group, κ be an infinite cardinal such
that κ 6 |G|. Then G can be partitioned in κ κ-large subsets.
Proof. For κ = ℵ0, this is Theorem 3.12 from [43]. For κ > ℵ0, we choose
a filtration {Gα : α < |G|} such that |Gα| = |α| for every infinite ordinal
α < |G|. For each α < κ, we put
Lα = {g ∈ G : γs(g) = α}.
Then Gα+1Lα = G so Lα is κ-large. Since the subsets {Lα < κ} are
pairwise disjoint, to get a desired partition of G, we join G \⋃α<κ Lα to
some subset Lα.
240 Selective survey on Subset...
Theorem 4.3. Let G be an infinite group, κ be an infinite cardinal such
that either κ < |G| or κ = |G| and κ is regular. Then G can be partitioned
in |G| κ-thick subsets.
Proof. This is a partial case of Theorem 1.4. Here we use a filtration
{Gα : α < |G|} to point out directly a desired partition in the case
κ < cf |G|, |G| > ℵ0. We partition the cardinal |G| in |G| subsets of
cardinality |G|: G = ⋃λ<|G| Iλ. We put TI =
⋃
λ∈I(Gλ+1 \Gλ) and show
that TI is κ-thick. Let X be a subset of G such that |X| < κ. Since
κ 6 cf |G| and I is cofinal in |G|, there exists λ ∈ I such that X ⊂ Gα.
We take an arbitrary g ∈ Gλ+1 \Gλ. Then Gλg ∈ TI so Xg ⊆ TI .
Question 4.1. Can every infinite group G be partitioned in ℵ0 subsets
which are κ-small for every infinite cardinal κ 6 |G|? By the Theorem
4.1, this is so if |G| is regular.
Question 4.2. Can every infinite group G be partitioned in G |G|-thick
subsets? By the Theorem 4.3 this is so if |G| is regular.
In the following question, we formalize a problem of partitions of
group into thin subsets.
(κ, µ)-Question. Let G be an infinite group, κ, µ be infinite cardinals
such that κ 6 |G|, µ < |G|. How to detect whether G can be partitioned
in 6 µ κ-thin subsets?
The following two theorems essentially clarify this question.
Theorem 4.4. Let G be an infinite group, κ, µ be infinite cardinals such
that κ 6 |G| and µ+ < |G|. If either κ < |G| or κ = |G| and κ is regular
then G cannot be partitioned in 6 µ κ-thin subsets.
Theorem 4.5. Let µ be an infinite cardinal, G be a subgroup of a direct
product
⊗
α<µ+ Gα of groups {Gα : α < µ+} of cardinality 6 µ. Then G
can be partitioned in 6 µ thin subsets.
The proofs of Theorem 4.4 and 4.5 are based on the following combi-
natorial lemmas.
Lemma 4.1. Let µ be an infinite cardinal, X be a set such that cf |X| >
µ+, χ : [X]2 → µ be an arbitrary mapping. Then there exist λ ∈ µ,
distinct elements x, y ∈ X and a subset Z of X such that x /∈ Z, y /∈ Z,
|Z| = |X| and χ({x, z}) = χ({y, z}) = λ for every z ∈ Z.
I. V. Protasov 241
Lemma 4.2. For any infinite cardinal µ and m ∈ N, there exists a
mapping χ : [µ+]m → µ with the following property. For any λ ∈ µ,
l ∈ N, l < m and any disjoint subsets A,B ∈ [µ+]l, we have
|{C ∈ [µ+]m−l : (A ∪B) ∩ C = ∅, χ(A ∪ C) = χ(B ∪ C) = λ}| 6 1.
It is well known that every Abelian group can be embedded in a direct
product of countable groups. Thus, Theorem 4.4 and Theorem 4.5 answer
the (κ, µ)-Question for every Abelian group G and all cardinals κ, µ with
exception κ = |G|, κ is singular and µ < cfκ. If µ+ < |G| and either
κ < |G| or κ = |G| and κ is regular, we apply Theorem 4.4. If µ+ > |G|,
we use Theorem 4.5. If κ = |G|, κ is singular and µ > cfκ, we partition
G in cfκ subsets of cardinality < κ and note that each subset of this
partition is |G|-thin. The exceptional case remains open.
Question 4.3. Let G be a group of singular cardinality κ, µ be an
infinite cardinal such that µ < cfκ. Can G be partitioned in µ κ-thin
subsets?
For a natural number k, it is more convenient to call a subset A of a
group G to be k-thin if |gA ∩A| 6 k for every g ∈ G, g 6= e.
Question 4.4. Can R be partitioned in ℵ0 subsets such that each subset
of the partition is k-thin for some k ∈ N? Does there exist k ∈ N such
that R can be partitioned in ℵ0 k-thin subset? Can R be partitioned in
ℵ0 subsets linearly independent over Q (each such subset is 1-thin)?
By Theorem 4.4, under ¬CH the answers to all subquestions of Ques-
tion 4.4 are negative. In contrast to Theorem 4.5, stating that under CH
R can be partitioned in ℵ0 thin subsets, we expect the negative answer
to Question 4.4 with no additional to ZFC set-theoretical assumptions.
We conclude this section with two propositions showing that above
results (concerning partitions of groups) fail to be true for partitions of
G-spaces.
A permutation f of a set X is called finitary if there exists a finite
subset F of X such that f(x) = x for all x ∈ X \F . A space X endowed
with the action of the group G of all finitary permutations of X is called
a finitary G-space.
A set X endowed with the action of the group of all permitations of
X is called a universal G-space.
Proposition 4.1. Let X be an infinite finitary G-space, A ⊆ X. Then
the following statements hold
(i) A is large if and only if G \A is finite;
242 Selective survey on Subset...
(ii) A is small if and only if A is finite;
(iii) A is thick if and only if A is infinite;
(iv) A is thin if and only if A is finite.
Proposition 4.2. Let X be an infinite universal G-space, A ⊆ X. Then
the following statements hold
(i) A is large if and only if |A| = |X|;
(ii) A is small if and only if |A| < |X|;
(iii) A is thick if and only if |G \A| < |X|;
(iv) A is thin if and only if A is finite.
Comments. For usage of filtration in Homological Algebra and Theory
of Abelian group see [15]. Some applications of filtrations to Topological
Algebra can be find in [45] (one of them: every non-meager left topological
group can be partitioned in ℵ0 dense subsets). Theorem 4.1 from [39],
Theorem 4.2 from [35], Theorems 4.4 and 4.5 are new. For applications
of Theorem 4.3 to topologies on group see [36], some generalization of
Theorem 4.3 to semigroups are in [10].
4.2. Partitions of groups in two subsets
Given any finite partition of an infinite group, what can we say about
the cells of the partition? This is the main question in the Ramsey Group
Theory (see [22, Chapters 5,14,16,18]). Most results of this theory state
that at least one cell of partition has rich algebraic structure or is “large”
by the combinatorial size, so following Taras Banakh, we may say that a
full chaos is impossible.
By [43, Theorem 12.7], for every finite partition of a group G = A1 ∪
· · · ∪ An, there exist i ∈ {1, . . . , n} and a finite subset K of G such that
G = KAiA−1i . It is still unknown whether we can choose K such that
|K| 6 n [43, Question 12.1]. This is so if either G is amenable [43,
Theorem 12.8] or n = 2.
Theorem 4.6. For a group G, the following statements are equivalent
(i) G is a torsion group with no elements of order 2;
(ii) for any partition G = A ∪B, either G = AA−1 or G = BB−1.
Theorem 4.7. Let Z = Z1 ∪ Z2 be a partition such that Z 6= Zi − Zi,
i ∈ {1, 2}. Then the following statements hold
I. V. Protasov 243
(i) there exists k ∈ N such that Zi − Zi + kZ = Zi − Zi, i ∈ {1, 2};
(ii) either 2Z = Zi − Zi, i ∈ {1, 2} or there exists a > 1 such that
Z \ aZ ⊆ Zi − Zi and {−a+ 1, . . . , a− 1} ⊆ Zi − Zi, i ∈ {1, 2}.
For every k ∈ N, Z can be partitioned Z = Z1 ∪ Z2 such that (k +
2kZ) ∩ (Zi − Zi) = ∅, i ∈ {1, 2}.
It would be interesting to extend Theorem 4.7 to the groups Zn, n ∈
N.
By van der Waerden theorem (see [19]), for every finite partition of
Z, one cell of the partition contains an arbitrarily long finite arithmetic
progression.
Theorem 4.8. For every 2-coloring of N, there are infinitely many
monochrome 3-term arithmetic progressions with common first term.
Theorem 4.9. There exists a 3-coloring of N such that every set of
monochrome 3-term arithmetic progressions with common first term is
finite.
Theorem 4.10. There exists a 2-coloring of N such that every set of
monochrome 4-term arithmetic progressions with common first term is
finite.
For a subset A of N, we put
PS(A) = {a+ b : a, b ∈ A, a 6= b},
FS(A) = {a1 + · · ·+ an : n ∈ N, a1, . . . , an ∈ A,
ai 6= aj for all i < j 6 n},
and note that A+A = PS(A) + 2A.
Let N = A1 ∪ . . .∪An be an arbitrary partition. We define a coloring
χ : [N 2] → {1, . . . , n} by the rule: χ({a, b}) = i if and only if a+ b ∈ Ai.
By the Ramsey theorem (see [19, Chapter 2]), there exist an infinite
subset A of N and i ∈ {1, . . . , n} such that χ({a, b}) = i for all distinct
a, b ∈ A. It means that PS(A) ⊆ Ai. Much more delicate statements
follow from the Hindman theorem (see [22, Chapter 5]): there exist i ∈
{1, . . . , n} and an infinite subset A ⊆ N such that FS(A) ⊆ Ai.
One of the most intriguing open question in Combinatorics of Num-
bers, the Owings problem (see Amer. Math. Monthly, 81 (1974), 902)
is: Given any partition N = A1 + A2, do there exist i ∈ {1, 2} and in-
finite subset A of N such that A + A * Ai? Equivalently, does there
exist an increasing sequence of even naturals (ai)i∈ω such that the set
{ai+aj2 : i, j ∈ ω} is monochrome?
244 Selective survey on Subset...
Theorem 4.11. For every 2-coloring of N, there exists an increasing
sequence of even numbers a1, a2, . . . such that the sequence
a1,
a1 + a2
2 , a2,
a2 + a3
2 , a3, . . . , an,
an + an+1
2 , an+1, . . .
is monochrome.
Comments. Theorem 4.6 from [18], Theorem 4.7 is new, all other the-
orems from [53].
5. Packings
5.1. Packing numbers
For a subset A of a group G, we put
pack(A) = sup{|S| : S ⊆ G is such that
the family {gA : g ∈ S} is disjoint}.
Answering a question from [13], T. Banakh and N. Lyaskovska con-
structed, in any infinite group G, a subset A such that pack(A) = ℵ0
but A is not P -small, so the supremum in the definition of pack(A) is
not accessible. In this connection, they introduced the following packing
number
Pack(A) = min{κ : ∀S ⊆ G, |S| = κ,
the family {gA : g ∈ S} is not disjoint}.
If the supremum in the definition of pack(A) is accessible, then Pack(A)
= (pack(A))+, otherwise Pack(A) = pack(A).
Theorem 5.1. An infinite Abelian group G contains a subset A ⊆ G
with Pack(A) = κ if and only if one of the following conditions holds
(i) 2 6 κ 6 |G|+ and κ /∈ {3, 4};
(ii) κ = 3 and G is not isomorphic to ⊕i∈I Z3;
(iii) κ = 4 and G is not isomorphic to ⊕i∈I Z2 or to Z4 ⊕
(⊕
i∈I Z2
)
.
Theorem 5.2. An infinite Abelian group G contains a subset A with
pack(A) = κ if and only if one of the following conditions holds
(i) 1 6 κ 6 |G| and κ /∈ {2, 3};
I. V. Protasov 245
(ii) κ = 2 and G is not isomorphic to ⊕i∈I Z3;
(iii) κ = 3 and G is not isomorphic to ⊕i∈I Z2 or to Z4 ⊕
(⊕
i∈I Z2
)
.
Given a translation invariant ideal I in PG and a subset A ⊆ G, we
define the relative packing numbers
I-pack(A) = sup{|B| : B ⊆ G is such that
{bA : b ∈ B} is disjoint modulo I},
I-Pack(A) = sup{|B|+ : B ⊆ G is such that
{bA : b ∈ B} is not disjoint modulo I}.
A family F of subsets of G is called disjoint modulo I if F ∩H ∈ I
for all distinct H,F ∈ I. It is clear that {∅}-pack(A) = pack(A), {∅}-
pack(A) = Pack(A), I-pack(A) 6 I-Pack(A) and
I-pack(A) = sup{κ : κ < I-PackA},
so the value of I-pack(A) can be recovered from that of I-Pack(A).
Theorem 5.3. Let G be an infinite group of cardinality κ, A be a subset
of G such that [G]<ω-Pack(A) = κ+. Then A can be partitioned A =
A1 ∪A2 such that Pack(Ai) 6 (cfk)+, i ∈ {1, 2}.
Theorem 5.4. Let G be an infinite Abelian group, κ be a cardinal. Then
the following statements are equivalent
(i) there exists a subset A ⊆ G such that [G]<ω-Pack(A) = κ;
(ii) there exists a subset A ⊆ G such that Pack(A) = κ.
In fact, the packing numbers I-pack(A) and I-Pack(A) are the partial
cases of the packing numbers I-packn(A) and I-Packn(A) defined for
every natural number n > 2 by the formulas:
I-packn(A) = sup
{
|B| : B ⊆ G is such that
{ ⋂
c∈C
cA : C ∈ [B]n
}
∈ I
}
,
I-Packn(A) = sup
{
|B|+ : B ⊆ G is such that
{ ⋂
c∈C
cA : C ∈ [B]n
}
∈ I
}
.
246 Selective survey on Subset...
It is clear that I-pack(A)=I-pack2(A) and I-Pack(A)=I-Pack2(A).
Also, I-packn(A) 6 I-packn+1(A) and I-Packn(A) 6 I-Packn+1(A) for
every n > 2.
If I = {∅}, then we shall write packn(A) and Packn(A) instead of
{∅}-packn(A) and {∅}-Packn(A).
5.2. Packing-complete ideals
It is clear that, for each subset A ∈ I and n > 2, we get I-packn(A) =
|G| and I-Packn(A) = |G|+. We shall be interested in ideals for which
the (partial) converse implications hold.
A translation invariant ideal I in PG is called Packn-complete (resp.
packn-complete) if I contains each subset A ⊆ G with I-Packn(A) >
ℵ0 (resp. I-packn(A) > ℵ0). Clearly, each Packn+1-complete ideal is
Packn(A)-complete.
A translation invariant ideal I in PG is called Pack<ω-complete if I
is Packn-complete for each n > 2.
Theorem 5.5. For every amenable group G, the following ideals are
Pack<ω-complete:
(i) Nµ = {A ⊆ G : µ(A) = 0}, µ is a Banach measure on PG;
(ii) N = ⋂{Nµ : µ is a Banach measure on PG};
(iii) the ideal SG of all small subsets of G.
For a translation invariant ideal I of PG and n > 2, we put
Packn(I) =
⋂
{J : I ⊂ J ,J is Packn-complete},
Pack<ω(I) =
⋂
{J : I ⊂ J ,J is Pack<ω-complete},
and say that Packn(I) and Pack<ω(I) are the Packn-completion and
Pack<ω-completion of I.
Proposition 5.1. The Packn-completion of I is equal to the union
I<ω1 =
⋃
α<ω1
Iα,
where I0 = I and Iα is the smallest ideal in PG containing all subsets
A ⊆ G with infinite Iβ-Packn(A) for some β < α.
I. V. Protasov 247
Proposition 5.2. The Pack<ω-completion of I is equal to the union
I<ω1 =
⋃
α<ω1
Iα,
where I0 = I and Iα is the smallest ideal in PG containing all subsets
A ⊆ G with infinite Iβ-Packn(A) for some β < α and n < ω.
Question 5.1. Are the ideals Packn({∅}), n > 2 in PZ pairwise dis-
tinct? Do they differ from Pack<ω({∅})?
Question 5.2. Characterize the smallest ideal in PZ containing all P -
small subsets.
5.3. Packing in topological group
For a topological group G, it is naturally to ask about the possible
values of the packing numbers of subsets with good topological or de-
scriptive properties. The authors of [3] addressed this general question
to K. Omiljanowski.
We recall that a Polish group is a metrizable, separable and complete
topological group.
Theorem 5.6. If A is a σ-compact subset of a Polish group G, then
pack(A) ∈ N ∪ {ℵ0, 2ℵ0}. Moreover, if A is compact, then
(i) pack(A) = 2ℵ0 if G is not locally compact;
(ii) pack(A) ∈ {ℵ0, 2ℵ0} if G is locally compact but not compact;
(iii) pack(A) ∈ N ∪ {2ℵ0} if G is compact.
Question 5.3. Is there a compact group G and a σ-compact subset A
of G with pack(A) = ℵ0?
Question 5.4. Is there a Polish group G and a Borel subset A ⊂ G with
ℵ0 < pack(A) < 2ℵ0?
For the possible values of the packing numbers of the Borel and ana-
lytic subsets of a Polish group see [3, Section 3].
Theorem 5.7. Every non-discrete Polish Abelian group G contains two
closed subsets A,B such that pack(A) = pack(B) = 2ℵ0 and |g(A∪B)∩
(A ∪B)| = |A ∪B| for every g ∈ G.
We recall that a subset A of a topological group G is Haar null if
there is a Borel probability measure µ on G such that µ(xAy) = 0 for all
x, y ∈ G.
248 Selective survey on Subset...
Theorem 5.8. Every non-discrete Polish Abelian group G contains a
closed nowhere dense Haar null subset C such that G = CC−1 and |gC∩
C| = |C| for every g ∈ G.
Comments. This section with open questions is a poppuree from the
papers [1–3,27]. Theorem 5.3 is a generalization of Theorem 3.5 from [24].
6. Around thin subsets
Let G be a group with the identity e, X be a G-space, k ∈ N. A
subset A of X is said to be
• k-thin if |gA ∩A| 6 k for each g ∈ G, g 6= e;
• almost thin if the set ∆(A) is finite, where ∆(A) = {g ∈ A : gA∩A}
is infinite;
• sparse if, for every infinite subset S of G, there exists a non-empty
finite subset F ⊂ S such that ⋂g∈F gA is finite;
• k-sparse if, for every infinite subset S of G, there exists a finite
subset F ⊂ S such that |F | 6 k and ⋂g∈F gA is finite.
6.1. Sparse subsets
For motivation to study the sparse subsets see Theorem 3.21. We say
that a subset A of G is finitely sparse if A is k-sparse for some k ∈ N. The
following theorem shows that the family of all sparse subsets of X and the
family of all finitely sparse subsets form the ideals in the Boolean algebra
PX . The key part in the proof of Theorem 6.1 (ii) plays the following
observation: a subset A of a group G is k-sparse if and only if, for every
infinite subset S of G, there exists an infinite subset S′ ⊆ S such that,
for each F ∈ [S′]k, the subset ⋂g∈F gA is finite.
Theorem 6.1. Let X be a G-space, k,m ∈ N, A and B be subsets of X.
Then
(i) if A,B are sparse then A ∪B is sparse;
(ii) if A is k-sparse and B is m-sparse then A∪B is (k+m−1)-sparse.
The following two theorems clarify the relationships between k-sparse
and sparse subsets of groups.
Theorem 6.2. For every infinite group G and every k ∈ N, there exists
(k + 1)-sparse but not k-sparse subset of G.
I. V. Protasov 249
Theorem 6.3. For every infinite group G, there exists a sparse subset
which is not k-sparse for every k ∈ N.
The relationships between sparse, small and P -small subsets are re-
flected in the following theorems.
Theorem 6.4. Every sparse subset A of an infinite group G is small. If
G is amenable then A is an absolute zero-subset.
Theorem 6.5. For every infinite group G, there exists a sparse subset
which is not P -small.
Theorem 6.6. For every infinite group G, there exists a small and P-
small subset A which is not sparse.
In construction of the subset A from Theorem 6.5, we used the fol-
lowing claim: if A is a subset of G such that AA−1 is not large then A is
small and P-small.
6.2. Thin, almost thin and 2-sparse subsets
Theorem 6.7. For every infinite group G, there exists a thin subset
which is not k-thin for each k ∈ N.
Theorem 6.8. For every infinite finitely generated Abelian group G,
there exists a thin subset A such that whenever A is finitely partitioned
A = A1 ∪ · · · ∪An, there exist j ∈ {1, . . . ,m} and a finite subset K of G
such that
G = K + (Aj −Aj +Aj −Aj).
In particular, Aj generates a subgroup of finite index.
More on thin generating subsets of a group can be find in the subsec-
tion 6.3.
Theorem 6.9. Every almost thin subset A of a group G can be parti-
tioned in 3|∆(A)|−1 thin subsets. If G has no elements of odd order then
A can be partitioned in 2|∆(A)|−1 thin subsets.
Theorem 6.10. A subset A of a group G is 2-sparse if and only if
X−1X * ∆(A) for every infinite subset X of G. In particular, every
almost thin subset of G is 2-sparse.
Theorem 6.11. For every countable thin subset A of a group G, there
exists a subset B such that A ∪B is 2-sparse but not almost thin.
250 Selective survey on Subset...
Theorem 6.12. For every infinite thin subset A of a group G, there
exists a 2-thin subset B such that A ∪B is not 2-sparse.
Theorem 6.13. Suppose that a group G is either non-torsion, or for
every n ∈ N, there exists a finite subgroup Hn such that |Hn| > n. Then
there exists a 2-sparse subset of G which cannot be partitioned in finitely
many thin subsets.
Theorem 6.14. Every 2-sparse subset of a group G can be partitioned
in two P -small subsets.
6.3. Thin generating subsets of groups
By [43, Theorem 13.1], every infinite group G can be generated by
some small subset. This statement can be essentially strengthened if we
use the thin subsets instead of small.
In the following theorems ”k-thin subset A of a group G” means that
A is both left and right k-thin, i.e. |gA ∩A| 6 k, |Ag ∩A| 6 k for every
g ∈ G, g 6= e.
Theorem 6.15. Every infinite group G has a 2-thin system of genera-
tors. Moreover, if G has no elements of order 2 and G is either Abelian
or a torsion group, then there exists a 1-thin system of generators of G.
Theorem 6.16. For every infinite group G, there exists a 2-thin subset
X such that G = XX−1 ∪X−1X.
Theorem 6.17. For every infinite group G, there exists a 4-thin subset
X such that G = XX−1.
Comments. Theorems 6.14, 6.15, 6.17 are from [23], all other results
from [24].
7. Colorings
7.1. Chromatic numbers
Let X be a set and F be a family of subsets of X (the pair (X,F)
can be thought as a hypergraph with the set of vertices X and the set
of edges F). Following [43], a coloring χ : X → κ of X (i.e., a surjective
mapping of X onto a cardinal κ) is defined to be
• F-surjective if the restriction χ|F is surjective for all F ∈ F ;
• F-injective if χ|F is injective for all F ∈ F ;
I. V. Protasov 251
• F-nonconstant if χ|F is not constant for all F ∈ F ;
• F-bijective or F-kaleidoscopical if χ|F is bijective for all F ∈ F .
The family F is called kaleidoscopical if it admits an F-kaleidoscopical
coloring χ : X → κ. Other three notions lead us to the following cardinal
characteristics of the family F :
κsur(F) = sup{κ : there is an F-surjective coloring χ : X → κ};
κinj(F) = min{κ : there is an F-injective coloring χ : X → κ};
κnon(F)= min{κ : there is an F-nonconstant coloring χ :X→ κ}.
If X admits no F-nonconstant colorings, we put κnon(F) = 1. Due to
historical traditions, we call the cardinals κsur(F), κnon(F) and κinj(F)
the resolvability, coresolvability and achromatic number of F , respec-
tively.
These numbers have been studied in many different contexts. The
concept of resolvability came from topology. In 1943 E. Hewitt [21] in-
troduced the notion of an irresolvable topological space, i.e., a space X
with κsur(F) = 1, where F is the family of non-empty open subsets of
X. The information about the status of the resolvable spaces and its
algebraic aspects can be found in the surveys [7, 12,32].
On the other hand, the study of coresolvability numbers is the cen-
tral topic of Ramsey Theory, see [19, 22, 41]. For example, the Wan der
Waerden Theorem is nothing else but the equality κnon(F) = ℵ0 where
F is the family of all arithmetic progressions in N.
Another very important field where the coresolvability and achromatic
numbers appear naturally is Graph Theory. For example, the chromatic
number κ(Gr) of a graph Gr is nothing else but κnon(F) = κinj(F)
where F is the family of edges of Gr. In fact, many questions concerning
coloring of a hypergraph (X,F) can be reduced to studying the graph
GrF whose set of vertices is X and two vertices v1, v2 ∈ X are connected
by an edge in GrF if and only if v1, v2 ∈ F for some F ∈ F . Using this
observation, we get (see [43, Theorem 5.7]) the following estimates for
the numbers κsur(F), κinj(F) and κnon(F):
κsur(F) 6 minF∈F |F | 6 supF∈F
|F | 6 κinj(F) 6 sup
x∈X
|St(x, F )|,
κnon(F) 6 1 + ord(F) and κnon(F) = 2 ⇔ κsur(F) > 2,
where ord(x,F) = |{F ∈ F : x ∈ F}|, ord(F) = supx∈X ord(x,F), and
St(x, F ) = ∪{F ∈ F : x ∈ F} for x ∈ X.
252 Selective survey on Subset...
Given a subset F ⊆ X of a G-space X, we get the hypergraph
(X, {gF : g ∈ G}). For the chromatic characteristics of this hypergraph
and a couple of open questions see [43, Chapters 6,7]. Only one typical
result [43, Theorem 7.1].
Theorem 7.1. Let G be a group considered as the left regular G-space,
F be a finite subset of G with |F | > 1, F = {gF : g ∈ G}. Then the
following statements hold
(i) κinj(F) 6 |F |2 − |F |+ 1 and κnon(F) 6 3;
(ii) κinj(F) = |F |2 − |F | + 1 if and only if either F = {a, b} is two-
element subset with ab−1 being of odd order, or else F−1F is a
subgroup of size |F−1F | = |F |2 − |F |+ 1;
(iii) κinj(F) = 2 if F−1F contains an element of infinite or even order.
A new chromatic characteristic of a hypergraph (X,F), the color
detector, appeared in [46] in connection with [5]. Let λ be a cardinal,
λ < |X|. A coloring χ : X → κ is called λ-admissible if |χ(F )| 6 λ for
every F ∈ F . Then λ is a color detector if
λ = sup{|χ(X)| : χ is an λ-admissible coloring of X}.
Theorem 7.2. Let G be a group with the identity e, F ⊆ G and e ∈ F .
Then 1 is a color detector of the hypergraph (G, {gF : g ∈ G}) if and
only if G = 〈F 〉.
One of the most interesting branch of the Subset Combinatorics of
Groups is the Symmetry and Colorings (see the survey [7] and [8]). A
subset A of a group G is said to be symmetric if A = gA−1g for some
g ∈ G, the center of symmetry. A good part of efforts was concentrated
around calculations of ν(G, κ): the minimal number of colors necessary to
color the group G so that G contains no monochrome symmetric subsets
of size κ. We restrict ourself with only one result in this direction.
Theorem 7.3. For an infinite Abelian group G,
ν(G,ℵ0)
=



r0(G) + 1, if G is finitely generated;
r0(G) + 2, if G is countable, not
finitely generated and |B(G)| < ℵ0;
max{|B(G)|, log |G|}, if G is uncountable or |B(G)| > ℵ0
where r0(G) is a free rank of G, B(G) = {g ∈ G : 2g = 0}, log κ =
min{α : 2α > κ}.
I. V. Protasov 253
In particular, ν(Zn,ℵ0) = n+1, ν(Qn,ℵ0) = n+2 and ν(Rn,ℵ0) = ℵ0
for n ∈ N.
7.2. Kaleidoscopical configurations
Let X be a G-space. We say that a subset F of X is a kaleidoscopical
configuration if there exists a coloring χ : X → κ such that the restriction
χ|gF : gF → κ is a bijection for every g ∈ G. Clearly, F is a kaleido-
scopical configuration if and only if the hypergraph (X, {gF : g ∈ G}) is
kaleidoscopical.
To characterize the kaleidoscopical configurations in groups (consid-
ered as the left regular G-space), we use the following definitions.
A subset A of a group G is called
• complemented if there is a subset B ⊆ G such that the multiplica-
tion mapping µ : A×B → G, µ(a, b) = ab, is bijective;
• doubly complemented if there is a complemented subset B ⊆ G
such that the multiplication mapping µ : A×B → G, µ(a, b) = ab,
is bijective.
Theorem 7.4. Let G be a group. Each kaleidoscopical subset of G is
complemented and each doubly complemented subset of G is kaleidoscop-
ical.
It should be mentioned that Theorem 7.4 reduces the kaleidoscop-
ical problem in Abelian groups to the well known factorization prob-
lem. For the current state of the latter problem see [Sa´ndor Szabo´,
Arthur D. Sands, Factoring groups into subsets, CRC Press, 2009].
Corollary 7.1. The cadinality |F | of a kaleidoscopical subset F of a
finite group G divides |G|.
Corollary 7.2. A subset F of an Abelian group G is kaleidoscopical if
and only if F is complemented.
Question 7.1. Is each kaleidoscopical subset of a group double comple-
mented?
Given a subset A of a group G, how to detect whether A is a kalei-
doscopical configuration? For a finite Abelian group G, the following
theorem reduces this question to the case in which |A| and |G| have the
same set of prime divisors.
Theorem 7.5. Let A be a kaleidoscopical configuration in a finite Abelian
group G, m be a natural number such that (m, |A|) = 1. Then mA is a
kaleidoscopical configuration in mG.
254 Selective survey on Subset...
The following theorem reduces the detecting problem for Z to the case
of finite cyclic groups.
Theorem 7.6. Let F be a kaleidoscopical configuration in Z, χ : Z →
{1, . . . , n} be corresponding kaleidoscopical coloring. Then there exists a
natural number t such that χ(z + t) = χ(z) for every z ∈ Z.
Now we describe some general construction of kaleidoscopical con-
figurations in a transitive G-space X. To this end we use the standart
indentification of X with the (left) coset space G/H where H = {g ∈ G :
gx0 = x0}, x0 is a fixed element of X.
Let G be a group, H be a subgroup of G, and let
G = G0 ⊃ G1 ⊃ · · · ⊃ Gn = H
be a chain of subgroups of G. The coset tree T = T (G0, G1, . . . , Gn)
is a tree with the root G0, whose vertices are all left cosets of G by
Gi, i ∈ {1, . . . , n}, and two vertices A ∈ G/Gi and B ∈ G/Gj are
incident if and only if j = i + 1 and B ⊂ A. Thus, G/H is the set of
endvertices of T .
We say that a coloring of T in two colors (black and white) is coherent
if
(i) the root G0 is black;
(ii) if a vertex is white then all its successors are white;
(iii) if a vertex is black then either one of its successors is black and
others are white (type I) or all its successors are black (type II);
(iv) any two vertices on the same level are of the same type.
Theorem 7.7. The set of all black endvertices in a coherent coloring of
T forms a kaleidoscopical configuration in G/H.
The above construction can also be used as the coherent test giv-
ing a sufficient condition for a subset F ⊂ G/H to be a kaleidoscopical
configuration.
Let G0 = G,Gn = H and T (G0, G1, . . . , Gn) be a coset tree. Let F
be a subset of G/H. We define a coloring of T in black and white by
the following rule: a vertex gGi is black if and only if gGi ∩ F 6= ∅.
We say that F satisfies the coherent test for T (G0, G1, . . . , Gn) if this
coloring is coherent. If this is so, by Theorem 7.7, F is a kaleidoscopical
configuration. If F does not satisfy this test, we have nothing to say
about the kaleidoscopicality of F .
I. V. Protasov 255
Question 7.2. Let F be a kaleidoscopical configuration in a finite cyclic
group G. Does there exist a decreasing system G = G0, G1, . . . , Gn = {0}
of subgroups of G such that F satisfies the coherent test for T (G0, G1, . . . ,
Gn)?
Theorem 7.8. Let p be a prime number, n ∈ N. A subset F ⊆ Zpn is
a kaleidoscopical configuration if and only if F satisfies the coherent test
for the coset tree T (Zpn , pZpn , . . . , pnZpn).
Theorem 7.9. Let p1, . . . , pn be distinct primes, N = p1 . . . pn. A subset
F ⊆ ZN is a kaleidoscopical configuration if and only if |F | divides N
and F satisfies the coherent test for the coset tree T (ZN ,mZN , {0}) where
m = N|F | .
Question 7.3. Is there a polynomial test detecting whether a given
subset A of a finite Abelian group is a kaleidoscopical?
By Theorems 7.8 and 7.9, such test exists in corresponding cases.
References
[1] T. Banakh, N. Lyaskovska, Weakly P-small not P-small subsets in groups //
Intern. J. Algebra Computation, 18 (2008), 1–6.
[2] T. Banakh, N. Lyaskovska, Completenness of translation invariant ideals in
groups // Ukr. Math. J., (to appear).
[3] T. Banakh, N. Lyaskovska, D. Repovsˇ, Packing index of subsets in Polish
groups // Notre Dame J. Formal Logic, 50:4 (2009), 453–468.
[4] T. Banakh, O. Petrenko, I. Protasov, Kaleidoscopical configurations, manuscript.
[5] T. Banakh, S. Pikhurko, A game characterization of limit-detecting sequences in
locally compact G-space // Math. Stud., 21, N 2, 115–132.
[6] T. O. Banakh, I. V. Protasov, Asymmetric colorings of Abelian groups // Math.
Zametki, 66 (1999), 17–30.
[7] T. O. Banakh, I. V. Protasov, Symmetry and colorings: some results and open
problems // Izv. Gomel Univ., Voprosy algebry, 17 (2001), 4–15.
[8] T. Banakh, I. Protasov, O. Verbitskiy, Symmetry and Colorings, monograph in
preparation.
[9] A. Bella, V. Malykhin, Certain subsets of a group // Questions Answers General
Topology, 17 (1999), 183–187.
[10] T. Carlson, N. Hindman, J. McLeod, D. Strauss, Almost disjoint large subsets of
semigroups // Topology Appl., 155 (2008), 433–444.
[11] C. Chou, On the size of the set of left invariant means on a semigroup // Proc.
Amer. Math. Soc., 23 (1969), 199–205.
[12] W. W. Comfort, S. Garsia-Ferreira, Resolvability: a selective survey and some
results // Topology Appl., 74 (1996), 149–167.
[13] D. Dikranjan, I. Protasov, Every infinite group can be generated by P-small
subset // Appl. General Topology, 7 (2006), 265–268.
256 Selective survey on Subset...
[14] D. Dikranjan, I. Protasov, Counting maximal topologies on countable groups and
rings // Topol. Appl., 156 (2008), 322–325.
[15] P. C. Eklof, Set theoretical methods in Homological Algebra and Abelian group,
Les Press de L’Universite’ de Montreal, Montreal, 1980.
[16] M. Filali, Ie. Lutsenko, I. V. Protasov, Boolean group ideals and the ideal structure
of βG // Math. Stud., 31 (2009), 19–28.
[17] M. Filali, I. V. Protasov, Spread of balleans // Appl. General Topology, 9 (2008),
161–175.
[18] V. Gavrylkiv, Algebraic-topological structures on superextensions, Dissertation,
Lviv, 2009.
[19] R. Graham, B. Rotschild, J. Speneer, Ramsey Theory, Willey, NY, 1980.
[20] F. Greenleaf, Invariant Means on Topological Groups and their Applications, Van
Nostrand, NY, London, Melbourne, Toronto, 1966.
[21] E. Hewitt, A problem in set-theoretical topology // Duke Math. J., 10 (1943),
309–333.
[22] N. Hindman, D. Strauss, Algebra in the Stone-Cˇech Compactification — Theory
and Applications, Walter de Grueter, Berlin, New York, 1998.
[23] Ie. Lutsenko, Thin systems of generators of groups // Algebra Discrete Math., to
appear.
[24] Ie. Lutsenko, I. V. Protasov, Sparse, thin and other subsets of groups // Intern.
J. Algebra Computation, 19 (2009), 491–510.
[25] Ie. Lutsenko, I. V. Protasov, Sketch of vector balleans // Math. Stud., 31 (2009),
219–224.
[26] Ie. Lutsenko, I. V. Protasov, Thin subsets of balleans, manuscript.
[27] N. Lyaskovska, Constructing subsets of given packing index in Abelian groups //
Acta Universitatis Carolinae, Mathematica et Phisica, 48 (2007), 69–80.
[28] V. Malykhin, R. Moresko, Small generated groups // Questions Answers General
Topology, 19 (2001), 47–53.
[29] V. I. Malykhin, I. V. Protasov, Maximal resolvability of bounded groups // Topol.
Appl., 20 (1996), 1–6.
[30] I. Prodanov, Some minimal group topologies are precompact // Math. Ann., 227
(1977), 117–125.
[31] I. V. Protasov, Resolvability of τ -bounded groups // Math. Stud., 5 (1995), 17–20.
[32] I. V. Protasov, Resolvability of groups // Math. Stud., 9 (1998), 130–148.
[33] I. V. Protasov, Partitions of groups onto large subsets // Math. Notes, 73 (2003),
271–281.
[34] I. V. Protasov, Small systems of generators of groups // Math. Notes, 76 (2004),
420–426.
[35] I. V. Protasov, Resolvability of ball structures // Appl. General Topology, 5
(2004), 191–198.
[36] I. V. Protasov, Cellularity and density of balleans // Appl. General Topology, 8
(2007), 283–291.
[37] I. V. Protasov, Extraresolvability of balleans // Comment. Math. Univ. Carolinae,
48 (2007), 161–175.
I. V. Protasov 257
[38] I. V. Protasov, Balleans of bounded geometry and G-spaces // Math. Stud., 30
(2008), 61–66.
[39] I. V. Protasov, Small subsets of groups // Topology Appl., 156 (2009), 2651–2658.
[40] I. Protasov, Counting Ω-ideals, Algebra Universalis.
[41] I. V. Protasov, Combinatorics of Numbers, Math. Stud. Monogr. Ser., Vol. 2,
VNTL Publishers, Lviv, 1997.
[42] I. Protasov, E. Zelenyuk, Topologies on Groups Determined by Sequence, Math.
Stud. Monogr. Ser., Vol. 4, VNTL Publishers, Lviv, 1999.
[43] I. Protasov, T. Banakh, Ball Structures and Colorings of Graphs and Groups,
Math. Stud. Monogr. Ser., Vol. 11, VNTL Publishers, Lviv, 2003.
[44] I. Protasov, M. Zarichnyi, General Asymptology, Math. Stud. Monogr. Ser.,
Vol. 12, VNTL Publishers, Lviv, 2007.
[45] I. Protasov, M. Filaly, Ultrafilters and Topologies on Groups, Math. Stud. Monorg.
Ser., (to appear).
[46] I. V. Protasov, O. I. Protasova, Color-detectors of hypergraphs // Algebra Dis-
crete Math., (2005), N 1, 91–98.
[47] I. V. Protasov, O. I. Protasova, On closed ideals of βG // Semigroup Forum,
75 (2007), 237–240.
[48] J. Roe, Lectures on Coarse Geometry, AMS University Lecture Ser, vol. 31,
2003.
[49] W. Seredin´ski, Some operations related to translations // Colloq. Math., 57
(1989), 203–219.
[50] S. Solecki, Translation invariant ideals // Israel J. Math., 135 (2003), 93–110.
[51] S. Solecki, Size of subsets of groups and Haar null sets // GAFA, 15 (2005),
246–273.
[52] T. Tao, V. Vu, Additive Combinatorics, Cambridge Studies in Advance Math.,
vol. 105, Cambridge University Press, 2006.
[53] V. O. Vasil’eva, I. V. Protasov, Around van der Waerden Theorem // U sviti
matematyky, (2000), 17–19.
Contact information
Igor V. Protasov Taras Shevchenko National
University of Kyiv
64, Volodymyrs’ka St.,
01601 Kyiv,
Ukraine
E-Mail: i.v.protasov@gmail.com