need to apply [FJLS21, Theorem 1.7] to obtain Eq. (6.20) and [FJ19, Corollary
3.11] to obtain Eq. (6.21). ∎

Here we remark that the arguments of [FJLS21, Theorem 1.7] and [FJ19,
Corollary 3.11] to bound ${\mathbf{G}}^{\prime}$ use a nice double counting
trick to exploit the largeness of $R_{k}^{\delta}({\mathbf{b}})$. Very roughly
speaking, because $R_{k}^{\delta}({\mathbf{b}})$ is large for all
${\mathbf{b}}\subset{\mathbf{a}}_{\operatorname{supp}({\mathbf{a}})}$, there
is a small index set $I$ over which if we fix the values of $w_{i}$ for $i\in
I$, the values of other $w_{j}$ will be determined.

While Theorem 6.18 above will suffice to study the symmetric and skew-
symmetric case, for the Laplacian case we will need to modify a bit. In what
follows $L$ stands for Laplacian, we define

$\displaystyle{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N):=$
$\displaystyle\Big{\\{}{\mathbf{a}}=(a_{1},\dots,a_{N})\in{\mathbb{F}}_{p}^{N},|\operatorname{supp}({\mathbf{a}})|=d,\forall{\mathbf{b}}\subset{\mathbf{a}}_{\operatorname{supp}({\mathbf{a}})}\textrm{
such that }s_{1}\leq|{\mathbf{b}}|\leq s_{2}$ $\displaystyle\text{ we have
}\rho_{L}({\mathbf{b}})\geq 3C(t+1)\sqrt{k}/(p\sqrt{s_{1}})\Big{\\}}.$

and

$\displaystyle{{\mathbf{G}}^{\prime}}_{L,d,k,s_{1},s_{2},\geq t}(N):=$
$\displaystyle\Big{\\{}{\mathbf{a}}\in{\mathbb{F}}_{p}^{N},|\operatorname{supp}({\mathbf{a}})|=d,\forall\Lambda\subset\operatorname{supp}({\mathbf{a}})\textrm{
such that }s_{1}\leq|\Lambda|\leq s_{2},$ $\displaystyle\text{ with
${\mathbf{b}}={\mathbf{a}}|_{\Lambda}$, we have
}R_{k}^{\delta}({\mathbf{b}}-a\mathbf{1})\geq
t\frac{2^{2k}|{\mathbf{b}}|^{2k}}{p}\text{ for some $a$}\Big{\\}}.$

Arguing as in the non-Laplacian case, by Theorem 6.15 we have

${\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq
t}(N)\subset{{\mathbf{G}}}^{\prime}_{L,d,k,s_{1},s_{2},\geq t}(N).$ (6.22)

We have the following

######  Proposition 6.23.

For $C$ sufficiently large given $\alpha$, the following holds for any
sufficiently small $\delta$. Let $p$ be a prime and let $1\leq t\leq p$ and
$1\leq s_{1}\leq s_{2}\leq d\leq N,$ and $1\leq k\leq s_{1}/2$ such that

$\frac{p}{t}\sqrt{\frac{s_{1}}{k}}\leq\min\\{e^{s_{1}/2k},(s_{1}/Ck)^{(1-\delta)k/2}\\}.$

We have that

$|{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)|\leq
p\binom{N}{d}2^{d+4}p^{d+s_{2}}(\delta t)^{-d(1-s_{1}/s_{2})}.$

###### Proof.

Consider ${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)$ with
$\operatorname{supp}({\mathbf{a}})=[d]$. Without loss of generality we assume
that $d$ is even (as the reader will see, if this is not the case we just need
to freeze another coordinate of ${\mathbf{a}}$). Define
${\mathbf{a}}^{\prime}=(a_{1}-a_{2},a_{3}-a_{4},\dots,a_{d-1}-a_{d})$ and
${\mathbf{a}}^{\prime\prime}=(a_{2}-a_{3},a_{4}-a_{5},\dots,a_{d}-a_{1})$.

Let ${\mathbf{b}}^{\prime}$ be any subvector of ${\mathbf{a}}^{\prime}$ with
$s_{1}/2\leq|{\mathbf{b}}^{\prime}|\leq s_{2}/2$, that is
${\mathbf{b}}^{\prime}$ has the form
$(a_{i_{1}}-a_{i_{1}+1},\dots,a_{i_{|{\mathbf{b}}^{\prime}|}}-a_{i_{|{\mathbf{b}}^{\prime}|}+1})$.
Then by (5.10)

$\rho_{\alpha/2}({\mathbf{b}}^{\prime})\geq\rho_{L,\alpha}(a_{i_{1}},a_{i_{1}+1},\dots,a_{i_{|{\mathbf{b}}^{\prime}|}},a_{i_{|{\mathbf{b}}^{\prime}|}+1})\geq
3C(t+1)\sqrt{k}/(p\sqrt{s_{1}}),$ (6.24)

where in the last estimate we used the fact that
${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)$.

Given $d^{\prime}$, we will consider the ${\mathbf{a}}^{\prime}$ with
$|\operatorname{supp}({\mathbf{a}}^{\prime})|=d^{\prime}$. We always have
$d^{\prime}\leq d/2$. First we consider the dominating case when $s_{2}/2\leq
d^{\prime}$. We apply Theorem 6.18 with the $(s_{1},s_{2},d,N,k)$ in that
theorem replaced by $(s_{1}/2,s_{2}/2,d^{\prime},d/2,\lfloor k/2\rfloor)$. By
(6.24) and by Theorem 6.18, the number of ${\mathbf{a}}^{\prime}$ with
$d^{\prime}=|\operatorname{supp}({\mathbf{a}}^{\prime})|$ that can come from
${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)$ is bounded by

$\binom{d/2}{d^{\prime}}p^{d^{\prime}+s_{2}/2}(\delta
t)^{-d^{\prime}(1-s_{1}/s_{2})}\leq\binom{d/2}{d^{\prime}}p^{d/2+s_{2}/2}(\delta
t)^{-(d/2)(1-s_{1}/s_{2})}=:{\mathcal{N}},$

as long as $C$ is large enough given $\alpha$.

Secondly, if $s_{1}/2\leq d^{\prime}\leq s_{2}/2$, by (6.20) the number of
such ${\mathbf{a}}^{\prime}$ is bounded by

$\binom{d/2}{d^{\prime}}p^{d^{\prime}}(\delta
t)^{-d^{\prime}+s_{1}/2}\leq\binom{d/2}{d^{\prime}}t^{s_{1}/2}(p/t)^{d^{\prime}}\delta^{-d^{\prime}+s_{1}/2}\leq\binom{d/2}{d^{\prime}}t^{(d/2)s_{1}/s_{2}}(p/t)^{d/2}\delta^{-(d/2)(1-s_{1}/s_{2})}\leq{\mathcal{N}}.$

Thirdly, if $d^{\prime}\leq s_{1}/2$ then the number of such vectors is simply
bounded by $\binom{d/2}{d^{\prime}}p^{s_{1}/2}\leq{\mathcal{N}}$ because as
$t\leq p$,

$p^{d/2+s_{2}/2}(\delta t)^{-(d/2)(1-s_{1}/s_{2})}\geq
p^{d/2+s_{2}/2}p^{-d/2}\geq p^{s_{2}/2}.$

Hence in total we see that the number of ${\mathbf{a}}^{\prime}$ with
$d^{\prime}=|\operatorname{supp}({\mathbf{a}}^{\prime})|$ that can come from
${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)$ is at most
$3{\mathcal{N}}$. Summing over $d^{\prime}$ we see that the number of
${\mathbf{a}}^{\prime}$ is at most

$3\times 2^{d/2}p^{d/2+s_{2}/2}(\delta t)^{-(d/2)(1-s_{1}/s_{2})}.$

We bound similarly for the number of ${\mathbf{a}}^{\prime\prime}$. Therefore
the number of $({\mathbf{a}}^{\prime},{\mathbf{a}}^{\prime\prime})$ is at most

$2^{d+4}p^{d+s_{2}}(\delta t)^{-d(1-s_{1}/s_{2})}.$

Finally, we remark that when ${\mathbf{a}}^{\prime}$ and
${\mathbf{a}}^{\prime\prime}$ are given, then any assignment of $a_{1}$ would
then determine the ${\mathbf{a}}$ they came from. Thus the number of
${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}(N)$ with
$\operatorname{supp}({\mathbf{a}})=[d]$ can be bounded by
$p2^{d+4}p^{d+s_{2}}(\delta t)^{-d(1-s_{1}/s_{2})}$. Multiplying by a factor
of $\binom{N}{d}$ to include ${\mathbf{a}}$ with any support of size $d$ gives
the result. ∎

In our application, ${\mathbf{a}}$ will be a generalized normal vector (with
respect to some given $Y_{0}$). In our next steps we will be working with
overwhelming events defined below.

######  Remark 6.25.

Let $N$ be a positive integer, $\delta>0$, $p$ be a prime such that
$8N^{12\delta}\leq p\leq\exp(N^{\delta/2})$, $Y_{0}\in{\mathbb{F}}_{p}^{N}$.

  * •

Let $G_{N}$ be either $M_{N}$ or $A_{N}$. Then let ${\mathcal{E}}_{non-
sparse}$ (implicitly depending on our choice of random matrix model and
$N,p,Y_{0},\delta$) be the event that for every nonzero
${\mathbf{a}}\in{\mathbb{F}}_{p}^{N}$ such that $L_{N}{\mathbf{a}}=Y_{0}$ in
at least $N-N^{\delta}$ coordinates, for any
$\Lambda\subset\operatorname{supp}({\mathbf{a}})$ with $s_{1}\leq|\Lambda|$
(for $s_{1}$ as in Definition 6.16)) we have

$N-s_{1}/2\leq|\operatorname{supp}({\mathbf{a}})|.$

  * •

Let ${\mathcal{E}}_{L,non-sparse}$ (implicitly depending on
$N,p,Y_{0},\delta$) be the event that for every nonzero
${\mathbf{a}}\in{\mathbb{F}}_{p}^{N}$ such that $L_{N}{\mathbf{v}}=Y_{0}$ in
at least $N-N^{\delta}$ coordinates, for any
$\Lambda\subset\operatorname{supp}({\mathbf{a}})$ with $s_{1}\leq|\Lambda|$
(for $s_{1}$ as in Definition 6.16)) we have

$|\Lambda|-s_{1}/2\leq|\operatorname{supp}({\mathbf{a}}-w\mathbf{1})_{\Lambda}|.$

By Lemma 6.5 (applied to $\lambda_{N}=n^{-4\delta}/2$) we have

${\mathbf{P}}({\mathcal{E}}_{non-sparse}),{\mathbf{P}}({\mathcal{E}}_{L,non-
sparse})\geq 1-\exp(-(N^{1-\delta})).$

Now for the set of non-sparse structured vectors, we decompose it into
disjoint union of sets of type

${\mathbf{G}}_{d,k,s_{1},s_{2},\geq
t_{i}}(N)\backslash{\mathbf{G}}_{d,k,s_{1},s_{2},\geq 2t_{i}}(N)\mbox{ or
}{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq
t_{i}}(N)\backslash{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq 2t_{i}}(N)$

from which we will take advantage of the counting results from Theorems 6.18
and 6.23 to show that it is unlikely for $G_{N}$ to have structured
generalized normal vectors.

######  Lemma 6.26.

Given $\alpha$, for any sufficiently small $\delta>0$ and any sufficiently
large $C$, there exists $C^{\prime}$ depending on $\delta,\alpha$ and $C$ such
that the following holds. Let $N,s_{1},k,t,d$ be positive integers and $p$ a
prime such that $N^{12\delta}\leq p\leq\exp(N^{\delta/2})$, and
$\frac{p}{t}\sqrt{\frac{s_{1}}{k}}\leq\min\\{e^{s_{1}/2k},(s_{1}/Ck)^{(1-\delta)k}\\},$
and $1\leq s_{1}\leq d\leq N,$ and $C\leq k\leq s_{1}$. We have the following

  * •

(symmetric and skew-symmetric) The event ${\mathcal{E}}_{non-sparse}$ and the
event that there exists ${\mathbf{a}}\in{\mathbf{G}}_{d,k,s_{1},s_{2},\geq
t}\backslash{\mathbf{G}}_{d,k,s_{1},s_{2},\geq 2t}$ such that
$G_{N}{\mathbf{a}}=Y_{0}$ in at least $N-N^{\delta/2}$ coordinates have
probability at most

$(C^{\prime})^{N}p^{N^{\delta/2}}(\frac{1}{p}+\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}\binom{N}{d}p^{d+s_{2}}(\delta
t)^{-d(1-s_{1}/s_{2})}.$

  * •

(Laplacian) The event ${\mathcal{E}}_{L,non-sparse}$ and the event that there
exists ${\mathbf{a}}\in{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq
t}\backslash{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq 2t}$ such that
$G_{N}{\mathbf{a}}=Y_{0}$ in at least $N-N^{\delta/2}$ coordinates have
probability at most

$(C^{\prime})^{N}p^{N^{\delta/2}}(\frac{1}{p}+\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}\times
p\times\binom{N}{d}2^{d+4}p^{d+s_{2}}(\delta t)^{-d(1-s_{1}/s_{2})}.$

Again, we will apply this result for the choice of parameters from Eq. (6.17)
and with $t$ satisfying
$\frac{p}{t}\sqrt{\frac{s_{1}}{k}}\leq\min\\{e^{s_{1}/2k},(s_{1}/Ck)^{(1-\delta)k}\\}$.

###### Proof of Lemma 6.26.

We will only explain the details in the Laplacian case, the cases of symmetric
and skew-symmetric matrices are similar. For a fixed ${\mathbf{a}}$ in
${\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq
t}(N)\backslash{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq 2t}(N)$ we show that the
event that $G_{N}{\mathbf{a}}=Y_{0}$ in at least $N-N^{\delta/2}$ coordinates
has probability at most

$2^{N}p^{N^{\delta/2}}(\frac{1}{p}+\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}.$
(6.27)

Note that on ${\mathcal{E}}_{L,non-sparse}$ of Lemma 6.5,
$|\operatorname{supp}({\mathbf{a}}-w\mathbf{1})|$ has order $N$ for all $w$.
Let ${\mathbf{b}}$ be the a subvector ${\mathbf{a}}_{\Lambda}$ such that
$\rho_{L}({\mathbf{b}})\leq\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}}$. Recall our
treatment from (6.3) and (6.4) that we can write

$G_{N}=\Big{(}\begin{array}[]{cc}G_{([N]\backslash\Lambda)\times([N]\backslash\Lambda)}&G_{([N]\backslash\Lambda)\times\Lambda}\\\
G_{\Lambda\times([N]\backslash\Lambda)}&G_{\Lambda\times\Lambda}\end{array}\Big{)}.$

Assume that we have to work with an event of type $G_{N}{\mathbf{a}}=Y_{0}$ in
all coordinates (after adding $p^{N^{\delta/2}}$ other possibilities for the
missing equalities). We will decompose our matrix as above and then consider a
system of $N-|\Lambda|$ equations

$G_{([N]\backslash\Lambda)\times([N]\backslash\Lambda)}{\mathbf{a}}_{[N]\backslash\Lambda}+G_{([N]\backslash\Lambda)\times\Lambda}{\mathbf{a}}_{\Lambda}=(Y_{0})_{[N]\backslash\Lambda}.$

If we condition on the entries of
$G_{([N]\backslash\Lambda)\times([N]\backslash\Lambda)}$, then we can view the
above as $G_{([N]\backslash\Lambda)\times I}{\mathbf{b}}=D$, where $D$ is
deterministic (after expanding out the diagonals in $L_{N}$, $D$ will depend
on the other entries not belonging to the above block), and we notice that now
the entries of $G_{([N]\backslash\Lambda)\times\Lambda}$ are i.i.d.. So we can
estimate the above probability by

${\mathbf{P}}(G_{([N]\backslash\Lambda)\times\Lambda}{\mathbf{b}}=D)\leq\prod_{i\in[N]\backslash\Lambda}(\frac{1}{p}+\rho({\mathbf{b}}-a_{i}\mathbf{1}))\leq(\frac{1}{p}+\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}},$
(6.28)

Summing over the support choice of $\binom{N}{N^{\delta/2}}$ coordinates, and
over other $p^{N^{\delta/2}}$ assignments of the unknown entries (toward
$G_{N}{\mathbf{a}}=Y_{0}$) we complete the proof of (6.27).

To complete the proof of Lemma 6.26, we use Theorem 6.23 and (6.27) to
estimate the probability under consideration by

$(C^{\prime})^{N}p^{N^{\delta/2}}(\frac{1}{p}+\frac{3C(t+1)\sqrt{k}}{p\sqrt{s_{1}}})^{n-s_{2}}\times
p\times\binom{N}{d}2^{d+4}p^{d+s_{2}}(\delta t)^{-d(1-s_{1}/s_{2})}.$

∎

Now we prove Proposition 5.19 (Proposition 5.18 can be shown similarly). We
will restate in the following form for the reader’s convenience.

######  Proposition 6.29.

Let $0<\lambda\leq 1$ be a given constant. There exist positive constants
$c_{1},c_{2},c_{3},c_{4}$ such that the following holds. Let $n,N$ be
sufficiently large positive integers and let $L_{n}$ be as in Theorem 1.22,
and let $L_{N}$ be the $[N]\times[N]$ submatrix of $L_{n}$. Let
$I_{0}\subset[N]$ be a (random) index set of size $\lfloor\lambda N\rfloor$
that might be depend on the randomness of $x_{kl},$ for $N+1\leq k\text{ or
}N+1\leq l$, but is independent of the randomness of $x_{kl},$ for $1\leq
k<l\leq N$. Let $p$ be a sufficiently large prime given $\lambda$ but
$p\leq\exp(N^{c_{1}})$. Then for any non-zero fixed vector
$Y_{0}\in{\mathbb{F}}_{p}^{N}$, with probability at least $1-\exp(-N^{c_{2}})$
for any vector ${\mathbf{v}}$ such that $L_{N}{\mathbf{v}}=Y_{0}$ in at least
$N-N^{c_{3}}$ coordinates we have

$\rho_{L}({\mathbf{v}}_{I_{0}})\leq\exp(-N^{c_{4}}).$

It is clear that Proposition 5.19 would follow by taking
$c=\min\\{c_{1},c_{2},c_{3},c_{4}\\}$.

###### Proof of Proposition 6.29.

For the proof, we choose some small $\delta>0$. In several steps, we will
require $\delta$ sufficiently small (in an absolute sense) and we can work
with any fixed $\delta$ that satisfies all the requirements. Throughout the
proof, all statements we make are assuming that $N$ is sufficiently large with
respect to $\lambda$ and $\delta$ (and since we take $\delta$ an absolute
constant in the end, this really only means $N$ is sufficiently large with
respect to $\lambda$). It suffices to prove the result assuming

$\lambda\leq\delta$ (6.30)

for some $0<\delta<1$ because the statement for $\delta<\lambda\leq 1$ will
follow from the monotonicity of Fact 6.12.

The choices for the parameters $c_{i}$ is somewhat flexible, but for instance
we can take

$c_{1}=c_{3}=c_{4}=\delta/2,c_{2}=1-2\delta.$

We let ${\mathcal{V}}$ denote the vectors ${\mathbf{v}}$ in
${\mathbb{F}}_{p}^{N}$ for which ${\mathbf{v}}-a\mathbf{1}$ has at least
$N-\lambda N/4$ non-zero coordinates for every $a$, and
${\mathcal{W}}_{I_{0}}$ the set of non-zero vectors
${\mathbf{v}}\in{\mathbb{F}}_{p}^{N}$ that such that we have

$\rho_{L}({\mathbf{v}}_{I_{0}})>e^{-N^{c_{4}}}.$

Observe that

$\displaystyle{\mathbf{P}}(\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}},\mbox{$(L_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$
in at least $N-N^{c_{3}}$ coordinates })$
$\displaystyle={\mathbf{P}}(\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap{\mathcal{V}},\mbox{
$(L_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$ in at least $N-N^{c_{3}}$ coordinates
})$
$\displaystyle+{\mathbf{P}}(\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap{\mathcal{V}}^{c},\mbox{
$(L_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$ in at least $N-N^{c_{3}}$ coordinates
}).$

By Lemma 6.5 (with $\lambda_{N}=\lambda/4$),

$\displaystyle{\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{V}}^{c},\mbox{
$(G_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$ in at least $N-N^{c_{3}}$
coordinates}\Big{)}\leq\exp(-N^{1-\delta}).$ (6.31)

Therefore, it suffices to focus on the event ${\mathcal{F}}$ that there exists
${\mathbf{v}}\in{\mathcal{V}}\cap{\mathcal{W}}_{I_{0}},$ such that
$G_{N}{\mathbf{v}}=Y_{0}$ in at least $N-N^{c_{3}}$ coordinates. We first
bound the event $\tilde{\mathcal{F}}$ that there exists
${\mathbf{v}}\in{\mathcal{V}}\cap{\mathcal{W}}_{I_{0}},$ such that
$(G_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$ for all $i$.

If $p$ is sufficiently large but $p\leq N^{12\delta}$, then as
${\mathbf{v}}\in{\mathcal{V}}$, we have that ${\mathbf{v}}_{I_{0}}$ has
highest multiplicity less than $|I_{0}|/4$ (because in ${\mathcal{V}}$, for
any $a$ the vector ${\mathbf{v}}_{I_{0}}-a\mathbf{1}$ has at least
$|I_{0}|-\lambda N/4$ non-zero coordinates). Hence we can apply Lemma 5.14,
provided that $\delta$ is small, to obtain that

$\rho_{L}({\mathbf{v}}_{I_{0}})\leq\exp(-N^{1/16}).$

We now assume $p>N^{12\delta}$. In what follows set

$\tau:=N^{1/16}\mbox{ and $k:=\lfloor N^{1/4}\rfloor,s_{1}:=\lfloor
N^{1-4\delta}\rfloor,s_{2}:=\lfloor N^{1-2\delta}/2\rfloor$}.$

We let $d\leq N$ be fixed with $d\geq s_{1}$, and let $C$ be a constant which
will have to be sufficiently large to an extent that will be specified later.

Note that any non-zero ${\mathbf{v}}$ resides in
${\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},>p}$ (because as
$R^{\delta}_{k}({\mathbf{w}})\leq R_{k}({\mathbf{w}})\leq
2^{2k}|{\mathbf{b}}|^{2k}$, for $t>p$ we have that
${\mathbf{G}}^{\prime}_{L,d,k,s_{1},s_{2},\geq t}$ is empty, and hence
${\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq t}$ is empty by (6.22)). $\clubsuit$
Hoi: [added this eqn.]

So with $j_{0}$ being the smallest integer such that $2^{j_{0}}\tau>p$, we
have an increasing nested sequence
$({\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},2^{j}\tau})_{j=0}^{j_{0}}$ and we can
partition ${\mathcal{V}}$ into union of disjoint sets

${\mathcal{V}}=({\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\geq\tau})\cup\bigcup_{j=1}^{j_{0}}({\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\geq
2^{j}\tau}\cap{\mathbf{G}}_{L,d,k,s_{1},s_{2},\geq 2^{j-1}\tau}).$

Let $X_{i}$ be the $i$th row of $L_{N}$. We then have that
${\mathbf{P}}(\tilde{\mathcal{F}})$ is

$\displaystyle{\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap{\mathcal{V}},{\mathbf{v}}\cdot
X_{i}=(Y_{0})_{i},1\leq i\leq
N\Big{)}={\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap{\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\tau},{\mathbf{v}}\cdot
X_{i}=(Y_{0})_{i},1\leq i\leq N\Big{)}$
$\displaystyle+\sum_{j=1}^{j_{0}}{\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap({\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},2^{j}\tau}\cap{\mathbf{G}}_{L,d,k,s_{1},s_{2},2^{j-1}\tau}),{\mathbf{v}}\cdot
X_{i}=(Y_{0})_{i},1\leq i\leq n\Big{)}.$

