XSci

A Log-Star Comparison Between Expectation Threshold and Fractional Expectation Threshold

Xuan Fang, Tianyu Wang

Submitted by Xuan Fang

Published November 16, 2026 · Version v1, November 16, 2026 · DOI 10.66977/xsci.2611.002p

Combinatorics

Abstract

We proved a log-star comparison between the expectation threshold q(F)q(\mathcal F) and the fractional
expectation threshold qf(F)q_f(\mathcal F) for any nontrivial increasing family F\mathcal F on a finite ground set VV of size ∣V∣=N|V|=N. Specifically, we show that
qf(F)≤64log⁡2∗(N+2) q(F),q_f(\mathcal F)\le64\log_2^*(N+2)\,q(\mathcal F),
where log⁡2∗x\log_2^* x is the iterated logarithm of base-2.

Using similiar methods, one can extend this result to the following stronger form: there exists a universal constant C>0C>0 such that
qf(F)≤Cq(F)log⁡2∗(l(F)),qf(F)≤Cq(F)(1+log⁡2∗(VC⁡(min⁡F)+2)), q_f(\mathcal F)\le Cq(\mathcal F)\log_2^*(l(\mathcal F)),\quad q_f(\mathcal F)\le Cq(\mathcal F)\bigl(1+\log_2^*(\operatorname{VC}(\min\mathcal F)+2)\bigr),
where l(F):=max⁡{2,max⁡S∈min⁡F∣S∣}l(\mathcal F):=\max\{2,\max_{S\in\min\mathcal F}|S|\} and VC⁡(min⁡F)\operatorname{VC}(\min\mathcal F) denotes the VC-dimension of min⁡F\min\mathcal F.

On October 7, 2026, OpenAI released a result proving the equivalence of fractional and integral thresholds, which supersedes the findings in this note. The authors are keeping this note for historical reference.

View PDF