Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.23858
curl -X POST /api/v1/records/arxiv/2609.23858/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23858/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'