Distinct Partial Sums in Cyclic Groups: Polynomial Method and Constructive Approaches

Abstract

Let $(G,+)$ be an abelian group and consider a subset $A\subseteq G$ with $|A|=k$. Given an ordering $(a_1,\dots ,a_k)$ of the elements of $A$, define its {\em partial sums} by $s_0=0$ and $s_j={\sum }_{i=1}^j{a}_i$ for $1\le j\le k$. We consider the following conjecture of Alspach: For any cyclic group ${\mathbb{Z}}_n$ and any subset $A\subseteq {\mathbb{Z}}_n\setminus \{0\}$ with $s_k\ne 0$, it is possible to find an ordering of the elements of $A$ such that no two of its partial sums $s_i$ and $s_j$ are equal for $0\le i<j\le k$. We show that Alspach's Conjecture holds for prime $n$ when $k\ge n-3$ and when $k\le 10$. The former result is by direct construction, the latter is non-constructive and uses the polynomial method. We also use the polynomial method to show that for prime $n$ a sequence of length $k$ having distinct partial sums exists in any subset of ${\mathbb{Z}}_n\setminus \{0\}$ of size at least $2k-\sqrt{8k}$ in all but at most a bounded number of cases.

18 pages