In what follows, without loss of generality we assume that $\lambda N$ is an
integer (otherwise one just replaces $\lambda N$ by $\lfloor\lambda N\rfloor$
in all estimates.)

Case 1. We begin with vectors in
${\mathcal{V}}\cap{\mathcal{W}}_{I_{0}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\tau}$.
Let $\tilde{\mathcal{F}}_{1}$ be the subevent of $\tilde{\mathcal{F}}$ that
there exists a vector ${\mathbf{v}}$ in
${\mathcal{V}}\cap{\mathcal{W}}_{I_{0}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\tau}$
such that $L_{N}{\mathbf{v}}=Y_{0}$. Note that as
${\mathbf{v}}\in{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\tau}$, we cannot hope for
structures of ${\mathbf{v}}$. However, because of the lower bound
$e^{-N^{c_{4}}}\leq\rho_{L}({\mathbf{v}}_{I_{0}})$, by Lemma 5.15 there exists
a generalized arithmetic progression $P$ of rank one in ${\mathbb{F}}_{p}$ and
of size $O(p/N^{c_{4}})$ that contains at least all but $N^{4c_{4}}$ entries
of ${\mathbf{v}}_{I_{0}}$. Note that the number of ways to choose such a $P$
is bounded by $p^{O(1)}$. For a fixed $P$, the number of vectors
${\mathbf{v}}_{I_{0}}$ with at least $\lambda N-N^{4c_{4}}$ components in $P$
is at most

$\binom{\lambda N}{\lfloor N^{4c_{4}}\rfloor}|P|^{\lambda
N-N^{4c_{4}}}p^{N^{4c_{4}}}\leq\binom{\lambda N}{\lfloor
N^{4c_{4}}\rfloor}O(p/N^{c_{4}})^{\lambda N-N^{4c_{4}}}p^{N^{4c_{4}}}\leq
O(1)^{\lambda N}(p/N^{c_{4}})^{\lambda N},$ (6.32)

where we used the fact that $p\leq\exp(N^{c_{1}})$ with small $c_{1},c_{4}$.

Together with $p^{O(1)}$ (which is trivially bounded by $O(1)^{N}$ as
$p\leq\exp(N^{c_{1}})$) number of ways to choose $P$, we thus have the
following.

######  Claim 6.33.

The total number of ${\mathbf{v}}_{I_{0}}$ (where $|I_{0}|=\lambda N$) with
$e^{-N^{c_{4}}}\leq\rho_{L}({\mathbf{v}}_{I_{0}})$ is at most $O(1)^{\lambda
N}(p/N^{c_{4}})^{\lambda N}$.

Our next step is similar to the proof of Lemma 6.5 (where there we started
with a subvector with high entry multiplicities) that we will try to saturate
${\mathbf{v}}$ until there is almost no (GAP-type) structure left.

We will conditioned on the $(x_{kl})_{N+1\leq k\text{ or }N+1\leq l}$ and
treat $I_{0}$ as fixed. Without loss of generality we assume that $I_{0}$ is
the set $[\lambda N]$ of the first $\lambda N$ indices.

Let $k_{0}:=\lfloor N^{1-\delta}\rfloor$. We then divide the index set
$[\lambda N+1,\dots,N]$ into subsequences $J_{1},\dots,J_{\ell}$ of
consecutive numbers so that $|J_{i}|=k_{0}$ for $i<\ell$ and
$k_{0}\leq|J_{\ell}|<2k_{0}$.

Given ${\mathbf{v}}$, we partition $[N]$ into two subsets, $I_{m}$ and
$I_{s}$. We let $I_{s}$ be the union of the $J_{i}$ such that
$\rho_{L}({\mathbf{v}}_{J_{i}})\geq e^{-N^{c_{4}}}$, along with $[\lambda N]$.
We let $I_{m}=[N]\backslash I_{s}$. We write
${\mathbf{v}}_{m}:={\mathbf{v}}_{I_{m}}$ and
${\mathbf{v}}_{s}:={\mathbf{v}}_{I_{s}}$.

Notice that as the index set of the components of ${\mathbf{v}}_{s}$ has the
form $I_{0}\cup_{l}J_{i_{l}}$, there are at most $2^{\ell}\leq 2^{N^{\delta}}$
such subsets (where we used the fact that $N$ sufficiently large given
$\delta,\lambda$).

Subcase 1.1. Let ${\mathcal{F}}_{1}$ be the event that there exists a
${\mathbf{v}}$ as in the definition of $\tilde{{\mathcal{F}}}_{1}$ such that
${\mathbf{v}}_{m}$ is empty. Then by repeatedly applying Claim 6.33 we obtain
that the number of such vectors ${\mathbf{v}}={\mathbf{v}}_{s}$ is bounded by

$O(1)^{\lambda N}(p/N^{c_{4}})^{\lambda N}\left(O(1)^{\lfloor
N^{1-\delta}\rfloor}(p/N^{c_{4}})^{\lfloor
N^{1-\delta}\rfloor}\right)^{N^{\delta}-\lambda N^{\delta}}O(1)^{2\lfloor
N^{1-\delta}\rfloor}(p/N^{c_{4}})^{2\lfloor
N^{1-\delta}\rfloor}=O(p^{2N}N^{-c_{4}N/8}),$ (6.34)

provided that $N$ is sufficiently large, where the first factor comes from the
number of ${\mathbf{v}}_{0}$, the second factor comes from the number of
${\mathbf{v}}_{J_{i}}$ for all $i<\ell$, and the third factor comes from the
number of ${\mathbf{v}}_{J_{\ell}}$.

Then the probability that any
${\mathbf{v}}\in{\mathcal{V}}\cap{\mathcal{W}}_{I_{0}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},\tau}$
of the above type and satisfies ${\mathbf{v}}\cdot X_{i}=(Y_{0})_{i},1\leq
i\leq N$ is bounded by (via (6.27), where we note that in the proof there we
exploited the randomness of $(x_{kl})_{k,l\in[N],k\neq l}$ only)

${\mathbf{P}}({\mathcal{F}}_{1})\leq
p^{2N}N^{-c_{4}N/8}\Big{(}\frac{1}{p}+\frac{3C(N^{1/16}+1)\sqrt{N^{1/4}}}{p\sqrt{N^{1/2}}}\Big{)}^{N-s_{2}}\leq
N^{-c_{4}N/9},$

where we used that $N^{12\delta}<p\leq\exp(N^{\delta/2}),s_{2}=\lfloor
N^{1-2\delta}/2\rfloor$ and $\tau=N^{1/16}$ and $N$ is sufficiently large and
$\delta$ is sufficiently small.

Subcase 1.2. Let ${\mathcal{F}}_{2}$ be the event that there exists a
${\mathbf{v}}$ as in the definition of $\tilde{{\mathcal{F}}}_{1}$ such that
${\mathbf{v}}_{m}$ is not empty. We have that $k=\lfloor
N^{1-\delta}\rfloor\leq|I_{m}|$ and $|I_{s}|\geq\lambda N$.

Similarly to the proof of Lemma 6.5, we now describe a function $f$ from
subsets of $[N]$ (that can occur as $I_{s}$) to subsets of $[N]$. We describe
$f(I_{s})$, and write $I_{m}$ for $[N]\setminus I_{s}$, but note that $f$ does
not depend on ${\mathbf{v}}$. If $|I_{s}|>|I_{m}|$, we let $f(I_{s})$ be the
first $|I_{m}|$ elements of $I_{s}$. Otherwise, we choose
$J_{i_{1}},\dots,J_{i_{l}}$ arbitrarily from $I_{m}$ so that
$|I_{s}|-N^{1-\delta}\leq|J_{i_{1}}|+\dots+|J_{i_{l}}|<|I_{s}|$ and let
$f(I_{s}):=[N]\backslash(J_{i_{1}}\cup\dots\cup J_{i_{l}})$. (Hence, to relate
to our proof of Lemma 6.5, the set $J^{\ast}$ there plays the role of
$J_{i_{1}}\cup\dots\cup J_{i_{l}}$, and $f(I_{s})$ is the union of $I_{s}$ and
the complement of $J^{\ast}$ in $I_{m}$.)

In either case, we have

$|f(I_{s})|\geq|I_{m}|\mbox{ and }|[N]\backslash
f(I_{s})|\geq|I_{s}|-N^{1-\delta}.$

Recall from the proof of Lemma 6.5 that ${\mathcal{E}}_{drop}$ is the event
that there is a square submatrix $G_{A\times B}$ of $G_{N}$ of dimension
$\geq\lfloor N^{1/2+\delta}\rfloor$ with rank less than $|A|-\lfloor
N^{1/2+\delta}\rfloor$ and we have ${\mathbf{P}}({\mathcal{E}}_{drop})\leq
e^{-c_{drop}N^{1+2\delta}},$ for some $c_{drop}>0$ depending on $\alpha$.

We wish to bound the probability of
$\mathcal{F}_{2}\setminus{\mathcal{E}}_{drop}$. Since for ${\mathbf{v}}$
causing $\mathcal{F}_{2}$, we have $|I_{m}|\geq N^{1-\delta}$, and hence
$|I_{m}|\geq\lfloor N^{1/2+\delta}\rfloor$ (by assuming $\delta<1/4$). So
outside of ${\mathcal{E}}_{drop}$, the matrix $G_{f(I_{s})\times I_{m}}$ has
rank $\geq|I_{m}|-\lfloor N^{1/2+\delta}\rfloor$, and hence it has a square
submatrix $G_{{{{{I^{\prime}_{s}}}}}\times{{I^{\prime}_{m}}}}$ of dimension
$|I_{m}|-\lfloor N^{1/2+\delta}\rfloor$ which has full rank.

Given subsets $M$, ${{I^{\prime}_{m}}}$, and ${{{{I^{\prime}_{s}}}}}$ of $[N]$
such that $|{{I^{\prime}_{m}}}|=|{{{{I^{\prime}_{s}}}}}|$ and
${{I^{\prime}_{m}}}\subset M$ and ${{{{I^{\prime}_{s}}}}}\subset
f([N]\setminus M)$, and such that $M$ is non-empty and can occur as $I_{m}$,
let $\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}})$ be the
event that there is a ${\mathbf{v}}\in{\mathbb{F}}_{p}^{N}$ such that
$\rho_{L}({\mathbf{v}}_{I_{0}})\geq e^{-N^{c_{4}}}$,
$G_{N}{\mathbf{v}}=Y_{0}$, and $I_{m}=M$, and
$G_{{{{{I^{\prime}_{s}}}}}\times{{I^{\prime}_{m}}}}$ is full rank. In
particular, above we just saw that
$\mathcal{F}_{2}\setminus{\mathcal{E}}_{drop}$ implies
$\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}})$ for some $M$,
${{I^{\prime}_{m}}}$, and ${{{{I^{\prime}_{s}}}}}$ with
$|M|-|{{I^{\prime}_{m}}}|=\lfloor N^{1/2+\delta}\rfloor$ and $N-|M|\geq\lambda
N$.

######  Claim 6.35.

For all $M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}}$ such that
$\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}})$ is defined,
we have

${\mathbf{P}}(\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}}))\leq
N^{-c_{4}\lambda N/9}.$

###### Proof.

By using Claim 6.33 over the $J_{i}$, as $|I_{s}|=N-|M|$, for ${\mathbf{v}}$
such that $\rho_{L}({\mathbf{v}}_{[\lambda N]})\geq e^{-N^{c_{4}}}$ and
$I_{m}=M$ there are at most

$O(1)^{\lambda N}(p/N^{c_{4}})^{\lambda N}\left(O(1)^{\lfloor
N^{1-\delta}\rfloor}(p/N^{c_{4}})^{\lfloor
N^{1-\delta}\rfloor}\right)^{(N-M-\lambda
N)/N^{1-\delta}}=O(1)^{N-M}p^{N-|M|}N^{-c_{4}(N-|M|)/8}$

choices of ${\mathbf{v}}_{I_{s}}$, and
$\binom{N}{N^{1/2+\delta}}p^{N^{1/2+\delta}}$ choices for
$({\mathbf{v}})_{I_{m}\backslash I_{m}^{\prime}}$. Let $F=f([N]\backslash M)$.
We condition on $L_{F\times[N]}$ and compute the conditional probability of
$\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}})$. If
$G_{{{{{I^{\prime}_{s}}}}}\times{{I^{\prime}_{m}}}}$ is not full rank, then
the desired (conditional) probability is $0$. Otherwise, as in the argument of
Claim 6.8, we have ${\mathbf{v}}_{I^{\prime}_{m}}$ is determined (and hence
the entire ${\mathbf{v}}$ is determined).

We let $J_{*}$ be one of the $J_{i}$ that is in $M$ but has no intersection
with $F$. For each $i\in([N]\setminus F)\setminus J_{*}$, we let $X_{i}$ be
the $i$th row of $G_{N}$. The equation $X_{i}{\mathbf{v}}=(Y_{0})_{i}$ implies

$\sum_{j\in
J_{*}}x_{ij}(v_{j}-v_{i})=(Y_{0})_{i}-\sum_{j\in[N]\setminus(J_{*}\cup\\{i\\})}x_{ij}(v_{j}-v_{i})+\sum_{j\in[n+1]\setminus[N]}x_{ij}v_{i}.$
(6.36)

The $x_{ij}$ for $i\in([N]\setminus F)\setminus J_{*}$ and $j\in J_{*}$ are
all independent. We further condition on $x_{ij}$ for $i\in([N]\setminus
F)\setminus J_{*}$ and $j\not\in J_{*}$. Since $J_{*}\cap F=\emptyset$, none
of the $x_{ij}$ for $i\in([N]\setminus F)\setminus J_{*}$ and $j\in J_{*}$
have been conditioned on. Thus after our conditioning, the probability of
(6.36) holding is at most $\rho_{L}({\mathbf{v}}_{J_{*}}).$ We have
$N-|F|-|J_{*}|$ independent such equations that are implied by
$G_{N}{\mathbf{v}}=Y_{0}$. Thus the probability that, for a given
${\mathbf{v}}_{s}$ and ${\mathbf{v}}_{I_{m}\setminus{{I^{\prime}_{m}}}},$ we
have the event in the claim, is at most

$\rho_{L}({\mathbf{v}}_{J_{*}})^{N-|F|-|J_{*}|}.$

Since $J_{*}$ is one of the $J_{i}$ that is a subset of $I_{m}$, by definition
of $I_{m}$ we have that

$\rho_{L}({\mathbf{v}}_{J_{*}})\leq e^{-N^{c_{4}}}+1/p.$

We have $|J_{*}|\leq 2\lfloor N^{1-\delta}\rfloor$ and
$|M|\leq|F|\leq|M|+N^{1-\delta}$. Thus the probability that, for a given
${\mathbf{v}}_{s}$ and ${\mathbf{v}}_{I_{m}\setminus{{I^{\prime}_{m}}}},$ we
have the event in the claim, is at most

$\left(e^{-N^{c_{4}}}+1/p\right)^{N-|M|-3\lfloor N^{1-\delta}\rfloor}.$

Summing over the possible values for ${\mathbf{v}}_{s}$ and
${\mathbf{v}}_{I_{m}\setminus{{I^{\prime}_{m}}}}$ (which are bounded in number
above), we obtain we thus obtain a probability bound

$O(1)^{N-M}p^{N-|M|}N^{-c_{4}(N-|M|)/8}\binom{N}{N^{1/2+\delta}}p^{N^{1/2+\delta}}(e^{-N^{c_{4}}}+1/p)^{N-|M|-3\lfloor
N^{1-\delta}\rfloor}\leq N^{-c_{4}\lambda N/9},$

where we used the fact that $\delta$ is sufficiently small (and
$c_{1}=c_{4}=\delta/2$) and $p\leq e^{N^{\delta/2}}$ and $|M|\leq N-\lambda
N$. ∎

The event ${\mathcal{F}}_{2}$ is the union of ${\mathcal{E}}_{drop}$ with
$\mathcal{F}_{2.1}(M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}})$ over
$M,{{I^{\prime}_{m}}},{{{{I^{\prime}_{s}}}}}$ with
$|M|-|{{I^{\prime}_{m}}}|=\lfloor N^{1/2+\delta}\rfloor$ and
$|N|-|M|\geq\lambda_{N}N$ and $M$ a possible value of $I_{m}$. There are at
most $2^{\ell}\leq 2^{2N^{\delta}}$ possible values of $I_{m}$ (and hence
$M$). Given $M$, there are at most $\binom{|M|}{\lfloor
N^{1/2+\delta}\rfloor}$ choices of ${{I^{\prime}_{m}}}$, and
$\binom{|f([N]\setminus M)|}{\lfloor
N^{1/2+\delta}\rfloor}\leq\binom{|M|+N^{1-\delta}}{\lfloor
N^{1/2+\delta}\rfloor}$ choices of ${{{{I^{\prime}_{s}}}}}$. Hence, we have

$\displaystyle{\mathbf{P}}({\mathcal{F}}_{2})$ $\displaystyle\leq
e^{-c_{drop}N^{1+2\delta}}+2^{2N^{\delta}}N^{2N^{1/2+\delta}}N^{-c_{4}\lambda
N/9}.$

Thus, for $\delta$ sufficiently small and $N$ sufficiently large given
$\delta$ and $\lambda$,

${\mathbf{P}}(\tilde{\mathcal{F}}_{1})\leq{\mathbf{P}}({\mathcal{F}}_{1})+{\mathbf{P}}({\mathcal{F}}_{2})\leq
N^{-c_{4}\lambda N/10}.$

For the next case, we use an argument similar to that in [FJLS21], but with a
modification for the Laplacian case from Theorem 6.23.

