Proof. A symmetric matrix of rank \(r\) has a nonsingular principal submatrix of size \(r\). Indeed, write it as \(XSX^{\mathsf T}\), where \(X\) has \(r\) independent columns and \(S\) is nonsingular, and choose \(r\) independent rows of \(X\). The principal submatrix on those rows is a product of three nonsingular square matrices. For a fixed candidate principal submatrix, reveal it and its cross block. If the full matrix has the same rank, the Schur complement forces all entries in the remaining principal block. Each forced entry has conditional probability at most \(b\). Consequently, with \(t=\lceil n^{3/5}\rceil\), \[\mathbb P(n-\mathop{\mathrm{rank}}A\ge t) \le \sum_{k=t}^n\binom nk b^{k(k+1)/2} \le 2^{-\Omega_p(n^{6/5})}.\]

Now let \(K=\ker A\) have dimension \(1\le k<t\). Choose a set \(I\) of \(k-1\) coordinates whose restrictions to \(K\) are independent linear functionals, and flip the diagonal signs on \(I\). Write \(D\) for the diagonal matrix of these changes. If \((A+D)y=0\), then \[x^{\mathsf T}Dy=0\qquad(x\in K).\] The map \(x\mapsto x_I\) maps \(K\) onto \(\mathbb R^I\), and each entry of \(D\) on \(I\) is nonzero. Hence \(y_I=0\), and then \(Ay=0\). Conversely, every vector in \(K\) vanishing on \(I\) is in \(\ker(A+D)\). The new kernel is exactly that one-dimensional subspace.

Fix a choice of \(I\) for each such matrix. The probability of a matrix divided by that of its image is at most \((b/p)^t\). Each image has at most \[\sum_{j\le t}\binom nj=2^{O(n^{3/5}\log n)}\] preimages, since specifying the flipped coordinates recovers the original matrix. Both factors are \(2^{o(n)}\), proving the lemma. ◻

Proof. Put \(\mu=2p-1\) and \(W=A-\mu\mathbf1\mathbf1^{\mathsf T}\). For a sufficiently large fixed \(L\), \[ \mathbb P(\lVert W\rVert_{\mathrm{op}}>L\sqrt n)\le 2^{-4n}. \tag{4}\] To see this, for a fixed unit vector \(x\), write \(x^{\mathsf T}Wx\) as a sum over the independent upper-triangular entries. Its coefficients have squared sum \[\sum_i x_i^4+4\sum_{i<j}x_i^2x_j^2\le2.\] Hoeffding’s inequality [8] therefore gives a bound \(2\exp(-cL^2n)\) at a constant multiple of \(L\sqrt n\). A \(1/4\)-net of the unit sphere has at most \(9^n\) points, and the usual quadratic-form net inequality bounds the operator norm by twice the maximum over this net. Taking \(L\) large proves (4).

Fix an anchor \(a_0\) and a tail support \(T\), with \(j=|T|\le\lambda n\). If a tail is within \(\delta\) of a vector on \(T\), its truncation to \(T\) has error at most \(\delta\). Approximate this truncation by a \(\delta\)-net of the unit ball in \(\mathbb R^T\), and approximate the anchor coefficient on \([-\sqrt n,\sqrt n]\) with mesh at most \(\delta\). The resulting vector \(x\), supported on \(S=T\cup\{a_0\}\), satisfies \[\lVert v-x\rVert_2\le3\delta,\qquad \lVert x_T\rVert_2\ge1-2\delta,\qquad |x_{a_0}|\ge\max_{i\in T}|x_i|-2\delta.\] It suffices to retain net points with these last two properties. Also approximate \(\sum_i v_i\) by a number \(u\) with error at most \(\delta\). By (3), this sum lies in \([-2\sqrt n,2\sqrt n]\). For each \(T\), the number of pairs \((x,u)\) is at most \((C/\delta)^j\) times a polynomial in \(n\), with fixed parameters. The separate scalar approximation prevents the mean matrix from amplifying the error in the coordinate sum.

On the event \(\lVert W\rVert_{\mathrm{op}}\le L\sqrt n\), the equation \(Av=0\) implies that one of these pairs satisfies \[ \lVert Wx+\mu u\mathbf1\rVert_2 \le C_1L\delta\sqrt n. \tag{5}\] We next show that every fixed pair has small probability of satisfying this inequality. There are fixed \(w>0\) and \(\delta_0>0\), depending on \(p\), such that, whenever \(\delta<\delta_0\), each row outside \(S\) satisfies \[ \mathbb P\bigl(|(Wx)_i+\mu u|\le w\bigr)\le Q. \tag{6}\] All row shifts here may be arbitrary.

Choose a small fixed coefficient threshold \(u_0>0\). If some \(|x_j|\ge u_0\), \(j\in T\), then \(|x_{a_0}|\ge u_0/2\) when \(\delta\) is small enough. Condition on all signs in this row except those at \(j,a_0\). For \(w<u_0/4\), the interval of length \(2w\) cannot contain two outcomes that differ in only one of these two signs. The allowed vertices of the two-bit square thus consist of at most one vertex or two opposite vertices. Their total probability is at most \[\max\{b^2,p^2,2pb,p^2+b^2\}=Q.\] If instead every tail coefficient has absolute value below \(u_0\), condition on the anchor sign and use the tail alone. Its centered sum has variance \[\sigma_T^2=4pb\sum_{j\in T}x_j^2,\] bounded below by a positive constant depending on \(p\). The sum of its third absolute centered moments is at most \(C_pu_0\sum_{j\in T}x_j^2\). The Berry–Esseen inequality [2, 5], in its unequal-summand form [21], bounds the uniform distribution-function error by an absolute constant times the sum of these third moments divided by \(\sigma_T^3\). The error from the centered normal law with variance \(\sigma_T^2\) is therefore at most \(C_pu_0\). The probability of any interval of length \(2w\) is therefore at most \(C_p(w+u_0)\). Choose \(u_0\), then \(w\), small enough to make this quantity less than \(Q\), and finally decrease \(\delta_0\). This proves (6) in both cases.

