OctoInformBeta

Boolean functions violate the square-root degree bound by arbitrary factors

Let nn be a positive integer, and let XX be uniform on the sign cube {−1,1}n\{-1,1\}^n. A Boolean function on this cube is a map f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}. Its real Fourier coefficient at S⊆{1,…,n}S\subseteq\{1,\ldots,n\} is f̂(S)=𝔼[f(X)∏i∈SXi]\widehat f(S)=\mathbb E[f(X)\prod_{i\in S}X_i]. Its Fourier degree is deg⁡(f)=max⁡{|S|:f̂(S)≠0}\deg(f)=\max\{|S|:\widehat f(S)\ne0\}, with degree zero for constants. The signed singleton sum is ∑i=1nf̂({i})\sum_{i=1}^n\widehat f(\{i\}). The square-root question asks whether this sum is bounded by a fixed constant multiple of deg⁡(f)\sqrt{\deg(f)} on every finite sign cube.

The preprint recalls the dimension bound ∑i=1nf̂({i})≤n\sum_{i=1}^n\widehat f(\{i\})\le\sqrt n. It also recalls the universal linear bound ∑i=1n|f̂({i})|≤deg⁡(f)\sum_{i=1}^n|\widehat f(\{i\})|\le\deg(f).

The preprint proves that for every real C>0C>0 there are a positive integer nn and a nonconstant Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} such that ∑i=1nf̂({i})>Cdeg⁡(f)\sum_{i=1}^n\widehat f(\{i\})>C\sqrt{\deg(f)}. The ratios ∑i=1n|f̂({i})|/deg⁡(f)\sum_{i=1}^n|\widehat f(\{i\})|/\sqrt{\deg(f)} are unbounded over nonconstant Boolean functions on finite sign cubes.

The Lean library BooleanFunctions is the reference for these pages because Lean has checked every result of the Lean library. Each result is stated as the Lean library states it, with a link to the Lean declaration behind it. Where the preprint states a result differently, its statement appears beside the Lean library’s statement. The preprint is a guide only for the order and names of the results.

The Lean library: BooleanFunctions

BooleanFunctions is a Lean library: 13 items, in four groups. Each has a page written by OctoInform, listed below.