Case 2. We next consider the subevent $\tilde{\mathcal{F}}_{2}$ of
$\tilde{\mathcal{F}}$ that there exists a vector
${\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap\cup_{j=1}^{j_{0}}({\mathcal{V}}\cap{\mathbf{G}}_{L,d,k,s_{1},s_{2},2^{j}\tau}^{c}\wedge{\mathbf{G}}_{L,d,k,s_{1},s_{2},2^{j-1}\tau})$
such that $L_{N}{\mathbf{v}}=Y_{0}$. By Lemma 6.26 (where we can check that
all of the conditions are met we have for some sufficiently large
$C^{\prime}>0$ depending on $\delta$

$\displaystyle{\mathbf{P}}(\tilde{\mathcal{F}}_{2})\leq$
$\displaystyle\sum_{j=1}^{j_{0}}{\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{W}}_{I_{0}}\cap({\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},2^{j}\tau}\cap{\mathbf{G}}_{L,d,k,s_{1},s_{2},2^{j-1}\tau}),{\mathbf{v}}\cdot
X_{i}=(Y_{0})_{i},1\leq i\leq n\Big{)}$
$\displaystyle\leq\sum_{j=1}^{j_{0}}{\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in({\mathcal{V}}\cap{\mathbf{G}}^{c}_{L,d,k,s_{1},s_{2},2^{j}\tau}\cap{\mathbf{G}}_{L,d,k,s_{1},s_{2},2^{j-1}\tau}),{\mathbf{v}}\cdot
X_{i}=(Y_{0})_{i},1\leq i\leq n\Big{)}$
$\displaystyle\leq\binom{N}{d}\sum_{j=1}^{j_{0}}(C^{\prime})^{N}p^{N^{\delta/2}}\left(\frac{1}{p}+\frac{3C(2^{j-1}\tau+1)\sqrt{k}}{p\sqrt{s_{1}}}\right)^{N-s_{2}}2^{d+4}p^{d+s_{2}+1}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle\leq\binom{N}{d}2^{d+4}\sum_{j=1}^{j_{0}}(C^{\prime})^{N}p^{N^{\delta/2}}3^{N-s_{2}-1}\left[(\frac{1}{p})^{N-s_{2}}+(\frac{3C\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}+(\frac{3C2^{j-1}\tau\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}\right]p^{d+s_{2}+1}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle\leq\sum_{j=1}^{j_{0}}(12C^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}(\frac{1}{p})^{N-s_{2}}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle+\sum_{j=1}^{j_{0}}(36CC^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}(\frac{\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle+\sum_{j=1}^{j_{0}}(36CC^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}(\frac{2^{j-1}\tau\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}.$

Recall that $\tau=N^{1/16},k=\lfloor N^{1/4}\rfloor,s_{1}=\lfloor
N^{1-4\delta}\rfloor,s_{2}=\lfloor N^{1-2\delta}/2\rfloor$. It is clear that
the first two sums are bounded by $N^{-10\delta N}$ as long as $\delta$ is
sufficiently small and $p\geq N^{12\delta}$ and $N$ are sufficiently large
given $\delta$.

For the third sum, for $j=1$ we have

$(36CC^{\prime})^{N}(\frac{\tau\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}\tau^{-d(1-s_{1}/s_{2})}\leq(1/p)^{N/2}.$

The sum of other terms can be rewritten as

$\displaystyle\sum_{j=2}^{j_{0}}(36CC^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}(\frac{2^{j-1}\tau\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}(2^{j-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle=(36CC^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}\sum_{j=2}^{j_{0}}(\frac{\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}\tau^{N-s_{2}-d(1-s_{1}/s_{2})}2^{(j-1)(N-s_{2}-d(1-s_{1}/s_{2}))}.$

Note that $N-s_{2}-d(1-s_{1}/s_{2})\geq
N-s_{2}-N(1-s_{1}/s_{2})=Ns_{1}/s_{2}-s_{2}>0$ as $N$ is sufficiently large,
the above sum is clearly bounded by $(j_{0}-1)$ times the last summand when
$j=j_{0}$, and that last term is bounded by (where we recall that
$p<2^{j_{0}}\tau\leq 2p$)

$\displaystyle(36CC^{\prime})^{N}p^{N^{\delta/2}+d+s_{2}+1}(\frac{2^{j_{0}-1}\tau\sqrt{k}}{p\sqrt{s_{1}}})^{N-s_{2}}(2^{j_{0}-1}\tau)^{-d(1-s_{1}/s_{2})}$
$\displaystyle\leq(36CC^{\prime})^{N}2^{d}p^{N^{\delta/2}+d+s_{2}+1}(\frac{\sqrt{k}}{\sqrt{s_{1}}})^{N-s_{2}}p^{-d(1-s_{1}/s_{2})}$
$\displaystyle\leq(72CC^{\prime})^{N}p^{N^{\delta/2}+s_{2}+ds_{1}/s_{2}}(\frac{\sqrt{k}}{\sqrt{s_{1}}})^{N-s_{2}}\leq
N^{-N/4}$

because $d\leq N$ and $p\leq\exp(N^{c_{1}})$ where $c_{1}=\delta/2$ and we
take $\delta$ sufficiently small.

Combining the above estimates, by summing over all $d\leq N$, we can bound
${\mathbf{P}}(\tilde{\mathcal{F}}_{2})$ of Case 2 by

${\mathbf{P}}(\tilde{\mathcal{F}}_{2})\leq N^{-10\delta N}+N^{-N/4}.$

Putting the two cases together we conclude that

${\mathbf{P}}(\tilde{\mathcal{F}})={\mathbf{P}}\Big{(}\exists{\mathbf{v}}\in{\mathcal{V}}\cap{\mathcal{W}}_{I_{0}},\mbox{$(G_{N}{\mathbf{v}})_{i}=(Y_{0})_{i}$
for all $i$}\Big{)}\leq N^{-c_{4}\lambda N/10}+N^{-10\delta N}+N^{-N/4}\leq
3N^{-c_{4}\lambda N/10}$

as $c_{4}=\delta/2$ and $\delta$ is sufficiently small.

To bound the probability of ${\mathcal{F}}$, we need to account also for the
analog of $\tilde{\mathcal{F}}$ where $Y_{0}$ is replaced by any vector that
shares at least $N-N^{c_{3}}$ coordinates with it. This gives

$\binom{N}{N^{c_{3}}}p^{N^{c_{3}}}$

total events with the same probability bound as we showed above for
$\tilde{\mathcal{F}}$, whose union is ${\mathcal{F}}$. We then have

$\displaystyle{\mathbf{P}}({\mathcal{F}})\leq$
$\displaystyle\left(\binom{N}{N^{c_{3}}}p^{N^{c_{3}}}\right)3N^{-c_{4}\lambda
N/10}\leq N^{-c_{4}\lambda N/11},$

provided that $\delta$ is chosen sufficiently small. This, together with
(6.31), complete the proof of Proposition 6.29. ∎

##  7\. Treatment for moderate primes: proof of Propositions 2.1 and 2.3

We will be focusing mostly on the Laplacian case, the skew-symmetric and
symmetric cases will be discussed later (by a simpler argument). The plan for
the Laplacian matrix works as follows.

  1. (1)

We first sample $L_{n}$ using Phase 1 from Definition 1.23. For each
$N_{0}=\lfloor cn\rfloor\leq N\leq n$ (where $c$ is a sufficiently small
positive constant), we record the index set $I_{N+1}\subset[N]$ of $1\leq
j\leq N$ where $v_{j}$ has exactly one neighbor in $\\{v_{N+1},v_{N+2}\\}$.
Recall (1.27), by Chernoff’s bound with probability at least
$1-\exp(-\Theta(n))$ (with respect to $L_{n}$) we have for all $N_{0}\leq
N\leq n$

$(1/2-c)N\leq|I_{N+1}|\leq(1/2+c)N.$ (7.1)

  2. (2)

We notice that the random set $I_{N+1}$ is independent of the entries
$x_{ij},1\leq i<j\leq N$ of $L_{N}$. Hence for each $N_{0}\leq N\leq n$ we can
apply Proposition 5.19 to $L_{N}$ with $I_{0}=I_{N}$. To start with, when
$N=N_{0}$ let us call the event under consideration
${\mathcal{E}}_{N_{0}}^{\ast}$. This event belongs to the $\sigma$-algebra
generated by the random entries of $L_{n}$, and

${\mathbf{P}}({\mathcal{E}}_{N_{0}}^{\ast})\geq
1-O(\exp(-N^{c}))=1-O(\exp(-\Theta(n^{c}))).$ (7.2)

  3. (3)

We next reshuffle the neighbors of $v_{N_{0}+1}$ and $v_{N_{0}+2}$ to create
new randomness in the column corresponding to $v_{N_{0}+1}$. After adding this
column to $L_{N_{0}}$ we obtain $L_{N_{0}+1}^{\ast}$, where we use the
asterisk to distinguish with $L_{N_{0}+1}$ of $L_{n}$.

     * •

On the one hand, conditioning on ${\mathcal{E}}_{N_{0}}^{\ast}$, we can use
the randomness of the column corresponding to $v_{N_{0}+1}$ to study the rank
relation of $L_{N_{0}+1}^{\ast}$ with that of $L_{N_{0}}$.

     * •

By Fact 1.26, $L_{N_{0}+1}^{\ast}$ has the same distribution as $L_{N_{0}+1}$
(of $L_{n}$), hence we can apply Proposition 5.19 to $L_{N_{0}+1}^{\ast}$ with
respect to $I_{0}=I_{N_{0}+1}$. Let ${\mathcal{E}}_{N_{0}+1}^{\ast}$ denote
the overwhelming event obtained by this result (with probability similarly to
(7.2)), which now belongs to the sigma-algebra generated by $L_{n}$ and the
new random variables of the column corresponding to $v_{N_{0}+1}$.

We will repeat the process until $v_{n}$.

$L_{N}^{\ast}$$x_{N+1}$$I_{N+1}$$X_{N+1}$ Figure 3. Row and column exposure
process during reshuffling.

With the outline in mind, we will study the ranking evolution when moving from
$L_{N}^{\ast}$ to $L_{N+1}^{\ast}$.

######  Definition 7.3.

Given $I_{0}\subset[N]$. A random vector $X=(x_{1},\dots,x_{n})$ is called
$I_{0}$-adapted if the $x_{i}$ are i.i.d. copies of $\xi$ satisfying Eq. (1.2)
(for a given prime $p$) for all $i\in I_{0}$, while $x_{i},i\notin I_{0}$ are
deterministic (i.e. held fixed).

We first prove an elementary decoupling result to motivate our later treatment
(see also [CTV06, Map13b, KN22]).

######  Lemma 7.4.

Assume that $a_{ij}\in{\mathbb{Z}}/p{\mathbb{Z}}$ and $a_{ij}=a_{ji}$ and
$b_{i}\in{\mathbb{Z}}/p{\mathbb{Z}}$. Assume $X$ is as in 7.3 for a given
$I_{0}$. Then for any $I\subset[n]$ we have

$\sup_{r}|{\mathbf{P}}(\sum_{ij}a_{ij}x_{i}x_{j}+\sum_{i}b_{i}x_{i}=r)-1/p|^{4}\leq|{\mathbf{P}}(\sum_{i\in
I,j\in I^{c}}a_{ij}y_{i}y_{j}=0)-1/p|,$

where $y_{i},i\in I_{0}$ are i.i.d. copies of $\xi-\xi^{\prime}$.

###### Proof of Lemma 7.4.

For short we write $f(X)=\sum_{ij}a_{ij}x_{i}x_{j}+\sum_{i}b_{i}x_{i}$. We
write

$|{\mathbf{P}}(f(X)=r)-\frac{1}{p}|\leq\frac{1}{p}\sum_{t\neq
0}|{\mathbf{E}}e_{p}(-tf(X))|$

where $e_{p}(x)=e^{2\pi ix/p}$.

We then use Cauchy-Schwarz to complete squares,

$\displaystyle LHS^{2}\leq\frac{p-1}{p^{2}}\sum_{t\neq
0}|{\mathbf{E}}e_{p}(-tf(X))|^{2}$
$\displaystyle\leq\frac{p-1}{p^{2}}\sum_{t\neq
0}{\mathbf{E}}_{X_{I}}|{\mathbf{E}}_{X_{I^{c}}}e_{p}(-tf(X_{I},X_{I^{c}}))|^{2}$
$\displaystyle=\frac{p-1}{p^{2}}\sum_{t\neq
0}{\mathbf{E}}_{X_{I}}{\mathbf{E}}_{X_{I^{c}},X^{\prime}_{I^{c}}}e_{p}(-t[f(X_{I},X_{I^{c}})-f(X_{I},X_{I^{c}}^{\prime})])$
$\displaystyle=\frac{p-1}{p^{2}}\sum_{t\neq
0}{\mathbf{E}}_{X_{I^{c}},X^{\prime}_{I^{c}}}{\mathbf{E}}_{X_{I}}e_{p}(-t[f(X_{I},X_{I^{c}})-f(X_{I},X_{I^{c}}^{\prime})]).$

Using Cauchy-Schwarz once more,

$\displaystyle LHS^{4}$
$\displaystyle\leq(\frac{p-1}{p^{2}})^{2}(p-1)\sum_{t\neq
0}{\mathbf{E}}_{X_{I^{c}},X^{\prime}_{I^{c}}}{\mathbf{E}}_{X_{I},X_{I}^{\prime}}e_{p}(-t[f(X_{I},X_{I^{c}})-f(X_{I},X_{I^{c}}^{\prime})-f(X_{I}^{\prime},X_{I^{c}})+f(X_{I}^{\prime},X_{I^{c}}^{\prime})])$
$\displaystyle=(\frac{p-1}{p^{2}})^{2}p(p-1)\frac{1}{p}\sum_{t\neq
0}{\mathbf{E}}_{Y_{I},Y_{I^{c}}}e_{p}(-t\sum_{i\in I,j\in
I^{c}}a_{ij}y_{i}y_{j})=(\frac{p-1}{p})^{3}({\mathbf{P}}(\sum_{i\in I,j\in
I^{c}}a_{ij}y_{i}y_{j}=0)-1/p).$

∎

By Lemma 5.5, with probability at least $1-\exp(-\Theta(n))$ we can assume
that $L_{N}^{\ast}$ has rank at least $N-cN/2$ for each $N+0\leq N\leq n$. Let
us consider the event that $L_{N}^{\ast}$ has rank exactly $N-k$ (where $k\leq
cN/2$).

######  Claim 7.5.

Assume that $L_{N}^{\ast}$ has rank $N-k$, then there is a set
$I\subset[N],|I|=N-k$ such that the principle minor matrix $L_{I\times
I}^{\ast}$ has full rank $N-k$.

###### Proof of Claim 7.5.

Assume without loss of generality that
${\mathbf{r}}_{1}(L_{N}^{\ast}),\dots,{\mathbf{r}}_{n-k}(L_{N}^{\ast})$ span
the row vectors of $L_{N}^{\ast}$, then in particularly
${\mathbf{r}}_{i}|_{[N-k]},i\geq N-k+1$ belong to the span of
${\mathbf{r}}_{i}|_{[N-k]},1\leq i\leq n-k$. This implies that the matrix
spanned by the first $N-k$ columns $X_{1},\dots,X_{N-k}$ has rank at most
$N-k$. On the other hand, as the matrix is symmetric, this column matrix has
the same rank as that of the matrix generated by
${\mathbf{r}}_{1}(L_{N}^{\ast}),\dots,{\mathbf{r}}_{N-k}(L_{N}^{\ast})$, which
is $N-k$. So the matrix $L_{[N-k]\times[N-k]}$ generated by
${\mathbf{r}}_{i}|_{[N-k]},1\leq i\leq N-k$ has rank $N-k$. ∎

In what follows, assume again without loss of generality that
${\mathbf{r}}_{1}(L_{N}^{\ast}),\dots,{\mathbf{r}}_{N-k}(L_{N}^{\ast})$ span
the row vectors of $L_{N}^{\ast}$. When we add a new column
$X_{N+1}=(x_{1(N+1)},\dots,x_{(N+1)(N+1)}):=(x_{1},\dots,x_{N+1})$ and its
transpose to create $L_{N+1}^{\ast}$, if
${\operatorname{rank}}(L_{N+1}^{\ast})<{\operatorname{rank}}(L_{N}^{\ast})+2$
then the extended row vector
${\mathbf{r}}_{1}(L_{N+1}^{\ast}),\dots,{\mathbf{r}}_{N-k}(L_{N+1}^{\ast})$
still generate the space of the vectors
${\mathbf{r}}_{1}(L_{N+1}^{\ast}),\dots,{\mathbf{r}}_{N}(L_{N+1}^{\ast})$. In
particularly, this implies that

$x_{i}=\sum_{j=1}^{N-k}a_{ij}x_{j},\text{for $N-k+1\leq i\leq N$,}$ (7.6)

where $a_{ij}$ are determined from $L_{N}^{\ast}$ via
${\mathbf{r}}_{i}(L_{N}^{\ast})=\sum_{j=1}^{N-k}a_{ij}{\mathbf{r}}_{j}(L_{N}^{\ast})$.
In other words, Eq. (7.6) says that the vector $(x_{1},\dots,x_{N})$ is
orthogonal to the vectors $(a_{i1},\dots,a_{i(N-k)},0,\dots,-1,0,\dots,0)$, or
equivalently it belongs to the hyperplane $H_{N}$ generated by the column
vectors of $L_{N}^{\ast}$.

Now, by using our result on the normal vectors in the previous section, we
will obtain a bound $p^{-k}+O(e^{-n^{c}})$ for this event.

######  Lemma 7.7.

Assume that $1\leq k\leq cN$. There exists a positive constant $c$ so that for
any sufficiently large prime $p$ at most $\exp(n^{c})$ there exists an event
${\mathcal{E}}_{N}^{\ast}$ with ${\mathbf{P}}({\mathcal{E}}_{N}^{\ast})\geq
1-\exp(-n^{c})$ such that the following holds

${\mathbf{P}}\big{(}X_{N+1}|_{[N]}\in
H_{N}\big{|}{\operatorname{rank}}(L_{N}^{\ast})=N-k\wedge{\mathcal{E}}_{N}^{\ast}\big{)}=\frac{1}{p^{k}}+O(\exp(-n^{c})).$

We also refer the reader to [Map13a, Theorem 1.1], [NP20, Theorem A.1, A.4],
and [NW22, Theorem 8.2] for similar results for random i.i.d. matrices as well
as its i.i.d. Laplacian.

To prove Lemma 7.7, we first show the following analog of [LMN20, Lemma 7.1]
and [KN22, Lemma 2.11] for adapted vectors.

######  Lemma 7.8.

Assume that $H$ is a subspace in ${\mathbb{F}}_{p}^{N}$ of codimension $k$,
and such that for any ${\mathbf{w}}\in H^{\perp}$ we have

$\rho({\mathbf{w}}_{I_{0}})\leq\delta_{0}.$

Then with $X$ being adapted to $I_{0}$ as in 7.3 we have

$|{\mathbf{P}}(X\in H)-1/p^{k}|\leq 2\delta_{0}.$

###### Proof of Lemma 7.8.

We have the following identity,

$\displaystyle 1_{a_{1}=0\wedge\dots\wedge
a_{k}=0}=\frac{1}{p^{k}}\sum_{t_{1},\dots,t_{k}\in{\mathbb{F}}_{p}}e_{p}(a_{1}t_{1}+\dots+a_{k}t_{k}).$

Therefore, letting ${\mathbf{v}}_{1},\dots,{\mathbf{v}}_{k}$ be a basis for
$H^{\perp}$,

$\displaystyle{\mathbf{P}}(X\in H)$
$\displaystyle={\mathbf{P}}(X\cdot{\mathbf{v}}_{1}\wedge\dots\wedge
X\cdot{\mathbf{v}}_{k})$
$\displaystyle={\mathbf{E}}\Big{[}\frac{1}{p^{k}}\sum_{t_{1},\dots,t_{k}\in{\mathbb{F}}_{p}}e_{p}(t_{1}[X\cdot{\mathbf{v}}_{1}]+\dots+t_{k}[X\cdot{\mathbf{v}}_{d}])\Big{]}$
$\displaystyle={\mathbf{E}}\Big{[}\frac{1}{p^{k}}+\frac{1}{p^{k}}\sum_{\begin{subarray}{c}t_{1},\dots,t_{k}\in{\mathbb{F}}_{p}\\\
\text{ not all $t_{i}$ are
zero}\end{subarray}}e_{p}(t_{1}[X\cdot{\mathbf{v}}_{1}]+\dots+t_{k}[X\cdot{\mathbf{v}}_{k}])\Big{]}$
$\displaystyle=\frac{1}{p^{k}}+\frac{1}{p^{k}}\sum_{\begin{subarray}{c}t_{1},\dots,t_{k}\in{\mathbb{F}}_{p}\\\
\text{ not all $t_{i}$ are
zero}\end{subarray}}{\mathbf{E}}e_{p}(t_{1}[X\cdot{\mathbf{v}}_{1}]+\dots+t_{k}[X\cdot{\mathbf{v}}_{k}]).$

We now split the sum into projective equivalence classes. Let $\sim$ be the
equivalence relation given by
$(t_{1},\dots,t_{k})\sim(t_{1}^{\prime},\dots,t_{k}^{\prime})$ if there exists
$t\neq 0$ such that $(t_{1},\dots,t_{k})=(t\cdot t_{1}^{\prime},\dots,t\cdot
t_{k}^{\prime})$. Not worrying about our choice of representative on account
of our inner sum,

$\displaystyle=\frac{1}{p^{k}}+\frac{1}{p^{k}}\sum_{(t_{1},\dots,t_{k})\in({\mathbb{F}}_{p}^{N})^{\times}/\sim}\bigg{[}\sum_{t\in{\mathbb{F}}_{p}^{\times}}e_{p}(t(t_{1}[X\cdot{\mathbf{v}}_{1}]+\dots+t_{k}[X\cdot{\mathbf{v}}_{k}]))\bigg{]}$
$\displaystyle=\frac{1}{p^{k}}+\frac{1}{p^{k}}\sum_{(t_{1},\dots,t_{k})\in({\mathbb{F}}_{p}^{N})^{\times}/\sim}p\bigg{[}\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p}^{\times}}e_{p}(t(X\cdot\sum_{i=1}^{n}t_{i}{\mathbf{v}}_{i}))\bigg{]}.$

Now observe,

$\displaystyle\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p}^{\times}}e_{p}(t(X\cdot\sum_{i=1}^{k}t_{i}{\mathbf{v}}_{i}))={\mathbf{P}}(X\cdot\sum_{i=1}^{k}t_{i}{\mathbf{v}}_{i}=0)-1/p.$

The ${\mathbf{v}}_{i}$ are a basis and the $t_{i}$ are not all zero so
$\sum_{i=1}^{k}t_{i}{\mathbf{v}}_{i}$ is a nonzero element of $H^{\perp}$. By
assumption then this is bounded by $\delta_{0}$. There are
$\frac{p^{k}-1}{p-1}$ elements in
$(t_{1},\dots,t_{k})\in({\mathbb{F}}_{p}^{n})^{\times}/\sim$. We have
$\frac{p(p^{k}-1)}{p^{k}(p-1)}\leq 2$. So by the triangle inequality

$\displaystyle|{\mathbf{P}}(X\in H)-1/p^{k}|\leq 2\delta_{0}.$

∎

###### Proof of Lemma 7.7.

Let ${\mathcal{E}}_{N}^{\ast}$ be the event from Proposition 5.19 applied to
$L_{N}^{\ast}$ for $I_{0}=I_{N+1}$. Under ${\mathcal{E}}_{N}^{\ast}$ we have
learned that for any ${\mathbf{w}}\in H_{N}$ then
$\rho_{L}({\mathbf{w}}_{I_{N+1}})=O(\exp(-n^{c}))$, where $I_{N+1}$ is the
given index set where $X_{N+1}$ is adapted. ∎

For symmetric matrices
${\operatorname{rank}}(L_{N+1}^{\ast})\leq{\operatorname{rank}}(L_{N}^{\ast})+1$
does not automatically implies that
${\operatorname{rank}}(L_{N+1}^{\ast})={\operatorname{rank}}(L_{N}^{\ast})$,
so we have to consider the events
$L_{N+1}^{\ast})={\operatorname{rank}}(L_{N}^{\ast})$ and
${\operatorname{rank}}(L_{N+1}^{\ast})={\operatorname{rank}}(L_{N}^{\ast})+1$
separately. Let’s consider the first event that

${\operatorname{rank}}(L_{N+1}^{\ast})={\operatorname{rank}}(L_{N}^{\ast}).$

Here beside the event $X_{N+1}|_{[N]}\in H_{N}$ considered in Lemma 7.7,
$X_{N+1}={\mathbf{r}}_{N+1}(L_{N+1}^{\ast})$ also belongs to the subspace
generated by
${\mathbf{r}}_{1}(L_{N+1}^{\ast}),\dots,{\mathbf{r}}_{N}(L_{N+1}^{\ast})$.
This latter condition can be interpreted in quadratic forms as follows.
Conditioning on
${\operatorname{rank}}(L_{N}^{\ast})=N-k\wedge{\mathcal{E}}_{N}^{\ast}$, by
Claim 7.5 we can assume that $L_{I\times I}^{\ast}$ is a submatrix of full
rank $N-k$ in $L_{N}^{\ast}$, for some $I\subset[N]$ and $|I|=N-k$. Let
$B=(b_{ij})$ be the inverse of $L_{I\times I}^{\ast}$ in ${\mathbb{F}}_{p}$.
The exposure of $(x_{1},\dots,x_{N-k},x_{N+1})$ would then increase the rank
of $L_{N+1}^{\ast}$ except when

$\sum_{ij}b_{ij}x_{i}x_{j}+x_{N+1}=0.$ (7.9)

This leads us to consider the following for adapted vectors.

######  Lemma 7.10.

Let $k\geq 0$. Let $H_{N}$ and ${\mathcal{E}}_{N}^{\ast}$ be as in the proof
of Lemma 7.7. Let $X$ be as in 7.3 for a given index set $I_{0}$ satisfying
(7.1). For any sufficiently large prime $p$ at most $\exp(n^{c})$, we have

$\Big{|}{\mathbf{P}}\big{(}X\in H_{N}\wedge
f(X)=0|{\operatorname{rank}}(L_{N}^{\ast})=N-k\wedge{\mathcal{E}}_{N}^{\ast}\big{)}-p^{-k-1}\Big{|}=O(\exp(-\Theta(n^{c}))),$

where $f(X)=\sum_{1\leq i,j\leq N-k}b_{ij}x_{i}x_{j}+x_{N+1}$.

###### Proof of Lemma 7.10.

We write

$\displaystyle{\mathbf{P}}(X\in H_{N}\wedge f(X)=0)$
$\displaystyle=p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{E}}e_{p}(X\cdot\xi+f(X)t)$
$\displaystyle=p^{-k-1}+p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}{\mathbf{E}}e_{p}(X\cdot\xi+f(X)t)+p^{-k-1}\sum_{\xi\neq 0,\xi\in
H_{N}^{\perp}}{\mathbf{E}}e_{p}(X\cdot\xi).$

Note that the third sum is

$p^{-k-1}\sum_{\xi\neq 0,\xi\in
H_{N}^{\perp}}{\mathbf{E}}e_{p}(X\cdot\xi)=p^{-k-1}(\sum_{\xi\in
H_{N}^{\perp}}{\mathbf{E}}e_{p}(X\cdot\xi)-1)=\frac{1}{p}{\mathbf{P}}(X\in
H_{N})-p^{-k-1}.$

Hence the third sum can be bounded by $O(\exp(-n^{c}))$ in absolute value
using the condition on $G_{n}$ from Lemma 7.7.

For the second sum, we have

$|p^{-k-1}\sum_{\xi\in H_{N}^{\perp},t\in{\mathbb{F}}_{p},t\neq
0}{\mathbf{E}}e_{p}(X\cdot\xi+f(X)t|\leq\Big{(}p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}|{\mathbf{E}}e_{p}(X\cdot\xi+f(X)t|^{4}\Big{)}^{1/4}.$

Recall that $|I_{0}|$ satisfies (7.1). For now we let $I_{2}\subset I_{0}$ of
size $\lfloor cN\rfloor$, and let $I_{1}=I\backslash I_{2}$. By using Cauchy-
Schwarz as in the proof of Lemma 7.4, we then bound this by

$\displaystyle\ \ \ p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}\big{|}{\mathbf{E}}e_{p}(X\cdot\xi+f(X)t\big{|}^{4}$ $\displaystyle\leq
p^{-k-1}\sum_{\xi\in H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}\Big{|}{\mathbf{E}}_{X_{I_{1}}}{\mathbf{E}}_{X_{I_{2}},X_{I_{2}}^{\prime}}e_{p}\big{(}(X_{I_{2}}-X_{I_{2}}^{\prime})\cdot\xi+(f(X_{I_{1}},X_{I_{2}})-f(X_{I_{1}},X_{I_{2}}^{\prime}))t\big{)}\Big{|}^{2}$
$\displaystyle\leq p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}{\mathbf{E}}_{X_{I_{2}},X_{I_{2}}^{\prime}}{\mathbf{E}}_{X_{I_{1}},X_{I_{2}}}e_{p}\Big{(}(f(X_{I_{1}},X_{I_{2}})-f(X_{I_{1}},X_{I_{2}}^{\prime})-f(X_{I_{1}}^{\prime},X_{I_{2}})+f(X_{I_{1}}^{\prime},X_{I_{2}}^{\prime}))t\Big{)}$
$\displaystyle=p^{-k-1}\sum_{\xi\in
H_{N}^{\perp},t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}{\mathbf{E}}_{Y}e_{p}(\sum_{i\in I_{1},j\in
I_{2}}b_{ij}y_{i}y_{j}t)=\frac{1}{p}\sum_{t\in{\mathbb{Z}}/p{\mathbb{Z}},t\neq
0}{\mathbf{E}}_{Y}e_{p}(\sum_{i\in I_{1},j\in I_{2}}b_{ij}y_{i}y_{j}t)$
$\displaystyle={\mathbf{P}}(Y_{I_{1}}^{\prime}\cdot
BY_{I_{2}}^{\prime}=0)-\frac{1}{p},$

where $y_{i},i\in I_{0}$ are i.i.d. copies of the the random variable
$\xi-\xi^{\prime}$, and where $Y_{I_{1}}^{\prime}$ and $Y_{I_{2}}^{\prime}$
are the vectors in ${\mathbb{F}}_{p}^{I}$ obtained from $Y_{I_{1}}$ (i.e.
$Y_{I}|_{I_{1}}$) and $Y_{I_{2}}$ (i.e. $Y_{I}|_{I_{2}}$) resp. by appending
zero entries.

Let $J=[N]\backslash I$, so $|J|=k$ and that $[N]=I_{1}\cup I_{2}\cup J$. We
let $B^{\prime}$ be the symmetric matrix of size $n$ obtained from $B$ by
simply adding zero entries. Similarly, let $Y_{I_{1}}^{\prime\prime}$ and
$Y_{I_{2}}^{\prime\prime}$ be the vectors in ${\mathbb{F}}_{p}^{N}$ obtained
from $Y_{I_{1}}^{\prime}$ and $Y_{I_{2}}^{\prime}$ by appending zero
components. Then $Y_{I_{1}}^{\prime}\cdot BY_{I_{2}}^{\prime}=0$ is equivalent
to

$Y_{I_{1}}^{\prime\prime}\cdot B^{\prime}Y_{I_{2}}^{\prime\prime}=0.$

Furthermore, notice that the vector $Y_{I_{2}}^{\prime\prime}$ is non-zero (in
${\mathbb{F}}_{p}^{N}$) with probability at least $1-\exp(-\Theta(n))$
(because $Y_{I_{2}}^{\prime\prime}$ has $\lfloor cN\rfloor$ i.i.d. entries)
and that

$L_{N}^{\ast}(B^{\prime}Y_{I_{2}}^{\prime\prime})=(L_{N}^{\ast}B^{\prime})Y_{I_{2}}^{\prime\prime}=Y_{I_{2}}^{\prime\prime},$

where we used the fact that $B=(b_{ij})$ is the inverse of $L_{I\times
I}^{\ast}$ in ${\mathbb{F}}_{p}$.

It follows by Proposition 5.19 that on ${\mathcal{E}}_{N}^{\ast}$

$\rho_{L}(B^{\prime}Y_{I_{2}}^{\prime\prime}|_{I_{0}\cap
I_{1}})\leq\exp(-\Theta(n^{c})).$

Conditioned on such $Y_{I_{2}}^{\prime\prime}$, by (5.3)

$|{\mathbf{P}}_{Y_{I_{1}}^{\prime}}(Y_{I_{1}}^{\prime}\cdot
BY_{I_{2}}^{\prime}=0)-\frac{1}{p}|=|{\mathbf{P}}_{Y_{I_{1}}^{\prime}}(Y_{I_{1}}^{\prime\prime}\cdot
B^{\prime}Y_{I_{2}}^{\prime\prime}=0)-\frac{1}{p}|\leq\exp(-\Theta(n^{c})).$

∎

Having obtained the necessary concentration bounds, we will next put things
together to obtain the rank statistics for the three matrix models, our method
is similar to that of [Map13b, KN22].

######  Proposition 7.11 (Rank relations for Laplacian matrices).

There exists a positive constant $c$ such that the following holds. Assume
that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. For $N_{0}\leq
N\leq n$ there exists an event ${\mathcal{E}}_{N}^{\ast}$ on the
$\sigma$-algebra generated by $L_{n}$ and by the neighbor reshuffling process
up to step $N$ such that ${\mathbf{P}}({\mathcal{E}}_{N}^{\ast})\geq
1-\exp(-n^{c})$ and for $k\leq cN$

  * •

assume that $k\geq 1$ then

$\Big{|}{\mathbf{P}}\big{(}{\operatorname{rank}}(L_{N+1}^{\ast})\leq{\operatorname{rank}}(L_{N}^{\ast})+1|{\mathcal{E}}_{N}^{\ast}\wedge{\operatorname{rank}}(L_{N}^{\ast})=N-k)\big{)}-\frac{1}{p^{k}}\Big{|}\leq\exp(-\Theta(n^{c}));$

  * •

assume that $k\geq 0$ then

$\Big{|}{\mathbf{P}}\big{(}{\operatorname{rank}}(L_{N+1}^{\ast})={\operatorname{rank}}(L_{N}^{\ast})|{\mathcal{E}}_{N}^{\ast}\wedge{\operatorname{rank}}(L_{N}^{\ast})=N-k)\big{)}-\frac{1}{p^{k+1}}\Big{|}\leq\exp(-\Theta(n^{c})).$

By a similar much much simpler method (where we don’t have to do the
reshuffling process, and where $I_{0}=[N]$ at each step, but we still need
variants of Lemma 7.7 and Lemma 7.10 with obvious modifications) we also
obtain the following for symmetric matrices.

######  Proposition 7.12 (Rank relations for symmetric matrices).

There exists a positive constant $c$ such that the following holds. Assume
that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. For $N_{0}\leq
N\leq n$ there exists an event ${\mathcal{E}}_{N}$ on the $\sigma$-algebra
generated by the first $N$ rows (and columns) of the matrix $M_{N}=M_{N\times
N}$ (as a principle minor of $M_{n}$ from Theorem 1.3) such that
${\mathbf{P}}({\mathcal{E}}_{N})\geq 1-\exp(-n^{c})$ and for $k\leq cN$

  * •

assume that $k\geq 1$ then

$\Big{|}{\mathbf{P}}\big{(}{\operatorname{rank}}(M_{N+1})\leq{\operatorname{rank}}(M_{N})+1|{\mathcal{E}}_{N}\wedge{\operatorname{rank}}(M_{N})=N-k)\big{)}-\frac{1}{p^{k}}\Big{|}\leq\exp(-\Theta(n^{c}));$

  * •

assume that $k\geq 0$ then

$\Big{|}{\mathbf{P}}\big{(}{\operatorname{rank}}(M_{N+1})={\operatorname{rank}}(M_{N})|{\mathcal{E}}_{N}\wedge{\operatorname{rank}}(M_{N})=N-k)\big{)}-\frac{1}{p^{k+1}}\Big{|}\leq\exp(-\Theta(n^{c})).$

Next we comment on random skew-symmetric matrices. Here the rank evolution is
slightly simpler and different. We note that, similarly to random symmetric
matricers, Lemma 7.7 also works for random skew-symmetric matrices. Let us
call ${\mathcal{E}}_{N}$ the event under consideration. The key difference
here is that the event that for skew-symmetric matrices,
${\operatorname{rank}}(A_{N+1})\leq{\operatorname{rank}}(A_{N})+1$ implies
that ${\operatorname{rank}}(A_{N+1})={\operatorname{rank}}(A_{N})$. This is
because if $X_{N+1}|_{[N]}=A_{N}Y_{0}$ for some $Y_{0}$, then $Y_{0}^{T}\cdot
X_{N+1}|_{[N]}=0$, and so $Y_{0}^{T}A_{[N]\times[N+1]}=X_{N+1}^{T}$, that is
the $(N+1)$-th row also belongs the the linear space spanned by the first $n$
rows. Thus Lemma 7.7 applied to skew-symmetric matrices imply

######  Proposition 7.13 (Rank relations for skew-symmetric matrices).

There exists a positive constant $c$ such that the following holds. Assume
that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. For $N_{0}\leq
N\leq n$ there exists an event ${\mathcal{E}}_{N}$ on the $\sigma$-algebra
generated by the first $N$ rows (and columns) of the matrix $A_{N}=A_{N\times
N}$ (as a principle minor of $A_{N}$ from Theorem 1.4) such that
${\mathbf{P}}({\mathcal{E}}_{N})\geq 1-\exp(-n^{c})$ and for $k\leq cN$
444Strictly speaking, Lemma 7.7 just gave $k\geq 1$, but for $k=0$ the bound
automatically holds with probability one. then

$\Big{|}{\mathbf{P}}\big{(}{\operatorname{rank}}(A_{N+1})={\operatorname{rank}}(A_{N})|{\mathcal{E}}_{N}\wedge{\operatorname{rank}}(A_{N})=N-k\big{)}-\frac{1}{p^{k}}\Big{|}=O(\exp(-n^{c})).$

One can then deduce the asymptotic probability of the event
${\operatorname{rank}}(A_{N+1})={\operatorname{rank}}(A_{N})+2$ under
${\mathcal{E}}_{N}\wedge{\operatorname{rank}}(A_{N})=N-k$. We note that the
transition probability
${\mathbf{P}}({\operatorname{rank}}(A_{N+1})={\operatorname{rank}}(A_{N}))$ of
the skew-symmetric case above is quite similar to that of the i.i.d. models
considered in [Map13a, NW22, NP20] (where there we expose the first $N$ column
vectors of the matrix of size $n$). However the difference here is that
${\operatorname{rank}}(A_{N+1})$ jumps by 2 (rather than 1) in the complement
event.

To complete the subsection, we remark that Propositions 7.12 and 7.13
automatically extend to the uniform models where $M_{N},A_{N}$ are uniformly
chosen from the set of all symmetric matrices and skew-symmetric matrices in
${\mathbb{F}}_{p}$ because the uniformly chosen entries are clearly
$\alpha$-balanced.

###  7.1. The rank evolving process: completing the proof of Proposition 2.1
and Proposition 2.3

Let $G_{N}$ be either $A_{N},M_{N}$ or $L_{N}^{\ast}$. We will start from
$N=N_{0}=\lfloor cn\rfloor$, which is assumed to possess
${\mathcal{E}}_{N_{0}}$ and have rank at least $N_{0}-N_{0}^{1/2+c}$, where we
have learned that the latter event has probability at least
$1-\exp(\Theta(n))$ by Lemma 5.5. We will apply Propositions 7.13 and 7.11 for
$G_{N_{0}+1},\dots,G_{n}$. To compare with the rank evolution of the uniform
model, for convenience we will use the following result from [NW22, Theorem
5.3].

######  Theorem 7.14.

Let $x_{N_{0}},\dots,x_{n},g_{N_{0}-1},\dots,g_{n-1}$ be a sequence of random
variables. Let $y_{N_{0}},\dots,y_{n}$ be a sequence of random variables where
$y_{N_{0}}=x_{N_{0}}$. We assume each $x_{N},y_{N}$ takes on at most countably
many values, and $g_{N}\in\\{0,1\\}$. Suppose that for $0\leq N\leq n-1$,

$\displaystyle{\mathbf{P}}(y_{N+1}=s|y_{N}=r)={\mathbf{P}}(x_{N+1}=s|x_{N}=r\textrm{
and }g_{N}=1)+\delta(N,r,s)$ $\displaystyle\textrm{ for all $r$ and $s$ s.t.
${\mathbf{P}}(y_{N}=r){\mathbf{P}}(x_{N}=r\textrm{ and }g_{N}=1)\neq 0$}.$

Then for any set $A$ of values taken by $x_{n}$ and $y_{n}$, we have

$\displaystyle|{\mathbf{P}}(x_{n}\in A)-{\mathbf{P}}(y_{n}\in A)|$
$\displaystyle\leq\frac{1}{2}\sum_{N=N_{0}}^{n-1}\sum_{r}\sum_{s}|\delta(N,r,s)|{\mathbf{P}}(x_{N}=r)+\sum_{N=N_{0}}^{n-1}{\mathbf{P}}(g_{N}\neq
1),$

where $r$ is summed over $\\{r\ |\ {\mathbf{P}}(x_{N}=r)\neq 0\textrm{ and
}{\mathbf{P}}(y_{N}=r)\neq 0)\\}$ and $s$ is summed over $\\{s\ |\
{\mathbf{P}}(x_{N+1}=s)\neq 0\textrm{ or }{\mathbf{P}}(y_{N+1}=s)\neq 0)\\}.$

For the detailed statistics of skew-symmetric matrices, let $\mu_{alt,n}$ be
the rank distribution of the uniform skew-symmetric model in
${\mathbb{F}}_{p}$ (i.e. each non-diagonal entry is independent uniform in
${\mathbb{Z}}/p{\mathbb{Z}}$). By [Mac69] we have

$\mu_{alt,n}(k)={\mathbf{P}}({\operatorname{rank}}(A_{n,uniform}=n-k)=\frac{N_{0}(n,n-k)}{p^{\binom{n}{2}}}$

where

$N_{0}(n,2h)=\prod_{i=1}^{h}\frac{p^{2i-2}}{p^{2i}-1}\prod_{i=0}^{2h-1}(p^{n-i}-1)\mbox{
and }N_{0}(2h+1)=0.$

However we cannot apply Theorem 7.14 directly to
$x_{N}={\operatorname{rank}}(A_{N})$ and
$y_{N}={\operatorname{rank}}(A_{N,uniform})$ and $g_{N}=1_{{\mathcal{E}}_{N}}$
because the above uniform statistics is grown from a zero-dimension matrix. To
amend this, we can start from any realization of
$A_{N_{0}}^{\prime}=A_{N_{0}}$ and add rows and columns according to the
uniform model until $A_{n}^{\prime}$. We call this model uniform with initial
matrix $A_{N_{0}}$. Then [KN22, Proposition 3.13] applied to this
$A_{n}^{\prime}$ shows that its rank statistics is extremely close to the
uniform model, that

$d_{TV}(n-{\operatorname{rank}}(A_{n}^{\prime}/p),\mu_{alt,n})\leq
p^{-\Theta(n)}.$

Now we can apply Theorem 7.14 and use the triangle inequality to conclude that

$d_{TV}(n-{\operatorname{rank}}(A_{n}/p),\mu_{alt,n})\leq e^{-n^{c}}.$

On the other hand, by [FG15, Section 5]

$d_{TV}(\mu_{alt,n},\mu_{alt,e})=O(\frac{1}{p^{n+1}})\mbox{ if $n$ is even}$

and

$d_{TV}(\mu_{alt,n},\mu_{alt,o})=O(\frac{1}{p^{n+1}})\mbox{ if $n$ is odd}$

where the limiting distributions are given by

${\mathbf{P}}(\mu_{alt,e}=k):=\begin{cases}\prod_{i=0}^{\infty}(1-p^{-2i-1})\frac{p^{k}}{\prod_{i=1}^{k}(p^{i}-1)},&\mbox{$k$
is even}\\\ 0,\mbox{ $k$ is odd}\end{cases}$

and

${\mathbf{P}}(\mu_{alt,o}=k):=\begin{cases}\prod_{i=0}^{\infty}(1-p^{-2i-1})\frac{p^{k}}{\prod_{i=1}^{k}(p^{i}-1)},&\mbox{$k$
is odd}\\\ 0,\mbox{ $k$ is even}\end{cases}$

Putting together

######  Theorem 7.15 (Ranks statistics of random skew-symmetric matrices).

Assume that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. Assume
that $A_{n}$ is as in Theorem 1.4, then

$d_{TV}(n-{\operatorname{rank}}(A_{n}/p),\mu_{alt,e})=O(e^{-n^{c}}),\text{ $n$
is even}$

and

$d_{TV}(n-{\operatorname{rank}}(A_{n}/p),\mu_{alt,o})=O(e^{-n^{c}}),\text{ $n$
is odd.}$

The claim of Proposition 2.3 then follows easily because

$\sum_{k\geq 3}{\mathbf{P}}(\mu_{alt,e}=k)=\sum_{k\geq
4}{\mathbf{P}}(\mu_{alt,e}=k)=O(\frac{1}{p^{6}})$

and

$\sum_{k\geq 3}{\mathbf{P}}(\mu_{alt,o}=k)=O(\frac{1}{p^{3}}).$

Now for symmetric and Laplacian matrices, let with $\mu_{sym,n}$ be the rank
distribution of the random uniform symmetric matrix of size $n$ where each
$x_{ij},1\leq i\leq j\leq n$ are independent uniform over
${\mathbb{Z}}/p{\mathbb{Z}}$. By [Car54, Mac69] we have

$\mu_{sym,n}(k)={\mathbf{P}}({\operatorname{rank}}(M_{uniform}=n-k))=\frac{N(n,n-k)}{p^{\binom{n+1}{2}}}$

where

$N(n,2h)=\prod_{i=1}^{h}\frac{p^{2i}}{p^{2i}-1}\prod_{i=0}^{2h-1}(p^{n-i}-1),2h\leq
n$

and

$N(n,2h+1)=\prod_{i=1}^{h}\frac{p^{2i}}{p^{2i}-1}\prod_{i=0}^{2h}(p^{n-i}-1),2h+1\leq
n.$

Arguing as in the skew-symmetric case, we can grow the uniform model from
$G_{N_{0}}^{\prime}=G_{N_{0}}$, and add rows and columns according to the
uniform model to form $G_{N_{0}+1}^{\prime}$ and so on until $G_{n}^{\prime}$.
Then [KN22, Proposition 3.13] applied to this uniform model $G_{n}^{\prime}$
with initial $G_{N_{0}}$ shows that its rank statistics is extremely close to
the uniform model, and hence by Theorem 7.14 and by the triangle inequality

$d_{TV}(n-{\operatorname{rank}}(G_{n}/p),\mu_{sym,n})\leq e^{-n^{c}}.$

On the other hand, by [FG15, Section 4] we have

$d_{TV}(\mu_{sym,n},\mu_{sym})=O(\frac{1}{p^{n+1}})$

where

${\mathbf{P}}(\mu_{sym}=k)=\frac{\prod_{i=0}^{\infty}(1-p^{-2i-1})}{\prod_{i=1}^{k}(p^{i}-1)}.$

Putting together we have thus obtained

######  Theorem 7.16 (Ranks statistics of random symmetric matrices).

Assume that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. Assume
that $M_{n}$ is as in Theorem 1.3, then

$d_{TV}(n-{\operatorname{rank}}(M_{n}/p),\mu_{sym})=O(e^{-n^{c}}).$

######  Theorem 7.17 (Ranks statistics of random Laplacian matrices).

Assume that $p$ is a sufficiently large prime and $p\leq\exp(n^{c})$. Assume
that $L_{n}$ is as in Theorem 1.22, then

$d_{TV}(n-{\operatorname{rank}}(L_{n}/p),\mu_{sym})=O(e^{-n^{c}}).$

Proposition 2.1 then follows because

$\sum_{k\geq 2}{\mathbf{P}}(\mu_{sym}=k)=O(\frac{1}{p^{3}}).$

To conclude the section, as $G_{n}=A_{n},M_{n},L_{n}$ are integral, if
$\det(G_{n})=0$ then for any prime $p$ we have $G_{n}/p$ is singular, i.e.
${\operatorname{rank}}(G_{n}/p)\leq n-1$. Using our result of corank
comparison, by choosing $p$ sub-exponentially large we obtain the following
bound for singularity.

######  Corollary 7.18 (Singularity of skew-symmetric, symmetric and Laplacian
matrices).

There exists a positive constant $c>0$ so that

${\mathbf{P}}(\det(A_{2n})=0)=O(\exp(-n^{c}));{\mathbf{P}}(\det(M_{n})=0)=O(\exp(-n^{c}));$

and

${\mathbf{P}}(\det(L_{n})=0)=O(\exp(-n^{c})).$

For the random symmetric model we also refer the reader to [CMMM21, FJ19,
Ver14] for analogous sub-exponential bounds (with explicit constants), and to
a more recent work [CJMS21] for exponential bounds. Our results for the skew-
symmetric and Laplacian cases are new.

######  Remark 7.19.

While the current paper was under preparation, a recent paper by Ferber et.
al. [FJSS21] has obtained a similar result to Theorem 7.16 for Bernoulli
matrices with explicit $c$. Here in the symmetric case we established this
result for general random matrices of balanced entries. We also obtained
similar results for the skew-symmetric model, which has different and
interesting rank statistics. However, as the reader can see, our main
difficulty for the moderate primes lies in Laplacian matrices, where we had to
look at the local structures of the generalized normal vectors of $L_{N}$ over
a random index set $I_{N+1}$. In fact, prior to this work, not much has been
known about this complicated model from the viewpoint of rank statistics and
singularity. The only results that we are aware of for the Laplacian are from
[Woo17], where it justifies Theorem 7.17 for relatively small $p$, and that
${\mathbf{P}}(\det(L_{n})=0)=1-o(1)$ for a somewhat implicit rate of
convergence.

##  8\. Treatment for large primes: control of blowing up and quadratic
inverse theorems

While in the previous sections we are able to control all primes up to
$\exp(n^{c})$, our treatment for larger primes cannot follow the same way
because taking union bound over all large primes is extremely costly. We
cannot take union bound even with the conjectural forms of Theorems 7.15, 7.16
and 7.17 that the error bounds are of form $\exp(-cn)$ in place of
$\exp(-n^{c})$ because there are $n^{cn}$ primes to handle. To avoid this
obstacle, we will find a common structure that is passable to all large primes
simultaneously. In general, this idea was also applied in [NW22] to treat with
random non-symmetric matrices, but the extension to symmetric and Laplacian
matrices does require significantly new ideas.

Our main results of this section are Theorem 8.3 and Theorem 8.14. To start
with, we first recall from [TV10b] a notion of additive structures in abelian
groups. Let $G$ be an (additive) abelian group.

######  Definition 8.1.

A set $Q$ is a _generalized arithmetic progression_ (GAP) of rank $r$ if it
can be expressed as in the form

$Q=\\{a_{0}+x_{1}a_{1}+\dots+x_{r}a_{r}|M_{i}\leq x_{i}\leq
M_{i}^{\prime}\hbox{ and $x_{i}\in{\mathbb{Z}}$ for all }1\leq i\leq r\\}$

for some elements $a_{0},\ldots,a_{r}$ of $G$, and for some integers
$M_{1},\ldots,M_{r}$ and $M^{\prime}_{1},\ldots,M^{\prime}_{r}$.

It is convenient to think of $Q$ as the image of an integer box
$B:=\\{(x_{1},\dots,x_{r})\in{\mathbb{Z}}^{r}|M_{i}\leq x_{i}\leq
M_{i}^{\prime}\\}$ under the linear map

$\Phi:(x_{1},\dots,x_{r})\mapsto a_{0}+x_{1}a_{1}+\dots+x_{r}a_{r}.$

Given $Q$ with a representation as above

  * •

the numbers $a_{i}$ are _generators_ of $Q$, the numbers $M_{i}$ and
$M_{i}^{\prime}$ are _dimensions_ of $Q$, and ${\operatorname{Vol}}(Q):=|B|$
is the _volume_ of $Q$ associated to this presentation (i.e. this choice of
$a_{i},M_{i},M_{i}^{\prime}$);

  * •

we say that $Q$ is _proper_ for this presentation if the above linear map is
one to one, or equivalently if $|Q|=|B|$;

  * •

If $-M_{i}=M_{i}^{\prime}$ for all $i\geq 1$ and $a_{0}=0$, we say that $Q$ is
symmetric for this presentation.

We note again that unlike in other applications of additive structures in
random matrix theory that researchers used structures to enumerate vectors
satisfying certain properties, here we use the above structure as it is to
pass to all large primes; so the structure itself is important.

The following inverse-type result established by the current authors from
[NW22] (which was in turn motivated by the inverse-type idea from [TV09]) will
allow us to prove bounds sharper than Theorem 5.11.

######  Theorem 8.2.

Let $\varepsilon<1$ and $C$ be positive constants. Assume that $p\geq
C^{\prime}N^{C}$ is a prime where $C^{\prime}$ is sufficiently large. Let
$\xi$ be a random variable taking values in ${\mathbb{Z}}/p{\mathbb{Z}}$ which
is $\alpha$-balanced. Assume
${\mathbf{w}}=(w_{1},\dots,w_{N})\in({\mathbb{Z}}/p{\mathbb{Z}})^{N}$ such
that

$\rho_{l}({\mathbf{w}}):=\sup_{a\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{P}}(\xi_{1}w_{1}+\dots+\xi_{N}w_{N}=a)\geq
N^{-C},$

where $\xi_{1},\dots,\xi_{N}$ are i.i.d. copies of $\xi$. Then for any
$N^{\varepsilon/2}\alpha^{-1}\leq N^{\prime}\leq N$ there exists a proper
symmetric GAP $Q$ of rank $r=O_{C,\varepsilon}(1)$ which contains all but
$N^{\prime}$ elements of $w$ (counting multiplicity), where

$|Q|\leq\max\left\\{1,O_{C,\varepsilon}(\rho_{l}^{-1}/(\alpha
N^{\prime})^{r/2})\right\\}.$

We remark that $\rho_{l}(.)$ (where the subscript stands for linear) is
slightly different from $\rho(.)$ defined in (5.8). We removed $1/p$ in
$\rho_{l}(.)$ as it has little effect when $p$ is large. Note that this result
continues to hold for $\alpha$ could be as small as $n^{-1+o(1)}$, but we just
assume $\alpha$ to be a constant here as usual. We also refer the reader to
[KNP21] for various versions in general Abelian groups where GAP is replaced
by coset-progressions.

We now introduce an inverse result for bilinear forms, which is another
contribution of the current paper.

######  Theorem 8.3.

Let $C>0$ and $\varepsilon>0$. There exists a constant $A$ such that the
following holds for any prime $p\geq N^{A}$. Assume that $B=(b_{ij})_{1\leq
i,j\leq N}$ is an array of elements of ${\mathbb{Z}}/p{\mathbb{Z}}$ so that

$\rho_{b}:=\sup_{a\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{P}}_{X,Y}(\sum_{i,j\leq
n}b_{ij}x_{i}y_{j}=a)\geq N^{-C},$

where $X=(x_{1},\dots,x_{N}),Y=(y_{1},\dots,y_{N})$, and $x_{i}$ and $y_{i}$
are i.i.d. copies of $\xi$ as in Theorem 8.2. Then, there exist an integer
$k\neq 0,|k|=N^{O_{C,\varepsilon}(1)}$, a set of $r=O(1)$ rows
${\mathbf{r}}_{i_{1}},\dots,{\mathbf{r}}_{i_{r}}$ of $B=(b_{ij})_{1\leq
i,j\leq n}$, and set $I$ of size at least $N-N^{\varepsilon}$ such that for
each $i\in I$, there exist integers $k_{ii_{1}},\dots,k_{ii_{r}}$, all bounded
by $N^{O_{C,\varepsilon}(1)}$, with the following property

${\mathbf{P}}_{Z}\Big{(}Z\cdot(k{\mathbf{r}}_{i}(B)+\sum_{j=1}^{r}k_{ii_{j}}{\mathbf{r}}_{i_{j}}(B))=0\
\operatorname{mod}\ p\Big{)}\geq N^{-O_{C,\varepsilon}(1)},$ (8.4)

where $Z=(z_{1},\dots,z_{N})$ and $z_{i}$ are i.i.d. copies of $\xi$.

In connection to our previous sections, the parameter $N$ will be chosen to
satisfy $cn\leq N\leq n$ throughout this section. In our later application we
just need to consider $p\geq\exp(n^{c})$, so the above assumption on the range
of $p$ is natural. On the other hand, it is of independent interest to extend
the results of Theorem 8.3 (and Theorem 8.14 below) to small $p$, we hope to
be able to address this issue elsewhere.

So in a way our result says that the rows of $B$ have low rank modulo some GAP
noise. (Indeed it follows from (8.4) and from Theorem 8.2 that for each $i\in
I$, most of the entries of
$k{\mathbf{r}}_{i}(B)+\sum_{j}k_{ii_{j}}{\mathbf{r}}_{i_{j}}(B)$ belong to a
symmetric GAP $P_{i}$ of rank $O(1)$ and size $N^{O(1)}$. One can in fact
unify these structures into one but we will not do it here.) We will also
introduce a quadratic version later (Theorem 8.14) and prove it in the
appendix. For the rest of this section we give a proof of Theorem 8.3,
adapting the method of [Ngu12] toward ${\mathbb{Z}}/p{\mathbb{Z}}$.

We first rely on the following simple fact about generalized arithmetic
progressions of small rank and large characteristic.

######  Fact 8.5.

Let $C>$ be given. Assume that $q_{1},\dots,q_{r+1}$ are elements of a GAP of
rank $r$ and of cardinality $N^{C}$ in ${\mathbb{Z}}/p{\mathbb{Z}}$, where
$p\geq N^{A}$ for sufficiently large $A$ depending on $r$ and $C$, then there
exist integer coefficients $\alpha_{1},\dots,\alpha_{r}$ with
$|\alpha_{i}|\leq N^{rC}$, not all zero, such that in
${\mathbb{Z}}/p{\mathbb{Z}}$

$\sum_{i=1}^{r+1}\alpha_{i}q_{i}=0.$

To prove Theorem 8.3, we begin by applying Theorem 8.2.

######  Lemma 8.6.

Let $\varepsilon<1$ and $C$ be positive constants. With the assumption as in
Theorem 8.2, assume that $\rho_{b}\geq N^{-C}$. Then the following holds with
probability at least $3\rho_{b}/4$ with respect to $Y$. There exist a proper
symmetric GAP $Q_{Y}$ in ${\mathbb{Z}}/p{\mathbb{Z}}$ of rank
$O_{C,\varepsilon}(1)$ and size $O_{C,\varepsilon}(1/\rho_{b})$ and a set
$I_{Y}$ of $N-N^{\varepsilon}$ indices such that for each $i\in I_{Y}$ we have
$\sum_{j}b_{ij}y_{j}\in Q_{Y}$.

###### Proof.

For short we write $\sum_{i,j}b_{ij}x_{i}y_{j}=\sum_{i=1}^{N}x_{i}B_{i}(Y)$,
where

$B_{i}(Y):=\sum_{j}b_{ij}y_{j}.$

We call a vector $Y$ good if
${\mathbf{P}}_{{\mathbf{x}}}(\sum_{i=1}^{n}x_{i}B_{i}(Y)=a)\geq\rho_{b}/4$. We
call $Y$ bad otherwise. Let $G$ be the collection of good vectors. By
averaging, one can show that the probability of random vector $Y$ being good
is at least, say $3\rho_{b}/4$.

Next, we consider good vectors $Y\in G$. By definition,
${\mathbf{P}}_{{\mathbf{x}}}(\sum_{i=1}^{N}x_{i}B_{i}(Y)=a)\geq\rho_{b}/4$. A
direct application of Theorem 8.2 to the sequence $B_{i}(Y)$, $i=1,\dots,N$
yields the desired result. ∎

By a useful property of GAP containment (see for instance [TV09, Section 8]
and [Ngu12, Theorem 6.1]), we may assume that the $q_{i}(Y)$ span $Q_{Y}$ in
${\mathbb{Z}}/p{\mathbb{Z}}$. From now on we fix such a $Q_{Y}$ for each $Y$.
Recall that $G$ is the collection of good vectors and we have

${\mathbf{P}}_{Y}(Y\in G)\geq 3\rho_{b}/4.$ (8.7)

Now we state a main lemma for the proof of Theorem 8.3.

######  Lemma 8.8.

There exits an index set $I$ of size at least $N-2N^{\varepsilon}$, an index
set $I_{0}$ of size $O_{C,\varepsilon}(1)$, and an integer $k\neq 0$ with
$|k|\leq N^{O_{C,\varepsilon}(1)}$ such that for any index $i$ from $I$, there
are numbers $k_{ii_{0}}\in{\mathbb{Z}},i_{0}\in I_{0}$, all bounded by
$n^{O_{C,\varepsilon}(1)}$, such that

${\mathbf{P}}_{Y}\Big{(}kB_{i}(Y)+\sum_{i_{0}\in
I_{0}}k_{ii_{0}}B_{i_{0}}(Y)=0\ \operatorname{mod}\
p\Big{)}=\rho_{b}/N^{O_{C,\varepsilon}(1)}.$

Assume this result for a moment.

###### Proof of Theorem 8.3.

From Lemma 8.8, for any fixed $i\in I$, we note that

$kB_{i}(Y)+\sum_{i_{0}\in
I_{0}}k_{ii_{0}}B_{i_{0}}(Y)=\sum_{j}(kb_{ij}+\sum_{i_{0}}k_{ii_{0}}b_{i_{0}j})y_{j}.$

By the conclusion of Lemma 8.8, we have

$\sup_{a\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{P}}_{Y}(\sum_{j}(kb_{ij}+\sum_{i_{0}\in
I_{0}}k_{ii_{0}}b_{i_{0}j})y_{j}=a\ \operatorname{mod}\
p)\geq\rho_{b}/N^{O_{C,\varepsilon}(1)}.$

∎

We now give a proof for Lemma 8.8.

###### Proof of Lemma 8.8.

For each $Y\in G$, we choose from $I_{Y}$ $s$ indices
$i_{(1,Y)},\dots,i_{{(s,Y)}}$ such that $q_{i_{{(j,Y)}}}(Y),1\leq j\leq s$,
span $Q_{Y}$ in ${\mathbb{Z}}/p{\mathbb{Z}}$, where $s$ is the rank of
$Q_{Y}$. We note that $s=O_{C,\varepsilon}(1)$ for all $Y\in G$.

Consider the tuples $(i_{{(1,Y}},\dots,i_{{(s,Y}})$ for all $Y\in G$. Because
there are $\sum_{s}O_{C,\varepsilon}(N^{s})=N^{O_{C,\varepsilon}(1)}$
possibilities these tuples can take, by the pigeon-hole principle there exists
a tuple, say $(1,\dots,r)$ (by rearranging the rows of $B=(b_{ij})$ if
needed), such that $(i_{{(1,Y}},\dots,i_{{(s,Y}})=(1,\dots,r)$ for all $Y\in
G^{\prime}$, where $G^{\prime}$ is a subset of $G$ satisfying

${\mathbf{P}}_{Y}(Y\in G^{\prime})\geq{\mathbf{P}}_{Y}(Y\in
G)/N^{O_{C,\varepsilon}(1)}=\rho_{b}/N^{O_{C,\varepsilon}(1)}.$ (8.9)

For each $1\leq i\leq r$, we express $q_{i}(Y)$ in terms of the generators of
$Q_{Y}$ for each $Y\in G^{\prime}$,

$q_{i}(Y)=c_{i1}(Y)g_{1}(Y)+\dots+c_{ir}(Y)g_{r}(Y)\ \operatorname{mod}\ p,$

where $c_{i1}(Y),\dots c_{ir}(Y)$ are integers bounded by
$n^{O_{C,\varepsilon}(1)}$, and $g_{i}(Y)$ are the generators of $Q_{Y}$.
Furthermore, as the $q_{i}(Y)$ span $Q_{Y}$, the vectors
$(c_{11},\dots,c_{1r}),\dots,(c_{r1},\dots c_{rr})$ span
${\mathbb{Z}}^{{\operatorname{rank}}(Q_{Y})}$.

We show that there are many $Y$ that correspond to the same coefficients
$c_{i_{1}i_{2}}$.

######  Claim 8.10.

There exists a (“dense”) subset $G^{\prime\prime}\subset G^{\prime}$ such that
the following holds

  * •

${\mathbf{P}}_{Y}(Y\in G^{\prime\prime})\geq{\mathbf{P}}_{Y}(Y\in
G^{\prime})/N^{O_{C,\varepsilon}(1)}\geq\rho_{b}/N^{O_{C,\varepsilon}(1)};$

  * •

there exist $r$ tuples $(c_{11},\dots,c_{1r}),\dots,(c_{r1},\dots c_{rr})$,
whose components are integers bounded by $n^{O_{C,\varepsilon}(1)}$ and
$(c_{11},\dots,c_{1r}),\dots,(c_{r1},\dots c_{rr})$ span
${\mathbb{Z}}^{{\operatorname{rank}}(Q_{Y})}$ such that for all $Y\in
G^{\prime\prime}$

$q_{i}(Y)=c_{i1}g_{1}(Y)+\dots+c_{ir}g_{r}(Y)\mbox{ for $i=1,\dots,r$.}$

###### Proof of Claim 8.10.

Consider the collection $\mathcal{C}$ of the coefficient-tuples

$\mathcal{C}:=\Big{\\{}\Big{(}\big{(}c_{11}(Y),\dots,c_{1r}(Y)\big{)};\dots;\big{(}c_{r1}(Y),\dots
c_{rr}(Y)\big{)}\Big{)},Y\in G^{\prime}\Big{\\}}.$

Because the number of possibilities these tuples can take is at most
$(N^{O_{C,\varepsilon}(1)})^{r^{2}}=N^{O_{C,\varepsilon}(1)}$, again by the
pigeon-hole principle there exists a coefficient-tuple, say
$\Big{(}(c_{11},\dots,c_{1r}),\dots,(c_{r1},\dots
c_{rr})\Big{)}\in\mathcal{C}$, such that

$\displaystyle\quad\Big{(}\big{(}c_{11}(Y),\dots,c_{1r}(Y)\big{)};\dots;\big{(}c_{r1}(Y),\dots
c_{rr}(Y)\big{)}\Big{)}$
$\displaystyle=\Big{(}(c_{11},\dots,c_{1r}),\dots,(c_{r1},\dots
c_{rr})\Big{)}$

for all $Y$ from a subset $G^{\prime\prime}$ of $G^{\prime}$ which satisfies

${\mathbf{P}}_{Y}(Y\in G^{\prime\prime})\geq{\mathbf{P}}_{Y}(Y\in
G^{\prime})/N^{O_{C,\varepsilon}(1)}\geq\rho_{b}/N^{O_{C,\varepsilon}(1)}.$
(8.11)

∎

Now we focus on the elements of $G^{\prime\prime}$. Because $|I_{Y}|\geq
N-N^{\varepsilon}$ for each $Y\in G^{\prime\prime}$, by an averaging argument
we can obtain the following.

######  Claim 8.12.

There is a set $I$ of size $N-3N^{\varepsilon}$ such that
$I\cap\\{1,\dots,r\\}=\emptyset$ and for each $i\in I$ we have

${\mathbf{P}}_{Y}(i\in I_{Y},Y\in G^{\prime\prime})\geq{\mathbf{P}}_{Y}(Y\in
G^{\prime\prime})/2.$ (8.13)

Now we conclude the proof of Lemma 8.8. Fix an arbitrary index $i$ from $I$.
We concentrate on those $Y\in G^{\prime\prime}$ where the index $i$ belongs to
$I_{Y}$. Because $q_{i}(Y)\in Q_{Y}$, we can write

$q_{i}(Y)=c_{1}(Y)g_{1}(Y)+\dots c_{r}(Y)g_{r}(Y)\ \operatorname{mod}\ p,$

where $c_{1}(Y),\dots,c_{r}(Y)$ are integers bounded by
$N^{O_{C,\varepsilon}(1)}$.

For short, we denote by $v_{i,Y}$ the vector $(c_{1}(Y),\dots c_{r}(Y))$, we
also use the shorthand $v_{j}$ for the vectors $(c_{j1},\dots,c_{jr})$
obtained from Claim 8.10.

Because $Q_{Y}$ is spanned by $q_{1}(Y),\dots,q_{r}(Y)$, we must have
$k:=\det({v}_{1},\dots v_{r})\neq 0\ \operatorname{mod}\ p$ (and hence $k\neq
0$ because $p\geq n^{A}$ with sufficiently large $A$) and that in
${\mathbb{Z}}/p{\mathbb{Z}}$

$\displaystyle kq_{i}(Y)+\det({v}_{i,Y},{v}_{2},\dots,{v}_{r})q_{1}(Y)+\dots$
$\displaystyle+\det({v}_{i,Y},{v}_{1},\dots,{v}_{r-1})q_{r}(Y)=0.$

Furthermore, because each coefficient of the identity above is bounded by
$n^{O_{C,\varepsilon,\mu}(1)}$, there exists a subset $G_{i}^{\prime\prime}$
of $G^{\prime\prime}$ such that all $Y\in G_{i}^{\prime\prime}$ correspond to
the same identity, and

$\displaystyle{\mathbf{P}}_{Y}(Y\in G_{i}^{\prime\prime})$
$\displaystyle\geq({\mathbf{P}}_{Y}(Y\in
G^{\prime\prime})/2)/(N^{O_{C,\varepsilon}(1)})^{r}$
$\displaystyle\geq\rho_{b}/N^{O_{C,\varepsilon}(1)}.$

In other words, there exist integers $k_{1},\dots,k_{r}$, all bounded by
$N^{O_{C,\varepsilon}(1)}$, such that

$kq_{i}(Y)+k_{1}q_{1}(Y)+\dots+k_{r}q_{r}(Y)=0$

for all $Y\in G_{i}^{\prime\prime}$.

Note that $k$ is independent of the choice of $i$ and $Y$. Finally recall that
$q_{i}=\sum_{j}b_{ij}y_{j}=B_{i}(Y)$, we thus complete the proof of Lemma 8.8.
∎

After proving our inverse result for bilinear forms, by using a decoupling
method (similarly to Lemma 7.4) we can also obtain the following analog of
Theorem 8.3 for quadratic forms, which is another highlight of the section.

######  Theorem 8.14.

Let $C>0$ and $\varepsilon>0$. Then there exists a constant $A$ such that the
following holds for any prime $p\geq n^{A}$. Assume that $B=(b_{ij})_{1\leq
i,j\leq N}$ is a symmetric array of elements of ${\mathbb{Z}}/p{\mathbb{Z}}$
so that

$\rho_{q}:=\sup_{a\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{P}}_{X}(\sum_{i,j\leq
n}b_{ij}x_{i}x_{j}=a)\geq N^{-C},$

where $X=(x_{1},\dots,x_{n})$, and $x_{i}$ are i.i.d. copies of $\xi$. Then,
there exist an integer $k\neq 0,|k|=N^{O_{C,\varepsilon}(1)}$, a set of
$r=O(1)$ rows ${\mathbf{r}}_{i_{1}},\dots,{\mathbf{r}}_{i_{r}}$ of $B$, and
set $I$ of size at least $N-2N^{\varepsilon}$ such that for each $i\in I$,
there exist integers $k_{ii_{1}},\dots,k_{ii_{r}}$, all bounded by
$N^{O_{C,\varepsilon}(1)}$, such that the following holds.

${\mathbf{P}}_{Z}\Big{(}Z\cdot(k{\mathbf{r}}_{i}(B)+\sum_{j=1}^{r}k_{ii_{j}}{\mathbf{r}}_{i_{j}}(B))=0\
\operatorname{mod}\ p\Big{)}\geq N^{-O_{C,\varepsilon}(1)},$ (8.15)

where $Z=(z_{1},\dots,z_{N})$ and $z_{i}$ are i.i.d. copies of
$(u-u^{\prime})(\xi-\xi^{\prime})$, where $u,u^{\prime},\xi,\xi$ are
independent and $u,u^{\prime}$ are Bernoulli random variables of parameter
$1/2$.

A proof of this result is given in Appendix A.

To conclude the section, when working with Laplacian matrices our random
vectors will be adapted along an index set $I_{0}$ as in Definition 7.3.
However the above result automatically applies if we restrict to the
coefficients indexed from $I_{0}$. In other words we have

######  Corollary 8.16.

Let $C>0$ and $\varepsilon>0$. Then there exists a constant $A$ such that the
following holds for any prime $p\geq n^{A}$. Assume that $X$ is adapted to
$I_{0}$ as in Definiotion 7.3 where $|I_{0}|\geq\varepsilon N$ and

$\sup_{a\in{\mathbb{Z}}/p{\mathbb{Z}}}{\mathbf{P}}_{X}(\sum_{i,j\in
I_{0}}b_{ij}x_{i}x_{j}=a)\geq N^{-C}.$

Then, there exist an integer $k\neq 0,|k|=N^{O_{C,\varepsilon}(1)}$, a set of
$r=O(1)$ rows ${\mathbf{r}}_{i_{1}},\dots,{\mathbf{r}}_{i_{r}}$ of $B$, and
set $I\subset I_{0}$ of size at least $|I_{0}|-2N^{\varepsilon}$ such that for
each $i\in I$, there exist integers $k_{ii_{1}},\dots,k_{ii_{r}}$, all bounded
by $N^{O_{C,\varepsilon}(1)}$, such that the following holds.

${\mathbf{P}}_{Z}\Big{(}Z_{I_{0}}\cdot(k{\mathbf{r}}_{i}(B)+\sum_{j=1}^{r}k_{ii_{j}}{\mathbf{r}}_{i_{j}}(B))_{I_{0}}=0\
\operatorname{mod}\ p\Big{)}\geq N^{-O_{C,\varepsilon}(1)},$ (8.17)

where $Z=(z_{1},\dots,z_{N})$ and $z_{i}$ are as in Theorem 8.14.

Theorem 8.2 will be exploited many times in our next section. Also, Corollary
8.16 will play a key role in the proof of Lemma 9.4.

##  9\. Treatment for large primes: proof of Propositions 2.5 and 2.7

For a sufficiently positive small constant $c$ (to be fixed throughout the
section) we let

${\mathfrak{P}}_{n}:=\Big{\\{}p\textrm{ prime},e^{n^{c}}\leq
p\leq(C_{\xi}\sqrt{n})^{n}\Big{\\}}.$

###  9.1. Outline for the symmetric and Laplacian models

As usual, $G_{N}$ stands for the principle minor $M_{N}$ for symmetric
matrices, or the principle minor $L_{N}^{\ast}$ (after the neighbor
reshuffling process) for laplacian matrices.

Let us start from $G_{N_{0}}$, where

$N_{0}=\lfloor cn\rfloor.$

Consider the event ${\mathcal{E}}_{N,non-sing}$ that the matrix $G_{N}$ is
non-singular in ${\mathbb{R}}$ (or ${\mathbb{Z}}$); we are going to work on
the intersection of all these events.

######  Definition 9.1.

Let ${\mathcal{E}}_{non-sing}$ be the intersection of all
${\mathcal{E}}_{N,non-sing}$, where $N_{0}\leq N\leq n$. Note that this event
is independent of $p$. By Corollary 7.18,

${\mathbf{P}}({\mathcal{E}}_{non-sing})=1-\exp(-\Theta(n^{c})).$

Let ${\mathfrak{W}}_{N_{0}}$ be the list of primes $p\in{\mathfrak{P}}_{n}$
such that $p|\det(G_{N_{0}})$, this is the list of bad primes. Notice that as
by Hadamard’s bound, $|\det(G_{N})|\leq(C_{\xi}N)^{N/2}$, and so, counting
multiplicities we have

$|{\mathfrak{W}}_{N_{0}}|\leq\frac{(N_{0}/2)\log(C_{\xi}N)}{n^{c}}\leq n.$

Notice that for $p\in{\mathfrak{W}}_{N_{0}}$ and $p\in{\mathfrak{P}}_{n}$, the
${\operatorname{rank}}(G_{N_{0}}/p)$ could be as small as
$N_{0}-\frac{(N_{0}/2)\log(C_{\xi}N)}{n^{c}}\geq N_{0}-n^{1-c/2}$, but we will
show that throughout the column exposure process below, this rank will be
improved fast and achieves the value at least $n-1$ in the last step.

For $N_{0}\leq N\leq n-1$, we consider the process of adding the $N+1$-th
column and $N+1$-th row to form $G_{N+1}$, note that for the Laplacian case,
this is Phase 2, obtained via the neighbors reshuffling.

After each step, let ${\mathfrak{W}}_{N+1}$ be the collection of primes
$p\in{\mathfrak{W}}_{N}$ that $G_{N+1}/p$ does not have full rank and the new
primes $p$ that did not belong to ${\mathfrak{W}}_{N}$ but
${\operatorname{rank}}(G_{N+1}/p)\leq N$. Notice that for these new primes, as
$p\notin{\mathfrak{W}}_{N}$, we have ${\operatorname{rank}}(G_{N}/p)=N$, and
so ${\operatorname{rank}}(G_{N+1}/p)$ must be $N$ in this case. As of now, we
will want to make sure that for the newly arising primes the rank are not very
small, especially in the very last steps, because otherwise adding the last
few rows and columns will not increase the ranks to at least $n-1$ as desired.
Another remark here is that, as $0<|\det(G_{N+1})|\leq(C_{\xi}N)^{N/2}$, the
number of newly arising primes is bounded by $(N/2)\log(C_{\xi}N)/n^{c}\leq
n$. So we trivially have

$|{\mathfrak{W}}_{N+1}|\leq|{\mathfrak{W}}_{N}|+n\leq(N+1)n.$

Our key result of this section is the following proposition.

######  Proposition 9.2.

Let $C>0$ be a given large constant. There is an event
${\mathcal{E}}={\mathcal{E}}_{N}$ in characteristic zero with probability at
least $1-n^{-C}$ such that under this event, for any $p\in{\mathfrak{W}}_{N}$,
and for all $N_{0}\leq N\leq n-1$ we have

${\operatorname{rank}}(G_{N+1}/p)=\min\\{{\operatorname{rank}}(G_{N}/p)+2,N+1\\}.$

It is clear that this proposition would then imply Proposition 2.5 because
with probability at least $1-O(n^{-C+3})$ (on the intersection of
$\cap_{N_{0}\leq N\leq n}{\mathcal{E}}_{N}$), for all $p\in{\mathfrak{P}}_{n}$
we have ${\operatorname{rank}}(G_{n-1}/p)\geq n-1$ as
${\operatorname{rank}}(G_{n}/p)$ becomes full after exposing the last $n$-th
row and column for all $p\in{\mathfrak{W}}_{n-1}$, and for newly arising
primes $p$ we have
${\operatorname{rank}}(G_{n}/p)={\operatorname{rank}}(G_{n-1}/p)=n-1$ as
$p\notin{\mathfrak{W}}_{n-1}$.

Before moving to discuss the technical details, we pause to compare the
current method with that of [NW22, Section 6] for the i.i.d. model. Both
methods rely on the “watch list” argument. However, unlike in the i.i.d. case,
here at the starting point $N=N_{0}$ some prime $p$ in the list
${\mathfrak{W}}_{N}$ might have very high multiplicities. Fortunately, each
exposure step usually improves the rank by 2 (rather than by 1 as in the
i.i.d. case) thanks to Proposition 9.2. So the rank over ${\mathbb{F}}_{p}$
will become almost full very fast. When the rank becomes full we remove $p$
from the watch list ${\mathfrak{W}}_{N}$, but this $p$ might reappear later in
the process, the difference now is that the corank over ${\mathbb{F}}_{p}$
will be at most one as we have seen above.

In the remaining part we prove Proposition 9.2, which is an innovative part of
the treatment. We will mainly focus on the Laplacian model (and hence
$G_{N}=L_{N}^{\ast}$) as the symmetric case will follow almost automatically.
Our proof consists of three steps outlined below

  * •

Step 1. If

${\mathbf{P}}({\operatorname{rank}}(G_{N+1}/p)=\min\\{{\operatorname{rank}}(G_{N}/p)+2,N+1\\})\leq
1-n^{-C},$

where the randomness is on the $N+1$-th column and $N+1$-th row (of the
reshuffling process), then by Theorem 8.14 and Corollary 8.16 there is a
“local” $O(1)$-normal vector of $G_{N}$ which has partially rich structure in
${\mathbb{F}}_{p}$. Here $C$ is large enough to compensate with the loss of
the watching list argument after taking union bound over all primes from
${\mathfrak{W}}_{N},N\leq n-1$. We refer the reader to Subsection 9.2 for
precise statements.

  * •

Step 2. We then use Definition 1.28 to pass to the symmetric model, showing
that the event that a local normal vector is partially structured but not
fully structured has probability $n^{-An}$ with large $A$, for which we can
take union bound over all $p\in{\mathfrak{P}}_{n}$. This step is carried out
in Subsection 9.3.

  * •

Step 3. It remains to estimate the event that there is a fully structured
normal vector for each $p$ in the watch list. We then use the low rank and
rich structure to show that this event for $p\geq e^{n^{c}}$ can be passed to
characteristic zero, and henceforth to ${\mathbb{Z}}/p{\mathbb{Z}}$ for some
$e^{n^{c/2}}\leq p\leq e^{n^{c}}$, while for the latter setting we have shown
in the previous section that this hold with probability
$\exp(-\Theta(n^{c}))$. We will complete this final step in Subsection 9.4.

From now on, if not specified otherwise, $p$ is a prime from
${\mathfrak{P}}_{n}$.

###  9.2. Step 1: normal vectors with adapted structures.

In what follows, for the Laplacian case we recall that the randomness is from
Phase 2 of Definition 1.23. That is $I_{0}=I_{N+1}$ is the set of indices from
$v_{1},\dots,v_{N}$ that is connected to exactly one vertex from the pair
$\\{v_{N+1},v_{N+2}\\}$. Recall (1.27), by Chernoff’s bound with probability
at least $1-\exp(-\Theta(n^{1-c}))$, for all $N_{0}\leq N\leq n-1$ we have

$|I_{0}|\in[N/2-N^{1-c/2},N/2+N^{1-c/2}].$ (9.3)

######  Lemma 9.4.

Let $0<\varepsilon<1,C>0$ be given constants. Under ${\mathcal{E}}_{non-
sing}$, assume that $N\geq N_{0}$, and

${\mathbf{P}}\Big{(}{\operatorname{rank}}(G_{N+1}/p)=\min\\{{\operatorname{rank}}(G_{N}/p)+2,N+1\\}\Big{)}\leq
1-n^{-C},$

where the randomness is on the random reshuffling process with respect to
$v_{N+1}$ and $v_{N+2}$. Then there exist a constant $C_{\ast}$ depending on
$C,c,\varepsilon$ and there exist a non-zero vector ${\mathbf{v}}$ and a
subset $J_{0}\subset I_{0}$ such that

  * •

$|J_{0}|\geq|I_{0}|-2N^{1-c/2}$;

  * •

all of the entries of ${\mathbf{v}}_{J_{0}}$ belong to a GAP of size at most
$n^{C_{\ast}}$ and rank at most $C_{\ast}$,

  * •

${\mathbf{v}}$ is orthogonal to all but at most $C_{\ast}$ rows of $G_{N}$.

###### Proof of Lemma 9.4.

As we are working with primes $p>\exp(n^{c})$, if we are on the event
${\mathcal{E}}_{non-sing}$ (in particularly $\det(G_{N})\neq 0$) then as
$|\det(G_{N})|\leq(C_{\xi}N)^{N/2}$, we have that

$k={\operatorname{rank}}(G_{N}/p)\geq N-N^{1-c/2}.$

Case 1. Assume that $k\leq N-1$. Let $G_{J\times J}$ be a submatrix in $G_{N}$
of full rank, $|J|=k$, where $J=\\{i_{1},\dots,i_{k}\\}$. We add one more
column corresponding to the vertex $v_{N+1}$ and consider the matrix
$G_{J\times(J\cup\\{v_{N+1}\\})}$. Let $H$ be the subspace generated by the
rows of this matrix, and let
${\mathbf{v}}^{\prime}=(v_{i_{1}},\dots,v_{i_{k+1}})$ be a normal vector of
$H$. When we expose the $N+1$-th vector $X_{N+1}$, as we have seen in Section
7, if $(x_{i_{1}},\dots,x_{i_{k}},x_{N+1})\notin H$ then
${\operatorname{rank}}(G_{N+1}/p)={\operatorname{rank}}(G_{N}/p)+2$. So we
must have $(x_{i_{1}},\dots,x_{i_{k}},x_{N+1})\in H$, and hence

${\mathbf{v}}^{\prime}\cdot(x_{i_{1}},\dots,x_{i_{k}},x_{N+1})=0.$ (9.5)

We will restrict the above event to the randomness over $x_{i_{j}}$ where
$i_{j}\in I_{0}\cap J$. Recall that as $|J|\geq N-N^{1-c/2}$ and
$I_{0}\subset[N]$ satisfying (9.3), we have

$|I_{0}\cap J|\geq N/2-2N^{1-c/2}.$

By Theorem 8.2, the event of (9.5) has probability smaller than $N^{-C}$
except all but $N^{\prime}=N^{1-c/2}$ of the entries of the
$v_{i_{j}},i_{j}\in I_{0}\cap J$ belong to a GAP structure of size
$O(\rho_{l}({\mathbf{v}}^{\prime})^{-1}/\sqrt{N^{1-c/2}})$. To complete the
proof, by definition ${\mathbf{v}}^{\prime}$ is orthogonal to all columns of
$G_{J\times[N]}$ (because $G_{J\times J}$ has the same rank as $G_{N}$), and
hence the vector ${\mathbf{v}}$ obtained from ${\mathbf{v}}^{\prime}$ by
appending $N-k-1$ components of value zero is orthogonal to all columns of
$G_{N}$. Case 2. Assume that $k=N$. In this case $G_{J\times J}=G_{N}$. Let
$B=(b_{ij})$ be the inverse matrix $G_{N}^{-1}$. As we have seen in (7.9), by
adding a new row and column (associated to $v_{N+1}$) we see that the rank
does increase unless $\sum_{i,j\in I_{0}}b_{ij}x_{i}x_{j}=0$. Assume that this
holds with probability at least $n^{-C}$, then we can apply Corollary 8.16.
For each $i\in I$ obtained by this corollary (where we recall that $I$ is of
subset size at least $|I_{0}|-2n^{\varepsilon}$ of $I_{0}$) let

${\mathbf{r}}_{i}^{\prime}=k{\mathbf{r}}_{i}(B)+\sum_{j=1}^{r}k_{ii_{j}}{\mathbf{r}}_{i_{j}}(B).$

Because $B$ has rank $m$, the rows ${\mathbf{r}}_{i}(B)$ are linearly
independent, and so ${\mathbf{r}}_{i}^{\prime}$ is non-zero for
$i\notin\\{i_{1},\dots,i_{r}\\}$. We fix one such non-zero vector
${\mathbf{v}}^{\prime}={\mathbf{r}}_{i_{0}}^{\prime}$, and in this case set
${\mathbf{v}}:={\mathbf{v}}^{\prime}$. By definition ${\mathbf{v}}$ is
orthogonal to all but only $r+1$ columns of indices from
${i_{0},i_{1},\dots,i_{r}}$. Furthermore by (8.4) we have that

${\mathbf{P}}_{Z}\Big{(}Z\cdot{\mathbf{v}}=0\ \operatorname{mod}\ p\Big{)}\geq
n^{-O_{C,\varepsilon}(1)},$

where $Z$ is adapted to $I_{0}$. As a direct application of Theorem 8.2, we
then infer that all but $n^{\varepsilon}$ of the entries of
${\mathbf{v}}_{I_{0}}$ belongs to a GAP structure of size $O(n^{O(1)})$ and
rank $O(1)$ as claimed. ∎

We note from the proof above that ${\mathbf{v}}$ is defined via $B$, and hence
$G_{J\times J}$, a submatrix of full rank in $G_{N}$. Hence it is natural to
call ${\mathbf{v}}$ a local (w.r.t. $J$) almost normal vector of $G_{N}$. In
what follows, for given $C$ and $c,\varepsilon$, the parameter
$C_{\ast}=C_{\ast}(C,c,\varepsilon)$ is always chosen as in the conclusion of
Lemma 9.4. Motivated by this result, it is natural to define the following
notion of partially structured vectors.

######  Definition 9.6.

Let $J_{0}\subset[N]$ be given. Let $C_{\ast},C_{\ast}^{\prime},\varepsilon>0$
be constants (where $C_{\ast}=C_{\ast}(C,c,\varepsilon)$).

  * •

(partially structured) We say ${\mathbf{v}}\in{\mathbb{F}}_{p}^{N}$ is a
$J_{0}$-structured almost normal vector with respect to $G_{N}$ (and with
respect to the parameter $C_{\ast}$) if all components of
${\mathbf{v}}_{J_{0}}$ come from a GAP (over ${\mathbb{Z}}/p{\mathbb{Z}}$)
with size at most $n^{C_{\ast}}$ and rank at most $C_{\ast}$ and
${\mathbf{v}}$ is orthogonal to all but at most $C_{\ast}$ columns of $G_{N}$.

  * •

(fully structured) We say that ${\mathbf{v}}$ is a fully structured almost
normal vector (with respect to the parameters $C_{\ast}^{\prime},\varepsilon$)
if all but $n^{\varepsilon}$ components of ${\mathbf{v}}$ come from a GAP
(over ${\mathbb{Z}}/p{\mathbb{Z}}$) with size at most $n^{C_{\ast}^{\prime}}$
and rank at most $C_{\ast}^{\prime}$ and ${\mathbf{v}}$ is orthogonal to all
but $C_{\ast}^{\prime}$ columns of $G_{N}$.

By Lemma 9.4, if $G_{N}$ has an almost normal vector that is not locally
structured then we would be done with the proof of Proposition 9.2. Hence we
need to work with the event that $G_{N}$ has a non-trivial almost normal
vector that is $J_{0}$-structured for some $J_{0}$. On the other hand, for the
step of passing to all primes in ${\mathfrak{P}}_{n}$ at once it is desirable
to have fully structured vectors instead, which motivated us to introduce
Definition 9.6 and add another twist into the plan to treat with locally but
not fully structured below. We notice that this problem only occurs in the
Laplacian case; for the random symmetric model $I_{0}$ is already the whole
set $[N]$ and in this case we can completely skip these extra treatments.

###  9.3. Step 2: partially but not fully structured almost normal vectors of
Laplacian matrices

Note that in the Laplacian model, after Phase 1 of Definition 1.28 the degree
sequence ${\mathbf{d}}=(d_{1},\dots,d_{n+1})$ is fixed, and also by (1.25)
with probability $1-\exp(-\Theta(n))$

$d_{1},\dots,d_{n+1}\in[(1/2-\varepsilon)n,(1/2+\varepsilon)n].$ (9.7)

For convenience we define

######  Definition 9.8.

Let ${\mathcal{E}}_{mixing}$ be the intersection of the events from (9.7) and
from (9.3) and for all $N_{0}\leq N\leq n-1$. Note that this event is on the
graph and is independent of $p$ and

${\mathbf{P}}({\mathcal{E}}_{mixing})\geq 1-\exp(-\Theta(n^{1-c})).$

We will show the following

######  Lemma 9.9 (structure propagation in perturbed symmetric matrices).

Let $0<\varepsilon<1$ and $A,C>0$ be given constants. Then there exists a
constant $C_{\ast}^{\prime}$ such that the following holds for all
$p\in{\mathfrak{P}}_{n}$, and on ${\mathcal{E}}_{mixing}$. The probability of
the intersection of the events that all principle minors $G_{N},N_{0}\leq
N\leq n$ have non-zero determinant and that there exist $N$ in the above range
and a local almost normal vector of $G_{N}/p$ that is $J_{0}$-structured (with
respect to $C_{\ast}$ as in Lemma 9.4 for given $C,\varepsilon,c$) for some
$J_{0}\subset[N]$ of size at least $N/2-2N^{1-c/2}$ but not fully structured
with respect to $C_{\ast}^{\prime},\varepsilon$ is bounded by $O(n^{-An})$,
where the implied constants are allowed to depend on the given constants.

Note again that it would be more natural to have the probability bound of the
form $O(N^{-AN})$ for each $N$, but by changing $A$ we can replace the bounds
by $O(n^{-An})$ for convenience. We will prove Lemma 9.9 by passing to random
symmetric matrices of given diagonal entries, via Definition 1.28 of the
Laplacians. We can do this thanks to the key lemma below which roughly says
that the rare event is very rare.

######  Lemma 9.10 (partial structure in perturbed random symmetric matrices).

Let $0<\varepsilon<1$ and $A,C>0$ be given constants. Then there exists a
constant $C_{\ast}^{\prime}$ such that the following holds. Let
$p\in{\mathfrak{P}}_{n}$. Let ${\mathbf{d}}=(d_{1},\dots,d_{n+1})$ be an
degree sequence so that

${\mathbf{P}}\big{(}G(n+1,1/2)\in G_{{\mathbf{d}}}\big{)}\geq n^{-4n}.$

Assume that $M_{n}$ is the random symmetric matrix as in Theorem 1.3. Then on
the intersection of the event ${\mathcal{E}}_{non-sing}$ in ${\mathbb{Z}}$
that all principle minors $M_{N}-D_{N},N_{0}\leq N\leq n$ have non-zero
determinant (where $D_{N}={\operatorname{diag}}(d_{1},\dots,d_{N})$ is the
diagonal matrix with entries $d_{i}$), the event that there exists $N$ in the
above range and a local almost normal vector ${\mathbf{v}}$ of
$(M_{N}-D_{N})/p$ that is $J_{0}$-structured (with respect to $C_{\ast}$) for
some $J_{0}\subset[N]$ satisfying $|J_{0}|\geq N/2-2N^{1-c/2}$ but
${\mathbf{v}}$ is not fully structured with respect to
$C_{\ast}^{\prime},\varepsilon$ has probability bounded by $O(n^{-An})$.

We then deduce the following version for random matrices of given degree
sequence.

######  Corollary 9.11.

Let $0<\varepsilon<1$ and $C>0$ be given. There there exists a constant
$C_{\ast}^{\prime}$ such that the following holds. Let
${\mathbf{d}}=(d_{1},\dots,d_{n+1})$ be an degree sequence with $(1/2-c)n\leq
d_{i}\leq(1/2+c)n$ so that

${\mathbf{P}}(G(n+1,1/2)\in G_{{\mathbf{d}}})\geq n^{-4n}.$

Let $G_{\mathbf{d}}$ be a random graph in ${\mathcal{G}}_{{\mathbf{d}}}$
defined in Phase 2 of Definition 1.28,

${\mathbf{P}}(G_{{\mathbf{d}}}=G):=\frac{{\mathbf{P}}(G(n+1,1/2)=G)}{{\mathbf{P}}(G(n+1,1/2)\in{\mathcal{G}}_{d})},\mbox{
for each $G$ of degree sequence ${\mathbf{d}}$}.$

Then the conclusion of Lemma 9.10 holds for the matrix $L_{n,{\mathbf{d}}}$
obtained from $M_{G_{\mathbf{d}}}-{\operatorname{diag}}({\mathbf{d}})$ by
removing the last row and column.

###### Proof of Corollary 9.11.

Let $M_{n+1}$ be the adjacency matrix of $G(n+1,1/2)$ and let
${\mathcal{C}}_{{\mathbf{d}}}$ be the event that
$G(n+1,1/2)\in{\mathcal{G}}_{\mathbf{d}}$ (that is
$\\{M_{n+1}\in{\mathcal{C}}_{\mathbf{d}}\\}=\\{G(n+1,1/2)\in{\mathcal{G}}_{\mathbf{d}}\\}$).
Then by definition ${\mathbf{P}}(M_{n+1}\in{\mathcal{C}}_{\mathbf{d}})\geq
n^{-4n}$ and for each $G\in{\mathcal{G}}_{\mathbf{d}}$

${\mathbf{P}}(M_{G_{\mathbf{d}}}=M_{G})=\frac{{\mathbf{P}}(M_{n+1}=M_{G})}{{\mathbf{P}}(M_{n+1}\in{\mathcal{C}}_{\mathbf{d}})}.$

Let ${\mathcal{F}}$ be the set of square matrices (of size $n$) where every
$J_{0}$-structured normal vectors is fully structured, and let ${\mathcal{E}}$
be the non-singularity event ${\mathcal{E}}_{non-sing}$ considered in Lemma
9.10. We have (where $L_{n}(M_{n+1})$ is the principle minor of
$M_{n+1}-{\operatorname{diag}}({\mathbf{d}})$)

$\displaystyle{\mathbf{P}}(L_{n,{\mathbf{d}}}\in{\mathcal{E}}\cap\bar{{\mathcal{F}}})$
$\displaystyle=\frac{{\mathbf{P}}(L_{n}(M_{n+1})\in{\mathcal{E}}\cap\bar{{\mathcal{F}}}\wedge
M_{n+1}\in{\mathcal{C}}_{\mathbf{d}})}{{\mathbf{P}}(M_{n+1}\in{\mathcal{C}}_{\mathbf{d}})}\leq\frac{{\mathbf{P}}(L_{n}(M_{n+1})\in{\mathcal{E}}\cap\bar{{\mathcal{F}}}\wedge
M_{n+1}\in{\mathcal{C}}_{\mathbf{d}})}{n^{-4n}}$
$\displaystyle=O(n^{-(A-4)n}),$

where in the last estimate we applied Lemma 9.10. ∎

###### Proof of Lemma 9.9.

On ${\mathcal{E}}_{mixing}$ we have (recalling that $G_{n}=L_{n}$)

$\displaystyle{\mathbf{P}}(L_{n}\in{\mathcal{E}}\cap\bar{{\mathcal{F}}}\cap{\mathcal{E}}_{mixing})$
$\displaystyle\leq\sum_{{\mathbf{d}};{\mathbf{P}}(G(n+1,1/2)\in{\mathcal{G}}_{{\mathbf{d}}})\geq
n^{-4n}}{\mathbf{P}}(M_{n+1}\in{\mathcal{E}}\cap\bar{{\mathcal{F}}}|M_{n+1}\in{\mathcal{C}}_{{\mathbf{d}}}){\mathbf{P}}(M_{n+1}\in{\mathcal{C}}_{{\mathbf{d}}})$
$\displaystyle=\sum_{{\mathbf{d}};{\mathbf{P}}(G(n+1,1/2)\in{\mathcal{G}}_{{\mathbf{d}}})\geq
n^{-4n}}{\mathbf{P}}(L_{n,{\mathbf{d}}}\in{\mathcal{E}}\cap\bar{{\mathcal{F}}}){\mathbf{P}}(M_{n+1}\in{\mathcal{C}}_{{\mathbf{d}}})$
$\displaystyle=O(n^{-(A-4)n}).$

∎

What remains is to justify the symmetric matrix model.

###### Proof of Lemma 9.10.

Our proof is somewhat similar to those of Proposition 5.19 and Lemma 6.5. It
suffices to consider for a fixed $N$ in the range $N_{0}=\lfloor cn\rfloor\leq
N\leq n$. Assume that there is a local almost orthogonal vector
${\mathbf{v}}^{\prime}$ (from both cases of the proof of Lemma 9.4, not
including the $N-k$ appended zero components) that is $J_{0}$-structured for
some $J_{0}$ but not fully structured. We will show that the probability of
this event is as small as expected via two stages. In what follows we will use
the notation from the proof of Lemma 9.4.

Stage 1. Let ${\mathbf{v}}^{\prime}=({\mathbf{v}}_{0},{\mathbf{v}}_{1})$ be
the decomposition into the $J_{0}$-structured part ${\mathbf{v}}_{0}$ and the
remaining part ${\mathbf{v}}_{1}$, where
$J_{0}=\operatorname{supp_{index}}({\mathbf{v}}_{0})$. We will fix $J_{0}$
(there are crudely at most $2^{N}$ such $J_{0}$), where $|J_{0}|\geq
N/2-2N^{1-c/2}$ on ${\mathcal{E}}_{mixing}$, and
$|J_{1}|=|\operatorname{supp_{index}}({\mathbf{v}}_{1})|=|J\backslash
J_{0}|+1\leq N/2+2N^{1-c/2}$ (see the left picture from Figure 4.)

We will argue that ${\mathbf{v}}_{1}$ can be determined via ${\mathbf{v}}_{0}$
and some part of the matrix $G_{N}$. We will be focusing on Case 1 of the
proof of Lemma 9.4, the other case is similar. Using notation from that proof,
we have $G_{J\times(J\cup\\{N+1\\})}{\mathbf{v}}^{\prime}=0$, and so
$M_{0}{\mathbf{v}}_{0}+M_{1}{\mathbf{v}}_{1}=0$ where $M_{0}=G_{J\times
J_{0}}$ and $M_{1}=G_{J\times J_{1}}$. As the matrix
$G_{J\times(J\cup\\{N+1\\})}$ has full rank, the matrix $G_{J\times J_{1}}$
has rank at least $|J_{1}|-1$. Without loss of generality we assume that
$G_{J\times J_{1}}$ has rank $|J_{1}|$, and hence it has a square submatrix
$M_{1}^{\prime}$ of size $|J_{1}|$ which is non-singular.

######  Claim 9.12.

With probability at least $1-O(\exp(-n^{1+\varepsilon}))$, $M_{1}^{\prime}$
can take the form $M_{B\times J_{1}}$ where

$|B\cap J_{1}|\leq 5N^{1-c/2}.$

###### Proof.

We first choose $B^{\prime}=J_{0}\cup B^{\prime\prime}$ for any
$B^{\prime\prime}\subset J_{1}$ so that $|B^{\prime}|=J_{1}$. Then
$|B^{\prime}\cap J_{1}|\leq 4N^{1-c/2}$. By the proof of Lemma 5.5, we see
that the matrix $M_{B\times J_{1}}$ already has rank at least
$|J_{1}|-n^{1/2+\varepsilon}$ with probability at least
$O(\exp(-n^{1+2\varepsilon}))$. Hence by interchanging with at most
$n^{1/2+\varepsilon}$ row vectors of $M_{(J\backslash B^{\prime})\times
J_{1}}$, we can obtain $B$ for which $M_{B\times J_{1}}$ has full rank, and
that $|B\cap J_{1}|\leq|B^{\prime}\cap J_{1}|+n^{1/2+\varepsilon}\leq
5N^{1-c/2}$. ∎

Using the matrix $M_{1}^{\prime}=M_{B\times J_{1}}$ above, we will extract
from $M_{J\times(J\cup\\{v\\})}{\mathbf{v}}^{\prime}=0$ the portion
$M_{0}^{\prime}{\mathbf{v}}_{0}+M_{1}^{\prime}{\mathbf{v}}_{1}=0$, where
$M_{0}^{\prime}=M_{B\times J_{0}}$. After fixing $M_{0}^{\prime}$ and
$M_{1}^{\prime}$ we have

${\mathbf{v}}_{1}=(M_{1}^{\prime})^{-1}M_{0}{\mathbf{v}}_{0}.$

In summary, by conditioning on $M_{0}^{\prime}$ and $M_{1}^{\prime}$, and on a
realization of ${\mathbf{v}}_{0}$, the vector ${\mathbf{v}}_{1}$ is
determined. Note that by fixing $M_{0}^{\prime}$ and $M_{1}^{\prime}$, we have
fixed a submatrix of size $J_{1}\times[N]$ in $G_{N}$.

Set $A_{0}:=C_{\ast}$. There are
$N^{C_{\ast}N/2}p^{O(1)}=N^{A_{0}N/2}e^{O(n^{c})}$ ways to choose the
structured vector ${\mathbf{v}}_{0}$, and $O(2^{N}\times 2^{N})=O(4^{N})$ ways
to choose $J_{0}$ and the row index for $M_{1}^{\prime}$. Thus in total we
have a collection ${\mathcal{C}}_{0}$ of at most $N^{A_{0}N}$ ways to choose
the vectors ${\mathbf{v}}_{0},{\mathbf{v}}_{1}$.

$M_{0}^{\prime}$$M_{1}^{\prime}$${\mathbf{v}}_{0}$${\mathbf{v}}_{1}$${\mathbf{v}}_{1}^{\prime}$

${\mathbf{v}}_{0}$${\mathbf{v}}_{1}^{\prime}$${\mathbf{v}}_{1}^{\prime\prime}$$M_{0}^{\prime\prime}$$M_{1}^{\prime\prime}$$M_{0}^{\prime\prime}$

Figure 4. Finding non-structured subvectors.

Next we show that for a fixed ${\mathbf{v}}_{1}$ in the way above, by
exploiting the remaining randomness and the remaining equations from
$M_{0}{\mathbf{v}}_{0}+M_{1}{\mathbf{v}}_{1}=0$, the most part of
${\mathbf{v}}_{1}$ must be structured with extremely high probability. To do
this, let $(J_{1}\backslash B)^{+}$ and $(J_{1}\backslash B)^{-}$ be any two
parts of $J_{1}\backslash B$ of size almost equal. If the part
${\mathbf{v}}_{1}$ restricted to $J_{1}\backslash B$ has the property that

$\rho_{l}(({\mathbf{v}}_{1})_{(J_{1}\backslash B)^{+}})\leq n^{-K_{0}}\mbox{
or }\rho_{l}(({\mathbf{v}}_{1})_{(J_{1}\backslash B)^{-}})\leq n^{-K_{0}}$
(9.13)

for some large constant $K_{0}$ chosen depending on $A_{0}$ (i.e. on
$C_{\ast}$) and $A$. Without loss of generality assume that
$\rho_{l}(({\mathbf{v}}_{1})_{(J_{1}\backslash B)^{+}})\leq n^{-K_{0}}$. Then
by using the i.i.d. decomposition as in (6.3) and (6.4) we can bound the
probability that $M_{(J\cup\\{N+1\\})\times J}{\mathbf{v}}^{\prime}=0$ by

$\displaystyle{\mathbf{P}}(\exists{\mathbf{v}}^{\prime}\in{\mathcal{C}}_{0},M_{J\times(J\cup\\{v\\})}{\mathbf{v}}^{\prime}=0)$
$\displaystyle\leq\sup_{{\mathbf{a}}}{\mathbf{P}}(\exists{\mathbf{v}}^{\prime}\in{\mathcal{C}}_{0},M_{(J\backslash
B)\times(J_{1}\backslash B)}{\mathbf{v}}^{\prime}={\mathbf{a}})$
$\displaystyle\leq(1/n^{K_{0}})^{|(J_{1}\backslash B)^{-}|}N^{A_{0}N}4^{n}\leq
1/n^{NK_{0}/4}\leq 1/n^{An}.$

Hence it remains to assume that $\rho_{l}(({\mathbf{v}}_{1})_{(J_{1}\backslash
B)^{+}})\geq n^{-K_{0}}$ and $\rho_{l}(({\mathbf{v}}_{1})_{(J_{1}\backslash
B)^{-}})\geq n^{-K_{0}}$. Under these assumptions, however, Theorem 8.2
implies that $({\mathbf{v}}_{1})_{J_{1}\backslash B}$ is structured in the
sense that all but $n^{\varepsilon}$ element of
$({\mathbf{v}}_{1})_{J_{1}\backslash B}$ belongs to a GAP of size bounded by
$n^{K_{0}}$. Hence we have just shown that all but at most $n^{\varepsilon}$
exceptional entries of the vector
${\mathbf{v}}^{\prime}|_{J_{0}\cup(J_{1}\backslash B)}$ belong to a GAP of
size $n^{O(1)}$ and rank $O(1)$, where the implied constants depend on
$\varepsilon,K_{0}$. So crudely the collection ${\mathcal{C}}_{1}$ of such
structured vectors is now bounded by $n^{A_{1}n}$ for some sufficiently
constant depending on $A_{0},A,\varepsilon$.

Stage 2. Because the contribution of $n^{\varepsilon}$ exceptional entries can
be easily absorbed into the total number of unstructured entries, let us focus
only on the vector ${\mathbf{v}}_{1}|_{B\cap J_{1}}$, where we will show that
with extremely high probability all but $n^{O(\varepsilon)}$ entries of this
vector are structured. We have learned that $N^{\prime}:=|B\cap J_{1}|\leq
4N^{1-c/2}$. If $N^{\prime}\leq n^{\varepsilon}$ then we are done. Assume
otherwise, we will then apply the following variant of Lemma 5.5 and Claim
9.12 above.

######  Claim 9.14.

Assume that $I$ is an index set with $|I|=N^{\prime}$ where
$n^{\varepsilon}\leq N^{\prime}\leq 4N^{1-c/2}$. Then with probability at
least $1-\exp(-\Theta(N\times{N^{\prime}}^{\varepsilon}))$ the matrix
$G_{([N]\backslash I)\times I}$ has a square submatrix of size $|I|$ of rank
at least $|I|-{N^{\prime}}^{1/2+\varepsilon}$.

###### Proof.

We decompose the matrix $G_{([N]\backslash I)\times I}$ into $k=\lfloor
N/N^{\prime}\rfloor$ disjoint square matrices of type $M_{B_{1}\times
I},\dots,M_{B_{k}\times I}$ where $B_{1},\dots,B_{k}$ are arbitrary but
disjoint, each has size $N^{\prime}$ in $[N]\backslash I$. For each such
matrix, the probability it has rank at most
$|I|-{N^{\prime}}^{1/2+\varepsilon}$ is bounded by
$\exp(-\Theta({N^{\prime}}^{1+2\varepsilon}))$ by the argument of Lemma 5.5
(with $N^{\prime}$ in place of $n$). Because these matrices are independent,
the probability that at least one of these matrices has rank at least
$|I|-{N^{\prime}}^{1/2+\varepsilon}$ is bounded below by

$1-\exp(-\Theta(k{N^{\prime}}^{1+2\varepsilon}))\geq
1-\exp(-\Theta(N\times{N^{\prime}}^{\varepsilon})).$

∎

In our next step we work with ${\mathbf{v}}_{1}|_{B\cap J_{1}}$ as with
${\mathbf{v}}_{1}$ from Stage 1. By using the argument in Stage 1 (relying on
$M_{0}{\mathbf{v}}_{0}+M_{1}{\mathbf{v}}_{1}=0$, but now with a fixed
structured vector ${\mathbf{v}}^{\prime}|_{J_{0}\cup(J_{1}\backslash B)}$ from
${\mathcal{C}}_{1}$) to passing to a potential unstructured vector
${\mathbf{v}}_{1}^{\prime\prime}$ (see the right-side illustration in Figure
4) whose support is a subset of size at most ${N^{\prime}}^{1/2+\varepsilon}$
in $J_{1}$, where $\rho_{l}({\mathbf{v}}_{1}^{\prime\prime})\leq n^{-K_{2}}$
for some $K_{2}$ chosen sufficiently large compared to $A_{1},A,\varepsilon$.

One then iterate Claim 9.14 until we get a subvector supported on an index set
of size $O(n^{\varepsilon})$. It is clear that this process terminates after
$O(1)$ steps because the support size of the potential unstructured vectors
decreases from $N^{\prime}$ to ${N^{\prime}}^{1/2+\varepsilon}$ each time.

By gathering the structures together, we obtain a unified GAP (over
${\mathbb{Z}}/p{\mathbb{Z}}$), which might have large size and rank, but still
of order $O(n^{O(1)})$ and $O(1)$ respectively. Let $C_{\ast}^{\prime}$ be the
maximum of these constants (which depend on the choices of $K_{i}$, and hence
of $A$ and $\varepsilon$), we are done with the proof. ∎

To conclude this subsection, by combining Lemma 9.4 Lemma 9.9 we obtain the
following

######  Lemma 9.15.

Let $C,\varepsilon>0$ be given, where $C$ can be large and $\varepsilon$ can
be small. There exists a constant $C_{\ast}^{\prime}$, and there exists an
event ${\mathcal{E}}_{partial-full}$ of probability $1-n^{-An}$ such that on
the event ${\mathcal{E}}_{mixing}\wedge{\mathcal{E}}_{non-
sing}\wedge{\mathcal{E}}_{partial-full}$, assume that $N\geq cn$, and
${\mathbf{P}}({\operatorname{rank}}(G_{N+1}/p)=\min\\{{\operatorname{rank}}(G_{N}/p)+2,N+1\\})\leq
1-n^{-C}$ for some $p\in{\mathfrak{P}}_{n}$ (where the randomness is on the
$N+1$-th column and $N+1$-th row of the reshuffling process if in the
Laplacian case.) Then there exists a non-zero vector ${\mathbf{v}}$ such that
all but $n^{\varepsilon}$ of its entries belong to a GAP in
${\mathbb{Z}}/p{\mathbb{Z}}$ of size at most $n^{C_{\ast}^{\prime}}$ and rank
at most $C_{\ast}^{\prime}$ such that ${\mathbf{v}}$ is orthogonal to all but
at mot $C_{\ast}^{\prime}$ rows of $G_{N}$.

We end this section with a result for some restricting range of $p$, that will
be useful in Step 3. This result is an analog of Proposition 5.18 and 5.19 for
GAP structures.

######  Proposition 9.16.

Let $\varepsilon,C_{\ast}^{\prime}$ be given. Assume that $N\geq cn$ and
$e^{n^{c/2}}\leq p$. The probability that there exists a non-sparse vector
${\mathbf{v}}$ whose all but $n^{\varepsilon}$ entries belong to a GAP of size
at most $n^{C_{\ast}^{\prime}}$ and rank at most $C_{\ast}^{\prime}$ and
${\mathbf{v}}$ is orthogonal to all but at mot $C_{\ast}^{\prime}$ rows of
$G_{N}$ is bounded by $n^{-\Theta(n)}$.

We refer the reader to Appendix B for a proof of this result. We also refer
the reader to [NW22, Lemma 7.6] for a similar statement for non-symmetric
matrices.

###  9.4. Step 3: passing to characteristic zero and back

In what follows we let $W_{m}/p$ be the subspace generated by the columns
(rows) of $G_{m}$ over $p$. We first need the following

######  Lemma 9.17 (Lifting sparse normal vectors from
${\mathbb{Z}}/p{\mathbb{Z}}$ to ${\mathbb{R}}$).

[NW22, Lemma 6.5] Let $T>0$ be fixed 555In our application, as the matrix
entries in all models under consideration are bounded by $O(1)$, we can let
$T=1$, say, and assume $n$ to be sufficiently large.. Let $k,l,n$ be positive
integers with $l\leq k$, and $M$ a $l\times k$ matrix with integer entries
$|M_{ij}|\leq n^{T}$. If $p$ is a prime larger than $e^{(k\log k)/2+kT\log
n}$, then the rank of $M$ over ${\mathbf{Q}}$ is equal to the rank of $M/p$
over ${\mathbb{Z}}/p{\mathbb{Z}}$. This has the following corollaries.

  1. (1)

If $Z_{1},\dots,Z_{k}\in{\mathbb{Z}}^{l}$ are vectors with entries
$|Z_{ij}|\leq n^{T}$, and $Z_{1}/p,\dots,Z_{k}/p$ are linearly dependent in
$({\mathbb{Z}}/p{\mathbb{Z}})^{l}$, then $Z_{1},\dots,Z_{k}$ are also linearly
dependent in ${\mathbb{Z}}^{l}$.

  2. (2)

Let $Z_{1},\dots,Z_{i}\in{\mathbb{Z}}^{m}$ be vectors with entries
$|Z_{ij}|\leq n^{T}$ . If there is a non-zero vector
${\mathbf{w}}\in({\mathbb{Z}}/p{\mathbb{Z}})^{m}$ with at most $k$ non-zero
entries that is normal to $Z_{1}/p,\dots,Z_{l}/p$, then there is a non-zero
vector ${\mathbf{w}}^{\prime}\in{\mathbb{Z}}^{m}$ with at most $k$ non-zero
entries and normal to $Z_{1},\dots,Z_{l}$.

  3. (3)

The kernel of the map $M:{\mathbb{Z}}^{k}\rightarrow{\mathbb{Z}}^{l}$ surjects
onto the kernel of the map
$M:({\mathbb{Z}}/p{\mathbb{Z}})^{k}\rightarrow({\mathbb{Z}}/p{\mathbb{Z}})^{l}$.

We say a submodule of ${\mathbb{Z}}^{n}$ is _admissible_ if it is generated by
vectors with coordinates at most $n^{T}$ in absolute value. Recall that a
vector is structured (or fully structured) if it satisfies the hypothesis and
conclusion of Lemma 9.15.

######  Lemma 9.18 (Lifting and reducing structured vectors).

Let $\varepsilon$ be given sufficiently small (given $c,C,A,T$). Let $M_{0}$
be an admissible submodule of ${\mathbb{Z}}^{n}$, and $p$ be a prime $\geq
e^{n^{c}}$. Then $M_{0}$ has a structured almost normal vector in
${\mathbb{Z}}$ (that is all but $n^{\prime}=n^{\varepsilon}$ entries of it
belongs to a symmetric GAP with integral generators which has size at most
$n^{C_{\ast}^{\prime}}$ and rank at most $C_{\ast}^{\prime}$, where
${\mathbb{C}}_{\ast}^{\prime}$ is allowed to depend on $\varepsilon$ as in the
conclusion of Lemma 9.15) if and only if $M_{0}/p$ has a structured almost
normal vector (of the same parameters).

We note that this result is similar to [NW22, Lemma 7.7], where almost normal
vectors were replaced by normal vectors. A proof of this result is included in
Appendix C for convenience.

We now complete our main result of the section.

###### Proof of Proposition 9.2 for the Laplacian model (and hence also for
the symmetric model).

Here we assume $N\geq cn$. Let $W_{N}$ be the submodule in ${\mathbb{Z}}$
generated by the columns of $G_{N}$. We let $\mathcal{S}^{\prime}$ be the set
of submodules $H_{N}$ of ${\mathbb{Z}}^{N}$ such that for all primes
$p>e^{n^{c}}$, the vector space $H_{N}/p$ has no structured almost normal
vector ${\mathbf{w}}$. First, we will bound
${\mathbf{P}}(W_{N}\not\in\mathcal{S}^{\prime})$. By Lemma 9.18, for $p\geq
e^{n^{c}}$, if $W_{N}/p$ has a structured almost normal vector, then $W_{N}$
has a structured almost normal vector, and then $W_{N}/p^{\prime}$ has a
structured almost normal vector for every prime $p^{\prime}$ with
$e^{n^{c/2}}\leq p^{\prime}<e^{n^{c}}$. So it suffices to bound the condition
that $W_{N}/p$ has a structured almost normal vector for $p$ is a prime
$e^{n^{c/2}}\leq p<e^{n^{c}}.$

We will include in our upper bound the probability that $W_{N}/p$ has a non-
zero almost normal vector ${\mathbf{w}}$ with
$|\operatorname{supp}({\mathbf{w}})|\leq cN$ for some prime $p<e^{n^{c}}$,
which is at most $e^{-\Theta(n)}$ by Lemmas 5.4. Then, otherwise, by
Proposition 9.16, it is of probability at most $n^{-\Theta(n)}$ that, for some
prime $e^{n^{c/2}}\leq p\leq e^{n^{c}}$, the space $W_{N}/p$ has a non-sparse
structured almost normal vector ${\mathbf{w}}$. We conclude that,
unconditional on all overwhelming events such as
${\mathcal{E}}_{mixing},{\mathcal{E}}_{non-sing},{\mathcal{E}}_{partial-full}$
we have

${\mathbf{P}}(W_{N}\in\mathcal{S}^{\prime})\geq 1-e^{-\Theta(n^{c})}.$

Let $H_{N}\in\mathcal{S}^{\prime}$, then $H_{N}/p$ has no structured almost
normal vectors for any $p\geq e^{n^{c}}$. Then by Lemma 9.15 we must have

${\mathbf{P}}({\operatorname{rank}}(G_{N+1}/p)=\min\\{{\operatorname{rank}}(G_{N}/p)+2,N+1\\})\geq
1-n^{-C},$

completing the proof. ∎

###  9.5. Outline for the skew-symmetric model

As this case is fairly simple compared to the symmetric and especially the
Laplacian case, we just sketch the proof. Our initial setting is similar to
the case of symmetric and Laplacian matrices, where we rely on Corollary 7.18
for $A_{2n}$ and the following analog of Proposition 9.2.

######  Proposition 9.19.

There is an event ${\mathcal{E}}_{alt}$ in characteristic zero with
probability $1-e^{-O(n^{c})}$ such that under this event, for any primes
$p\geq e^{n^{c}}$ in the watch list ${\mathfrak{W}}_{2N}$, and for all $cn\leq
2N\leq 2n-2$ we have

${\operatorname{rank}}(A_{2N+1}/p)={\operatorname{rank}}(A_{2N}/p)+2$

and

${\operatorname{rank}}(A_{2N+2}/p)={\operatorname{rank}}(A_{2N+1}/p)+2.$

Using this we can conclude Proposition 2.7 as follows.

###### Proof of Proposition 2.7.

We will condition on the event ${\mathcal{E}}_{alt}$ from Proposition 9.19. We
first show that

${\operatorname{rank}}(A_{2n}/p)\geq 2n-2,\forall p\geq e^{n^{c}}.$

Indeed, if ${\operatorname{rank}}(A_{2n}/p)\leq 2n-4$, then
$p\in{\mathfrak{W}}_{2n-2}$. Let $N_{\min}\leq n-1$ be a smallest index where
for all $N\in[N_{\min},n-1]$ we have $p\in{\mathfrak{W}}_{2N}$. Because of
Proposition 9.19, we certainly have $n/2\leq N_{\min}$. Now if $N_{\min}<n-1$,
then we have learned that $p\notin{\mathfrak{W}}_{2N_{\min}-1}$, and hence
$A_{2N_{\min}-1}/p$ has full rank but $A_{2N_{\min}}/p$ has rank
$2N_{\min}-2$. In this case, by Proposition 9.19 $A_{2N_{\min}+2}$ has rank
$2N_{\min}+2$, so $p\notin{\mathfrak{W}}_{2(N_{\min}+1)}$, a contradiction. So
we must have $N_{\min}=n-1$. This implies that $A_{2(n-2)}/p$ has full rank
and $A_{2(n-1)}/p$ has rank $2n-4$. Another application of Proposition 9.19
then yields that $A_{2n}/p$ has rank $2n-2$, another contradiction.

Now we show that

${\operatorname{rank}}(A_{2n+1}/p)\geq 2n,\forall p\geq e^{n^{c}}.$

If $A_{2n}/p$ has rank $2n$ then there is nothing to prove. If $A_{2n}/p$ has
rank $2n-2$, then $p\in{\mathfrak{W}}_{2n}$, and hence by Proposition 9.19 we
have $A_{2n+1}/p$ has rank $2n$. ∎

In what follows we sketch the idea to prove Proposition 9.19. Our method
follows the arguments from the previous section (especially for the symmetric
matrices case) without the need of Subsection 9.3. Indeed, assume that

${\mathbf{P}}\Big{(}{\operatorname{rank}}(A_{N+1}/p)=\min\big{\\{}{\operatorname{rank}}(A_{N}/p)+2,N+(N\
\operatorname{mod}\ 2)\big{\\}}\Big{)}\leq 1-n^{-C},$

where $C$ is chosen sufficiently large (so after taking union bound over
$O(n^{2})$ primes from the watch lists we still have the above event with
overwhelming probability.) Then by Lemma 7.7 (applied to the skew-symmetric
matrix case) and by Theorem 8.2 there is an almost normal vector of $A_{N}$
(the vectors of $a_{ij}$ from (7.6)) which is fully structured. (We remark
that here there is no need to use Theorem 8.14 as in the Laplacian case
because it suffices to consider $X_{N+1}\notin W_{N}$ (where
$X_{N+1}\in{\mathbb{F}}_{p}^{N}$ is the last column of $A_{N+1}/p$ without the
last entry, and for this Theorem 8.2 suffices). Finally we then use the
methods from Subsection 9.4 to show that these events over different $p$ can
be simultaneously treated by working only on one $p$ in the range
$e^{n^{c/2}}\leq p\leq e^{n^{c}}$, and to this end we use Proposition 9.16.

##  10\. Further remarks and directions

Our treatment for Laplacian graphs can be extended to random Erdős-Rényi
graphs of other parameters.

######  Theorem 10.1.

Let $q>0$ be fixed. The results of Theorem 1.1 and Theorem 1.22 also hold for
the Laplacian of $G(n,q)$.

We sketch the main ideas below, omitting the details.

  * •

First, the neighbor reshuffling process remains the same where we reshuffle
the pairs of edge and non-edge in Definition 1.23 by a fair coin flip (hence
the randomness created by reshuffling are i.i.d. Bernoulli taking values $0,1$
with probability 1/2). Here by Chernoff we just need to modify (1.25) to
${\mathbf{P}}(\wedge_{i=1}^{n+1}qn-t\sqrt{n}\leq d_{i}\leq qn+t\sqrt{n})\geq
1-n\exp(-\Theta_{q}(t^{2}))$ and (1.27) to ${\mathbf{P}}\big{(}\wedge_{k\geq
cn}|I_{k}|\in(2q(1-q)k-t\sqrt{n},2q(1-q)k+t\sqrt{n}\big{)}\geq
1-n\exp(-\Theta_{q}(t^{2}))$. We also need to modify (9.3) and (9.7)
accordingly.

  * •

Next, for our treatment of small primes, by [Woo17, Theorem 1.1], Theorem 1.20
extends to the Laplacian model of $G(n,q)$.

  * •

For moderate primes, to establish Proposition 2.1 we will need Theorem 7.17.
For this, the main results of Sections 5 and 6, Lemma 5.5, Proposition 5.19,
Lemma 6.5, and Proposition 6.29 are all valid in the more general setting of
$G(n,q)$ with the modified reshuffling process. Here we note that Theorem 5.11
and Theorem 6.15 work under fairly general assumption of randomness (such as
(1.2)).

  * •

Lastly, for large primes, to establish Proposition 2.5 we use the “watch list”
method of Section 9. Here, again we rely on the inverse results of Theorem 8.2
and 8.14 of Section 8, as well as Lemma 9.9 by passing to the matrix model of
Definition 1.28.

It is an interesting problem to extend our results to random sparse graphs and
matrices. This is not impossible, especially when $q\geq n^{-1+\varepsilon}$,
but the proofs are expected to be extremely technical. It is also interesting
to generalize our results to Laplacian of general random matrices. (In this
paper we relied on the neighbor reshuffling process, which is rather specific
to $\\{0,1\\}$ matrices.) Furthermore, it would be interesting to extend our
results to adjacency matrices of random graphs of given degrees $d_{i}$ (say
all of order $n$, for instance the model ${\mathcal{G}}_{\mathbf{d}}$ from
Def. 1.28). Some of our results, such as Corollary 9.11, are applicable to
this setting, but other ingredients such as Theorem 1.20 666Heuristically one
can hope to use the method of [M2́0] for this, but the implementation seems
highly non-trivial. and Theorem 7.17 are largely missing.

Finally, there are other interesting global statistics that we do not access
in this paper, such as the probability that the group has square-free order
(or cube-free order in the even dimensional skew-symmetric case), it would be
interesting to address these issues.

## Acknowledgements

The first author is partially supported by NSF CAREER grant DMS-1752345. The
second author is partially supported by a Packard Fellowship for Science and
Engineering, NSF CAREER grant DMS-2052036, and NSF Waterman award DMS-2140043.

##  Appendix A Proof of Theorem 8.14

Let $f(X)=\sum_{1\leq i\leq j\leq N}b_{ij}x_{i}x_{j}$. We write

$\displaystyle|{\mathbf{P}}(f(X)=a)-\frac{1}{p}|$
$\displaystyle=\frac{1}{p}|\sum_{t\neq
0,\in{\mathbb{F}}_{p}}{\mathbf{E}}e_{p}(f(X)t)e_{p}(-at)|\leq\frac{1}{p}\sum_{t\neq
0,\in{\mathbb{F}}_{p}}|{\mathbf{E}}e_{p}(f(X)t)|.$

For now we let $U\subset[N]$ and let $U^{c}=[N]\backslash U$. This set $U$
will be randomized at the end, but now it is deterministic. By using Cauchy
Schwarz as in the proof of Lemma 7.4

$\displaystyle(\frac{1}{p}\sum_{t\neq
0,\in{\mathbb{F}}_{p}}|{\mathbf{E}}e_{p}(f(X)t)|)^{4}$
$\displaystyle\leq\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p},t\neq
0}|{\mathbf{E}}e_{p}(f(X)t)|^{4}\leq\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p},t\neq
0}|{\mathbf{E}}_{X_{U}}{\mathbf{E}}_{X_{U^{c}},X_{U^{c}}^{\prime}}e_{p}((f(X_{U},X_{U^{c}})-f(X_{U},X_{U^{c}}^{\prime}))t)|^{2}$
$\displaystyle=\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p},t\neq
0}{\mathbf{E}}_{X_{U^{c}},X_{U^{c}}^{\prime}}{\mathbf{E}}_{X_{U},X_{U}^{\prime}}e_{p}((f(X_{U},X_{U^{c}})-f(X_{U},X_{U^{c}}^{\prime})-f(X_{U}^{\prime},X_{U^{c}})+f(X_{U}^{\prime},X_{U^{c}}^{\prime}))t)$
$\displaystyle=\frac{1}{p}\sum_{t\in{\mathbb{F}}_{p},t\neq
0}{\mathbf{E}}_{Y}e_{p}(\sum_{i\in U,j\in
U^{c}}b_{ij}y_{i}y_{j}t)={\mathbf{P}}(Y_{U}BY_{U^{c}}=0)-\frac{1}{p}={\mathbf{P}}(Y_{1}B_{U}Y_{2}=0)-\frac{1}{p},$

