Jan. 20 3:30pm, Wean 8220

Jeff Wheeler, University of Pittsburgh

A Proof of the Erdos-Heilbronn Problem using the Polynomial Method of Alon, Nathanson, and Rusza

Jeff Wheeler, University of Pittsburgh

A Proof of the Erdos-Heilbronn Problem using the Polynomial Method of Alon, Nathanson, and Rusza

Abstract:

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.