A Compressed Presentation of OpenAI's Proof of the Unique Games Theorem
We reconstruct the main argument of OpenAI's preprint "The Unique Games Theorem" (23 September 2026). Three earlier theorems are stated as inputs: Håstad's parity gap, the Khot–Minzer–Safra Grassmann expansion theorem, and Dinur–Steurer projection-game repetition. The remaining argument constructs stable nonlinear noise, extracts constant-output certificates, decodes them using only local information, and contradicts parallel repetition on clean coordinates. We retain the conditioning and parameter order on which these steps depend. The aim is a short, continuous proof for a reader comfortable with finite-field linear algebra and Fourier analysis on finite groups who has not read the preprint. We modify the root construction of the noise gadget, simplify certificate extraction, and rewrite the genericity proof; these changes are identified and proved explicitly, and are listed, with smaller ones, under Attribution. Status: an explanatory reconstruction prepared with Codex (OpenAI) and Claude (Anthropic). Its mathematical content received source-based reviews by AI agents; no human expert has reviewed it, and it does not certify the preprint. The files include the script and logs of our run of the Comparator check on OpenAI's Lean 4 formalization, which passed; that check concerns OpenAI's formal development, not this note (see Appendix A).
Authors
- Ariel Elboim (ORCID: https://orcid.org/0009-0001-1341-366X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-10-09
- DOI
- https://doi.org/10.5281/zenodo.23264901
- Citations
- 1
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint