Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Independent nonnegative mean-one random variables sum below n+1 with probability at least (n/(n+1))^n, which is at least 1/e.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-31 12:18 UTC pith:SQBMBYYK

load-bearing objection Short, sharp proof of Feige's conjecture for δ=1 that cleanly reduces to the VT26 merger plus a simplex section bound. the 3 major comments →

arxiv 2607.24528 v1 pith:SQBMBYYK submitted 2026-07-27 math.PR

On Feige's conjecture

Zipei Nie , Jiaye Wei This is my paper
classification math.PR MSC 60E1560F1062G10
keywords Feige's conjecturelower-tail boundsnonnegative random variablesmergersDirichlet distributionsimplex sectionsconcentration inequalities
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Feige's conjecture asks for a dimension-free lower-tail bound: if X1 through Xn are independent and nonnegative with mean one, the chance their sum is less than n+1 is at least 1/e. This paper proves the sharp finite-n form of that statement: the probability is at least (n/(n+1))^n, which tends to 1/e and is achieved by simple two-point laws. The argument reduces the probability question to a pointwise bound on a single function Kn built from Dirichlet weights, then estimates that function by a geometric half-space section of the simplex. For general deviations up to 1 the same method yields an explicit bound that is sharp at deviation 1; the fully general Feige conjecture for every positive deviation remains open, though an improved two-variable merger already settles the n=2 case for all deviations.

Core claim

For every n and every deviation δ in (0,1], independent nonnegative mean-one random variables satisfy P(sum Xi < n+δ) ≥ δ (n/(n+δ))^n. When δ=1 this is exactly Feige's conjecture, and the bound is sharp for every n by taking each Xi equal to n+1 with probability 1/(n+1) and 0 otherwise.

What carries the argument

The merger Kn: the probability, under uniform Dirichlet weights on the simplex, that a weighted sum of the coordinates is at most 1. Because Kn is a merger, any region where Kn is pointwise at most α automatically has probability at most α under independent nonnegative mean-one inputs; a simplex half-space estimate then supplies the needed pointwise bound.

Load-bearing premise

The whole proof rests on the external fact that the Dirichlet half-space function Kn really is a merger, i.e., never exceeds its nominal level under independent nonnegative mean-at-most-one variables.

What would settle it

Either exhibit independent nonnegative mean-one variables whose sum falls below n+1 with probability strictly less than (n/(n+1))^n, or show that Kn itself violates the merger inequality for some input vector and some level α.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Feige's original 1/13 constant is replaced by the sharp 1/e (and the exact finite-n constant) for the unit-deviation lower tail.
  • Applications that invoked Feige's inequality in algorithms, extremal combinatorics, and search heuristics inherit the improved numerical constant at once.
  • For two variables the admissible merger already yields the sharp Feige bound for every positive deviation.
  • The same merger-plus-geometry template supplies an explicit (though not always sharp) lower-tail bound for every deviation at most 1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If admissible higher-dimensional mergers can be constructed, the same reduction would likely settle Feige's conjecture for every positive deviation, not only deviations at most 1.
  • The geometric half-space estimate on the simplex is the only place where the restriction δ≤1 enters; a tighter section inequality could remove that limitation without changing the merger.
  • Any future improvement of the merger Kn that remains a merger would automatically tighten the lower-tail constants obtained by this method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The manuscript proves Feige's conjecture (2006): for independent nonnegative random variables X_1,...,X_n with E[X_i]=1, P(ΣX_i < n+1) ≥ (n/(n+1))^n ≥ 1/e, with the constant sharp for every n. More generally, Theorem 1.3 gives P(ΣX_i < n+δ) ≥ δ(n/(n+δ))^n for all 0<δ≤1. The proof has two ingredients: (i) the function K_n(x) = P(Σ x_i D_i ≤ 1) for (D_0,...,D_n)~Dir(1,...,1), which is a "merger" (valid distribution-free p-value) by the recent Vlassis–Thomas resolution of Gaffke's conjecture [VT26], combined with a simple reduction (Lemma 2.2) turning any pointwise bound on a merger over {Σx_i ≥ n+δ} into a lower-tail bound; and (ii) a geometric estimate (Lemma 2.5) bounding K_n on that region via a Grünbaum-type half-space section inequality for the simplex [LY24, Theorem 4], whose closed form simplifies exactly to δ(n/(n+δ))^n. Section 3 uses the admissible n=2 merger K^ad_2 of [MRS+26] to recover the sharp two-variable bound min(δ/(1+δ), ((1+δ)/(2+δ))^2) for every δ>0, with matching extremal examples; the arbitrary-δ, arbitrary-n conjecture remains open.

