Extremal combinatorics · subset sums · probability

Manickam–Miklós–Singhi Conjecture

Collaboration beta

If n≥4k real numbers have nonnegative total, must at least a k/n share of all k-subsets also have nonnegative sum?

(x_{1}, \dots, x_{n}) \in ℝ^{n}, n \geq 4 k, \sum_{i = 1}^{n} x_{i} \geq 0 \Rightarrow # {S \in (\binom{[n]}{k}) : \sum_{i \in S} x_{i} \geq 0} \geq (\binom{n - 1}{k - 1})

Listed inDouglas West’s REGS open-problem collection

Known results and sources

Weighted points and subset constellations introduce the Manickam–Miklós–Singhi question: how many k-subsets must have nonnegative sum?

Research problem

Exact mathematical statement

\text{If }(x_1,…,x_n)\in\mathbb{R}^n,\;n\ge4k\text{ and }\sum_{i=1}^{n}x_i\ge0,\quad \#\left\{S\in\binom{[n]}k: \sum_{i\in S}x_i\ge0\right\}\ge\binom{n-1}{k-1}.

the source studies the strict-positive polarized form of a hypothetical minimal counterexample and splits the remaining work between the d≤4k transport problem and the distinct-subset bridge in the d>4k branch.

Problem infographic

Problem at a glance

Scientific infographic for the open Manickam–Miklós–Singhi Conjecture on a deep forest-green background. The conditions n ≥ 4k and total weight sum at least zero appear beside a diagram explaining how to choose k real weights and add them. A sharp n = 8, k = 2 example has x₁ = +7 and exactly seven tokens x₂ through x₈ equal to −1; seven emerald spokes mark the seven nonnegative pairs containing +7, while one vermilion link marks a pair summing to −2. The conjecture asks for at least C(n−1,k−1), equivalently k/n of all k-subsets, to have nonnegative sum. The bottom states that the general conjecture remains open. — For n ≥ 4k and total weight at least zero, the Manickam–Miklós–Singhi conjecture predicts at least C(n−1,k−1) nonnegative k-subset sums. The displayed n = 8, k = 2 star example attains the bound exactly; the general conjecture remains open.

Current mathematical picture

Where work on Manickam–Miklós–Singhi Conjecture stands

Open conjecture

This curated overview maps selected current claims from authoritative Part I of the v8.1 source material. It retains the polarized two-branch architecture, the current work-reported closure of the arithmetic branch through eight negative coordinates, the five-cover, harmonic, mixed-restriction, heavy-normal-form, and value-weighted advances that narrow the first open nine-negative case, and the independent selector, local/profile, toric, and cap frontiers. Superseded mass bounds and route eliminations are labeled separately; the guarded Part II archive is not treated as current state. The full conjecture remains open, the continuous arguments have not received external line-by-line review, harmonic inputs remain qualified, and the embedded verifier checks algebra and finite cases rather than the full proof.

Strongest supported footholdUniform value-weighted five-cover payment

Five disjoint negative blocks now yield an explicit expected positive-margin lower bound, including a bonus for unused negative mass.

Evidence posture · Reported result

Leading routeUniform arithmetic route

The paired arithmetic architecture is closed through m≤8, narrowed at m=9, and still requires a theorem for every m≥10 with m<ρ.

Route status · Active route

Useful failureWithdrawn suffix-profile route

The older unspecified v7.0 suffix-profile assertion remains unavailable and is not revived by the new five-cover certificate.

Route status · Eliminated route

Main reductionHeavy-count and remainder staircase

Exact one-light, two-light, and all-heavy closures impose three low-remainder and high-excess residual regimes.

Evidence posture · Reported reduction

Completed special caseHarmonic stability and upper-remainder closure

Harmonic reserve strengthens five-cover and closes the all-heavy upper remainder, with exact finite checks through k≤30.

Evidence posture · Reported special case

Evidence footholdArtificial nine-negative vector is nonrepresentable

The retained v7.1 abstract layer vector at (m,k,ρ,d,n)=(9,24,10,97,106) has q₁+4q₂=4/5<1, so it cannot arise from a polarized additive system.

Evidence posture · Computation reproduced · provisional

Priority open bridgeProve the selector safe-surplus payment

Prove 𝔖≥𝔇, or the explicit sufficient value-weighted bound, on the exact triangular cutoff grid.

Task status · Prerequisites still open

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Manickam–Miklós–Singhi Conjecture in numbers

