Let ${\mathbf x} \in {\mathbb R}^n$ be a vector of $n$ real numbers with nonnegative sum: $\sum_{i=1}^n x_i \geq 0$. It is natural to ask how many partial sums must be nonnegative? Of course, all $2^n$ partial sums could be nonnegative when $x_i = 0$ always, so the interesting case is to try and minimize the number of nonnegative sums. One example is to take the vector

Such a vector has $2^{n-1}$ nonnegative partial sums and $\binom{n-1}{k-1}$ nonnegative partial $k$-sums. Bier and Manickam proved that this is the extremal example for partial sums of any order. The Manickam-Miklós-Singhi conjecture states that this is the extremal example for partial $k$-sums, given $n \geq 4k$.

Hartke and Stolee prove a stronger statement for all $k \leq 7$ and make a stronger conjecture.

The SearchLib project MMSConjecture contains all source code related to our solution. Full compilation requires TreeSearch, Utilities, and at least one of GLPK or CPLEX.

See the MMSConjecture User Guide for more information on compilation and running the software.

• Data values in Excel format
• Data values in CSV files:
  • Values of $g(n,k)$ and sharp examples
  • Values of $g_s(n,k)$ and strong examples

Computational Combinatorics Blog Post

Update to the Manickam-Miklós-Singhi Conjecture