Significance. Feige's conjecture has been open since 2006 and the best prior constant was 0.1798 (Guo–He–Ling–Liu); the inequality is a standard tool in randomized algorithms, extremal combinatorics, and heuristic runtime analysis. If the external inputs hold, this is a complete, parameter-free resolution with no fitted constants: the bound δ(n/(n+δ))^n is derived from a geometric volume computation and shown sharp for every n at δ=1 via an explicit two-point extremal example. The proof is short, fully self-contained modulo two clearly identified citations, and each internal step is verifiable line by line — I checked the algebra in Lemma 2.5 and the simplification to δ(n/(n+δ))^n is exact. The n=2 sharp bound for all δ>0 and the honest discussion of why the method does not yet settle the arbitrary-δ conjecture add value. The paper also transparently discloses AI assistance in the discovery phase while asserting independent human verification, which is appropriate practice.

major comments (3)
  1. [§2, Theorem 2.4] Theorem 2.4 is the single load-bearing input: Lemma 2.2 converts the merger property of K_n directly into the tail bound, and no independent proof is given. The manuscript quotes [VT26] without stating the hypotheses under which K_n is shown to be a merger. This matters concretely: Gaffke-type validity statements are classically proved for i.i.d. nonnegative samples, whereas the present application (Lemma 2.2 applied in the proof of Theorem 1.3) requires the property for independent but arbitrarily non-identically-distributed nonnegative variables with E[X_i] <= 1. If [VT26] establishes validity only under i.i.d. (or exchangeable, or bounded) hypotheses, Theorem 1.3 as stated does not follow. Please reproduce the precise statement from [VT26] (theorem number and hypotheses) and confirm it covers independent, non-identically-distributed variables with heterogeneous means mu_i <= 1; a one-
  2. [§2, Lemma 2.5] The estimate in Lemma 2.5 is the other load-bearing step, and it rests on [LY24, Theorem 4] applied to the half-space {⟨u,v⟩ > ((1-δ)/(n+δ)) · (Σx_i)/(n+1)} in the centered simplex. The algebra in the displayed chain is correct — I verified that the expression (n/(n+1))^n (1+q)^n (1−nq) with q=(1−δ)/(n+δ) simplifies exactly to δ(n/(n+δ))^n, and that the inclusion {⟨u,v⟩>t} ⊆ {Σx_iD_i > 1} follows from Σx_iD_i > Σx_i/(n+δ) ≥ 1. However, the applicability of the quoted theorem is not shown: for a general direction u = (0,x_1,...,x_n) − (Σx_i/(n+1))(1,...,1), the cutting hyperplane is not parallel to a facet of Δ, so the classical facet-parallel Grünbaum formula does not directly apply, and the reader must know precisely how the parameter q in [LY24, Theorem 4] is defined relative to the directional data (e.g., relative to min_{v∈Δ}⟨u,v⟩, which here is attained at the vertex (1,0,...,0)). P
  3. [§3, Lemma 3.3] Lemma 3.3 invokes [MRS+26, Lemma 3.4] for the equivalence between the pointwise bound on K^ad_2 and the condition b ≥ 1/((1−s)(1+as)). Since [MRS+26] is a 2026 preprint and Theorem 3.4 is a self-contained-looking corollary, a brief restatement of that lemma (or a two-line derivation from Definition 3.1 and the quadratic defining τ(a,b)) would make Section 3 independently checkable. This is less critical than the §2 dependencies since Theorem 3.4 is acknowledged to be known, but the same hypothesis-matching concern applies in miniature.
