Proof. Put \(\epsilon=(A_n)_{11}\), multiply \(A_n\) by \(\epsilon\), and then apply the diagonal congruence with diagonal \[1,\ \epsilon(A_n)_{12},\ldots,\epsilon(A_n)_{1n}.\] The resulting first row and column consist of ones. Conditional on the original first row, the lower principal block still has independent uniform signs on and above its diagonal: every one of these signs has only been multiplied by a sign determined by the first row. Its Schur complement at the top left entry is therefore \(-2\mathbf B_{n-1}\). The two operations and the Schur complement preserve singularity. ◻

Proof. Choose a matrix \(X\) whose \(r\) columns form a basis of the column space of \(M\), and choose a left inverse \(T\) of \(X\). Since \(M\) is symmetric, its row space is the row space of \(X^{\mathsf T}\). Thus \[M=X S X^{\mathsf T},\qquad S=TMT^{\mathsf T}.\] The matrix \(S\) is symmetric and has rank \(r\). Choose \(r\) independent rows of \(X\). On those indices the principal submatrix of \(M\) is a product of three nonsingular \(r\times r\) matrices. ◻

Proof. If the rank is \(m-j\), Lemma 3 supplies a nonsingular principal submatrix on some \(m-j\) indices. Reveal all entries in the corresponding columns. The remaining symmetric \(j\times j\) block is forced over \(\mathbb K\), since its Schur complement must vanish. Each forced entry has at most one possible bit value, so the conditional probability is at most \(2^{-j(j+1)/2}\). Union over the choices of indices and over \(j\ge k\). For \(j>N^{3/5}\), the factor \(2^{-j(j+1)/2}\) dominates the at most \(2^m\) choices of indices and the \(m\) choices of \(j\). ◻

Proof. Let \(B\) have corank \(k\ge1\), and write \(K=\ker B\). Choose \(k-1\) coordinates whose restrictions to \(K\) are independent linear functionals. Flip the diagonal bit at each of those coordinates, and write \(D\) for the diagonal matrix of the changes. Its selected diagonal entries are all nonzero.

If \((B+D)v=0\), pairing this equation with every \(u\in K\) gives \(u^{\mathsf T}Dv=0\). The chosen coordinate functionals on \(K\) are independent, so the selected coordinates of \(v\) are zero. It follows that \(Bv=0\). Conversely, every vector in \(K\) with these coordinates zero lies in \(\ker(B+D)\). This subspace has dimension one. Hence flipping \(k-1\) diagonal bits produces a matrix of corank one.

For every matrix with \(k\le N^{3/5}\), fix one such choice of coordinates. Each resulting matrix has at most \[\sum_{j\le \lceil N^{3/5}\rceil}\binom Nj =2^{O(N^{3/5}\log N)}=2^{o(N)}\] preimages, because a preimage is recovered by specifying the flipped coordinates. All binary matrices are equally likely. The matrices of larger corank have the probability bounded in Lemma 4. ◻

Proof. Suppose a symmetric matrix \(M\) of size \(N\) has corank one, and choose \(0\ne v\in\ker M\). Delete an index \(i\) for which \(|v_i|\) is largest. The resulting principal submatrix \(B\) is nonsingular. Indeed, the adjugate of \(M\) is a nonzero scalar multiple of \(vv^{\mathsf T}\), so its \(i\)-th diagonal entry is nonzero.

Write \(z\) for the column at \(i\) on the remaining indices and \(a\) for its diagonal bit. The kernel equation and the Schur complement give \[B^{-1}z=-v_{[N]\setminus\{i\}}/v_i,\qquad a=z^{\mathsf T}B^{-1}z.\] Thus \(z\in\mathcal S(B)\). For any fixed deleted index, conditional on \(B\), the pair \((z,a)\) is uniform on \(\{0,1\}^{N-1}\times\{0,1\}\). For each \(z\in\mathcal S(B)\), the displayed equality fixes \(a\). The probability for that index is therefore \(2^{-N}\mathbb E|\mathcal S(\mathbf B_{N-1})|\). Union over \(i\). ◻

Proof. Extend a basis \(b_1,\ldots,b_k\) of \(K\) to a basis \(b_1,\ldots,b_r\) of \(L\). The projected vectors \(\pi_{F^\perp}b_{k+1},\ldots,\pi_{F^\perp}b_r\) form a basis of the projected lattice. Splitting Euclidean volume into the factor in \(F\) and the factor orthogonal to \(F\) gives the first determinant identity. The Gram matrix of the dual basis is the inverse Gram matrix, giving the identity for \(\det L^*\).

For \(y\in E\cap F^\perp\), the equality \(\langle y,\pi_{F^\perp}x\rangle=\langle y,x\rangle\) gives \((L/K)^*=L^*\cap F^\perp\). Projection of \(L^*\) to \(F\) is contained in \(K^*\). Conversely, for \(w\in K^*\), prescribe on the basis of \(L\) the integer values \(\langle w,b_i\rangle\) for \(i\le k\) and zero for \(i>k\). The representing vector belongs to \(L^*\), and its projection to \(F\) is \(w\). This proves the second dual identity. Finally, lift a basis of \(M\) and adjoin the basis of \(K\). The resulting basis of \(\widetilde M\) gives its rank and determinant by the same volume factorization. Empty bases give all the rank-zero cases. ◻

Proof. Put \(J=U\cap V\), and project orthogonally off \(J\). The lattice \(\Lambda_J=\Lambda_U\cap\Lambda_V\) is primitive in each of \(\Lambda_U,\Lambda_V,\Lambda_U+\Lambda_V\). For the last assertion, if \(u+v\in J\) with \(u\in\Lambda_U\) and \(v\in\Lambda_V\), then \(u,v\in J\). The projected spans of \(U\) and \(V\) intersect trivially. If \(\overline\Lambda_U,\overline\Lambda_V\) denote their projected lattices, the union of bases of these lattices is therefore a basis of their sum. Orthogonally projecting the second set of basis vectors off the span of the first can only decrease its volume. Hence \[\det(\overline\Lambda_U+\overline\Lambda_V) \le \det\overline\Lambda_U\,\det\overline\Lambda_V.\] Lemma 9 now gives \[\det(\Lambda_U+\Lambda_V)\det\Lambda_J \le \det\Lambda_U\,\det\Lambda_V.\] The saturation of \(\Lambda_U+\Lambda_V\) is \(\Lambda_{U+V}\), whose determinant is no larger. This proves the height inequality, and taking \(\log_N\) proves its additive form.

For a rank-\(r\) rational subspace, wedge a basis of \(\Lambda_W\). The resulting vector in \(\bigwedge^r\mathbb Z^m\) is determined up to sign, has Euclidean norm \(H(W)\), and determines its supporting subspace \(W\). Its integer coordinates are not all zero, so its norm is at least one. A bounded ball contains finitely many vectors of \(\bigwedge^r\mathbb Z^m\), and there are only \(m+1\) possible ranks. This proves the finiteness assertion. For \(r=0\), the exterior vector is \(1\) and there is just the zero subspace. ◻

Proof. The lattice \(\Lambda_V\) is primitive in \(\Lambda_U\), so the second dual identity in Lemma 9 gives \(\pi_V(\Lambda_U^*)=\Lambda_V^*\). Its kernel is \(\mathcal N_U(V)\), a primitive sublattice of the asserted rank. Factoring the determinant of \(\Lambda_U^*\) along this kernel gives \[\frac1{H(U)} =\det\mathcal N_U(V)\,\det\Lambda_V^* =\frac{\det\mathcal N_U(V)}{H(V)}.\]

An integer basis matrix for \(\Lambda_U\) gives a rational basis for its dual by inverting its Gram matrix. Thus \(\mathop{\mathrm{span}}M\), and hence \(V_M\), is rational. The saturation of \(M\) in \(\Lambda\) is exactly \(\mathcal N_U(V_M)\). The index formula for determinants and the first part of the lemma give the final identity; the inequality follows from \(H(V_M)\ge1\). ◻

Proof. Apply the cited theorem to \(T^{-1}L\) in its Euclidean span. Every rank-\(t\) sublattice of \(T^{-1}L\) has determinant at least one, and \(\rho_{1/\tau_j}(T^{-1}L)=\rho_{T/\tau_j}(L)\). ◻