For a fixed pair \((x,u)\), the rows outside \(S\) depend on disjoint sets of upper-triangular entries, so these tests are independent. Choose a small fixed \(\gamma>0\), and then \(\delta<\delta_0\) so that \(C_1^2L^2\delta^2/w^2<\gamma\). Inequality (5) allows at most \(\gamma n\) rows to fail the interval test. Thus its probability, for fixed data, is at most \[\left(\sum_{i\le\gamma n}\binom ni\right) Q^{\,n-j-1-\gamma n}.\] The norm event was used only to obtain (5); the independent tests in this bound are not conditioned on that event.

For \(t\in(0,1)\), let \(H_2(t)=-t\log_2t-(1-t)\log_2(1-t)\). Union over anchors, supports, and net points gives a base-two logarithm at most \[-d_*n+ \bigl[d_*(\lambda+\gamma)+H_2(\gamma)+H_2(\lambda) +\lambda\log_2(C/\delta)\bigr]n+o(n).\] Choose \(\gamma\) sufficiently small, then \(\delta\) as above, then \(\lambda\) sufficiently small, to make the bracket less than \(\epsilon/2\). Adding (4) and taking \(n\) large proves the lemma. ◻

Proof. Relabel the fixed index as the first coordinate, put \(\mu=2p-1\), \(t=A_{11}\) and \(u_i=A_{1i}\) for \(i>1\), and set \[D=\mathop{\mathrm{diag}}(1,tu_2,\ldots,tu_n).\] The matrix \(tDAD\) has first row and column equal to one. Its lower principal block is the sign matrix \(C_{ij}=tu_i u_j A_{ij}\), \(i,j>1\). Hence its Schur complement at the first entry is \[C-\mathbf1\mathbf1^{\mathsf T}=-2M,\qquad M_{ij}=\frac{1-tu_i u_j A_{ij}}2.\] After the anchor row is fixed, the remaining original signs are independent. The displayed formula proves (i) and gives \[\mathbb EM=\frac12\mathbf1\mathbf1^{\mathsf T} -\frac{\mu t}{2}uu^{\mathsf T}.\] This includes the diagonal, since \(u_i^2=1\), and proves (ii). Multiplication by \(t\), diagonal congruence, and taking the Schur complement of the nonzero first entry preserve nullity. More explicitly, \(Dv\) is a kernel vector of \(tDAD\), and its lower coordinates are in \(\ker M\). They differ from the original tail only by coordinate signs, which proves (iii). ◻

Proof. If at least \(\rho n\) rows fail, at least half fail in the same direction. Choose a set \(I\) of \(k=\lceil\rho n/3\rceil\) such rows, for all sufficiently large \(n\); it suffices to consider \(\rho<1\). The sum of their positive-entry counts is a sum of independent upper-triangular Bernoulli variables with coefficients one or two. Its mean is \(pkn\), and its coefficients have squared sum at most \(2kn\). The common-direction deviation is at least \(kwn\). Hoeffding’s inequality [8] bounds this probability by \(2\exp(-kw^2n)\). There are at most \(2^n\) sets \(I\) and two directions, giving the assertion. ◻

Proof of Theorem 1, assuming Proposition 5. Fix \(\epsilon>0\), and choose \(\lambda,\delta\) from Lemma 3. By Lemma 2, it suffices to bound the corank-one event; the matrices discarded in the corank reduction are already negligible. Discard also the event in Lemma 3.

Take any remaining normalized tail and choose a fixed \(c\in(0,\delta)\). There are at least \(\lambda n/2\) off-anchor coordinates with absolute value at least \(c/\sqrt n\). Otherwise truncation to these coordinates would have support at most \(\lambda n\) and discarded norm at most \(c\), contrary to the choice of the tail. For a fixed tolerance \(w_1>0\), Lemma 6 with \(\rho=\lambda/4\) shows, apart from probability \(\exp(-\Omega_{\lambda,w_1}(n^2))\), that some such coordinate has a row count within \(w_1n\) of \(pn\). Choose it as the deletion index.

Fix the anchor and deletion indices and condition on the anchor row. This does not condition on their having been chosen by a kernel vector; we will take a union bound over their indices. Apply Lemma 4, and denote the transformed unit tail by \(v\in\ker M\), where \(M\) has size \(N=n-1\) and corank one. Its deletion coordinate has \(|v_i|\ge c/\sqrt n\). The adjugate of a symmetric corank-one matrix is a nonzero scalar multiple of \(vv^{\mathsf T}\). Thus deleting coordinate \(i\) leaves a nonsingular principal minor \(B\) of size \(N-1\). Writing \[M=\begin{pmatrix}B&z\\z^{\mathsf T}&d\end{pmatrix}, \qquad d\in\{0,1\},\] the kernel equation and Schur complement give \[B^{-1}z=-\frac{v_{[N]\setminus\{i\}}}{v_i}, \qquad z^{\mathsf T}B^{-1}z=d.\] Consequently \(z\in\mathcal S_{L_0}(B)\) for a fixed \(L_0\ge\max(1,2/c)\).

