5Sum sets
III Combinatorics
5 Sum sets
Let G be an abelian group, and A, B ⊆ G. Define
A + B = {a + b : a ∈ A, b ∈ B}.
For example, suppose
G
=
R
and
A
=
{a
1
< a
2
< ··· < a
n
}
and
B
=
{b
1
<
b
2
< ··· < b
m
}
. Surely,
A
+
B ≤ nm
, and this bound can be achieved. Can we
bound it from below? The elements
a
1
+ b
1
, a
1
+ b
2
, . . . , a
1
+ b
m
, a
2
+ b
m
, . . . , a
n
+ b
m
are certainly distinct as well, since they are in strictly increasing order. So
|A + B| ≥ m + n − 1 = |A| + |B|−1.
What if we are working in a finite group? In general, we don’t have an order, so
we can’t make the same argument. Indeed, the same inequality cannot always
be true, since
|G
+
G|
=
|G|
. Slightly more generally, if
H
is a subgroup of
G
,
then |H + H| = |H|.
So let’s look at a group with no subgroups. In other words, pick G = Z
p
.
Theorem
(Cauchy–Davenport theorem)
.
Let
A
and
B
be non-empty subsets
of Z
p
with p a prime, and |A| + |B| ≤ p + 1. Then
|A + B| ≥ |A| + |B|−1.
Proof.
We may assume 1
≤ |A| ≤ |B|
. Apply induction on
|A|
. If
|A|
= 1, then
there is nothing to do. So assume A ≥ 2.
Since everything is invariant under translation, we may assume 0
, a ∈ A
with
a 6
= 0. Then
{a,
2
a, . . . , pa}
=
Z
p
. So there exists
k ≥
0 such that
ka ∈ B
and
(k + 1)a 6∈ B.
By translating B, we may assume 0 ∈ B and a 6∈ B.
Now 0 ∈ A ∩ B, while a ∈ A \ B. Therefore we have
1 ≤ |A ∩ B| < |A|.
Hence
|(A ∩ B) + (A ∪ B)| ≥ |A ∩ B|+ |A ∪B| − 1 = |A| + |B|−1.
Also, clearly
(A ∩ B) + (A ∪ B) ⊆ A + B.
So we are done.
Corollary. Let A
1
, . . . , A
k
be non-empty subsets of Z
p
such that
d
X
i=1
|A
i
| ≤ p + k −1.
Then
|A
1
+ . . . + A
k
| ≥
k
X
i=1
|A
i
| − k + 1.
What if we don’t take sets, but sequences? Let
a
1
, . . . , a
m
∈ Z
n
. What
m
do we need to take to guarantee that there are
m
elements that sums to 0? By
the pigeonhole principle, m ≥ n suffices. Indeed, consider the sequence
a
1
, a
1
+ a
2
, a
1
+ a
2
+ a
3
, ··· , a
1
+ ··· + a
n
.
If they are all distinct, then one of them must be zero, and so we are done. If
they are not distinct, then by the pigeonhole principle, there must be
k < k
0
such that
a
1
+ ··· + a
k
= a
1
+ ··· + a
k
0
.
So it follows that
a
k+1
+ ··· + a
k
0
.
So in fact we can even require the elements we sum over to be consecutive. On
the other hand, m ≥ n is also necessary, since we can take a
i
= 1 for all i.
We can tackle a harder question, where we require that the sum of a fixed
number of things vanishes.
Theorem
(Erd¨os–Ginzburg–Ziv)
.
Let
a
1
, . . . , a
2n−1
∈ Z
n
. Then there exists
I ∈ [2n − 1]
(n)
such that
X
i∈I
a
i
= 0
in Z
n
.
Proof. First consider the case n = p is a prime. Write
0 ≤ a
1
≤ a
2
≤ ··· ≤ a
2p−1
< p.
If
a
i
=
a
i+p−1
, then there are
p
terms that are the same, and so we are done
by adding them up. Otherwise, set
A
i
=
{a
i
, a
i+p−1
}
for
i
= 1
, . . . , p −
1, and
A
p
= {a
2p−1
}, then |A
i
| = 2 for i = 1, . . . , p − 1 and |A
p
| = 1. Hence we know
|A
1
+ ··· + A
p
| ≥ (2(p − 1) + 1) − p + 1 = p.
Thus, every element in
Z
p
is a sum of some
p
of our terms, and in particular 0 is.
In general, suppose
n
is not a prime. Write
n
=
pm
, where
p
is a prime and
m >
1. By induction, for every 2
m −
1 terms, we can find
m
terms whose sum
is a multiple of m.
Select disjoint S
1
, S
2
, . . . , S
2p−1
∈ [2n − 1]
(m)
such that
X
j∈S
i
a
j
= mb
i
.
This can be done because after selecting, say, S
1
, . . . , S
2p−2
, we have
(2n − 1) − (2p − 2)m = 2m − 1
elements left, and so we can pick the next one.
We are essentially done, because we can pick
j
1
, . . . , j
p
such that
P
p
k=1
b
i
k
is
a multiple of p. Then
p
X
k=1
X
j∈S
i
k
a
j
is a sum of mp = n terms whose sum is a multiple of mp.