Talagrand's expectation-threshold and discrete-convexity conjectures
From OpenAI Aftermath
Talagrand's expectation-threshold and discrete-convexity conjectures are two problems from Talagrand's 2010 paper on whether many small sets are explicitly small. The first asks whether the fractional and integral expectation thresholds of an increasing family agree up to a universal factor; the second asks whether a bounded number of members of a sufficiently likely family cover every set outside an explicitly small exceptional family. Three manuscripts in OpenAI's public mathematics collection (github.com/openai/math), dated 23 September and 5 October 2026, claim both conjectures with explicit constants and, as an application, the graph-decomposition conjecture of Ascoli, He, Park and Talagrand. The collection includes a Lean formalization of the two conjectures. This page summarizes the published claims 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 introductions of the manuscripts:
- Kahn and Kalai conjectured that thresholds exceed integral expectation thresholds by at most a logarithmic factor. Frankston, Kahn, Narayanan and Park proved the fractional version, building on the sunflower methods of Alweiss, Lovett, Wu and Zhang, and Park and Pham proved the integral version.
- For discrete convexity, Park and Pham proved the positive-selector consequence; Hua, Song and Tudose resolved Talagrand's Gaussian convexity problem and derived a discrete conclusion with three unions; Li (arXiv:2609.08967) resolved the fractional form; and Ascoli, He, Park and Talagrand gave a threshold reformulation, proved cases for graph containment and formulated the graph-decomposition conjecture.
The original results
- Claim. Theorem 1.1 of Integral and fractional expectation thresholds are equivalent states that every nonempty proper increasing family on a finite set satisfies qf ≤ 25·5124·q, with both thresholds at cover budget 1/2; this is Talagrand's Conjecture 6.3. Theorem 1.1 of Talagrand's discrete-convexity conjecture states, with k = 275, that if a family has Bernoulli-p measure at least 1 − 1/k, then the sets not contained in a union of k of its members form a p-small family; this is Talagrand's Conjecture 7.1, with no monotonicity assumption. Graph Decompositions at the Integral Expectation Threshold states that the edges of every graph split into a universally bounded number of pieces, each with containment threshold at most a universal constant times the graph's integral expectation threshold, which is Conjecture 8.1 of Ascoli, He, Park and Talagrand; the embeddings of the pieces need not agree on shared vertices.
- Method, as described: the graph-decomposition manuscript uses the discrete-convexity theorem as an essential input: it places a labelled copy of the graph inside a bounded union of deterministic graphs from a likely class, and proves the remaining decomposition and embedding arguments itself.
- Sources. The manuscripts Integral and fractional expectation thresholds are equivalent, Talagrand's discrete-convexity conjecture and Graph Decompositions at the Integral Expectation Threshold at commit
1581d4c. - Formalization, as described by the repository. The scope note states that the formalization proves the expectation-threshold comparison with constant 25·5124 for every nonempty proper increasing family on a finite nonempty ground set, with fractional covers allowed to weight every subset, and the discrete-convexity assertion with k = 275 for every 0 < p < 1, with repeated members allowed and no monotonicity assumption. The Comparator statements are
TalagrandExpectationThreshold.leanandTalagrandDiscreteConvexity.lean.
Public follow-up work
| Date | Work | Relation | Public claim | Public status (checked 20 October 2026) |
|---|---|---|---|---|
| 2026-10-08 | X. Fang and T. Wang, A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold, arXiv:2609.30680v2 | Earlier partial result, superseded (author remark) | Proves qf ≤ 64 log2*(N + 2)·q for every nontrivial increasing family on a ground set of size N, with variants in terms of the size of minimal members and their VC-dimension. Version 2 adds that on 7 October 2026 OpenAI released a result proving the equivalence of the two thresholds, which supersedes the note, and that the note is kept for historical reference. | arXiv preprint; version 1 of 25 September 2026, version 2 of 8 October 2026. The paper states that its proof was developed by an AI model under the authors' guidance and checked by them. |
| 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 "partial": the two conjectures are stated with explicit constants, while the graph-decomposition application has no challenge statement. It records sandboxed Comparator passes for TalagrandExpectationThreshold and TalagrandDiscreteConvexity. |
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 38019899278: TalagrandExpectationThreshold and TalagrandDiscreteConvexity | Verification (two kernels) | Records that Lean's default kernel and the nanoda kernel accept both solutions, in 63 s and 64 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) lists neither challenge, so both were accepted by con-leche and by Lean's official kernel. |
Development journal. |
| 2026-10-16 | J. Jardine, Lattice24, referee review of the graph-decomposition manuscript in JJardine919/openai-math-audit (archived at Zenodo 10.5281/zenodo.23422995) | Review (AI-assisted audit) | Reports no gap and states that the reviewer read the whole paper and checked its lemmas line by line. Its one minor note is that the large-degeneracy case depends entirely on the companion discrete-convexity theorem, which the paper does not prove and the review did not verify; the reviewer calls this a disclosed dependency and adds that the argument would survive with a constant loss if the companion held only at a smaller parameter. | Part of an audit of the collection's manuscripts that the audit describes as complete. The reviews are published under CC BY 4.0. |
Notes
- The earlier results are due to the authors named in the Background section, as recounted by the manuscripts.
- Park and Talagrand (arXiv:2609.33644, 27 September 2026) explain an AI model's proof of a different conjecture from Talagrand's paper, his Conjecture 9.1.
- The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.
