3.1 Nets for level sets of MRLCD

The main result of this subsection is the following.

Proposition 3.3 Let $c_0, c_1 \in (0,1)$ . There exists $C_{3.3} = C_{3.3}(c_0,c_1) > 0$ for which the following holds. Let $\lambda \in (C_{3.3}/n, c_{2.3}/2)$ and $L \ge 1$ . For every $D \ge 1$ , $S_{D}$ has a $\beta$ -net $\mathcal{N}$ such that

\begin{equation*}\beta = \frac{L\sqrt{\log(2D)}}{D}, \quad |\mathcal{N}| \le D^{1/\lambda}\left(\frac{C_{3.3}D}{\sqrt{\log(2D)}}\right)^n\cdot\left(\frac{\sqrt{\log(2D)}}{\sqrt{\lambda n}}\right)^{c_{2.3}n/8}.\end{equation*}

Remark By changing $C_{3.3}$ by a constant factor, we can further assume that $\mathcal{N}\subseteq S_D$ . Also, the L dependence here is not optimal – one can save a factor of $L^{n(1-c_{2.3}/8)}$ by being more careful, although this does not affect the overall bounds if L is of constant order as in our application.

The proof of Proposition 3.3 relies on a bound on the size of nets for level sets of the LCD.

Lemma 3.4 (Corollary of Lemma 7.8 in [Reference Vershynin30]) Let $m \in \mathbb{N}$ , $D \ge 1$ , and $c\in(0,1)$ be such that $D > c\sqrt{m}\ge 2$ . There exists a constant C depending only on c for which the following holds. Let $\chi > 1$ , $L \ge 1$ , and $\lambda > 0$ . Then the set

\begin{equation*}\{x\in\sqrt{\chi\lambda}\mathbb{B}_2^{m}\,{:}\, c\sqrt{m} < D_L(x/\lVert{x}_2\rVert)\le D\}\end{equation*}

has a $\beta\sqrt{\chi\lambda}$ -net $\mathcal{N}$ such that

\begin{equation*}\beta = \frac{4L\sqrt{\log(2D)}}{D},\quad|\mathcal{N}|\le\left(\frac{CD}{\sqrt{m}}\right)^mD^2.\end{equation*}

Now we conclude the result.

Proof of Proposition 3.3. Let $r = \lceil \lambda n \rceil$ and $k = c_{2.5}(\lambda)n$ , so that $r | k$ by definition.

Let $v \in S_D$ . By paying a factor of at most $2^n$ in the size of our net, we may fix a realization of $\operatorname{Spread}(v)$ , which determines $\operatorname{Spread}_\lambda(v)$ and $\operatorname{Spread}_\lambda^j(v)$ for $1\le j\le k/r$ . We pay an additional factor of at most $2^n$ to reveal which sets $\operatorname{Spread}_\lambda^j(v)$ are in $\mathcal{J}_M(v)$ . Let $J\subseteq[k/r]$ be the collection of corresponding indices j. We see that $t \,{:\!=}\, |J|\ge k/(2r)$ by definition of median. Write $J = \{j_1,\ldots,j_t\}$ and let $I_i = \operatorname{Spread}_\lambda^{j_i}(v)$ .

Note that, given $I_1,\ldots,I_t$ , we know that $D_L(v_{I_i}/\lVert{v_{I_i}}_2\rVert)\le 2D$ for all $1\le i\le t$ . Moreover, since $I_i \subseteq \operatorname{Spread}_{\lambda}(v)$ , it follows that $\lVert{v_{I_i}}_2\rVert\le\sqrt{\chi\lambda}$ for some $\chi$ depending only on $c_0$ . Further, by [Reference Vershynin30, Lemma 6.2], it follows (again, since $I_i \subseteq \operatorname{Spread}_{\lambda}(v)$ ) that $D_L(v_{I_i}/\lVert{v_{I_i}}\rVert_2) \ge c\sqrt{\lceil \lambda n \rceil}$ for some c depending only on $c_0, c_1$ . Hence, by Lemma 3.4, we have a $\beta\sqrt{\chi\lambda}$ -net for $\{v_{I_i}\}_{v\in S_D}$ where

\begin{equation*}\beta = \frac{2L\sqrt{\log(4D)}}{D}\end{equation*}

of size at most

\begin{equation*}\left(\frac{CD}{\sqrt{\lceil\lambda n\rceil}}\right)^{\lceil\lambda n\rceil}D^2.\end{equation*}

Finally, we take a product of these nets over $1\le i\le t$ , along with a standard $\beta$ -net of $\mathbb{B}_2^{I_0}$ (this net has size at most $(1+3/\beta)^{|I_0|}$ ), where we let $I_0 = [n]\setminus(I_1\cup\cdots\cup I_t)$ , to obtain the desired conclusion upon adjusting the value of $\beta$ by standard arguments.

3.2 Anticoncentration via MRLCD

We derive anticoncentration for a fixed vector with respect to MRLCD; the key idea is to patch together anticoncentration estimates on different segments of the vector through the use of Lemma 2.9.

Let $L\ge p_0^{-1/2}$ , $\lambda \in (C^{\prime}_{3.5}L^2/n,c_{2.3})$ , $v \in \operatorname{Incomp}(c_0, c_1)$ , $J\subseteq\operatorname{Spread}_\lambda(v)$ , and $S_J = \sum_{k \in J}v_k \xi_k$ . Suppose that J is a union of sets in $\mathcal{I}_M(v)$ . Then for every $\epsilon \ge 0$ , we have for sufficiently large n (depending on $\epsilon_0, p_0, M_0, c_0, c_1$ ) that

\begin{equation*}\mathcal{L}(S_J,\epsilon) \le C_{3.5}L\left(\frac{\epsilon}{\sqrt{|J|/n}} + \frac{\sqrt{\lambda n/|J|}}{\widehat{MD}_{L}(v,\lambda)}\right).\end{equation*}