6.7kretained lines of mathematical investigation6,678 in the current working snapshot

Argument development: 5,645 · 85%
Explored or eliminated routes: 283 · 4%
Computational analysis: 91 · 1%
Open obligations: 373 · 6%
Definitions and setup: 286 · 4%

24selected mapped statements10routes investigated11reported milestones7open questions1contribution-ready tasks

Evidence attached to the current work2 original computation reruns

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byN. Manickam, D. Miklós, N. M. SinghiProposed1988Status checkedAug 2, 2026

Source recordedAug 2, 2026

Recommended next task

Independently audit continuous and harmonic inputs

Before publication-grade reliance, independently audit the continuous combinatorial arguments, precisely prove or cite the harmonic formulas, and reproduce the exact computation with a second implementation or formal proof.

Suggested move: Bind a line-by-line review to Part I, record exact Kneser/down-up/slice references, and independently reimplement the Appendix A checks.

What would count as progress

Audit every internal proof used by the current frontier.
Resolve or explicitly cite each harmonic dependency.
Produce an independently implemented or formal computation check.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

27 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeUniform arithmetic route

The paired arithmetic architecture is closed through m≤8, narrowed at m=9, and still requires a theorem for every m≥10 with m<ρ.

Route status · Active route

Active routeShifted selector-payment route

Exact double-cutoff transport and unsafe-core charging are retained; safe surplus still must pay unsafe deficit without losing the near-star boundary.

Route status · Active route

Active routeLocal certificates plus profile gluing

The five-unit kernel is closed; a uniform local theorem and orbit-safe profile gluing remain separate missing arrows.

Route status · Active route

Active routeToric/Graver stationarity

Stationarity transfer is closed; the primitive incomparable-Graver atom theorem is the next target.

Route status · Active route

Active routeCapped-functional route

The stronger cap objective retains local certificates but lacks a global deficit/overshoot unbiasing or fractional-packing theorem.

Route status · Active route

Explored alternatives

Other routes

5 recorded

Narrowed routeNine-negative distinct-count route

The first open arithmetic case is narrowed to k≥31, seven to nine heavy labels, low remainder, high but non-one-heavy excess, exact thresholds, and a value-weighted margin whose distinct-count conversion remains open.

Route status · Narrowed route

Useful but insufficientFree linear five-cover relaxation

Too weak by the explicit q₁=1/3, q₂=1/6 profile; additive or harmonic stability remains viable.

Route status · Useful but insufficient

Useful but insufficientFree mixed-restriction relaxation

Too weak on its own because the artificial vector passes all 239 constraints; it remains active only as an ingredient joined to representability.

Route status · Useful but insufficient

Browse 2 more explored routes

Eliminated routeWithdrawn suffix-profile route

The older unspecified v7.0 suffix-profile assertion remains unavailable and is not revived by the new five-cover certificate.

Route status · Eliminated route

Narrowed routeTotal-mass closure as final target

The Δ<5k−8 and Δ<6k−8 arguments are retained for reusable matching mechanisms but are superseded by the seven-heavy normal form and staircase.

Route status · Narrowed route

Route statements and reductions

Statements the next route can inspect and build on

Route statementArithmetic branch closed through eight negatives

The current work reports that every arithmetic-branch case with m≤8 is closed.

Source-reported route statement

Route statementUniform arithmetic extension beyond nine negatives

The eventual arithmetic theorem must cover every m≥9 with m<ρ; the generalized value-weighted five-cover already supplies a uniform interface, but the distinct-count conversion or covering architecture must extend.

Source-reported route statement · dependencies incomplete

Route statementExact shifted double-cutoff transport

For d≤4k, the current work represents the positive-set count as an average of cutoff-core counts G_{a,b} over an exact triangular probability measure supported on a≤b.

Source-reported route statement

Route statementRobust unsafe-core charge

The selector deficit is bounded by value-weighted predecessor payments, and the value-selector terms retain favorable nonnegative covariance.

Source-reported route statement

Route statementSelector safe-surplus payment

The first unproved selector theorem is 𝔖≥𝔇, preferably via the explicit value-weighted cutoff inequality that matches the exact triangular transport and strip coefficients.

Source-reported route statement · dependencies incomplete

Route statementUniform local theorem and orbit-safe gluing

The local/profile architecture still needs a uniform replacement-cone, balanced-rectangle, or dominance theorem and profile-circuit gluing without double charging orbit weights.

