Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 34 min ago
PreprintarXiv licencearXiv

Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold

  • Kyle Luh
Open at sourcePDFDOICite

Abstract

Let d ≥ 1 be fixed and let D(n,d) := ∑j=0d binomn−1j. We show that if x(1), …, x(m) are independent uniform points of {± 1}n then uniformly for m ≤ D(n,d), there exists a constant Cd > 0 such that ℙ((x(1))⊗ d, …, (x(m))⊗ d are linearly independent) = 1 − Od((logCd n)/n1/2 ). 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.

Related

  1. Independence Threshold for Collision Times of Many Planar Random Walks
    Ziyang Liu
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv
  2. The threshold for linear independence of multiple zeta values in positive characteristic
    Bo-Hae Im, Hojin Kim, Tuan Ngo Dac
    HALPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsHAL
  3. The satisfiability threshold of random linear equations over finite commutative rings
    Pu Gao, Theodore Morrison
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. A Universal Threshold Theory for Local Properties of Random Linear Codes
    Vinayak M. Kumar, Ray Li, Jonathan Mosheiff +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Almost every Boolean function has central threshold degree
    Martin Anthony
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{luh2026linear,
  title = {{Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold}},
  author = {Kyle Luh},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23858},
  eprint = {2609.23858},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23858},
}
RIS
TY  - UNPB
TI  - Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
AU  - Kyle Luh
PY  - 2026
DA  - 2026/09/24
PB  - arXiv
DO  - 10.48550/arxiv.2609.23858
UR  - https://arxiv.org/abs/2609.23858
AB  - Let d ≥ 1 be fixed and let D(n,d) := ∑_j=0^d binomn−1j. We show that if x^(1), …, x^(m) are independent uniform points of {± 1}^n then uniformly for m ≤ D(n,d), there exists a constant C_d > 0 such that ℙ((x^(1))^⊗ d, …, (x^(m))^⊗ d are linearly independent) = 1 − O_d((log^C_d n)/n^1/2 ). 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.
ER  -