Ordering subsets of the cyclic group to give distinct partial sums

Question

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\cdots+a_k$ are all distinct. Equivalently, you want to avoid runs $a_i+a_{i+1}+\cdots+a_j$ that add to zero (where $1<i<j\le k$).

In the case when $k=n-1$ this is known -- it is covered by the theory of sequenceable and $R$-sequenceable groups. Has anyone looked at the above generalisation before? Even though $k=n-1$ feels like it should be the hardest case, it doesn't seem to imply the other cases. I have some hope of a proof for the case when $n$ is prime, but before I go to the effort of sorting out the details I want to be sure I'm not reinventing the wheel.

It is tempting to think the problem will be easy when $k$ is very much smaller than $n$. However, it is possible that $S$ might be all the nonzero elements of some subgroup of $\mathbb{Z}_n$, in which case you are just looking for a sequencing of that subgroup. This will exist, but are probably very rare in some sense.

This problem was told to me by Jeff Dinitz, and I think he might have got it from Dan Archdeacon. Any pointers to relevant literature will be much appreciated.

Answer 1

This is not a complete solution, but I believe it can be completed with some further effort for the case where $n$ is prime. (As you have noted, for $n$ composite we can run into troubles with subgroups, and it is not clear whether the assertion holds true in this case.)

Assuming thus that $n$ is prime, let $$ P(x_1,\ldots, x_k):= \prod_{1<i<j\le k} (x_i+\dotsb+x_j) \cdot \prod_{1\le i<j\le k} (x_j-x_i) \in {\mathbb F}_n[x_1,\ldots x_k]. $$ This is a polynomial in $k$ variables of degree $(k-1)^2$; it is homogeneous, so that none of its monomials is dominated by any other monomial.

The crucial observation is that if a set $S\subset{\mathbb F}_n^\times$ cannot be ordered the way you want it, then $P$ vanishes on the cartesian product $S^k=S\times\dotsb\times S$. Consequently, by the "generalized Combinatorial Nullstellnsatz" (Theorem 2 of this paper by Michal Lason), $P$ does not contain any monomial $ax_1^{d_1}...x_k^{d_k}$ with $d_1,\dotsc,d_k<k$. In other words, if we can show that $P$ contains a monomial with the individual degree in each variable smaller than $k$, then we are done.

Playing around with small values of $k$ suggests that $P$ actually contains lots of such monomials; for instance, $x_1^{k-1}\ldots x_{k-1}^{k-1}$ has coefficient $\pm 1$ in $P$ for $k\le 5$. I would speculate that the coefficients of $P$ can be computed explicitly, and this should give the result.

Answer 2

Just a long comment: I wonder if much more is true. For instance, if $G$ is an (additive) abelian group, and $a_1,a_2,\ldots, a_k$ is a list of non-zero, distinct elements of $G$ with $$(\ast)\qquad a_1+a_2+\cdots+a_k\neq 0$$ is it true that we can order the list so that $$a_i+a_{i+1}+\cdots + a_j\neq 0\text{ for all }1\leq i\leq j\leq k?$$

(I've checked it for small values of $k$.)

Here is my proof that $(\mathbb{R},+)$ has this property. First off, we can write the list as $n_s<n_{s-1}<\ldots<n_1<0<p_1<p_2<\ldots<p_t$. (The $n$'s are the negative terms, and the $p$'s are the positive ones.) The idea is that we take this ordering, and then modify it in small ways, to eventually end up with an ordering that has the desired property.

Suppose that there is a subsum which is zero. This would mean $\sum_{i=1}^{t_0}p_i=-\sum_{i=1}^{s_0}n_i$ for some $s_0\leq s,t_0\leq t$. We take $t_0$ minimal with this property. (Then $s_0$ is minimal as well.)

Case 1: $t_0=t$. Then $s_0<s$ (by $(\ast)$), and we can just switch $n_{s_0}$ and $n_{s_0+1}$ and we are done.

Case 2: $t_0<t$ and $s_0=s$. Similar.

Case 3: $s_0<s$, $t_0<t$, and $-\sum_{i=1}^{s}n_i<\sum_{i=1}^{t_0+1}p_i$. Switch $n_{s_0}$ and $n_{s_0+1}$, and again we are done.

Case 4: $s_0<s$, $t_0<t$, and $-\sum_{i=1}^{s}n_i\geq \sum_{i=1}^{t_0+1}p_i$. Switch $p_{t_0}$ and $p_{t_0+1}$. There are two subcases here. First, it might happen that $p_{t_0+1}+\sum_{i=1}^{t_0-1}p_i=-\sum_{i=1}^{s_1}n_i$ for some $s_1>s_0$. In that case we switch $n_{s_1}$ and $n_{s_1+1}$. If that subcase doesn't happen, then we don't make any extra switch.

Note that the only case which doesn't immediately finish the problem is Case 4. However, after the switch(es) in Case 4, and then after renumbering, the minimal $s_0$ and $t_0$ have increased. The only other property of our ordering that we need to preserve, so that we can iterate this process, is that any new terms $p_{t'}$ and $p_{t'+1}$ we will switch (respectively $n_{s'}$ and $n_{s'+1}$) are strictly increasing (resp. decreasing). One quickly checks that Case 4 does preserve this fact, given the initial ordering.

Answer 3

I independently came up with a proof in the real case that is a bit different from Pace's:

Let's solve the problem over $\mathbb R$. If you order the elements with all the positive first and the negatives last, you only lose if some final segment of the positives balances some initial segment of the negatives. You can avoid this by building the order inside-out using a greedy algorithm.

You have a pile of negatives and a pile of positives. You have a current sequence. If the total is negative, you add a positive to the left. If the total is positive, you add a negative to the right. As long as the total never becomes zero, you win.

If you have more than one choice for what to add, you can always add in such a way that the total is not zero. You only lose if there is exactly one number left on one of the sides, and that number would perfectly balance the sum. If that number is positive, you're actually fine - because $a_1$ contributes to every sum, it contributes to none of the differences, and so this balanced sum doesn't actually count. Then adding all the negatives, you will never get another balanced sum. If it's negative, just reverse the order and use the same argument.

The problem is solvable over $\mathbb R$, hence over $\mathbb Z$. A failure to solve the problem for a given $k$ can be viewed as a nontrivial solution to a certain set of linear equations. Because there are no solutions over $\mathbb Z$, there are no solutions mod $p$ for $p$ sufficiently large, hence there are no solutions mod $n$ as long as all prime divisors of $n$ are sufficiently large relative to $k$. I believe greater than $k^{k/2}$ is enough.