VibeMathedMath problems solved with AI
Sign in

The Friedgut-Kalai threshold-width conjecture for r-uniform hypergraph properties

For a nontrivial increasing property of rr-uniform hypergraphs on nn vertices invariant under relabelling, the transitive symmetry of the (nr)\binom nr edge coordinates gives threshold width O(1/log⁡n)O(1/\log n) by the Friedgut-Kalai method. Friedgut and Kalai (1996, Section 5) conjectured that the vertex symmetry does better: for each fixed rr the width from probability ε\varepsilon to 1−ε1-\varepsilon should be Or,ε((log⁡n)−r/(r−1))O_{r,\varepsilon}((\log n)^{-r/(r-1)}), the graph case being r=2r=2. Bourgain and Kalai reached exponent r/(r−1)−δr/(r-1)-\delta for the influence bound at the uniform measure. For every fixed r≥3r\ge3, is the threshold width of every such property Or,ε((log⁡n)−r/(r−1))O_{r,\varepsilon}((\log n)^{-r/(r-1)})?

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

What was actually shown

Theorem 1.1: for each r≥3r\ge3 there is CrC_r with Varp(f)≤CrIp(f)/(log⁡n)r/(r−1)\mathrm{Var}_p(f)\le C_rI_p(f)/(\log n)^{r/(r-1)} for every relabelling-invariant Boolean property of rr-uniform hypergraphs, every n≥rn\ge r and every 0<p<10<p<1, without monotonicity. Corollary 4.1: for nontrivial increasing properties the width from ε\varepsilon to 1−ε1-\varepsilon is Or(log⁡(1/ε)/(log⁡n)r/(r−1))O_r(\log(1/\varepsilon)/(\log n)^{r/(r-1)}). Not shown: explicit constants CrC_r or sharpness examples for each rr.

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, Theorem 1.1 and Corollary 4.1 were read against the conjecture as the manuscript quotes it. The proof (vertex-block restrictions with an r-uniform degree estimate) was not refereed. The family's Lean challenge SharpThreshold covers only graphs (r=2r=2), so this entry is not lean-checked.

Sources

Changelog1 change

Discussion