Welcome to MathOverflow

Question

4

3

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.

edited Oct 31 2010 at 7:38

asked Oct 31 2010 at 6:57

Hsien-Chih Chang
764●1●8●13

	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 2010 at 7:30
	You are considering only Abelian groups? – Mark Sapir Oct 31 2010 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 2010 at 2:17

Mark Sapir · Accepted Answer · 2010-10-31 18:02:26Z UTC

3

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.

edited Oct 31 2010 at 18:02

answered Oct 31 2010 at 14:11

Mark Sapir
27.6k●2●57●118

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 Bartel Oct 31 2010 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 2010 at 18:06

Yes, the fix was easy enough. Nice answer! – Alex Bartel Nov 1 2010 at 0:10

Nice answer indeed. Thanks!! – Hsien-Chih Chang Nov 1 2010 at 2:16

Upper bound for size of subsets of a finite group that contains a sum-full set

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Problem

Motivation

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.