Threshold parallel repetition for entangled games
From OpenAI Aftermath
Threshold parallel repetition for entangled games concerns two-player one-round games played with quantum entanglement: when the entangled value of a game is less than one, is the probability of winning at least a slightly larger fraction of many independent repetitions exponentially small in the number of repetitions? A manuscript dated 25 September 2026 in OpenAI's public mathematics collection (github.com/openai/math) claims such a threshold bound for every finite two-player game, with arbitrary correlated question distributions and finite-dimensional entangled strategies, and a universal rate. The collection includes a Lean formalization of a version of this bound. This page summarizes the published claim and lists publicly available follow-up work. Statements are the respective authors' claims; the publication of a paper, code or a formal proof is not presented here as independent verification.
Background
- As recounted in the introduction of the manuscript:
- For the classical value, Raz proved that the probability of winning every repetition decays exponentially, Holenstein simplified the argument with correlated sampling, and Rao proved exponential concentration above the classical value for general games.
- For entangled strategies, Cleve, Slofstra, Unger and Upadhyay treated XOR games, Kempe, Regev and Toner unique games, Dinur, Steurer and Vidick projection games, Jain, Pereszlényi and Yao free games (with an improved rate by Chailloux and Scarpa), and Chailloux and Scarpa complete-support question distributions. Yuen proved polynomial decay for arbitrary finite entangled games, and Bavarian, Vidick and Yuen obtained exponential amplification by anchoring, which adds questions to the game.
- Chapter 6 of OpenAI's separate publication Ten Advances in Mathematics and Theoretical Computer Science obtains exponential all-wins repetition for arbitrary finite entangled games, and Song improved the dependence on the gap to a cubic power; the manuscript describes these as its antecedents and uses Song's conditioning lemma.
The original result
- Claim. Theorem 1.1 of Threshold parallel repetition for finite-dimensional entangled games states that there is a universal constant κ0 > 0 such that for every finite two-player one-round game with entangled value v < 1, every 0 < δ < 1 − v, every number k of repetitions and every finite-dimensional joint strategy, the probability of winning at least ⌈(v + δ)k⌉ repetitions is at most exp[−κ0δ5k/(1 + log d)], where d is the product of the answer-set sizes; the same holds for the supremum over strategies. The question distribution may be correlated and may have zero entries. A further corollary gives a cubic rate in δ with a constant depending on the question distribution.
- Method, as described: a transfer from bounds after conditioning on tested coordinates to threshold bounds, whose selection of the tested set uses only the joint law of the binary win indicators, is combined with Song's conditioning estimate; the cubic bound for a fixed distribution is proved by constructing one reference state per component of the support.
- Sources. The manuscript Threshold parallel repetition for finite-dimensional entangled games at commit
1581d4c. - Formalization, as described by the repository. The scope note states that the formalization gives exponential threshold parallel repetition for every finite two-player game with arbitrary correlated questions, with the bound exp[−κδ13k/(1 + log(|A||B|))] for one universal κ > 0, for every joint finite-dimensional strategy and for their supremum, and that the distribution-dependent cubic bound is outside its scope. The manuscript notes that the rate with δ13 already follows from its Theorem 1.1. The Comparator statement is
EntangledGames.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-08 | MathVet (GitHub; review of openai/math, tables at repository commit c76f1e4, 14 October 2026) |
Review (fidelity of the formal statements) | Rates this family "full": the Lean statement gives, for one universal constant, the threshold bound with exponent δ13 for every joint finite-dimensional strategy and for the threshold value, with games given by an arbitrary correlated question distribution and the entangled value defined as a supremum, which it describes as exactly the summary's exponential threshold repetition. It records a sandboxed Comparator pass for the challenge. | MathVet states that it does not claim any theorem false and reports what was machine-checked as stated. |
| 2026-10-10 | cert-machine, openai/math lane K: run 38040214623 | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept the EntangledGames solution, in 360 s. The project reports two-kernel certification of 398 of 416 challenges of the collection. |
Repository. |
| 2026-10-10 to 2026-10-14 | con-leche development journal (task #348) | Verification (second kernel) | In its run over all Comparator challenges of the collection at commit fd4aeeb, the journal's table of exceptions (time-outs, memory, errors) does not list EntangledGames, so it was accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-15 | R. Jain, Parallel Repetition for Entangled Games via Conditional Relative Entropy, arXiv:2610.21410v1 | Related work (alternative proof and threshold bound) | Gives a proof, by quantum conditional relative entropy, of the cubic parallel-repetition bound exp[−Ω(ε3n/L)] for games of entangled value 1 − ε, recovering Song's rate, and proves the threshold bound exp[−Ω(δ5n/(ε2L))] for 0 < δ ≤ ε. Its introduction cites Chapter 6 of OpenAI's Ten Advances for exponential decay with gap power thirteen and states that OpenAI established threshold repetition for arbitrary finite entangled games, with a universal δ5 rate and a distribution-dependent cubic rate; it compares its approach with that framework as refined by Song. The acknowledgements state that ChatGPT assisted with mathematical exploration, checking calculations, revising the exposition and preparing the LaTeX source. | arXiv preprint, version 1 of 15 October 2026. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscript.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
