The sharp exponential rate of singularity for symmetric Bernoulli matrices

Proof. Put \epsilon=(A_n)_{11}, multiply A_n by \epsilon, and then apply the diagonal congruence with diagonal

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

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 2.2 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

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 2.3.□

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

Thus z\in\mathcal S(B). For any fixed deleted index, conditional on B, the pair (z,a) is uniform on \bits^{N-1}\times\bits. For each z\in\mathcal S(B), the displayed equality fixes a. The probability for that index is therefore 2^{-N}\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

Lemma 3.1 now gives

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\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\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 3.1 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

An integer basis matrix for \Lambda_U gives a rational basis for its dual by inverting its Gram matrix. Thus \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

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 3.4. 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^{\rank L_0}.

For a sublattice M\subset L/L_0, lift it to \widetilde M as in Lemma 3.1. Minimality gives

which proves the quotient bound. Under the additional hypothesis, writing k=\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

There are finitely many distinct restrictions. Replacing the restricting affine space by \aff\mathcal Q preserves the restriction, so write the maximizer as \mathcal A_0=\mathcal A\cap F, F=\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

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 \bits^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 \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 3.6. Write \Gamma=L_\Phi/L_0 for its orthogonal quotient and j=\rank\Gamma. The quotient has \det M\ge T^{\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 3.5 at scale T/\tau_j bounds the number M of distinct projections by

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

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

For j=0 this is the equality 1=1. Factoring the determinant along L_0 now yields

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\Z^m. Saturating therefore decreases its determinant, giving H(W)\le\det L_\Phi and the asserted height bound.□

Proof. Choose a fixed B_0>D+A+2, and put

Throughout the proof N is sufficiently large in terms of these fixed parameters. In particular a=o(1) and 1/\log N=o(a). We will encode a space within distance \Delta of each eligible W, at a cost o(N^2\ell^{-A}) bits. We follow the coordinate equations of W by a nested chain of minimizing spaces. The height budget limits the total dimension lost in drops larger than one. A flag in the normal lattice encodes each drop, and the minimizing inequalities ensure that few flag positions have a large encoding cost. We then sum these costs over the chain.

The minimizing chain. Let r=\dim W. Choose r pivot coordinates on which the coordinate projection of W is an isomorphism, and write W as the graph of rational linear functions on these coordinates. Order the nonpivot coordinates, and impose their graph equations one at a time. This gives rational spaces

At a step with coordinate vector e, one has P_{s-1}=P_s\oplus\R e. Every coordinate vector whose equation has not yet been imposed belongs to P_s.

For each s, minimize

over rational subspaces U, write the minimum as E_s, and let U_s be the greatest minimizer under inclusion. We justify these choices. By Lemma 3.2, h(U)\ge0, and only finitely many rational spaces satisfy H(U)\le N^{am}. Testing U=0 shows that a minimizer can be sought among those spaces, so the minimum exists. Lemma 3.2 and the inequality

show that the sum and intersection of two minimizers for F_s are again minimizers. The displayed inequality follows from the dimension identity for U,V and the inclusion (U\cap P)+(V\cap P)\subseteq (U+V)\cap P. Since the set of minimizers is finite, their sum is the greatest one. Also U_0=\R^m and E_0=0.

The minimizers descend with the graph spaces. In fact, if P'\subseteq P, then

Here the required inequality between intersection dimensions follows from (U\cap P)+(V\cap P')\subseteq (U+V)\cap P, whose two summands intersect in U\cap V\cap P'. Combining this inequality with Lemma 3.2, for U=U_{s-1} and V=U_s, gives

Minimality gives the reverse inequality. Hence U_{s-1}+U_s is an old minimizer, and greatestness implies U_s\subseteq U_{s-1}.

Every unprocessed coordinate vector e\in P_s belongs to U_s. Indeed, Lemma 3.2, together with H(\R e)=1 and H(U\cap\R e)\ge1, gives

If e\notin U but e\in P_s, adjoining e decreases d(U,P_s) by one, contradicting minimality. The energies are nondecreasing as well. For a step P_{s-1}=P_s\oplus\R e, one has

This follows directly by comparing the intersections after adjoining e: the new intersection contains (U\cap P_s)\oplus\R e, while the dimensions of U and P_s each increase by at most one. The height inequality just proved, applied to U=U_s, yields E_{s-1}\le E_s.

Testing the last objective at W gives E_{m-r}\le h(W). Therefore

Write c_s=\dim U_{s-1}-\dim U_s for the dimension drop at step s, and let z count the steps with c_s=0. At such a step the old and new minimizers coincide and contain the coordinate vector e being processed. Their intersection with P_s has dimension one less than their intersection with P_{s-1}, so E_s-E_{s-1}=a. Consequently z\le h(W)/a. Write \dim U_{m-r}=r+\theta. The distance bound gives |\theta|\le h(W)/a, while summing the drops gives \sum_s c_s=m-r-\theta. Since there are m-r steps,

It follows that

Normal flags for a transition. We next count the choices for a transition U_{\rm old}\supseteq U_{\rm new} of drop c\ge1, assuming U_{\rm old} is known. Let P_{\rm old}\supset P_{\rm new} be the corresponding graph spaces, and set

in the Euclidean span U_{\rm old}, and let K=\Lambda\cap U_{\rm new}^{\perp}. This is a primitive rank c sublattice of \Lambda, and it determines U_{\rm new}. For a rational V\subseteq U_{\rm old}, Lemma 3.3 identifies the determinant of its primitive normal lattice as

If V has codimension t in U_{\rm old}, the two rank distances from V and U_{\rm old} to any fixed space differ by at most t. Comparing V with the old minimizer, and saturating any sublattice of \Lambda, therefore gives

and hence

If K'\subseteq K is primitive of rank t, it is also primitive in \Lambda, and is the normal lattice of a rational space V' with U_{\rm new}\subseteq V'\subseteq U_{\rm old}. The normal-height identity and comparison with the new minimizer give

Thus

These two bounds are the only restrictions on the transition used in the count.

Choose a saturated flag

as follows. In the orthogonally projected quotient K/K_{i-1}, choose a shortest nonzero vector v_i, put \mu_i=\|v_i\|, and let K_i/K_{i-1} be the lattice on its line. A shortest nonzero vector is primitive, so K_i/K_{i-1}=\Z v_i. Each K_i is primitive in K, hence also in \Lambda. Put y_i=\log_N\mu_i. The determinant identity in Lemma 3.1 and Equation (4.2) give, for every suffix,

The classical shortest-vector consequence of Minkowski’s convex body theorem in rank u is \lambda_1(L)\le C\sqrt u\,(\det L)^{1/u}, with an absolute C. Apply it to K_{i+u-1}/K_{i-1}. The vector v_i is shortest even in the larger lattice K/K_{i-1}, and hence

Taking a full suffix in this inequality shows

In particular y_i\le1 for large N.

Call position i expensive if y_i>1/2-3a. A flag of length c has O(ac) expensive positions, and has none when c=1. For the latter assertion, Equation (4.3) gives y_1\le a<1/2-3a. For the general assertion, suppose an expensive position exists, and partition the suffix from the first such position into ranges, each starting at an expensive position and ending just before the next one, or at the end. For a range of length u, Equation (4.4) gives

For u\le N^{2/5}, this is at least u/5 for large N. For every u\le N, it is at least -C_1au, since 1/\log N=o(a). The total over the ranges is nonpositive by Equation (4.3). The total length of the short ranges is thus O(ac). There are at most c/N^{2/5}=o(ac) long ranges, and at most the total short length short ranges. This proves the asserted count.

Counting flag vectors. We count the vector at each flag position in a quotient determined by the preceding choices. Put

again using orthogonal projection. A rank t sublattice \bar L of \Pi lifts, together with K_{i-1}, to a rank t+i-1 sublattice of \Lambda. By Lemma 3.1, the first normal balance bound, and \det K_{i-1}=\prod_{j<i}\mu_j\le N^c, it follows that

Apply Lemma 3.6 to \Pi with T=N^{-2a}. Fix a deterministic choice of its minimizing primitive sublattice L_0, so that this choice requires no additional encoding once \Pi is known. If j_0=\rank L_0, the rank-zero competitor and Equation (4.5) imply

All sublattices of the quotient \Omega=\Pi/L_0 have determinant at least N^{-2a} to their rank.

First encode the image of v_i in \Omega. If \Omega has rank zero this image is unique. Otherwise, because its rank is at most N, Lemma 3.5 applies at the common smaller scale

for a suitable absolute C_2. For an inexpensive position, \mu_i\le N^{1/2-3a}, and orthogonal projection does not increase norm. Lemma 3.5 therefore bounds the base-two logarithm of the number of images by

For an expensive position the general bound on y_i permits a common radius R=C_3N^{1/2+a}, with an absolute C_3. Use the Gaussian comparison in Lemma 3.5 from s_0 to s_1=R/\sqrt N. These satisfy s_1\ge s_0 for large N. Writing k=\rank\Omega\le N, the base-two logarithm of the count is at most

The last equality uses a\log N\gg\log\log N.

It remains to count the vectors above one fixed image in \Omega. Use the common radius R=C_3N^{1/2+a} for both kinds of position, and let \mathcal V be the vectors v\in\Pi above that image with \|v\|\le R. If \mathcal V is nonempty, its differences lie in L_0. Let F be their real span, of dimension

The intersection lattice L_F=\Pi\cap F has rank j, and Equation (4.5) gives \det L_F\ge N^{-aj-2c}. If j=0, there is at most one vector. Otherwise choose j independent differences in \mathcal V, each of norm at most 2R, and let L'\subseteq L_F be their integer span. Fix v_0\in\mathcal V. Within each coset of L' in v_0+L_F, the translates at the points of \mathcal V of a half-open fundamental parallelepiped for these differences are disjoint up to boundaries. They lie in the j-dimensional ball centered at v_0 of radius 2(1+j)R. Writing B_j(r) for the Euclidean j-ball of radius r, we may sum over the [L_F:L']=\det L'/\det L_F cosets to obtain

Since j\le N and R=O(N^{1/2+a}), the logarithm of the numerator is O(j\log N). The determinant bound consequently gives

This bound is uniform over the fixed image and the preceding flag choices.

The image and fiber choices specify v_i\in\Pi. They also specify K_i: for any lift \widetilde v_i\in\Lambda,

Thus the encoding reconstructs the next quotient and ultimately K, and hence U_{\rm new}. The counts above can be applied successively to the prefixes of all encodings of actual minimizing chains; only such prefixes need satisfy the balance bounds.

Total encoding cost. We finish by summing the costs. Specifying the pivot and coordinate order, the drops, and the expensive positions costs O(N\log N) bits. There are at most N flag positions altogether, because the sum of all drops is at most m. Put

by Equation (4.1). The expensive-position count gives at most O(aS) such positions over the whole chain; there are none in drops of size one. For a drop c, the c fiber costs in Equation (4.7) total O(c^2\log N/a). Using \sum_{s:c_s\ge2}c_s^2\le S^2, the full base-two logarithmic cost is therefore bounded as follows. The four terms in the first bound account, respectively, for the choices of pivots, order, drops, and positions; for inexpensive images; for expensive images; and for fibers:

Each term is o(N^2\ell^{-A}). For the first, N^{-2a}\log^2N=\exp(-2\log N/\ell^{B_0}+2\ell) =o(\ell^{-A}). The second has factor a\ell^D=\ell^{D-B_0}=o(\ell^{-A}). For the third, \ell^{2D}/(a^3\log N)=\ell^{2D+3B_0}/\log N=o(\ell^{-A}); the fourth follows from \ell^{B_0}\log N/N=o(\ell^{-A}). All exponents here are fixed before N tends to infinity.

Collect the terminal spaces decoded by all these encodings, removing duplicates. This is a list independent of W, of size at most 2^{N^2\ell^{-A}} for sufficiently large N. Every eligible W contributes an encoding whose terminal space satisfies

The required distance bound follows, uniformly for m\le N.□

Proof. For any rational subspace U\subseteq\R^m, the lattice U\cap\Z^m is primitive in \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 \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 \F_2. Thus Equation (5.1) 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,

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 \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

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

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

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 4.1 with precision exponent P=2A+4. For each m\in\mathcal I_N, it gives a list \mathcal C_m of rational subspaces with

for every W in the height range of the proposition. Set t=\lceil s/2\rceil. Apply Equation (5.1) 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

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 (5.2), applied to their orthogonal complements, bounds each deficiency for W by

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

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 5.1 therefore gives the claimed rank for the inverse form, on the same typical set.□

Proof. If B is nonsingular over \R, its determinant is a nonzero integer. Every prime at which its reduction has positive corank divides that determinant. Hadamard’s inequality gives

so it suffices to consider primes p\le N^{N/2}. For each such prime, Lemma 2.3, with field \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

for all sufficiently large N. This also proves the asserted uniformity.□

Proof. Mean bound. Let J_m be the all-ones matrix and write

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

For i\ge1 with i+1\le m,

To prove it, expand the normalized trace as

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

and its odd moments vanish. Combining these estimates, and using \mathrm{Cat}_i\le4^i, gives Equation (5.3).

Fix the exponent A in the proposition and put

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

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 (5.3) term by term, the sum of the absolute values of its coefficients is 2(17/16)^{2j}. Consequently

This estimate verifies the required growing degrees: indeed

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

The pointwise majorization now proves

again uniformly in m.

Concentration and translation to B. We next obtain concentration strong enough for typicality. Pointwise,

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

The identities

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, Theorem 1 and Remark 2], with their eigenvalues ordered, states that

It follows by Cauchy–Schwarz that for a=1,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, Theorem 3] implies that, for universal c,C>0, if F:\R^d\to\R is convex and globally L-Lipschitz for the Euclidean norm, then its value at independent uniform signs satisfies

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 (5.4), their difference \Tr f(X)=m-\Tr g_1(X)+\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

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,

for all sufficiently large N. The eigenvalues of B in the interval of the proposition therefore number at most

Together with Equation (5.5), 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 (\Z/2^j\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

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 (6.2) forces

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

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 (6.2). In particular F\le i, and F has the parity of both i and j. Write

where X,Y are units. With n=F-h>0, the self-pairing condition is

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,

This is precisely Equation (6.1).

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

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

interchanging a,d when the second coordinate is the pivot. The self-pairing numerator is twice this quadratic form. Thus Equation (6.2) says

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

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

Restoring the common factor 2^{2t} proves Equation (6.1). 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 6.2, 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

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

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

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 \Hom(\bar L,\mathbb Q/\Z) into \Hom(L,\mathbb Q/\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 \Z in \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

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

which proves Equation (6.5). The rank-zero case has t=1 and follows from the stated conventions.□

Proof of Proposition 2.6. Fix A>0, and choose a fixed P>A+2. Intersect the typical event of Corollary 5.2 with exponent D=2 in the subspace height bound and precision P, and that of Proposition 5.4 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\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 3.7, applied to this color with parameter \rho=\ell^{-P}, gives a nonempty subset T robust on its affine span and satisfying

Put W=\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

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

and the rank-r lattice

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 3.8 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

For all sufficiently large N, the second bound in Equation (6.8) is at most \exp(N\ell^2). Thus this adaptively chosen W lies in the simultaneous scope of Corollary 5.2. Lemma 3.8 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(\R^m), define

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 5.2 gives

The reduction of Q modulo \Z on L is the pullback of the restricted discriminant pairing on

Indeed, the map L\to H sending \gamma(u) to u+B\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 6.3, 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 6.4 applies since B^{-1} is rational and the first coordinates of vectors in L are integral. Consequently \rank L=r, \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 6.4, followed by Equation (6.8), now gives

We compare this with the spectrum of Q on \Gamma, using the Euclidean metric induced from \R^{2m}. If v_i are orthonormal eigenvectors of B, with nonzero eigenvalues \lambda_i, then their graph vectors are orthogonal and

It follows that the self-adjoint operator representing Q on \Gamma has eigenvalues

All have absolute value at most one. Let C_P be the fixed constant supplied by Proposition 5.4. Apart from t_B\le N\ell^{-P} eigenvalues, that proposition gives |\lambda_i|>\sqrt N\,\ell^{-C_P}. For these indices,

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

The last inequality is also valid for s<t_B, since a_N<1. Comparing Equations (6.10) and (6.11) and taking logarithms yields

The coefficient on the left is positive for large N. Together with Equation (6.9) and t_B\le N\ell^{-P}, this implies

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 (6.6), (6.7), and (6.3). They give

The equality follows from Equations (2.4) and (6.4). 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. The cofactor identity gives

Thus a nonzero diagonal entry of B^{-1} gives the first alternative. Suppose instead that all diagonal entries of B^{-1} vanish. Since B^{-1} is nonsingular, it has a nonzero off-diagonal entry. Choose i,j to maximize the absolute value of an entry of B^{-1}, and write \kappa=(B^{-1})_{ij}\ne0. Then

Jacobi’s complementary minor identity gives

Order the coordinates with I first and write

Block inversion shows that

The diagonal of T is therefore zero. Its two diagonal equations give v_a^{\mathsf T}C^{-1}v_a=D_{aa}\in\bits for a=1,2. Moreover, the two columns of the displayed inverse block are -\kappa C^{-1}v_2 and -\kappa C^{-1}v_1. Every entry in that block has absolute value at most |\kappa|, by the choice of i,j. Hence \|C^{-1}v_a\|_\infty\le1 for a=1,2. These two facts are exactly the defining conditions for v_1,v_2\in\mathcal S(C).□

Proof. Quotienting by p^t and by v commutes:

Taking orders proves Equation (7.8).

Write G_p=\bigoplus_i\Z/p^{b_i}\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

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 (7.8) at t=e-1 from the equation at t=e proves Equation (7.9).

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

Put

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\Z^m. Its index is

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 7.3. Equation (7.10) at t=b_i gives u_{b_i}\ge b_i-r_i. All the first b_i layers are positive, and Equation (7.9) shows that the number among them that are retained is

If every layer in E is retained, then

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=\Z/p^t\Z, and reduce the blocks of B modulo p^t, writing them as C_t,V_t,D_t. Let

The presentation of the cokernel gives

Since C_t is an endomorphism of the finite group X, its kernel and cokernel have the same order. Hence

Define

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 (7.13) gives

For a kernel vector (x,y)\in X\oplus Y of B modulo p^t, the first block equation is

It requires y\in\ker\alpha. For each such y, its solutions in x form a coset x_0+L.

Consider the map

We claim that |\im\gamma|=p^{U_t}. Equip X and Y with their standard character pairings, for example

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

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 (7.17). Therefore L^\perp=J. It follows that

Equation (7.17) in Y now gives

For a fixed y\in\ker\alpha and x=x_0+z from Equation (7.16), the second block equation is

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

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 (7.14).□

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\R^h, and put L_V=V\cap\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

The image of L_V under this functional modulo \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

All these ratios are at least one. The initial projected space is \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,

We count possible av in \Lambda=L_V^*. Lemma 3.3, applied to V\subset\R^h, gives \det M\ge H(V)^{-1} for every sublattice M\subset\Lambda.

Apply Lemma 3.6 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

Every sublattice of the quotient has determinant at least T to its rank. By Lemma 3.5, the number of quotient images of vectors of norm at most N^{1/10} is

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

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 3.8, with the fixed parameter \rho=\ell^{-3D_0}, gives

The integer lattice sum of W_i\cap\Z^m is contained in W\cap\Z^m. The volume inequality for this sum and saturation give

Choose a fixed D_1>D_0+1. For sufficiently large N, this is at most \exp(N\ell^{D_1}). We impose Proposition 5.1 at this height and at a fixed precision strong enough that its rank error is at most \eta^5N. We also impose Proposition 5.3. Their intersection is typical. All counting below takes place within this intersection.

For a fixed list of dimensions, Lemma 8.2 counts centers and ordered bases of differences for the pieces with total logarithmic cost

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 \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

The choices for different pieces form distinct basis lists. As t\le m/N\le1, their total logarithm is at least

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 5.1 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 \R^m/W using columns of B. Let P be the resulting set of m-tN indices and Y=[m]\setminus P. Then

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

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

We next enumerate the possible K containing this known L. Let r_N=\lceil N^{3/5}\rceil. For every prime p,

by Proposition 5.3. 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 \Z^m/K, and also its character dual, can be generated by at most r_N elements.

Put H=\Z^m/L. The annihilator of K/L identifies (\Z^m/K)^\vee with a subgroup of H^\vee=\Hom(H,\mathbb Q/\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

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\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

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

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 (8.7) gives a lower bound of

on the number of pairs. On the other hand, Equations (8.6) and (8.8), together with the matrix saving, give the upper bound

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 (8.5) implies

All binary matrices have probability 2^{-T_m}. Dividing the pair bounds therefore gives

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 8.1. 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 8.3, and fix an arbitrary K with B\Z^m\subseteq K\subseteq\Z^m.

Apply Lemma 3.6 to K with T=(\log N)^4, and let K_0 be a minimizing saturated sublattice. Put F=\Span K_0 and

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

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 3.5 gives at most

distinct projections. Restrict to a largest projection fiber and then apply Lemma 3.7 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

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

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 (8.10) to a full-coordinate coset attaining M_K. Denote the resulting robust subset by S_*, put W_*=\Span(S_*-S_*), and write

An affine space of dimension \dim W_* contains at most 2^{\dim W_*} cube points, by coordinate projection. Consequently

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 8.3. 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

For a coset attaining M_K(J_0\cup A_i), apply Equation (8.10). It gives a robust subset S_i whose difference span satisfies

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 (8.11) 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

Remove one coordinate from the last A_i and include all of J_0. The resulting set D satisfies

by the minimum cardinality of that A_i. For x\ge0, t>0, define

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

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 8.3 applied to the constructed list gives

The 1/N accounts for the coordinate removed in Equation (8.14). 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

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

We have proved

Use the same D again, now with the singleton list consisting of S_*. Truncate D to size vN if necessary. From Proposition 8.3 and Equation (8.12),

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

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 (8.16) gives

Suppose instead that d\le f. Monotonicity and the unit Lipschitz bound of e in its first argument, together with Equations (8.15) and (8.16), give

Put u=d/f\in[0,1]. Directly from Equation (8.1),

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

The function a\mapsto a+e(\sqrt{2da},f) is nondecreasing and increases by at least the increase in a. Therefore Equation (8.17) implies \alpha\le\alpha_0+O(\sqrt\eta). Both cases give

By Equation (8.9), monotonicity of c, and Equation (8.3),

It follows that

Because D_0>2A is fixed, both error terms are o(\ell^{-A}). Increasing N makes their sum at most \ell^{-A}, proving Equation (8.2). The argument was deterministic for every K on the single typical event of Proposition 8.3, so the conclusion is simultaneous in K.□

Proof. Work conditionally on fixed exposed data satisfying the assumptions. Choose a fixed cube precision A_{\mathrm{cube}}>0, to be specified at the end, and invoke Equation (9.1) for each fixed candidate E. Here the quotient map G_C\twoheadrightarrow G, composed with the natural map from \Z^m, gives the exposed map \pi in that observation. This uses only the conditional uniformity of v; additional random bits and the restriction to \mathcal A need not be independent of v.

We now construct the classes. Fix a large constant D>0, to be chosen at the end, and set \delta=\ell^{-D} and a_p=\log_Np. The order bound gives

We classify the marks in three prime ranges.

For a_p>\ell^D, record every mark bit. There are at most N/(2\ell^D) layers in this range by the first bound in Equation (9.6), so this record costs O(N\ell^{-D}) bits.

For a_p<1-\delta, record the number of marks on each plateau. These counts determine all the marks because they are prefixes. There are at most N^{1-\delta} primes in this range. If d_p is the number of plateaus at p, their distinct positive heights give

Cauchy–Schwarz and the second bound in Equation (9.6) show that the total number of these plateaus is O(N^{1-\delta/2}\sqrt{\log N}). Each prefix count costs O(\log N) bits, since every plateau length is O(N\log N). The total cost is therefore

For the last equality, use \delta\log N=(\log N)/\ell^D\gg\log\log N.

The remaining primes satisfy 1-\delta\le a_p\le\ell^D. For each category, split this range into bins of width at most \delta, starting at 1-\delta, and call a category-bin pair a cell. There are J=O(\ell^{2D}) cells. In a cell j, let \lambda_j be the lower endpoint of its bin, so

The number of layers in this entire range is O(N), again by the first order bound. Record only the number of marks in each cell. This costs O(\ell^{2D}\log N)=o(N\ell^{-D}) bits. All these records depend only on the marks and the exposed data; intersecting their classes with \mathcal A gives the desired classes for the subevent. Their number is at most 2^{O(N\ell^{-D})+o(N\ell^{-D})}, uniformly in the exposed quotient.

Fix one class, a representative, and target weights as in the statement. For category i, put \theta_i=x_i/s_i if s_i>0, and put \theta_i=0 otherwise. In the large and small prime ranges the marked sets are known throughout the class; include all of them in each certificate. In an intermediate cell j of category i, let n_j be its number of layers and r_j its recorded number of marks, and require a certificate to contain any

of those marked layers. Thus every outcome in the class offers exactly

certificates, whereas the number of possible certificates for the class is at most

Empty products have value one. The latter count is an upper bound because it allows arbitrary layers in each cell, without imposing the prefix restriction.

We check the weight certified by each such choice uniformly over all outcomes in the class. In category i, let s_i^0 be the marked weight in the large and small prime ranges; it is fixed in the class. The representative’s marked weight in its intermediate cells differs from \sum_{j\in i}\lambda_jr_j/N by at most \delta\sum_{j\in i}r_j/N=O(\delta). The weight selected in those cells is at least

The last term is O(\ell^{3D}/N)=o(\delta). Since all of the known marked weight is included and s_i^0\ge\theta_i s_i^0, the selected weight in this category is at least x_i-O(\delta). Every selected layer there has height at least w_i. Consequently, uniformly over its choices,

Both q(E) and q_0 belong to [0,1/2]: for the latter, q_0\le\sum_i w_i s_i\le\sum_{p,e}k_G(p,e)\nu_p. The profile c is increasing and Hölder continuous of exponent 1/2 on this interval. Equation (9.7) therefore gives

Together with Equation (9.1), this bounds the probability of offering any one fixed candidate certificate by 2^{-N(c(q_0)-\eta_N-O(\sqrt\delta))}. This conclusion holds after intersection with the class and with \mathcal A, since such an intersection still implies v\in K_E.

Double counting outcome-certificate pairs now yields

Indeed, summing over candidate certificates the probabilities of the outcomes in the class offering that certificate gives \mathfrak m\Pr(\mathcal A_\alpha\mid\mathcal F); each summand is bounded by the fixed-certificate estimate. This also explains why no conditional independence of the marks or of the subevent is needed.

It remains to bound the ratio in Equation (9.8). For integers 0\le a\le n, the elementary binomial bounds are

For completeness, insert the parameter a/n into the binomial distribution. The upper bound follows because its probability at a is at most one, and the lower bound follows because a is a mode and there are n+1 probabilities summing to one. The endpoints are immediate. Applying these bounds to a cell gives

All arguments here stay in a fixed bounded set. Replacing a_j/N by \theta_i r_j/N changes the entropy term by O(N^{-1/2}), uniformly in \theta_i, by the Hölder estimate above. After summing over J=O(\ell^{2D}) cells, all rounding and binomial errors are

which is smaller than every fixed negative power of \ell.

We convert the remaining entropy terms from counts to weights. Their nonnegativity and homogeneity give, for a cell in category i,

Let u_i^0, alongside s_i^0, denote the unmarked weight in the known large and small ranges, and put

By Equation (9.5) the weighted cell terms sum to at most \mathcal E_{\theta_i}(\underline s_i,\underline u_i). Here adding the known ranges preserves this upper bound because their entropy term is nonnegative. The representative weights satisfy

All these weights have bounded sum, at most 1/2 before replacing weights by lower endpoints. The uniform Hölder estimate for \mathcal E_{\theta_i} and the factor (1-\delta)^{-1}=1+O(\delta) therefore show that

The constants in this estimate are uniform in the targets, including their endpoint values.

Choose the fixed D sufficiently large that \ell^{-D/2}=o(\ell^{-A}), and then choose a fixed cube precision A_{\mathrm{cube}}>A. The class count is at most 2^{N\ell^{-A}} for large N. Moreover, \eta_N, the rounding errors, and the two O(\sqrt\delta) errors in Equations (9.8) and (9.9) have sum at most \ell^{-A} for large N. Substitution proves Equation (9.3). Every choice of precision was fixed before N tended to infinity and was independent of the quotient and exposed columns, as required.□

Proof. Apply Proposition 9.1 at the fixed precision A_0=40. For the j-th quotient, condition on C and the preceding columns; these fix the quotient map to G^{(j-1)}, while v_j remains uniform. Use one category of all its layers, take w_1=1, and mark all retained layers. Lemma 7.3 ensures that these marks are prefixes on plateaus. Restrict to the subevent in Equation (9.11). For any representative of a nonempty class its marked weight s is at least \sigma, so we may choose x=\sigma^2. The total layer weight s+u is at most 1/2, by Equation (2.3). Since H_2(t)\le t\log_2(e/t), Equation (9.2) yields

This bound is uniform over the representatives in this subevent.

The defining formula for the profile c satisfies c(q)=2\sqrt q+O(q) as q\downarrow0. Indeed, in that formula u=2q/(1-2q)=2q+O(q^2), so \sqrt{2u-u^2}=2\sqrt q+O(q^{3/2}), and substitution gives the claimed expansion. In particular c(q)\ge(3/2)\sqrt q for all sufficiently small q. Proposition 9.1 therefore bounds the probability of each class by

There are at most 2^{N\ell^{-40}} classes. Since \sigma\asymp\ell^{-12}, both \sigma^2\log(1/\sigma)=o(\sigma) and \ell^{-40}=o(\sigma). Summing the class probabilities gives Equation (9.11) for large N.

The argument tests only the quotient by the selected column. It does not use a new principal block or any property of an enlarged matrix. The conditional uniformity for a second column and the simultaneous cube estimate for lattices containing C\Z^m establish the claimed uniformity over the preceding column.□

Proof of Proposition 7.2. 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 9.1 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 10.1 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

Proposition 9.1, applied to this representative in the restricted outcome space, therefore yields

Since \Psi(B_{\mathcal C})-\Psi(C)\le I by Equation (10.2), the contribution of this class satisfies

Summing over the classes proves

for all sufficiently large N.

For width two, take C also in the typical set of Proposition 2.6 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 \bits^m. For the gate \mathcal G_2=\{v_1,v_2\in\mathcal S(C)\}, that Proposition gives

On nonsingular outcomes \Psi(B)\le1. Consequently

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 7.2, with arbitrary fixed precision and with the stated nonsingularity and gate indicators.□

Proof of Lemma 10.1. 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 (8.1) 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

Write I=\beta g+(6-\beta)a_0-\beta u. We will prove that, for every w\ge0,

Here is a justification that this suffices. If g=a_0=0, taking x=y=0 proves Equation (10.4) 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

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

a contradiction. The claimed maximum separates into its two coordinates. Hence the maximum of the left side of Equation (10.4) is exactly c^*(w)+\mathcal F_w(g,v_0)+\mathcal F_{2w}(a_0,u) at this supporting slope. Equation (10.5) proves the desired assertion.

Entropy minimum and criterion. We use the function H from Equation (9.4) to compute a lower bound for the two \mathcal F terms. For t>0 set

For r\ge0, maximizing H(z,r)-tz over 0\le z\le1 at z=\min\{1,r/(2^t-1)\} gives

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

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

Indeed, homogeneity and Equation (10.6) imply

These remain true when g=0 or a_0=0. Using the first two inequalities in Equation (10.7) now gives

The two budgets and the third inequality in Equation (10.7) yield Equation (10.5).

Exact verification. We verify Equation (10.7) with three explicit choices. The function D is decreasing, and, for h>0,

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:

Indeed, if v=2^{-1/10}, then v<14/15 because 15^{10}<2\cdot14^{10}. Thus

which is equivalent to Equation (10.9).

We will use the support bounds

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

Then

The expression (r+2q)/(1+r) increases in r, so

The difference in the last inequality is 4q\sqrt q/(1+2\sqrt q). Testing q=(w+2)^{-2}\le1/4 now gives

including at w=0.

One global estimate handles the middle range:

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,

Consequently the arithmetic–geometric mean inequality gives

which proves Equation (10.11).

We use the following choices, writing h=\beta+\lambda+2\mu:

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

By Equations (10.8) and (10.9), the second multiplier expression exceeds

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 (10.10).

For 8/5\le w\le3, take \lambda=17/24-w/6 and \mu=1/4. These are nonnegative, and

By Equation (10.11), the first multiplier expression exceeds

By Equations (10.8) and (10.9), the second expression exceeds

Finally, \lambda+\mu=23/24-w/6, so Equation (10.10) gives the third inequality.

For w\ge3, take \lambda=0 and \mu=3\,2^{-w}, which are nonnegative. The elementary bound

and 2^\mu-1\ge\mu\log2 give

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 (10.8) therefore shows that the second expression is greater than

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

It follows that \mu\le2/(w+2)\le2c^*(w) by Equation (10.10). This verifies Equation (10.7) for every w\ge0, and hence proves Equation (10.4).□

Proof. Fix a prime p, and put F_D(p,t)=\sum_{e=1}^{t}k_D(p,e) for D=C,B. Take t to be the largest e for which k_B(p,e)>s, or take t=0 when there is no such e. Then

For e\le t, the height in G_B is at least s+1. The final successive quotient of G_C is also obtained from G_B by h one-element quotients. The interlacing of heights under each such quotient therefore gives

Let u_i(p,t) be the total drop in the first t layers at the i-th quotient and put U_p(t)=\sum_i u_i(p,t). Each layer in this range has positive starting height, and each of its drops is zero or one. Thus

All the layers on the right have the height lower bound just displayed. Lemma 7.5 now yields

Multiplying by \nu_p and summing over p proves the claim.□

Proof. Conditioning on \mathcal F fixes the quotient map and H; it leaves v uniform on \bits^m. For a fixed mask E of layers required to be retained, Lemma 7.4 supplies the necessary condition

We first show that this condition costs at least 2q(E)N/3 bits of probability.

Write g_1,\ldots,g_m for the images of the coordinate vectors in \Z^m/K_E. Choose a maximal subset g_{i_1},\ldots,g_{i_j} that is dissociated, meaning that all of its subset sums are distinct. After the other bits of v are fixed, at most one choice of the j selected bits can give any prescribed group element. Hence every atom of the image of v, in particular the zero atom, has probability at most 2^{-j}.

Maximality also implies that every g_a is a combination of the selected elements with coefficients in \{0,1,-1\}: otherwise adjoining g_a would preserve distinctness of subset sums. Choose such representations, using the identity representations at the selected indices, and arrange their coefficients as the columns of a matrix M\in\Z^{j\times m}. This matrix has rank j. The selected elements generate \Z^m/K_E, so they define a surjection \theta:\Z^j\to\Z^m/K_E. Every column of MC belongs to \ker\theta, because the columns of C belong to K_E. Since C is nonsingular, MC still has rank j. Choose j independent columns of MC. Each of their entries has absolute value at most m\le N. Their lattice is contained in \ker\theta, and Hadamard’s inequality gives

For j=0, the group is trivial and the same conclusion has its usual empty-product meaning. It follows that

We next bound the number of possible masks consisting of all retained layers of height at least R-1, when their value of Q lies in [q,2q). At a fixed prime the retained layers on each plateau form a prefix. Let d_p be the number of plateaus of H at p. Their distinct positive heights imply

Moreover, \sum_{p,e}k_H(p,e)\le\log_2|H|=O(N\log N). There are at most N^{1/2} primes p\le N^{1/2}, so Cauchy–Schwarz bounds the number of their plateaus by

Each prefix length has O(N\log N) possible values and costs O(\log N) bits. The full cost for these primes is consequently

Here the final estimate is uniform for q\ge q_0.

For p>N^{1/2}, each eligible layer has, for large N,

The total height times weight in H is at most 1/2, so there are at most 3N/(2R) eligible layers in this range. A mask with Q<2q selects at most 6qN/R of them. The usual binomial estimate, using the bound 2^a for all subsets when the permitted number is a fixed fraction of the a available layers, gives a logarithmic count of at most

Indeed qN/R\ge\eta N/(100R\log N)\to\infty, so integer rounding does not affect this estimate, and

Combining the two prime ranges, the mask entropy is o_\eta(qN) uniformly in the indicated interval. For every mask being counted, q(E)=Q\ge q. The union bound with Equation (11.4) is therefore

The conditioning argument uses only that \mathcal F fixes C,\pi and leaves v uniform, so it also applies when \mathcal F includes a preceding column.□

Proof of Proposition 2.7. Fix 0<\epsilon<1/10, and put

Here J_* is the length of the long path, and L_* is the length of its terminal window. The following comparisons will be used throughout:

They hold for all sufficiently large N, since R\asymp\ell^2 and every fixed power of \ell is o(N^a) for every fixed a>0. The first line keeps every node in \mathcal I_N and leaves enough preceding steps to drive the tail threshold past N^{3/5}. The second line keeps the potential-step error small over the terminal window, makes the accumulated costly-step exponent diverge, and makes that cost dominate the entropy of choosing the costly positions.

For m\in\mathcal I_N, let \mathcal T_m be the set of nonsingular matrices satisfying the estimates in Propositions 5.3 and 9.2, and those in Propositions 2.6 and 7.2 at precision A=60, including both widths in the latter proposition. These finitely many properties can be chosen so that, for some f(N)\to\infty,

Write m_*=N-1. Consider all principal submatrices of \mathbf B_{m_*} obtained by deleting at most 2J_* indices. Their sizes lie in \mathcal I_N by Equation (11.5), and their number is at most

Let \mathcal E_N be the event that any nonsingular one of these submatrices fails its typical properties. Each fixed submatrix is a binary matrix, so the union bound gives

Since 2^{N\Psi}\le2^N, its contribution to the moment is at most

Starting from a nonsingular realization on [m_*], apply Lemma 7.1 backwards for exactly J_* steps. It gives a path of nonsingular principal minors, each deletion having width one or two, and every deletion of width two satisfying the gate when read as a forward transition. At most 2J_* indices are deleted, so all these operations stay in the prescribed size range. On \mathcal E_N^c, all of their nodes also belong to their respective sets \mathcal T_m.

For clarity, the path just obtained is chosen backwards as a function of the realized terminal matrix. We use it only to cover the terminal event by path events. Let \Pi_N be the collection of all fixed index paths

An ordering of the two indices in a pair is fixed once for each path. At each backward step there are at most 2N^2 choices, whence

For a fixed \pi\in\Pi_N, put B_t=\mathbf B_{m_*}[I_t]. Let \Gamma_t be the event \mathcal G_{h_t} from Equation (7.2) for step t. Define

The backward construction shows that every nonsingular terminal matrix outside \mathcal E_N lies in at least one \mathcal A_\pi. Consequently

We now bound a summand for a fixed \pi. Expose the entries of B_0 first and then expose each transition forwards. Conditional on the entries already exposed, its cross columns are independent uniform bit vectors on the starting indices, and its new symmetric block consists of independent bits. Within a pair the second cross column is still uniform after the first is exposed. We sum over fixed paths before making any of these exposures; we never condition this forward process on the backward choice of a path. The future nonsingularity, typicality, and gate requirements are imposed only through indicators.

Call the last L_* steps and their L_*+1 nodes the terminal window. We will prove the three weighted bounds in Table 1.

Large tails in the window. At each cross column of the fixed path, form Q as in Lemma 11.2 using the quotient immediately before that column. Put

For an unconditional exposure on which the starting matrix C of a step is singular, define \widetilde Q=0 for its cross columns. This convention permits estimates on the entire probability space. For a nonsingular start, Q\le1/2 by the group order bound. Apply Lemma 11.2 with \eta=\epsilon' to the dyadic values q_j=2^j q_{\min} up to 1/2. Conditional on everything exposed before a cross column,

The last inequality holds for large N, since Nq_{\min}\to\infty; the dyadic sum is at most twice its first term and is then bounded by the displayed \delta_N. It holds also for a singular start by the convention above. There are d_\pi=\sum_t h_t\le2J_*=O(N^{3/5}) cross columns. Successive conditioning, including between the two columns of a pair, therefore gives the multiplicative bound

In particular the accumulated error in its logarithm is O(N^{3/5}2^{-\epsilon'N/(2000\log N)})=o(1).

On \mathcal A_\pi, suppose W_R(B_t)>\epsilon' at a node J_*-L_*\le t\le J_*. Starting at this node, iterate Lemma 11.1 backwards, increasing s by the width at every step. Stop as soon as s>N^{3/5}. This takes at most \lceil N^{3/5}\rceil steps, so the available preceding path is long enough by Equation (11.5). Every invocation has s\ge R\ge2, as required. At the last node the tail is zero: Proposition 5.3 gives

at every typical nonsingular node and every prime p.

Number the backwards steps from the chosen node by j=1,2,\ldots,r. Before step j, the current value of s is R plus the widths of its j-1 predecessors. If the current width is h\le2, each charged layer in Equation (11.2) thus has height at least

The charge from one quotient at this step is bounded by 2Q/(R+j-2), because Q includes height times weight for all retained layers of height at least R-1. There are at most two quotients per step. The terms with Q<q_{\min} contribute at most

for large N. Here r\le\lceil N^{3/5}\rceil and the last comparison follows from the definition of q_{\min}. The remaining charges must therefore exceed \epsilon'/2. Since every denominator is at least R-1, this implies

The same condition on the sum over the whole path is necessary if any node of the window has W_R>\epsilon'. By Markov’s inequality and Equation (11.8),

Multiplication by the terminal weight, which is at most 2^N, still gives 2^{-\omega(N)}, because R\to\infty.

A small potential in the window. Proposition 7.2 at precision 60 states, for either width and for a starting matrix C\in\mathcal T_m,

where \Gamma is the gate for width two and the certain event for width one. Adding a typicality indicator at the endpoint only decreases the left side. Successive conditioning from a node t to the terminal node consequently bounds the conditional weighted expectation with all the intervening requirements by

whenever B_t\in\mathcal T_{|I_t|}. This is an application to the fixed forward exposure, with no conditioning on future requirements. For each t in the window, on \Psi(B_t)\le\epsilon it is at most 2^{N(\epsilon+L_*\ell^{-60})}. Dropping all requirements before t and summing over its L_*+1 possible values gives

This records both the accumulated transition error and the cost of choosing the node.

The remaining window event. Consider the event

At any node B of this event, \phi(k)\le2k and \phi(0)=\phi(1)=0 show that \sum_{k_B\ge2}k_B\nu_p\ge\epsilon/2. On the other hand,

Dividing the contribution from 2\le k_B\le2R by 2R gives

If in addition \Psi(B)>1-1/R, the contribution to \Psi(B) from height two is at most \beta/4=7/20. Indeed, 2\sum_{k_B=2}\nu_p\le1/2 by the order bound. Thus

For large N the height times weight on the left after division by two is at least 1/4. Since \epsilon'<1/200, deleting the layers above 2R and dividing by 2R yields

For each quotient at step t, let V_{t,i} be the sum of the weights \nu_p of all of its retained layers. On \mathcal A_\pi, call a step in the window costly if some V_{t,i}\ge\sigma, or if it has width two and its starting node C=B_{t-1} satisfies \Psi(C)\le1-1/R. To price this description without conditioning on \mathcal A_\pi, define an exposure event D_t as follows: the starting node belongs to its set \mathcal T_m, and either some V_{t,i}\ge\sigma, or the step has width two, \Psi(C)\le1-1/R, and its gate \Gamma_t holds. Every costly step of a required path satisfies D_t.

Let \mathcal F_{t-1} be the sigma-field generated by all entries exposed through C. Proposition 9.2, applied to each column and conditioned on a preceding column when needed, gives probability at most 2^{-N\sigma/2} for each event V_{t,i}\ge\sigma. For the other alternative, the two cross columns are conditionally independent and the gate requires both to belong to \mathcal S(C). Proposition 2.6 gives

Here 1-m/N\le N^{-3/10}. If \Psi(C)\le1-1/R, then \ell^{-60}+N^{-3/10}=o(R^{-1}) and \sigma=R^{-6}=o(R^{-1}), so for large N this probability is at most 2^{-N/R}\le2^{-N\sigma/2}. If the start is not in \mathcal T_m, the event D_t is empty. The union bound therefore gives, uniformly in the revealed history,

In particular, for any fixed set T of step positions, ordinary successive conditioning in the forward exposure gives

This estimate imposes no conditioning on the other path requirements.

Descent at noncostly steps. To force many costly steps on \mathcal H_\pi, we combine two tails. At width one, the smaller R^{-2}W_1 term uses the mass of layers of height at least two. At width two, W_2 uses the stronger gap between W_2 and W_4, while the small coefficient prevents the W_1 term from offsetting that gap. Define

The order bound implies 0\le Z(B)\le(1+R^{-2})/2\le1. At a noncostly step all its V_{t,i} are less than \sigma. For a step of width one, Lemma 11.1 gives

Equations (11.1) and (11.11) then show

for large N, since \sigma=R^{-6}=o_\epsilon(R^{-3}). At a noncostly step of width two, its starting potential is \Psi(C)>1-1/R. Lemma 11.1 gives

Also

by Equation (11.12). Using W_1(B)\le1/2, we obtain

for all sufficiently large N. The middle comparison uses 4R^{-6}+(2R^2)^{-1}=o(R^{-1}). Thus every noncostly step decreases Z by at least

Let n_{\mathrm{cost}} be the number of costly steps in this window. A costly step can increase Z by at most one. Telescoping the L_* changes and using 0\le Z\le1 gives

Now \delta\to0 and L_*\delta\asymp_\epsilon R^9\to\infty. Consequently, for large N,

Set t_*=\lceil L_*\epsilon/(100R^3)\rceil. The event \mathcal H_\pi therefore implies D_t at at least t_* positions in the window. Equations (11.13) and (11.14) yield

The entropy of choosing these positions satisfies

Together with the factor 3^{t_*}, this is o(N\sigma t_*), because N\sigma/\log R\to\infty. In particular, for all sufficiently large N,

This bound uses L_*\sigma/R^3\asymp R^3\to\infty. The corresponding weighted expectation is at most 2^{N-\Omega_\epsilon(NR^3)}=2^{-\omega(N)}.

Equations (11.9), (11.10), and (11.15) prove the three weighted bounds in Table 1. Its row events cover all outcomes in \mathcal A_\pi, so their sum gives, uniformly over all fixed index paths,

Finally use Equation (11.7). The index-path sum adds O(N^{3/5}\log N)=o(N) to the logarithm, and Equation (11.6) gives a negligible exceptional contribution even after the weight 2^N. Hence

For each fixed \epsilon this estimate holds for all sufficiently large N. Letting \epsilon tend to zero after N proves Proposition 2.7.□

Proof of Theorem 1.1. By the implication established in Section 2, Propositions 2.6 and 2.7 give Equation (2.2): \E|\mathcal S(\mathbf B_{N-1})|\le2^{o(N)}.

Lemmas 2.4 and 2.5 now give

A specified row of \mathbf B_N is identically zero with probability 2^{-N}, so the reverse bound follows from that event. Therefore \Pr(\det\mathbf B_N=0)=2^{-N+o(N)}. Finally Lemma 2.1, with N=n-1, yields

□