VibeMathedMath problems solved with AI
Sign in

The Friedgut-Kalai sharp-threshold conjecture: threshold width O(1/log^2 n) for monotone graph properties

For a nontrivial increasing graph property PP on nn vertices and 0<ε<1/20<\varepsilon<1/2, let pap_a be the edge probability at which G(n,p)G(n,p) has PP with probability aa. Friedgut and Kalai (1996), combining the KKL and BKKKL influence theorems with Russo's formula, proved p1−ε−pε≤Clog⁡(1/2ε)/log⁡np_{1-\varepsilon}-p_\varepsilon\le C\log(1/2\varepsilon)/\log n, observed that containing a clique of size about log⁡n\log n has width of order (log⁡n)−2(\log n)^{-2}, and conjectured that this is the truth (Conjecture 1.2). Bourgain and Kalai reached (log⁡n)−2+δ(\log n)^{-2+\delta} for every δ>0\delta>0. Is p1−ε−pε≤Clog⁡(1/2ε)/(log⁡n)2p_{1-\varepsilon}-p_\varepsilon\le C\log(1/2\varepsilon)/(\log n)^2 for every such property, with CC universal?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Random graphs, analysis of Boolean functions
Posed by
Ehud Friedgut and Gil Kalai
Year posed
1996
Years open
30y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
35 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: for every n≥2n\ge2, nontrivial increasing vertex-symmetric graph property and 0<ε<1/20<\varepsilon<1/2, p1−ε−pε≤219log⁡(1/(2ε))/(log⁡n)2p_{1-\varepsilon}-p_\varepsilon\le2^{19}\log(1/(2\varepsilon))/(\log n)^2. It follows from Theorem 1.2, Varp(f)≤217Ip(f)/(log⁡n)2\mathrm{Var}_p(f)\le2^{17}I_p(f)/(\log n)^2 for every vertex-symmetric Boolean ff and every 0<p<10<p<1, without monotonicity, which removes the (log⁡log⁡n)2(\log\log n)^2 loss of Kelman-Kindler-Lifshitz-Minzer-Safra at p=1/2p=1/2. The order is optimal for fixed ε\varepsilon (clique example). Not shown: the best constant, or where thresholds lie (a different question).

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscripts are authored 'OpenAI' and name no human author. The family has two manuscripts (September 25 and October 5, 2026); the hypergraph paper adapts the method of the graph paper.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction and Theorems 1.1-1.2 were read against Conjecture 1.2 as the manuscript states it. The proof (vertex-block random restrictions and a low-degree Fourier estimate) was not refereed. The challenge lean/ComparatorChallenges/SharpThreshold.json (theorem OAI.Problem313.sharp_threshold_width, solution module OAI.Combinatorics.SharpThreshold.Main, present at the pinned commit) is not in the formalization catalogue lean/formalization.yaml; it is found through lean/docs/186.md. Its statement was read here: for every n≥2n\ge2, every vertex-permutation-invariant, increasing, nontrivial Boolean function of the edge configuration and every 0<ε<1/20<\varepsilon<1/2, the difference of the (1−ε)(1-\varepsilon)- and ε\varepsilon-quantiles (infimum of p∈[0,1]p\in[0,1] with mean at least the level) is at most 219log⁡(1/(2ε))/(log⁡n)22^{19}\log(1/(2\varepsilon))/(\log n)^2. This states the headline claim. Not rebuilt here. Permitted axioms: propext, Quot.sound, Classical.choice.

Sources

Changelog1 change

Discussion