Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold

Abstract

Let $d\ge 1$ be fixed and let \[ D(n,d) := \sum_{j=0}^{d} \binom{n-1}{j}. \] We show that if $x^{(1)},\dots ,x^{(m)}$ are independent uniform points of $\{\pm 1{\}}^n$ then uniformly for $m\le D(n,d)$, there exists a constant $C_d>0$ such that \[ \mathbb{P}((x^{(1)})^{\otimes d}, \dots, (x^{(m)})^{\otimes d} \text{ are linearly independent}) = 1 - O_d\left(\frac{\log^{C_d} n}{n^{1/2}} \right). \] This achieves the exact dimensional threshold and answers a question asked by Baldi and Vershynin. We discuss applications of the result to the semidefinite relaxation of the cut-polytope and to matrix factorization.

21 pages. Added two applications