Adding Distinct Congruence Classes Modulo a Prime

Abstract

The Erdős-Heilbronn conjectureThe 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. The polynomial methodLemma 1 (Alon-Tarsi [2]) Let A and B be nonempty subsets of a field F with |A| = k and |B| = l.Let f (x, y) be a polynomial with coefficients in F and

Locations

• American Mathematical Monthly - View
• CiteSeer X (The Pennsylvania State University) - View - PDF