# Positive sum can always be presented as a sum with strictly positive incremental sub-sums

I am trying to prove the following (which to my knowledge is just a "conjecture", I have not seen this proved anywhere or mentioned as a theorem so it very well may be a false statement):

Suppose we have a list of integers $$d_i$$ (positive, negative and zero allowed) such that the overall sum is positive: $$\sum_{i=0}^{N-1} d_i > 0$$. Then there must be an index $$j$$ such that if we re-arrange the sum to "start at index $$j$$" and wrap around we will get strictly positive intermediate sums.

Much easier illustrated with example:

Let our list be: $$[-2, -2, 3, -1, 3]$$. It is a valid list (positive sum), and clearly we can start at index 2 (zero-based) and "Wrap around" while always maintaing positive sub-sums:

$$3 = 3 \\ 3-1=2 \\ 3-1+3=5 \\ 3-1+3-2=3 \\ 3-1+3-2-2=1 \\$$

I am looking for feedback whether this is indeed a true statement or can be falsified.

I believe I proved it but feel a bit iffy about it:

I went by induction on number of negative entries $$N_{neg}$$:

For $$N_{neg} = 1$$, clearly the sum of the other (all positive!) entries must be a larger positive number, so we start at the first positive number immediately following the negative one and get the result.

For $$N_{neg} = 2$$, its abit more instructive but also fairly easy to see; there must be at least one negative entry smaller than the sum of the preceding consecutive sum of positive entries (otherwise the overall sum cant be positive), so we start with those positive entries and get the result.

An example to illustrate this case: [1, 1, -3, 1, -2, 3]. In this case we start at index 5 (value = 3), and wrap around to get the ordering [3, 1, 1, -3, 1, -2] which gives us the desired result.

Assume the statement is true for $$N_{neg} = k$$, then for k+1 we pick a couple of negative entries with only positive entries in between them, "merge" them by merging all intermediate positive values along with the two negative ones to get a list of $$k$$ negative numbers while still maintaing that overall sum is positive. By induction hypothesis we can start the sum at some index to get strictly positive intermediate sums; expanding back the merged items does not alter that (by associativity) - QED.

An example illustrating this: $$[1, 2, -4, 3, -3, 1, 2, -1]$$. We merge, for example, -3, 1, 2 and -1 to get: $$[1, 2, -4, 3, (-3 + 1 + 2 -1)] = [1, 2, -4, 3, -1]$$ which reduces to the case of 2 negative numbers which is true by induction hypothesis.

The extension to a statement about non-negative sums and non-negative intermediate sums rather than strictly positive is also straightforward by above argument I believe.

Is this a valid statement??

• There's a proof of this in Aigner and Ziegler Proofs from the Book.
– MJD
Commented Jul 11 at 14:40
• @MJD love that book! Do you recall which section it’s under? Commented Jul 11 at 15:08
• I just looked for it but couldn't find it, so perhaps I am remembering wrong. If I do turn it up I will let you know.
– MJD
Commented Jul 11 at 16:54
• I found it. It's in Graham et al, Concrete Mathematics 345–346. (§7.5 “Convolutions”). They call it “Raney's lemma”.
– MJD
Commented Jul 11 at 17:23

The statement is true. A possible index $$j$$ where to wrap the list can be determined as follows:

Choose the “wrap index” $$j$$ such that the sum of the first $$j$$ list elements is minimal. If there are multiple $$j$$ with the same minimal partial sum then choose the largest $$j$$ among those.

Then $$\tag{1} d_0 + d_1 + \ldots + d_{j-1} \le d_0 + d_1 + \ldots + d_k \quad \text{ for } 0 \le k \le j-1$$ and $$\tag{2} d_0 + d_1 + \ldots + d_{j-1} < d_0 + d_1 + \ldots + d_k \quad \text{ for } j \le k \le N-1 \, .$$ If $$j=N$$ then the original list satisfies the wanted condition. Otherwise $$d_j, \ldots, d_{N-1}, d_0 \ldots, d_{j-1}$$ does the job: For $$j \le k \le N-1$$ is $$d_j + \ldots + d_{k} > 0$$ because of $$(2)$$ and for $$0 \le k \le j-1$$ is $$d_j + \ldots + d_{N-1} + d_0 + \ldots + d_{k} \ge \sum_{i=0}^{N-1} d_i > 0$$ because of $$(1)$$.

Example: The list $$[1, 2, -4, 3, -3, 1, 2, -1]$$ has the partial sums $$[1, 3, -1, 2, -1, 0, 2, 1]$$. The third and the fifth partial sum are both equal to $$-1$$, which is the minimal value. Choose $$j=5$$ as the larger of the indices $$3$$ and $$5$$.

The wrapped list is $$[1, 2, -1, 1, 2, -4, 3, -3]$$ with the partial sums $$[1, 3, 2, 3, 5, 1, 4, 1]$$, which are all positive.

• thank you for a constructive solution! Commented Jul 11 at 14:38

Let's assume towards a contradiction that for each possible starting index $$j\in\{0,...,N-1\}$$ there exists a smallest index $$k_j\le N$$ such that if we sum up the first $$k_j$$ values of the sum starting with index $$j$$, the resulting series is non-positive.

Define for all $$j\in\{0,...,N-1\}$$: $$f(j):= j+k_j \quad \pmod N$$

Now there must exist some $$j\in\{0,...,N-1\}$$ and $$z\in\mathbb N$$ such that $$f^z(j)=j$$.

That is, if we start from index $$j$$, sum up the following elements till the sum of elements we just added is negative, and repeat that process, eventually we arrive at index $$j-1 \pmod N$$; That is, at some point we added up all elements of the whole sum $$\sum_{i=0}^{N-1} d_i$$, though possibly not just once, but a total of $$n$$ times (for some $$n\in\mathbb N$$).

So altogether we've now obtained $$n\sum_{i=0}^{N-1} d_i\le 0$$, since at each step we added a non-positive number; that is, we've arrived at a contradiction.

• That is a nice argument! It probably should be $(\mod N)$ instead of $(\mod N-1)$, though. Commented Jul 11 at 14:48
• @MartinR You're right. Thanks for the correction! Commented Jul 11 at 14:51
• Beautiful! Thank you @ConnFus Commented Jul 11 at 15:09
• This can even be made into a constructive method! – Start with $j=0$. If a partial sum starting at $j$ is $\le 0$ then replace $j$ by $j + k_j \pmod N$. Your argument shows that this procedure must eventually stop, and then you have an index $j$ such that all partial sums starting at $j$ are positive. Commented Jul 12 at 8:09
• (Cont.) For the example list $[1, 2, -4, 3, -3, 1, 2, -1]$ one gets $j=0 \to 3 \to 5 \to$ done. Commented Jul 12 at 8:12