subsequence sum


Davenport's constant ★★★

Author(s):

For a finite (additive) abelian group $G$, the \emph{Davenport constant} of $G$, denoted $s(G)$, is the smallest integer $t$ so that every sequence of elements of $G$ with length $\ge t$ has a nontrivial subsequence which sums to zero.

\begin{conjecture} $s( {\mathbb Z}_n^d) = d(n-1) + 1$ \end{conjecture}

Keywords: Davenport constant; subsequence sum; zero sum

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $G$, let $s(G)$ ($s'(G)$) denote the smallest integer $m$ so that every sequence of $m$ elements of $G$ has a subsequence of length $>0$ (length $|G|$) which has product equal to 1 in some order.

\begin{conjecture} $s'(G) = s(G) + |G| - 1$ for every finite group $G$. \end{conjecture}

Keywords: subsequence sum; zero sum

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

\begin{conjecture} For every $0 \le t \le n-1$, the sequence in ${\mathbb Z}_n^2$ consisting of $n-1$ copes of $(1,0)$ and $t$ copies of $(0,1)$ has the fewest number of distinct subsequence sums over all zero-free sequences from ${\mathbb Z}_n^2$ of length $n-1+t$. \end{conjecture}

Keywords: subsequence sum; zero sum

Syndicate content