Source-reported route statement · dependencies incomplete

Route statementPrimitive incomparable-Graver atom theorem

After the retained stationarity transfer and same-cell smoothing results, the first toric target is the primitive incomparable identity (0,4,5)∼(1,2,6).

Source-reported route statement · dependencies incomplete

Route statementCap deficit/overshoot packing theorem

The cap objective is stronger than MMS and still needs a global fractional-packing or unbiasing theorem that avoids overcharging deficit capacity.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

7 featured tasks

Independently audit continuous and harmonic inputs

Suggested move: Bind a line-by-line review to Part I, record exact Kneser/down-up/slice references, and independently reimplement the Appendix A checks.

Ready to work on

Prove the selector safe-surplus payment

Prove 𝔖≥𝔇, or the explicit sufficient value-weighted bound, on the exact triangular cutoff grid.

Suggested move: Match the strip coefficients, exploit positive value-selector covariance, and preserve the near-star mass-slack-one boundary without double-spending spectral reserve.

Prerequisites still open

Extend the arithmetic theorem to every m≥10

After the nine-negative case, obtain an arithmetic theorem uniform for every m≥10 with m<ρ.

Suggested move: Generalize the value-weighted cover construction, heavy threshold, or distinct-count conversion without discarding the common paired denominator.

Prerequisites still open

Prove a uniform local theorem and orbit-safe gluing

Close the replacement-cone or balanced-rectangle step and glue local profile circuits without double charging orbit weights.

Suggested move: Separate the uniform local certificate from the global orbit-weight accounting and prove both interfaces explicitly.

Prerequisites still open

Prove the primitive incomparable-Graver atom theorem

Decompose the mixed-sign curvature of (0,4,5)∼(1,2,6) into established same-cell smoothing inequalities plus nonnegative endpoint mass.

Suggested move: Work at the first primitive incomparable identity and retain the already-established stationarity sign rather than reopening transfer.

Prerequisites still open

Global cap deficit/overshoot packing

Prove a global fractional packing or unbiasing theorem for the stronger cap objective without overcharging local deficit capacity.

Suggested move: Formulate the exact global capacity budget joining the retained endpoint, KKT, transport, and local bonus certificates.

Prerequisites still open

Convert value-weighted margin into distinct count

Prove the exact seven-to-nine-heavy theorem by converting the five-cover margin into at least C(d+8,k−1) distinct positive k-sets without repeated charging.

Suggested move: Split the exact heavy normal form into multi-center concentrated and dispersed excess cases; test every inequality against the retained artificial, equality, one-heavy, staircase-boundary, and selector examples.

Prerequisites still open

Sourced mathematical context

The known mathematical landscape

Context collected Aug 2, 2026

Current statusOpen conjecture

The full threshold n≥4k remains open. It is proved for all sufficiently large n relative to k, including a published linear bound n≥Ck with a very large absolute constant, and for each k≤7 by finite/computational methods.

[4][1][6]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2015
Peer reviewedPokrovskiy proved a linear bound f(k)≤Ck for an absolute constant C.[4]
2014
PreprintChowdhury, Sarkis, and Shahriari improved the general quadratic range to n≥8k² and resolved the vector-space analogue for n≥3k.[2]
2013
PreprintHartke and Stolee made verification for each fixed k a finite branch-and-cut problem and proved a strengthening for k≤7, including f(4)=14, f(5)=17, f(6)=20, and f(7)=23.[1]
2012
Peer reviewedAlon, Huang, and Sudakov proved the conjecture when n is at least min(33k², 2k³).[5]

Mathematical neighborhood

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Cited passages corrected

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

12 mapped milestonesretained argument map

Browse all 12 mapped stages

stage 1Polarized branch interfaces
stage 2Universal five-cover structure
stage 3Artificial vector excluded by a new certificate
stage 4Upper-remainder nine-negative range closed
stage 5Mixed hierarchy separated from representability
stage 6Total-mass targets superseded
stage 7Strong one-heavy concentration excluded
stage 8Seven-heavy normal form
stage 9Value-weighted five-cover payment
stage 10Heavy-count and remainder staircase
stage 11Distinct-count frontier isolated
stage 12Exact verifier and audit boundary

Polarized branch interfacesThe retained program organizes a hypothetical minimal counterexample into exact paired-arithmetic and shifted-selector branches.