## DIMACS TR: 94-02

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

### Author: Melvyn B. Nathanson

**
ABSTRACT
**

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