combinatorics / Analysis of Boolean functions

The Gopalan-Servedio conjecture: is ∑if^({i})=O(deg⁡f)\sum_i\widehat f(\{i\})=O(\sqrt{\deg f}) for Boolean functions?

Theorem 1: for every C>0C>0 there is a nonconstant f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} with ∑if^({i})>Cdeg⁡f\sum_i\widehat f(\{i\})>C\sqrt{\deg f}; equivalently ∑i∣f^({i})∣/deg⁡f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f} is unbounded over Boolean functions of positive degree, so no constant multiple of the conjectured bound holds. The dimension and copy counts in the construction are finite but not usefully bounded, so no growth rate of the violation in terms of degree is given. The true order between deg⁡f\sqrt{\deg f} and the linear bound deg⁡f\deg f is left open.

14Significance / 100
1Frontier events
0Verification tasks
0Recorded attempts

Temporal state

Current frontier

No reconciled state yet.

Append-only history

Frontier timeline

combinatoricsSep 26, 2026Significance 14/100Registry: lean checked

The Gopalan-Servedio conjecture: is ∑if^({i})=O(deg⁡f)\sum_i\widehat f(\{i\})=O(\sqrt{\deg f}) for Boolean functions?

Prior state unknown→disproved

Theorem 1: for every C>0C>0 there is a nonconstant f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} with ∑if^({i})>Cdeg⁡f\sum_i\widehat f(\{i\})>C\sqrt{\deg f}; equivalently ∑i∣f^({i})∣/deg⁡f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f} is unbounded over Boolean functions of positive degree, so no constant multiple of the conjectured bound holds. The dimension and copy counts in the construction are finite but not usefully bounded, so no growth rate of the violation in term…

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Research memory

Claims and attempts

Scoped claims

Source authenticated

Theorem 1: for every C>0C>0 there is a nonconstant f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} with ∑if^({i})>Cdeg⁡f\sum_i\widehat f(\{i\})>C\sqrt{\deg f}; equivalently ∑i∣f^({i})∣/deg⁡f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f} is unbounded over Boolean functions of positive degree, so no constant multiple of the conjectured bound holds. The dimension and copy counts in the construction are finite but not usefully bounded, so no growth rate of the violation in terms of degree is given. The true order between deg⁡f\sqrt{\deg f} and the linear bound deg⁡f\deg f is left open.

Theorem 1: for every C>0C>0 there is a nonconstant f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} with ∑if^({i})>Cdeg⁡f\sum_i\widehat f(\{i\})>C\sqrt{\deg f}; equivalently ∑i∣f^({i})∣/deg⁡f\sum_i|\widehat f(\{i\})|/\sqrt{\deg f} is unbounded over Boolean functions of positive degree, so no constant multiple of the conjectured bound holds. The dimension and copy counts in the construction are finite but not usefully bounded, so no growth rate of the violation in terms of degree is given. The true order between deg⁡f\sqrt{\deg f} and the linear bound deg⁡f\deg f is left open.

Recorded attempts

Evidence graph

Connected research record