The ACO Seminar (2010-2011)

A well know result is a Theorem attributed jointly to Cauchy and Davenport that given two nonempty subsets A and B of Z/pZ, the sumset A+B is no smaller than the minimum of |A|+|B|-1 and p. Here A+B := {a+b | a in A and b in B}. Paul Erdos and Hans Heilbronn conjectured that if we restrict the operation to distinct elements, namely we consider the set {a+b | a in A and b in B, a not equal to b}, then the bound changes to he minimum of |A|+|B|-3 and p. What is interesting is that the Cauchy-Davenport Theorem was proven immediately, but the conjecture of Erdos and Heilbronn was open for more than 30 years. We present the proof of the conjecture due to Noga Alon, Melvyn Nathanson, and Imre Ruzsa [1995]. Their technique is known as the Polynomial Method and is regarded by many to be a powerful tool in Additive Combinatorics.