Polynomial inverse Gowers conjecture for the U3U^3 norm

About 16 years old · traced to

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

∥f∥U3≥ϵ,\|f\|_{U^3}\ge\epsilon,

then there exists a quadratic polynomial p:F2n→F2p:\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.