Factorization conjecture for concentrated homogeneous polynomials

Let x1,,xnx_1,\dots,x_n be independent and uniformly chosen from {1,1}\{-1,1\}, and let

f(x1,,xn)=1i1ikai1ikxi1xikf(x_1,\dots,x_n)=\sum_{1\leq i_1\dots\leq i_k}a_{i_1\dots i_k}x_{i_1}\dots x_{i_k}

be a degree-kk homogeneous polynomial with at least mnk1mn^{k-1} nonzero coefficients. Polynomial factorization conjecture. If the concentration satisfies

supcP(f(x1,,xn)=c)=Ωk(mk/2+ϵ),\sup_c\mathbb{P}(f(x_1,\dots,x_n)=c)=\Omega_k(m^{-k/2+\epsilon}),

then ff differs in only a few coefficients from a polynomial which factors. The same passage also conjectures the upper bound supcP(f(x1,,xn)=c)=O(m1/2)\sup_c\mathbb{P}(f(x_1,\dots,x_n)=c)=O(m^{-1/2}) under the stated coefficient-count hypothesis.

Sources & referencesView supporting material

Primary source

Kevin P. Costello, “Bilinear and Quadratic Variants on the Littlewood-Offord Problem”, arXiv:0902.1538 (2009).

Additional references

2 papers in this index state this conjecture (2007–2009). The statement above is taken from the most recent of them; the others are arXiv:0704.2953.

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.