A linear bound on the Manickam–Miklós–Singhi conjecture

• Progress is made 20 year old conjecture with a very simple statement.
• A new method is developed and used to improve known bounds on this conjecture.
• The conjecture is proved in a range which is a constant factor away from the conjectured range.

Suppose that we have a set S of n real numbers which have nonnegative sum. How few subsets of S of order k   can have nonnegative sum? Manickam, Miklós, and Singhi conjectured that for n≥4kn≥4k the answer is (n−1k−1). This conjecture is known to hold when n is large compared to k  . The best known bounds are due to Alon, Huang, and Sudakov who proved the conjecture when n≥33k2n≥33k2. In this paper we improve this bound by showing that there is a constant C   such that the conjecture holds when n≥Ckn≥Ck. This establishes the conjecture in a range which is a constant factor away from the conjectured bound.