where $B_{U}$ is the matrix $B_{U}(ij)=b_{ij}$ iff $i\in U,j\in U^{c}$ and
$B_{U}(ij)=0$ otherwise, and $Y_{1},Y_{2}$ are independent with entries as
i.i.d. copies of $\xi-\xi^{\prime}$.

If ${\mathbf{P}}(f(X)=a)\geq n^{-C}$ and if $p\geq n^{A}$ with sufficiently
large $A$ (given $C$) then $|{\mathbf{P}}(f(X)=a)-1/p|\geq N^{-C}/2$, and
hence ${\mathbf{P}}(Y_{1}B_{U}Y_{2}=0)\geq n^{-4C}/16+1/p\geq N^{-4C}/16$. We
can then apply Lemma 8.3 to this bilinear form to obtain

######  Corollary A.1.

There exist a set $I_{0}(U)$ of size $O_{C,\varepsilon}(1)$ and a set $I(U)$
of size at least $n-n^{\varepsilon}$ such that for any $i\in I$, there are
integers $0\neq k(U)$ and $k_{ii_{0}}(U),i_{0}\in I_{0}(U)$, all bounded by
$n^{O_{C,\varepsilon}(1)}$, such that

${\mathbf{P}}_{Y}\big{(}\langle
k(U){\mathbf{r}}_{B_{U}}(i),Y\rangle+\langle\sum_{i_{0}\in
I_{0}}k_{ii_{0}}(U){\mathbf{r}}_{B_{U}}(i_{0}),Y\rangle=0\big{)}=N^{-O_{C,\varepsilon}(1)},$

where $Y=(y_{1},\dots,y_{N})$ and $y_{i}$ are i.i.d. copies of
$\xi-\xi^{\prime}$.

Note that Corollary A.1 holds for all $U$. In what follows we gather the
information together to obtain structures for the entire matrix $B$ (rather
than for $B_{U}$).

As $I_{0}(U)\subset[N]^{O_{C,\varepsilon}(1)}$ and $k(U)\leq n$, there are
only $N^{O_{C,\varepsilon}(1)}$ possibilities that $(I_{0}(U),k(U))$ can take.
Thus there exists a tuple $(I_{0},k)$ such that $I_{0}(U)=I_{0}$ and $k(U)=k$
for $2^{N}/N^{O_{C,\varepsilon}(1)}$ different $U$. Let us denote this set of
$U$ by $\mathcal{U}$. Thus

$|\mathcal{U}|\geq 2^{N}/N^{O_{C,\varepsilon}(1)}.$

Next, let $I$ be the collection of $i$ which belong to at least
$|\mathcal{U}|/2$ index sets $I_{U}$. Then we have