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$
  • 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 Feb 28 '16 at 21:41
  • $\begingroup$ Do you know the answer if $G=\mathbb Z_n$ and $\nu$ maps everything to $1$? $\endgroup$ – domotorp Feb 29 '16 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$ – monkeymaths Feb 29 '16 at 12:32
  • $\begingroup$ So it is not known then, right? $\endgroup$ – domotorp Feb 29 '16 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$ – monkeymaths Feb 29 '16 at 15:30
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$
  • $\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$ – monkeymaths Feb 25 '16 at 16:15
  • $\begingroup$ Yes, this is a delicate place, thus I work with integers. Hopefully it is ok. $\endgroup$ – Fedor Petrov Feb 25 '16 at 16:52
  • $\begingroup$ But shouldn't $\varphi(p) = \varphi(0) = 0 \mod p$ hold? $\endgroup$ – monkeymaths Feb 25 '16 at 17:07
  • $\begingroup$ no, $\varphi(p)=(-1)^{p^s}$ by very definition (if $s>1$, of course) $\endgroup$ – Fedor Petrov Feb 25 '16 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$ – monkeymaths Feb 29 '16 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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