Remark The above proposition should be compared with [Reference Vershynin30, Proposition 6.9], which bounds the Lévy concentration function in terms of the regularized LCD. The key difference is that the term $\sqrt{|J|/n}$ in the denominator of our bound is replaced by $\sqrt{\lambda}$ , which is always smaller. In fact, in the application considered here, $\lambda$ must be chosen to be $O (1/\sqrt{n})$ , which makes the above proposition significantly more efficient than the corresponding proposition in [Reference Vershynin30] for most of the matrix row-vector products (which satisfy $|J|/n = \Theta(1)$ ).

Proof. Since $v\in\operatorname{Incomp}(c_0,c_1)$ , we have $\widehat{MD}_L(v,\lambda)\ge c\sqrt{\lceil\lambda n\rceil}$ for some c depending only on $c_0,c_1$ ([Reference Vershynin30, Lemma 6.2]).

First, assume that $\epsilon \le 1/(c\sqrt{n})$ . Let $r = \lceil \lambda n \rceil$ and $k = c_{2.5}(\lambda)n$ , so that $r | k$ by definition. For $i\in[k/r]$ , let

\begin{equation*}S_i = \sum_{k\in\operatorname{Spread}_\lambda^i(v)}v_k\xi_k.\end{equation*}

Let I be such that $J = \cup_{i\in I}\operatorname{Spread}_\lambda^i(v)$ . Since J is a union of sets in $\mathcal{I}_M(v)$ , and $D_L(v_I/\lVert{v_I}\rVert_2) \ge \widehat{MD}_L(v,\lambda)$ for each $I \in \mathcal{I}_M(v)$ , it follows by standard anticoncentration estimates based on the LCD (see [Reference Vershynin30, Proposition 6.9] for the logarithmic version), that there exists an absolute constant $C > 0$ such that

\begin{equation*}\mathcal{L}(S_i,\epsilon)\le CL\left(\frac{\epsilon}{\sqrt{\lambda}}+\frac{1}{\widehat{MD}_L(v,\lambda)}\right) < \frac{1}{2}\end{equation*}

for all $i\in I$ , where the latter inequality follows from the assumption that $\epsilon \le 1/(c\sqrt{n})$ , along with the lower bound on $\lambda$ (by taking $C^{\prime}_{3.5}$ sufficiently large depending on various parameters).

Now note that

\begin{equation*}S_J = \sum_{i\in I}S_i\end{equation*}

and that the $S_i$ are independent. Also, note that $|I| = |J|/\lceil\lambda n\rceil$ . Therefore, by Lemma 2.9, we have

\begin{align*}\mathcal{L}(S_J,\epsilon)&\le C_{2.9}\epsilon\left(\sum_{i\in I}\frac{\epsilon^2(1-\mathcal{L}(S_i,\epsilon))}{\mathcal{L}(S_i,\epsilon)^2}\right)^{-1/2}\\[3pt] &\le\frac{C_{2.9}\sqrt{2}}{\sqrt{|I|}}\max_{i\in I}\mathcal{L}(S_i,\epsilon)\le\frac{2C_{2.9}}{\sqrt{|J|/n}}\cdot CL\left(\epsilon+\frac{\sqrt{\lambda}}{\widehat{MD}_L(v,\lambda)}\right),\end{align*}

which proves the desired conclusion for $\epsilon \le 1/c\sqrt{n}$ .

Finally, for $\epsilon > 1/(c\sqrt{n})$ , we note that any interval of length $2\epsilon$ can be tiled by at most $2\epsilon/\epsilon_0$ intervals of length $2\epsilon_0$ , where $\epsilon_0 = 1/(2c\sqrt{n})$ . Moreover, for such $\epsilon_0$ , we have

\begin{equation*}\epsilon_0 + \frac{\sqrt{\lambda}}{\widehat{MD}_L(v,\lambda)} \le 4\epsilon_0.\end{equation*}

Hence, we have that for all $\epsilon > 1/(c\sqrt{n})$ ,

\begin{align*} \mathcal{L}(S_J, \epsilon) &\le \frac{2\epsilon}{\epsilon_0}\cdot\mathcal{L}(S_J, \epsilon_0)\\[3pt] &\le \frac{2\epsilon}{\epsilon_0}\cdot\frac{2C_{2.9}CL}{\sqrt{|J|/n}}\cdot 4\epsilon_0 \le {16C_{2.9}CL}\cdot \frac{\epsilon}{\sqrt{\lambda}},\end{align*}

as desired.

Next, we derive a small-ball result for (symmetric) matrix-vector products.

Let $\lambda \in (C_{3.6}/n, c_{3.6})$ and suppose that $v\in S_D$ (with MRLCD defined with respect to $\lambda, L$ ). Then, for any $u \in \mathbb{R}^{n}$ , we have

\begin{equation*}\mathbb{P}[\lVert{Av-u}\rVert_2\le K\beta\sqrt{n}]\le\left(\frac{C_{3.6}L^2\sqrt{\log(2D)}}{D}\right)^{n-\lceil\lambda n\rceil},\end{equation*}

where

\begin{equation*}\beta = \frac{L\sqrt{\log(2D)}}{D}.\end{equation*}

Proof. Fix $u \in \mathbb{R}^{n}$ and $v \in S_D$ . Note that for any permutation matrix P, $\lVert{Av-u}\rVert_2\le K\beta\sqrt{n}$ occurs if and only if

\begin{equation*}\lVert{(PAP^{-1})Pv-Pu}\rVert\le K\beta\sqrt{n}.\end{equation*}

Furthermore, $PAP^{-1} = PAP^\intercal$ has the same distribution as A. Therefore, we will be able to permute the indices of [n] at our convenience (depending on v).

In particular, we may assume that $\operatorname{Spread}_\lambda(v) = [c_{2.5}(\lambda)n]$ . Let $A_t = \{k\in[n]\,{:}\, t\lceil\lambda n\rceil < k\le (t+1)\lceil\lambda n\rceil\}$ (defined for $0\le t\le T-1$ ), where

\begin{equation*}T = \frac{c_{2.5}(\lambda)n}{\lceil\lambda n\rceil}.\end{equation*}

We may also assume that $A_{t} \in \mathcal{I}_M(v)$ for all $t\le \lceil T/2 \rceil - 1$ . Then, for all $\lceil\lambda n\rceil\le j\le c_{2.5}(\lambda)n$ , the set $J = [j]$ has a subset of at least half the size which satisfies the assumptions of Proposition 3.5 (namely, the union of the first $\lfloor j/\lceil\lambda n\rceil\rfloor$ sets $A_t$ ).

Therefore, Proposition 3.5 implies that for all L sufficiently large depending on the sub-Gaussian norm of $\xi$ , if $j\ge\lceil\lambda n\rceil$ and $\epsilon\ge 0$ , then

\begin{equation*}\mathcal{L}((Av-u)_j|(Av-u)_{j+1,\ldots,n},\epsilon)\le CC_{3.5}L\left(\frac{\epsilon}{\sqrt{j/n}}+\frac{\sqrt{\lambda n/j}}{D}\right),\end{equation*}

where C depends only on $c_0,c_1$ . Here, we have used that the first j elements of the $j\textrm{th}$ row are independent of rows $j+1,\dots,n$ , and that the Lévy concentration is monotone under removing independent random variables from a sum.

Let $j' = \min(j, c_{2.5}(\lambda)n)$ . Then, by Lemma 2.7, we deduce

