Inverse conjecture for polynomially concentrated bilinear forms

Let AA be an n×nn\times n matrix of nonzero entries, and let x,yx,y be chosen independently and uniformly from {1,1}n\{-1,1\}^n. For a matrix decomposition A=A1+A2+A3A=A_1+A_2+A_3, say that A1A_1 is a low-rank component, A2A_2 is a generalized-arithmetic-progression component, and A3A_3 is a sparse component according to the bounds below. Bilinear inverse conjecture. For any a>0a>0, there are constants a1,a2,a3a_1,a_2,a_3 and N0N_0 such that, for all n>N0n>N_0, if

supcP(xTAy=c)>na,\sup_c \mathbb{P}(x^TAy=c)>n^{-a},

then A=A1+A2+A3A=A_1+A_2+A_3, where A1A_1 has rank at most a1a_1, the entries of A2A_2 are drawn from a generalized arithmetic progression of rank at most a2a_2 and volume at most a3a_3, and A3A_3 contains at most n2/lognn^2/\log n nonzero entries. The conjecture proposes that algebraic low rank and arithmetic structure, together with combinations of these and a sparse error, are essentially the only sources of polynomial concentration for bilinear forms.

Sources & referencesView supporting material

Primary source

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

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.