ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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

f(x1,…,xn)=∑1≤i1⋯≤ikai1…ikxi1…xikf(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 mnk−1mn^{k-1} nonzero coefficients. Polynomial factorization conjecture. If the concentration satisfies

sup⁡cP(f(x1,…,xn)=c)=Ωk(m−k/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 sup⁡cP(f(x1,…,xn)=c)=O(m−1/2)\sup_c\mathbb{P}(f(x_1,\dots,x_n)=c)=O(m^{-1/2}) under the stated coefficient-count hypothesis.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.