5
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Sorry, what's $d$ here? $\endgroup$ Dec 15, 2010 at 8:09
  • $\begingroup$ Oh, I see, presumably it's $p$. $\endgroup$ Dec 15, 2010 at 8:10
  • $\begingroup$ oops, they should be p. I'll edit the question. $\endgroup$ Dec 15, 2010 at 8:11

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\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$ Dec 15, 2010 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$ Dec 15, 2010 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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