It remains to bound the probability of these possible columns under the biased law. Conditional on the anchor row, \(B\) and the entries of \(z\) are independent. A specified \(z\) specifies the \(n-2=N-1\) original off-diagonal signs of the deleted column outside the anchor. If \(r\) of those signs are positive, its point probability is exactly \[p^r b^{N-1-r}.\] The full original row has only two additional entries, its diagonal and its anchor entry. Compatibility with the selected row-count condition therefore requires \(|r-pn|\le w_1n+2\). For every such \(z\), \[ p^r b^{N-1-r} \le 2^{-N(h_*-C_pw_1-o(1))}. \tag{9}\] Indeed its negative base-two logarithm is \[(N-1)h_*+ \bigl(r-p(N-1)\bigr)\log_2(b/p).\] The count here concerns positive original signs; the success probabilities of the transformed bits need not be equal. We have not charged the deleted diagonal: dropping its requirement only enlarges the event.

On the event that the nonsingular \(B\) satisfies the cardinality conclusion of Proposition 5, independence and (9) bound the conditional probability by \[2^{-N(h_*-e_0-C_pw_1-o(1))}.\] The exceptional nonsingular minors have conditional probability at most \(2^{-N(2a-10e_0)}\). Both bounds are uniform in the anchor row, so averaging over that row introduces no additional factor. The choices of anchor and deletion indices cost at most \(n^2\).

After \(L_0\) has been fixed, choose \(e_0,w_1>0\) sufficiently small that \[2a-10e_0>d_*, \qquad h_*-e_0-C_pw_1>d_*,\] using (2). Together with the discarded events and the subexponential corank reduction, this proves \[\limsup_{n\to\infty}\frac1n\log_2 \mathbb P(\det A_n^{(p)}=0)\le-d_*+\epsilon.\] Letting \(\epsilon\downarrow0\) gives the required upper bound.

For the lower bound, require the first two rows to be equal. The entries in their first two coordinates must satisfy \(A_{11}=A_{12}=A_{22}\), at cost \(p^3+b^3\). For each \(j\ge3\), the independent pair \((A_{1j},A_{2j})\) agrees with probability \(Q\). These requirements involve disjoint upper-triangular entries, and hence \[\mathbb P(\det A_n^{(p)}=0)\ge(p^3+b^3)Q^{n-2}.\] This gives the matching lower bound. Negation handles \(p>1/2\). ◻

Proof. For a fixed prime, Equation (10) with \(k=\lfloor N^{3/5}\rfloor+1\) gives the asserted probability bound. If \(B\) is nonsingular over \(\mathbb R\), every prime with positive corank divides the nonzero integer \(\det B\). Hadamard’s inequality gives \[1\le |\det B|\le m^{m/2}\le N^{N/2}.\] A union bound over all primes at most \(N^{N/2}\) therefore costs at most \(2^{O(N\log N)}\), which is negligible compared with \(2^{-\Omega_p(N^{6/5})}\). Finally, \[\dim_{\mathbb F_q}(G_B/qG_B) =\operatorname{corank}_{\mathbb F_q}(B\bmod q).\] The structure theorem for finite abelian groups identifies the minimum number of generators with the maximum of these dimensions. ◻

Proof. The zero sublattice gives value one. For each positive rank \(r\), the wedge of a basis belongs to the discrete lattice \(\bigwedge^r L\), so there are only finitely many such wedge vectors of norm at most \(T^r\). Thus the normalized determinants no greater than one have only finitely many possible values, and the minimum is attained. Saturation preserves rank and can only lower the determinant. Comparing with the zero sublattice gives the first bound. For a sublattice \(M\) of the quotient, its full preimage \(\widetilde M\subseteq L\) has \[\det\widetilde M=\det L_{\min}\det M, \qquad \mathop{\mathrm{rank}}\widetilde M=\mathop{\mathrm{rank}}L_{\min}+\mathop{\mathrm{rank}}M.\] Minimality applied to \(\widetilde M\) gives the second bound. ◻

Proof. For \(s>0\), write \(\rho_s(\Lambda)=\sum_{x\in\Lambda} \exp(-\pi\lVert x\rVert_2^2/s^2)\). The Reverse Minkowski Theorem of Regev and Stephens-Davidowitz [18], in the scaled form of [17], gives \(\rho_{s_0}(\Lambda)\le3/2\) under precisely the stated sublattice hypotheses. Every vector of norm at most \(R\) contributes at least \(\exp(-\pi R^2/s_0^2)\), yielding the displayed count; this is [17]. Finally, \(s_0\ge c(\log N)^3\) for \(1\le j\le N\), which gives the claimed exponent. ◻

Proof. Choose a maximal such set of indices, say \(i_1,\ldots,i_j\). Adding an unselected index creates a pair of subset sums at distance at most \(R_0\sqrt N\) modulo \(S\Lambda\). The added index occurs in exactly one of them, since the old subset sums were separated. Undoing \(S\), we obtain, for every \(i\in[m]\), \[ u\pi_Ee_i\equiv \sum_{h=1}^j a_{hi}u\pi_Ee_{i_h}+\varepsilon_i \pmod\Lambda, \qquad a_{hi}\in\{-1,0,1\}, \qquad\lVert S\varepsilon_i\rVert_2\le R_0\sqrt N, \tag{20}\] where \(\varepsilon_i\in\Pi\). For the selected indices use the exact representations, with coefficient columns the standard basis and zero errors.

