Lean formalization and a new proof of Feige’s conjecture for $delta f\ge 1$
RexDouglass · x · 2026-07-28
A new arXiv paper proves a sharp small-deviation inequality for sums of independent nonnegative random variables and confirms Feige’s conjecture for the $delta f\ge 1$ case.
What the proof does
- For independent nonnegative $Xi$ with $\mathbb{E}Xi\le 1$, it lower-bounds
$\mathbb{P}(S<\mathbb{E}S+\delta)$ by an explicit sharp bound $b{n,\delta}$.
- When $\delta\ge 1$, the bound is sharp and implies $b{n,\delta}\ge e^{-1}$, proving Feige’s conjecture in that regime.
How it is proved
- The argument combines a recent result by Vlassis and Thomas on Gaffke’s conjecture in statistics.
- It also uses convex-geometry tools, especially Grünbaum’s centroid halfspace theorem and a generalization by Letwin and Yaskin.
- The proof has been formalized end-to-end in Lean.
The poster also notes that GPT-5.6 helped produce the proof sketch.
Related event: GPT-5.6 Reportedly Assists in Proving Long-Standing Feige's Conjecture(4 posts)→
More from Research
- MIT's Neil Thompson: AI comes for tasks before jobs, and fixed costs favor big firms — bigdata · 2026-10-16
- UMD's PAIR framework bridges perception and action in VLA models via bridge tokens — Kaixi Feng · 2026-10-16
- CI-MSE offline metric hits -0.87 Spearman correlation with real robot task success vs weak raw MSE — chris_j_paxton · 2026-10-16
- Colossal Biosciences uses AI to decode genetic switches behind the extinct dodo — castrotech · 2026-10-16
- Colossal Biosciences uses AI to identify gene switches in dodo de-extinction push — castrotech · 2026-10-16
- Cheng Lou open-sources Handwired: hand-written weights turn code into training-free neural nets — dotey · 2026-10-16