Erdös-Heilbronn problem

(Redirected from Erdös–Heilbronn problem)

Let $G$ be an Abelian group and let $A \subset G$. For $k \in \mathbf N$, let

$$k \wedge A = \left \{ {\sum _ {x \in X } x } : {X \subset A \textrm{ and } \left | X \right | = k } \right \} .$$

(Here, $| A |$ denotes the cardinality of a set $A$.) Let $p$ be a prime number and let $A \subset \mathbf Z/p \mathbf Z$. It was conjectured by P. Erdös and H. Heilbronn that $| {2 \wedge A } | \geq \min ( p,2 | A | - 3 )$.

This conjecture, mentioned in [a5], was first proved in [a3], using linear algebra. As a consequence of the lower bound on the degree of the minimal polynomial of the Grasmann derivative, the following theorem is true [a3]: Let $p$ be a prime number and let $A \subset \mathbf Z/ {p \mathbf Z }$. Then

$$\left | {k \wedge A } \right | \geq \min ( p,k ( \left | A \right | - k ) + 1 ) .$$

Applying this theorem with $k = 2$, one obtains the Erdös–Heilbronn conjecture mentioned above. A generalization of the theorem has been obtained in [a2]. Presently (1996), almost nothing is known for composite numbers. The following conjecture is proposed here: Let $n$ be a composite number (cf. also Prime number) and let $A \subset \mathbf Z/ {n \mathbf Z }$ be such that $| A | \geq k - 1 + { {( n - 1 ) } / k }$. Then $0 \in j \wedge A$ for some $1 \leq j \leq k$.

For a prime number $n$, the above conjecture is an easy consequence of the theorem above. Some applications to integer subset sums are contained in [a6]. Along the same lines, the conjecture has several implications. In particular, for $k = 3$ one finds: Let $A \subset \{ 1 \dots n \}$ be such that $| A | \geq 5 + { {( n - 1 ) } / 3 }$. Then there is a $B \subset A$ such that $3 \leq | B | \leq 6$ and $\sum _ {x \in B } x = 2n$.

This was conjectured partially by Erdös and R. Graham [a5] and follows easily by applying the conjecture twice, after adding $0$.

How to Cite This Entry:
Erdös–Heilbronn problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Erd%C3%B6s%E2%80%93Heilbronn_problem&oldid=38691