() @ Appl. Gen. Topol. 14, no. 2 (2013), 171-178doi:10.4995/agt.2013.1587 c© AGT, UPV, 2013 The combinatorial derivation Igor V. Protasov Department of Cybernetics, Kyiv University, Volodimirska 64, Kyiv 01033, Ukraine (i.v.protasov@gmail.com) Abstract Let G be a group, PG be the family of all subsets of G. For a subset A ⊆ G, we put ∆(A) = {g ∈ G : |gA ∩ A| = ∞}. The mapping ∆ : PG → PG, A 7→ ∆(A), is called a combinatorial derivation and can be considered as an analogue of the topological derivation d : PX → PX, A 7→ A d , where X is a topological space and A d is the set of all limit points of A. Content: elementary properties, thin and almost thin subsets, partitions, inverse construction and ∆-trajectories, ∆ and d. 2010 MSC: 20A05, 20F99, 22A15, 06E15, 06E25. Keywords: Combinatorial derivation; ∆-trajectories; large, small and thin subsets of groups; partitions of groups; Stone-Čech compactifi- cation of a group. 1. Introduction Let G be a group with the identity e, PG be the family of all subsets of G. For a subset A of G, we denote ∆(A) = {g ∈ G : |gA ∩ A| = ∞}, observe that ∆(A) ⊆ AA−1, and say that the mapping ∆ : PG → PG, A 7→ ∆(A) is the combinatorial derivation. In this paper, on one hand, we analyze from the ∆-point of view a series of results from Subset Combinatorics of Groups (see the survey [9]), and point out some directions for further progress. On the other hand, the ∆-operation is interesting and intriguing by its own sake. In contrast to the trajectory A → Received October 2012 – Accepted January 2013 http://dx.doi.org/10.4995/agt.2013.1587 I. V. Protasov AA−1 → (AA−1)(AA−1)−1 → . . ., the ∆-trajectory A → ∆(A) → ∆2(A) → . . . of a subset A of G could be surprisingly complicated: stabilizing, increasing, decreasing, periodic or chaotic. For a symmetric subset A of G with e ∈ A, there exists a subset X ⊆ G such that ∆(X) = A. We conclude the paper by demonstrating how ∆ and a topological derivation d arise from some unified ultrafilter construction. We note also that ∆(A) may be considered as some infinite version of the symmetry sets well-known in Additive Combinatorics [11, p. 84]. Given a finite subset A of an Abelian group G and α > 0, the symmetry set Symα(A) is defined by Symα(A) = {g ∈ G : |A ∩ (A + g)| > α|A|}. 2. Elementary properties Claim 2.1. (∆(A))−1 = ∆(A), ∆(A) ⊆ AA−1. Claim 2.2. ∆(A) = ∅ ⇔ e /∈ ∆(A) ⇔ A is finite. Claim 2.3. For subsets A, B of G, we let ∆(A, B) = {g ∈ G : |gA ∩ B| = ∞} and note that ∆(A ∪ B) = ∆(A) ∪ ∆(B) ∪ ∆(A, B) ∪ ∆(B, A), ∆(A ∩ B) ⊆ ∆(A) ∩ ∆(B) . Claim 2.4. If F is a finite subset of G then ∆(FA) = F∆(A)F −1. Claim 2.5. If A is an infinite subgroup then A = ∆(A) but the converse statement does not hold, see Theorem 6.2. 3. Thin and almost thin subsets A subset A of a group G is said to be [8]: • thin if either A is finite or ∆(A) = {e}; • almost thin if ∆(A) is finite; • k-thin (k ∈ N) if |gA ∩ A| 6 k for each g ∈ G \ {e}; • sparse if, for every infinite subset X ⊆ G, there exists a non-empty finite subset F ⊂ X such that ⋂ g∈F gA is infinite; • k-sparse (k ∈ N) if, for every infinite subset X ⊆ G, there exists a subset F ⊂ X such that |F | 6 k and ⋂ g∈F gA is finite. The following statements are from [8]. Theorem 3.1. Every almost thin subset A of a group G can be partitioned 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. c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 172 The combinatorial derivation Theorem 3.2. A subset A of a group G is 2-sparse if and only if X−1X * ∆(A) for every infinite subset X of G. Theorem 3.3. For every countable thin subset A of a group G, there is a thin subset B such that A ∪ B is 2-sparse but not almost thin. Theorem 3.4. Suppose that a group G is either torsion-free or, for every n ∈ N, there exists a finite subgroup Hn of G such that |Hn| > n. Then there exists a 2-sparse subset of G which cannot be partitioned in finitely many thin subsets. By Theorem 3.2, every almost thin subset is 2-sparse. By Theorems 3.3, 3.4, the class of 2-sparse subsets is wider than the class of almost thin subsets. By Theorem 3.3, a union of two thin subsets needs not to be almost thin. By Theorem 2.3, a union A1 ∪ . . . ∪ An of almost thin subset is almost thin if and only if ∆(Ai, Aj) is finite for all i, j ∈ {1, . . . , n}, By Claim 2.4, if A is almost thin and K is finite then KA is almost thin. The following statements are from [7]. Theorem 3.5. For every infinite group G, there exists a 2-thin subset such that G = XX−1 ∪ X−1X. Theorem 3.6. For every infinite group G, there exists a 4-thin subset such that G = XX−1. Since ∆(X) = {e} for each infinite thin subset of G, Theorem 3.6 gives us X with ∆(X) = {e} and XX−1 = G. 4. Large and small subsets A subset A of a group G is called [8]: • large if there exists a finite subset F of G such that G = FA; • ∆-large if ∆(A) is large; • small if (G \ A) ∩ L is large for each large subset L of G; • P-small if there exists an injective sequence (gn)n∈ω in G such that the subsets {gnA : n ∈ ω} are pairwise disjoint; • almost P-small if there exists an injective sequence (gn)n∈ω in G such that the family {gnA : n ∈ ω} is almost disjoint, i.e. gnA ∩ gmA is finite for all distinct n, m ∈ ω. • weakly P-small if, for every n ∈ ω, one can find distinct elements g1, . . . , gn of G such that the subsets g1A, . . . , gnA are pairwise disjoint. Let G be a group, A is a large subset of G. We take a finite subset F of G, F = {g1, . . . , gn} such that G = FA. Take an arbitrary g ∈ G. Then giA ∩ gA is infinite for some i ∈ {1, . . . , n}, so g−1i g ∈ ∆(A). Hence, G = F∆(A) and A is ∆-large. By Theorem 3.6, the converse statement is very far from being true. If A is not small then FA is thick (see Definition 5.2) for some finite subset F . It follows that ∆(FA) = G. By Claim 2.4, ∆(FA) = F∆(A)F −1, so if G is Abelian then A is ∆-large. c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 173 I. V. Protasov J. Erde proved that every non-small subset of an arbitrary infinite non- Abelian group G ∆-large. It is easy to see that A is P-small (almost P-small) if and only if there exists an infinite subset X of G such that X−1X∩PP −1 = {e} (X−1X∩∆(X) = {e}). A is weakly P-small if and only if, for every n ∈ ω, there exists F ⊂ G such that |F | = n and F −1F ∩ PP −1 = {e}. By [8, Lemma 4.2], if AA−1 is not large then A is small and P-small. Using the inverse construction from Section 6, we can find A such that A is not ∆-large and A is not P-small. Every infinite group G has a weakly P-small not P-small subsets [1]. More- over, G has almost P-small not P-small subset and , if G is countable, weakly P-small not almost P-small subset. By [8], every almost P-small subset can be partitioned in two P-small subsets. If A is either almost or weakly P-small then G \ ∆(A) is infinite, but a subset A with infinite G \ ∆(A) could be large: G = Z, A = 2Z. 5. Partitions Let G be a group and let G = A1 ∪ . . . An be a finite partition of G. In section 7, we show that at least one cell Ai is ∆-large, in particular, AiA −1 i is large. If G is infinite amenable group and µ is a left invariant Banach measure on G, we can strengthened this statement: there exist a cell Ai and a finite subset F such that |F | 6 n and G = F∆(Ai). To verify this statement, we take Ai such that µ(Ai) > 1 n and choose distinct g1, . . . , gm such that µ(gkAi ∩ glAi) = 0 for all distinct k, l ∈ {1, . . . , m}, and the family {g1Ai, . . . , gmAi} is maximal with respect to this property. Clearly, m 6 n. For each g ∈ G, we have µ(gAi ∩ gkAi) > 0 for some k ∈ {1, . . . , m} so g−1k g ∈ ∆(Ai) and G = {g1, . . . , gm}∆(Ai). By [10, Theorem 12.7], for every partition A1 ∪. . .∪An of an arbitrary group G, there exist a cell Ai and a finite subset F of G such that G = FAiA −1 i and |F | 6 22n−1−1. S. Slobodianiuk strengthened this statement: there are F and Ai such that |F | 6 22 n−1−1 and G = F∆(Ai). It is an old unsolved problem [5, Problem 13.44] whether i and F can be chosen so that G = FAiA −1 i and |F | 6 n, see also [10, Question 12.1]. Question 5.1. Given any partition G = A1 ∪ . . . ∪ An, do there exist F and Ai such that G = F∆(Ai) and |F | 6 2n? Definition 5.2. A subset A of a group G is called [11]: • thick if G \ A is not large; • k-prethick (k ∈ N) if there exists a subset F of G such that |F | 6 k and FA is thick; • prethick if A is k-prethick for some k ∈ N. By [3, Theorem 5.3.2], for a group G, the following two conditions (i) and (ii) are equivalent: c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 174 The combinatorial derivation (i) for every partition G = A ∪ B, either G = AA−1 or G = BB−1; (ii) each element of G has odd order. If G is infinite, we can show that these conditions are equivalent to (iii) for every partition G = A ∪ B, either G = ∆(A) or G = ∆(G). 6. Inverse construction and ∆-trajectories Theorem 6.1. Let G be an infinite group, A ⊆ G, A = A−1, e ∈ A. Then there exists a subset X of G such that ∆(X) = A. Proof. First, assume that G is countable and write the elements of A in the list {an : n < ω}, if A is finite then all but finitely many an are equal to e. We represent G \ A as a union G \ A = ⋃ n∈ω Bn of finite subsets such that Bn ⊆ Bn+1, B−1n = Bn. Then we choose inductively a sequence (Xn)n∈ω of finite subsets of G, Xn = {xn0, xn1, . . . , xnn, a0xn0, . . . , anxnn} such that XmX −1 n ∩ Bn = {e} for all m 6 n < ∞. After ω steps, we put X = ⋃ n∈ω Xn. By the construction, ∆(X) = A. If |A| 6 ℵ0 but G is not countable, we take a countable subgroup H of G such that A ⊆ H, forget about G and find a subset X ⊆ H such that ∆(X) is equal to A in H. Since gA ∩ A = ∅ for each g ∈ G \ H, we have ∆(X) = A. At last, let |A| > ℵ0. By above paragraph, we may suppose that |A| = |G|. We enumerate A = {aα : α < |G|} and construct inductively a sequence (Xα)α<|G| of finite subsets of G and an increasing sequence (Hα)α<|G| of sub- group of G such that if α = 0 or α is a limit ordinal, n ∈ ω, Xα+n = {xα+n,0, xα+n,1, . . . , xα+n,n, aαxα+n,0, . . . , aα+nxα+n,n}, Xα+n ⊆ Hα+n+1 \ Hα+n, Xα+nX−1α+n ⊆ A ∪ (Hα+n+1 \ Hα+n). After |G| steps, we put X = ⋃ α<|G| Xα. By the construction, ∆(X) = A. � Let A1, . . . , Am be subsets of an infinite group G such that G = A1∪. . .∪Am. By the Hindman theorem [4, Theorem 5.8], there are exists i ∈ {1, . . . , m} and an injective sequence (gn)n∈ω in G such that FP(gn)n∈ω ⊆ Ai, where FP(gn)n∈ω is a set of all element of the form gi1gi2 . . . gil, i1 < . . . , ik < ω, k ∈ ω. We show that there exists X ⊆ FP(gn)n∈ω such that ∆(X) = {e} ∪ FP(gn)n∈ω ∪ (FP(gn)n∈ω)−1. We note that if G is countable, at each step n of the inverse construction, the elements xn0, . . . , xnn can be chosen from any pregiven infinite subset Y of G. We enumerate FP(gn)n∈ω in a sequence (an)n∈ω and put Y = {gn : n ∈ ω}. Using above observation, we get the desired X. If G is countable, we can modify the inverse construction to get X such that ∆(X) = A and |X ∩g1 ∩g2X| < ∞ for all distinct g1, g2 ∈ G\{e}, in particular, X is 3-sparse and, in particular, small. c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 175 I. V. Protasov Another modification, we can choose X such that X ∩ gX 6= ∅ for each g ∈ G. If we take A not large, then we get X which is not P-small and X is not ∆-large, see Section 4. Theorem 6.2. Let G be a countable group such that, for each g ∈ G \ {e}, the set √ g = {x ∈ G : x2 = g} is finite. Then the following statements hold: (T r1) Given any subset X0 ⊆ G, X0 = X−10 , e ∈ X0, there exists a sequence (Xn)n∈ω of subsets of G such that ∆(Xn+1) = Xn and Xm ∩Xn = {e}, 0 < m < n < ω. (T r2) There exists a sequence (Xn)n∈Z of subsets of G such that ∆(Xn) = Xn+1, Xm ∩ Xn = {e}, m, n ∈ Z, m 6= n. (T r3) There exists a subset A of G such that ∆(A) = A but A is not a subgroup. (T r4) There exists a subset A such that A ⊃ ∆(A) ⊃ ∆2(A) ⊃ . . .. (T r5) There exists a subset A such that A ⊂ ∆(A) ⊂ ∆2(A) ⊂ . . .. (T r6) For each natural natural number n, there exists a periodic ∆-trajectory X0, . . . , Xn−1 of length n: X1 = ∆(X0), X2 = ∆(X1), . . . , Xn = ∆(Xn−1) such that Xi ∩ Xj = {e}, i < j < n. Proof. We use the following simple observation (*) if F is a finite subset of an infinite group G and g /∈ F then the set {x ∈ G : x−1gx /∈ F} is infinite. In constructions of corresponding trajectories, at each inductive step, we use a finiteness of √ g and (*) in the following form: (**) if a ∈ G, F is a finite subset of G, F ∩ {e, a±1} = ∅ then there exists x ∈ G such that {x±1, (ax)±1}{x±1, (ax)±1} ∩ F = ∅. We show how to get a 2-periodic trajectory: X, Y , ∆(X) = Y , ∆(Y ) = X, X ∩ Y = {e}. We write G as a union G = ⋃ n∈ω Fn of increasing chain {Fn : n ∈ ω} of finite symmetric subsets F0 = {e}. We put X0 = Y0 = {e} and construct inductively with usage of (**) two chains (Xn)n∈ω, (Yn)n∈ω of finite subsets of G such that, for each n ∈ ω, Xn+1 = {(x(y))±1, (yx(y))±1 : y ∈ Y0 ∪ . . . ∪ Yn}, Yn+1 = {(y(x))±1, (xy(x))±1 : x ∈ X0 ∪ . . . ∪ Xn}, (X0 ∪ . . . ∪ Xn) ∩ (Y0 ∪ . . . ∪ Yn) = {e}, Xn+1Xn+1 ∩ (Fn+1 \ (Y0 ∪ . . . ∪ Yn)) = ∅, Yn+1Yn+1 ∩ (Fn+1 \ (X0 ∪ . . . ∪ Xn)) = ∅, (X0 ∪ . . . ∪ Xn)Xn+1 ∩ (Fn+1 \ (Y0 ∪ . . . ∪ Yn)) = ∅, (Y0 ∪ . . . ∪ Yn)Yn+1 ∩ (Fn+1 \ (X0 ∪ . . . ∪ Xn)) = ∅. After ω steps, we put X = ⋃ n∈ω Xn, Y = ⋃ n∈ω Yn. � c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 176 The combinatorial derivation 7. ∆ and d For a subset A of a topological space X, the subset Ad of all limit points of A is called a derived subset, and the mapping d : P(X) → P(X), A → Ad, defined on the family of P(X) of all subsets of X, is called the topological derivation, see [6, §9]. Let X be a discrete set, βX be the Stone-Čech compactification of X. We identify βX with the set of all ultrafilters on X, X with the set of all principal ultrafilters, and denote X∗ = βX \ X the set of all free ultrafilters. The topology of βX can be defined by the family {A : A ⊆ X} as a base for open sets, A = {p ∈ βX : A ∈ p}, A∗ = A ∩ G∗. For a filter ϕ on X, we put ϕ = {p ∈ βX : ϕ ⊆ p}, ϕ∗ = ϕ ∩ G∗. Let G be a discrete group, p ∈ βG. Following [2, Chapter 3], we denote cl(A, p) = {g ∈ G : A ∈ gp}, gp = {gP : P ∈ p}, say that cl(A, p) is a closure of A in the direction of p, and note that ∆(A) = ⋂ p∈A∗ cl(A, p). A topology τ on a group G is called left invariant if the mapping lg : G → G, lg(x) = gx is continuous for each g ∈ G. A group G endowed with a left invariant topology τ is called left topological. We note that a left invariant topology τ on G is uniquely determined by the filter ϕ of neighbourhoods of the identity e ∈ G, ϕ and ϕ∗ are the sets of all ultrafilters an all free ultrafilters of G converging to e. For a subset A of G, we have Ad = ⋂ p∈(τ∗) cl(A, p), and note that Ad ⊆ ∆(A) if A is a neighbourhood of e in (G, τ). Now we endow G with the discrete topology and, following [4, Chapter 4], extend the multiplication on G to βG. For p, q ∈ βG, we take P ∈ p and, for each g ∈ P , pick some Qg ∈ q. Then ⋃ g∈p gQp ∈ pq and each member of pq contains a subset of this form. With this multiplication, βG is a compact right topological semigroup. The product pq can also be defined by the rule [2, Chapter 3]: A ⊆ G, A ∈ pq ⇔ cl(A, q) ∈ p. If (G, τ) is left topological semigroup then τ is a subsemigroup of βG. If an ultrafilter p ∈ τ is taken from the minimal ideal K(τ) of τ, by [2, Theorem 5.0.25]. there exists P ∈ p and finite subset F of G such that Fcl(P, p) is neighbourhood of e in τ. In particular, if τ indiscrete (τ = {∅, G}), p ∈ K(βG)) and P ∈ p then cl(P, p) is large. If G is infinite, p ∈ K(βG) is free, so cl(P, p) ⊆ ∆(P) and P is ∆-large. If a group G is finitely partitioned G = A1 ∪ . . . ∪ An, then some cell Ai is a member of p, hence Ai is ∆-large. c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 177 I. V. Protasov References [1] T. Banakh and N. Lyaskovska, Weakly P-small not P-small subsets in groups, Intern. J. Algebra Computations 18 (2008), 1–6. [2] M. Filali and I. Protasov, Ultrafilters and Topologies on Groups, Math. Stud. Monorg. Ser., Vol. 13, VNTL Publishers, Lviv, 2010. [3] V. Gavrylkiv, Algebraic-topological structure on superextensions, Dissertation, Lviv, 2009. [4] N. Hindman and D. Strauss, Algebra in the Stone-Čech compactification, Walter de Grueter, Berlin, New York, 1998. [5] The Kourovka Notebook, Novosibirsk, Institute of Math., 1995. [6] K. Kuratowski, Topology, Vol. 1, Academic Press, New York and London, PWN, Warszawa, 1969. [7] Ie. Lutsenko, Thin systems of generators of groups, Algebra and Discrete Math. 9 (2010), 108–114. [8] Ie. Lutsenko and I. V. Protasov, Sparse, thin and other subsets of groups, Intern. J. Algebra Computation 19 (2009), 491–510. [9] I. V. Protasov, Selective survey on Subset Combinatorics of Groups, J. Math. Sciences 174 (2011), 486–514. [10] I. Protasov and T. Banakh., Ball Structure and Colorings of Groups and Graphs, Math. Stud. Monorg. Ser., Vol. 11, VNTL Publishers, Lviv, 2003. [11] T. Tao and V. Vu, Additive Combinatorics, Cambridge University Press, 2006. c© AGT, UPV, 2013 Appl. Gen. Topol. 14, no. 2 178