6
$\begingroup$

The Davenport constant $D(G)$ of a finite abelian group $G$ is the minimum integer $n$ such that whenever $a_1, \ldots, a_n \in G$ (not necessarily distinct), there is a non-empty $I \subseteq [n]$ such that $\sum_{i \in I} a_i = 0$.

I wonder what happens when we cannot just add the entries up:

Given a finite ground-set, say $[n]$, and a union-closed family $\mathcal{A}$ of (non-empty) subsets of $[n]$, let's say $\mathcal{A}$ has the zero-sum property with respect to $G$ if for every map $\nu : [n] \to G$, there is a $A \in \mathcal{A}$ with $\sum_{x \in A} \nu(x) = 0$.

If $\mathcal{A}$ contains $D(G)$ disjoint sets $A_1, \ldots, A_{D(G)}$, then under any $\nu : [n] \to G$ there will be some $I \subseteq [D(G)]$ such that $\sum_{x \in \bigcup_{i \in I} A_i} v(x) = 0$. Thus $\mathcal{A}$ has the zero-sum property.

If $\mathcal{A}$ can be covered by some $X \subseteq [n]$ of size $|X| < D(G)$, meaning that $X$ meets every element of $\mathcal{A}$, then $\mathcal{A}$ does not have the zero-sum property: By definition, there exists a map $\nu : X \to G$ without zero-sum subsequence and we can extend this map by setting $\nu(y) = 0$ for every $y \notin X$.

The question I ultimately want to get at is the following: Does the converse of the last statement also hold, namely: If $\mathcal{A}$ does not have the zero-sum property, does it necessarily admit a cover of size less than $D(G)$? Or, possibly weaker, is there some constant $q = q(G)$ such that if $\mathcal{A}$ does not have the zero-sum property, then it admits a cover of size at most $q$?

Using the inclusion-exclusion principle, this is easy to show for $G = \mathbb{Z}_2$, but it is not clear to me how to extend this to other groups.

[The question is related to, but different from this one that I asked on this site a while ago.]

Edit: Trimmed the question to make it more accessible.

$\endgroup$
7
  • 1
    $\begingroup$ Not crucial, but the word 'covered' is usually used for other stuff, imho. I would say 'hit' or 'pierced' or 'stabbed'. $\endgroup$
    – domotorp
    Commented Feb 28, 2016 at 21:41
  • $\begingroup$ Do you know the answer if $G=\mathbb Z_n$ and $\nu$ maps everything to $1$? $\endgroup$
    – domotorp
    Commented Feb 29, 2016 at 11:01
  • $\begingroup$ If $G = \mathbb{Z}_m$, then the general case is easily reduced to the case $\nu \equiv 1$ by 'copying' the points of the ground set (take $\nu : [n] \to [m]$ and replace every $x \in [n]$ by $\nu(x)$ new points). In fact, that case had been studied by Alon et al "Set systems with no union of cardinality 0 modulo m" under the hypothesis of bounded maximum degree. Their result would follow immediately from my conjectured statement. For my application, though, the non-cyclic case is most interesting, in particular groups like $\mathbb{Z}_p^n$. $\endgroup$ Commented Feb 29, 2016 at 12:32
  • $\begingroup$ So it is not known then, right? $\endgroup$
    – domotorp
    Commented Feb 29, 2016 at 13:45
  • $\begingroup$ No it is not (or rather: I do not know) and that case would suffice to settle it for cyclic groups (and arbitrary $\nu$) in the strong sense that any bound $q(G)$ valid for $\nu \equiv 1$ is valid for every map $\nu$. $\endgroup$ Commented Feb 29, 2016 at 15:30

1 Answer 1

3
+100
$\begingroup$

Let me prove that for $G=\mathbb{Z}_{p^s}$, $p$ is prime, we indeed have $q(G)=p^s-1=D(G)-1$. It is again inclusion-exclusion, as for $p^s=2$.

Let $\mathcal{A}$ be a union-closed family, assume that a function $\nu:[n]\rightarrow \mathbb{Z}$ satisfies the following condition: $p^s$ does not divide $S(A):=\sum_{x\in A} \nu(x)$ for any set $A\in {\mathcal A}$.

We use the following polynomial $$ \varphi(x)=\binom{x-1}{p^s-1}+(-1)^{p^s}. $$ We have $\varphi(0)=0$ and $\varphi(x)\equiv (-1)^{p^s} \pmod p$ for integer $x$ not divisible by $p^s$.

Let $\mathcal A$ be union-generated by sets $A_1,\dots,A_m$ (we may even assume that these are all sets of our family $\mathcal A$). Consider the following sum $$ \sum \varphi(S(A_i))-\sum_{i<j} \varphi(S(A_i\cup A_j))+\sum_{i<j<k}\varphi(S(A_i\cup A_j\cup A_k))-\dots $$ Modulo $p$ it equals $$ (-1)^{p^s}\left(m-\binom{m}2+\binom{m}3-\dots\right)=(-1)^{p^s}. $$ On the other hand, expand this as a polynomial in variables $\nu(1),\nu(2),\dots,\nu(n)$. There is no free term, since $\varphi(0)=0$. Consider any specific term, say $X=\nu(1)^3 \nu(2)\nu(5)\nu(8)^{p^s-6}$. Assume that elements 1,2,5,8 do not cover our family $\mathcal A$, that is, there exists index $t$ such that $\{1,2,5,8\}\cap A_t=\emptyset$. Then we may partition summands with the term $X$ onto pairs $\{\cup_{i\in I} A_i,\cup_{i\in I\cup\{t\}} A_i\}$, where $I$ runs over non-empty subsets of $[m]\setminus t$ such that $\{1,2,5,8\}\subset \cup_{i\in I} A_i$. For each such pair term $X$ cancels. So, total coefficient of $X$ is 0. But some coefficient is non-zero, since tital sum is not divisible by $p$. Thus there exists a cover of $\mathcal A$ of size at most $\deg \varphi=p^s-1$.

$\endgroup$
6
  • $\begingroup$ Thank you very much for your answer! To be honest I am still a bit confused - you need to work in the field $\mathbb{Z}_p$, but in there you cannot distinguish between numbers which are multiples of $p$ and numbers which are multiples of $p^s$, since both are simply zero. But yet you need to handle them differently, because a sum might be a multiple of $p$, but not of $p^s$... ? Thus the step I do not understand is the line about $\varphi$. (At least when $s = 1$ and $\varphi(x) = x^{p-1}$, I think I can follow your argument. Very nice!) $\endgroup$ Commented Feb 25, 2016 at 16:15
  • $\begingroup$ Yes, this is a delicate place, thus I work with integers. Hopefully it is ok. $\endgroup$ Commented Feb 25, 2016 at 16:52
  • $\begingroup$ But shouldn't $\varphi(p) = \varphi(0) = 0 \mod p$ hold? $\endgroup$ Commented Feb 25, 2016 at 17:07
  • $\begingroup$ no, $\varphi(p)=(-1)^{p^s}$ by very definition (if $s>1$, of course) $\endgroup$ Commented Feb 25, 2016 at 17:46
  • $\begingroup$ I think it's fine because $\varphi \in \mathbb{Q}[X]$, not in $\mathbb{Z}[X]$ (if it had integer coefficients, then projecting $\mod p$ would create havoc, which is what I had in mind earlier). $\endgroup$ Commented Feb 29, 2016 at 10:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .