Kyle Luh

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{...