On some subgroup chains related to Kneser’s theorem
Yahya O. Hamidoune∗ Oriol Serra† Gilles Zémor‡
March 28, 2007
Abstract
A recent result of Balandraud shows that for every subset S of an
abelian group G there exists a non trivial subgroup H such that |TS| ≤
|T |+ |S| − 2 holds only if H ⊂ Stab(TS). Notice that Kneser’s Theorem
only gives {0} 6= Stab(TS).
This strong form of Kneser’s theorem follows from some nice properties
of a certain poset investigated by Balandraud. We consider an analogous
poset for nonabelian groups and, by using classical tools from Additive
Number Theory, extend some of the above results. In particular we obtain
short proofs of Balandraud’s results in the abelian case.
1 Introduction
In order to avoid switching from multiplicative to additive notation, all groups
will be written multiplicatively.
Kneser’s addition theorem states that if S, T are finite subsets of an abelian
group G then |ST | ≤ |S| + |T | − 2 holds only if ST is periodic (i.e, there
is a non trivial subgroup H such that HST = ST .) Kneser’s Theorem is a
fundamental tool in Additive number Theory. Proofs of this result may be
found in [4, 5, 6, 7, 9].
In all previously known proofs of Kneser’s Theorem, the subgroup H depends
crucially on both sets S and T . With the goal of breaking this double depen-
dence in S and T , Balandraud investigated in recent work [1, 2] the properties
of a combinatorial poset that we now present.
Let S be a finite subset containing 1 of a group G. Following Balandraud, let
us define a cell of S as a finite subset X such that, for all z /∈ X, it holds that
zS 6⊂ XS. This notion is defined in [1, 2] and it is equivalent to the notion of
Université Pierre et Marie Curie, Paris 6, Combinatoire et Optimisation - case 189, 4
place Jussieu, 75252 Paris Cedex 05. yha@ccr.jussieu.fr
Universitat Politècnica de Catalunya, Matemàtica Aplicada IV, Campus Nord - Edif. C3,
C. Jordi Girona, 1-3, 08034 Barcelona, Spain. oserra@mat.upc.es
Université de Bordeaux 1, Institut de Mathématiques de Bordeaux, 351 cours de la
Libération, 33405 Talence. zemor@math.u-bordeaux1.fr
http://arxiv.org/abs/0704.0382v1
nonextendible subset used in [3]. Throughout the paper, by a cell we always
mean a cell of S.
A cell X is called a u-cell if |XS| − |X| = u. A u-cell with minimal cardinality
is called a u-kernel (of S).
Balandraud showed that, for a finite set S in an abelian group G, in the poset
of j–cells containing the unity ordered by inclusion with 1 ≤ j ≤ |S| − 2, the
set of kernels form a chain of subgroups. Moreover, if there exists a u–cell, then
there is a unique u–kernel containing the unit element which is contained in all
u–cells containing the unit element.
One of the consequences of this work is a new proof and the following strength-
ening of Kneser’s Theorem:
Theorem 1 (Balandraud) For any non-empty finite subset S of an abelian
group G, there exists a finite subgroup H of G such that for any finite subset T
of G one of the following conditions hold :
• |TS| ≥ |T |+ |S| − 1
• HTS = TS and |TS| ≤ |HS|+ |HT | − |H|
As far as the authors are aware this is a surprising and strong formulation that
was not observed before and does not follow straightforwardly from the classical
forms of Kneser’s Theorem.
The purpose of the present note is to give a short proof for the nonabelian
case that, in the poset of j–cells that are subgroups ordered by inclusion with
0 ≤ j ≤ |S| − 1, the set of kernels form a chain of subgroups. Moreover, each
u-kernel of this poset is unique and contained in all u–cells of this poset.
From this statement Kneser’s theorem allows one to deduce Balandraud’s re-
sults for the abelian case, and in particular Theorem 1. Kneser’s Theorem has
several equivalent forms. We use the following one; see e.g [4, 7]:
Theorem 2 (Kneser [5]) Let G be an abelian group and X,Y ⊂ G be finite
subsets such that |XY | ≤ |X| + |Y | − 2. Then
|XY | = |HX|+ |HY | − |H|,
where H = stab(XY ) = {x : xXY = XY }.
Our main tool is the following Theorem of Olson[8, Theorem 2]. We give an
equivalent formulation here where we use left–cosets instead of right–cosets.
Theorem 3 (Olson [8]) Let X,Y be finite subsets of a group G, and let H
and K be subgroups such that HX = X, KY = Y and KX 6= X, HY 6= Y .
|X \ Y |+ |Y \X| ≥ |H|+ |K| − 2|H ∩K|.
In particular either |X \ Y | ≥ |H| − |H ∩K| or |Y \X| ≥ |K| − |H ∩K|.
We shall use the following lemma.
Lemma 4 ([1, 2]) Let G be a group and 1 ∈ S ⊂ G be a finite subset. Then
the intersection of two cells M1,M2 of S is a cell of S.
Proof. Let x /∈ M1 ∩M2. There is i with x /∈ Mi. Then xS 6⊂ MiS. Hence
xS 6⊂ (M1 ∩M2)S.
We can now state our main result, namely Theorem 5 below.
2 An application of Olson’s Theorem
Balandraud [1, 2] proved that, in the abelian case, the set of kernels containing
the unit element and ordered by inclusion is a chain of subgroups. In the non
abelian case we can prove only that the set of kernels that are subgroups forms
a chain. The abelian case can then be easily recovered, since Kneser’s Theorem
implies (as we shall see below) that a kernel containing the unit element is a
subgroup.
Theorem 5 Let S be a finite subset containing 1 of a group G. Let M be a
u–kernel of S which is a subgroup. Let N be a subgroup which is a v–cell and
suppose u, v ≤ |S| − 1.
(i) If either N is a v–kernel or u = v then M ⊂ N or N ⊂ M .
(ii) If N is a v–kernel and v ≤ u then M ⊂ N .
Proof. Suppose that M 6⊂ N and N 6⊂ M . Note that, since M is a cell, if
NMS = MS then NM = M , thus N ⊂ M against our assumption. Hence we
may assume NMS 6= MS and similarly MNS 6= NS. By Theorem 3 we have
one of the two following cases.
Case 1: |MS| − |(MS) ∩ (NS)| = |(MS) \ (NS)| ≥ |M | − |M ∩N |. It follows
that |(M ∩N)S| − |M ∩N | ≤ |(MS)∩ (NS)| − |M ∩N | ≤ |MS| − |M |. On the
other hand we have u = |MS| − |M | < |S| ≤ |(M ∩N)S|. Since |MS| − |M | is
a multiple of |M ∩N | we have
u = |MS| − |M | = |(M ∩N)S| − |M ∩N |.
By Lemma 4, M ∩N is a cell. Since M is a u–kernel, we have M ∩N = M, a
contradiction.
Case 2: |NS| − |(NS) ∩ (MS)| = |(NS) \ (MS)| ≥ |N | − |N ∩M |. It follows
that |(N ∩ M)S| − |N ∩ M | ≤ |(NS) ∩ (MS)| − |N ∩ M | ≤ |NS| − |N |. On
the other hand we have |NS| − |N | < |S| ≤ |(N ∩M)S|. Since |NS| − |N | is a
multiple of |N ∩M | we have
|NS| − |N | = |(N ∩M)S| − |N ∩M |. (1)
Assume first u = v. Then u = |MS|−|M | = |NS|−|N | = |(N∩M)S|−|N∩M |.
Since M is a u–kernel, we have M ∩N = M, a contradiction.
Assume that N is a v–kernel. Then (1) implies N ∩M = N, a contradiction.
This proves (i).
Assume now that v ≤ u. Suppose M 6⊂ N . By (i) we have N ⊂ M , which
implies in particular that |MS| − |M | is a multiple of N . Therefore, from
u = |MS| − |M | < |S| ≤ |NS| we have u = |MS| − |M | ≤ |NS| − |N | = v
which gives u = v. But then M 6⊂ N and N ⊂ M imply |N | < |M |, and since
N is now a u–cell, this contradicts M being a u–kernel.
We can now deduce Balandraud’s description for kernels and cells :
Corollary 6 (Balandraud [1, 2]) Let G be an abelian group and S ⊂ G be
a finite subset with 1 ∈ S. Let M be a u–kernel of S containing 1 with 1 ≤ u ≤
|S| − 2. Then,
(i) M is a subgroup.
(ii) Each u-cell is M–periodic.
(iii) Each v–kernel with u < v ≤ |S| − 2 is a proper subgroup of M .
Proof. Let X be a u-cell with u ≤ |S| − 2. By Kneser’s Theorem, the
inequality |XS| − |X| = u ≤ |S| − 2 implies
u = |XS| − |HX| = |HS| − |H|, (2)
where H is the stabilizer of XS. Since X is a cell and HXS = XS, we
have X = HX. Note that, since G is abelian, ({y} ∪ H)S = HS implies
y ∈ Stab(HS) ⊂ Stab(XS), so that y ∈ H. This observation and (2) imply
that H is an u–cell. In particular, by taking X = M , the period K of MS is a
u–cell. Since KMS = MS and M is a u–cell, we have K ⊂ KM ⊂ M . Since
M is a u–kernel we have M = K. This proves (i).
Now let H be the stabilizer of XS, where X is a u–cell. As shown in the
preceding paragraph H is also a u–cell. By Theorem 5 we have M ⊂ H and
thus MH = H. Since X is a cell and HXS = XS, we have X = HX = MHX.
Hence X ⊂ MX ⊂ MHX = X implies X = MX. This proves (ii).
Finally, by (i), a v–kernel N is a subgroup. By Theorem 5 we have N ⊂ M .
From Corollary 6, one can deduce Theorem 1.
Proof of Theorem 1: We may assume without loss of generality that 1 ∈ S.
Case 1: There is no m–cell for any 1 ≤ m ≤ |S| − 2.
• either we have |TS| ≥ |S|+ |T | − 1 for any non-empty finite T , in which
case the theorem clearly holds with H = {1}.
• or there exists some non-empty finite T such that |TS| ≤ |S| + |T | − 2.
Without loss of generality, we may also suppose 1 ∈ T . Now T must be
contained in an m–cell with m ≤ |S| − 2, but since no such cell exists for
1 ≤ m, we have that T itself must be a cell (a 0-cell) i.e. |TS| = |T |. We
therefore have HT = TH = T = TS = HTS where H is the (necessarily
finite) subgroup generated by S. We have just proved that the theorem
holds in this case with H = 〈S〉.
Case 2: There exists an m–cell with 1 ≤ m ≤ |S| − 2. We may therefore
consider the largest integer u ≤ |S| − 2 for which S admits a u–cell. Let H be
the u–kernel containing 1. Note that u ≤ |S|−2 implies that H is different from
{1}. Now let T be any finite non-empty subset such that |TS| − |T | ≤ |S| − 2.
We shall prove that HTS = TS.
By adding elements to T as long as necessary, we can find a cell X that contains
T and such that XS = TS. Note that we then have |XS| − |X| ≤ |TS| − |T | ≤
|S| − 2, so that X is a v–cell for some v ≤ u. By Corollary 6 (ii) we have
TS = XS = MXS = MTS where M is the v-kernel containing 1. By part (i)
of Corollary 6, H is a subgroup of M so that TS = XS = HTS as well.
Finally, |ST | ≤ |HS|+ |HT | − |H| follows from |ST | being a multiple of |H|.
References
[1] E. Balandraud, Une variante de la méthode isopérimetrique de Hamidoune,
appliquée au theoreme de Kneser, Preprint, december 2005.
[2] E. Balandraud, Quelques résultats combinatoires en Théorie Additive des
Nombres, Thèse de Doctorat de l’Université de Bordeaux I, May 2006.
[3] D. Grynkiewicz, A step beyond Kempermann structure Theorem, Preprint
May 2006.
[4] J. H. B. Kemperman, On small sumsets in Abelian groups, Acta Math. 103
(1960), 66–88.
[5] M. Kneser, Summenmengen in lokalkompakten abelesche Gruppen, Math.
Zeit. 66 (1956), 88–110.
[6] H.B. Mann, Addition Theorems, R.E. Krieger, New York, 1976.
[7] M. B. Nathanson, Additive Number Theory. Inverse problems and the ge-
ometry of sumsets, Grad. Texts in Math. 165, Springer, 1996.
[8] J.E. Olson, On the symmetric difference of two sets in a group. European
J. Combin. 7 (1986), no. 1, 43–54.
[9] T. Tao and V.H. Vu, Additive Combinatorics, Cambridge Studies in Ad-
vanced Mathematics 105 (2006), Cambridge University Press.
	Introduction
	An application of Olson's Theorem

  A recent result of Balandraud shows that for every subset S of an abelian
