Adding Distinct Congruence Classes Modulo a Prime

The Cauchy-Davenport theorem states that if A and B are nonempty sets of congruence classes modulo a prime p, and if |A| = k and |B| = l, then the sumset A + B contains at least min(p, k + l − 1) congruence classes. It follows that the sumset 2A contains at least min(p, 2k − 1) congruence classes. Erdős and Heilbronn conjectured 30 years ago that there are at least min(p, 2k − 3) congruence classes that can be written as the sum of two distinct elements of A. Erdős has frequently mentioned this problem in his lectures and papers (for example, Erdős-Graham [4, p. 95]). The conjecture was recently proven by Dias da Silva and Hamidoune [3], using linear algebra and the representation theory of the symmetric group. The purpose of this paper is to give a simple proof of the Erdős-Heilbronn conjecture that uses only the most elementary properties of polynomials. The method, in fact, yields generalizations of both the Erdős-Heilbronn conjecture and the Cauchy-Davenport theorem.