# Ordering subsets of the cyclic group to give distinct partial sums

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.

-
I don't know if this has been studied before, but some relevant problems, most of which probably you are aware of: openproblemgarden.org/op/snevilys_conjecture, mathoverflow.net/questions/24108/…, cs.elte.hu/blobs/diplomamunkak/msc_mat/2013/… – domotorp Apr 25 '14 at 4:12
I can confirm the Dan Archdeacon link. He told me this problem a few months ago. (seems tough to me) – Peter Dukes Apr 28 '14 at 7:34
Is there a simple proof for the real case? That is, given a set of $k$ non-zero real numbers, can we order them so as to have all the partial sums $a_1+\dotsb+a_i\ (1\le i\le k)$ pairwise distinct? – Seva Apr 14 '15 at 18:57

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.

-
Is there some slight typo somewhere? Perhaps the subscript on the first product should be $1 \leq i < j \leq k$ or $1 \leq i \leq j \leq k$? But thank you, this seems like a great start. – David Speyer Apr 16 '15 at 19:30
@David: No typo (which is pretty unusual for me). We need $a_i+\ldots+a_j$ to be distinct from $0$ only for $1<i<j\le k$. – Seva Apr 16 '15 at 19:35
For $k=6$ (which is, of course, not prime, but still...) I get a coefficient of $4$. – David Speyer Apr 16 '15 at 19:40
@David: Do you mean the coefficient of $x_1^5\ldots x_5^5$? Well, quite possible. What are the coefficients of $x_1^5\ldots x_6^5/x_i^5$ for $1\le i\le 5$? – Seva Apr 16 '15 at 20:04
@Pace Nielsen: This cannot happen as $P$ is a homogeneous polynomial; and so, no monomial contained in $P$ is dominated by another one. Does this answer your question? – Seva Apr 20 '15 at 8:20

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.

-
Perhaps this argument extends to ordered groups. It is hard for me to see how one would avoid consecutive runs of a subgroup like (Z_2)^2 with methods like this. Maybe estimating the number of partial sequences could benefit from something like this? – The Masked Avenger Apr 15 '15 at 15:27
"Perhaps this argument extendds to ordered groups." Yes, with the same proof. – Pace Nielsen Apr 15 '15 at 16:53

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.

-