{"id":"0e0463ef-b683-49d4-bcc0-3510fd5668dd","arxiv_id":"2607.24528","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For independent nonnegative mean-one random variables, P(sum < n+1) is at least (n/(n+1))^n ≥ 1/e, proving Feige's conjecture with a matching extremal example.","lead":"A short proof establishes Feige's conjecture: n independent nonnegative random variables with mean one have P(sum < n+1) at least (n/(n+1))^n, hence at least 1/e. The argument uses a recent distribution-free p-value merger and a simplex half-space inequality, settling a long-open sharp lower-tail bound used in algorithms and combinatorics.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"No new internal objection: Theorem 1.3 follows cleanly, but only modulo the explicitly imported VT26 merger theorem.","rationale":"The reader identified the correct weakest assumption. Internally, the chain is short and checks out: Lemma 2.2 is a direct event inclusion plus the merger property; Lemma 2.5's half-space event implies ∑x_iD_i>1 because the threshold gives ∑x_iD_i>(∑x_i)/(n+δ)≥1; and the cap-volume formula algebraically equals δ(n/(n+δ))^n. At δ=1, the two-point example attains the bound. The reliance on [LY24] appears dimensionally and analytically consistent, while the reliance on [VT26] is openly stated and is the substantive external risk. I would not change the ACCEPT verdict on the basis of an explicitly cited theorem, but independent verification of that theorem remains the decisive check.","tokens_in":6927,"tokens_out":9272,"duration_ms":933136,"concrete_test":"Independently re-derive Theorem 2.4 of [VT26] under exactly Definition 2.1 here: arbitrary independent nonnegative X_i with E[X_i]≤1, with no additional iid, boundedness, or exchangeability hypothesis. An independent analytical proof or machine-checked formalization would settle the dependency; a counterexample would invalidate the reduction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The single load-bearing point is Theorem 2.4, quoted from [VT26]: K_n must be a merger for every collection of independent nonnegative variables with E[X_i]≤1. Lemma 2.2 converts that property directly into the desired lower-tail bound, and no independent merger proof is supplied. Thus, if the VT26 result has narrower hypotheses (for example, iid, bounded, or exchangeable variables) or its proof fails, the proof of Theorem 1.3 collapses. This is an explicit external dependency rather than a concealed gap. I did not find an internal mismatch: Lemma 2.5 uses the centered simplex with c=(∑x_i)/(n+1), q=(1−δ)/(n+δ)≤1/n, and the displayed Grünbaum-type bound simplifies exactly to δ(n/(n+δ))^n. The strict/non-strict inequalities are also measure-theoretically harmless.","agreement_with_reader":"agree"},"referee_report":{"model":"moonshotai/kimi-k3","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.","tokens_in":7018,"tokens_out":7253,"duration_ms":664976,"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":[{"comment":"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-","section":"§2, Theorem 2.4"},{"comment":"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","section":"§2, Lemma 2.5"},{"comment":"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.","section":"§3, Lemma 3.3"}],"minor_comments":[{"comment":"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.","section":"§1, Theorem 1.3"},{"comment":"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.","section":"§1, after Theorem 1.3"},{"comment":"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.","section":"§3, proof of Lemma 3.3"},{"comment":"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.","section":"References"},{"comment":"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.","section":"§2, Lemma 2.2"}],"recommendation":"minor_revision","confidential_remarks":"This is a four-page resolution of a well-known 2006 conjecture, and its correctness hinges almost entirely on two very recent unrefereed preprints ([VT26], arXiv 2026, resolving Gaffke's conjecture, and [LY24], arXiv 2024). The internal mathematics in the present manuscript is short and checks out, so the editorial risk concentrates on the status of those references; if [VT26] is sound and holds under the stated hypotheses, I see no internal obstacle. The authors disclose that the proof was found with GPT-5.6 assistance and independently verified by them; this is transparently handled and does not affect the mathematical assessment, but the editor may wish to note it given the novelty of such disclosures for a result of this profile. I recommend prompt handling given likely competing write-ups in this area."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This closes Feige's conjecture (the δ=1 case) with the sharp finite-n constant (n/(n+1))^n. That is the real news. Prior published constants stopped around 0.18; the two-point extremal example shows you cannot do better, so the problem is settled for the classical statement.\n\nWhat they do well is the reduction. They take the Dirichlet half-space function K_n from Vlassis–Thomas, note that it is a merger, and prove a clean geometric upper bound on K_n whenever the coordinates sum to at least n+δ (for δ≤1). The half-space inclusion plus the LY24 section probability simplify exactly to the claimed expression. Lemma 2.2 is elementary set inclusion. No free parameters, no circular encoding of 1/e, and the AI-assistance disclosure is honest. Section 3 on the admissible n=2 merger is useful context and recovers the known sharp two-variable form without overclaiming.\n\nThe soft spot is exactly the one the stress-test flags, and it is not hidden: the whole argument sits on VT26's theorem that K_n is a merger for independent nonnegative mean-≤1 variables. If that result is narrower than stated or fails, Theorem 1.3 collapses. Secondary dependence on LY24 is milder and checkable. Arbitrary-δ for general n stays open, which the authors say plainly. None of that undercuts the internal algebra of what they actually prove.\n\nThis is for people who work on concentration under minimal assumptions, randomized algorithms, or extremal combinatorics. It is short enough for a reading group and formally grounded enough that a serious editor should send it to referees rather than desk-reject. I would cite the sharp δ=1 bound. Engage with it; the dependency is explicit and the contribution is real.","headline":"Short, sharp proof of Feige's conjecture for δ=1 that cleanly reduces to the VT26 merger plus a simplex section bound.","tokens_in":7869,"tokens_out":471,"would_cite":true,"duration_ms":7947,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60E15","60F10","62G10"],"pacs":[],"model":"grok-4.5","headline":"Independent nonnegative mean-one random variables sum below n+1 with probability at least (n/(n+1))^n, which is at least 1/e.","keywords":["Feige's conjecture","lower-tail bounds","nonnegative random variables","mergers","Dirichlet distribution","simplex sections","concentration inequalities"],"falsifier":"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 α.","tokens_in":7822,"feed_emoji":"📉","tokens_out":951,"duration_ms":13039,"temperature":0.7,"pith_summary":"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.","feed_headline":"Feige's 1/e lower-tail bound is proved, sharp for every n","feed_subtitle":"Independent nonnegative mean-one variables sum below n+1 with probability at least (n/(n+1))^n","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Short proof of Feige's conjecture: sum tail at least 1/e","Feige bound holds: P(sum < n+1) ≥ (n/(n+1))^n for mean-one variables","Feige's conjecture settled, sharp for every n via two-point laws","Lower tail of nonnegative mean-one sums bounded by (n/(n+δ))^n","Gaffke route yields Feige: P(sum Xi < n+1) ≥ (n/(n+1))^n"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Short proof of Feige's conjecture: sum tail at least 1/e","Feige bound holds: P(sum < n+1) ≥ (n/(n+1))^n for mean-one variables","Feige's conjecture settled, sharp for every n via two-point laws","Lower tail of nonnegative mean-one sums bounded by (n/(n+δ))^n","Gaffke route yields Feige: P(sum Xi < n+1) ≥ (n/(n+1))^n"]},"model":"grok-4.5","effort":"low","cost_usd":0.002798,"raw_usage":{"total_tokens":950,"prompt_tokens":671,"num_sources_used":0,"completion_tokens":115,"cost_in_usd_ticks":27984000,"prompt_tokens_details":{"text_tokens":671,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":164,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":671,"tokens_out":115,"duration_ms":4538,"temperature":1.0,"reasoning_tokens":164,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T12:18:28.988324+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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 α.","supporting_citations":[],"review_version":1}