7
$\begingroup$

Problem

I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:

Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we define $k(G)$ be the minimum $k$ such that every subset $X \in \mathcal F_k$ contains a non-empty sum-full set $S$, which is a set satisfies $$ S \subseteq S+S := \{ x+y \mid x,y \in S \}. $$

Note that the inequality $k(G) \leq |G|$ holds trivially since there is only one subset in $\mathcal F_{|G|}$ which is $G$ itself, and $G$ is a semigroup indeed.

Are there any papers or references about this number $k(G)$? Does it have a name? I'm interesting in particularly upper bounds of $k(G)$, but any related results are fine.


Motivation

The restricted Davenport number $\hat{D}(G)$ of a group $G$, is defined as the smallest number $d$ such that given a subset $A \in \mathcal F_d$, there exists a zero-sum non-empty subset $S \subseteq A$, that is,

$$ \sum_{x \in S} x = 0, $$

where $0$ is the identity in $G$. In the paper "On a conjecture of Erdos and Heilbronn", Szemeredi has proved:

$$\hat{D}(G) = O(\sqrt{|G|}). $$

Hamidoune and Zemor set a precise bound $\sqrt{2}$ on the constant of the big-O notation.

I'm trying to provide a link between $\hat{D}(G)$ and the number $k(G)$; it seems to me that the size of sum-full sets in $G$ may related to the zero-sum problem. I'll provide the justification in another post, which is highly related.

$\endgroup$
3
  • $\begingroup$ Oops, I messed up with the definition of a semigroup. What I'm looking for is a sum-full set $A \subseteq A+A$, where a semigroup is a set with $A+A \subseteq A$. I'll modify the question. $\endgroup$ Oct 31, 2010 at 7:30
  • $\begingroup$ You are considering only Abelian groups? $\endgroup$
    – user6976
    Oct 31, 2010 at 12:56
  • $\begingroup$ When dealing with Davenport number, one usually considers Abelian groups. But I'm also interested in non-Abelian ones. $\endgroup$ Nov 1, 2010 at 2:17

1 Answer 1

4
$\begingroup$

First of all the $k(G)$ cannot be smaller than the size of any proper subgroup of $G$, because if $H$ is a proper subgroup, $gH$ is a coset, $g\not\in H$, then $gHgH$ does not intersect $gH$ (if $ghgh'=gh''$, then $g\in H$). For example, if $G$ is Abelian, $|G|$ is not prime (i.e. $G$ is not cyclic of prime order), then $k(G)>\sqrt{|G|}$: look at the size of a maximal proper subgroup.

$\endgroup$
3
  • $\begingroup$ Mark, the question asks that each set of size $k$ should contain a sum-full set. It does not demand that any set of size $k$ should be sum-full itself. Am I completely misunderstanding your answer? $\endgroup$
    – Alex B.
    Oct 31, 2010 at 15:52
  • 2
    $\begingroup$ @Alex: I corrected my answer. The coset $gH$ cannot contain a non-empty subset $X$ with $X\subseteq XX$. This is not a complete answer because I did not treat the case when $|G|$ is prime $\gt 3$, for example. But in that case $G=\langle a\rangle$, and one can take the set of all odd powers $\le |G|/2$. This subset does not contain any subset $X$ with $X\subseteq XX$. So in this case $k$ cannot be smaller than $|G|/4$. $\endgroup$
    – user6976
    Oct 31, 2010 at 18:06
  • $\begingroup$ Yes, the fix was easy enough. Nice answer! $\endgroup$
    – Alex B.
    Nov 1, 2010 at 0:10

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.