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.
More from Research
- A Reddit user builds a Wan 2.2 continuation workflow with LoRAs and ComfyUI — SnooMacaroons1365 · 2026-07-28
- Kimi K3 reproduces RLVR findings without overclaiming, author says — infoxiao · 2026-07-28
- CASIA paper maps how long-horizon planning emerges in foundation-model agents — CASIA · 2026-07-28
- TriWorldBench launches the first benchmark for robot multi-view world models — 机器之心 · 2026-07-28
- A 5 MB McBess-style LoRA for Krea2 trained on 120 captioned images — Winter_unmuted · 2026-07-28
- GaussianGPT uses autoregressive next-token prediction to generate 3D Gaussian scenes — rsasaki0109 · 2026-07-28