\begin{align*}\mathbb{P}[\lVert{Av-u}\rVert_2\le K\beta\sqrt{n}]&\le\mathbb{P}\left[\sum_{j = \lceil \lambda n \rceil}^{n} (Av-u)_{j}^{2} \le K^{2}\beta^{2} n\right]\\[3pt] &\le (CL)^n\prod_{j=\lceil\lambda n\rceil}^n\left(\frac{K\beta\sqrt{n/(n-\lceil\lambda n\rceil)}}{\sqrt{j'/n}}+\frac{\sqrt{\lambda n/j'}}{D}\right)\\[3pt] &\le (CL)^n\prod_{j=\lceil\lambda n\rceil}^n\left(\frac{KL\sqrt{n\log(2D)}}{D\sqrt{j'}}\right)\\[3pt] &\le\left(\frac{CL^2\sqrt{\log(2D)}}{D}\right)^{n-\lceil\lambda n\rceil},\end{align*}

where the last inequality uses $\prod_{j=1}^n(n/j)\le e^n$ .

3.3 Structure theorem

We will need the following structure theorem, which shows that, except with exponentially small probability, the preimage under A of any fixed vector is highly unstructured. This is our replacement for the key [Reference Vershynin30, Theorem 7.1]. As usual, A denotes a random $n\times n$ symmetric matrix with independent $\xi$ entries on and above the diagonal.

Theorem 3.7 Fix $K\ge 1$ . Depending on the sub-Gaussian norm of $\xi$ , we can choose L, c, C so that the following holds. For all $\lambda\in (C/n,1/\sqrt{n})$ , we have for any $u \in \mathbb{R}^{n}$ that

\begin{equation*}\mathbb{P}[\exists v\in\mathbb{S}^{n-1}\,{:}\, (Av\parallel u)\wedge(v\in\operatorname{Comp}(c_0,c_1)\vee\widehat{MD}_L(v,\lambda)\le 2^{\lambda n/C})\wedge(\lVert{A}\rVert\le K\sqrt{n})]\le 2e^{-cn}.\end{equation*}

Proof. This is an immediate consequence of Proposition 3.3, Lemmas 3.2 and 3.6. Note that if $Av = tu$ for $t\in\mathbb{R}$ , then $\lVert{A}\rVert\le K\sqrt{n}$ implies $\lVert{tu}\rVert_2\le K\sqrt{n}$ . For compressible vectors v, we use Lemma 2.2 on a constant amount of target vectors parallel to u so as to cover the full range. For the rest, if the MRLCD is between D and 2D (for some $D\le 2^{\lambda n/C}$ ), we take a net constructed in Lemma 3.4 along with a $1/D$ -net for $\{tu\,{:}\, \lVert{tu}\rVert_2 \le K\sqrt{n}\}$ , which adds an additional (unimportant) factor of $KD\sqrt{n}$ to the size of our nets. Since

\begin{align*}KD\sqrt{n}\cdot D^{1/\lambda}\left(\frac{C_{3.3}D}{\sqrt{\log(2D)}}\right)^n\cdot&\left(\frac{\sqrt{\log(2D)}}{\sqrt{\lambda n}}\right)^{c_{2.3}n/8}\times\left(\frac{C_{3.6}L^2\sqrt{\log(2D)}}{D}\right)^{n-\lceil\lambda n\rceil}\\[2pt] &= KD\sqrt{n}\cdot D^{1/\lambda}\left(\frac{C'D}{\sqrt{\log(2D)}}\right)^{\lceil\lambda n\rceil}\left(\frac{\sqrt{\log(2D)}}{\sqrt{\lambda n}}\right)^{c_{2.3}n/8}\\[2pt] &\le C'^n\cdot 2^{\lambda^2n^2/C}\cdot (1/C)^{c_{2.3}n/16}\\[2pt] &\le C'^n2^{n/C}(1/C)^{c_{2.3}n/16},\end{align*}

the result follows by a union bound upon taking C sufficiently large. We omit the standard details, referring the reader to the proof of [Reference Vershynin30, Theorem 7.1] for a more detailed calculation.

4.1. Threshold of random lattice points

We next recall the key technical result of Tikhomirov [Reference Tikhomirov29], which upper bounds the number of vectors with “large” threshold within a lattice of appropriate size. The important fact is that the number of such vectors is superexponentially small compared to the size of the lattice, which is the key difference with the results coming from the MRLCD. First, we must establish some notation.

Theorem 4.4 (From [Reference Tikhomirov29, Corollary 4.3]). Let $\delta,\epsilon\in(0,1]$ , $p\in (0,1/2]$ , and $K,M\ge 1$ . There exist $n_{4.4} = n_{4.4}(\delta,\epsilon,K,M)\ge 1$ and $L_{4.4} = L_{4.4}(\delta,\epsilon,K) > 0$ such that the following holds. If $n\ge n_{4.4}$ , $1\le N\le (1-p+\epsilon)^{-n}$ , and $\mathcal{A}$ is $(N,n,K,\delta)$ -admissible, then

\begin{equation*}\bigg|\bigg\{x\in\mathcal{A}\,{:}\, \mathcal{L}\left(\sum_{i=1}^nb_ix_i,\sqrt{n}\right)\ge L_{4.4}N^{-1}\bigg\}\bigg|\le\exp(\!-\!Mn)|\mathcal{A}|,\end{equation*}

where the $b_i$ are i.i.d. $\operatorname{Ber}(p)$ random variables. Furthermore, $n_{4.4} = \exp(C_{4.4}(\delta,\epsilon,K)M^2)$ is allowable.

Remark. This is the same as [Reference Tikhomirov29, Corollary 4.3], except that we have claimed an explicit dependence between n and M, namely that one can take M growing as $(\!\log n)^{1/2}$ (all other parameters fixed). This is an immediate consequence of unraveling the parameter dependencies in [Reference Tikhomirov29, Theorem 4.2]. We give a brief sketch, using the notation of [Reference Tikhomirov29, Theorem 4.2]. In the proof of [Reference Tikhomirov29, Theorem 4.2], one sets $L = L_{4.5}(2M,p,\delta,\epsilon/2)$ , which can be checked to grow exponentially in M by examining the last line of the proof of [Reference Tikhomirov29, Proposition 4.5]. This shows that the parameter q in the proof of [Reference Tikhomirov29, Theorem 4.2] is chosen to be linear in M, and hence, the parameter $\widetilde{\epsilon}$ grows as $M^{-1}$ . Next, it is required that $n\ge n_{4.10}(p,\widetilde{\epsilon},\max(16\widetilde{R},L),\widetilde{R},2M)$ and $n \ge n_{4.5}(2M, p, \delta, \epsilon/2)$ . The more restrictive condition comes from [Reference Tikhomirov29, Proposition 4.10], and indeed, an examination of the first few lines of the proof of this proposition reveals that it suffices to have n growing as $\exp(\Theta(M^{2}))$ . One also sees that $\eta_{4.2} = \eta_{4.10}(p,\widetilde{\epsilon},\max(16\widetilde{R},L),\widetilde{R},2M)$ decays as $\exp(\!-\Theta(M^{2}))$ . Finally, the deduction of [Reference Tikhomirov29, Corollary 4.3] from [Reference Tikhomirov29, Theorem 4.2] requires $n^{-1/2}\le\eta$ , for which n growing as $\exp(\Theta(M^{2}))$ is sufficient in light of the decay of $\eta$ discussed above.

4.2. Replacement

In order to relate the anticoncentration of a vector with respect to Rademacher random variables to Definition 4.1 and 4.2, we will require the following inequality. This is closely related to the replacement trick employed by Kahn et al. [Reference Kahn, Komlós and Szemerédi13] and later by Tao and Vu [Reference Tao and Vu28] (although the application here is substantially simpler).

Lemma 4.5 There exists an absolute constant $C_{4.5}$ for which the following holds. Let $v\in \mathbb{R}^n$ and $r> 0$ . Then, for any $0 < p \le (2-\sqrt{2})/4$ ,

\begin{equation*}\mathcal{L}\left(\sum_{i=1}^{n}b_iv_i,r\right)\le C_{4.5} \mathcal{L}\left(\sum_{i=1}^{n}b_i'v_i,r\right),\end{equation*}

where $b_i$ are independent Rademacher random variables and $b_i'$ are distributed as $\operatorname{Ber}(p)-\operatorname{Ber}'(p)$ .

Proof. Note that by scaling v, we may assume without loss of generality that $r = 1$ . Let $X = \sum_{i=1}^nb_i'v_i$ . By Esseen’s inequality and $|\cos t|\le (3+\cos(2t))/4$ , we find

\begin{align*}\mathcal{L}\left(\sum_{i=1}^nb_iv_i,1\right)&\le C\int_{-2}^2\prod_{i=1}^n|\cos(v_i\theta)|d\theta\le C\int_{-2}^2\prod_{i=1}^n\left(\frac{3}{4}+\frac{1}{4}\cos(2v_i\theta)\right)d\theta\\[3pt] &\le C\int_{-2}^2 \prod_{i=1}^{n}\mathbb{E}\exp\left(i\theta \cdot 2b_i'v_i\right)d\theta\le 2C\int_{\mathbb{R}}{1}_{[\!-2,2]}\ast{1}_{[\!-2,2]}(\theta)\mathbb{E}\exp(i\theta(2X))d\theta\\\end{align*}

\begin{align*} &= 4C\mathbb{E}\left(\frac{\sin(4X)}{2X}\right)^2\\[2pt] &\le 4C\mathbb{E}\left(\frac{\sin(4X)}{2X}\cdot {1}_{X\in [\!-1,1]}\right)^2 + \sum_{k=1}^{\infty}4C\mathbb{E}\left(\frac{\sin(4X)}{2X}\cdot {1}_{\pm X\in [2k-1, 2k+1]} \right)^2\\[2pt] &\le 16C\mathcal{L}(X,1) + C\sum_{k=1}^{\infty}\frac{\mathcal{L}(X,1)}{(2k-1)^{2}} \le C'\mathcal{L}(X,1).\end{align*}

The third inequality uses $p\le (2-\sqrt{2})/4$ , and the penultimate inequality uses $\sin(4x)/(2x) \le 2$ for $x \in [\!-1,1]$ .

4.3 Randomized rounding

We will make use of a slight modification of [Reference Tikhomirov29, Lemma 5.3], proved using randomized rounding (cf. [Reference Livshyts15]). As the proof is identical we omit the details.

Suppose that for all $t\ge \sqrt{n}$ ,

\begin{equation*}\mathbb{P}\bigg[\bigg|\sum_{i=1}^nb_iy_i-\psi\bigg|\le t\bigg]\le \mu t,\end{equation*}

where $(b_1,\dots, b_n)$ are independent and distributed as $\Delta$ . Then, there exists a vector $y' \in \mathbb{Z}^{n}$ satisfying

1. (R1) $\lVert{y-y'}\rVert_\infty\le 1$ ,

2. (R2) $\mathbb{P}[|\sum_{i=1}^nb_iy_i'-\psi|\le t]\le C_{4.6}\mu t$ for all $t\ge \sqrt{n}$ , and

3. (R3) $\mathcal{L}(\sum_{i=1}^nb_iy_i',\sqrt{n})\ge c_{4.6}\mathcal{L}(\sum_{i=1}^nb_iy_i,\sqrt{n})$ .

Next, we prove a version of the above proposition for the case when $\Delta = \operatorname{Ber}(p) - \operatorname{Ber}'(p)$ with p sufficiently small. The main difference is that the left hand side in (R2) above can be replaced by the Lévy concentration at width t; this can be done since for a distribution with non-negative characteristic function, the maximum concentration of given width is essentially obtained around $\psi = 0$ .

Suppose that for all $t\ge \sqrt{n}$ ,

\begin{equation*}\mathcal{L}\left(\sum_{i=1}^nb_i'y_i,t\right)\le\mu t,\end{equation*}

where the $b_i'$ are independent and distributed as $\operatorname{Ber}(p)-\operatorname{Ber}'(p)$ . Then, there exists a vector $y' = (y_1',\dots,y_n') \in \mathbb{Z}^{n}$ satisfying

1. (R1) $\lVert{y-y'}\rVert_\infty\le 1$ ,

2. (R2) $\mathcal{L}(\sum_{i=1}^nb_i'y_i',t)\le C_{4.7}\mu t$ for all $t\ge \sqrt{n}$ , and

3. (R3) $\mathcal{L}(\sum_{i=1}^nb_i'y_i',\sqrt{n})\ge c_{4.7}\mathcal{L}(\sum_{i=1}^nb_i'y_i,\sqrt{n})$ .

Proof. We apply Lemma 4.6 to the distribution $\Delta = \operatorname{Ber}(p)- \operatorname{Ber}'(p)$ and $\psi = 0$ . From (R2),

\begin{equation*}\mathbb{P}\bigg[\bigg|\sum_{i=1}^nb_i'y_i\bigg|\le t\bigg]\le C_{4.6}\mu t\end{equation*}

for all $t\ge\sqrt{n}$ . Now let $t\ge\sqrt{n}$ and $X = (\sum_{i=1}^nb_i'y_i')/t$ , and note that X has nonnegative characteristic function since $b_i'$ does. Thus, for all $\psi\in\mathbb{R}$ ,

\begin{align*}\mathbb{P}[|X-\psi|\le 1]&=\mathbb{E}[{1}_{[\!-1,1]}(X-\psi)]\le\mathbb{E}[{1}_{[\!-1,1]}\ast{1}_{[\!-1,1]}(X-\psi)]\\[3pt]&=\int_{\mathbb{R}}\left(\frac{2\sin\theta}{\theta}\right)^2\mathbb{E}\exp(i\theta(X-\psi))d\theta\\[3pt]&\le\int_{\mathbb{R}}\left(\frac{2\sin\theta}{\theta}\right)^2|\mathbb{E}\exp(i\theta X)|d\theta\\[3pt] &=\int_{\mathbb{R}}\left(\frac{2\sin\theta}{\theta}\right)^2\mathbb{E}\exp(i\theta X)d\theta\\[3pt] &= \mathbb{E}[{1}_{[\!-1,1]}\ast{1}_{[\!-1,1]}(X)]\le 2\mathbb{P}[|X|\le 2]\le 4C_{4.6}\mu t.\\[-35pt]\end{align*}

4.4 Threshold structure theorem

We now prove the following improved version of Theorem 3.7.

Theorem 4.8 Fix $K\ge 1$ and $0 < p\le (2-\sqrt{2})/4$ . We can choose $L, c > 0$ and $c' = c'(p)$ so that the following holds for sufficiently large n. For all $\lambda\in (n^{-2/3},c(\!\log n)^{1/4}n^{-1/2})$ , we have for any $u \in \mathbb{R}^{n}$ that

\begin{equation*}\mathbb{P}[\exists v\in\mathbb{S}^{n-1}\,{:}\, (Av\parallel u)\wedge(v\in\operatorname{Comp}(c_0,c_1)\vee\widehat{\mathcal{T}}_{p,L}(v,\lambda)\ge 2^{-c'\lambda n})\wedge(\lVert{A}\rVert\le K\sqrt{n})]\le 2e^{-cn},\end{equation*}

where A is a symmetric matrix with entries on and above the diagonal i.i.d. and distributed as the sum of a Rademacher random variable, and a Gaussian random variable of mean 0 and variance $n^{-2n}$ .

Remark The Gaussian perturbation of the entries of A is not important here and will only be used later, where it will be convenient to assume that various sub-matrices of A are invertible almost surely. Moreover, the variance of the Gaussian is chosen sufficiently small so that all anticoncentration claims that we need are essentially unaffected by this perturbation.

Proof. As in the proof of Theorem 3.7, we can deal with compressible vectors using Lemma 2.2. Therefore, it remains to deal with incompressible vectors with ‘large’ median threshold.

By standard small-ball estimates for incompressible vectors using a quantitative central limit theorem (see [Reference Tikhomirov29, Lemma 5.1]), for $v\in\operatorname{Incomp}(c_0,c_1)$ , there is $C_0 = C_0(p,c_0,c_1)$ such that $\widehat{\mathcal{T}}_{p,L}(v,\lambda)\le C_0(\lambda n)^{-1/2}$ . We let $r = \lceil\lambda n\rceil$ and $k = c_{2.5}(\lambda)n$ , so that $r|k$ by definition, and let $m = \lfloor k/(2r)\rfloor$ .

Step 1: Randomized rounding. We consider the case $\widehat{\mathcal{T}}_{p,L}(v,\lambda)\in[1/T,2/T]$ , where $T\in[C_0^{-1}\sqrt{\lambda n},2^{c'\lambda n}]$ . Then, by definition, there exist intervals $I_1,\ldots,I_m$ of the form $\operatorname{Spread}_\lambda^j(v)$ with

\begin{equation*}{\mathcal{T}}_{p,L}(v_{I_i}/\lVert{v_{I_i}}\rVert_2)\le 2/T\end{equation*}

for all $i\in[m]$ .

Let $D = C_1\sqrt{n}T$ , where $C_1 = C_1(p,c_0,c_1)\ge 1$ will be an integer chosen later. Let $y = Dv$ . By the definition of the threshold, for all $t\ge\sqrt{\lceil\lambda n\rceil}$ we have

\begin{align*}\mathcal{L}\left(\sum_{j\in I_i}b_j'y_j,t\right) &= \mathcal{L}\left(\sum_{j\in I_i}b_j'v_j,\frac{t}{D}\right) = \mathcal{L}\left(\sum_{j\in I_i}b_j'\frac{v_j}{\lVert{v_{I_i}}\rVert_{2}},\frac{t}{D\lVert{v_{I_i}}\rVert_{2} }\right)\\[3pt] &\le\mathcal{L}\left(\sum_{j\in I_i}b_j'\frac{v_j}{\lVert{v_{I_i}}\rVert_2},\frac{\sqrt{2}t}{c_1C_1\sqrt{\lceil\lambda n\rceil}T}\right)\le\frac{L}{T}\cdot\frac{2t}{\sqrt{\lceil\lambda n\rceil}},\end{align*}

as long as we chose $C_1 > \sqrt{2}/c_1$ , where the $b_i'$ are independent random variables distributed as $\operatorname{Ber}(p)-\operatorname{Ber}'(p)$ . Applying Lemma 4.7 to the $\lceil\lambda n\rceil$ -dimension vector $y_{I_i}$ , we see that there is $y_{I_i}^{\prime}\in\mathbb{Z}^{\lceil\lambda n\rceil}$ satisfying the conclusions of Lemma 4.7 (with n replaced by $\lceil\lambda n\rceil$ ). In particular, by (R3), we see that

(3) \begin{align} \mathcal{L}\left(\sum_{j\in I_i}b_j^{\prime}y_j^{\prime}, \sqrt{\lceil\lambda n\rceil}\right) &\ge c_{4.7}\mathcal{L}\left(\sum_{j\in I_i}b_j^{\prime}v_j, \sqrt{\lambda}/(C_1T)\right) \nonumber\\ & \ge c_{4.7}\mathcal{L}\left(\sum_{j\in I_i}b_j^{\prime}\frac{v_j}{\lVert{v_{I_i}}\rVert_{2}}, \frac{2\sqrt{\lambda}}{C_1T\cdot \sqrt{\lambda/c_0}}\right) \nonumber\\ &\ge C_1^{-1}\sqrt{c_0}\cdot c_{4.7}\mathcal{L}\left(\sum_{j\in I_i}b_j^{\prime}\frac{v_j}{\lVert{v_{I_i}}\rVert_2}, 2/T\right) \nonumber\\ &\ge C_1^{-1}\sqrt{c_0}\cdot c_{4.7}\cdot 2LT^{-1}.\end{align}

Let $I_0 = [n]\setminus (I_1 \cup \dots \cup I_m)$ . Then, by approximating each coordinate of $y_{I_0}$ by the nearest integer, and combining with the above integer approximations of $y_{I_1},\dots, y_{I_m}$ , we obtain an integer vector $y'\in\mathbb{Z}^n$ such that for all $1\leq i \leq m$ , the $\lceil \lambda n \rceil$ -dimensional integer vector $y^{\prime}_{I_i}$ satisfies $\|y_{I_i} - y^{\prime}_{I_i}\|_{\infty} \leq 1$ , (3), and

\begin{equation*}\mathcal{L}\left(\sum_{j \in I_i} b_j^{\prime}y_j^{\prime}, t \right) \leq C_{4.7}\frac{2L}{T\sqrt{\lceil \lambda n \rceil}} t, \quad \text{for all }t\geq \sqrt{\lceil \lambda n \rceil}.\end{equation*}

Step 2: Size of nets of level sets. We now estimate the number of possible realizations y’. This is the analogue of Proposition 3.3 in the present context. By paying an overall factor of at most $6^n$ , we may fix $\operatorname{Spread}(v)$ (hence all the $\operatorname{Spread}_\lambda^j(v)$ ), as well as which $\operatorname{Spread}_\lambda^j(v)$ are in $\mathcal{I}_M(v)$ and $\mathcal{J}_M(v)$ . As above, let us denote the intervals $\operatorname{Spread}_\lambda^j(v)$ in $\mathcal{I}_M(v)$ by $I_1,\dots, I_m$ , and let $I_0 = [n]\setminus (I_1\cup \dots \cup I_m)$ .

First, note that the number of choices for $y^{\prime}_{I_0}$ is at most $(CD/\sqrt{n})^{|I_0|}$ for an absolute constant C – this follows since $y^{\prime}_{I_0}$ is an integer point in a ball of radius $D \ge \sqrt{n} \ge \sqrt{|I_0|}$ (provided that $C_1$ is chosen sufficiently large), at which point, we can use a standard volumetric estimate for the number of integer points in $\mathbb{R}^{I_0}$ in a ball of radius $R \ge \sqrt{|I_0|}$ , together with the bound $|I_0| \ge n/2$ .

Next, we fix $i \in [m]$ , and bound the number of choices for $y^{\prime}_{I_i}$ . Note that for any $r \ge 0$ ,

\begin{equation*}\mathcal{L}\left(\sum_{j \in I_i}b_j y^{\prime}_j, r\right) \ge \mathcal{L}\left(\sum_{j \in I_i}(b_j - \widetilde{b}_j) y^{\prime}_j, r\right),\end{equation*}

where $b_i, \widetilde{b}_i$ are independent copies of $\operatorname{Ber}(p)$ . Since $b^{\prime}_j$ is distributed as $b_j - \widetilde{b}_j$ , it follows from (3) that

\begin{equation*}\mathcal{L}\left(\sum_{j\in I_i}b_jy_j^{\prime},\sqrt{\lceil\lambda n\rceil}\right)\ge c_2LN^{-1},\end{equation*}

where $b_j$ are i.i.d. $\operatorname{Ber}(p)$ random variables. From the definition of $\operatorname{Spread}_{\lambda}(v)$ and (R1), we see that $y_{I_i}^{\prime}$ lies within a $(D/(C_2\sqrt{n}),\lceil\lambda n\rceil,K',1)$ -admissible set $\mathcal{A}$ for $C_2$ and K’ sufficiently large depending on $c_0, c_1$ . Then, for L sufficiently large depending on $c_0, c_1, p$ , by Theorem 4.4 (noting that D is bounded by $n2^{c'\lambda n}$ for all sufficiently large n, and that we can take c’ to be sufficiently small depending on p), we deduce that the number of potential $y_{I_i}^{\prime}\in\mathbb{Z}^{I_i}$ is bounded by

\begin{equation*}\exp(\!-\!M|I_i|)(CD/\sqrt{n})^{|I_i|},\end{equation*}

where C depends on $c_0, c_1$ , and M grows as $\sqrt{\log\lceil\lambda n\rceil}$ , hence as $\sqrt{\log n}$ . Explicitly, we can pick $M\ge c_3\sqrt{\log n}$ for some small $c_3 > 0$ depending only on $c_0, c_1, p$ . Multiplying the total number of possibilities for $y^{\prime}_0,y^{\prime}_1,\dots, y^{\prime}_m$ , we see that the total number of possibilities for $y' \in \mathbb{Z}^{n}$ is at most

\begin{equation*}\exp(\!-\!c_{2.3}Mn/8)(CD/\sqrt{n})^n,\end{equation*}

for C depending on $c_0, c_1$ and $M \ge c_3 \sqrt{\log{n}}$ with $c_3$ depending on $c_0, c_1, p$ .

Step 3: Small-ball probability for net points. Fix $y' \in \mathbb{Z}^{n}$ resulting from the randomized rounding process and $u \in \mathbb{R}^{n}$ . Our goal is to bound $\mathbb{P}[\lVert{Ay'-u}\rVert_{2} \le Kn]$ . As in the proof of Lemma 3.6, we can without loss of generality permute the coordinates of y’ so that $I_1,\ldots,I_m$ are the first m blocks of size $\lceil\lambda n\rceil$ within [n]. Then, for all $\lceil\lambda n\rceil\le j\le c_{2.5}(\lambda)n$ , we have for all $\epsilon \ge 0$ that

\begin{equation*}\mathcal{L}((Ay'-u)_j|(Ay'-u)_{j+1,\ldots,n},D\epsilon)\le CL\left(\frac{\epsilon}{\sqrt{j/n}}+\frac{\sqrt{\lambda n/j}}{{T}}\right),\end{equation*}

where C is an absolute constant. To deduce this, we use that the first j elements of row j are independent of rows $j+1,\dots, n$ , then use Lemma 4.5 to replace the Rademacher entries of A (plus the small Gaussian perturbation, which has variance so small that it can be disregarded) by $\operatorname{Ber}(p)-\operatorname{Ber}'(p)$ , and finally use Lemma 2.9 (as in the proof of Proposition 3.5) to stitch together the Lévy concentration properties of each $y_{I_i}^{\prime}$ (guaranteed by (R3) of Lemma 4.7). Combining this with Lemma 2.7, we see that for y’, u as above,

\begin{equation*}\mathbb{P}[\lVert{Ay'-u}\rVert_{2} \le Kn]\le \left(\frac{C''L\sqrt{n}}{D}\right)^{n-\lceil\lambda n\rceil},\end{equation*}

where C $^{\prime\prime}$ depends only on $c_0, c_1, p$ .

Step 4: Union bound. On the event $\lVert{A}\rVert\le K\sqrt{n}$ , $Av = tu$ with $\lVert{tu}\rVert_{2} \le K\sqrt{n}$ . By splitting the range $\{tu\}$ into $(4D/\sqrt{n})^{2}$ intervals, and rounding v as in Step 2, we see that the probability of the event in question is bounded above by

\begin{equation*}\exp(\!-\!c_{2.3}Mn/8)\left(\frac{CD}{\sqrt{n}}\right)^{n+2}\sup_{y',u}\mathbb{P}[\lVert{Ay'-u}\rVert_2\le Kn],\end{equation*}

where the supremum is over $u \in \mathbb{R}^{n}$ and $y' \in \mathbb{Z}^{n}$ such that each $y_{I_i}^{\prime}$ for $i\in[m]$ satisfies the conclusions of Lemma 4.7 (with n replaced by $\lceil\lambda n\rceil$ ). Controlling the final factor by Step 3, we see that the probability is bounded above by

\begin{equation*}\exp(\!-\!c_{2.3}Mn/8)C^nD^{\lceil\lambda n\rceil+2},\end{equation*}

where C depends on $c_0, c_1, p$ . Finally, since $D\le 2^{2c'\lambda n}$ for all n sufficiently large (depending on $c_0, c_1, p$ ), we obtain an overall upper bound of

\begin{equation*}\exp(\!-\!c_{2.3}Mn/8 + n\log C + 2c'\lambda^2n^2 + 6c'\lambda n).\end{equation*}

Since $M \ge c_3 \sqrt{\log{n}}$ , for $c_3$ depending on $c_0, c_1, p$ , the desired result follows by choosing $\lambda < c(\!\log n)^{1/4}n^{-1/2}$ for c sufficiently small depending on $c_0, c_1, p$ , so that the quantity above is bounded by $\exp(\!-\Omega(n(\!\log n)^{1/2}))$ .

5.1 Quadratic small-ball probabilities

To prove Theorem 1.1 and 1.2, we need the following small-ball inequalities for quadratic forms. The derivation is almost identical to the approach in [Reference Vershynin30, Theorem 8.1], with improvements coming from Theorem 3.7 and Proposition 3.5 (respectively Theorem 4.8). We include details in the appendix for the reader’s convenience.

Theorem 5.1 Let A be an $n\times n$ symmetric random matrix whose independent entries are identical copies of a sub-Gaussian random variable $\xi$ with variance 1. Suppose X is a random vector (independent of A) whose entries are independent copies of $\xi$ . Then, for every $\epsilon\ge 0$ and $u\in\mathbb{R}$ , we have

\begin{equation*}\mathbb{P}\bigg[\frac{|\langle {A^{-1}X,X} \rangle-u|}{\sqrt{1+\lVert{A^{-1}X}\rVert_2^2}}\le\epsilon\wedge\lVert{A}\rVert\le K\sqrt{n}\bigg]\le C_{5.1}\epsilon^{1/8}+2\exp(\!-\!c_{5.1}n^{1/2}).\end{equation*}

We similarly derive the following strengthening for Rademacher entries.

Theorem 5.2 Let A be an $n\times n$ symmetric random matrix whose independent entries are distributed as the sum of a Rademacher random variable and a centred Gaussian with variance $n^{-2n}$ . Suppose X is a random vector (independent of A) whose entries are independent Rademachers. Then, for all sufficiently large n, and for every $\epsilon\ge 0$ and $u\in\mathbb{R}$ , we have

\begin{equation*}\mathbb{P}\bigg[\frac{|\langle {A^{-1}X,X} \rangle-u|}{\sqrt{1+\lVert{A^{-1}X}\rVert_2^2}}\le\epsilon\wedge\lVert{A}\rVert\le K\sqrt{n}\bigg]\le C_{5.1}\epsilon^{1/8}+2\exp(\!-\!c_{5.1}n^{1/2}(\!\log n)^{1/4}).\end{equation*}

5.2 Putting it together

Given the above, the proofs of Theorems 1.1 and 1.2 follows from a modification (due to Vershynin) of the invertibility-via-distance paradigm due to Rudelson and Vershynin. We reproduce the details from [Reference Vershynin30] for the reader’s convenience

Proof of Theorems 1.1 and 1.2. Fix $c_0, c_1,c \in (0,1)$ , as guaranteed by Lemma 2.2. We can clearly assume that $\epsilon \le c$ . Then, by the union bound and Lemma 2.2, we have

\begin{align*}\mathbb{P}[s_n(A)\le\epsilon/\sqrt{n}]&\le\mathbb{P}[\exists v\in\operatorname{Comp}(c_0,c_1)\,{:}\, \lVert{Av}\rVert_2\le c\sqrt{n}] + \mathbb{P}[\exists v\in\operatorname{Incomp}(c_0,c_1)\,{:}\, \lVert{Av}\rVert_2\le\epsilon/\sqrt{n}]\\&\le 2\exp(\!-\!cn) + \mathbb{P}[\exists v\in\operatorname{Incomp}(c_0,c_1)\,{:}\, \lVert{Av}\rVert_2\le\epsilon/\sqrt{n}].\end{align*}

Let $A_1,\dots, A_n$ denote the rows of A, and note that, by symmetry,

\begin{equation*}Av = \sum_{i=1}^nv_iA_i^T.\end{equation*}

In particular,

\begin{equation*}\lVert{Av}\rVert_2 \ge |v_i|\operatorname{dist}(A_i, H_i),\end{equation*}

where $H_i$ is the span of the rows $A_j$ for $j\neq i$ . Since $|v_i| \ge c_1/2\sqrt{n}$ for all $i \in \operatorname{Spread}(v)$ , it follows that if $\lVert{Av}\rVert_2 \le \epsilon/\sqrt{n}$ for some $v \in \operatorname{Incomp}(c_0, c_1)$ , then we must necessarily have

\begin{equation*}\operatorname{dist}(A_i,H_i)\le\frac{\epsilon\sqrt{2}}{c_1}\end{equation*}

for at least $c_{2.3}n$ indices $i \in [n]$ . Thus, we see that the probability that $s_n(A) \le \epsilon/\sqrt{n}$ is at most

\begin{equation*}2\exp(\!-\!cn) + \frac{1}{c_{2.3}n}\sum_{i=1}^n\mathbb{P}\bigg[\operatorname{dist}(A_i,H_i)\le\frac{\epsilon\sqrt{2}}{c_1}\bigg].\end{equation*}

Therefore, for Theorem 1.1 it suffices to show that

\begin{equation*}\mathbb{P}[\operatorname{dist}(A_1,H_1)\le\epsilon]\le C\epsilon^{1/8}+2\exp(\!-\!cn^{1/2}).\end{equation*}

A direct computation ([Reference Vershynin30, Proposition 5.1]) shows that

\begin{equation*}\operatorname{dist}(A_1,H_1) = \frac{|\langle {(A')^{-1}X,X} \rangle-a_{11}|}{\sqrt{1+\lVert{(A')^{-1}X}\rVert_2^2}},\end{equation*}

where A $^{\prime}$ is the bottom right $(n-1)\times(n-1)$ block of A, and X is the first column of A with the top element removed. At this point, we can apply Theorem 5.1 to conclude. If A has Rademacher entries, by continuity we can transfer the singular value estimate to the model where the distribution is perturbed by a centred Gaussian with sufficiently small variance, at which point, an application of Theorem 5.2 allows us to conclude.