/- 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. -/ module public import FormalConjecturesUtil

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

@[expose] public sectionopen Finsetnamespace ManickamMiklosSinghiConjecture

The number of k-element subsets of Fin n on which the real weights x have nonnegative sum.

noncomputable def nonnegSubsetCount (n k : ℕ) (x : Fin n → ℝ) : ℕ := ((univ : Finset (Fin n)).powersetCard k).filter (fun S => 0 ≤ ∑ i ∈ S, x i) |>.card

The Manickam–Miklós–Singhi conjecture (1988).

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.)

@[category research open, AMS 5] theorem manickam_miklos_singhi_conjecture : ∀ (n k : ℕ), 1 ≤ k → 4 * k ≤ n → ∀ x : Fin n → ℝ, ∑ i, x i = 0 → (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x := ⊢ ∀ (n k : ℕ), 1 ≤ k → 4 * k ≤ n → ∀ (x : Fin n → ℝ), ∑ i, x i = 0 → (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x All goals completed! 🐙

Pokrovskiy (2015): the conjecture holds for $n \ge C k$ with an absolute constant $C$.

Pokrovskiy proved this with $C = 10^{46}$, the first bound linear in $k$.

Reference: [Po15].

@[category research solved, AMS 5] theorem manickam_miklos_singhi_conjecture.variants.pokrovskiy : ∃ C : ℕ, ∀ (n k : ℕ), 1 ≤ k → C * k ≤ n → ∀ x : Fin n → ℝ, ∑ i, x i = 0 → (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x := ⊢ ∃ C, ∀ (n k : ℕ), 1 ≤ k → C * k ≤ n → ∀ (x : Fin n → ℝ), ∑ i, x i = 0 → (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x All goals completed! 🐙

Chowdhury–Sarkis–Shahriari (2014): the conjecture holds for $n \ge 8k^2$.

Reference: [CSS14].

@[category research solved, AMS 5] theorem manickam_miklos_singhi_conjecture.variants.quadratic (n k : ℕ) (hk : 1 ≤ k) (hn : 8 * k ^ 2 ≤ n) (x : Fin n → ℝ) (hx : ∑ i, x i = 0) : (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x := n:ℕk:ℕhk:1 ≤ khn:8 * k ^ 2 ≤ nx:Fin n → ℝhx:∑ i, x i = 0⊢ (n - 1).choose (k - 1) ≤ nonnegSubsetCount n k x All goals completed! 🐙

The case k = 1.

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$).

n:ℕhn:4 ≤ nx:Fin n → ℝhx:∑ i, x i = 0hne:univ.Nonemptyi:Fin nhi:0 ≤ x i⊢ ({i} ⊆ univ ∧ #{i} = 1) ∧ 0 ≤ ∑ i ∈ {i}, x i exact ⟨⟨Finset.subset_univ _, Finset.card_singleton i⟩, n:ℕhn:4 ≤ nx:Fin n → ℝhx:∑ i, x i = 0hne:univ.Nonemptyi:Fin nhi:0 ≤ x i⊢ 0 ≤ ∑ i ∈ {i}, x i All goals completed! 🐙⟩end ManickamMiklosSinghiConjecture