minor comments (5)
  1. [§1, Theorem 1.3] The restriction to 0 < δ ≤ 1 in Theorem 1.3 is stated but not motivated; a one-sentence remark that the geometric bound in Lemma 2.5 requires q = (1−δ)/(n+δ) ≥ 0 would explain why the method does not extend to δ > 1, complementing the discussion in §3.
  2. [§1, after Theorem 1.3] Sharpness for Theorem 1.3 is stated with the two-point example X_i ∈ {0, n+1}; it would help to note explicitly that P(ΣX_i < n+1) = (n/(n+1))^n for this law (all X_i = 0), so that the constant is attained rather than merely approached.
  3. [§3, proof of Lemma 3.3] In Lemma 3.3, the phrase 'a concave function can only attain its minimum at a boundary point' should read 'on a compact interval, a concave function attains its minimum at an endpoint'; as written it is slightly imprecise.
  4. [References] References [VT26], [MRS+26], and [LY24] are all preprints (two from 2026). Given that the main theorem rests on [VT26], please track and update the publication status of these references at revision, and consider citing the specific theorem numbers in [LY24] and [VT26] at each invocation rather than only at first use.
  5. [§2, Lemma 2.2] Typographical: the strict/non-strict inequality handling in Lemma 2.2 (the event {ΣX_i ≥ n+δ} vs. the open event in the theorem statement) is correct but worth one clarifying phrase for readers, since K_n is defined with a non-strict inequality while Theorem 1.3 uses a strict one.

Circularity Check

0 steps flagged

No circularity: Feige bound is derived from an independently defined Dirichlet merger plus a one-way geometric estimate, not assumed or fitted.

full rationale

The derivation chain is Lemma 2.2 (merger reduction) + Theorem 2.4 (K_n is a merger, cited from Vlassis–Thomas VT26) + Lemma 2.5 (pointwise bound on K_n via a Grünbaum-type simplex section from LY24). K_n is defined as the Dirichlet half-space probability P(∑ x_i D_i ≤ 1), which does not encode Feige’s tail; the merger property is an external finite-sample validity result, not a restatement of the target inequality; and Lemma 2.5 only upper-bounds that fixed function on {∑ x_i ≥ n+δ}. Sharpness is checked by an independent two-point construction, not by normalizing constants fitted to the claim. Authors Nie–Wei do not self-cite a uniqueness or ansatz theorem that forces the result. Ordinary dependence on concurrent external work (VT26, MRS+26, LY24) is load-bearing for correctness but is not circularity under the stated criteria. Score 0; steps empty.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 0 invented entities

Central claim is a pure probabilistic inequality. No fitted parameters. Background is standard probability plus two external theorems (VT26 merger property of K_n; LY24 simplex section bound). Domain assumptions are exactly Feige's: independence, nonnegativity, unit means. 'Merger' and K_n are imported definitions, not invented here to force the result.

axioms (5)
  • domain assumption Independence, nonnegativity, and E[X_i]=1 (or ≤1 in the merger definition) for the random variables under study.
    Stated in Conjectures 1.1–1.2 and Theorem 1.3; without them the lower-tail claim is false in general.
  • domain assumption K_n is a merger: for independent nonnegative mean-≤1 variables, P(K_n(X)≤α)≤α for all α∈[0,1] (Theorem 2.4 / VT26).
    Invoked as a black box to finish the proof of Theorem 1.3 via Lemma 2.2; not re-proved in this paper.
  • standard math Half-space section volume bound for the centered simplex ([LY24, Theorem 4]) as applied in Lemma 2.5.
    Used to convert the geometric inclusion into the explicit constant δ(n/(n+δ))^n.
  • standard math Dirichlet(1,...,1) is uniform on the simplex; standard inner-product identities for centered weights.
    Used to identify K_n with a uniform simplex probability and to compute ⟨u,v⟩.
  • domain assumption For n=2, K_ad_2 is a merger and satisfies the pointwise bound in Lemma 3.3 (MRS+26).
    Needed only for the optional sharp all-δ two-variable Theorem 3.4, not for Feige's conjecture itself.

