Skip to main content
1 of 11
Turbo
  • 13.9k
  • 1
  • 27
  • 76

Probabilistic statement on bilinear forms

Given $B(x_1,\dots,x_n,y_1,\dots,y_n)=x'Ay$ a bilinear form with $rank(A)=r$ with $A\in\{0,1\}^{n\times n}$.

Denote $\mathsf{1_n}\in\{0,1\}^n$ as vector with $1$s.

Denote $J\in\{0,1\}^{n\times n}$ as matrix with $1$s.

Is it true $$\lim_{n\rightarrow\infty}\mathsf{P}\Bigg(\mathsf{1_n}'(J-A)\mathsf{1_n}>\frac{r^{1+\log_2r}}{\log_2r}\sum_{i=1}^{\log_2r}\frac{1}{2^i}\Bigg)\rightarrow1?$$

Turbo
  • 13.9k
  • 1
  • 27
  • 76