Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Hsien-Chih Chang 張顯之 Oct 31 '10 at 7:30
    
You are considering only Abelian groups? –  Mark Sapir Oct 31 '10 at 12:56
    
When dealing with Davenport number, one usually considers Abelian groups. But I'm also interested in non-Abelian ones. –  Hsien-Chih Chang 張顯之 Nov 1 '10 at 2:17
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  Alex B. Oct 31 '10 at 15:52
1  
@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$. –  Mark Sapir Oct 31 '10 at 18:06
    
Yes, the fix was easy enough. Nice answer! –  Alex B. Nov 1 '10 at 0:10
    
Nice answer indeed. Thanks!! –  Hsien-Chih Chang 張顯之 Nov 1 '10 at 2:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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