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?

  • $\begingroup$ Sorry, what's $d$ here? $\endgroup$ – Harry Altman Dec 15 '10 at 8:09
  • $\begingroup$ Oh, I see, presumably it's $p$. $\endgroup$ – Harry Altman Dec 15 '10 at 8:10
  • $\begingroup$ oops, they should be p. I'll edit the question. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Oh, so the GEH for cyclic group HAS to be weaken... Thank you for the nice example! Any idea on the weaker results? $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 15 '10 at 9:46
  • $\begingroup$ @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! $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 15 '10 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.