pith-pipeline@v1.2.0-grok45-kimik3 · 10979 in / 3153 out tokens · 57673 ms · 2026-07-31T12:18:28.988324+00:00 · methodology

0 comments
read the original abstract

We present a short proof of Feige's conjecture: for $n$ independent nonnegative random variables with expectation one, the probability that their sum is less than $n+1$ is at least $\left(\frac{n}{n+1}\right)^n\ge \frac{1}{e}$. The proof was obtained with the assistance of GPT-5.6 Sol and builds on the recent breakthrough of Vlassis and Thomas establishing Gaffke's conjecture on the finite-sample validity of a distribution-free $p$-value. We also discuss the implications of the subsequent work of Ming, Ramdas, Shen, Wang, and Waudby-Smith.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. From Lecture Notes to Lean: Formalizing a Textbook on Probability Theory

    cs.LO 2026-07 conditional novelty 5.0

    An ongoing Lean formalization of Shum's probability textbook, using AI-assisted translation and bridge lemmas, has uncovered a textbook error.

Reference graph

Works this paper leans on

17 extracted references · 2 linked inside Pith · cited by 1 Pith paper

  1. [1]

    On a conjecture of

    Alqasem, Abdulmajeed and Aravinda, Heshan and Marsiglietti, Arnaud and Melbourne, James , journal=. On a conjecture of. 2024 , publisher=

    2024

  2. [2]

    Journal of Combinatorial Theory, Series B , volume=

    Nonnegative k -sums, fractional covers, and probability of small deviations , author=. Journal of Combinatorial Theory, Series B , volume=. 2012 , publisher=

    2012

  3. [3]

    Frankl, Peter and Kupavskii, Andrey , journal=. The. 2022 , publisher=

    2022

  4. [4]

    A short proof of

    Egozcue, Mart. A short proof of. arXiv preprint arXiv:2509.19949 , year=

    arXiv

  5. [5]

    SIAM Journal on Computing , volume=

    On sums of independent random variables with unbounded variance and estimating the average degree in a graph , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    2006

  6. [6]

    Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Counting stars and other small subgraphs in sublinear time , author=. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2010 , organization=

    2010

  7. [7]

    Journal of Combinatorial Theory, Series A , volume=

    Small deviations of sums of independent random variables , author=. Journal of Combinatorial Theory, Series A , volume=. 2020 , publisher=

    2020

  8. [8]

    Bounding probability of small deviation on sum of independent random variables:

    Guo, Jiayi and He, Simai and Ling, Zi and Liu, Yicheng , journal=. Bounding probability of small deviation on sum of independent random variables:

  9. [9]

    Bounding probability of small deviation:

    He, Simai and Zhang, Jiawei and Zhang, Shuzhong , journal=. Bounding probability of small deviation:. 2010 , publisher=

    2010

  10. [10]

    A generalization of

    Letwin, Brayden and Yaskin, Vladyslav , journal=. A generalization of

  11. [11]

    arXiv preprint arXiv:2607.18661 , year=

    Gaffke's confidence interval for the mean of bounded data is inadmissible but asymptotically efficient , author=. arXiv preprint arXiv:2607.18661 , year=

    Pith/arXiv arXiv

  12. [12]

    On some conjectures of

    Paulin, Roland , journal=. On some conjectures of

  13. [13]

    arXiv preprint arXiv:2607.08415 , year=

    An Exact Distribution-Free Test for Means of Nonnegative Random Variables , author=. arXiv preprint arXiv:2607.08415 , year=

    Pith/arXiv arXiv

  14. [14]

    Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation , pages=

    Simplified runtime analysis of estimation of distribution algorithms , author=. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation , pages=

    2015

  15. [15]

    Algorithmica , volume=

    Level-based analysis of the univariate marginal distribution algorithm , author=. Algorithmica , volume=. 2019 , publisher=

    2019

  16. [16]

    Oliveto , title =

    Andrei Lissovoi and Pietro S. Oliveto , title =. Journal of Artificial Intelligence Research , volume =. 2019 , doi =

    2019

  17. [17]

    Econometrica , volume=

    The speed of innovation diffusion in social networks , author=. Econometrica , volume=. 2020 , publisher=

    2020