/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/modulepublicimportFormalConjecturesUtil
The Manickam–Miklós–Singhi conjecture (1988)
References:
[MM88] Manickam, N. and Miklós, D. (1988). "On the number of nonnegative partial sums of a
nonnegative sum." Colloq. Math. Soc. János Bolyai 52, pp. 385--392.
[MS88] Manickam, N. and Singhi, N. M. (1988). "First distribution invariants and EKR theorems."
J. Combin. Theory Ser. A 48, pp. 91--103.
[CSS14] Chowdhury, A., Sarkis, G. and Shahriari, S. (2014). "The Manickam–Miklós–Singhi
conjectures for sets and vector spaces." J. Combin. Theory Ser. A 128, pp. 84--103.
arXiv:1309.2212
[Po15] Pokrovskiy, A. (2015). "A linear bound on the Manickam–Miklós–Singhi conjecture."
J. Combin. Theory Ser. A 133, pp. 280--306. arXiv:1308.2176
If $n \ge 4k$ and $x_1, \dots, x_n$ are real numbers with $x_1 + \dots + x_n = 0$, then at least
$\binom{n-1}{k-1}$ of the $k$-element subsets $S \subseteq {1, \dots, n}$ have
$\sum_{i \in S} x_i \ge 0$. (The bound is attained by $x = (n-1, -1, \dots, -1)$; the
condition $n \ge 4k$ cannot be weakened to $n \ge 3k + 1$ in general.)
With $k = 1$ the claim is that some $x_i$ is nonnegative, which is immediate since the $x_i$
sum to $0$ (and $n \ge 4 > 0$, so there is at least one $x_i$).