Vu's global rank resilience conjecture for Rademacher matrices

About 2 years old · traced to

Let M∈{±1}n×mM\in\{\pm1\}^{n\times m} with m≥nm\geq n, and let Res⁡(M)\operatorname{Res}(M) be the least number of entry-flips needed to produce from MM a matrix whose rank is strictly less than nn. Let M∼MnM\sim\mathcal{M}_n, where Mn\mathcal{M}_n is the distribution of n×nn\times n Rademacher matrices, whose entries are independent random variables taking the values −1-1 and 11 with probability 1/21/2 each. Vu's global rank resilience conjecture. One has

Res⁡(M)=(1/2+o(1))n\operatorname{Res}(M)=\left(1/2+o(1)\right)n

a.a.s. as n→∞n\to\infty. This strengthens the singularity estimate for random Rademacher matrices: exponential upper bounds on the singularity probability imply only a weaker lower bound of order n/log⁡nn/\log n for the resilience, whereas the conjecture predicts the optimal asymptotic value n/2n/2.

References

Primary source

Elad Aigner-Horev, Daniel Rosenberg and Roi Weiss, “Resilience of Rademacher chaos of low degree”, arXiv:2402.10504 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.