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
2n1
Z
n
. Then there exists
I [2n 1]
(n)
such that
X
iI
a
i
= 0
in Z
n
.
Proof. First consider the case n = p is a prime. Write
0 a
1
a
2
··· a
2p1
< p.
If
a
i
=
a
i+p1
, 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+p1
}
for
i
= 1
, . . . , p
1, and
A
p
= {a
2p1
}, 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
2p1
[2n 1]
(m)
such that
X
jS
i
a
j
= mb
i
.
This can be done because after selecting, say, S
1
, . . . , S
2p2
, 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
jS
i
k
a
j
is a sum of mp = n terms whose sum is a multiple of mp.