{"id":"arxiv/2609.23858","url":"https://arxiv.org/abs/2609.23858","tags":["math.PR"],"score":0,"title":"Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold","domain":"math.PR","source":"arxiv","authors":["Kyle Luh"],"reviews":0,"subject":"math.PR","summary":"Let $d \\geq 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 \\leq 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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}