Let \(t\) be the dimension spanned by the errors, and choose \(t\) independent ones. By Equation (18), their volume is at least \(1/H(F)\). On every \(t\)-dimensional subspace, \(S\) expands volume by at least \(N^{2t-(C+7)r}\): at most \(r\) singular directions have the smaller scale in Equation (16). Hadamard’s inequality for the scaled errors gives \[H(F)^{-1}N^{2t-(C+7)r}\le(R_0\sqrt N)^t.\] Using Equation (12), we conclude that \[ t=O_C\left(r+\frac{N\ell}{\log N}\right)=o(\tau N). \tag{21}\]

Define a real linear map \(M:\mathbb R^m\to\mathbb R^j\oplus E\) whose \(i\)th column is \((a_{1i},\ldots,a_{ji},\varepsilon_i)\). Its integer image \(M\mathbb Z^m\) is a sublattice of \(\mathbb Z^j\oplus\Pi\), of rank \(s\le j+t\). Evaluation of a representation defines the homomorphism \[\Psi:\mathbb Z^j\oplus\Pi\longrightarrow\Pi/\Lambda, \qquad \Psi(a,v)=\sum_{h=1}^j a_hu\pi_Ee_{i_h}+v\pmod\Lambda.\] By Equation (20), \(\Psi(M\mathbb Z^m)=u(\Pi/\Lambda)\). Every column of \(MB\) lies in \(\ker\Psi\), because its evaluation is \(u\pi_EBe_i\in\Lambda\). Moreover, \(B\) is nonsingular, so \(\mathop{\mathrm{rank}}(MB)=s\). Choose \(s\) independent columns of \(MB\), and let \(L'\) be their integer span. Then \[|u(\Pi/\Lambda)|\le[M\mathbb Z^m:L'] =\frac{\det L'}{\det(M\mathbb Z^m)}.\] Each error has ordinary norm at most \(R_0N^{C+5}\sqrt N\). Since the entries of \(B\) are bounded by one, the chosen columns have norm at most \(N^{C+9}\) for large \(N\). Equation (18) and Hadamard’s inequality therefore imply \[N^{\tau N-o(\tau N)} \le H(F)N^{(C+9)s} \le H(F)N^{(C+9)(j+t)}.\] Together with Equation (21), this yields \(j\ge c_1\tau N\), for example with \(c_1=1/[2(C+9)]\) and sufficiently large \(N\). ◻

Proof. Let \(X=\xi-\xi'\) where \(\xi,\xi'\) are independent vectors of Bernoulli \(p\) bits on \(J\), extended by zero outside \(J\). Expanding the product in Equation (24) expresses its expectation as \[\mathbb E_X\left[e^{2\pi i\sum_{i\in J}s_iX_i} \mathbb E_y e^{2\pi i u\langle y,X\rangle}\right].\] Poisson summation in \(E\) gives \[ \mathbb E_y e^{2\pi i u\langle y,X\rangle}=f(uX),\qquad f(uX)= \frac{\sum_{\lambda\in\Lambda} e^{-\pi\lVert S(\lambda-u\pi_EX)\rVert_2^2}} {\sum_{\lambda\in\Lambda}e^{-\pi\lVert S\lambda\rVert_2^2}}. \tag{25}\] The ratio is nonnegative and at most one. Positivity follows from the displayed formula; the upper bound follows either from its characteristic-function interpretation or from the Gaussian translate inequality. Thus taking absolute values permits us to discard the phases involving \(s_i\) and bound the original expectation by \(\mathbb E_X f(uX)\).

We record explicitly the Gaussian estimates used here. For every lattice \(L\) of rank \(d\) and every \(z\) in its span, Poisson summation and positivity of the Fourier transform of a Gaussian imply \[\sum_{v\in L}e^{-\pi\lVert v-z\rVert_2^2/2} \le\sum_{v\in L}e^{-\pi\lVert v\rVert_2^2/2}, \qquad \frac{\sum_{v\in L}e^{-\pi\lVert v\rVert_2^2/2}} {\sum_{v\in L}e^{-\pi\lVert v\rVert_2^2}} \le 2^{d/2}.\] For the second inequality, Poisson summation expresses the ratio as \(2^{d/2}\) times a ratio of dual Gaussian masses at decreasing scales. These estimates hold for arbitrary lattices, with no additional regularity assumption. For these lattice Gaussian comparisons, see Banaszczyk [1] and [18].

Apply them to \(L=S\Lambda\). If \(\operatorname{dist}(uS\pi_EX,S\Lambda)\ge R_0\sqrt N/3\), retaining half of each Gaussian exponent in the numerator of Equation (25) gives \[ f(uX)\le e^{-\pi R_0^2N/18}2^{\dim E/2} \le e^{-c_4N} \tag{26}\] for an absolute \(c_4>0\).

To bound the complementary event, condition on \(\xi'\) and on all coordinates of \(\xi\) except those in \(J\cap I_u\). By Lemma 12, at most one of the remaining subset sums lies within distance \(R_0\sqrt N/3\) of the prescribed translate of \(S\Lambda\). Otherwise the distance between two such sums would be at most \(2R_0\sqrt N/3\). The probability of any one bit pattern is at most \(b^{|J\cap I_u|}\le b^{c_2\tau N}\). Combining this bound with Equation (26) proves the result, after decreasing \(c_3\). ◻

Proof. Write \(f=f_l\) and \(U=U_l\). Multiply the perfect pairing on \(U\) by \(l^f\), and quotient \(U\) by the radical of this new pairing. The resulting pairing on a group \(\bar U\) is perfect. Its order is \[|\bar U|=l^{\sum_i(b_{l,i}-f)_+}.\] Indeed, under the original perfect pairing the new radical is \(U[l^f]=\{u\in U:l^fu=0\}\), and each cyclic factor of exponent \(b>f\) leaves a quotient of order \(l^{b-f}\). By Equation (41), the images of one color generate a subgroup \(A\subset\bar U\) with \(A\subset A^\perp\). Perfectness gives \(|A|\,|A^\perp|=|\bar U|\), so \[[\bar U:A]\ge|\bar U|^{1/2} =l^{\frac12\sum_i(b_{l,i}-f)_+} \ge l^{b_{l,2}-f}.\] Take the preimage of \(A\) in \(U\), and add the unrestricted summand \(V_l\). This subgroup contains the entire primary color and has the required index. The argument also covers \(U=0\), when the asserted index is one. ◻

Proof. The group-order bound gives \(b_{l,1}\le(N/2)\log_2N\), so the first bound in Equation (40) costs \(O(\log N)\) bits per prime. All primes \(l\le\sqrt N\) together therefore cost \(O(\sqrt N\log N)=o(N)\). For larger primes, \(\nu_l>1/(2N)\); they are odd for large \(N\), and hence \[ \sum_{l\in\mathcal P,\ l>\sqrt N}\log_2 C_l \le\sum_{l\in\mathcal P,\ l>\sqrt N}(b_{l,2}-b_{l,3}) \le2N\sum_{l\in\mathcal P,\ l>\sqrt N} (b_{l,2}-b_{l,3})\nu_l. \tag{43}\] For (i), first include every contributing prime at most \(\sqrt N\). If their total weight is below \(\sigma\), add larger contributing primes until that threshold is first reached. Before the last prime, Equation (43) costs at most \(2\sigma N\) bits. Charge the last prime only \(O(\log N)\) bits using the first color bound, regardless of its weight. The total is \(o(N)\), since \(\sigma\to0\). For (ii), Equation (43) applies to all large primes with total cost at most \(2\sigma N\); the small-prime cost is unchanged. ◻

Proof. The matrix of \(q\) in a lattice basis is rational. Its radical therefore has a rational basis, so \(K\) spans the radical and is primitive in \(L\). The orthogonal projection \(\bar L\) of \(L\) onto \(S\) is a lattice, and \(\det L=\det K\det\bar L\). The form descends to \(\bar L\) with the same pairing image order, because pullback of characters along \(L\to\bar L\) is injective.

Let \(M\) be the nonsingular matrix of the descended form in a basis of \(\bar L\). Its pairing kernel modulo \(\mathbb Z\) in the coordinate lattice has index \(t\). If \(A\) is an integer basis matrix for that kernel, then \(|\det A|=t\) and \(A^{\mathsf T}M\) is integral and nonsingular. Thus \[1\le|\det(A^{\mathsf T}M)|=t|\det M|.\] Changing from the lattice basis to an orthonormal basis divides this determinant by \((\det\bar L)^2\), which proves Equation (45). If \(S\) has dimension zero, then \(K=L\) and \(t=1\), so both sides of Equation (45) are one. ◻

Proof. The assertion is immediate if \(\mathcal S_{L_0}(B)\) is empty. Choose a largest overall color \(\mathcal A\) of the column set, and apply Lemma 18 with \(\rho=\ell^{-2}\). For the resulting set \(\mathcal V\), Lemma 17(ii) gives \[ \log_2|\mathcal S_{L_0}(B)| \le\log_2|\mathcal V|+o(N). \tag{46}\] Put \(F_0=\mathop{\mathrm{span}}(\mathcal V-\mathcal V)\) and \(r_0=\dim F_0\). We place each column beside its inverse image: the norm condition keeps differences short, while the first coordinates remain integral. The induced graph metric will also control the inverse form near small eigenvalues of \(B\). Define the rational graph map and its difference lattice \[\gamma(x)=(x,B^{-1}x),\qquad L=\langle\gamma(v)-\gamma(v'):v,v'\in\mathcal V\rangle_{\mathbb Z} \subset\gamma(F_0).\] The graph differences satisfy \[\lVert\gamma(v)-\gamma(v')\rVert_2^2 \le m+4L_0^2N\le(1+4L_0^2)N.\] Lemma 19, applied both to the graph map and to the identity map, consequently gives \[ \det L\le\exp(O_{L_0}(N\ell)), \qquad H(F_0)\le\exp(O(N\ell))\le\exp(N\ell^2) \tag{47}\] for sufficiently large \(N\).

On the full graph \(\Gamma=\gamma(\mathbb R^m)\), define the rational symmetric form \[q(\gamma(x),\gamma(y))=x^{\mathsf T}B^{-1}y.\] Its restriction to \(\gamma(F_0)\) has rank \(s\) satisfying \[ s\ge r_0-\xi N \tag{48}\] by the first hypothesis and Equation (47). The hypothesis covers every subspace of this height, including \(F_0\), which was selected from admissible columns for \(B\).

The map \(L\to G_B\) taking \(\gamma(u)\) to \(u+B\mathbb Z^m\) has image \[H=\langle\bar v-\bar v':v,v'\in\mathcal V\rangle.\] It is surjective onto \(H\), and the form modulo \(\mathbb Z\) is the pullback of the restricted pairing on \(H\). Pullback of characters is injective, so the two pairing maps have equal image orders. Lemma 15 bounds this order by \(N^{NJ_B}\). Let \(K\) be the radical lattice of the restriction to \(\gamma(F_0)\), and let \(S\) be its radical’s orthogonal complement in that space. The first-coordinate projection is injective on \(\Gamma\) and takes \(K\) to an integer lattice of the same rank. Such a lattice has covolume at least one, and orthogonal projection contracts volumes. Hence \(\det K\ge1\). Lemma 20 now yields \[ |\det_{\mathrm{orth}}(q|_S)| \ge N^{-NJ_B}\exp(-O_{L_0}(N\ell)). \tag{49}\]

The same determinant admits an upper bound from the spectrum of \(B\). If \(v\) is a unit eigenvector with nonzero eigenvalue \(x\), its graph vector has squared norm \(1+x^{-2}\), while \(q(\gamma(v),\gamma(v))=x^{-1}\). Orthogonal eigenvectors of \(B\) have orthogonal graph vectors. Thus the eigenvalues of the self-adjoint operator representing \(q\) on \(\Gamma\) are \[\frac{x}{1+x^2}.\] They have absolute value at most one. By the second hypothesis, all but at most \(\xi N\) of them have absolute value at most \(C_w/\sqrt N\), where \(C_w=1/w\).

The absolute determinant of the compression of a self-adjoint operator to any \(s\)-dimensional subspace is at most the product of its largest \(s\) singular values. Indeed, it is \(\langle\omega,(\bigwedge^s T)\omega\rangle\), where \(\omega\) is the unit exterior product of an orthonormal basis of the subspace. Applying this to \(S\), whose dimension is \(s\), gives \[ |\det_{\mathrm{orth}}(q|_S)| \le\left(\frac{C_w}{\sqrt N}\right)^{(s-\xi N)_+}. \tag{50}\] This argument applies to indefinite forms and includes \(s=0\). Combining Equations (49) and (50), and then using Equation (48), gives \[(s-\xi N)_+ \left(\frac12\log N-\log C_w\right) \le NJ_B\log N+O_{L_0}(N\ell), \qquad \frac{r_0}{N}\le2J_B+2\xi+o(1).\] The second bound also holds when \(s<\xi N\).

Finally, projection to \(r_0\) suitable coordinates is injective on the affine span of \(\mathcal V\), so \(|\mathcal V|\le2^{r_0}\). Equation (46) and the preceding dimension bound imply \[\frac1N\log_2|\mathcal S_{L_0}(B)| \le 2J_B+2\xi+o(1).\] The error is bounded by \(O_{L_0,w}(\ell^{-2}+\sigma+N^{-1/2}\log N+\ell/\log N)\). The first three terms come from extraction and colors, and the last from the determinant comparison, using \(J_B\le1/2\). This establishes the asserted uniformity. ◻

Proof. The cofactor identity gives the first alternative if some diagonal entry of \(B^{-1}\) is nonzero. Otherwise choose distinct \(i,j\) maximizing the absolute value of an entry of \(B^{-1}\), and write \(\kappa=(B^{-1})_{ij}\ne0\). The corresponding principal block is \(\left(\begin{smallmatrix}0&\kappa\\\kappa&0\end{smallmatrix}\right)\). Jacobi’s complementary minor identity makes the complementary matrix \(C\) nonsingular. In the block notation of Equation (53), its Schur complement \(T=D-V^{\mathsf T}C^{-1}V\) satisfies \[T^{-1}=\begin{pmatrix}0&\kappa\\\kappa&0\end{pmatrix}, \qquad (B^{-1})_{I,\{i,j\}}=-C^{-1}VT^{-1},\] where \(I\) is the set of remaining indices. The diagonal of \(T\) vanishes, giving the two quadratic identities. The two columns of the inverse block on the right are \(-\kappa C^{-1}v_2\) and \(-\kappa C^{-1}v_1\). Their entries have absolute value at most \(|\kappa|\), proving the norm bound. Finally \(\lVert C^{-1}v_i\rVert_2\le\sqrt{\operatorname{size}(C)} \le\sqrt N\le L_0\sqrt N\). ◻

Source and interpretation. Part (i) is the Retention lattice lemma [17], including arbitrary, nonconsecutive sets of layers. Part (ii) is the Tail recursion lemma [17] together with common-quotient interlacing [17]. For the latter, projection onto the old coordinates identifies \(G_h\) with the quotient of \(G_B\) by the \(h\) new coordinate classes. Since a one-element quotient lowers each height by at most one, \(k_B\le k_{G_h}+h\le k_C+h\). The stronger recursion uses symmetry through the Symmetric kernel inequality [17]; it needs no assumption on the entry distribution. All of these statements therefore apply to the present biased model. ◻

Proof. Impose Theorem 11 on \(C\) with \(\tau=\ell^{-20}\) and some fixed \(0<\alpha<e_0\). Then \(\tau=o(\sigma)\). We show that the retention condition can be covered by \(2^{o(N)}\) selected layer sets, each giving a lattice of index at least \(N^{\sigma N}\).

Let \(G\) be the group before one column is tested. It is a quotient of \(G_C\), so its total height times weight is at most \(1/2\). At a prime \(l\), let \(d_l\) be its number of plateaus. Distinct positive plateau heights give \(d_l^2\le2\sum_j k_G(l,j)\), and the group-order bound gives \(\sum_{l,j}k_G(l,j)=O(N\log N)\). Consequently the number of plateaus at primes \(l\le\sqrt N\) is \(O(N^{3/4}\sqrt{\log N})\), by Cauchy–Schwarz. Each prefix length has \(O(N\log N)\) possible values. Thus the complete retention pattern at these primes can be specified with \[ O\bigl(N^{3/4}(\log N)^{3/2}\bigr)=o(N) \tag{60}\] bits. Include all those retained layers in the selected set.

If their total weight is below \(\sigma\), add retained layers at primes \(l>\sqrt N\) until the total first reaches \(\sigma\). There are at most \(N\) candidate layers in this prime range, since each has \(\nu_l>1/(2N)\). At most \(\lceil2\sigma N\rceil+1\) additions suffice. The binomial bound therefore contributes \(2^{o(N)}\) further possibilities. This constructs the claimed cover whenever the retained weight is at least \(\sigma\).

For every selected set \(\mathcal D\), positive heights and Equation (56) give \(q(\mathcal D)\ge\sigma\). The simultaneous cube estimate applies to \(K_{\mathcal D}\), since it contains \(C\mathbb Z^m\), even when \(G\) depends on an earlier column. Each cube point has probability at most \(b^m\), where \(m=N-o(N)\). The one-column probability is therefore at most \[2^{o(N)}2^{\alpha N}b^m =2^{-N(a-\alpha-o(1))}.\] The slack \(\alpha<e_0\) absorbs a union over at most two columns and yields Equation (59).

Finally impose Proposition 14 on the start. When \(W_2(C)\le\zeta\), each column belongs to \(\mathcal S_{L_0}(C)\) with probability at most \(2^{e_0N}b^m\). The two cross columns are independent conditional on \(C\), so the gate probability is at most \((2^{e_0N}b^m)^2\le p_N^2\). ◻

Proof. Write \(g_1,\ldots,g_m\) for the coordinate images in \(\mathbb Z^m/K\). Choose a maximal set of \(j\) of these images whose subset sums are all distinct. Such a set is called dissociated. Once the other bits are fixed, at most one assignment of these \(j\) bits gives zero in the quotient, and that assignment has probability at most \(b^j\).

Maximality says that every \(g_i\) is a combination of the selected images with coefficients in \(\{-1,0,1\}\): otherwise adding it would preserve distinct subset sums. Put these coefficients in a \(j\)-by-\(m\) integer matrix \(M\), using identity columns at the selected indices. Then \(\mathop{\mathrm{rank}}M=\mathop{\mathrm{rank}}(MC)=j\), and evaluation of the selected images is a surjection \(\theta:\mathbb Z^j\twoheadrightarrow\mathbb Z^m/K\). Every column of \(MC\) lies in \(\ker\theta\). Choose \(j\) independent such columns; each has norm at most \(N\sqrt j\). The index of their integer span bounds the quotient order, so Hadamard’s inequality gives \[N^{qN}\le(N\sqrt j)^j\le N^{3j/2}.\] Thus \(j\ge2qN/3\), proving the assertion. If \(j=0\), the quotient is trivial and the same conclusion holds with empty products. ◻

Proof. For a fixed set \(\mathcal D\) of retained layers, the retention lattice and Lemma 27 give cost \(2^{-(2a/3)q(\mathcal D)N}\). Enumerate the sets consisting of all retained layers of height at least \(R-1\), with their total height times weight in \([q,2q)\).

For primes at most \(\sqrt N\), prefix lengths on the eligible plateaus specify the set. Equation (60) costs \[O\bigl(N^{3/4}(\log N)^{3/2}\bigr) =o(N/\log N)=o_\eta(qN)\] bits uniformly over the stated range. At larger primes each eligible layer contributes at least \((R-1)/(2N)\). There are therefore \(O(N/R)\) eligible layers in total, and a set of weight below \(2q\) contains at most \(O(qN/R)\) of them. The binomial estimate, or the all-subsets bound when \(q\) is bounded below, gives logarithmic count \[O\!\left(\frac{qN}{R}\bigl(1+\log(1/q)\bigr)\right) =o_\eta(qN).\] Indeed \(1+\log(1/q)=O_\eta(\ell)\), \(R\asymp\ell^2\), and \(qN/R\to\infty\) uniformly, so rounding has no effect. Every counted set has \(q(\mathcal D)\ge q\). Its probability cost absorbs both entropy bounds; for instance any fixed \(0<c_p<2a/3\) works for all sufficiently large \(N\). ◻

Proof. At each tested column form \(Q_{\rm hi}\) from Equation (62), and put \[\widetilde Q= \begin{cases} Q_{\rm hi},&Q_{\rm hi}\ge q_{\min},\\ 0,&Q_{\rm hi}<q_{\min}, \end{cases} \qquad q_{\min}=\frac{\eta}{100\log N}.\] Set \(\widetilde Q=0\) for every cross column of a step with singular start. This defines the quantities on the entire exposure space. At nonsingular starts, \(Q_{\rm hi}\le1/2\). For dyadic values \(q_j=2^jq_{\min}\le1/2\), Lemma 28 gives, with any fixed \(0<c'_p<c_p/2\), \[\begin{align*} \mathbb E\!\left[2^{c'_pN\widetilde Q}\mid\text{previous exposure}\right] &\le 1+\sum_{j:q_j\le1/2}2^{2c'_pNq_j}2^{-c_pNq_j}\\ &\le1+2^{-\Omega_{p,\eta}(N/\log N)}. \tag{67}\end{align*}\] The same bound holds at singular starts. There are at most \(2H_0\) tested columns. Successive conditioning, including between columns of a pair, yields \[ \mathbb E\,2^{c'_pN\sum\widetilde Q}\le1+o(1). \tag{68}\]

On \(\mathcal A\), suppose a window node has \(W_R>\eta\). Iterate Equation (57) backwards from that node, beginning with \(s=R\) and increasing \(s\) by the width at each step. Stop once \(s>N^{3/5}\). This takes at most \(\lceil N^{3/5}\rceil\) steps; even the earliest window node has \(H_0-5R>\lceil N^{3/5}\rceil\) predecessors for large \(N\). The final tail vanishes because Lemma 7 bounds every layer height by \(N^{3/5}\).

Number these backwards steps by \(j=1,2,\ldots\). At step \(j\), the threshold in the recursion is \(R\) plus the preceding widths, so every charged layer has height at least \[s+1-h\ge R+j-2\ge R-1.\] The contribution from one column is therefore at most \(2Q_{\rm hi}/(R+j-2)\). There are at most two columns per step. All contributions with \(Q_{\rm hi}<q_{\min}\) total at most \[4q_{\min}\sum_j\frac1{R+j-2} \le4q_{\min}(1+\log N)<\eta/2.\] The remaining contributions must exceed \(\eta/2\). Their denominators are at least \(R-1\), and consequently \[ \sum\widetilde Q\ge\frac{(R-1)\eta}{4}, \tag{69}\] where the sum may be extended to all tests on the fixed path. This same necessary condition holds for a violation at any window node. Markov’s inequality and Equation (68) prove the claim. ◻

Proof. At a noncostly step of width \(h\), the recursion gives \[ W_s(B)\le W_{s+h}(C)+4\sigma \qquad(s\ge h). \tag{70}\] Iterate this inequality from \(s=2\) backwards over any block of \(R\) noncostly steps. The threshold increases by at least \(R\), so the endpoint satisfies \[W_2\le\delta,\qquad \delta:=\eta+4R\sigma.\] Here and below \(\delta<\zeta\) for large \(N\).

Label the window nodes \(X_0,\ldots,X_{5R}\). If there are no costly steps, the last \(R\) steps contradict the terminal value. Suppose there is exactly one costly step, at position \(t\). There must be fewer than \(R\) steps after it, or the same argument again applies. Thus \(t\ge4R+1\). Both \(X_{t-2}\) and \(X_{t-1}\) end blocks of \(R\) noncostly steps inside the window, and hence both have \(W_2\le\delta\).

Assume there is no width-two step whose starting \(W_2\) is at most \(\zeta\). The two steps at positions \(t-1,t\) must then both have width one. Applying Equation (70) with \(s=1\) to the preceding step gives \[W_1(X_{t-1})\le W_2(X_{t-2})+4\sigma\le\delta+4\sigma.\] Even though step \(t\) is costly, its width is one, so the height comparison in Lemma 25 gives \[W_2(X_t)\le W_1(X_{t-1})\le\delta+4\sigma.\] The remaining steps are noncostly. For either width, Equation (70) with \(s=2\) and monotonicity of \(W_s\) in \(s\) show that each increases \(W_2\) by at most \(4\sigma\). There are fewer than \(R\) such steps, whence \[W_2(X_{5R})\le\eta+8R\sigma<\zeta,\] a contradiction. Figure 2 records the two adjacent width-one steps used in this argument. ◻

Proof of Proposition 5. Outside a set of probability \(2^{-\omega(N)}\), every nonsingular terminal matrix belongs to a required fixed-path event \(\mathcal A\). By Lemma 29 and Equation (65), we may also exclude, at the same scale, all such path events having \(W_R>\eta\) anywhere in their windows.

For a fixed remaining path with terminal \(W_2>\zeta\), Lemma 30 forces either two costly positions or a width-two gate with starting \(W_2\le\zeta\). To make the conditional probability calculation explicit, let \(\mathcal F_t\) contain all entries exposed through step \(t\). Define \(D_t\) to be the event that the starting matrix is in its typical set and step \(t\) is costly. Its starting-matrix indicator is \(\mathcal F_{t-1}\)-measurable, and Lemma 26 gives \[\mathbb E[\mathbf 1_{\{D_t\}}\mid\mathcal F_{t-1}]\le p_N.\] For any two positions \(r<t\), including consecutive ones, \[ \mathbb P(D_r\cap D_t) =\mathbb E\!\left[\mathbf 1_{\{D_r\}} \mathbb E[\mathbf 1_{\{D_t\}}\mid\mathcal F_{t-1}]\right] \le p_N\mathbb P(D_r)\le p_N^2. \tag{71}\] For a specified width-two position, the event of a typical start with \(W_2\le\zeta\) and a satisfied gate likewise has probability at most \(p_N^2\). These bounds require no conditioning on how a backwards path was selected or on any future path requirement: we upper-bound by the stated events after dropping all other conditions.

There are only \(O(R^2)\) pairs of positions or individual gate positions in the window. Taking the union over these and all fixed paths gives \[\mathbb P\{B\text{ nonsingular},\ W_2(B)>\zeta\} \le2^{-\omega(N)}+2^{o(N)}p_N^2 =2^{-\omega(N)}+2^{-2N(a-2e_0)+o(N)}.\] If \(W_2(B)\le\zeta\), Proposition 14 gives \(|\mathcal S_{L_0}(B)|\le2^{e_0N}\), apart from another typical exception. For all sufficiently large \(N\), the displayed bound and these exceptions are at most \(2^{-N(2a-10e_0)}\), as required. ◻