On complete subsets of the cyclic group
On complete subsets of the cyclic group
Y. O. Hamidoune
A.S. Lladó
O. Serra
Abstract
A subset X of an abelian G is said to be complete if every element of the subgroup
generated by X can be expressed as a nonempty sum of distinct elements from X .
Let A ⊂ Z
be such that all the elements of A are coprime with n. Solving a conjecture
of Erdős and Heilbronn, Olson proved that A is complete if n is a prime and if |A| > 2
Recently Vu proved that there is an absolute constant c, such that for an arbitrary large n,
A is complete if |A| ≥ c
n, and conjectured that 2 is essentially the right value of c.
We show that A is complete if |A| > 1 + 2
n− 4, thus proving the last conjecture.
1 Introduction
The additive group of integers modulo n will be denoted by Zn.
Let G be a finite Abelian group and let X ⊂ G. The subgroup generated by a subset X of G
will be denoted 〈X〉. For a positive integer k, we shall write
k ∧X =
A ⊂ X and |A| = k
Following the terminology of [12] we write
k ∧X.
The set X is said to be complete if SX = 〈X〉. The reader may find the connection between this
notion and the corresponding notion for integers in [12]. We shall also write
S0X = SX ∪ {0}.
Note that S0X =
x∈X{0, x}.
Université Pierre et Marie Curie, E. Combinatoire, Case 189, 4 Place Jussieu, 75005 Paris, France.
yha@ccr.jussieu.fr
Universitat Politècnica de Catalunya, Dept. Matemàtica Apl. IV; Jordi Girona, 1, E-08034 Barcelona, Spain.
allado@ma4.upc.edu
Universitat Politècnica de Catalunya, Dept. Matemàtica Apl. IV; Jordi Girona, 1, E-08034 Barcelona, Spain.
oserra@ma4.upc.edu
http://arxiv.org/abs/0704.0541v1
Let p denote a prime number and let A ⊂ Zp \ {0}. Erdős and Heilbronn [4] showed that A is
complete if |A| ≥
p, and conjectured that
18 can be replaced by 2. This conjecture was
proved by Olson[8]. More precisely, Olson’s Theorem states that A is complete if |A| ≥
4p− 4.
This result was sharpened by Dias da Silva and one of the authors [1] by showing that |k∧A| = p,
if |A| ≥
4p − 4, where k = ⌈
p− 1 ⌉. They also showed that |(j ∧ A) ∪ ((j + 1) ∧A)| = p, if
|A| ≥
4p− 8, where j = ⌈
p− 2 ⌉.
Let G be a finite abelian group and let A ⊂ G\{0}. Complete sets for general abelian group were
investigated by Diderrich and Mann [3]. Diderrich [2] proved that, if |G| = pq is the product of
two primes, then A is complete if |A| ≥ p+ q − 1.
Let p be the smallest prime dividing |G|. Diderrich conjectured [2] that A is complete, if |G|/p
is composite and |A| = p+ |G|/p− 2. This conjecture was finally proved by Gao and one of the
authors [5]. More precise results were later proved by Gao and the present authors [6]. Note
that the bound of Diderrich is best possible, since one may construct non complete sets of size
p+ |G|/p − 3.
However the result of Olson was extended recently by Vu [13] to general cyclic groups. Let
A ⊂ Zn be such that all the elements of A are coprime with n. Vu proved that there is an
absolute constant c such that, for an arbitrary large n, A is complete if |A| ≥ c
n. The proof of
Vu is rather short and depends on a recent result of Szemerédi and Vu [11]. In the same paper
Vu conjectures that the constant is essentially 2.
Our main result is the following:
Theorem 1.1 Let A be a subset of Zn be such that all the elements of A are coprime with n.
If |A| > 1 + 2
n− 4 then A is complete.
This result implies the validity of the last conjecture of Vu. We conjecture the following:
Conjecture 1.2 Let A ⊂ Zn be such that all the elements of A are coprime with n and |A| ≥√
4n− 4. Then |k ∧A| = n, where k = ⌈
n− 1 ⌉.
2 Some tools
In this section we present known material and some easy applications of it. We give short proofs
in order to make the paper self-contained.
Recall the following well-known and easy lemma.
Lemma 2.1 Let G be a finite group. Let X and Y be subsets of G such that X + Y 6= G. Then
|X|+ |Y | ≤ |G|.
Proof. Take a ∈ G \ (X + Y ). We have (a− Y ) ∩X = ∅. ✷
We use also the Chowla’s Theorem [7, 10] :
Theorem 2.2 (Chowla [7, 10]) Let n be a positive integer and let X and Y be non-empty
subsets of Zn. Assume that 0 ∈ Y and that the elements of Y \ {0} are coprime with n. Then
|X + Y | ≥ min(n, |X| + |Y | − 1).
Proof. The proof is by induction on |Y |, the result being obvious for |Y | = 1. Assume first
that Y ⊂ X − x, for all x ∈ X. Then X + Y ⊂ X, and hence X + Y = X. It follows that
X + Y = X + nY = Zn.
Assume now that Y 6⊂ X − x, for some x ∈ X. Then 0 ∈ Y ∩ (X − x) and |Y ∩ (X − x)| < |Y |.
By the induction hypothesis, |X|+ |Y | − 1 ≤ |((X − x) ∪ Y ) + ((X − x) ∩ Y )| ≤ |(X − x) + Y |.
Let B ⊂ G and x ∈ G. Following Olson, we write
λB(x) = |(B + x) \B|.
The following result is implicit in [8]:
Lemma 2.3 (Olson, [8]) Let Y be a nonempty subset of G \ {0}, z /∈ Y and y ∈ Y . Put
B = S0Y . Then
|B| ≥ |S0Y \{y}|+ λB(y), (1)
|S0Y ∪{z}| = |S
Y |+ λB(z). (2)
Proof. Clearly we have B∩(B−y) ⊂ B\S0
Y \{y}
and hence λB(y) = |B∩(B−y)| ≤ |B|−|S0Y \{y}|.
¿From S0
Y ∪{z}
= B + {0, z} we have |S0
Y ∪{z}
| = |B|+ |(B + z) \B|} = |B|+ λB(z). ✷
We need the following helpful result also due to Olson:
Lemma 2.4 (Olson [8]) Let B and C be nonempty subsets of an abelian group G such that
0 6∈ C. Then,
λB(x) = λB(−x). (3)
λB(x+ y) ≤ λB(x) + λB(y). (4)
λB(x) ≥ |B|(|C| − |B|+ 1). (5)
Proof. For each x ∈ G we have
|(B + x) ∩B| = |B + x| − |(B + x) ∩B|
= |B − x| − |B ∩ (B − x)|
= |B ∩ (B − x)| = λB(−x),
proving (3). Let x, y ∈ G. Then,
λB(x+ y) = |(B + x+ y) ∩B|
= |(B + x) ∩ (B − y)|
= |(B + x) ∩B ∩ (B − y)|+ |(B + x) ∩B ∩ (B − y)|
≤ |(B + x) ∩B|+ |B ∩ (B − y)|
= λB(x) + λB(y),
proving (4). Finally,
λB(x) ≥
(|B + x| − |B ∩ (B + x)|)
≥ |C||B| −
|B ∩ (B + x)|
≥ |C||B| −
x∈G\0
|B ∩ (B + x)|
= |B|(|C| − |B|+ 1),
proving (5). ✷
3 The main result
The next Lemma is the key tool for our main result.
Lemma 3.1 Let A and B be nonempty subsets of Zn. Assume that A ∩ (−A) = ∅ and that
each element in A is coprime with n. Put a = |A| and b = |B|. Assume also that a ≥ 3 and
2b ≤ n+ 2. Then
λB(x) > a−
a(a− 3)
. (6)
In particular, if 2b ≥ a(a− 3), then
λB(x) ≥ a− 1. (7)
Proof. Put A∗ = A ∪ (−A) ∪ {0}. Let t < n be a positive integer and set
t = 2ma+ r, m ≥ 0, 0 ≤ r ≤ 2a− 1.
Let Cj = jA
∗. By Chowla’s theorem, |Cj| ≥ min{n, 2ja + 1} = 2ja + 1, for j ≤ m. Therefore
we can choose a set C ⊃ A∗ of cardinality t + 1 which intersects Cj in exactly 2ja elements
j = 2, . . . ,m, and intersects Cm+1 in exactly r elements. Let E = C \{0}. Let α = max{λB(x) :
x ∈ A}. By (3) we have λB(x) ≤ α, for all x ∈ A∗. For an element x in Cj there are elements
x1, · · · , xj ∈ A∗ such that x = x1+ · · ·+xj. In view of (4) we have λB(x) ≤ λ(x1)+ · · ·+λ(xj) ≤
jα. Therefore,
λB(x) ≤ α2a+ 2α2a + · · ·+mα2a+ r(m+ 1)α
= α(m+ 1)(ma+ r) =
α(t− r + 2a)(t+ r)
≤ α(t+ a)
By using (5) we have
x∈E λB(x)
(t+ a)2
≥ 4ab(t− b+ 1)
(t+ a)2
In particular, since 2b ≤ n+ 2, we can set t = 2b− 3 to get,
α ≥ 4ab(b− 2)
(2b+ a− 3)2
≥ a(b− 2)
(1− a− 3
> a− a(a− 3)
where we have used a ≥ 3. In particular, if 2b ≥ a(a − 3), then α > a − 2 so that α ≥ a − 1.
This completes the proof. ✷
Lemma 3.1 gives the following estimation for the cardinality of the set of subset sums.
Lemma 3.2 Let A ⊂ Zn such that A ∩ (−A) = ∅ and every element of A is coprime with n.
Also assume |A| ≥ 2. Then
|S0A| ≥ min{
n + 2
, 3 +
|A|(|A| − 1)
Proof. We shall prove the result by induction on a = |A|, the result being obvious for a = 2.
Suppose a > 2. Put B = S0A. We may assume b = |B| ≤ n2 + 1 so that 2b ≤ n + 2. By the
induction hypothesis, 2b ≥ 6 + (a− 1)(a− 2) > a(a− 3).
By (7) there is an x ∈ A with λB(x) ≥ a− 1. Then, by Lemma 2.3,
|B| ≥ |S0A\{x}|+ λB(x) ≥ 3 + (a− 2)(a − 1)/2 + a− 1 = 3 +
a(a− 1)
as claimed. ✷
We are now ready for the proof of Theorem 1.1.
Proof of Theorem 1.1. Suppose A non complete and put |A| = k. Let X,Y be disjoint subsets
of A. We clearly have SX + S
Y ⊂ SA 6= Zn. Since |SX | ≥ |S0X | − 1, we have
|S0X |+ |S0Y | ≤ n+ 1, (8)
by Lemma 2.1.
Partition A = A1 ∪ A2 into two almost equal parts, i.e. |A1| = ⌈k/2⌉ and |A2| = ⌊k/2⌋, such
that Ai ∩ (−Ai) = ∅, i = 1, 2.
We must have
3 + ⌊k
⌋ − 1)/2 < (n+ 2)/2, (9)
since otherwise, by Lemma 3.2, we have |S0A1 |+ |S
| ≥ n+ 2, contradicting (8).
Case 1. k even.
Then we have by (9)
n/2 > 2 +
− 1)/2 = 2 + k(k − 2)/8,
and hence (k − 1)2 + 16 ≤ 4n, a contradiction.
Case 2. k odd.
Put a = k−1
. In view of (9), Lemma 3.2 implies
|S0A2 | ≥ 3 + a(a− 1)/2.
By (7) with B = S0A2 , there is a y ∈ A1 such that
λB(y) ≥ a− 1.
Put C1 = A1 \ {y} and C2 = A2 ∪ {y}. Then we have, by Lemma 2.3,
|S0C2 | ≥ |S
|+ λB(y) ≥ 3 + a(a− 1)/2 + a− 1 = 2 +
a(a+ 1)
On the other hand, from (9) and Lemma 3.2 we get
|S0C1 | ≥ 3 +
a(a− 1)
By (8),
n+ 1 ≥ |S0C1 |+ |S
| ≥ 3 + a(a− 1)/2 + 2 + a(a+ 1)/2 = 5 + a2.
Therefore 4n ≥ 16 + 4a2 = 16 + (k − 1)2, a contradiction. This completes the proof. ✷
References
[1] J.A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and
additive theory, Bull. London Math. Soc., 26 (1994), 140-146.
[2] G.T. Diderrich, An addition theorem for abelian groups of order pq, J. Number Theory 7
(1975), 33-48.
[3] G. T. Diderrich and H. B. Mann, Combinatorial problems in finite abelian groups, In: ”A
survey of Combinatorial Theory” (J.L. Srivasta et al. Eds.), pp. 95- 100, North- Holland,
Amsterdam (1973).
[4] P. Erdős and H. Heilbronn, On the Addition of residue classes mod p, Acta Arith. 9 (1964),
149-159.
[5] W. Gao and Y.O. Hamidoune, On additive bases, Acta Arith. 88 (1999), 3, 233-237.
[6] W. Gao, Y.O. Hamidoune A. S. Lladó and O. Serra, Covering a finite abelian group by
subset sums. Combinatorica 23 (2003), no. 4, 599–611.
[7] H.B. Mann, Addition Theorems, R.E. Krieger, New York, 1976.
[8] J. E. Olson, An addition theorem mod p, J. Comb. Theory 5 (1968), 45-52.
[9] S. Chowla, A theorem on the addition of residue classes: applications to the number Γ(k)
in Waring’s problem, Proc.Indian Acad. Sc. 2 (1935) 242–243.
[10] M. B. Nathanson, Additive Number Theory. Inverse problems and the geometry of sumsets,
Grad. Texts in Math. 165, Springer, 1996.
[11] E. Szemerédi and V.H. Vu, Long arithmetic progressions in finite and infinite sets, Annals
of Math., to appear.
[12] T. Tao and V.H. Vu, Additive Combinatorics, Cambridge Studies in Advanced Mathematics
105 (2006), Cambridge Press University.
[13] V.H. Vu, Olson Theorem for cyclic groups, Preprint, arXiv:math.NT/0506483 v1, 23 june
2005.
http://arxiv.org/abs/math/0506483
	Introduction
	Some tools
	The main result