group G, there exists a non trivial subgroup H such that |TS| <= |T|+|S|-2
holds only if the stabilizer of TS contains H. Notice that Kneser's Theorem
says only that the stabilizer of TS must be a non-zero subgroup.
  This strong form of Kneser's theorem follows from some nice properties of a
certain poset investigated by Balandraud. We consider an analogous poset for
nonabelian groups and, by using classical tools from Additive Number Theory,
extend some of the above results. In particular we obtain short proofs of
Balandraud's results in the abelian case.

Introduction
In order to avoid switching from multiplicative to additive notation, all groups
will be written multiplicatively.
Kneser’s addition theorem states that if S, T are finite subsets of an abelian
group G then |ST | ≤ |S| + |T | − 2 holds only if ST is periodic (i.e, there
is a non trivial subgroup H such that HST = ST .) Kneser’s Theorem is a
fundamental tool in Additive number Theory. Proofs of this result may be
found in [4, 5, 6, 7, 9].
In all previously known proofs of Kneser’s Theorem, the subgroup H depends
crucially on both sets S and T . With the goal of breaking this double depen-
dence in S and T , Balandraud investigated in recent work [1, 2] the properties
of a combinatorial poset that we now present.
Let S be a finite subset containing 1 of a group G. Following Balandraud, let
us define a cell of S as a finite subset X such that, for all z /∈ X, it holds that
zS 6⊂ XS. This notion is defined in [1, 2] and it is equivalent to the notion of
Université Pierre et Marie Curie, Paris 6, Combinatoire et Optimisation - case 189, 4
place Jussieu, 75252 Paris Cedex 05. yha@ccr.jussieu.fr
Universitat Politècnica de Catalunya, Matemàtica Aplicada IV, Campus Nord - Edif. C3,
C. Jordi Girona, 1-3, 08034 Barcelona, Spain. oserra@mat.upc.es
Université de Bordeaux 1, Institut de Mathématiques de Bordeaux, 351 cours de la
Libération, 33405 Talence. zemor@math.u-bordeaux1.fr
http://arxiv.org/abs/0704.0382v1
nonextendible subset used in [3]. Throughout the paper, by a cell we always
mean a cell of S.
A cell X is called a u-cell if |XS| − |X| = u. A u-cell with minimal cardinality
is called a u-kernel (of S).
Balandraud showed that, for a finite set S in an abelian group G, in the poset
of j–cells containing the unity ordered by inclusion with 1 ≤ j ≤ |S| − 2, the
set of kernels form a chain of subgroups. Moreover, if there exists a u–cell, then
there is a unique u–kernel containing the unit element which is contained in all
u–cells containing the unit element.
One of the consequences of this work is a new proof and the following strength-
ening of Kneser’s Theorem:
Theorem 1 (Balandraud) For any non-empty finite subset S of an abelian
group G, there exists a finite subgroup H of G such that for any finite subset T
of G one of the following conditions hold :
• |TS| ≥ |T |+ |S| − 1
• HTS = TS and |TS| ≤ |HS|+ |HT | − |H|
As far as the authors are aware this is a surprising and strong formulation that
was not observed before and does not follow straightforwardly from the classical
forms of Kneser’s Theorem.
The purpose of the present note is to give a short proof for the nonabelian
case that, in the poset of j–cells that are subgroups ordered by inclusion with
0 ≤ j ≤ |S| − 1, the set of kernels form a chain of subgroups. Moreover, each
u-kernel of this poset is unique and contained in all u–cells of this poset.
From this statement Kneser’s theorem allows one to deduce Balandraud’s re-
sults for the abelian case, and in particular Theorem 1. Kneser’s Theorem has
several equivalent forms. We use the following one; see e.g [4, 7]:
Theorem 2 (Kneser [5]) Let G be an abelian group and X,Y ⊂ G be finite
subsets such that |XY | ≤ |X| + |Y | − 2. Then
|XY | = |HX|+ |HY | − |H|,
where H = stab(XY ) = {x : xXY = XY }.
Our main tool is the following Theorem of Olson[8, Theorem 2]. We give an
equivalent formulation here where we use left–cosets instead of right–cosets.
Theorem 3 (Olson [8]) Let X,Y be finite subsets of a group G, and let H
and K be subgroups such that HX = X, KY = Y and KX 6= X, HY 6= Y .
|X \ Y |+ |Y \X| ≥ |H|+ |K| − 2|H ∩K|.
In particular either |X \ Y | ≥ |H| − |H ∩K| or |Y \X| ≥ |K| − |H ∩K|.
We shall use the following lemma.
Lemma 4 ([1, 2]) Let G be a group and 1 ∈ S ⊂ G be a finite subset. Then
the intersection of two cells M1,M2 of S is a cell of S.
Proof. Let x /∈ M1 ∩M2. There is i with x /∈ Mi. Then xS 6⊂ MiS. Hence
xS 6⊂ (M1 ∩M2)S.
We can now state our main result, namely Theorem 5 below.
2 An application of Olson’s Theorem
Balandraud [1, 2] proved that, in the abelian case, the set of kernels containing
the unit element and ordered by inclusion is a chain of subgroups. In the non
abelian case we can prove only that the set of kernels that are subgroups forms
a chain. The abelian case can then be easily recovered, since Kneser’s Theorem
implies (as we shall see below) that a kernel containing the unit element is a
subgroup.
Theorem 5 Let S be a finite subset containing 1 of a group G. Let M be a
u–kernel of S which is a subgroup. Let N be a subgroup which is a v–cell and
suppose u, v ≤ |S| − 1.
(i) If either N is a v–kernel or u = v then M ⊂ N or N ⊂ M .
(ii) If N is a v–kernel and v ≤ u then M ⊂ N .
Proof. Suppose that M 6⊂ N and N 6⊂ M . Note that, since M is a cell, if
NMS = MS then NM = M , thus N ⊂ M against our assumption. Hence we
may assume NMS 6= MS and similarly MNS 6= NS. By Theorem 3 we have
one of the two following cases.
Case 1: |MS| − |(MS) ∩ (NS)| = |(MS) \ (NS)| ≥ |M | − |M ∩N |. It follows
that |(M ∩N)S| − |M ∩N | ≤ |(MS)∩ (NS)| − |M ∩N | ≤ |MS| − |M |. On the
other hand we have u = |MS| − |M | < |S| ≤ |(M ∩N)S|. Since |MS| − |M | is
a multiple of |M ∩N | we have
u = |MS| − |M | = |(M ∩N)S| − |M ∩N |.
By Lemma 4, M ∩N is a cell. Since M is a u–kernel, we have M ∩N = M, a
contradiction.
Case 2: |NS| − |(NS) ∩ (MS)| = |(NS) \ (MS)| ≥ |N | − |N ∩M |. It follows
that |(N ∩ M)S| − |N ∩ M | ≤ |(NS) ∩ (MS)| − |N ∩ M | ≤ |NS| − |N |. On
the other hand we have |NS| − |N | < |S| ≤ |(N ∩M)S|. Since |NS| − |N | is a
multiple of |N ∩M | we have
|NS| − |N | = |(N ∩M)S| − |N ∩M |. (1)
Assume first u = v. Then u = |MS|−|M | = |NS|−|N | = |(N∩M)S|−|N∩M |.
Since M is a u–kernel, we have M ∩N = M, a contradiction.
Assume that N is a v–kernel. Then (1) implies N ∩M = N, a contradiction.
This proves (i).
Assume now that v ≤ u. Suppose M 6⊂ N . By (i) we have N ⊂ M , which
implies in particular that |MS| − |M | is a multiple of N . Therefore, from
u = |MS| − |M | < |S| ≤ |NS| we have u = |MS| − |M | ≤ |NS| − |N | = v
which gives u = v. But then M 6⊂ N and N ⊂ M imply |N | < |M |, and since
N is now a u–cell, this contradicts M being a u–kernel.
We can now deduce Balandraud’s description for kernels and cells :
Corollary 6 (Balandraud [1, 2]) Let G be an abelian group and S ⊂ G be
a finite subset with 1 ∈ S. Let M be a u–kernel of S containing 1 with 1 ≤ u ≤
|S| − 2. Then,
(i) M is a subgroup.
(ii) Each u-cell is M–periodic.
(iii) Each v–kernel with u < v ≤ |S| − 2 is a proper subgroup of M .
Proof. Let X be a u-cell with u ≤ |S| − 2. By Kneser’s Theorem, the
inequality |XS| − |X| = u ≤ |S| − 2 implies
u = |XS| − |HX| = |HS| − |H|, (2)
where H is the stabilizer of XS. Since X is a cell and HXS = XS, we
have X = HX. Note that, since G is abelian, ({y} ∪ H)S = HS implies
y ∈ Stab(HS) ⊂ Stab(XS), so that y ∈ H. This observation and (2) imply
that H is an u–cell. In particular, by taking X = M , the period K of MS is a
u–cell. Since KMS = MS and M is a u–cell, we have K ⊂ KM ⊂ M . Since
M is a u–kernel we have M = K. This proves (i).
Now let H be the stabilizer of XS, where X is a u–cell. As shown in the
preceding paragraph H is also a u–cell. By Theorem 5 we have M ⊂ H and
thus MH = H. Since X is a cell and HXS = XS, we have X = HX = MHX.
Hence X ⊂ MX ⊂ MHX = X implies X = MX. This proves (ii).
Finally, by (i), a v–kernel N is a subgroup. By Theorem 5 we have N ⊂ M .
From Corollary 6, one can deduce Theorem 1.
Proof of Theorem 1: We may assume without loss of generality that 1 ∈ S.
Case 1: There is no m–cell for any 1 ≤ m ≤ |S| − 2.
• either we have |TS| ≥ |S|+ |T | − 1 for any non-empty finite T , in which
case the theorem clearly holds with H = {1}.
• or there exists some non-empty finite T such that |TS| ≤ |S| + |T | − 2.
Without loss of generality, we may also suppose 1 ∈ T . Now T must be
contained in an m–cell with m ≤ |S| − 2, but since no such cell exists for
1 ≤ m, we have that T itself must be a cell (a 0-cell) i.e. |TS| = |T |. We
therefore have HT = TH = T = TS = HTS where H is the (necessarily
finite) subgroup generated by S. We have just proved that the theorem
holds in this case with H = 〈S〉.
Case 2: There exists an m–cell with 1 ≤ m ≤ |S| − 2. We may therefore
consider the largest integer u ≤ |S| − 2 for which S admits a u–cell. Let H be
the u–kernel containing 1. Note that u ≤ |S|−2 implies that H is different from
{1}. Now let T be any finite non-empty subset such that |TS| − |T | ≤ |S| − 2.
We shall prove that HTS = TS.
By adding elements to T as long as necessary, we can find a cell X that contains
T and such that XS = TS. Note that we then have |XS| − |X| ≤ |TS| − |T | ≤
|S| − 2, so that X is a v–cell for some v ≤ u. By Corollary 6 (ii) we have
TS = XS = MXS = MTS where M is the v-kernel containing 1. By part (i)
of Corollary 6, H is a subgroup of M so that TS = XS = HTS as well.
Finally, |ST | ≤ |HS|+ |HT | − |H| follows from |ST | being a multiple of |H|.
References
[1] E. Balandraud, Une variante de la méthode isopérimetrique de Hamidoune,
appliquée au theoreme de Kneser, Preprint, december 2005.
[2] E. Balandraud, Quelques résultats combinatoires en Théorie Additive des
Nombres, Thèse de Doctorat de l’Université de Bordeaux I, May 2006.
[3] D. Grynkiewicz, A step beyond Kempermann structure Theorem, Preprint
May 2006.
[4] J. H. B. Kemperman, On small sumsets in Abelian groups, Acta Math. 103
(1960), 66–88.
[5] M. Kneser, Summenmengen in lokalkompakten abelesche Gruppen, Math.
Zeit. 66 (1956), 88–110.
[6] H.B. Mann, Addition Theorems, R.E. Krieger, New York, 1976.
[7] M. B. Nathanson, Additive Number Theory. Inverse problems and the ge-
ometry of sumsets, Grad. Texts in Math. 165, Springer, 1996.
[8] J.E. Olson, On the symmetric difference of two sets in a group. European
J. Combin. 7 (1986), no. 1, 43–54.
[9] T. Tao and V.H. Vu, Additive Combinatorics, Cambridge Studies in Ad-
vanced Mathematics 105 (2006), Cambridge University Press.
	Introduction
	An application of Olson's Theorem
