# Is the generalized Erdős–Heilbronn problem true for finite cyclic groups?

The generalized Erdős–Heilbronn (GEH) theorem, which is proved by da Silva and Hamidoune in 1994, states that:

Theorem. If p is a prime and $X$ is a subset of $\mathbb{Z}_p$, then $|\hat{k}X| \geq \min \lbrace k|X|-k^2+1 , p \rbrace$ for $\hat{k}X = \lbrace x_1+\ldots+x_k \mid x_i \in X , x_i \neq x_j \rbrace$.

Also, for the case that $k=2$ (which is called the Erdős–Heilbronn problem), the above statement holds for $X$ as a subset of any finite group $G$; the result is proved by Balister and Wheeler in 2009.

Problem 1. Is the generalized Erdős–Heilbronn problem also true for any finite groups? In particular, is it true for finite cyclic groups?

This question is inspired by the construction of a counter-example to some variants of Ramsey theorem. In the construction we may not need the full strength of the GEH, so a related question is:

Problem 2. Is there any weaker results to the GEH, which have already been proved?

• Sorry, what's $d$ here? – Harry Altman Dec 15 '10 at 8:09
• Oh, I see, presumably it's $p$. – Harry Altman Dec 15 '10 at 8:10
• oops, they should be p. I'll edit the question. – Hsien-Chih Chang 張顯之 Dec 15 '10 at 8:11

Arithmetic progressions usually give small sumsets so...How about $X=\lbrace 0,3,6,9,12 \rbrace \subset \mathbb{Z}_{15}$? Then for $k=2,3,4$ one has $\hat{k}X=X$. That is ok for $k=4$ but not for $k=2,3$. (Doesn't that contradict what you said about $k=2$?)
In fact $X=\lbrace 0,d,2d,\cdots,nd\rbrace \subset \mathbb{Z}_{nd+d}$ for $n \ge 5$ is always a counter-example for $k=3$.
The same type of examples should work as well for larger $k$ and should also work with a few elements removed.
later One can't hope for better than $|\hat{k}X| \geq \min \lbrace k|X|-k^2+1 , |H| \rbrace$ where $H$ is the subgroup generated by $X$. After all, $\hat{k}X \subset H$. I don't know if that is true though. A weaker claim, which seems somewhat more likely, is to replace $|H|$ by the size of the smallest subgroup of size at least $|X|$. I have not read the Balister and Wheeler paper you mention but it seems (from the review posted) to replace $|H|$ with the size of the smallest non-trivial subgroup, which would be prime of cyclic order.
• @Aaron: For the case of $k=2$, we have to replace $p$ with the smallest prime divided $n$, as you mentioned in the edited part. And this is indeed a great answer, many thanks for your thoughtful observations and ideas! – Hsien-Chih Chang 張顯之 Dec 15 '10 at 18:36