Polynomial inverse Gowers conjecture for the U3U^3 norm

From papers

Let f:F2nF2f:\mathbb{F}_2^n\to\mathbb{F}_2 be a Boolean function, and let fU3\|f\|_{U^3} denote its Gowers U3U^3 norm. Polynomial inverse Gowers conjecture for the U3U^3 norm. If

fU3ϵ,\|f\|_{U^3}\ge\epsilon,

then there exists a quadratic polynomial p:F2nF2p:\mathbb{F}_2^n\to\mathbb{F}_2 such that

Pr[f(x)=p(x)]12+ϵO(1).\Pr[f(x)=p(x)]\ge\tfrac{1}{2}+\epsilon^{O(1)}.

The source notes that the inverse Gowers statement for U3U^3 was known with a non-polynomial quantitative bound, specifically of exponential type, and conjectures a polynomial dependence on ϵ\epsilon. The claim is open in the source context.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Shachar Lovett, “Equivalence of polynomial conjectures in additive combinatorics”, arXiv:1001.3356 (2010).

Solutions 0

No solutions have been posted yet.