DIMACS TR: 94-02

Ballot numbers, alternating products, and the Erdos-Heilbronn conjecture

Author: Melvyn B. Nathanson


Erd\H os and Heilbronn conjectured that if $A$ is a set of $k$ congruence classes modulo a prime $p$, then there are at least $\min(p, 2k-3)$ congruence classes that can be written as the sum of two distinct elements of $A$. This conjecture was recently proved by Dias da Silva and Hamidoune, using linear algebra and the representation theory of the symmetic groups. The representation theory can be eliminated by using classical combinatorial ballot numbers. The purpose of this paper is to give a complete exposition of this simplified proof of the Erd\H os-Heilbronn conjecture.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-02.ps
DIMACS Home Page