Proof. Each point of norm at most \(R\) contributes at least \(\exp(-\pi R^2/s^2)\) to \(\rho_s(L)\), proving the first bound. The Gaussian Poisson formula in the span of \(L\) is \[\rho_s(L)=\frac{s^j}{\det L}\rho_{1/s}(L^*).\] The Gaussian mass is nondecreasing in its scale. Applying this fact to \(1/s'\le1/s\) in the formula proves the second bound. The last bound follows by using the first bound at scale \(u\), then the second bound and Theorem 12. The same Poisson identity reads \(1=1\) in rank zero. ◻

Proof. The rank-zero lattice has normalized determinant one. For a fixed positive rank \(t\), the determinant of a sublattice is the norm of the wedge of one of its bases in the discrete lattice \(\bigwedge^t L\). There are only finitely many such norms at most \(T^t\). Thus among all normalized determinants no greater than one there are only finitely many values, and the minimum is attained. Saturating a minimizer can only decrease its determinant while preserving its rank, so a primitive minimizer may be chosen. Comparison with the rank-zero lattice gives \(\det L_0\le T^{\mathop{\mathrm{rank}}L_0}\).

For a sublattice \(M\subset L/L_0\), lift it to \(\widetilde M\) as in Lemma 9. Minimality gives \[\frac{\det L_0}{T^{\mathop{\mathrm{rank}}L_0}} \le \frac{\det\widetilde M}{T^{\mathop{\mathrm{rank}}L_0+\mathop{\mathrm{rank}}M}} = \frac{\det L_0\,\det M}{T^{\mathop{\mathrm{rank}}L_0+\mathop{\mathrm{rank}}M}},\] which proves the quotient bound. Under the additional hypothesis, writing \(k=\mathop{\mathrm{rank}}L_0\), the two bounds on \(\det L_0\) give \(e^{-\Delta}T_0^k\le T^k\). Taking logarithms proves the rank bound. ◻

Proof. Among all nonempty affine restrictions \(\mathcal Q\) of \(\mathcal A\), choose one maximizing \[|\mathcal Q|\,2^{-\rho\dim\mathop{\mathrm{aff}}\mathcal Q}.\] There are finitely many distinct restrictions. Replacing the restricting affine space by \(\mathop{\mathrm{aff}}\mathcal Q\) preserves the restriction, so write the maximizer as \(\mathcal A_0=\mathcal A\cap F\), \(F=\mathop{\mathrm{aff}}\mathcal A_0\). Comparison with \(\mathcal A\) gives the lower bounds for its size.

Let \(E\subset F\) have codimension \(t\). If \(\mathcal A_0\cap E\ne\varnothing\), its affine span has dimension at most \(r-t\), and the intersection is itself an affine restriction of \(\mathcal A\). Maximality therefore gives \[|\mathcal A_0\cap E|\,2^{-\rho\dim\mathop{\mathrm{aff}}(\mathcal A_0\cap E)} \le |\mathcal A_0|\,2^{-\rho r},\] which is the required robustness bound. Empty intersections satisfy the bound as well. Choose \(r\) coordinate functionals independent on the direction space of \(F\). Projection to those coordinates is injective on \(F\), and maps \(\mathcal A_0\) into \(\{0,1\}^r\). Thus \(|\mathcal A_0|\le2^r\).

Finally, after \(i\) independent differences have been chosen, their affine span with \(a_0\) has codimension \(r-i\) in \(F\). Robustness leaves at least \((1-2^{-\rho(r-i)})|\mathcal A_0|\) choices for the next point. Multiplication for \(i=0,\ldots,r-1\) gives the claimed count. The empty product proves the rank-zero assertion. ◻

Proof. The finitely many image differences are rational vectors, so they have a common denominator. Their integer span is therefore contained in a scaled copy of \(\mathbb Z^d\) and is discrete. The linear part of \(\Phi\) is injective on the direction space of \(F\), so this lattice has rank \(r\). Changing \(a_0\) does not change the generated group. The assertions are immediate if \(r=0\); suppose \(r\ge1\).

Set \(T=(\log N)^4\), and choose \(L_0\subset L_\Phi\) by Lemma 14. Write \(\Gamma=L_\Phi/L_0\) for its orthogonal quotient and \(j=\mathop{\mathrm{rank}}\Gamma\). The quotient has \(\det M\ge T^{\mathop{\mathrm{rank}}M}\) for every sublattice \(M\subset\Gamma\), while \(\det L_0\le T^{r-j}\). Fix \(a_0\), and project the vectors \(\Phi(a)-\Phi(a_0)\) into \(\Gamma\). They have norm at most \(C_0\sqrt N\). If \(j\ge1\), Lemma 13 at scale \(T/\tau_j\) bounds the number \(M\) of distinct projections by \[M\le\frac32 \exp\!\left(\frac{\pi C_0^2N\tau_j^2}{T^2}\right) \le 2^{O_{C_0}(N/(\log N)^6)}.\] Here \(j\le r\le N\), so \(\tau_j=O(\log N)\). The same final bound holds for \(j=0\), when \(M=1\).

The preimage in \(F\) of any one projection fiber is an affine subspace of codimension \(j\). A largest fiber contains at least \(|\mathcal A|/M\) points, whereas robustness bounds its size by \(2^{-\rho j}|\mathcal A|\). It follows that \[j\le\frac{\log_2 M}{\rho} =O_{C_0}\!\left(\frac{N\ell^D}{(\log N)^6}\right).\] The projected differences generate \(\Gamma\). Choose \(j\) of them that are independent. Their integer span is a full-rank sublattice of \(\Gamma\), so the index formula and Hadamard’s inequality give \[\det\Gamma\le (C_0\sqrt N)^j.\] For \(j=0\) this is the equality \(1=1\). Factoring the determinant along \(L_0\) now yields \[\det L_\Phi \le T^{r-j}(C_0\sqrt N)^j, \qquad \log\det L_\Phi \le 4N\ell+ O_{C_0}\!\left(\frac{N\ell^D}{(\log N)^5}\right).\] For fixed \(D\), the error is \(o(N\ell)\), which proves the stated determinant bound.

For the identity map the difference norms are at most \(\sqrt m\le\sqrt N\), and \(L_\Phi\) is a full-rank sublattice of \(W\cap\mathbb Z^m\). Saturating therefore decreases its determinant, giving \(H(W)\le\det L_\Phi\) and the asserted height bound. ◻

Proof. For any rational subspace \(U\subseteq\mathbb R^m\), the lattice \(U\cap\mathbb Z^m\) is primitive in \(\mathbb Z^m\). Consequently an integer basis matrix \(C_U\) of this lattice has full column rank modulo two: a basis of a primitive sublattice extends to a basis of \(\mathbb Z^m\). If \(U,V\) are rational, the matrix of the tested form is the integer matrix \(C_U^{\mathsf T}BC_V\). Its real rank is at least the rank of its reduction modulo two, because a nonzero minor modulo two is an odd, hence nonzero, integer minor. Moreover \(B\bmod 2\) is uniform among symmetric matrices over \(\mathbb F_2\). Thus Equation (12) applies to the reductions of the column spaces of \(C_U,C_V\), which have the same respective dimensions as \(U,V\). Their intersection after reduction can be larger than the reduction of \(U\cap V\); the intersection correction in the preceding count accommodates this without any further assumption.

The tests we need are \(U=V\), and \(V=E_X\). In the second case, \[\mathop{\mathrm{rank}}\bigl[\pi_UBe_i\bigr]_{i\in X} =\mathop{\mathrm{rank}}(C_U^{\mathsf T}BC_{E_X}),\] where \(C_{E_X}\) consists of the coordinate vectors with indices in \(X\). To see this equality, \(C_U^{\mathsf T}\) annihilates \(U^\perp\) and is an isomorphism from \(U\) to \(\mathbb R^{\dim U}\). It therefore detects exactly the rank after projection to \(U\).

We also need stability when the testing subspace changes. For fixed \(B\) and \(X\), define \[\delta_0(U)=\dim U-\mathop{\mathrm{rank}}(B|_U),\qquad \delta_X(U)=\min\{|X|,\dim U\} -\mathop{\mathrm{rank}}(C_U^{\mathsf T}BC_{E_X}),\] where the second rank can equivalently be defined by the bilinear form on \(U\times E_X\), without choosing an integer basis. If \(Z\subseteq U\), restricting a matrix to \(Z\times Z\) deletes \(\dim U-\dim Z\) rows and the same number of columns. Its rank decreases by an amount between zero and twice that number. Hence \[|\delta_0(U)-\delta_0(Z)|\le\dim U-\dim Z.\] For the form on \(U\times E_X\), the rank and the quantity \(\min\{|X|,\dim U\}\) each decrease by an amount between zero and \(\dim U-\dim Z\). The same inequality follows for \(\delta_X\). Taking \(Z=U\cap V\) in these two inequalities gives \[ |\delta_0(U)-\delta_0(V)|\le d(U,V),\qquad |\delta_X(U)-\delta_X(V)|\le d(U,V). \tag{13}\] Here \(d(U,V)=\dim U+\dim V-2\dim(U\cap V)\), and the dimension formula also gives \(d(U^\perp,V^\perp)=d(U,V)\).

Fix \(D,A\), put \(s=N\ell^{-A}\), and apply Theorem 17 with precision exponent \(P=2A+4\). For each \(m\in\mathcal I_N\), it gives a list \(\mathcal C_m\) of rational subspaces with \[|\mathcal C_m|\le 2^{N^2\ell^{-P}},\qquad \min_{V\in\mathcal C_m}d(W,V)\le N\ell^{-P}\] for every \(W\) in the height range of the proposition. Set \(t=\lceil s/2\rceil\). Apply Equation (12) to \(U=V^\perp\) for every \(V\in\mathcal C_m\), both to its restricted form and to its form against every \(E_X\). The comparison of real and mod-two ranks above shows that the probability that any of these real deficiencies is at least \(t\) is at most \[C_0(1+2^m)\,2^{N^2\ell^{-P}-t(t+1)/2} \le 2^{-\Omega(N^2\ell^{-2A})}.\] In the last inequality, \(N^2\ell^{-P}=o(N^2\ell^{-2A})\) and \(m=o(N^2\ell^{-2A})\), uniformly in the stated range of \(m\). Tests whose smaller dimension is less than \(t\) need not be included.

Outside this event, choose a covering \(V\) for a given \(W\). Equation (13), applied to their orthogonal complements, bounds each deficiency for \(W\) by \[t-1+N\ell^{-P}<s\] for all sufficiently large \(N\). This holds simultaneously for all such \(W\) and all \(X\). Finally, \(N\ell^{-2A}\to\infty\), so the displayed exceptional probability has the form required in the statement. ◻

Proof. The two radicals are \[\operatorname{rad}(B|_{W^\perp}) =W^\perp\cap B^{-1}W, \qquad \operatorname{rad}(B^{-1}|_W) =W\cap B(W^\perp).\] Since \(B\) is nonsingular, multiplication by \(B\) is an isomorphism from the first space onto the second, with inverse multiplication by \(B^{-1}\). Their dimensions are equal. The first assertion of Proposition 18 therefore gives the claimed rank for the inverse form, on the same typical set. ◻

Proof. If \(B\) is nonsingular over \(\mathbb R\), its determinant is a nonzero integer. Every prime at which its reduction has positive corank divides that determinant. Hadamard’s inequality gives \[1\le |\det B|\le m^{m/2}\le N^{N/2},\] so it suffices to consider primes \(p\le N^{N/2}\). For each such prime, Lemma 4, with field \(\mathbb F_p\), bounds the probability of corank greater than \(N^{3/5}\) by \(2^{-cN^{6/5}}\) for an absolute \(c>0\), uniformly in \(p\) and \(m\). Even bounding the number of these primes by \(N^{N/2}\), the union bound is \[2^{(N/2)\log_2N-cN^{6/5}} \le 2^{-cN^{6/5}/2}\] for all sufficiently large \(N\). This also proves the asserted uniformity. ◻

Proof. Mean bound. Let \(J_m\) be the all-ones matrix and write \[2B=J_m+S,\qquad X=S/\sqrt m.\] The entries of \(S\) on and above the diagonal are independent uniform signs. We first bound the number of eigenvalues of \(X\) in a short interval about zero.

The limiting moments in the following calculation are those of Wigner’s semicircle law [18]. We include the closed-walk enumeration to obtain the quantitative error bound needed here. Let \[d\mu_{\mathrm{sc}}(x)=\frac{1}{2\pi}\sqrt{4-x^2}\, \mathbf 1_{[-2,2]}(x)\,dx.\] For \(i\ge1\) with \(i+1\le m\), \[ \left|\frac1m\mathbb E\mathop{\mathrm{Tr}}X^{2i} -\int x^{2i}\,d\mu_{\mathrm{sc}}(x)\right| \le \frac{(2i+1)^{2i+2}}{m}, \qquad \mathbb E\mathop{\mathrm{Tr}}X^{2i-1}=0. \tag{14}\] To prove it, expand the normalized trace as \[\frac1m\mathbb E\mathop{\mathrm{Tr}}X^k =m^{-1-k/2}\sum_{v_0,\ldots,v_{k-1}\in[m]} \mathbb E\prod_{r=0}^{k-1}S_{v_rv_{r+1}}, \qquad v_k=v_0.\] Each summand is a closed walk, with edges regarded as unordered and loops allowed. Its expectation is one if every distinct edge is used an even number of times, and is zero otherwise. This proves the odd-moment assertion. For \(k=2i\), a contributing walk has at most \(i\) distinct edges. Its graph is connected, and hence has at most \(i+1\) vertices. Equality forces exactly \(i\) nonloop edges, each used twice, forming a tree. When vertices are named in order of first appearance, these walks are in bijection with Dyck words of length \(2i\): the first traversal of a tree edge raises the depth, and its return traversal lowers it. Their number is the Catalan number \(\mathrm{Cat}_i=(i+1)^{-1}\binom{2i}{i}\), and each has \((m)_{i+1}=m(m-1)\cdots(m-i)\) injective labelings.

The contribution of these tree walks is therefore \(\mathrm{Cat}_i(m)_{i+1}/m^{i+1}\). Its difference from \(\mathrm{Cat}_i\) is at most \(\mathrm{Cat}_i i(i+1)/(2m)\), using \(1-\prod_{h=0}^i(1-h/m)\le\sum_{h=0}^i h/m\). Every remaining contributing walk has at most \(i\) vertices. There are at most \((2i+1)^{2i}\) canonical vertex sequences, a crude bound obtained by allowing each position any of \(2i+1\) names. Each such sequence has at most \(m^i\) labelings and so contributes at most \(1/m\) after normalization. Finally, elementary beta integration gives \[\int x^{2i}\,d\mu_{\mathrm{sc}}(x) =\frac{(2i)!}{i!(i+1)!}=\mathrm{Cat}_i,\] and its odd moments vanish. Combining these estimates, and using \(\mathrm{Cat}_i\le4^i\), gives Equation (14).

Fix the exponent \(A\) in the proposition and put \[w=\ell^{-A-5},\qquad j=\lceil\ell^{2A+4}\rceil, \qquad f(x)=(1-|x|/w)_+, \qquad p_j(x)=2(1-x^2/16)^{2j}.\] For all large \(N\), \(f(x)\le p_j(x)\) for every real \(x\). Outside \([-w,w]\) this follows from nonnegativity of the even power. Inside that interval, Bernoulli’s inequality gives \[p_j(x)\ge 2(1-w^2/16)^{2j} \ge 2(1-jw^2/8)\ge1\ge f(x),\] because \(jw^2=O(\ell^{-6})\). All moments in \(p_j\) have degree at most \(4j\), and \(2j+1\le m\) uniformly in \(m\in\mathcal I_N\) for large \(N\). Expanding this polynomial and applying Equation (14) term by term, the sum of the absolute values of its coefficients is \(2(17/16)^{2j}\). Consequently \[\left|\frac1m\mathbb E\mathop{\mathrm{Tr}}p_j(X) -\int p_j\,d\mu_{\mathrm{sc}}\right| \le \frac{2(17/16)^{2j}(4j+1)^{4j+2}}{m} =m^{-1+o(1)}.\] This estimate verifies the required growing degrees: indeed \[j\log(j+1)=O_A(\ell^{2A+4}\log\ell)=o(\log m)\] uniformly in the stated range. In particular the last error is \(o(\ell^{-A})\). On the support of \(\mu_{\mathrm{sc}}\), \((1-x^2/16)^{2j}\le\exp(-jx^2/8)\) and the density is at most \(1/\pi\). Thus \[\int p_j\,d\mu_{\mathrm{sc}} \le \frac2\pi\int_{\mathbb R}e^{-jx^2/8}\,dx =O(j^{-1/2})=O(\ell^{-A-2}).\] The pointwise majorization now proves \[ \mathbb E\mathop{\mathrm{Tr}}f(X)=o(m\ell^{-A}), \tag{15}\] again uniformly in \(m\).

Concentration and translation to \(B\). We next obtain concentration strong enough for typicality. Pointwise, \[f(x)=1-g_1(x)+g_2(x),\qquad g_1(x)=|x|/w,\qquad g_2(x)=(|x|/w-1)_+.\] Both \(g_1,g_2\) are convex and \(1/w\)-Lipschitz. Their traces are convex functions of a real symmetric matrix. For completeness, if \(M_+\) denotes its spectral positive part, then \[\mathop{\mathrm{Tr}}M_+=\max_{0\preceq P\preceq I}\mathop{\mathrm{Tr}}(PM).\] The identities \[\mathop{\mathrm{Tr}}g_1(M)=w^{-1}\bigl(\mathop{\mathrm{Tr}}M_++\mathop{\mathrm{Tr}}(-M)_+\bigr),\qquad \mathop{\mathrm{Tr}}g_2(M)=\mathop{\mathrm{Tr}}(M/w-I)_++\mathop{\mathrm{Tr}}(-M/w-I)_+\] express each trace as a sum of suprema of affine functions of \(M\), which proves convexity.

Let \(y=(y_{ab})_{a\le b}\) be an arbitrary real vector of independent upper-triangular coordinates, and form \(X(y)=S(y)/\sqrt m\) by symmetric reflection. For real symmetric matrices, the Hoffman–Wielandt inequality [9], with their eigenvalues ordered, states that \[\sum_{i=1}^m|\lambda_i(M)-\lambda_i(M')|^2 \le\|M-M'\|_F^2.\] It follows by Cauchy–Schwarz that for \(a=1,2\), \[|\mathop{\mathrm{Tr}}g_a(X(y))-\mathop{\mathrm{Tr}}g_a(X(z))| \le\frac{\sqrt m}{w}\|X(y)-X(z)\|_F \le\frac{\sqrt2}{w}\|y-z\|_2.\] The last inequality uses \(\|X(y)-X(z)\|_F^2\le(2/m)\|y-z\|_2^2\). Thus each trace is convex and \(L\)-Lipschitz as a function of the independent coordinates, with \(L=\sqrt2/w\).

Talagrand’s convex Lipschitz concentration theorem on the product cube [15] implies that, for universal \(c,C>0\), if \(F:\mathbb R^d\to\mathbb R\) is convex and globally \(L\)-Lipschitz for the Euclidean norm, then its value at independent uniform signs satisfies \[\Pr(|F-\mathbb EF|>u)\le C\exp(-cu^2/L^2)\qquad(u\ge0).\] The usual statement about a median implies this form: integrating its tail bounds the difference between the median and the expectation by \(O(L)\), which can be absorbed by adjusting \(c,C\). Apply the theorem to the two traces. By Equation (15), their difference \(\mathop{\mathrm{Tr}}f(X)=m-\mathop{\mathrm{Tr}}g_1(X)+\mathop{\mathrm{Tr}}g_2(X)\) has expectation at most \(m\ell^{-A}/8\) for large \(N\). If it exceeds \(m\ell^{-A}/4\), at least one of the two convex traces deviates from its expectation by more than \(m\ell^{-A}/16\). Therefore \[ \Pr\bigl(\mathop{\mathrm{Tr}}f(X)>m\ell^{-A}/4\bigr) \le 2C\exp\bigl(-c' m^2\ell^{-2A}w^2\bigr) \le 2^{-c_A N^2\ell^{-4A-10}} \tag{16}\] for some \(c',c_A>0\) and all sufficiently large \(N\), uniformly in \(m\). Since \(N\ell^{-4A-10}\to\infty\), this is a \(2^{-Nf_A(N)}\) exceptional probability with \(f_A(N)\to\infty\).

On the complementary event, \(f\ge1/2\) on \([-w/2,w/2]\) shows that \(X\) has at most \(m\ell^{-A}/2\) eigenvalues in that interval. Finally \(2B/\sqrt m=X+J_m/\sqrt m\) is a rank-one perturbation of \(X\). Eigenvalue interlacing changes the cumulative eigenvalue count at either endpoint of an interval by at most one, so it can increase the count in any interval by at most two. Take \(C_A=A+6\). Uniformly for \(m\in\mathcal I_N\), \[2\sqrt{N/m}\,\ell^{-C_A}\le w/2\] for all sufficiently large \(N\). The eigenvalues of \(B\) in the interval of the proposition therefore number at most \[\frac12m\ell^{-A}+2\le N\ell^{-A}.\] Together with Equation (16), this proves the proposition. ◻

Proof. Let \(p^j\) be the exponent of a nonzero group still to be split. If some element has self-pairing of order \(p^j\), it has order \(p^j\) and its cyclic subgroup is a block of the first kind. Otherwise choose an element \(x\) of order \(p^j\). Perfectness implies that the character \(\lambda(x,\cdot)\) has order \(p^j\), so there is an element \(y\) for which \(\lambda(x,y)\) has order \(p^j\). Write the three pairing values on \(x,y\), with denominator \(p^j\), using numerators \(a,c,d\), respectively. Then \(c\) is a unit modulo \(p\), while \(a,d\) are divisible by \(p\). For odd \(p\), the self-pairing numerator of \(x+y\) is \(a+2c+d\), a unit, so again a block of the first kind is available.

For \(p=2\), the two diagonal numerators are even and the off-diagonal numerator is odd. The resulting two by two numerator matrix is invertible modulo \(2^j\). Pairing a relation between \(x,y\) with \(x,y\) therefore shows that its two coefficients vanish modulo \(2^j\). Thus they span \((\mathbb Z/2^j\mathbb Z)^2\), and the restriction of the pairing to this subgroup is perfect, giving the second kind of block.

It remains to justify splitting a block \(H\) off orthogonally. Because the pairing on \(H\) is perfect, for any \(g\in G\) there is a unique \(h\in H\) such that \(\lambda(g,\cdot)|_H=\lambda(h,\cdot)|_H\). Hence \(g-h\in H^\perp\). Also \(H\cap H^\perp=0\), so \(G=H\oplus H^\perp\). The pairing on \(H^\perp\) is perfect, since an element annihilating both summands annihilates \(G\). Iteration proves the decomposition. ◻

Proof. The exponent of \(T\) divides \(p^h\). Isotropy and orthogonality therefore imply \[ p^h\lambda_U(x_U,x_U)=0 \tag{18}\] for every element under consideration. There are at most two cyclic factors in \(U\). A block of the second kind cannot be divided by the cutoff at \(h\), since its two factors have equal exponent. We can thus handle all possibilities explicitly. In the following, \(v_p(0)=+\infty\); for a nonzero cyclic coordinate its valuation is that of any representative not divisible by the full modulus.

If \(U=0\), use one color. If it has one factor, this is a cyclic block of exponent \(j>h\), with coordinate \(x\) and a unit self-pairing numerator. Equation (18) forces \[v_p(x)\ge \left\lceil\frac{j-h}{2}\right\rceil.\] Two such coordinates have mutual pairing annihilated by \(p^h\), so again one color suffices.

Suppose next that \(U\) consists of two orthogonal cyclic blocks of exponents \(j\ge i>h\), with respective unit self-pairing numerators \(a_1,a_2\). For their coordinates \(x,y\), put \[F=\max\{j-2v_p(x),\,i-2v_p(y)\}.\] Use one deep color for \(F\le h\). Two deep elements have the required mutual denominator term by term, since the sum of the two valuations in either coordinate is at least its exponent minus \(h\). If \(F>h\), the two entries in the maximum must equal \(F\). Otherwise the term of largest denominator in the self-pairing could not cancel, contrary to Equation (18). In particular \(F\le i\), and \(F\) has the parity of both \(i\) and \(j\). Write \[x=p^{(j-F)/2}X,\qquad y=p^{(i-F)/2}Y,\] where \(X,Y\) are units. With \(n=F-h>0\), the self-pairing condition is \[a_1X^2+a_2Y^2\equiv0\pmod{p^n}.\] The residues of \(X,Y\) modulo \(p^n\) are well defined: they are determined modulo \(p^{(j+F)/2}\) and \(p^{(i+F)/2}\), respectively, and both exponents are at least \(F\ge n\). Color this element by \(F\) and \(r=XY^{-1}\bmod p^n\). Its ratio satisfies \(r^2\equiv-a_2a_1^{-1}\pmod{p^n}\). For two elements with the same color, using primes for the coordinates of the second one, \[a_1XX'+a_2YY' \equiv YY'(a_1r^2+a_2)\equiv0\pmod{p^n}.\] This is precisely Equation (17).

For completeness, a unit square has at most two square roots modulo an odd prime power and at most four modulo a power of \(2\). Indeed, for two unit roots \(r,s\), the modulus divides \((r-s)(r+s)\). At an odd prime at most one factor is divisible by \(p\), giving \(r\equiv s\) or \(r\equiv-s\pmod{p^n}\). At \(2\), for odd \(r,s\), one of \(r-s,r+s\) has valuation exactly one and the other is divisible by four, with the convention of infinite valuation at zero. For \(n\ge2\) this gives \(r\equiv s\) or \(r\equiv-s\pmod{2^{n-1}}\), allowing at most four residues modulo \(2^n\); \(n=1\) is immediate.

There are at most \(\lceil(i-h)/2\rceil\) possible nondeep values of \(F\). At odd \(p\), the count is thus at most \(1+2\lceil(i-h)/2\rceil\). For \(i-h\ge2\) this is at most \(2^{i-h}\). If \(i-h=1\) and a nondeep element exists, its value is \(F=h+1\). The parity just established shows that in a deep element the two exponent-minus-twice-valuation quantities are at most \(h-1\). In the coordinate of exponent \(j\), for example, a deep valuation is at least \((j-h+1)/2\), whereas a nondeep valuation is \((j-h-1)/2\). Their sum is at least \(j-h\), and the same argument applies to the coordinate of exponent \(i\). Every deep element therefore has the required mutual denominator with every nondeep element. Merge the deep color into one nondeep color, leaving at most two colors. If there is no nondeep element, one color suffices. This proves the odd-prime bound in this case. At \(2\), the unmerged count is at most \(1+4\lceil(i-h)/2\rceil\), which satisfies the asserted polynomial bound.

The remaining possibility is a single block of the second kind at \(2\), of exponent \(j>h\). Write its numerator matrix as \(\left(\begin{smallmatrix}2a&c\\c&2d\end{smallmatrix}\right)\) with \(c\) odd, and put \[t=\min\{v_2(x),v_2(y)\},\qquad F=j-2t.\] Again use a deep color for \(F\le h\). For two deep elements, the valuation of each coordinate in each element is at least \(\lceil(j-h)/2\rceil\), which proves the mutual denominator bound. For \(F>h\), write \(x=2^tX,y=2^tY\), so at least one of \(X,Y\) is odd, and put \(n=F-h\). Choose the first coordinate as pivot if it is odd, and otherwise choose the second. After ordering the pivot first, call it \(u\), call the other coordinate \(v\), and write \[f(X,Y)=aX^2+cXY+dY^2,\] interchanging \(a,d\) when the second coordinate is the pivot. The self-pairing numerator is twice this quadratic form. Thus Equation (18) says \[f(u,v)\equiv0\pmod{2^{n-1}},\] where the condition is empty for \(n=1\). Color the element by \(F\), the pivot, and \(r=vu^{-1}\bmod 2^n\). This ratio satisfies \[f(1,r)=a+cr+dr^2\equiv0\pmod{2^{n-1}}.\] The ratio is well defined modulo \(2^n\), since the normalized coordinates are determined modulo \(2^{j-t}\) and \(n\le j-t\). Its derivative \(c+2dr\) is odd. Every root modulo \(2^\alpha\), for \(\alpha\ge1\), therefore has exactly one root lift modulo \(2^{\alpha+1}\): the two possible lifts change the value modulo \(2^{\alpha+1}\) by \(2^\alpha\) times an odd number. There are at most two roots modulo \(2\). It follows that there are at most four permissible ratios modulo \(2^n\), including the one extra bit beyond the modulus in the self-pairing condition. This bound also holds for \(n=1\).

For two elements of the same color, their normalized pivot coordinates are odd numbers \(u,u'\) and their ratios satisfy \(r'\equiv r\pmod{2^n}\). Their bilinear numerator modulo \(2^n\) is \[uu'\bigl(2a+c(r+r')+2drr'\bigr) \equiv 2uu'f(1,r)\equiv0\pmod{2^n}.\] Restoring the common factor \(2^{2t}\) proves Equation (17). There are at most \(b_1\) possible values of \(F>h\), two pivots, and four ratios at each pivot, so the count is at most \(1+8b_1\). The same bound holds in all preceding cases. Finally, the number of factors above \(h\) is zero, one, or two according as handled above, and their second exponent satisfies \(i-h=b_2-b_3\) when there are two. This proves the asserted bounds. ◻

Proof. Fix a prime and abbreviate \(h=b_{p,3}\). In the orthogonal decomposition \(G_{B,p}=U\oplus T\) used in Lemma 23, let \(d=\#\{i:b_{p,i}>h\}\le2\). Project the \(p\)-primary part of \(H\) to subgroups \(H_U\subset U\) and \(H_T\subset T\). Every pairing between projections of elements of \(X\) is annihilated by \(p^h\) on \(U\). Bilinearity gives the same conclusion for pairings of arbitrary elements of \(H_U\), since these are generated by projections of differences.

A subgroup of a finite abelian \(p\)-group with \(d\) cyclic factors has at most \(d\) generators. One way to see this is that its minimal number of generators equals the dimension of its subgroup annihilated by \(p\), which is at most \(\dim_{\mathbb F_p}U[p]=d\). The image of the restricted pairing map on \(H_U\) is a quotient of \(H_U\), and it is annihilated by \(p^h\). Its order is therefore at most \(p^{hd}\). The image order of the restricted pairing on \(H_T\) is at most \(|H_T|\le|T|\).

Pull these two pairings back to the \(p\)-primary part of \(H\). The image of the sum of their maps is contained in the sum of their images, whose order is at most the product of the two orders. Consequently the image order at this prime is at most \[|T|p^{hd} =p^{\sum_i\min(b_{p,i},h)} =p^{\sum_{e\le b_{p,3}}k_B(p,e)}.\] The range \(e\le b_{p,3}\) is exactly the range in which \(k_B(p,e)\ge3\). Distinct primary pairings are orthogonal, so multiplying the last bound over primes gives \[|\mathop{\mathrm{im}}\theta_H| \le\prod_p p^{\sum_{e:\,k_B(p,e)\ge3}k_B(p,e)} =N^{NJ_B},\] as required. ◻

Proof. The matrix of \(q\) in an \(L\)-basis is rational. Its kernel is therefore rational in that basis, so \(K\) spans the radical. It is primitive because it is the intersection of \(L\) with a real subspace. Extending a basis of \(K\) to a basis of \(L\) shows both that \(\bar L\) is a lattice and that \[\det L=\det K\,\det\bar L.\] The form vanishes whenever one argument is in the radical, so it descends to the projected lattice \(\bar L\). Its pairing map there has the same image order \(t\): the quotient \(L\to\bar L\) is surjective, and pullback injects \(\mathop{\mathrm{Hom}}(\bar L,\mathbb Q/\mathbb Z)\) into \(\mathop{\mathrm{Hom}}(L,\mathbb Q/\mathbb Z)\). The image is finite because the form has rational entries in a lattice basis.

Let \(M\) be its matrix in a basis of \(\bar L\), of rank \(s=\dim S\). It is a nonsingular rational matrix. The kernel of the pairing modulo \(\mathbb Z\) in \(\mathbb Z^s\) has index \(t\); choose its integer basis matrix \(A\), so \(|\det A|=t\). The matrix \(A^{\mathsf T}M\) is integral. It has nonzero determinant, and hence \[1\le |\det(A^{\mathsf T}M)|=t|\det M|.\] This uses the pairing index on one side of the matrix. If \(P\) is the basis matrix of \(\bar L\) in orthonormal coordinates on \(S\), then \(M=P^{\mathsf T}M_{\mathrm{orth}}P\) and \(|\det P|=\det\bar L\). Thus \[|\det M_{\mathrm{orth}}| =\frac{|\det M|}{(\det\bar L)^2} \ge\frac{1}{t(\det\bar L)^2},\] which proves Equation (21). The rank-zero case has \(t=1\) and follows from the stated conventions. ◻

Proof of Proposition 7. Fix \(A>0\), and choose a fixed \(P>A+2\). Intersect the typical event of Corollary 19 with exponent \(D=2\) in the subspace height bound and precision \(P\), and that of Proposition 21 with precision \(P\). This is a typical event uniformly for \(m\in\mathcal I_N\). On it the rank conclusion holds simultaneously for every rational subspace \(W\subset\mathbb R^m\) with \(H(W)\le\exp(N\ell^2)\); the spectral conclusion holds for \(B\) itself. We will verify that the subspace selected below meets this height bound, so the selection may depend on \(B\) and on all its admissible columns.

Fix a nonsingular \(B\) in this event. There is nothing to prove if \(\mathcal S(B)\) is empty. Otherwise choose a largest overall color among its elements, with the color of a column meaning the color of its class in \(G_B\). Lemma 15, applied to this color with parameter \(\rho=\ell^{-P}\), gives a nonempty subset \(T\) robust on its affine span and satisfying \[ \log_2|\mathcal S(B)| \le \log_2 C_{\mathrm{col}}(B)+N\ell^{-P}+\log_2|T|. \tag{22}\] Put \(W=\mathop{\mathrm{span}}(T-T)\) and \(r=\dim W\). This is a rational subspace, since it is spanned by integer differences. Projection onto a suitable set of \(r\) coordinates is injective on \(W\), and hence on the affine span of \(T\). Therefore \[ |T|\le2^r. \tag{23}\]

The graph below uses admissibility to keep differences short and retains integral first coordinates for the determinant bound on the radical lattice. For an eigenvalue \(\lambda\) of \(B\), its induced metric changes the corresponding eigenvalue \(1/\lambda\) of the inverse form to \(\lambda/(1+\lambda^2)\), which is bounded even when \(\lambda\) is small. Consider the rational injective graph map \[\gamma:\mathbb R^m\longrightarrow\mathbb R^{2m},\qquad \gamma(z)=(z,B^{-1}z),\] and the rank-\(r\) lattice \[L=\langle\gamma(z)-\gamma(t):z,t\in T\rangle_{\mathbb Z} \quad\text{in }\gamma(W).\] Each graph difference has squared norm at most \(m+4m\le5N\): the first coordinates are differences of bits, and each inverse image has infinity norm at most one. The restriction of \(\gamma\) to the affine span of \(T\) is a rational affine injection, and it preserves the codimensions occurring in robustness. Lemma 16 therefore applies to these graph points. It also applies to the original cube points. For a constant \(C_0\) depending only on \(P\), it gives \[ \det L\le\exp(C_0N\ell),\qquad H(W)\le\exp(C_0N\ell). \tag{24}\] For all sufficiently large \(N\), the second bound in Equation (24) is at most \(\exp(N\ell^2)\). Thus this adaptively chosen \(W\) lies in the simultaneous scope of Corollary 19. Lemma 16 is deterministic for every such robust set and graph map, and the spectral event is a statement about all eigenvalues of \(B\); neither requires \(W\) to have been fixed in advance.

On the whole graph \(\Gamma=\gamma(\mathbb R^m)\), define \[Q(\gamma(x),\gamma(y))=x^{\mathsf T}B^{-1}y.\] Let \(s\) be the rank of its restriction to \(\gamma(W)\). The graph map identifies that restriction with the restriction of the bilinear form \(B^{-1}\) to \(W\). Hence Corollary 19 gives \[ s\ge r-N\ell^{-P}. \tag{25}\] The reduction of \(Q\) modulo \(\mathbb Z\) on \(L\) is the pullback of the restricted discriminant pairing on \[H=\langle \bar z-\bar t:z,t\in T\rangle\subset G_B.\] Indeed, the map \(L\to H\) sending \(\gamma(u)\) to \(u+B\mathbb Z^m\) is surjective and respects these pairings. Pullback on the corresponding character groups is injective, so the two pairing images have the same order. By Lemma 24, this order is at most \(N^{NJ_B}\).

Let \(K=L\cap\operatorname{rad}(Q|_{\gamma(W)})\), and let \(S\) be the orthogonal complement of this radical in \(\gamma(W)\). The rationality assertion in Lemma 25 applies since \(B^{-1}\) is rational and the first coordinates of vectors in \(L\) are integral. Consequently \(\mathop{\mathrm{rank}}L=r\), \(\mathop{\mathrm{rank}}K=r-s\), and \(\dim S=s\). There is also the lower bound \(\det K\ge1\). In fact the projection to the first \(m\) coordinates is injective on \(\Gamma\), and it maps \(K\) to an integer lattice of the same rank. The squared determinant of an integer lattice is the positive integer determinant of the Gram matrix of an integer basis, so its determinant is at least one. Orthogonal projection contracts Euclidean volumes, giving the same lower bound for \(\det K\). This includes rank zero by convention.

Lemma 25, followed by Equation (24), now gives \[ \left|\det_{\mathrm{orth}}(Q|_S)\right| \ge N^{-NJ_B}(\det L)^{-2} \ge N^{-NJ_B}\exp(-2C_0N\ell). \tag{26}\]

We compare this with the spectrum of \(Q\) on \(\Gamma\), using the Euclidean metric induced from \(\mathbb R^{2m}\). If \(v_i\) are orthonormal eigenvectors of \(B\), with nonzero eigenvalues \(\lambda_i\), then their graph vectors are orthogonal and \[\|\gamma(v_i)\|^2=1+\lambda_i^{-2}.\] It follows that the self-adjoint operator representing \(Q\) on \(\Gamma\) has eigenvalues \[\mu_i=\frac{\lambda_i}{1+\lambda_i^2}.\] All have absolute value at most one. Let \(C_P\) be the fixed constant supplied by Proposition 21. Apart from \(t_B\le N\ell^{-P}\) eigenvalues, that proposition gives \(|\lambda_i|>\sqrt N\,\ell^{-C_P}\). For these indices, \[|\mu_i|\le|\lambda_i|^{-1}\le a_N,\qquad a_N=\frac{\ell^{C_P}}{\sqrt N}<1\] for sufficiently large \(N\).

The determinant of a compression to any \(s\)-dimensional subspace is bounded in absolute value by the product of the largest \(s\) singular values of the whole operator. Indeed, if \(w\) is the unit exterior product of an orthonormal basis of that subspace and \(T_Q\) is the operator of \(Q\), the determinant is \(\langle w,(\bigwedge^s T_Q)w\rangle\), whose absolute value is at most \(\|\bigwedge^s T_Q\|\). Apply this to the subspace \(S\). Using the spectral bounds above, including the rank-zero convention, gives \[ \left|\det_{\mathrm{orth}}(Q|_S)\right| \le a_N^{(s-t_B)_+}\le a_N^{s-t_B}. \tag{27}\] The last inequality is also valid for \(s<t_B\), since \(a_N<1\). Comparing Equations (26) and (27) and taking logarithms yields \[(s-t_B)\left(\frac12\log N-C_P\log\ell\right) \le NJ_B\log N+2C_0N\ell.\] The coefficient on the left is positive for large \(N\). Together with Equation (25) and \(t_B\le N\ell^{-P}\), this implies \[\frac rN \le \frac{J_B+2C_0\ell/\log N} {1/2-C_P\log\ell/\log N} +2\ell^{-P} =2J_B+O(\ell^{-P}).\] For the last equality, use \(J_B\le1/2\), the fixedness of \(C_0,C_P,P\), and \((\ell+\log\ell)/\log N=o(\ell^{-P})\).

Finally combine Equations (22), (23), and (19). They give \[\begin{split} \frac{\log_2|\mathcal S(B)|}{N} &\le \beta\sum_{\substack{p,e\\k_B(p,e)=2}}\nu_p +2J_B+O(\ell^{-P})+O(N^{-1/5}\log N)\\ &=\Psi(B)+O(\ell^{-P})+O(N^{-1/5}\log N). \end{split}\] The equality follows from Equations (4) and (20). Because \(P>A+2\) is fixed, the sum of the two error terms is at most \(\ell^{-A}\) for all sufficiently large \(N\). This proves the claimed estimate on the chosen typical event and completes the proof. ◻

Proof. Quotienting by \(p^t\) and by \(v\) commutes: \[H/p^tH\cong (G/p^tG)/\langle v+p^tG\rangle.\] Taking orders proves Equation (35).

Write \(G_p=\bigoplus_i\mathbb Z/p^{b_i}\mathbb Z\). For the \(i\)-th coordinate of the \(p\)-primary component of \(v\), let \(r_i\) be its \(p\)-adic valuation capped at \(b_i\); in particular \(r_i=b_i\) for a zero coordinate. The order of that coordinate in \(G_p/p^tG_p\) is \(p^{(\min\{b_i,t\}-r_i)_+}\), where \(x_+=\max\{x,0\}\). The order of an element in a direct sum of \(p\)-groups is the largest of its coordinate orders, so \[ u_t=\max_i(\min\{b_i,t\}-r_i)_+, \tag{37}\] with maximum zero when \(G_p\) is trivial. Each function under this maximum is nondecreasing in \(t\) and increases by at most one at a step. The same is therefore true of \(u_t\); since it is integer valued, its increments belong to \(\{0,1\}\). Subtracting Equation (35) at \(t=e-1\) from the equation at \(t=e\) proves Equation (36).

On a plateau of height \(k\), the heights in \(H\) are either \(k\) or \(k-1\). They are nonincreasing as \(e\) increases, by their definition from invariant factors. Thus a height \(k-1\) cannot be followed on the plateau by height \(k\). The retained layers are exactly those of height \(k\), proving the prefix assertion. ◻

Proof. For each prime choose, once for the given group \(H\), cyclic coordinates \[H_p=\bigoplus_i\mathbb Z/p^{b_i}\mathbb Z.\] Put \[a_{p,i}=\#\{e:(p,e)\in E,\ e\le b_i\},\qquad T_E=\bigoplus_{p,i}p^{a_{p,i}}(\mathbb Z/p^{b_i}\mathbb Z)\subseteq H, \qquad K_E=\pi^{-1}(T_E).\] Here \(0\le a_{p,i}\le b_i\), and the subgroup in the \((p,i)\) coordinate consists of the classes divisible by \(p^{a_{p,i}}\). The lattice \(K_E\) contains \(C\mathbb Z^m\). Its index is \[[\mathbb Z^m:K_E]=[H:T_E] =\prod_{p,i}p^{a_{p,i}} =\prod_{(p,e)\in E}p^{k_H(p,e)} =N^{Nq(E)},\] where the penultimate equality counts a selected layer once for each cyclic factor reaching it. This proves all assertions about the lattice and its index.

It remains to prove the implication. Fix \(p,i\), and let \(r_i\) be the capped valuation of the \(i\)-th coordinate of \(\pi(v)\), as in the proof of Lemma 28. Equation (37) at \(t=b_i\) gives \(u_{b_i}\ge b_i-r_i\). All the first \(b_i\) layers are positive, and Equation (36) shows that the number among them that are retained is \[\sum_{e=1}^{b_i}\bigl(1-(u_e-u_{e-1})\bigr)=b_i-u_{b_i}.\] If every layer in \(E\) is retained, then \[a_{p,i}\le b_i-u_{b_i}\le r_i.\] Thus the coordinate of \(\pi(v)\) is divisible by \(p^{a_{p,i}}\). This holds in every primary coordinate, so \(\pi(v)\in T_E\) and \(v\in K_E\), as required. ◻

Proof. The assertion is immediate for \(t=0\). Fix \(t\ge1\), put \(R_t=\mathbb Z/p^t\mathbb Z\), and reduce the blocks of \(B\) modulo \(p^t\), writing them as \(C_t,V_t,D_t\). Let \[X=R_t^m,\qquad Y=R_t^h,\qquad L=\ker(C_t:X\to X),\qquad J=\mathop{\mathrm{im}}(C_t:X\to X).\] The presentation of the cokernel gives \[X/J\cong \mathbb Z^m/(C\mathbb Z^m+p^t\mathbb Z^m)\cong G_C/p^tG_C.\] Since \(C_t\) is an endomorphism of the finite group \(X\), its kernel and cokernel have the same order. Hence \[ |L|=|X/J|=p^{F_C(p,t)}. \tag{42}\]

Define \[\alpha:Y\longrightarrow X/J,\qquad \alpha(y)=V_ty+J.\] The image is the subgroup generated by the column classes in \(G_C/p^tG_C\). Quotienting by that subgroup gives \(H_h/p^tH_h\), so Equation (40) gives \[|\mathop{\mathrm{im}}\alpha|=p^{U_t},\qquad |\ker\alpha|=p^{ht-U_t}.\] For a kernel vector \((x,y)\in X\oplus Y\) of \(B\) modulo \(p^t\), the first block equation is \[ C_tx+V_ty=0. \tag{43}\] It requires \(y\in\ker\alpha\). For each such \(y\), its solutions in \(x\) form a coset \(x_0+L\).

Consider the map \[\gamma:L\longrightarrow Y,\qquad \gamma(z)=V_t^{\mathsf T}z.\] We claim that \(|\mathop{\mathrm{im}}\gamma|=p^{U_t}\). Equip \(X\) and \(Y\) with their standard character pairings, for example \[\langle x,z\rangle_X =\exp\!\left(\frac{2\pi i}{p^t}x^{\mathsf T}z\right).\] These pairings are perfect: a nonzero coordinate is detected by pairing with its standard basis vector. For a subgroup \(M\) of either module \(A\), write \(M^\perp\) for its annihilator. Character orthogonality gives \[ |M|\,|M^\perp| =\sum_{a\in A}\sum_{z\in M}\langle a,z\rangle_A =|A|. \tag{44}\] For the first equality, the sum over \(M\) is \(|M|\) on its annihilator and zero elsewhere. For the second, reverse the sums: by perfectness the sum over \(A\) vanishes for every \(z\ne0\), and the term \(z=0\) equals \(|A|\).

Symmetry of \(C_t\) gives \(J\subseteq L^\perp\), since \(\langle C_tx,z\rangle_X=\langle x,C_tz\rangle_X=1\) for \(z\in L\). Both groups have order \(|X|/|L|\), the former by the kernel-image formula and the latter by Equation (44). Therefore \(L^\perp=J\). It follows that \[\begin{align*} (\mathop{\mathrm{im}}\gamma)^\perp &=\{y\in Y:\langle y,V_t^{\mathsf T}z\rangle_Y=1 \text{ for every }z\in L\}\\ &=\{y\in Y:\langle V_ty,z\rangle_X=1 \text{ for every }z\in L\}\\ &=\{y\in Y:V_ty\in J\}=\ker\alpha. \end{align*}\] Equation (44) in \(Y\) now gives \[|\mathop{\mathrm{im}}\gamma|=\frac{|Y|}{|\ker\alpha|}=p^{U_t}, \qquad |\ker\gamma|=\frac{|L|}{|\mathop{\mathrm{im}}\gamma|} =p^{F_C(p,t)-U_t}.\]

For a fixed \(y\in\ker\alpha\) and \(x=x_0+z\) from Equation (43), the second block equation is \[\gamma(z)=-V_t^{\mathsf T}x_0-D_ty.\] It has either no solutions or one coset of \(\ker\gamma\). There are at most \(p^{ht-U_t}\) choices for \(y\), and for each at most \(p^{F_C(p,t)-U_t}\) choices for \(z\). Consequently \[|\ker(B\bmod p^t)|\le p^{F_C(p,t)+ht-2U_t}.\] As for \(C_t\), the kernel of the square endomorphism \(B\bmod p^t\) has the same order as its cokernel. That cokernel is \(G_B/p^tG_B\), of order \(p^{F_B(p,t)}\). Taking logarithms proves Equation (41). ◻

Proof. The case \(j=0\) is immediate. For \(j\ge1\), encode the center \(y\) and a choice of \(j\) pivot coordinates on which the differences remain independent. These choices cost \(O(N\log N)\) bits. At the pivots, each difference entry has two possible values once \(y\) is known, so all pivot entries cost \(j^2\) bits.

Add the other coordinates in a fixed order. Suppose the current projected span is \(V\subset\mathbb R^h\), and put \(L_V=V\cap\mathbb Z^h\). The next projected span is the graph of a rational functional \(x\mapsto\langle v,x\rangle\) on \(V\), represented by \(v\in V\). Put \[a=\min\{b\in\mathbb Z_{>0}:bv\in L_V^*\}.\] The image of \(L_V\) under this functional modulo \(\mathbb Z\) has order \(a\). Hence the projection of the integer lattice in the graph has index \(a\) in \(L_V\). The volume factor of the graph map on \(V\) is \(\sqrt{1+\|v\|^2}\), and therefore \[ \frac{H(\operatorname{graph}(v))}{H(V)} =a\sqrt{1+\|v\|^2}. \tag{48}\] All these ratios are at least one. The initial projected space is \(\mathbb R^j\), of height one, and the final one is \(W\). Thus every intermediate height is at most \(\exp(N\ell^C)\), and a ratio exceeding \(N^{1/10}\) occurs at most \(O(N\ell^C/\log N)\) times. Mark those coordinates and encode their \(j\) difference entries directly. Their total cost is \(O(N^2\ell^C/\log N)\) bits.

At any other coordinate, \[a\le N^{1/10},\qquad \|av\|\le N^{1/10}.\] We count possible \(av\) in \(\Lambda=L_V^*\). Lemma 11, applied to \(V\subset\mathbb R^h\), gives \(\det M\ge H(V)^{-1}\) for every sublattice \(M\subset\Lambda\).

Apply Lemma 14 to \(\Lambda\) with \(T=N^{-1/10}\), choosing a minimizing sublattice as a function of the known \(V\). If its rank is \(r_0\), comparison with the zero lattice and the preceding determinant bound give \[H(V)^{-1}\le T^{r_0},\qquad r_0\le \frac{10N\ell^C}{\log N}.\] Every sublattice of the quotient has determinant at least \(T\) to its rank. By Lemma 13, the number of quotient images of vectors of norm at most \(N^{1/10}\) is \[2^{O(N^{2/5}\log^2N)}.\] Here the quotient has rank at most \(N\), and the bound also covers rank zero.

Encode \(a\), costing \(O(\log N)\) bits, and the quotient image of \(av\). In a fixed fiber, \(v\) varies in an affine space of dimension at most \(r_0\). Evaluation on the already known \(j\) independent projected differences is injective on \(V\), and the evaluations are the \(j\) entries of the new difference column. Each entry has two possible values, determined by the corresponding coordinate of \(y\). An affine space of dimension \(r_0\) meets such a cube in at most \(2^{r_0}\) points, by projection onto \(r_0\) suitable coordinates. This bounds the fiber cost by \(r_0\) bits.

Summing over at most \(N\) coordinates, including the pivot, center, and marking costs, bounds the logarithm of the number of tuples by \[j^2+O\!\left( \frac{N^2\ell^C}{\log N}+N^{7/5}\log^2N+N\log N \right).\] For fixed \(C,C'\), the error is \(o(N^2\ell^{-C'})\), uniformly in \(j\) and \(m\), as required. ◻

Proof. The robust-height bound in Lemma 16, with the fixed parameter \(\rho=\ell^{-3D_0}\), gives \[H(W_i)\le\exp(O(N\ell)).\] The integer lattice sum of \(W_i\cap\mathbb Z^m\) is contained in \(W\cap\mathbb Z^m\). The volume inequality for this sum and saturation give \[H(W)\le\prod_i H(W_i) \le\exp(O(N\ell/\eta)).\] Choose a fixed \(D_1>D_0+1\). For sufficiently large \(N\), this is at most \(\exp(N\ell^{D_1})\). We impose Proposition 18 at this height and at a fixed precision strong enough that its rank error is at most \(\eta^5N\). We also impose Proposition 20. Their intersection is typical. All counting below takes place within this intersection.

For a fixed list of dimensions, Lemma 32 counts centers and ordered bases of differences for the pieces with total logarithmic cost \[ N^2\sum_i t_i^2+o(N^2\eta^4). \tag{50}\] Indeed, use that Lemma with a fixed \(C'\) larger than \(5D_0\) and sum its errors over at most \(3/\eta\) pieces. The height exponent there can be chosen fixed and large enough for all the \(W_i\).

For each individual witness, fix a center in each \(S_i\). At every stage of choosing an ordered basis of differences, the affine span of the center and the points already chosen is a proper affine subspace of \(\mathop{\mathrm{aff}}S_i\). Robustness bounds the fraction of \(S_i\) in that subspace by \(2^{-\rho}\). Consequently the number of choices of an ordered basis for this piece is at least \[\bigl((1-2^{-\rho})\,2^{\alpha_iN}\bigr)^{t_iN}.\] The choices for different pieces form distinct basis lists. As \(t\le m/N\le1\), their total logarithm is at least \[ N^2\sum_i t_i\alpha_i -O\bigl(N\log(1/\rho)\bigr) =N^2\sum_i t_i\alpha_i-o(N^2\eta^4). \tag{51}\]

Fix basis-list data, so in particular \(W\) is known. For a witnessed matrix choose a coordinate set \(Y_0\) of size \(tN\) containing \(D\). The second rank assertion of Proposition 18 shows that the columns on \([m]\setminus Y_0\), projected off \(W\), have rank at least \(m-tN-\eta^5N\). Choose an independent collection there, and use nonsingularity of \(B\) to complete it to a basis of the quotient \(\mathbb R^m/W\) using columns of \(B\). Let \(P\) be the resulting set of \(m-tN\) indices and \(Y=[m]\setminus P\). Then \[|D\cap P|\le\eta^5N.\] Encode \(D\) and \(P\), at cost \(O(N)\) bits, and reveal the columns on \(P\). If \(T_m=m(m+1)/2\) is the total number of independent bits of \(B\), these columns cost \[T_m-\binom{tN+1}{2}\] bits, using symmetry.

The revealed columns and the basis differences are \(m\) independent integer vectors: the differences form a basis of \(W\), and the revealed columns project to a basis off \(W\). Let \(L\) be their integer span. It is known from the encoded data, satisfies \(L\subset K\), and has full rank. Each generating vector has norm at most \(\sqrt N\), so Hadamard’s inequality gives \[|\mathbb Z^m/L|\le N^{m/2}\le N^{N/2}.\] We next enumerate the possible \(K\) containing this known \(L\). Let \(r_N=\lceil N^{3/5}\rceil\). For every prime \(p\), \[\dim_{\mathbb F_p}\bigl((\mathbb Z^m/K)/p(\mathbb Z^m/K)\bigr) \le\dim_{\mathbb F_p}(G_B/pG_B) =\mathop{\mathrm{corank}}_{\mathbb F_p}B\le r_N\] by Proposition 20. The minimum number of generators of a finite abelian group is the maximum of these dimensions over its primes, as follows from its invariant factors. Thus \(\mathbb Z^m/K\), and also its character dual, can be generated by at most \(r_N\) elements.

Put \(H=\mathbb Z^m/L\). The annihilator of \(K/L\) identifies \((\mathbb Z^m/K)^\vee\) with a subgroup of \(H^\vee=\mathop{\mathrm{Hom}}(H,\mathbb Q/\mathbb Z)\); by finite duality this subgroup determines \(K\). Every subgroup with at most \(r_N\) generators is generated by some ordered \(r_N\)-tuple in \(H^\vee\), padding with zero elements if necessary. The number of possible \(K\) is therefore at most \(|H|^{r_N}\). Its logarithm is \[ O(N^{8/5}\log N)=o(N^2\eta^4). \tag{52}\] This candidate list is formed after the basis lists and revealed columns fix \(L\), before the remaining matrix block is encoded. It may include lattices incompatible with every completion. The prime-corank condition is used only to ensure that each actual witnessed \(K\) appears in the list.

Write \(D'=D\cap Y\), \(y=|Y|=tN\), and \(d'=|D'|\). We have \(d'\ge(x-\eta^5)N\) and \(M_K(D')\le M_K(D)\le2^{\eta N}\). In the remaining \(Y\)-block, first encode the symmetric bits on \(Y\setminus D'\), at cost \(\binom{y-d'+1}{2}\). For a row indexed by \(Y\setminus D'\), all entries outside \(D'\) are now known. The full row belongs to \(K\), since \(B\) is symmetric and each column belongs to \(B\mathbb Z^m\). Its entries on \(D'\) therefore lie in a fixed coset of \(K\) and have at most \(M_K(D')\) possibilities. This encodes the cross block at cost at most \(\eta N(y-d')\). For the final \(D'\)-block, the same bound applies to each of its \(d'\) rows. Ignoring symmetry within that block only enlarges the count, so its cost is at most \(\eta Nd'\). Relative to an unrestricted symmetric \(Y\)-block the saving is at least \[\begin{split} \binom{y+1}{2}-\binom{y-d'+1}{2}-\eta Ny &=yd'-\frac{(d')^2}{2}+\frac{d'}2-\eta Ny\\ &\ge N^2\left(xt-\frac{x^2}{2}-\eta t -O(\eta^5+1/N)\right). \end{split}\]

It remains to compare the upper count with the multiplicity of witnesses. Group violating witnesses by \(h\), the integers \(t_iN\) and \(xN\), and the integers \[a_i=\lfloor\log_2|S_i|\rfloor,\qquad \bar\alpha_i=a_i/N.\] There are at most \(2^{O(\eta^{-1}\log N)}\) groups. Fix one group, and let \(\mathcal E\) be the set of matrices in the imposed typical intersection that have a violating witness in this group. For each \(B\in\mathcal E\), select one such witness and count the distinct pairs consisting of \(B\) and the basis lists supplied by that witness. Equation (51) gives a lower bound of \[|\mathcal E|\, 2^{N^2\sum_i t_i\bar\alpha_i-o(N^2\eta^4)}\] on the number of pairs. On the other hand, Equations (50) and (52), together with the matrix saving, give the upper bound \[2^{T_m+ N^2\left(\sum_i t_i^2-xt+x^2/2+\eta t\right) +o(N^2\eta^4)}.\] The enumeration may count a pair more than once if it has several compatible choices of \(D,P,K\); this preserves the upper bound. In particular, the lower bound selects just one witness per matrix, while the upper bound includes the union over all \(K\).

Since \(0\le\alpha_i-\bar\alpha_i<1/N\) and \(t\le1\), violation of Equation (49) implies \[\sum_i t_i(t_i-\bar\alpha_i)-xt+x^2/2+\eta t <-\eta^3+\frac1N.\] All binary matrices have probability \(2^{-T_m}\). Dividing the pair bounds therefore gives \[\Pr(\mathbf B_m\in\mathcal E) \le 2^{-N^2\eta^3+o(N^2\eta^4)}.\] The group count and all omitted costs are absorbed in this error. Since \(N\eta^3\to\infty\), the total probability of a violation is \(2^{-\omega(N)}\), including the exceptional probabilities of the imposed rank and corank properties. This proves the assertion, including its simultaneity over the lattices, lists, and coordinate sets. ◻

Proof of Proposition 31. Fix \(A>0\). Choose a fixed \(D_0>2A\), and put \(\eta=\ell^{-D_0}\), \(\rho=\eta^3\). Work on the typical event in Proposition 33, and fix an arbitrary \(K\) with \(B\mathbb Z^m\subseteq K\subseteq\mathbb Z^m\).

Apply Lemma 14 to \(K\) with \(T=(\log N)^4\), and let \(K_0\) be a minimizing saturated sublattice. Put \(F=\mathop{\mathrm{span}}K_0\) and \[d=\frac{m-\dim F}{N},\qquad f=1-d=\frac{\dim F+N-m}{N}.\] The projected quotient \(K/K_0\) has rank \(dN\) and all its sublattices have determinant at least \(T\) to their rank. Moreover \(\det K_0\le T^{\dim F}\), by comparison with the zero lattice. The projections of the columns of \(B\) span \(F^\perp\), and each has norm at most \(\sqrt N\). Choosing \(dN\) independent projections and using that their integer span is a sublattice of \(K/K_0\) gives \(\det(K/K_0)\le N^{dN/2}\). Hence \[ q=\frac{\log\det K}{N\log N} \le \frac d2+\frac{\dim F}{N}\frac{\log T}{\log N} \le \frac d2+\frac{4\ell}{\log N}. \tag{53}\]

Consider any nonempty subset \(S\) of a coset of \(K\) in the cube, and base its differences at one point of \(S\). Their projections off \(F\) belong to \(K/K_0\) and have norm at most \(\sqrt N\). Lemma 13 gives at most \[2^{O(N/\log^6N)}\] distinct projections. Restrict to a largest projection fiber and then apply Lemma 15 with parameter \(\rho=\eta^3\). For sufficiently large \(N\), these two operations lose at most \(2\eta^3N\) bits of logarithmic size. Thus, if \(|S|=2^{aN}\), they give a \(\rho\)-robust subset \(S'\) with \[ |S'|\ge2^{(a-2\eta^3)N}, \qquad \mathop{\mathrm{span}}(S'-S')\subset F. \tag{54}\] If \(S\) is supported on a coordinate set, the same is true of its differences after these operations.

Choose a set \(P_F\) of \(\dim F\) pivot coordinates for \(F\), so coordinate projection onto \(P_F\) is injective on \(F\), and put \(J_0=[m]\setminus P_F\). Then \(|J_0|=dN\) and a vector supported on \(J_0\) belongs to \(F\) only if it is zero. Distinct bit vectors supported on \(J_0\) therefore have distinct projections off \(F\): equal projections would give a difference in \(F\). Applying the preceding projection count to a coset intersection on \(J_0\) gives \[ M_K(J_0)\le2^{O(N/\log^6N)}\le2^{\eta N}. \tag{55}\]

Write \(M_K=2^{\alpha N}\). We have \(0\le\alpha\le1\). If \(\alpha<10\eta\), the conclusion follows for sufficiently large \(N\), since \(1-c(q)\ge0\) and \(10\eta\le\ell^{-A}\). We may therefore assume \(\alpha\ge10\eta\).

Apply Equation (54) to a full-coordinate coset attaining \(M_K\). Denote the resulting robust subset by \(S_*\), put \(W_*=\mathop{\mathrm{span}}(S_*-S_*)\), and write \[|S_*|=2^{\alpha_*N},\qquad v=\frac{\dim W_*}{N}.\] An affine space of dimension \(\dim W_*\) contains at most \(2^{\dim W_*}\) cube points, by coordinate projection. Consequently \[ \alpha_*\ge\alpha-2\eta^3,\qquad \alpha-2\eta^3\le v\le\frac{\dim F}{N}\le f. \tag{56}\] The last inequality uses \(m\le N\).

We construct one coordinate set \(D\) with small \(M_K(D)\) and use it in two applications of Proposition 33. A list of robust sets will force \(D\) to be large; applying the estimate to the full-coordinate set \(S_*\) then restricts how large \(\alpha\) can be for that same \(D\).

Initially all coordinates of \(P_F\) are available. At step \(i\), choose, among the available coordinates, a set \(A_i\) of minimum cardinality such that \[M_K(J_0\cup A_i)>2^{\eta N}.\] For a coset attaining \(M_K(J_0\cup A_i)\), apply Equation (54). It gives a robust subset \(S_i\) whose difference span satisfies \[W_i\subset F\cap E_{J_0\cup A_i},\qquad \alpha_i=\frac{\log_2|S_i|}{N}\ge\eta-2\eta^3,\qquad t_i=\frac{\dim W_i}{N}\ge\alpha_i.\] Because projection of \(F\) onto \(P_F\) is injective and \(W_i\) vanishes on \(P_F\setminus A_i\), we have \(t_iN\le|A_i|\). Choose \(t_iN\) pivot coordinates \(H_i\subset A_i\) on which projection of \(W_i\) is injective, and declare those coordinates unavailable. Stop when \(t=\sum_i t_i\ge\alpha-2\eta\).

The required set \(A_i\) exists before the stopping condition is met. Indeed, the coordinates already declared unavailable number \(tN\). In a full coset attaining \(M_K\), fix their bit values to a most frequent pattern. At least \(2^{(\alpha-t)N}>2^{2\eta N}\) points remain. Subtracting the fixed pattern on those coordinates translates the coset and leaves bit vectors supported on \(J_0\) and the available coordinates. Hence that coordinate set has \(M_K>2^{\eta N}\). Equation (55) also shows that each \(A_i\) is nonempty.

The spaces \(W_i\) form a direct sum. In a relation \(\sum_i w_i=0\) with \(w_i\in W_i\), the later terms vanish on the pivots \(H_1\); injectivity on \(W_1\) gives \(w_1=0\), and the same argument successively gives every \(w_i=0\). Thus \(t\le\dim F/N\le1\). Each increment is at least \(\eta-2\eta^3\), so there are fewer than \(3/\eta\) steps for sufficiently large \(N\). Together with the existence just proved, this ensures that the stopping condition is reached. The family of available subsets only shrinks from one step to the next. Since each \(A_i\) has minimum cardinality, the numbers \(|A_i|\) do not decrease. If the last one has size \(sN\), then \[ t\ge\alpha-2\eta,\qquad t_i\le |A_i|/N\le s \quad\text{for every }i. \tag{57}\]

Remove one coordinate from the last \(A_i\) and include all of \(J_0\). The resulting set \(D\) satisfies \[ |D|=(d+s)N-1,\qquad M_K(D)\le2^{\eta N}, \tag{58}\] by the minimum cardinality of that \(A_i\). For \(x\ge0\), \(t>0\), define \[e(x,t)= \begin{cases} x-x^2/(2t),&0\le x\le t,\\ t/2,&x\ge t. \end{cases}\] This function is nondecreasing in both variables. Its rate of change in \(x\) is between zero and one, and its rate of change in \(t\) is between zero and \(1/2\). These assertions follow from \[\partial_x e=1-x/t,\quad \partial_t e=x^2/(2t^2)\quad(x<t), \qquad \partial_x e=0,\quad \partial_t e=1/2\quad(x>t),\] and continuity at \(x=t\).

If necessary, truncate \(D\) to a subset of size \(tN\). Monotonicity of \(M_K(D)\) preserves its bound, so Proposition 33 applied to the constructed list gives \[\begin{split} e(d+s,t) &\le \frac1t\sum_i t_i(t_i-\alpha_i) +\eta+\frac{\eta^3}{t}+\frac1N\\ &\le s+O(\eta). \end{split}\] The \(1/N\) accounts for the coordinate removed in Equation (58). The last inequality uses \(\alpha_i\ge0\), \(t_i\le s\), and \(t\ge\alpha-2\eta\ge8\eta\). Replacing \(t\) by \(\alpha\) keeps this bound: if \(t\ge\alpha\), use monotonicity in the second variable; if \(t<\alpha\), use its \(1/2\)-Lipschitz bound and \(\alpha-t\le2\eta\). Thus \(e(d+s,\alpha)\le s+O(\eta)\).

Put \(h=d+s\). If \(h\le\alpha\), the last inequality gives \[d\le \frac{h^2}{2\alpha}+O(\eta).\] Since \(\alpha\le1\), it follows that \(h\ge\sqrt{2d\alpha}-O(\sqrt\eta)\). If \(h\ge\alpha\), it instead gives \(s\ge\alpha/2-O(\eta)\), and then \[h\ge d+\alpha/2-O(\eta) \ge\sqrt{2d\alpha}-O(\eta).\] We have proved \[ d+s\ge\sqrt{2d\alpha}-O(\sqrt\eta). \tag{59}\]

Use the same \(D\) again, now with the singleton list consisting of \(S_*\). Truncate \(D\) to size \(vN\) if necessary. From Proposition 33 and Equation (56), \[e(d+s,v) \le v-\alpha_*+\eta+\frac{\eta^3}{v}+\frac1N \le v-\alpha+O(\eta).\] Here \(v\ge\alpha-2\eta^3\ge9\eta\) for large \(N\). Since \(v\le f\) and the rate of change of \(e\) in its second argument is at most \(1/2\), this yields \[ e(d+s,f) \le e(d+s,v)+\frac{f-v}{2} \le f-\alpha+O(\eta). \tag{60}\]

We finish by solving the two coordinate inequalities. In the present case \(f\ge v>0\). If \(d\ge f\), then \(d+s\ge f\), so Equation (60) gives \[\alpha\le f/2+O(\eta)=fz(d/f)+O(\eta).\] Suppose instead that \(d\le f\). Monotonicity and the unit Lipschitz bound of \(e\) in its first argument, together with Equations (59) and (60), give \[ e(\sqrt{2d\alpha},f)\le f-\alpha+O(\sqrt\eta). \tag{61}\] Put \(u=d/f\in[0,1]\). Directly from Equation (45), \[2uz(u)\le1,\qquad 1-z(u)=\sqrt{2uz(u)}-uz(u).\] For completeness, if \(r=\sqrt{2u-u^2}\), then \((1-u)^2z(u)^2-2z(u)+1=0\), which gives the second identity after taking the nonnegative square root. The first is equivalent to \(2u\le1+r\); for \(u\le1/2\) it is immediate, and for \(u\ge1/2\) its square follows from \(r^2-(2u-1)^2=(1-u)(5u-1)\ge0\). These identities show that \(\alpha_0=fz(u)\) satisfies \[e(\sqrt{2d\alpha_0},f)=f-\alpha_0.\] The function \(a\mapsto a+e(\sqrt{2da},f)\) is nondecreasing and increases by at least the increase in \(a\). Therefore Equation (61) implies \(\alpha\le\alpha_0+O(\sqrt\eta)\). Both cases give \[\alpha\le fz(d/f)+O(\sqrt\eta) =1-c(d/2)+O(\sqrt\eta).\]

By Equation (53), monotonicity of \(c\), and Equation (47), \[c(q)\le c(d/2)+O\!\left(\sqrt{\frac{\ell}{\log N}}\right).\] It follows that \[\alpha\le 1-c(q)+O(\sqrt\eta) +O\!\left(\sqrt{\frac{\ell}{\log N}}\right).\] Because \(D_0>2A\) is fixed, both error terms are \(o(\ell^{-A})\). Increasing \(N\) makes their sum at most \(\ell^{-A}\), proving Equation (46). The argument was deterministic for every \(K\) on the single typical event of Proposition 33, so the conclusion is simultaneous in \(K\). ◻

Proof of Proposition 27. Fix the desired precision \(A>0\), and set \(A_1=A+2\). For width one, take a nonsingular starting matrix \(C\) in the typical set of Proposition 34 at precision \(A_1\) for \((w_1,w_2)=(1,2)\). Extend the marking rule above to singular outcomes by leaving all layers unmarked. Apply that Proposition with exposed information \(C\), starting quotient \(G_C\), and the subevent \(\{\det B\ne0\}\). The tested column is uniform conditional on \(C\), and the marks defined above are allowed to depend also on the new diagonal bit. The Proposition gives at most \(2^{N\ell^{-A_1}}\) classes. In each nonempty class \(\mathcal C\), choose an outcome \(B_{\mathcal C}\) maximizing \(\Psi(B)\) in that class. Such a representative exists because the outcome space is finite.

For this representative, form \(g,v_0,a,u,L,P,a_0\) and \(I\) as above. Lemma 36 supplies \(x\in[0,g]\) and \(y\in[0,a_0]\). These are admissible certificate target weights for the categories of minimum heights one and two, since \(a_0\le a\). The monotonicity of \(\mathcal E\) in its first argument gives \[\begin{aligned} c(x+2y)-\mathcal E(g,v_0,x)-\mathcal E(a,u,y) &\ge c(x+2y)-\mathcal E(g,v_0,x)-\mathcal E(a_0,u,y)\\ &\ge I. \end{aligned}\] Proposition 34, applied to this representative in the restricted outcome space, therefore yields \[\Pr(\mathcal C\mid C)\le2^{-N(I-\ell^{-A_1})}.\] Since \(\Psi(B_{\mathcal C})-\Psi(C)\le I\) by Equation (74), the contribution of this class satisfies \[\mathbb E\!\left[\mathbf 1_{\mathcal C}\,2^{N\Psi(B)}\mid C\right] \le 2^{N\Psi(B_{\mathcal C})}\Pr(\mathcal C\mid C) \le 2^{N(\Psi(C)+\ell^{-A_1})}.\] Summing over the classes proves \[\mathbb E\!\left[\mathbf 1_{\{\det B\ne0\}}\,2^{N\Psi(B)}\mid C\right] \le2^{N(\Psi(C)+2\ell^{-A_1})} \le2^{N(\Psi(C)+\ell^{-A})}\] for all sufficiently large \(N\).

For width two, take \(C\) also in the typical set of Proposition 7 at precision \(A_1\), and let \(m\) be its size. Conditional on \(C\), the two cross columns \(v_1,v_2\) are independent and uniform on \(\{0,1\}^m\). For the gate \(\mathcal G_2=\{v_1,v_2\in\mathcal S(C)\}\), that Proposition gives \[\Pr(\mathcal G_2\mid C) =2^{-2m}|\mathcal S(C)|^2 \le2^{-2m+2N(\Psi(C)+\ell^{-A_1})}.\] On nonsingular outcomes \(\Psi(B)\le1\). Consequently \[\begin{aligned} \mathbb E\!\left[\mathbf 1_{\{\det B\ne0\}}\mathbf 1_{\mathcal G_2} 2^{N\Psi(B)}\mid C\right] &\le2^{N-2m+2N(\Psi(C)+\ell^{-A_1})}\\ &\le2^{N(\Psi(C)+2(1-m/N)+2\ell^{-A_1})}\\ &\le2^{N(\Psi(C)+\ell^{-A})}. \end{aligned}\] The second line uses \(\Psi(C)\le1\), and the last uses \(1-m/N\le N^{-3/10}=o(\ell^{-A})\) together with \(A_1=A+2\). Intersecting the two typical sets proves both conditional assertions of Proposition 27, with arbitrary fixed precision and with the stated nonsingularity and gate indicators. ◻

Proof of Lemma 36. The second budget ensures \(x+2y\le1/2\) throughout the rectangle under consideration. Sections 8 and 9 show that \(c\) is nondecreasing and concave, while \(\mathcal E\) is continuous, nonnegative, convex in its target, homogeneous of degree one in all size variables, and nonincreasing in its first argument for fixed \(u,x\). Equation (45) further shows that \(c\) is differentiable on \((0,1/2)\), including the join at \(q=1/4\), has left derivative \(1\) at \(1/2\), and satisfies \(c(q)/q\to\infty\) as \(q\downarrow0\).

Supporting slope. For \(w,t\ge0\), put \[c^*(w)=\max_{0\le q\le1/2}\bigl(c(q)-wq\bigr),\qquad \mathcal F_t(s,u)=\max_{0\le x\le s} \bigl(tx-\mathcal E(s,u,x)\bigr).\] Write \(I=\beta g+(6-\beta)a_0-\beta u\). We will prove that, for every \(w\ge0\), \[ c^*(w)+\mathcal F_w(g,v_0)+\mathcal F_{2w}(a_0,u)\ge I. \tag{77}\] Here is a justification that this suffices. If \(g=a_0=0\), taking \(x=y=0\) proves Equation (76) immediately. Otherwise let \((x_*,y_*)\) maximize its left side on the compact rectangle, and put \(q_*=x_*+2y_*\). At zero the objective is zero. For a positive one of \(g,a_0\), its entropy cost is \(O(x)\) or \(O(y)\) near zero, by the derivative of \(H\) recorded in Section 9; the fact that \(c(q)/q\to\infty\) then shows that the maximum is positive. Thus \(q_*>0\).

Take \(w=c'(q_*)\) if \(q_*<1/2\), and the left derivative if \(q_*=1/2\). This is a nonnegative supporting slope, so \(c^*(w)=c(q_*)-wq_*\). Let \[K(x,y)=\mathcal E(g,v_0,x)+\mathcal E(a_0,u,y).\] We claim that \((x_*,y_*)\) maximizes \(w(x+2y)-K(x,y)\) on the same rectangle. If some \((x,y)\) gave a strictly larger value, take the point a fraction \(\theta\) along the segment from \((x_*,y_*)\) to \((x,y)\). Convexity of \(K\) and the one-sided differentiability of \(c\) in this feasible direction give, as \(\theta\downarrow0\), an increase in the original objective of at least \[\theta\bigl(w(x+2y-q_*)-K(x,y)+K(x_*,y_*)\bigr)+o(\theta)>0,\] a contradiction. The claimed maximum separates into its two coordinates. Hence the maximum of the left side of Equation (76) is exactly \(c^*(w)+\mathcal F_w(g,v_0)+\mathcal F_{2w}(a_0,u)\) at this supporting slope. Equation (77) proves the desired assertion.

Entropy minimum and criterion. We use the function \(H\) from Equation (65) to compute a lower bound for the two \(\mathcal F\) terms. For \(t>0\) set \[D(t)=-\log_2(1-2^{-t}).\] For \(r\ge0\), maximizing \(H(z,r)-tz\) over \(0\le z\le1\) at \(z=\min\{1,r/(2^t-1)\}\) gives \[\mathcal F_t(1,r)= \begin{cases} t-H(1,r)+D(t)r,&0\le r\le2^t-1,\\ 0,&r\ge2^t-1. \end{cases}\] For \(h\ge0\), the derivative on the first branch after adding \(hr\) is \(D(t)+h-\log_2(1+1/r)\). It is increasing in \(r\) and vanishes at \(r=(2^{D(t)+h}-1)^{-1}\le2^t-1\), with equality when \(h=0\). On the second branch \(hr\) is nondecreasing. Evaluation at this minimum therefore gives \[ \begin{aligned} \min_{r\ge0}\bigl(\mathcal F_t(1,r)+hr\bigr) &=t-D(D(t)+h)\\ &=\mathcal L(t,h):= \log_2\!\left(1+(2^t-1)(1-2^{-h})\right). \end{aligned} \tag{78}\] For \(t=0\), both the minimum and \(\mathcal L(0,h)\) are zero, so the equality between the first and last expressions holds there as well; the middle expression is used only for \(t>0\).

For a given \(w\), it is enough to find \(\lambda,\mu\ge0\) such that \[ \begin{aligned} 2\lambda+\mu+\mathcal L(w,\mu)&\ge\beta,\\ 3\lambda+2\mu+ \mathcal L(2w,\beta+\lambda+2\mu)&\ge6-\beta,\\ (\lambda+\mu)/2&\le c^*(w). \end{aligned} \tag{79}\] Indeed, homogeneity and Equation (78) imply \[\begin{aligned} \mathcal F_w(g,v_0)+\mu v_0&\ge g\,\mathcal L(w,\mu),\\ \mathcal F_{2w}(a_0,u)+(\beta+\lambda+2\mu)u &\ge a_0\,\mathcal L(2w,\beta+\lambda+2\mu). \end{aligned}\] These remain true when \(g=0\) or \(a_0=0\). Using the first two inequalities in Equation (79) now gives \[\mathcal F_w(g,v_0)+\mathcal F_{2w}(a_0,u) +\lambda(2g+3a_0+u)+\mu(g+v_0+2a_0+2u)\ge I.\] The two budgets and the third inequality in Equation (79) yield Equation (77).

Exact verification. We verify Equation (79) with three explicit choices. The function \(D\) is decreasing, and, for \(h>0\), \[ \mathcal L(t,h)\ge t-D(h). \tag{80}\] This follows by dropping the positive term \(2^{-h}\) from \(2^{\mathcal L(t,h)}=2^t(1-2^{-h})+2^{-h}\). Only one numerical estimate for \(D\) is needed: \[ D(21/10)<2/5. \tag{81}\] Indeed, if \(v=2^{-1/10}\), then \(v<14/15\) because \(15^{10}<2\cdot14^{10}\). Thus \[2^{-21/10}+2^{-2/5} =\frac v4+v^4 <\frac7{30}+\left(\frac{14}{15}\right)^4 =\frac{100457}{101250}<1,\] which is equivalent to Equation (81).

We will use the support bounds \[ 2c^*(w)\ge \max\left\{2-w,\ \frac32-\frac w2,\ \frac{23}{24}-\frac w6,\ \frac2{w+2}\right\}. \tag{82}\] The first three follow by testing \(q=1/2,1/4,1/12\) in the definition of \(c^*\). The first two values are \(c(1/2)=1\) and \(c(1/4)=3/4\). At \(q=1/12\), the argument of \(z\) is \(1/5\), the square root in its definition is \(3/5\), and \(c(1/12)=1-(5/6)(5/8)=23/48\). For the last bound, when \(0\le q\le1/4\), put \[r=\frac{2\sqrt{q(1-3q)}}{1-2q}.\] Then \[r^2-4q=\frac{4q^2(1-4q)}{(1-2q)^2}\ge0.\] The expression \((r+2q)/(1+r)\) increases in \(r\), so \[c(q)=\frac{r+2q}{1+r} \ge\frac{2\sqrt q+2q}{1+2\sqrt q} \ge2\sqrt q-2q.\] The difference in the last inequality is \(4q\sqrt q/(1+2\sqrt q)\). Testing \(q=(w+2)^{-2}\le1/4\) now gives \[2c^*(w)\ge2\bigl(c(q)-wq\bigr) \ge2\left(\frac2{w+2}-\frac{w+2}{(w+2)^2}\right) =\frac2{w+2},\] including at \(w=0\).

One global estimate handles the middle range: \[ \mathcal L(w,1/4)>\frac{w-1}{2}\qquad(w\ge0). \tag{83}\] To prove it, let \(b=2^{-1/4}\). The integer inequality \(20^4<2\cdot17^4\) gives \(1/2<b<17/20\). Since \(b(1-b)\) decreases for \(b\ge1/2\), \[b(1-b)>\frac{17}{20}\frac3{20} =\frac{51}{400}>\frac18.\] Consequently the arithmetic–geometric mean inequality gives \[2^{\mathcal L(w,1/4)}=b+(1-b)2^w \ge2\sqrt{b(1-b)2^w}>2^{(w-1)/2},\] which proves Equation (83).

We use the following choices, writing \(h=\beta+\lambda+2\mu\): \[(\lambda,\mu)= \begin{cases} \displaystyle\left(\max\left\{2-w,\frac32-\frac w2\right\},0\right), &\displaystyle 0\le w\le\frac85,\\[6pt] \displaystyle\left(\frac{17}{24}-\frac w6,\frac14\right), &\displaystyle \frac85\le w\le3,\\[6pt] (0,3\,2^{-w}),&w\ge3. \end{cases}\] Either choice works at a shared endpoint.

For \(0\le w\le8/5\), put \(S=\max\{2-w,3/2-w/2\}\), so \(\lambda=S\) and \(\mu=0\). Then \(S\ge7/10\), so \(h\ge21/10\) and \[2\lambda+\mathcal L(w,0)=2S\ge7/5.\] By Equations (80) and (81), the second multiplier expression exceeds \[3S+2w-\frac25 =\max\left\{\frac{28}{5}-w,\frac{41}{10}+\frac w2\right\} \ge\frac{23}{5}.\] For the last inequality, use the first term when \(w\le1\) and the second when \(w\ge1\). The choices are nonnegative, and the third multiplier inequality, in the equivalent form \(\lambda+\mu\le2c^*(w)\), follows directly from Equation (82).

For \(8/5\le w\le3\), take \(\lambda=17/24-w/6\) and \(\mu=1/4\). These are nonnegative, and \[h\ge\frac75+\frac5{24}+\frac12 =\frac{253}{120}>\frac{21}{10}.\] By Equation (83), the first multiplier expression exceeds \[2\lambda+\mu+\frac{w-1}{2} =\frac76+\frac w6 \ge\frac{43}{30}>\frac75.\] By Equations (80) and (81), the second expression exceeds \[3\lambda+2\mu+2w-\frac25 =\frac{89}{40}+\frac32w \ge\frac{37}{8}>\frac{23}{5}.\] Finally, \(\lambda+\mu=23/24-w/6\), so Equation (82) gives the third inequality.

For \(w\ge3\), take \(\lambda=0\) and \(\mu=3\,2^{-w}\), which are nonnegative. The elementary bound \[\log2=2\int_0^{1/3}\frac{dt}{1-t^2}>\frac23\] and \(2^\mu-1\ge\mu\log2\) give \[2^{\mu+\mathcal L(w,\mu)} =1+2^w(2^\mu-1) \ge1+3\log2>3>2^{7/5}.\] The last inequality follows from \(3^5>2^7\). This proves the first multiplier inequality. Here \(h\ge\beta>1\), so \(D(h)<D(1)=1\). Equation (80) therefore shows that the second expression is greater than \[2w-1\ge5>\frac{23}{5}.\] For the third inequality, \(3\,2^{-3}=3/8<2/5\), and \(2^w/(w+2)\) increases for \(w\ge3\), since its logarithmic derivative is \[\log2-\frac1{w+2}>\frac23-\frac15>0.\] It follows that \(\mu\le2/(w+2)\le2c^*(w)\) by Equation (82). This verifies Equation (79) for every \(w\ge0\), and hence proves Equation (76). ◻