THE SHARP EXPONENTIAL RATE OF SINGULARITY FOR SYMMETRIC BERNOULLI MATRICES
A complete proof, written to be read from start to finish.
==========================================================================
0. WHAT WE PROVE, AND THE SHAPE OF THE ARGUMENT
==========================================================================
Let A_n be a symmetric n x n matrix whose entries on and above the
diagonal are independent and uniform on {-1,+1}. We prove
Pr(det A_n = 0) = (1/2 + o(1))^n = 2^{-n+o(n)} as n -> infinity.
Why 2^{-n} is the natural scale. Two rows of A_n are equal with
probability 2^{-n}: along the diagonal and just off it the entries are
forced, and away from those n-2 spots the comparisons are free and each
holds with probability 1/2. Equal rows give det A_n = 0, so singular
matrices already appear at rate 2^{-n}. The theorem says nothing else
appears at a larger exponential rate. (The classical result of
Komlos--Tikhomirov for matrices with all n^2 entries independent has the
same constant 1/2; symmetry makes the proof harder because revealing one
row also reveals parts of every other row, but the answer is unchanged.)
The proof is long because every step must hold with enormous margin. We
organize it as SEVEN steps. Read this list first; each later section is
one step or a tool for one step.
Step 1 (Section 1). Reduce to a binary matrix, then to a matrix of
corank one, then count "admissible columns". Everything reduces to a
single estimate:
E |S(B_{n-1})| <= 2^{o(n)},
where S(B) is the set of bit vectors z with z^T B^{-1} z in {0,1} and
||B^{-1} z||_inf <= 1.
Step 2 (Section 2). Attach to each nonsingular B a number Psi(B) in
[0,1], read off from the arithmetic of the group Z^m/BZ^m. Show that
E|S(B)| is small once we know two facts:
(A) typically |S(B)| <= 2^{n(Psi(B)+tiny)},
(B) E[ 1_{det B != 0} 2^{n Psi(B)} ] <= 2^{o(n)}.
Step 3 (Sections 3-6). Prove (A). Build a toolkit of lattice facts
(Section 3), a finite list that "covers" all low-complexity subspaces
(Section 4), and the typical rank/spectral behaviour of a random binary
matrix (Section 5). Then color the admissible classes by the
discriminant pairing, build a graph lattice, and compare a determinant
lower bound (from the pairing) with an upper bound (from the spectrum);
the mismatch forces dim Span(S(B)) <= 2 J_B, which is exactly (A)
(Section 6).
Step 4 (Section 7). Set up the algebra of adding one or two rows and
columns to a matrix. The new and old groups share a quotient; this
controls how the "layers" that make up Psi can change.
Step 5 (Sections 8-10). Prove a local estimate: adding one random row
and column multiplies 2^{n Psi} by 2^{n(tiny)} in expectation, at least
on a typical starting matrix. Adding two rows works only on a "gate"
event, and (A) pays for the gate. The width-one case is a counting
argument ("certificate pricing", Sections 8-9) plus a small scalar
inequality (Section 10).
Step 6 (Section 11). Build any matrix from a small principal minor by
adding rows and columns one or two at a time (a "path of principal
minors"). A high-layer tail estimate and a bounded statistic that
decreases at every non-exceptional step show the local estimates chain
together, giving (B).
Step 7 (Section 11 end). Put (A) and (B) together to finish Step 2,
then Step 1, and read off the theorem.
All constants called "tiny" (written l^{-A}, N l^{-A}, etc.) are smaller
than any fixed negative power of l = log log N for large n; they never
affect the leading exponential rate and can be ignored on a first read.
The genuine content is: which object is small, and by how much.
==========================================================================
NOTATION
==========================================================================
Throughout, N is the main large parameter and m is a matrix size with
m in I_N := { integers m : N - N^{7/10} <= m <= N }.
We set
l = log log N.
"log" is natural log; "log_2" and "log_N" have the stated base.
[m] = {1,...,m}. Vectors are columns. B^T is transpose, B^{-1} inverse.
For a real symmetric matrix B and a subspace U, B|_U denotes the
symmetric bilinear form (u,v) -> u^T B v on U x U.
A property of the random binary matrix B_m "holds typically" if it fails
with probability at most 2^{-N f(N)} for some f(N) -> infinity, uniformly
over m in I_N. A finite intersection of typical properties is typical.
Bit vectors live in {0,1}^m, written bits^m; |X| is cardinality.
A "tiny" quantity is any O(l^{-A}) with A fixed; it is o(1).
==========================================================================
1. THREE REDUCTIONS: SIGNS TO BITS, BITS TO CORANK ONE, CORANK ONE TO
A COLUMN COUNT
==========================================================================
The goal of this section is to replace the original question by the
single estimate (Section 1.6):
E |S(B_{N-1})| <= 2^{o(N)}.
--------------------------------------------------------------------------
1.1 Signs to bits
--------------------------------------------------------------------------
A "binary matrix" of size m is a symmetric m x m matrix whose entries on
and above the diagonal are independent and uniform on {0,1}. Write B_m
for the random binary matrix and use B, C, M for realizations.
Lemma 1.1. For n >= 2, Pr(det A_n = 0) = Pr(det B_{n-1} = 0).
Proof. Let eps = (A_n)_{11} and multiply A_n throughout by eps. Then
apply the diagonal congruence with diagonal
1, eps (A_n)_{12}, ..., eps (A_n)_{1n}.
The resulting matrix has first row and first column all equal to 1.
Conditional on the original first row, every entry of the lower
principal block is still an independent uniform sign: each has only been
multiplied by a sign determined by the first row. The Schur complement
at the top-left entry (which equals 1) is therefore -2 B_{n-1}. A
congruence and a Schur complement preserve singularity, so A_n is
singular iff B_{n-1} is. QED
From now on we study the binary model. We will prove
Pr(det B_N = 0) = 2^{-N+o(N)}, i.e. the analogue of the theorem with
N playing the role of n; Lemma 1.1 then transfers it back.
We work throughout in a narrow band of sizes
I_N = { integers m : N - N^{7/10} <= m <= N },
so that passing between sizes m and N costs at most a factor that is
negligible exponentially. Recall l = log log N.
--------------------------------------------------------------------------
1.2 Two facts over arbitrary fields
--------------------------------------------------------------------------
Lemma 1.2 (principal rank). Let M be a symmetric matrix over a field,
of rank r. Then M has a nonsingular principal r x r submatrix.
Proof. Choose X with r columns forming a basis of the column space of M,
and a left inverse T of X. Since M is symmetric its row space is the row
space of X^T, so M = X S X^T with S = T M T^T symmetric of rank r. Pick r
independent rows of X; on those indices the principal submatrix of M is a
product of three nonsingular r x r matrices. QED
Lemma 1.3 (corank tail). Let K be any field and view the bits of B_m as
elements of K. For 1 <= k <= m,
Pr( corank_K B_m >= k ) <= sum_{j=k}^{m} C(m,j) 2^{-j(j+1)/2}.
Consequently, uniformly for m in I_N and for every field,
Pr( corank_K B_m > N^{3/5} ) <= 2^{-Omega(N^{6/5})}.
Proof. Rank m-j means, by Lemma 1.2, a nonsingular principal (m-j)x(m-j)
submatrix on some index set. Reveal all entries in those m-j columns.
The remaining symmetric j x j block is then forced over K (its Schur
complement must vanish), and each of its j(j+1)/2 free entries has at
most one admissible bit value; the conditional probability is at most
2^{-j(j+1)/2}. Union over the C(m,j) index sets and over j >= k.
For j > N^{3/5}, 2^{-j(j+1)/2} beats both 2^m choices of indices and the
at most m = 2^{o(N)} values of j. QED
--------------------------------------------------------------------------
1.3 Bits to corank one
--------------------------------------------------------------------------
Lemma 1.4 (reduction to corank one). For the binary model in dimension N,
Pr(det B_N = 0) <= 2^{o(N)} Pr(corank B_N = 1) + 2^{-Omega(N^{6/5})}.
Proof. Let B have corank k >= 1 and let K = ker B (over R). Choose k-1
coordinates whose restrictions to K are independent linear functionals.
Flip the diagonal bit at each of those coordinates; let D be the diagonal
matrix of the flips, its selected entries nonzero.
Claim: corank(B+D) = 1. If (B+D)v = 0, pairing with u in K gives
u^T D v = 0 for all u in K. Since the chosen coordinate functionals on K
are independent, the selected coordinates of v vanish. Then Dv = 0 on
the selected coordinates forces Bv = 0, i.e. v in K. Conversely every
v in K with those coordinates zero lies in ker(B+D). So ker(B+D) has
dimension one. (This step needs k <= N^{3/5} so the coordinate choice is
available and distinct entries stay nonzero; the general case is covered
by the corank tail below.)
For a matrix with corank k <= N^{3/5}, fix one such choice of coordinates.
The number of matrices mapping to a given one is at most
sum_{j <= ceil(N^{3/5})} C(N,j) = 2^{O(N^{3/5} log N)} = 2^{o(N)},
because a preimage is recovered by naming the flipped coordinates. All
binary matrices are equally likely. Add the probability of corank
> N^{3/5} from Lemma 1.3. QED
--------------------------------------------------------------------------
1.4 Admissible columns
--------------------------------------------------------------------------
For a nonsingular binary matrix B of size m define the set of admissible
columns
S(B) = { z in bits^m : z^T B^{-1} z in bits and ||B^{-1} z||_inf <= 1 },
and set S(B) = empty when B is singular. These are exactly the new
columns that can appear when a corank-one matrix is reduced by deleting a
largest coordinate of its kernel vector.
Lemma 1.5 (column reduction).
Pr(corank B_N = 1) <= N 2^{-N} E |S(B_{N-1})|.
Proof. Let M be symmetric of size N with corank one, and pick
0 != v in ker M. Delete an index i where |v_i| is largest; the resulting
principal submatrix B is nonsingular (the adjugate of M is a nonzero
multiple of v v^T, whose i-th diagonal entry is nonzero). Write z for the
column at i on the remaining indices and a for its diagonal bit. The
kernel equation and the Schur complement give
B^{-1} z = - v_{[N]\setminus{i}} / v_i, a = z^T B^{-1} z,
so z lies in S(B). For a fixed deleted index, conditional on B, the pair
(z,a) is uniform on bits^{N-1} x bits; each z in S(B) pins a uniquely.
The probability for that index is 2^{-N} E|S(B_{N-1})|. Union over the N
choices of deleted index. QED
--------------------------------------------------------------------------
1.5 The single estimate
--------------------------------------------------------------------------
Combining Lemmas 1.4 and 1.5,
Pr(det B_N = 0) <= 2^{o(N)} N 2^{-N} E|S(B_{N-1})| + 2^{-Omega(N^{6/5})}.
A specified row of B_N is identically zero with probability 2^{-N}, giving
the matching lower bound 2^{-N}. Therefore the theorem for the binary
model follows from
Lemma 1.6 (the target).
E |S(B_{N-1})| <= 2^{o(N)}.
Indeed, with Lemma 1.6 the upper bound becomes 2^{-N+o(N)}, and after
Lemma 1.1 this is (1/2+o(1))^n for A_n. The whole of Sections 2-11 is a
proof of Lemma 1.6. (Trivially |S(B)| <= 2^m, so Lemma 1.6 says the
number of admissible columns is 2^{o(N)} on average.) QED
==========================================================================
2. THE POTENTIAL, AND THE TWO PROPOSITIONS THAT PROVE LEMMA 1.6
==========================================================================
We must bound |S(B)| for a typical B. Each admissible column z obeys
z^T B^{-1} z in {0,1}, i.e. z^T B^{-1} z is an INTEGER. So z is a cube
point that lands, under the quadratic form of B^{-1}, on a lattice point
of Z. The many admissible columns occur only when the denominators in
B^{-1} are "rich" -- when the group Z^m/BZ^m has a lot of layered
structure. We package that structure into one number Psi(B) in [0,1].
--------------------------------------------------------------------------
2.1 The discriminant group and its layers
--------------------------------------------------------------------------
For nonsingular B the finite abelian group
G_B = Z^m / B Z^m
has order |det B|. It records the possible denominators of B^{-1} z for
integer z: B^{-1} z mod Z^m is exactly the class of z in G_B.
Write the p-primary part of a finite abelian group G in invariant-factor
form
G_p = (+)_i Z/p^{b_{p,i}} Z, b_{p,1} >= b_{p,2} >= ... >= 0,
only finitely many b_{p,i} positive. For an integer e >= 1 put
k_G(p,e) = #{ i : b_{p,i} >= e }, nu_p = (log_N p)/N.
Call (p,e) with k_G(p,e) > 0 a LAYER, the integer k_G(p,e) its HEIGHT,
and nu_p its WEIGHT. Think of the invariant factors as columns of a
"staircase": layer (p,e) has height k_G(p,e), the number of factors of
size at least p^e.
The order of the group is recorded by the layers:
sum_{p,e} k_G(p,e) nu_p = (log |G|)/(N log N). (2.1)
(This is just sum_e k_G(p,e) = sum_i b_{p,i} = log_p |G_p|, then sum over
p.) A binary matrix B of size m <= N satisfies Hadamard's bound
|det B| <= N^{N/2}, so the left side of (2.1) is at most 1/2 for G_B and
for every quotient of G_B. We use this repeatedly as a "budget": the
total of height times weight is at most 1/2.
Write k_B(p,e) = k_{G_B}(p,e) and set beta = 7/5. Define the potential
Psi(B) = sum_{p,e} nu_p phi( k_B(p,e) ), (2.2)
phi(0) = phi(1) = 0, phi(2) = beta, phi(k) = 2k for k >= 3.
Since 0 <= phi(k) <= 2k, the budget (2.1) gives 0 <= Psi(B) <= 1. Set
Psi(B) = 0 for singular B whenever Psi appears next to a nonsingularity
indicator.
Example. A p-primary part with cyclic exponents (5,3,1) has heights
(k_B(p,1),...,k_B(p,5)) = (3,2,2,1,1),
so it contributes (2*3 + beta + beta + 2*1 + 2*1) nu_p = (6 + 2 beta) nu_p
to Psi. The weights 2 (for k=3), beta (for k=2), 0 (for k=1), and
2k (for larger k) are chosen so that the two propositions below both hold;
beta = 7/5 sits between the coefficient 5/4 forced by the coloring bound
(Section 6) and the budget inequality of Section 10.
The potential quantifies exactly how many admissible columns to expect:
more layers -> more denominators -> more admissible columns. The two
statements that make this precise are the following.
--------------------------------------------------------------------------
2.2 The two propositions
--------------------------------------------------------------------------
Proposition A (admissible-column estimate). For every fixed A > 0,
typically for nonsingular B of size m in I_N,
|S(B)| <= 2^{N( Psi(B) + l^{-A} )}.
Proposition B (potential moment). For a binary matrix of size N-1,
E[ 1_{det B_{N-1} != 0} 2^{N Psi(B_{N-1})} ] <= 2^{o(N)}.
--------------------------------------------------------------------------
2.3 A and B imply Lemma 1.6
--------------------------------------------------------------------------
Fix any A > 0. On the typical set of Proposition A use its bound; off
that set (probability <= 2^{-N f(N)}, f(N) -> infinity) use the trivial
|S(B)| <= 2^N. Then
E|S(B_{N-1})|
<= 2^{N l^{-A}} E[ 1_{det != 0} 2^{N Psi(B_{N-1})} ] + 2^{N - N f(N)}
<= 2^{N l^{-A}} * 2^{o(N)} + 2^{N - N f(N)}
= 2^{o(N)}.
That is Lemma 1.6. (The first inequality uses |S(B)| <= 2^N off the
typical set, and the second uses Proposition B for the main term and the
tiny exceptional probability for the rest.) QED
So it remains to prove Proposition A (Sections 3-6) and Proposition B
(Sections 7-11). Proposition A is static: it holds for almost every B
individually. Proposition B is dynamic: it is proved by building B from
a tiny principal minor.
--------------------------------------------------------------------------
2.4 What beta = 7/5 does (read this before the hard sections)
--------------------------------------------------------------------------
Two separate inequalities pin down the height-two weight beta = phi(2):
(i) In Section 6 (coloring) each height-two layer can be offset by a
factor of at most 2^{5/4 nu_p}, so we need beta >= 5/4.
(ii) In Section 10 (the local potential step) the potential is allowed
to grow, but the scalar optimization there needs beta <= 7/5 to
close with the budgets (2.1).
Anything in [5/4, 7/5] works; we fix beta = 7/5, the top of the range,
because inequality (ii) is the tight one. If you only want the shape of
the proof, treat beta as a fixed constant in this window.
==========================================================================
3. LATTICE TOOLS
==========================================================================
This section collects reusable facts. Two uses later:
(L1) counting short vectors in a lattice after removing a direction of
small determinant (the Reverse Minkowski theorem);
(L2) showing that a large robust set of cube points has difference span
of controlled "height" (the determinant of a robust image lattice).
Throughout, "lattice" means discrete subgroup of a Euclidean space,
taken inside its real span.
--------------------------------------------------------------------------
3.1 Determinants, quotients, heights, normal lattices
--------------------------------------------------------------------------
Let L be a lattice with real span E = span L and rank r = dim E. If
b_1,...,b_r is a Z-basis its determinant (covolume) is
det L = det( (<b_i,b_j>)_{i,j=1..r} )^{1/2}, det{0} = 1.
A sublattice M <= L may have smaller rank. Its SATURATION is
M-bar = L ∩ span M, a lattice of the same rank, with
det M = [M-bar : M] * det M-bar.
M is PRIMITIVE (saturated) if M = M-bar; then a basis of M extends to a
basis of L. The dual is taken in the span:
L* = { y in E : <y,x> in Z for all x in L }.
Lemma 3.1 (orthogonal lattice quotients). Let L have rank r and span E,
and let K <= L be primitive of rank k with F = span K. Let pi_{F^perp}
be orthogonal projection of E onto E ∩ F^perp. Then the Euclidean model
L/K := pi_{F^perp}(L)
of the abstract quotient is a lattice of rank r-k, and
det L = det K * det(L/K), det L* = 1/det L,
(L/K)* = L* ∩ F^perp, K* = pi_F(L*) (pi_F onto F).
For a sublattice M <= L/K, the full preimage M~ = {x in L : pi_{F^perp}x in M}
has rank k + rank M and det M~ = det K * det M. All statements include
the cases k = 0, k = r, r = 0, with rank-zero determinants equal to 1.
Proof. Extend a basis b_1,...,b_k of K to a basis b_1,...,b_r of L. The
projections pi_{F^perp} b_{k+1},...,pi_{F^perp} b_r are a basis of the
projected lattice; splitting Euclidean volume into the F-factor and the
F^perp-factor gives det L = det K * det(L/K). The Gram matrix of the dual
basis is the inverse Gram matrix, giving det L* = 1/det L.
For y in E ∩ F^perp, <y, pi_{F^perp} x> = <y,x>, so (L/K)* = L* ∩ F^perp.
pi_F(L*) <= K*; conversely given w in K*, prescribe on the basis of L the
values <w,b_i> for i <= k and 0 for i > k; the representing vector lies in
L* and projects to w. This proves K* = pi_F(L*). Finally lift a basis of
M and adjoin the basis of K; the resulting basis of M~ gives rank and, by
the same volume factorization, det M~ = det K * det M. Empty bases give
the rank-zero cases. QED
A subspace W <= R^m is RATIONAL if spanned by integer vectors. Its
integer lattice is Lambda_W = W ∩ Z^m (rank dim W), and its HEIGHT is
H(W) = det Lambda_W, h(W) = log_N H(W).
Thus H({0}) = H(R^m) = 1.
Lemma 3.2 (height submodularity). For rational U, V <= R^m,
H(U+V) H(U ∩ V) <= H(U) H(V), i.e. h(U+V)+h(U∩V) <= h(U)+h(V).
Also H(W) >= 1 for every rational W, and for fixed m and C there are only
finitely many rational W <= R^m with H(W) <= C.
Proof. Put J = U ∩ V and project off J. Lambda_J = Lambda_U ∩ Lambda_V
is primitive in each of Lambda_U, Lambda_V, Lambda_U + Lambda_V (if
u + v in J with u in Lambda_U, v in Lambda_V then u,v in J). The projected
spans of U and V meet trivially, so the union of bases of the projected
lattices is a basis of their sum, and projecting the second off the first
only shrinks volume:
det(Lambda_U + Lambda_V projected) <= det Lambda_U * det Lambda_V.
Lemma 3.1 then gives det(Lambda_U + Lambda_V) * det Lambda_J <=
det Lambda_U * det Lambda_V. Saturating (Lambda_U + Lambda_V) to
Lambda_{U+V} can only shrink. For H(W) >= 1: wedge a basis of Lambda_W;
the resulting vector in (wedge)^r Z^m has norm H(W) and nonzero integer
coordinates, so H(W) >= 1; a ball contains finitely many such and there
are m+1 ranks. QED
For a coordinate vector e_i both intersections U ∩ R e_i have height 1,
so Lemma 3.2 also gives H(U + R e_i) <= H(U).
Lemma 3.3 (normal lattices and height). Let V <= U <= R^m be rational and
put Lambda = Lambda_U*. The primitive normal lattice
N_U(V) = Lambda ∩ V^perp
has rank dim U - dim V and
pi_V(Lambda) = Lambda_V*, det N_U(V) = H(V)/H(U).
More generally for any sublattice M <= Lambda, set V_M = U ∩ (span M)^perp
(rational). Then
det M = [N_U(V_M) : M] * H(V_M)/H(U) >= 1/H(U).
Proof. Lambda_V is primitive in Lambda_U, so Lemma 3.1 gives
pi_V(Lambda_U*) = Lambda_V*; its kernel is N_U(V), primitive of the stated
rank. Factoring det Lambda_U* = 1/H(U) along this kernel:
1/H(U) = det N_U(V) * det Lambda_V* = det N_U(V)/H(V).
For the general part: an integer basis matrix of Lambda_U has a rational
dual basis (invert its Gram matrix), so span M and V_M are rational. The
saturation of M in Lambda is exactly N_U(V_M); the index formula plus the
first part gives the display, and H(V_M) >= 1 gives the inequality. QED
--------------------------------------------------------------------------
3.2 Gaussian mass, Reverse Minkowski, deterministic removal
--------------------------------------------------------------------------
For a lattice L and s > 0, the Gaussian mass is
rho_s(L) = sum_{x in L} exp(-pi ||x||^2 / s^2), rho_s({0}) = 1.
We use the following scaled form of the Reverse Minkowski theorem of
Regev and Stephens-Davidowitz.
Theorem 3.4 (Reverse Minkowski, scaled). Let L have rank j >= 1 and let
T > 0. Suppose det M >= T^{rank M} for every sublattice M <= L. With
tau_j = 10(log j + 2),
rho_{T/tau_j}(L) <= 3/2.
(Rank zero: rho_s({0}) = 1 for all s.)
Proof. Apply the cited theorem to T^{-1}L in its span; every rank-t
sublattice of T^{-1}L has determinant >= 1, and
rho_{1/tau_j}(T^{-1}L) = rho_{T/tau_j}(L). QED
Here tau_j is bounded above and below by absolute multiples of log(2j).
Lemma 3.5 (Gaussian point counts). Let L have rank j. For R >= 0, s > 0,
#{x in L : ||x|| <= R} <= exp(pi R^2/s^2) rho_s(L),
and for s' >= s > 0, rho_{s'}(L) <= (s'/s)^j rho_s(L). In particular
under the hypothesis of Theorem 3.4, with s_0 = T/tau_j, for every u >= s_0,
#{x in L : ||x|| <= R} <= (3/2)(u/s_0)^j exp(pi R^2/u^2).
Rank zero: point count and all Gaussian masses are 1.
Proof. A point of norm <= R contributes at least exp(-pi R^2/s^2) to
rho_s(L), giving the first bound. The Gaussian Poisson formula in span L is
rho_s(L) = (s^j/det L) rho_{1/s}(L*); monotonicity of the Gaussian mass in
scale applied to 1/s' <= 1/s proves the second bound. The last bound uses
the first at scale u, then the second and Theorem 3.4. Rank zero reads
1 = 1. QED
The next lemma is the deterministic way to reach the hypothesis of
Theorem 3.4: remove one sublattice minimizing a normalized determinant.
Lemma 3.6 (determinant-minimizing sublattice). Let L be a lattice and
T > 0. The quantity det M / T^{rank M} over sublattices M <= L attains a
minimum at a primitive sublattice L_0, with
det L_0 <= T^{rank L_0}, det M >= T^{rank M} for all M <= L/L_0.
If moreover T_0 > T, Delta >= 0, and det M >= e^{-Delta} T_0^{rank M} for
all M <= L, then rank L_0 <= Delta / log(T_0/T). (For L = {0}: L_0 = {0}.)
Proof. The rank-zero lattice has normalized determinant 1. For a fixed
rank t, det M is the norm of the wedge of a basis in the discrete lattice
(wedge)^t L, and there are only finitely many such norms <= T^t; so among
normalized determinants <= 1 there are finitely many values and a minimum
exists. Saturating a minimizer only lowers its determinant at fixed rank,
so a primitive minimizer exists, and comparison with rank 0 gives
det L_0 <= T^{rank L_0}. For M <= L/L_0 lift to M~ (Lemma 3.1); minimality
of L_0 gives det L_0 / T^{rank L_0} <= det L_0 det M / T^{rank L_0 + rank M},
proving the quotient bound. Under the extra hypothesis write k = rank L_0;
the two bounds on det L_0 give e^{-Delta} T_0^k <= T^k; take logs. QED
--------------------------------------------------------------------------
3.3 Robust subsets and the determinant of a robust image lattice
--------------------------------------------------------------------------
Let A be a nonempty finite set with affine span F. For rho > 0 call A
RHO-ROBUST if every affine subspace E <= F of codimension t satisfies
|A ∩ E| <= 2^{-rho t} |A|.
Equivalently: no low-dimensional slice captures a large fraction of A.
Robustness is preserved by injective affine maps (they preserve
codimension on the affine span).
Lemma 3.7 (robust cube extraction). Let empty != A <= bits^m, rho > 0,
d = dim aff A. There is an affine restriction A_0 = A ∩ F, F = aff A_0 of
dimension r, such that A_0 is rho-robust and
log_2|A| - rho(d-r) <= log_2|A_0| <= log_2|A|, and log_2|A_0| <= r.
For any fixed a_0 in A_0, the number of ordered r-tuples
(a_1,...,a_r) in A_0^r for which a_1 - a_0,...,a_r - a_0 are independent
is at least
|A_0|^r prod_{t=1}^{r}(1 - 2^{-rho t}) >= ((1 - 2^{-rho})|A_0|)^r.
(Rank zero: A_0 is a singleton; one empty tuple.)
Proof. Among all nonempty affine restrictions Q of A pick one maximizing
|Q| 2^{-rho dim aff Q} (finitely many distinct restrictions). Replacing
the restricting space by aff Q does not change the restriction, so write
the maximizer as A_0 = A ∩ F, F = aff A_0. Comparison with A = A gives
log_2|A_0| >= log_2|A| - rho(d - r).
Now let E <= F have codimension t. If A_0 ∩ E is nonempty its affine span
has dimension <= r - t and it is again an affine restriction of A; by
maximality |A_0 ∩ E| 2^{-rho dim aff(A_0 ∩ E)} <= |A_0| 2^{-rho r}, which is
exactly the robustness bound (empty intersections satisfy it too).
|A_0| <= 2^r: choose r coordinate functionals independent on the direction
space of F; projection to those coordinates is injective on F and maps A_0
into bits^r. For the tuple count: after i independent differences are
chosen, their affine span with a_0 has codimension r - i in F, so
robustness leaves at least (1 - 2^{-rho(r-i)})|A_0| choices for the next
point; multiply for i = 0,...,r-1. Empty product proves rank zero. QED
The next lemma is the sole metric input used to bound the height of a
difference span. Its affine-image form will apply to graph lattices.
Lemma 3.8 (determinant of a robust image lattice). Fix D > 0 and C_0 > 0.
For all large N put rho = l^{-D}. Let m <= N, let empty != A <= bits^m be
rho-robust on its affine span F of dimension r, and let
Phi : F -> R^d be an injective rational affine map (maps rational points
of F to rational points of R^d). Suppose
||Phi(a) - Phi(b)|| <= C_0 sqrt(N) for all a,b in A.
Then for any a_0 in A, the group
L_Phi = sum_{a in A} Z (Phi(a) - Phi(a_0))
is a rank-r lattice independent of a_0, and
det L_Phi <= exp(O_{D,C_0}(N l)).
In particular, with W = span(A - A),
H(W) <= exp(O_D(N l)).
(Rank zero: both lattices have rank zero and determinant 1.)
Proof. The finitely many image differences are rational vectors, so they
have a common denominator; their integer span sits in a scaled copy of
Z^d and is discrete. The linear part of Phi is injective on the direction
space of F, so L_Phi has rank r; changing a_0 does not change the group.
Rank zero is immediate; assume r >= 1.
Set T = (log N)^4 and choose L_0 <= L_Phi by Lemma 3.6. Let
Gamma = L_Phi / L_0 (orthogonal quotient) with rank j = r - rank L_0. Every
sublattice M <= Gamma has det M >= T^{rank M}, and det L_0 <= T^{rank L_0}.
Fix a_0 and project Phi(a) - Phi(a_0) into Gamma; these have norm at most
C_0 sqrt(N). If j >= 1, Lemma 3.5 at scale T/tau_j bounds the number M of
distinct projections by
M <= (3/2) exp(pi C_0^2 N tau_j^2 / T^2) <= 2^{O_{C_0}(N/(log N)^6)},
using j <= r <= N so tau_j = O(log N); same bound if j = 0 (then M = 1).
The preimage in F of one projection fiber is an affine subspace of
codimension j. A largest fiber has at least |A|/M points, while robustness
bounds it by 2^{-rho j}|A|. Hence
j <= (log_2 M)/rho = O_{C_0}( N l^D / (log N)^6 ).
The projected differences generate Gamma. Choose j independent ones;
their integer span is a full-rank sublattice of Gamma, so the index
formula and Hadamard give det Gamma <= (C_0 sqrt N)^j (and 1 = 1 if j = 0).
Factoring the determinant along L_0,
det L_Phi <= T^{r-j} (C_0 sqrt N)^j,
log det L_Phi <= 4 N l + O_{C_0}( N l^D / (log N)^5 ).
For fixed D the error is o(N l), proving the determinant bound.
For the identity map the differences have norm <= sqrt(m) <= sqrt(N), and
L_Phi is a full-rank sublattice of W ∩ Z^m; saturating only decreases the
determinant, giving H(W) <= det L_Phi and the height bound. QED
==========================================================================
4. A FINITE COVER FOR SUBSPACES OF CONTROLLED HEIGHT
==========================================================================
Lemmas 3.7 and 3.8 turn a large subset of bits^m into a robust subset
whose difference span W satisfies H(W) <= exp(O(N l)). That W depends on
the matrix at hand, so a rank estimate for one fixed space is useless. We
replace every eligible W by a small fixed list, moving ranks only a little.
For rational U, V <= R^m define the rank distance
d(U,V) = dim U + dim V - 2 dim(U ∩ V),
the sum of the codimensions of U ∩ V in U and in V. Recall the height
H(U) = det(U ∩ Z^m), H(0) = 1. Note d(U^perp, V^perp) = d(U,V): passing
through the common subspace U^perp ∩ V^perp shows that the nullity of a
fixed symmetric form on U^perp x U^perp and on V^perp x V^perp, and the
rank of columns projected to these spaces, differ by O(d(U,V)). This is
how fixed-space rank estimates transfer to any W near a cover member.
Theorem 4.1 (low-height cover). Fix D, A > 0. For all large N and every
0 <= m <= N there is a list C_{m,N} of rational subspaces of R^m
(depending also on D, A) with
|C_{m,N}| <= 2^{N^2 l^{-A}},
such that every rational W <= R^m with H(W) <= exp(N l^D) satisfies
min_{U in C_{m,N}} d(U,W) <= N l^{-A}.
Proof. Choose a fixed B_0 > D + A + 2 and put
a = l^{-B_0}, h(U) = log_N H(U), Delta = N l^D / (a log N).
Throughout N is large in terms of the fixed parameters, so a = o(1) and
1/log N = o(a). We will encode, for each eligible W, a space within
distance Delta of W, using o(N^2 l^{-A}) bits; the decoded spaces are the
list. 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 a normal lattice encodes each drop, and
minimizing inequalities keep the number of costly encodings small.
-- The minimizing chain. --
Let r = dim W. Choose r pivot coordinates on which coordinate projection
is an isomorphism on W, write W as a graph over these coordinates, and
impose the nonpivot coordinate equations one at a time. This gives
R^m = P_0 > P_1 > ... > P_{m-r} = W,
with P_{s-1} = P_s (+) R e at one coordinate vector e per step; every
coordinate vector whose equation is not yet imposed lies in P_s.
For each s minimize F_s(U) = h(U) + a d(U, P_s) over rational U; let E_s
be the minimum and U_s the greatest minimizer under inclusion. (H(U) >= 0,
only finitely many rational U have H(U) <= N^{am}, and testing U = 0 shows
a minimizer exists in that finite range.) By Lemma 3.2 and
d(U+V,P) + d(U∩V,P) <= d(U,P) + d(V,P),
the sum and intersection of two minimizers are minimizers; as there are
finitely many, their sum is the greatest. Also U_0 = R^m, E_0 = 0. (The
displayed inequality comes from the dimension formula and
(U∩P)+(V∩P) <= (U+V)∩P.)
The minimizers descend. If P' <= P then
d(U+V,P) + d(U∩V,P') <= d(U,P) + d(V,P'),
because (U∩P)+(V∩P') <= (U+V)∩P and the two summands meet in U∩V∩P'.
With U = U_{s-1}, V = U_s and Lemma 3.2 this gives
F_{s-1}(U_{s-1}+U_s) + F_s(U_{s-1}∩U_s) <= E_{s-1} + E_s,
and minimality forces equality, so U_{s-1}+U_s is an old minimizer and,
by greatestness, U_s <= U_{s-1}.
Every unprocessed coordinate vector e in P_s belongs to U_s: by Lemma 3.2
(with H(R e) = 1, H(U ∩ R e) >= 1) H(U+R e) <= H(U), so if e were not in U
adjoining it would decrease d(U,P_s) by one, contradicting minimality.
The energies are nondecreasing: for a step P_{s-1} = P_s (+) R e,
d(U+R e, P_{s-1}) <= d(U,P_s)
(the new intersection contains (U∩P_s)(+)R e while both dim U and dim P_s
grow by at most one), so applying the height inequality to U = U_s gives
E_{s-1} <= E_s.
Testing F_{m-r} at W gives E_{m-r} <= h(W), hence
d(U_{m-r}, W) <= h(W)/a <= Delta.
Write c_s = dim U_{s-1} - dim U_s for the drop at step s, and let z count
steps with c_s = 0. At such a step the minimizers coincide and contain
the processed vector e; their intersection with P_s has codimension one
more than with P_{s-1}, so E_s - E_{s-1} = a, giving z <= h(W)/a. If
dim U_{m-r} = r + theta, the distance bound gives |theta| <= h(W)/a, and
summing drops gives sum_s c_s = m - r - theta. Over the m-r steps,
sum_{s: c_s >= 2} (c_s - 1) = z - theta <= 2 h(W)/a,
so
sum_{s: c_s >= 2} c_s <= 4 h(W)/a <= 4 Delta. (4.1)
-- Normal flags for a transition. --
Now count the choices for one transition U_old >= U_new of drop c >= 1,
assuming U_old known. Let P_old > P_new be the graph spaces and set
Lambda = (U_old ∩ Z^m)*
in the span U_old, and K = Lambda ∩ U_new^perp: a primitive rank-c
sublattice of Lambda determining U_new. For rational V <= U_old,
Lemma 3.3 gives det(Lambda ∩ V^perp) = H(V)/H(U_old).
If V has codimension t in U_old, the rank distances of V and U_old to a
fixed space differ by at most t; comparing V with the old minimizer and
saturating a sublattice of Lambda gives
h(V) - h(U_old) >= a( d(U_old,P_old) - d(V,P_old) ) >= -a t,
so det L >= N^{-a rank L} for every sublattice L <= Lambda. If
K' <= K is primitive of rank t, it is the normal lattice of a rational V'
with U_new <= V' <= U_old; the normal-height identity and comparison with
the new minimizer give
h(U_new) - h(V') <= a( d(V',P_new) - d(U_new,P_new) ) <= a(c - t).
Hence
det K / det K' = H(U_new)/H(V') <= N^{a(c-t)}. (4.2)
Choose a saturated flag 0 = K_0 < K_1 < ... < K_c = K
inductively: in the projected quotient K/K_{i-1} take a shortest nonzero
vector v_i, mu_i = ||v_i||, K_i/K_{i-1} = Z v_i. Each shortest vector is
primitive, so each K_i is primitive in K, hence in Lambda. Put
y_i = log_N mu_i. The determinant identity (Lemma 3.1) and (4.2) give,
for every suffix,
sum_{j=i}^{c} y_j <= a(c - i + 1). (4.3)
Minkowski's shortest-vector bound in rank u, lambda_1(L) <= C sqrt(u)
(det L)^{1/u}, applied to K_{i+u-1}/K_{i-1} (v_i is shortest even in the
larger K/K_{i-1}), gives
y_i <= (1/u) sum_{j=i}^{i+u-1} y_j + (1/2) log_N u + O(1/log N),
1 <= u <= c-i+1. (4.4)
A full suffix in (4.4) gives y_i <= 1/2 + a + O(1/log N), in particular
y_i <= 1. Call position i EXPENSIVE if y_i > 1/2 - 3a.
Claim: a flag of length c has O(ac) expensive positions and none when c=1.
For c=1, (4.3) gives y_1 <= a < 1/2 - 3a. In general suppose an expensive
position exists and split the suffix from the first such position into
ranges, each beginning at an expensive position and ending just before the
next one (or at the end). For a range of length u, (4.4) gives
sum_{range} (y_j - a) >= u( 1/2 - 4a - (1/2) log_N u - O(1/log N) ).
For u <= N^{2/5} this is >= u/5 for large N; for every u <= N it is
>= -C_1 a u, since 1/log N = o(a). The total over ranges is nonpositive
by (4.3). So the total length of short ranges is O(ac); there are at most
c / N^{2/5} = o(ac) long ranges. This proves the claim.
-- Counting flag vectors. --
Count the vector at each flag position in a quotient fixed by the earlier
choices. Put Pi = Lambda / K_{i-1}. A rank-t sublattice Lbar of Pi
lifts, with K_{i-1}, to a rank-(t+i-1) sublattice of Lambda; by Lemma 3.1,
the first balance bound, and det K_{i-1} = prod_{j<i} mu_j <= N^c,
det Lbar >= N^{-a(t+i-1)}/det K_{i-1} >= N^{-a t - 2c}. (4.5)
Apply Lemma 3.6 to Pi with T = N^{-2a}, fixing the minimizing primitive
sublattice L_0 deterministically (no encoding cost once Pi is known).
If j_0 = rank L_0, comparison with the zero lattice and (4.5) give
N^{-a j_0 - 2c} <= det L_0 <= N^{-2a j_0}, hence j_0 <= 2c/a. Every
sublattice of Omega = Pi / L_0 has det >= N^{-2a} to its rank.
First encode the image of v_i in Omega (unique if rank 0). Since rank
Omega <= N, Lemma 3.5 applies at the common scale
s_0 = N^{-2a}/(C_2 log(2N)). At an inexpensive position mu_i <= N^{1/2-3a},
and projection does not increase norm, so the number of images has
base-two logarithm at most
O(1 + N^{1-2a} log^2 N). (4.6)
At an expensive position y_i <= 1/2 + a, a common radius R = C_3 N^{1/2+a}
suffices; the Gaussian comparison from s_0 to s_1 = R/sqrt N (>= s_0 for
large N) with k = rank Omega <= N bounds the logarithm of the count by
O(1) + O(R^2/s_1^2) + k log_2(s_1/s_0)
<= O(N) + O(N(a log N + log log N)) = O(a N log N),
using R^2/s_1^2 = N, s_1/s_0 = O(N^{3a} log N), and a log N >> log log N.
It remains to count vectors of Pi above one fixed image in Omega that have
norm <= R = C_3 N^{1/2+a}. Call this set V. Its differences lie in L_0;
let F be their real span, of dimension j <= j_0 <= 2c/a and j <= N. The
lattice L_F = Pi ∩ F has rank j and, by (4.5), det L_F >= N^{-aj-2c}. If
j = 0 then |V| <= 1. Otherwise choose j independent differences in V,
each of norm <= 2R, with integer span L' <= L_F, and fix v_0 in V. The
translates of a fundamental parallelepiped of L', over the
[L_F : L'] = det L'/det L_F cosets in v_0 + L_F, are disjoint up to
boundaries and lie in the ball of radius 2(1+j)R, so
|V| <= vol_j B_j(2(1+j)R) / det L_F.
The numerator has logarithm O(j log N) (as j <= N, R polynomial), so
log_2 |V| <= O((j + c) log N) = O((c/a) log N). (4.7)
This is uniform over the fixed image and the earlier flag choices.
The image and fiber choices specify v_i in Pi, hence a lift in Lambda, and
then K_i = Lambda ∩ span(K_{i-1}, v~_i); this reconstructs the next
quotient and ultimately K, hence U_new.
-- Total encoding cost. --
Sum the costs. Pivot and coordinate order, drops, and expensive positions
cost O(N log N) bits. There are at most N flag positions total (the drops
sum to at most m). With S = sum_{s: c_s >= 2} c_s <= 4 Delta by (4.1), the
expensive-position count is O(a S) over the chain (none in drops of size
one), and a drop c has c fiber costs totaling O(c^2 log N / a). Since
sum_{s: c_s >= 2} c_s^2 <= S^2, the full base-two logarithm is
O(N log N) + O(N(1 + N^{1-2a} log^2 N)) + O(a^2 N log N * S)
+ O((log N / a)(S^2 + N))
<= O(N^2 N^{-2a} log^2 N) + O(a N^2 l^D)
+ O(N^2 l^{2D}/(a^3 log N)) + O(N log N / a).
Each term is o(N^2 l^{-A}): the first because
N^{-2a} log^2 N = exp(-2 log N / l^{B_0} + 2 l) = o(l^{-A}); the second
because a l^D = l^{D-B_0} = o(l^{-A}); the third because
l^{2D}/(a^3 log N) = l^{2D+3B_0}/log N = o(l^{-A}); the fourth because
l^{B_0} log N / N = o(l^{-A}). All exponents are fixed before N grows.
Collect the terminal spaces decoded by all encodings, removing duplicates:
a list independent of W, of size <= 2^{N^2 l^{-A}} for large N. Every
eligible W has an encoding whose terminal space satisfies
d(U_{m-r}, W) <= Delta = N l^{D+B_0}/log N = o(N l^{-A}),
uniformly for m <= N. QED
==========================================================================
5. TYPICAL RANK AND SPECTRAL PROPERTIES
==========================================================================
Three properties of a random binary matrix, each failing with probability
2^{-N f(N)}, f(N)->infinity: ranks on low-height subspaces (5.1), coranks
modulo every prime (5.2), and few eigenvalues near zero (5.3). The rank
properties are uniform over all rational W with H(W) <= exp(N l^D), which
is where Theorem 4.1 enters; the spectral one uses concentration.
For real symmetric B and a subspace U <= R^m, write B|_U for the form
(u,v) -> u^T B v on U x U, with nullity dim U - rank(B|_U). pi_U is
orthogonal projection onto U, and E_X = span{e_i : i in X} for X <= [m].
--------------------------------------------------------------------------
5.1 Uniform rank tests
--------------------------------------------------------------------------
Lemma 5.1 (finite-field rank). Let B be a uniform symmetric bilinear form
on F_2^m (independent diagonal entries), and S, T subspaces of dimensions
b, a with b <= a. For 1 <= t <= b,
Pr( rank(B|_{S x T}) <= b - t ) <= C_0 2^{-t(t+1)/2}, (5.1)
with an absolute constant C_0.
Proof. Such a deficiency gives a t-dimensional subspace K <= S with
B(K,T) = 0. The number of K is the Gaussian binomial
binomial(b,t)_2 = 2^{t(b-t)} prod_{i=0}^{t-1}(1-2^{i-b})/(1-2^{i-t})
<= C_0 2^{t(b-t)}, C_0 = prod_{j>=1}(1-2^{-j})^{-1}.
For a fixed K, let e = dim(K ∩ T). Choose a basis of the intersection,
extend it separately to bases of K and T, then extend their union to a
basis of F_2^m. A change of basis keeps the symmetric form uniform. In
this basis B(K,T) = 0 imposes ta - C(e,2) independent linear conditions on
the entries of the form: there are ta entries before using symmetry, and
the only repetitions are the two orders of each off-diagonal pair inside
K ∩ T (diagonal entries there stay independent, also in characteristic
two). Since e <= t and a >= b, this is at least tb - C(t,2). A union
bound over K and (5.1) follow; the event is empty if t > b. QED
Proposition 5.2 (uniform low-height rank tests). For every fixed D, A > 0
there is f_{D,A}(N) -> infinity such that, for every m in I_N and all
large N, with probability >= 1 - 2^{-N f_{D,A}(N)} for B = B_m, there
holds simultaneously for every rational W <= R^m with H(W) <= exp(N l^D):
(1) dim W^perp - rank(B|_{W^perp}) <= N l^{-A};
(2) for every coordinate set X <= [m],
rank[ pi_{W^perp} B e_i ]_{i in X} >= min{|X|, m - dim W} - N l^{-A}.
All ranks and projections are over R; B need not be nonsingular.
Proof. For rational U, the lattice U ∩ Z^m is primitive in Z^m, so an
integer basis matrix C_U has full column rank mod 2 (a primitive basis
extends to a basis of Z^m). For rational U, V the tested matrix is the
integer matrix C_U^T B C_V; its real rank is >= its mod-2 rank, since a
nonzero minor mod 2 is odd, hence nonzero. And B mod 2 is uniform among
symmetric matrices over F_2. So (5.1) applies to the reductions of the
column spaces of C_U, C_V (same dimensions as U, V). After reduction
U ∩ V can only grow, and the intersection correction in (5.1) covers this.
The tests are U = V and V = E_X. In the second case, using that C_U^T
annihilates U^perp and is an isomorphism U -> R^{dim U},
rank[ pi_U B e_i ]_{i in X} = rank(C_U^T B C_{E_X}).
Stability when the testing space changes: for fixed B and X define
delta_0(U) = dim U - rank(B|_U),
delta_X(U) = min{|X|, dim U} - rank(C_U^T B C_{E_X}).
Restricting to Z <= U deletes dim U - dim Z rows and the same number of
columns, so the rank drops by between 0 and twice that, giving
|delta_0(U) - delta_0(Z)| <= dim U - dim Z,
|delta_X(U) - delta_X(Z)| <= dim U - dim Z.
With Z = U ∩ V this yields
|delta_0(U) - delta_0(V)| <= d(U,V), |delta_X(U) - delta_X(V)| <= d(U,V).
(5.2)
Fix D, A, put s = N l^{-A}, and apply Theorem 4.1 with precision P = 2A+4.
For each m in I_N it gives a list C_m with |C_m| <= 2^{N^2 l^{-P}} and
min_{V in C_m} d(W,V) <= N l^{-P} for every W in the height range. Set
t = ceil(s/2). Apply (5.1) to U = V^perp for every V in C_m, both to its
restricted form and against every E_X. By the real/mod-2 rank comparison,
the probability that any of these deficiencies is >= t is at most
C_0(1+2^m) 2^{N^2 l^{-P} - t(t+1)/2} <= 2^{-Omega(N^2 l^{-2A})},
since N^2 l^{-P} = o(N^2 l^{-2A}) and m = o(N^2 l^{-2A}).
Off this event, choose a covering V for a given W; (5.2) (applied to the
orthogonal complements) bounds each deficiency for W by
t - 1 + N l^{-P} < s for large N, simultaneously in all W and X. Finally
N l^{-2A} -> infinity, so the exceptional probability has the required
form. QED
Corollary 5.3 (inverse restriction rank). For every D, A > 0, typically
for nonsingular B of size m in I_N, simultaneously for every rational W
with H(W) <= exp(N l^D),
rank(B^{-1}|_W) >= dim W - N l^{-A}.
Proof. The two radicals are
rad(B|_{W^perp}) = W^perp ∩ B^{-1} W,
rad(B^{-1}|_W) = W ∩ B(W^perp),
and B is an isomorphism from the first to the second with inverse B^{-1},
so their dimensions agree. Proposition 5.2(1) gives the claimed rank for
the inverse form on the same typical set. QED
--------------------------------------------------------------------------
5.2 Corank modulo all primes
--------------------------------------------------------------------------
For nonsingular B and any prime p, the presentation of G_B gives
k_B(p,1) = dim_{F_p}(G_B/pG_B) = corank_{F_p}(B mod p),
the minimal number of generators of the p-primary part; also
k_B(p,e) <= k_B(p,1). A uniform bound on these coranks caps layer heights
and the generators of quotients of G_B.
Proposition 5.4 (uniform prime corank). Typically for nonsingular B of
size m in I_N, simultaneously for every prime p,
corank_{F_p}(B mod p) <= N^{3/5}.
More precisely, uniformly for m in I_N, the probability of nonsingularity
together with failure is at most 2^{-Omega(N^{6/5})}.
Proof. If B is nonsingular over R, det B is a nonzero integer, and every
prime p with positive corank divides it. Hadamard gives
1 <= |det B| <= m^{m/2} <= N^{N/2}, so only p <= N^{N/2} matter. For each,
Lemma 1.3 (field F_p) bounds the probability of corank > N^{3/5} by
2^{-c N^{6/5}} uniformly in p and m. Union over at most N^{N/2} primes:
2^{(N/2) log_2 N - c N^{6/5}} <= 2^{-c N^{6/5}/2}
for large N. QED
--------------------------------------------------------------------------
5.3 Few eigenvalues near zero
--------------------------------------------------------------------------
Proposition 5.5 (typical small-spectrum bound). For every fixed A > 0
there is a fixed C_A > 0 (one may take C_A = A + 6) and f_A(N) -> infinity
such that, for every m in I_N and all large N, with probability >=
1 - 2^{-N f_A(N)}, the number of eigenvalues of B = B_m in
[ -sqrt(N) l^{-C_A}, sqrt(N) l^{-C_A} ]
is at most N l^{-A} (counted with multiplicity). No nonsingularity needed.
Proof. MEAN BOUND. Let J_m be the all-ones matrix and write
2B = J_m + S, X = S/sqrt(m),
so S has independent uniform signs on and above the diagonal. We bound
the count of eigenvalues of X near 0 using Wigner's semicircle law
dmu_sc(x) = (1/2pi) sqrt(4 - x^2) 1_{[-2,2]}(x) dx.
Closed-walk enumeration gives, for i >= 1 with i+1 <= m,
| (1/m) E Tr X^{2i} - int x^{2i} dmu_sc | <= (2i+1)^{2i+2}/m,
E Tr X^{2i-1} = 0. (5.3)
Indeed, m^{-1-k/2} E Tr X^k expands over closed walks v_0...v_{k-1}; the
expectation is 1 iff every edge is used an even number of times, else 0,
which proves the odd assertion. For k = 2i a contributing walk has at
most i distinct edges, and its graph is connected, hence has at most i+1
vertices. Equality forces i nonloop edges each used twice, forming a
tree; named in order of first appearance these are in bijection with Dyck
words of length 2i, so there are Catalan_i = (i+1)^{-1} C(2i,i) of them,
each with (m)_{i+1} injective labelings. Their contribution differs from
Catalan_i by at most Catalan_i i(i+1)/(2m). Every remaining contributing
walk has at most i vertices; there are at most (2i+1)^{2i} canonical
vertex sequences, each with at most m^i labelings, so it contributes at
most 1/m after normalization. Finally int x^{2i} dmu_sc = (2i)!/(i!(i+1)!)
= Catalan_i, and the odd moments vanish. Combining and using
Catalan_i <= 4^i gives (5.3).
Fix A and put
w = l^{-A-5}, j = ceil(l^{2A+4}), f(x) = (1 - |x|/w)_+,
p_j(x) = 2(1 - x^2/16)^{2j}.
For large N, f <= p_j pointwise. Outside [-w,w] this is nonnegativity of
the even power; inside, Bernoulli's inequality gives
p_j(x) >= 2(1 - w^2/16)^{2j} >= 2(1 - j w^2/8) >= 1 >= f(x), since
j w^2 = O(l^{-6}). All moments of p_j have degree <= 4j and 2j+1 <= m,
uniformly in m in I_N. Expanding p_j and applying (5.3) term by term
(the coefficients have absolute sum 2(17/16)^{2j}),
| (1/m) E Tr p_j(X) - int p_j dmu_sc |
<= 2(17/16)^{2j}(4j+1)^{4j+2}/m = m^{-1+o(1)},
because j log(j+1) = O_A(l^{2A+4} log l) = o(log m). This error is
o(l^{-A}). Since (1-x^2/16)^{2j} <= exp(-j x^2/8) on [-2,2] and the
density is <= 1/pi,
int p_j dmu_sc <= (2/pi) int exp(-j x^2/8) dx = O(j^{-1/2}) = O(l^{-A-2}).
The pointwise majorization then gives
E Tr f(X) = o(m l^{-A}), (5.4)
uniformly in m.
CONCENTRATION. Pointwise f = 1 - g_1 + g_2 with g_1(x) = |x|/w and
g_2(x) = (|x|/w - 1)_+; both are convex and 1/w-Lipschitz. Their matrix
traces are convex functions of a real symmetric matrix: writing M_+ for
the spectral positive part, Tr M_+ = max_{0<=P<=I} Tr(P M), and
Tr g_1(M) = w^{-1}(Tr M_+ + Tr(-M)_+),
Tr g_2(M) = Tr(M/w - I)_+ + Tr(-M/w - I)_+,
sums of suprema of affine functions of M.
Let y = (y_{ab})_{a<=b} be independent real coordinates and form
X(y) = S(y)/sqrt(m). The Hoffman-Wielandt inequality with ordered
eigenvalues gives
sum_i |lambda_i(M) - lambda_i(M')|^2 <= ||M - M'||_F^2;
by Cauchy-Schwarz, for a = 1,2,
|Tr g_a(X(y)) - Tr g_a(X(z))|
<= (sqrt(m)/w) ||X(y) - X(z)||_F <= (sqrt2/w)||y - z||_2,
using ||X(y)-X(z)||_F^2 <= (2/m)||y-z||_2^2. So each trace is convex and
L-Lipschitz in the independent coordinates with L = sqrt2/w.
Talagrand's convex-Lipschitz concentration on the cube: if F is convex and
globally L-Lipschitz on R^d, then at independent uniform signs
Pr(|F - E F| > u) <= C exp(-c u^2/L^2), u >= 0,
for universal c, C (the median form integrates to this one, adjusting
c, C by constants). Apply to the two traces. By (5.4),
Tr f(X) = m - Tr g_1(X) + Tr g_2(X) has expectation at most m l^{-A}/8 for
large N; if it exceeds m l^{-A}/4, one convex trace deviates from its
expectation by more than m l^{-A}/16. Hence
Pr(Tr f(X) > m l^{-A}/4)
<= 2C exp(-c' m^2 l^{-2A} w^2) <= 2^{-c_A N^2 l^{-4A-10}}. (5.5)
Off this event, f >= 1/2 on [-w/2,w/2], so X has at most m l^{-A}/2
eigenvalues in that interval. Finally 2B/sqrt(m) = X + J_m/sqrt(m) is a
rank-one perturbation; eigenvalue interlacing changes any interval's
cumulative count by at most one at each endpoint, i.e. by at most two.
With C_A = A + 6, 2 sqrt(N/m) l^{-C_A} <= w/2 for large N, uniformly in m,
so the eigenvalues of B in the proposition's interval number at most
(1/2) m l^{-A} + 2 <= N l^{-A}. Together with (5.5) (and
N l^{-4A-10} -> infinity) this proves the proposition. QED
==========================================================================
6. PROOF OF PROPOSITION A: THE DISCRIMINANT PAIRING
==========================================================================
We prove |S(B)| <= 2^{N(Psi(B)+tiny)}. An admissible column z has
z^T B^{-1} z an integer, so its class in G_B is isotropic for the
discriminant pairing. We color the isotropic classes so that within one
color the pairings of differences have small image order; a robust subset
of the largest color then has difference span of dimension bounded by the
"big layers", giving the estimate.
--------------------------------------------------------------------------
6.1 The discriminant pairing, blocks, and a coloring
--------------------------------------------------------------------------
For nonsingular symmetric integer B of size m, define on G_B = Z^m/BZ^m
lambda_B(x-bar, y-bar) = x^T B^{-1} y mod Z.
Changing x or y by an element of B Z^m changes the value by an integer,
so lambda_B is well defined; it is symmetric with values in Q/Z and
PERFECT: if lambda_B(x, y) = 0 for all y then B^{-1} x in Z^m, i.e. x-bar
= 0, so the map G_B -> Hom(G_B, Q/Z) is an isomorphism (equivalently
det B != 0). Distinct primary components are orthogonal (a value between
a p-power order and a q-power order element is killed by coprime powers),
so each primary part carries a perfect pairing. An element is ISOTROPIC
if its self-pairing is 0; isotropy passes to each primary projection. The
class of every z in S(B) is isotropic.
Lemma 6.1 (orthogonal block decomposition). Let G be a finite abelian
p-group with a perfect symmetric pairing lambda: G x G -> Q/Z. Then G is
an orthogonal direct sum of blocks of two forms:
(i) cyclic of order p^j, generator self-pairing a/p^j with p not | a;
(ii) p = 2 only: (Z/2^j Z)^2 with pairing matrix
2^{-j} [[2a, c],[c, 2d]] mod Z, c odd.
Proof. Let p^j be the exponent of a nonzero remainder. If some element
has self-pairing of order p^j, it has order p^j and its cyclic subgroup is
a block (i). Otherwise take x of order p^j; perfectness makes
lambda(x, .) have order p^j, so there is y with lambda(x,y) of order p^j.
Write the three values on x,y, with denominator p^j, as a,c,d. Then c is
a unit mod p while a,d are divisible by p. For odd p the self-pairing
numerator of x+y is a+2c+d, a unit: another block (i). For p = 2 the two
diagonal numerators are even and c is odd, so the 2x2 numerator matrix is
invertible mod 2^j; pairing any relation between x,y with x,y forces both
coefficients to vanish mod 2^j, so x,y span (Z/2^j Z)^2 and the
restriction is perfect: a block (ii).
To split a block H off orthogonally: the pairing on H is perfect, so for
each g in G there is a unique h in H with lambda(g, .)|_H = lambda(h, .)|_H,
so g - h is in H^perp; also H ∩ H^perp = 0. Hence G = H (+) H^perp, and
the pairing on H^perp is perfect (an element annihilating both summands
annihilates G). Iterate. QED
The cyclic exponents in this decomposition are the invariant exponents
b_1 >= b_2 >= ...; a block (ii) contributes two equal exponents.
Lemma 6.2 (primary coloring). In the setting of Lemma 6.1 put h = b_3
(zero exponents appended). In an orthogonal block decomposition, let U be
the sum of the blocks of exponent strictly greater than h, and T the rest.
There is a coloring of the isotropic elements of G with C_p colors such
that elements x,y of one color satisfy, with x_U, y_U their projections to U,
p^h lambda_U(x_U, y_U) = 0 in Q/Z, (6.1)
and the color count may be chosen with
C_p <= 1 + 8 b_1, C_p <= 2^{b_2 - b_3} if p is odd.
(The cutoff at b_3 leaves at most two cyclic factors above it, so U is
tiny; the height-two layers pay for the colors, higher layers control the
pairing image; see (6.2).)
Proof. The exponent of T divides p^h, so isotropy plus orthogonality gives
p^h lambda_U(x_U, x_U) = 0 (6.2)
for every element considered. There are at most two cyclic factors in U
(a block (ii) cannot straddle the cutoff at h, its factors being equal),
so we can enumerate.
U = 0: one color. U one factor, a cyclic block (i) of exponent j > h with
coordinate x and unit self-pairing numerator: (6.2) forces
v_p(x) >= ceil((j-h)/2), and two such coordinates pair to order <= p^h, so
one color. U two orthogonal cyclic blocks (i) of exponents j >= i > h,
units a_1, a_2: for coordinates x,y put F = max{ j - 2 v_p(x),
i - 2 v_p(y) }. One "deep" color for F <= h (two deep elements pair to
order <= p^h term by term). If F > h, both entries of the max equal F
(otherwise the largest-denominator term of the self-pairing cannot cancel
against (6.2)), so F <= i and F has the parity of both i and j. Write
x = p^{(j-F)/2} X, y = p^{(i-F)/2} Y with X,Y units; with n = F - h > 0,
(6.2) is a_1 X^2 + a_2 Y^2 = 0 mod p^n. The residues of X,Y mod p^n are
well defined, since their determination moduli p^{(j+F)/2}, p^{(i+F)/2}
exceed F >= n. Color by (F, r) with r = X Y^{-1} mod p^n; then
r^2 = -a_2 a_1^{-1} mod p^n. Two elements of one color, using primes for
the second,
a_1 X X' + a_2 Y Y' = Y Y'(a_1 r^2 + a_2) = 0 mod p^n,
which is (6.1). A unit square has at most two roots mod an odd prime
power (from p^n | (r-s)(r+s)) and at most four mod a power of 2 (for odd
r,s one of r-s, r+s has valuation exactly one and the other is divisible
by four; then r = +-s mod 2^{n-1}, giving at most four residues mod 2^n;
n = 1 immediate). So the count is at most 1 + 2 ceil((i-h)/2) for odd p,
which is <= 2^{i-h} when i-h >= 2; when i-h = 1 and a nondeep element
exists, its F = h+1, and the parity argument shows every deep element has
the required mutual denominator with every nondeep element, so merge the
deep color into one nondeep color (at most two colors); if no nondeep
element, one color. For p = 2 the unmerged count is at most
1 + 4 ceil((i-h)/2), a polynomial bound.
The last case: a single block (ii) at p = 2 of exponent j > h, numerator
matrix [[2a,c],[c,2d]] with c odd. Put t = min{v_2(x), v_2(y)},
F = j - 2t, deep color for F <= h. If F > h write x = 2^t X, y = 2^t Y
(at least one odd), n = F - h; take the pivot to be an odd coordinate,
call it u, the other v, and set f(X,Y) = a X^2 + c X Y + d Y^2 (swapping a,d
if the second coordinate is the pivot). The self-pairing numerator is
2 f, so (6.2) is f(u,v) = 0 mod 2^{n-1} (empty for n = 1). Color by
(F, pivot, r = v u^{-1} mod 2^n); then f(1,r) = a + c r + d r^2 = 0 mod
2^{n-1}, r well defined mod 2^n since the normalized coordinates are
determined mod 2^{j-t} >= 2^n, and the derivative c + 2 d r is odd, so
each root mod 2^alpha lifts uniquely to mod 2^{alpha+1} and there are at
most 4 permissible ratios mod 2^n. Two elements of one color have odd
pivots u,u' and r' = r mod 2^n, so
u u'(2a + c(r+r') + 2 d r r') = 2 u u' f(1,r) = 0 mod 2^n,
which after the common factor 2^{2t} is (6.1). The count is at most
1 + 8 b_1 (at most b_1 values of F > h, two pivots, four ratios each),
which also bounds all preceding cases. QED
Apply Lemma 6.2 independently to the primary parts of G_B; an overall
color is the tuple, with C_col(B) the product of counts over the nontrivial
parts. The needed estimate is
(log_2 C_col(B))/N
<= (5/4) sum_{k_B(p,e)=2} nu_p + O(N^{-1/5} log N)
<= beta sum_{k_B(p,e)=2} nu_p + O(N^{-1/5} log N). (6.3)
Indeed, for p >= N^{4/5} (odd for large N) the log color count is at most
b_{p,2} - b_{p,3}, exactly the number of its height-two layers, and
nu_p >= 4/(5N); these give the first term. For p < N^{4/5} use
C_p <= 1 + 8 b_{p,1} with b_{p,1} <= log_2|G_B| <= (N/2) log_2 N; there are
at most N^{4/5} such primes, costing O(N^{4/5} log N) bits. The second
bound uses 5/4 < beta = 7/5. The error is o(l^{-A}) for every fixed A.
Set
J_B = sum_{k_B(p,e) >= 3} k_B(p,e) nu_p. (6.4)
The budget (2.1) gives 0 <= J_B <= 1/2.
Lemma 6.3 (pairing image on differences). Let X be a set of isotropic
elements of G_B in a single overall color, and let
H = < x - y : x,y in X > <= G_B. For the restricted pairing map
theta_H : H -> Hom(H, Q/Z), theta_H(u) = lambda_B(u, .)|_H,
one has
|im theta_H| <= N^{N J_B}.
Proof. Fix a prime, h = b_{p,3}. In the decomposition G_{B,p} = U (+) T
used in Lemma 6.2, let d = #{i : b_{p,i} > h} <= 2. Project the p-primary
part of H to H_U <= U and H_T <= T. Every pairing between projections of
elements of X is annihilated by p^h on U, and bilinearity extends this to
all of H_U. A subgroup of a p-group with d cyclic factors has at most d
generators (its minimal number of generators equals dim of its p-torsion,
<= dim U[p] = d). The image of the restricted pairing on H_U is a quotient
of H_U, annihilated by p^h, so its order is <= p^{hd}; that on H_T is
<= |H_T| <= |T|. The image of the sum is contained in the sum of the two
images, order <= |T| p^{hd} = p^{sum_i min(b_{p,i}, h)} = p^{sum_{e<=b_{p,3}}
k_B(p,e)}, i.e. p^{sum_{e : k_B(p,e) >= 3} k_B(p,e)}. Distinct primary
pairings are orthogonal, so multiplying over primes gives
|im theta_H| <= prod_p p^{sum_{e : k_B(p,e)>=3} k_B(p,e)} = N^{N J_B}. QED
--------------------------------------------------------------------------
6.2 The graph lattice, the spectral comparison, and Proposition A
--------------------------------------------------------------------------
Lemma 6.4 (pairing index and determinant). Let L be a lattice with span
V and let q be a symmetric bilinear form on V with q(L,L) <= Q. Put
K = L ∩ rad q, S = V ∩ (rad q)^perp, Lbar = proj_S L.
Then K spans the radical and is primitive in L, and Lbar is a lattice in S.
If t is the order of the image of L -> Hom(L, Q/Z), x -> q(x, .) mod Z,
then
|det_orth(q|_S)| >= 1/(t (det Lbar)^2) = (det K)^2/(t (det L)^2). (6.11)
(Orthonormal determinant on S; rank-zero determinants are 1.)
Proof. The matrix of q in an L-basis is rational, so its kernel is
rational there and K spans the radical; K is primitive as the intersection
of L with a real subspace. Extending a basis of K to one of L gives
det L = det K det Lbar and shows Lbar is a lattice. q descends to Lbar
(it vanishes when an argument is in the radical), with the same image order
t (the quotient L -> Lbar is onto and pullback injects Hom(Lbar, Q/Z) into
Hom(L, Q/Z)); the image is finite since q is rational in a lattice basis.
Let M be the matrix of q in a basis of Lbar, of rank s = dim S; M is
nonsingular rational. The kernel of the pairing mod Z in Z^s has index t;
let A be an integer basis matrix of it, |det A| = t. Then A^T M is
integral with nonzero determinant, so
1 <= |det(A^T M)| = t |det M|.
If P is the basis matrix of Lbar in orthonormal coordinates on S, then
M = P^T M_orth P and |det P| = det Lbar, so
|det M_orth| = |det M|/(det Lbar)^2 >= 1/(t (det Lbar)^2). QED
Proof of Proposition A. Fix A > 0 and a fixed P > A + 2. Intersect the
typical event of Corollary 5.3 (D = 2, precision P) with that of
Proposition 5.5 (precision P). On it the rank conclusion (5.3) holds for
every rational W with H(W) <= exp(N l^2), and the spectral conclusion holds
for B itself.
Fix nonsingular B in this event; if S(B) is empty there is nothing to
prove. Choose the largest overall color among the elements of S(B) (the
color of a column is that of its class in G_B). Lemma 3.7 with rho = l^{-P}
gives a nonempty subset T robust on its affine span with
log_2|S(B)| <= log_2 C_col(B) + N l^{-P} + log_2|T|. (6.12)
Let W = span(T - T), r = dim W (rational). Projection onto r suitable
coordinates is injective on W, hence on aff T, so
|T| <= 2^r. (6.13)
Consider the rational injective graph map
gamma : R^m -> R^{2m}, gamma(z) = (z, B^{-1} z),
and the rank-r lattice
L = < gamma(z) - gamma(t) : z,t in T >_Z in gamma(W).
Each graph difference has squared norm <= m + 4m <= 5N (first coordinates
are bit differences; each inverse image has infinity norm <= 1 on the
robust subset). The restriction of gamma to aff T is a rational affine
injection preserving the codimensions in robustness, so Lemma 3.8 applies
to the graph points and to the cube points. For a constant C_0 depending
only on P,
det L <= exp(C_0 N l), H(W) <= exp(C_0 N l). (6.14)
For large N the second bound is <= exp(N l^2), so this adaptive W lies in
the scope of Corollary 5.3 (Lemma 3.8 is deterministic; the spectral event
concerns all eigenvalues of B; neither needs W fixed in advance).
On the graph Gamma = gamma(R^m) define Q(gamma(x), gamma(y)) =
x^T B^{-1} y. Let s be the rank of Q restricted to gamma(W); the graph
map identifies it with B^{-1} restricted to W, so Corollary 5.3 gives
s >= r - N l^{-P}. (6.15)
On L the reduction of Q mod Z is the pullback of the restricted
discriminant pairing on H = < z-bar - t-bar : z,t in T > <= G_B: the map
L -> H, gamma(u) -> u + B Z^m, is surjective and respects the pairings,
and pullback on character groups is injective, so the orders agree. By
Lemma 6.3 that order is at most N^{N J_B}.
Let K = L ∩ rad(Q|_{gamma(W)}) and S the orthogonal complement of this
radical in gamma(W). Lemma 6.4 applies (B^{-1} is rational and the first
coordinates of L are integral): rank L = r, rank K = r - s, dim S = s.
Also det K >= 1: projection to the first m coordinates is injective on
Gamma and maps K to an integer lattice of the same rank, whose
squared determinant is a positive integer (hence >= 1); orthogonal
projection contracts volume, so det K >= 1. Lemma 6.4 and (6.14) give
|det_orth(Q|_S)| >= N^{-N J_B}(det L)^{-2}
>= N^{-N J_B} exp(-2 C_0 N l). (6.16)
Now compare with the spectrum of Q on Gamma in the Euclidean metric of
R^{2m}. Let v_i be orthonormal eigenvectors of B with nonzero eigenvalues
lambda_i; their graph vectors are orthogonal and ||gamma(v_i)||^2 =
1 + lambda_i^{-2}. So the self-adjoint operator representing Q on Gamma
has eigenvalues mu_i = lambda_i/(1 + lambda_i^2), all of modulus <= 1. By
Proposition 5.5, apart from t_B <= N l^{-P} of them, |lambda_i| >
sqrt(N) l^{-C_P}, and for these
|mu_i| <= |lambda_i|^{-1} <= a_N := l^{C_P}/sqrt N < 1
for large N. The determinant of a compression to an s-dimensional
subspace is at most the product of the largest s singular values of the
operator: with w the unit exterior product of an orthonormal basis of S
and T_Q the operator,
det = <w, (wedge^s T_Q) w>, |det| <= ||wedge^s T_Q||.
Applied to S this gives
|det_orth(Q|_S)| <= a_N^{(s - t_B)_+} <= a_N^{s - t_B}. (6.17)
(The last also holds if s < t_B, since a_N < 1.)
Compare (6.16) and (6.17) and take logarithms:
(s - t_B)( (1/2) log N - C_P log l ) <= N J_B log N + 2 C_0 N l.
The coefficient on the left is positive for large N. With (6.15) and
t_B <= N l^{-P},
r/N <= (J_B + 2 C_0 l/log N)/(1/2 - C_P log l/log N) + 2 l^{-P}
= 2 J_B + O(l^{-P}),
the last equality using J_B <= 1/2, that C_0, C_P, P are fixed, and
(l + log l)/log N = o(l^{-P}).
Combine (6.12), (6.13), (6.3):
(log_2|S(B)|)/N
<= beta sum_{k_B(p,e)=2} nu_p + 2 J_B + O(l^{-P}) + O(N^{-1/5} log N)
= Psi(B) + O(l^{-P}) + O(N^{-1/5} log N),
the equality from (2.2) and (6.4). Since P > A + 2 is fixed, the two
error terms sum to at most l^{-A} for large N. This is Proposition A on
the chosen typical event. QED
==========================================================================
7. ALGEBRA OF PRINCIPAL-MINOR EXTENSIONS
==========================================================================
Now the dynamic half. We prove Proposition B by growing a matrix from a
tiny principal minor, adding one or two rows and columns at a time, and
showing the potential 2^{N Psi} is controlled in expectation at each step.
This section sets up the algebra; Sections 8-10 give the local step; Section
11 chains steps along a path.
Lemma 7.1 (gated deletion). Let B be a nonsingular symmetric r x r matrix
with bits, r >= 1. Either a principal submatrix obtained by deleting one
coordinate is nonsingular, or there are distinct i,j such that, with
I = [r] \ {i,j},
C = B_{I,I} is nonsingular, v_1 = B_{I,i} in S(C), v_2 = B_{I,j} in S(C).
(Empty minor has determinant one; S contains its unique empty column.)
Proof. The cofactor identity det B_{[r]\{i}} = det B (B^{-1})_{ii} shows a
nonzero diagonal entry of B^{-1} gives the first alternative. Suppose all
diagonal entries vanish; B^{-1} is nonsingular, so some off-diagonal entry
is nonzero. Pick i,j maximizing |(B^{-1})_{ij}|, kappa = (B^{-1})_{ij} != 0.
Then
(B^{-1})_{{i,j},{i,j}} = [[0, kappa],[kappa, 0]],
and Jacobi's complementary minor identity gives
det C = det B * det (B^{-1})_{{i,j},{i,j}} = -kappa^2 det B != 0.
Order coordinates with I first and write
B = [[C, V],[V^T, D]], V = (v_1 v_2), T = D - V^T C^{-1} V.
Block inversion gives
T^{-1} = (B^{-1})_{{i,j},{i,j}} = [[0, kappa],[kappa, 0]],
(B^{-1})_{I,{i,j}} = -C^{-1} V T^{-1}.
The diagonal of T is zero; its two diagonal equations give
v_a^T C^{-1} v_a = D_{aa} in bits (a = 1,2). The two columns of the
displayed inverse block are -kappa C^{-1} v_2 and -kappa C^{-1} v_1, and
by choice of i,j every entry of that block has modulus <= |kappa|. Hence
||C^{-1} v_a||_inf <= 1 for a = 1,2, i.e. v_1, v_2 in S(C). QED
For h in {1,2} with m, m+h in I_N and C a nonsingular binary matrix of
size m, a RANDOM EXTENSION of width h is
B = [[C, V],[V^T, D]], V = (v_1 ... v_h), (7.1)
where the mh entries of V and the h(h+1)/2 entries D_{ab} (a <= b) are
independent uniform bits (the lower triangle of D by symmetry). If C is
random these new bits are independent of C; conditional on C the columns
v_1,...,v_h are independent uniform in bits^m. Define the GATE events
G_1 = Omega, G_2 = { v_1 in S(C), v_2 in S(C) }. (7.2)
Conditional independence gives
Pr(G_2 | C) = (|S(C)|/2^m)^2. (7.3)
This is the lever that lets the admissible-column count pay for width-two
extensions. Lemma 7.1 says every nonsingular matrix has a backward move
whose forward extension satisfies its gate.
Proposition 7.2 (potential step). For every fixed A > 0, typically for
nonsingular binary C of size m in I_N: for each h in {1,2} with m+h in I_N
the random extension (7.1) satisfies
E[ 1_{det B != 0} 1_{G_h} 2^{N Psi(B)} | C ] <= 2^{N(Psi(C) + l^{-A})}.
(7.4)
The typical condition is imposed only on the starting matrix C.
Proved in Section 10. It is the local engine; everything in Sections 8-9
serves it.
--------------------------------------------------------------------------
7.1 The common quotient and the layers
--------------------------------------------------------------------------
Fix a realization of (7.1) with B nonsingular. Set
H_0 = G_C, H_j = Z^m/(C Z^m + Z v_1 + ... + Z v_j) = H_{j-1}/<v_j-bar>,
(7.5)
the image of v_j in H_{j-1}. These depend only on C and the columns
shown, and make sense even if B is singular. The last is also a quotient
of G_B:
H_h = G_B / < e-bar_{m+1}, ..., e-bar_{m+h} >, (7.6)
the bars denoting classes of the standard basis vectors in G_B. Indeed,
the right side is Z^{m+h}/(B Z^{m+h} + (0 (+) Z^h)), and projection to the
first m coordinates carries its relations onto C Z^m + V Z^h (the reverse
inclusion: subtract a suitable vector of B Z^{m+h} to land in 0 (+) Z^h).
For finite abelian G, prime p, and integer t >= 0 put
F_G(p,t) = sum_{e=1}^{t} k_G(p,e) = sum_i min{b_{p,i}, t}
= log_p |G/p^t G|, (7.7)
the empty sum being zero. For a nonsingular binary M write F_M = F_{G_M}.
Lemma 7.3 (layers under a one-element quotient). Let G be finite abelian,
v in G, H = G/<v>. Fix p and define u_t by p^{u_t} = |<v + p^t G>| in
G/p^t G (t >= 0). Then u_0 = 0, u_t - u_{t-1} in {0,1} for t >= 1, and
F_H(p,t) = F_G(p,t) - u_t, (7.8)
k_H(p,e) = k_G(p,e) - (u_e - u_{e-1}) in {k_G(p,e), k_G(p,e)-1}. (7.9)
Call a positive layer (p,e) of G RETAINED if k_H(p,e) = k_G(p,e). On each
maximal interval of consecutive layers where k_G(p,e) has a fixed positive
value (a PLATEAU), the retained layers form an initial interval, possibly
empty.
Proof. Quotienting by p^t and by v commutes, so H/p^t H = (G/p^t G)/<v+p^t G>
and taking orders gives (7.8). Write G_p = (+)_i Z/p^{b_i} Z; for the i-th
coordinate of v let r_i be its p-adic valuation capped at b_i (= b_i for a
zero coordinate). The coordinate's order in G_p/p^t G_p is
p^{(min{b_i,t} - r_i)_+}, and the order of an element in a direct sum of
p-groups is the largest coordinate order, so
u_t = max_i (min{b_i,t} - r_i)_+. (7.10)
Each term is nondecreasing in t and rises by at most one per step, so the
same holds for u_t, giving increments in {0,1}; subtracting (7.8) at
t = e-1 from t = e gives (7.9). On a plateau of height k the heights in H
are k or k-1, and they are nonincreasing in e (invariant factors), so a
k-1 cannot be followed by a k: retained layers are exactly the height-k
ones, an initial interval. QED
Applied to (7.5), and likewise to the h quotients of G_B by the standard
basis classes in (7.6), Lemma 7.3 gives, for every (p,e),
k_C(p,e) - h <= k_{H_h}(p,e) <= k_C(p,e),
k_B(p,e) - h <= k_{H_h}(p,e) <= k_B(p,e). (7.11)
In particular for h = 1 the common height is k_C or k_C - 1 (and k_B is
that or one more); a layer absent from G_C has height at most h in G_B.
--------------------------------------------------------------------------
7.2 The lattice forced by retention
--------------------------------------------------------------------------
Retaining prescribed layers forces the new column into an intermediate
lattice. This is the bridge from the additive structure of G to the cube.
Lemma 7.4 (retention lattice). Let C be nonsingular binary of size m and
pi: Z^m ->> H a quotient with C Z^m <= ker pi. Let E be any set of positive
layers of H. There is a lattice K_E, depending only on pi, H, E, with
C Z^m <= K_E <= Z^m, [Z^m : K_E] = N^{N q(E)},
q(E) = sum_{(p,e) in E} k_H(p,e) nu_p, (7.12)
such that: if every layer in E is retained in H -> H/<pi(v)>, then v in K_E.
Proof. Fix cyclic coordinates H_p = (+)_i Z/p^{b_i} Z once for H. Put
a_{p,i} = #{ e : (p,e) in E, e <= b_i },
T_E = (+)_{p,i} p^{a_{p,i}} (Z/p^{b_i} Z) <= H, K_E = pi^{-1}(T_E).
Then 0 <= a_{p,i} <= b_i and K_E contains C Z^m. Its index is
[Z^m : K_E] = [H : T_E] = prod_{p,i} p^{a_{p,i}}
= prod_{(p,e) in E} p^{k_H(p,e)} = N^{N q(E)},
the penultimate equality counting a layer once per cyclic factor reaching
it. For the implication, fix p,i and let r_i be the capped valuation of
the i-th coordinate of pi(v) (as in Lemma 7.3); (7.10) at t = b_i gives
u_{b_i} >= b_i - r_i. All first b_i layers are positive, and (7.9) shows
the number among them that are retained is sum_{e=1}^{b_i}(1 - (u_e -
u_{e-1})) = b_i - u_{b_i}. If every layer in E is retained then
a_{p,i} <= b_i - u_{b_i} <= r_i, so the i-th 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. QED
Example. For a p-primary part with cyclic exponents (5,3,1) (heights
(k_B(p,1),...,k_B(p,5)) = (3,2,2,1,1)), choosing E = {(p,2),(p,4)} gives
divisibility exponents (a_{p,1},a_{p,2},a_{p,3}) = (2,1,0). The two
selected layers have total weight 2 nu_p, while q(E) = 3 nu_p and
[Z^m : K_E] = p^3.
For the quotient in (7.5) the map pi is the natural map Z^m ->> H_{j-1},
and conditional on C and the preceding columns v_1,...,v_{j-1} the next
column is uniform on the cube.
--------------------------------------------------------------------------
7.3 A symmetric kernel inequality
--------------------------------------------------------------------------
Symmetry of B forces the destination layers to be controlled more strongly
than plain interlacing. At prime p let u_{j,t} be the exponent of
Lemma 7.3 for H_{j-1} -> H_j, and set
U_t = sum_{j=1}^{h} u_{j,t} = F_C(p,t) - F_{H_h}(p,t), (7.13)
the second equality by summing (7.8).
Lemma 7.5 (symmetric kernel inequality). For a nonsingular extension B of
a nonsingular C of width h in {1,2}, at every prime p and integer t >= 0,
F_B(p,t) <= F_C(p,t) + ht - 2 U_t. (7.14)
Proof. Trivial for t = 0. Fix t >= 1, R_t = Z/p^t Z, and reduce the
blocks of B mod p^t as C_t, V_t, D_t. Let X = R_t^m, Y = R_t^h,
L = ker(C_t : X -> X), J = im(C_t : X -> X). The presentation gives
X/J = Z^m/(C Z^m + p^t Z^m) = G_C/p^t G_C, and a square endomorphism of
the finite group X has kernel and cokernel of equal order, so
|L| = |X/J| = p^{F_C(p,t)}. (7.15)
Define alpha: Y -> X/J, alpha(y) = V_t y + J. Its image is the subgroup of
G_C/p^t G_C generated by the column classes, whose quotient is H_h/p^t H_h;
by (7.13) |im alpha| = p^{U_t} and |ker alpha| = p^{ht - U_t}. A kernel
vector (x,y) of B mod p^t satisfies the first block equation
C_t x + V_t y = 0, requiring y in ker alpha; for such y the solutions x form
a coset x_0 + L.
Consider gamma: L -> Y, gamma(z) = V_t^T z. Equip X, Y with the perfect
character pairings <x,z>_X = exp(2 pi i x^T z / p^t) (and similarly <.,.>_Y).
For a subgroup M of either module A, with M^perp its annihilator,
|M| |M^perp| = sum_{a in A} sum_{z in M} <a,z>_A = |A|. (7.16)
(The inner sum is |M| on the annihilator and 0 elsewhere; reversing the
sums, each z != 0 contributes 0 by perfectness and z = 0 contributes |A|.)
Symmetry of C_t gives J <= L^perp, since <C_t x, z>_X = <x, C_t z>_X = 1 for
z in L. Both have order |X|/|L| (J by kernel-image, L^perp by (7.16)), so
L^perp = J. Then
(im gamma)^perp
= { y in Y : <y, V_t^T z>_Y = 1 for all z in L }
= { y in Y : <V_t y, z>_X = 1 for all z in L }
= { y in Y : V_t y in J } = ker alpha,
so by (7.16) in Y, |im gamma| = |Y|/|ker alpha| = p^{U_t} and
|ker gamma| = |L|/|im gamma| = p^{F_C(p,t) - U_t}.
For a fixed y in ker alpha and x = x_0 + z, the second block equation is
gamma(z) = -V_t^T x_0 - D_t y, which has no solution or one coset of
ker gamma. So at most p^{ht - U_t} choices of y and, for each, at most
p^{F_C(p,t) - U_t} choices of z give
|ker(B mod p^t)| <= p^{F_C(p,t) + ht - 2 U_t}.
Finally the kernel of the square endomorphism B mod p^t has the order of
its cokernel G_B/p^t G_B, which is p^{F_B(p,t)}. Take logarithms. QED
==========================================================================
8. SIMULTANEOUS CONCENTRATION IN LATTICE QUOTIENTS
==========================================================================
Retaining layers forces the new column into an intermediate lattice K_E.
Section 8 bounds, on one typical event for the starting matrix, the number
of cube points in any coset of ANY such lattice -- simultaneously, so the
lattice may be chosen adaptively. The engine is a counting ("witness
pricing") argument, stated as Proposition 8.3.
Let B be nonsingular binary of size m in I_N and let B Z^m <= K <= Z^m.
For D <= [m] put
Q_D = { z in bits^m : z_j = 0 for j not in D },
M_K(D) = max_{a in Z^m} |Q_D ∩ (a + K)|, M_K = M_K([m]).
M_K(D') <= M_K(D) if D' <= D. The lattice K has full rank, det K =
[Z^m : K]. Define
q = q_K = (log [Z^m : K])/(N log N), so [Z^m : K] = N^{qN}.
The quotient Z^m/K is a quotient of G_B, so (2.1) gives 0 <= q <= 1/2.
For 0 <= d <= 1 write f = 1 - d and define the profile
c(d/2) = 1 - f z(d/f),
z(u) = (1 + sqrt(2u - u^2))^{-1} for 0 <= u <= 1, z(u) = 1/2 for u >= 1,
(8.1)
with the product fz(d/f) taken as 0 at f = 0. So c: [0,1/2] -> [0,1],
c(0) = 0, c(1/2) = 1.
Proposition 8.1 (cube concentration). For every fixed A > 0, typically
for nonsingular B of size m in I_N, simultaneously for every lattice
B Z^m <= K <= Z^m,
M_K <= 2^{N(1 - c(q_K) + l^{-A})}. (8.2)
The typical event may depend on A but not on K, so the choice of K may
depend on B and on other data.
The function c is nondecreasing and concave. With r(u) = sqrt(2u - u^2)
(0 < u < 1), r'(u) = (1-u)/r(u), r''(u) = -1/r(u)^3, so z = (1+r)^{-1} is
nonincreasing and convex (one checks z'' > 0, and the left derivative at 1
is 0 so the constant extension stays convex). The perspective f z(d/f)
is convex for f > 0 (convexity of z with weights proportional to the two
values of f), extends continuously and convexly to f = 0, and restricting
to f = 1-d makes c concave. As d grows both f and z(d/f) fall, giving
monotonicity. We will also use
|c(q) - c(q')| <= C_pr |q - q'|^{1/2}, 0 <= q, q' <= 1/2. (8.3)
Indeed |z(u) - z(v)| <= |r(u) - r(v)| <= sqrt(2|u-v|); on 0 <= d <= 1/2 the
map d -> d/(1-d) is 4-Lipschitz, so the product is Hoelder of exponent 1/2
there, while on 1/2 <= d <= 1 it is (1-d)/2; combine at d = 1/2 and use
d = 2q.
We first count bases of low-height subspaces, then use that count to price
the witnesses behind a large cube intersection.
--------------------------------------------------------------------------
8.1 Low-height bases: the exact count
--------------------------------------------------------------------------
Lemma 8.2 (exact-basis count). Fix C, C' > 0. Uniformly for m in I_N
and 0 <= j <= m, the number of ordered tuples
(y, y_1, ..., y_j) in (bits^m)^{j+1}
for which y_1 - y, ..., y_j - y are independent and their span W satisfies
H(W) <= exp(N l^C) is at most
2^{j^2 + o(N^2 l^{-C'})}.
Proof. j = 0 is immediate. For j >= 1 encode the center y and a choice of
j pivot coordinates on which the differences are independent: O(N log N)
bits. At the pivots each difference entry has two values once y is known,
costing j^2 bits.
Add the other coordinates in a fixed order. Suppose the current projected
span is V <= R^h with L_V = V ∩ Z^h; the next projected span is the graph
of a rational functional x -> <v,x> on V, v in V. Put
a = min{ b in Z_{>0} : b v in L_V^* }.
The image of L_V under this functional mod Z has order a, so 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), hence
H(graph(v))/H(V) = a sqrt(1 + ||v||^2). (8.4)
Every ratio is >= 1; the initial projected space is R^j (height 1) and the
final is W. So every intermediate height is <= exp(N l^C), and a ratio
exceeding N^{1/10} occurs at most O(N l^C / log N) times. Mark those
coordinates and encode their j difference entries directly: cost
O(N^2 l^C / log N) bits.
At any other coordinate a <= N^{1/10} and ||a v|| <= N^{1/10}. Count
possible a v in Lambda = L_V^*. Lemma 3.3 (applied to V <= R^h) gives
det M >= H(V)^{-1} for every sublattice M <= Lambda. Apply Lemma 3.6 to
Lambda with T = N^{-1/10} (minimizer chosen as a function of the known V).
If its rank is r_0, comparison with the zero lattice and the preceding bound
give H(V)^{-1} <= T^{r_0} and r_0 <= 10 N l^C / log N. Every sublattice of
the quotient has det >= T to its rank, so by Lemma 3.5 the number of
quotient images of vectors of norm <= N^{1/10} is
2^{O(N^{2/5} log^2 N)}
(the quotient has rank <= N; the bound covers rank zero).
Encode a (O(log N) bits) and the quotient image of a v. 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 with
two possible values (fixed by the corresponding coordinate of y). An
affine space of dimension r_0 meets such a cube in at most 2^{r_0} points
(project onto r_0 suitable coordinates), bounding the fiber cost by r_0
bits.
Summing over at most N coordinates, including pivot, center, and marking
costs, the logarithm of the number of tuples is at most
j^2 + O( N^2 l^C / log N + N^{7/5} log^2 N + N log N ).
For fixed C, C' this is j^2 + o(N^2 l^{-C'}), uniformly in j and m. QED
--------------------------------------------------------------------------
8.2 Witness pricing
--------------------------------------------------------------------------
A witness records why a cube coset is large: a lattice K, robust sets
S_i whose differences lie in K, a direct sum of their spans, and a
coordinate set D on which the cube intersection is small. Pricing the
witness against the free matrix bits bounds how large such a coset can be.
Proposition 8.3 (witness pricing). Fix D_0 > 0, put eta = l^{-D_0} and
rho = eta^3. Typically for nonsingular B of size m in I_N, simultaneously
for every B Z^m <= K <= Z^m:
Let S_1,...,S_h <= bits^m be nonempty, each rho-robust on its affine span,
with h <= 3/eta. Suppose S_i - S_i <= K, W_i = span(S_i - S_i), and
W = sum_i W_i is a direct sum. Write dim W_i = t_i N, t = sum_i t_i,
|S_i| = 2^{alpha_i N}. If D <= [m] has |D| = xN with x <= t, and
M_K(D) <= 2^{eta N}, then
x t - x^2/2 <= sum_i t_i (t_i - alpha_i) + eta t + eta^3. (8.5)
Counting interpretation. In a symmetric block on tN coordinates the
number of independent entries with an endpoint in a fixed set of xN
coordinates is (xt - x^2/2) N^2 + O(N); pinning each such row on that
set to at most 2^{eta N} choices saves this many bits, less eta t N^2.
Describing an ordered basis of S_i costs t_i^2 N^2 to leading order,
while robustness supplies alpha_i t_i N^2 bits of multiplicity; the
residual t_i(t_i - alpha_i) is the genuine cost. A violation would make
the row saving beat the total witness cost by eta^3 N^2.
Proof. Lemma 3.8 (with rho = l^{-3D_0}) gives H(W_i) <= exp(O(N l)); the
integer sum of W_i ∩ Z^m lies in W ∩ Z^m, so by the volume inequality and
saturation H(W) <= prod_i H(W_i) <= exp(O(N l/eta)). Choose D_1 > D_0 + 1;
for large N this is <= exp(N l^{D_1}). Impose Proposition 5.2 at this
height and at a precision strong enough that its rank error is <= eta^5 N,
and impose Proposition 5.4. Their intersection is typical; all counting
below is inside it.
Upper count of basis lists. For a fixed list of dimensions,
Lemma 8.2 counts centers and ordered bases of differences for the pieces
with total logarithm
N^2 sum_i t_i^2 + o(N^2 eta^4). (8.6)
(Use that lemma with a fixed C' > 5 D_0 and sum its errors over at most
3/eta pieces; choose the height exponent there fixed and large enough for
all W_i.)
Lower count of basis lists. For each 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, which robustness bounds by a fraction 2^{-rho}. So
the number of ordered bases for this piece is at least
((1 - 2^{-rho}) 2^{alpha_i N})^{t_i N}, and choices for distinct pieces
differ. As t <= m/N <= 1, the total logarithm is at least
N^2 sum_i t_i alpha_i - O(N log(1/rho)) = N^2 sum_i t_i alpha_i
- o(N^2 eta^4). (8.7)
Fix basis-list data (so W is known). For a witnessed matrix choose a
coordinate set Y_0 of size tN containing D. Proposition 5.2(2) shows the
columns on [m]\Y_0, projected off W, have rank at least m - tN - eta^5 N.
Choose an independent collection there and extend it, using nonsingularity
of B, to a basis of R^m/W by columns of B. Let P be the resulting set of
m - tN indices and Y = [m]\P; then |D ∩ P| <= eta^5 N. Encode D and P
(O(N) bits) and reveal the columns on P: if T_m = m(m+1)/2 is the number
of independent bits of B, this costs T_m - C(tN+1,2) bits (by symmetry).
The revealed columns together with the basis differences are m independent
integer vectors (differences span W; revealed columns project to a basis off
W). Let L be their integer span: known from the data, L <= K, full rank.
Each generator has norm <= sqrt N, so Hadamard gives
|Z^m/L| <= N^{m/2} <= N^{N/2}. Enumerate possible K containing L. With
r_N = ceil(N^{3/5}), for every prime p,
dim_{F_p}((Z^m/K)/p(Z^m/K)) <= dim_{F_p}(G_B/pG_B) = corank_{F_p} B
<= r_N
by Proposition 5.4, and the minimal number of generators of a finite
abelian group is the max of these over p, so Z^m/K and its dual need at
most r_N generators. Put H = Z^m/L: the annihilator of K/L identifies
(Z^m/K)^vee with a subgroup of H^vee, and every at-most-r_N-generated
subgroup is generated by some ordered r_N-tuple in H^vee. So the number
of possible K is at most |H|^{r_N}, logarithm
O(N^{8/5} log N) = o(N^2 eta^4). (8.8)
This candidate list is formed after the basis lists and revealed columns
fix L, before the remaining block is encoded; it may include incompatible
lattices, which only enlarges the count. Prime-corank only ensures each
actual witnessed K appears.
Matrix saving. Write D' = D ∩ Y, y = |Y| = tN, d' = |D'|: d' >= (x -
eta^5)N and M_K(D') <= M_K(D) <= 2^{eta N}. In the remaining Y-block
first encode the symmetric bits on Y\D' (cost C(y-d'+1,2)). For a row in
Y\D' all entries outside D' are known and the full row is in K (B symmetric,
columns in B Z^m), so its entries on D' lie in a fixed coset of K and have
at most M_K(D') <= 2^{eta N} choices: cost <= eta N(y-d'). The D'-block
costs <= eta N d' (ignore its internal symmetry). Against an unrestricted
symmetric Y-block the saving is at least
C(y+1,2) - C(y-d'+1,2) - eta N y
= y d' - (d')^2/2 + d'/2 - eta N y
>= N^2( x t - x^2/2 - eta t - O(eta^5 + 1/N) ). (8.9)
Double counting. Group violating witnesses by h, the integers t_i N, xN,
and a_i = floor(log_2 |S_i|) (alpha-bar_i = a_i/N): at most
2^{O(eta^{-1} log N)} groups. Fix one group and let E be the matrices in
the imposed typical intersection having a violating witness in it. For
each B in E select one such witness and count the distinct pairs
(B, basis list). The lower count (8.7) gives at least
|E| 2^{N^2 sum_i t_i alpha-bar_i - o(N^2 eta^4)}
pairs; the upper count (8.6), (8.8), and the saving (8.9) give at most
2^{T_m + N^2( sum_i t_i^2 - x t + x^2/2 + eta t ) + o(N^2 eta^4)}.
(Counting a pair twice when several compatible D, P, K exist only helps
the upper bound.) Since 0 <= alpha_i - alpha-bar_i < 1/N and t <= 1,
violation of (8.5) implies
sum_i t_i (t_i - alpha-bar_i) - x t + x^2/2 + eta t < -eta^3 + 1/N.
All binary matrices have probability 2^{-T_m}, so dividing the pair bounds,
Pr(B_m in E) <= 2^{-N^2 eta^3 + o(N^2 eta^4)}.
Since N eta^3 -> infinity, the total violation probability is
2^{-omega(N)}, including the imposed rank and corank exceptions. QED
--------------------------------------------------------------------------
8.3 From witness pricing to cube concentration
--------------------------------------------------------------------------
Proof of Proposition 8.1. Fix A > 0, choose D_0 > 2A, and put
eta = l^{-D_0}, rho = eta^3. Work on the typical event of Proposition 8.3
and fix K with B Z^m <= K <= Z^m.
Decompose K. Apply Lemma 3.6 to K with T = (log N)^4 and a minimizing
saturated sublattice K_0. Put F = span K_0,
d = (m - dim F)/N, f = 1 - d = (dim F + N - m)/N.
The quotient K/K_0 has rank dN and every sublattice has det >= T to its
rank; det K_0 <= T^{dim F} (comparison with zero). The projections of the
columns of B span F^perp, each of norm <= sqrt N; choosing dN independent
ones, their integer span is a sublattice of K/K_0, so Hadamard gives
det(K/K_0) <= N^{dN/2}. Hence
q = (log det K)/(N log N) <= d/2 + (dim F/N)(log T/log N)
<= d/2 + 4l/log N. (8.10)
Extract a robust set from a coset. Take any nonempty S in a coset of K;
base its differences at one point. Their projections off F lie in K/K_0
with norm <= sqrt N, so Lemma 3.5 gives at most 2^{O(N/log^6 N)} distinct
projections. Restrict to a largest projection fiber and apply Lemma 3.7
with rho = eta^3: for large N these lose at most 2 eta^3 N bits, so if
|S| = 2^{aN} they produce a rho-robust S' with
|S'| >= 2^{(a - 2 eta^3)N}, span(S' - S') <= F. (8.11)
If S is supported on a coordinate set, so is S'.
Choose sign-changing pivots. Let P_F be dim F pivot coordinates for F
(projection onto P_F injective on F) and J_0 = [m]\P_F, |J_0| = dN. A
vector supported on J_0 lies in F only if zero, so distinct bit vectors
supported on J_0 have distinct projections off F; the projection count
above applied to a coset on J_0 gives
M_K(J_0) <= 2^{O(N/log^6 N)} <= 2^{eta N}. (8.12)
Write M_K = 2^{alpha N}, 0 <= alpha <= 1. If alpha < 10 eta the conclusion
follows (1 - c(q) >= 0 and 10 eta <= l^{-A}). Assume alpha >= 10 eta.
Apply (8.11) to a full-coordinate coset attaining M_K; call the result S_*,
put W_* = span(S_* - S_*), |S_*| = 2^{alpha_* N}, v = dim W_*/N. An affine
space of dimension dim W_* contains at most 2^{dim W_*} cube points, so
alpha_* >= alpha - 2 eta^3, alpha - 2 eta^3 <= v <= (dim F)/N <= f. (8.13)
Build a coordinate set D with small M_K(D). Start with all of P_F
available. At step i choose, among the available coordinates, a set A_i of
minimum cardinality with M_K(J_0 ∪ A_i) > 2^{eta N}. Apply (8.11) to a
coset attaining M_K(J_0 ∪ A_i): a robust S_i with
W_i <= F ∩ E_{J_0 ∪ A_i}, alpha_i = log_2|S_i|/N >= eta - 2 eta^3,
t_i = dim W_i/N >= alpha_i.
Since projection of F onto P_F is injective and W_i vanishes on P_F\A_i,
t_i N <= |A_i|. Choose t_i N pivots H_i <= A_i on which W_i projects
injectively and declare them unavailable; stop when t = sum_i t_i >=
alpha - 2 eta.
(The set A_i exists before stopping: the unavailable coordinates number
tN; fix them to a most frequent pattern in a coset attaining M_K, leaving
>= 2^{(alpha - t)N} > 2^{2 eta N} points; subtracting the pattern gives bit
vectors on J_0 and the available coordinates, so that set has M_K > 2^{eta N}.
Equation (8.12) makes each A_i nonempty.)
The W_i form a direct sum: in 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 so on.
Thus t <= (dim F)/N <= 1; each increment is >= eta - 2 eta^3, so there are
fewer than 3/eta steps and the stopping condition is reached. Available
sets shrink and |A_i| is nondecreasing; if the last has size sN then
t >= alpha - 2 eta, t_i <= |A_i|/N <= s. (8.14)
Remove one coordinate from the last A_i and adjoin all of J_0: the set D
satisfies
|D| = (d + s)N - 1, M_K(D) <= 2^{eta N}. (8.15)
The scalar function. For x, t > 0 define
e(x,t) = x - x^2/(2t) if 0 <= x <= t, e(x,t) = t/2 if x >= t.
It is nondecreasing in both arguments, changing in x at rate in [0,1] and
in t at rate in [0,1/2] (from the partials 1 - x/t and x^2/(2t^2) below the
kink, 0 and 1/2 above, continuous at x = t).
First application. Truncate D to size tN (M_K only shrinks). Proposition
8.3 with the constructed list (using t >= alpha - 2 eta >= 8 eta and
t_i <= s) gives
e(d+s, t) <= (1/t) sum_i t_i (t_i - alpha_i) + eta + eta^3/t + 1/N
<= s + O(eta)
(the 1/N accounts for the removed coordinate). Replacing t by alpha keeps
this: if t >= alpha use monotonicity in t; if t < alpha use its 1/2
Lipschitz bound and alpha - t <= 2 eta. So e(d+s, alpha) <= s + O(eta).
With h = d + s: if h <= alpha then d <= h^2/(2 alpha) + O(eta), so
h >= sqrt(2 d alpha) - O(sqrt eta); if h >= alpha then s >= alpha/2 -
O(eta), so h >= d + alpha/2 - O(eta) >= sqrt(2 d alpha) - O(eta). Either way
d + s >= sqrt(2 d alpha) - O(sqrt eta). (8.16)
Second application. Use the same D with the singleton list {S_*}. Truncate
to size vN. Proposition 8.3 and (8.13) give
e(d+s, v) <= v - alpha_* + eta + eta^3/v + 1/N <= v - alpha + O(eta)
(for v >= alpha - 2 eta^3 >= 9 eta). Since v <= f and e grows at rate
<= 1/2 in its second argument,
e(d+s, f) <= e(d+s, v) + (f - v)/2 <= f - alpha + O(eta). (8.17)
Solve. If d >= f then d + s >= f, so (8.17) gives alpha <= f/2 + O(eta) =
f z(d/f) + O(eta). If d <= f, put u = d/f in [0,1]. Monotonicity and the
unit Lipschitz bound of e in x, with (8.16) and (8.17), give
e(sqrt(2 d alpha), f) <= f - alpha + O(sqrt eta). (8.18)
From (8.1) one checks 2 u z(u) <= 1 and 1 - z(u) = sqrt(2 u z(u)) - u z(u),
so alpha_0 = f z(u) satisfies e(sqrt(2 d alpha_0), f) = f - alpha_0. The map
a -> a + e(sqrt(2 d a), f) is nondecreasing and increases at least as fast as
a, so (8.18) gives alpha <= alpha_0 + O(sqrt eta). In both cases
alpha <= f z(d/f) + O(sqrt eta) = 1 - c(d/2) + O(sqrt eta). (8.19)
Finally, monotonicity of c, (8.10), and (8.3) give
c(q) <= c(d/2) + O(sqrt(l/log N)), so
alpha <= 1 - c(q) + O(sqrt eta) + O(sqrt(l/log N)).
Because D_0 > 2A is fixed, both error terms are o(l^{-A}); for large N their
sum is at most l^{-A}, proving (8.2). The argument was deterministic for
every K on the single typical event of Proposition 8.3, so it holds
simultaneously in K. QED
==========================================================================
9. PRICING RETAINED LAYERS BY CERTIFICATES
==========================================================================
Retaining layers forces the new column into a lattice (Lemma 7.4); its
weight q(E) sets the probability. We count PARTIAL certificates so that
the certificate size can be chosen per class of outcomes -- this is what
lets Section 10 choose the target according to the largest potential in a
class. We first bound the probability that one fixed certificate is
honored, then double count.
Fix exposed data F that determines nonsingular binary C of size m in I_N
and a quotient pi: Z^m ->> G with C Z^m <= ker pi, with the tested column v
conditional uniform on bits^m. Take C in the typical set of Proposition
8.1 at precision A_cube. For a fixed set E of positive layers of G let R
be the layers retained when quotienting by pi(v). Lemma 7.4 gives K_E
with C Z^m <= K_E <= Z^m, [Z^m : K_E] = N^{N q(E)},
q(E) = sum_{(p,e) in E} k_G(p,e) nu_p, and E <= R implies v in K_E. The
budget gives 0 <= q(E) <= 1/2. Conditional uniformity and the simultaneous
cube estimate give
Pr(E <= R | F) <= Pr(v in K_E | F) <= 2^{-m} M_{K_E}
<= 2^{-m} 2^{N(1 - c(q(E)) + l^{-A_cube})}
= 2^{-N(c(q(E)) - eta_N)}, eta_N = l^{-A_cube} + 1 - m/N, (9.1)
with 1 - m/N <= N^{-3/10}. One typical set serves every exposed quotient,
since all certificate lattices contain the original C Z^m.
For 0 <= t <= 1 let H_2(t) = -t log_2 t - (1-t) log_2(1-t). For s, u >= 0
and 0 <= x <= s define the entropy cost
E(s,u,x) = (s+u) H_2( x/(s+u) ) - s H_2( x/s ), (9.2)
with continuous values when a denominator vanishes. When all layers have
weight 1/N, the ratio C((s+u)N, xN)/C(sN, xN) counts possible certificates
against those offered by a fixed marked set, and its base-two logarithm is
N E(s,u,x) + O(log N).
Proposition 9.1 (certificate pricing). Fix A > 0 and at most two positive
constants w_i (only w_i in {1,2} needed). Typically for nonsingular binary
C of size m in I_N (imposing Proposition 8.1 at a large fixed precision),
the following holds. Let F fix C, a quotient G_C ->> G, and: a partition of
the layers of G into at most two categories, each a union of whole
plateaus, with every height in category i at least w_i. Conditional on F a
column v is uniform on bits^m; in the quotient by the image of v an outcome
may MARK some retained layers, the marked layers on each plateau forming a
prefix, and the marks may depend on other random bits.
Let A be any subevent. There is a partition of A into at most
2^{N l^{-A}} classes, built before choosing any representative or targets,
such that for any nonempty class A_alpha, any representative outcome, with
s_i, u_i the marked and unmarked weights in category i, and any
0 <= x_i <= s_i,
Pr(A_alpha | F) <= 2^{-N( c(sum_i w_i x_i) - sum_i E(s_i,u_i,x_i)
- l^{-A} )}. (9.3)
The estimate is uniform in the exposed data, the quotient, the subevent,
and the representative; the data may include a preceding column that fixes
G provided v stays conditionally uniform.
Proof. We condition on fixed exposed data. Fix a cube precision A_cube
(chosen at the end) and use (9.1) for each fixed candidate E; the quotient
G_C ->> G composed with Z^m ->> G_C gives the map pi there. Only conditional
uniformity of v is used; other random bits and the set A need not be
independent of v.
Construct the classes. Fix D > 0 (chosen at the end), delta = l^{-D},
a_p = log_N p. The order bound gives
sum_{p,e} k_G(p,e) a_p/N <= 1/2, sum_{p,e} k_G(p,e) <= (N log N)/(2 log 2).
Classify marks by prime range.
(i) a_p > l^D: record every mark bit. At most N/(2 l^D) such layers,
cost O(N l^{-D}) bits.
(ii) a_p < 1 - delta: record the number of marks on each plateau (these
determine the prefix marks). At most N^{1-delta} such primes; with
d_p the number of plateaus at p, d_p(d_p+1)/2 <= sum_e k_G(p,e),
Cauchy-Schwarz + the second bound above give total plateau count
O(N^{1 - delta/2} sqrt(log N)), each prefix count O(log N) bits:
cost O(N^{1 - delta/2}(log N)^{3/2}) = o(N l^{-D}) (since
delta log N >> log log N).
(iii) 1 - delta <= a_p <= l^D: split each category's range into cells of
width <= delta (a category-cell pair is a "cell"); J = O(l^{2D})
cells. In a cell j with lower endpoint lambda_j, record only the
number of marks. Total layers here O(N), cost
O(l^{2D} log N) = o(N l^{-D}) bits.
All records depend only on the marks and exposed data; intersecting their
classes with A gives the classes for A, fewer than 2^{O(N l^{-D}) +
o(N l^{-D})}, uniformly.
Fix a class, a representative, and targets. For category i put
theta_i = x_i/s_i (s_i > 0) else 0. Known marked sets (ranges (i),(ii))
are included whole. In an intermediate cell j of category i with n_j
layers and r_j recorded marks, require the certificate to contain any
a_j = floor(theta_i r_j) of the marks. Each outcome of the class offers
exactly m-prod = prod_j C(r_j, a_j) certificates, while the class has at
most n-prod = prod_j C(n_j, a_j) possible certificates (allowing arbitrary
layers in each cell, no prefix constraint -> an upper bound).
The weight certified is uniform over the class. In category i let s_i^0
be the known marked weight; the representative's intermediate marked
weight differs from sum_j lambda_j r_j/N by O(delta), and the selected
weight is at least theta_i sum_j lambda_j r_j/N - O(l^{3D}/N), so
the selected weight in category i is at least x_i - O(delta),
and every selected layer has height >= w_i. Hence, uniformly over the
choices,
q(E) >= q_0 - O(delta), q_0 = sum_i w_i x_i, (9.4)
both in [0,1/2]. Since c is increasing and Hoelder 1/2 on [0,1/2],
c(q(E)) >= c(q_0) - O(sqrt delta). With (9.1), any fixed candidate
certificate is honored with probability <= 2^{-N(c(q_0) - eta_N -
O(sqrt delta))}, also after intersecting with the class and A (that
intersection still implies v in K_E).
Double count outcome-certificate pairs:
Pr(A_alpha | F) <= (n-prod / m-prod) 2^{-N(c(q_0) - eta_N - O(sqrt delta))}. (9.5)
(Summing over candidate certificates, a class outcome offers m-prod of
them, and each summand is bounded by the fixed-certificate estimate; no
independence of the marks is needed.)
Bound the ratio. For integers 0 <= a <= n,
n H_2(a/n) - log_2(n+1) <= log_2 C(n,a) <= n H_2(a/n)
(paths: nH_2(a/n) >= log_2 C(n,a) since the binomial probability at a is
<= 1; a is a mode so n+1 = sum of probabilities >= C(n,a)2^{-nH_2(a/n)}).
Per cell,
(1/N) log_2 C(n_j,a_j)/C(r_j,a_j)
<= E( r_j/N, (n_j-r_j)/N, a_j/N ) + log_2(r_j+1)/N,
all arguments in a fixed bounded set. Replacing a_j/N by theta_i r_j/N
changes this by O(N^{-1/2}) (Hoelder), and after summing over J = O(l^{2D})
cells all rounding errors are O(l^{2D}(N^{-1/2} + log N/N)), below every
fixed negative power of l.
Convert counts to weights. Nonnegativity and homogeneity give, per cell in
category i,
E_{theta_i}( r_j/N, (n_j-r_j)/N )
<= (1 - delta)^{-1} E_{theta_i}( lambda_j r_j/N,
lambda_j (n_j-r_j)/N ),
and the superadditivity sum_j E_theta(s_j,u_j) <= E_theta(sum s_j, sum u_j)
bounds the weighted cell terms by E_{theta_i}(s_i-under, u_i-under) with
s_i-under = s_i^0 + sum_j lambda_j r_j/N, u_i-under = u_i^0 + sum_j
lambda_j(n_j-r_j)/N. Since 0 <= s_i - s_i-under = O(delta) and likewise for
u_i, and all weights sum to at most 1/2, the Hoelder estimate and the factor
(1-delta)^{-1} = 1 + O(delta) give
(1/N) log_2 (n-prod/m-prod)
<= sum_i E(s_i,u_i,x_i) + O(sqrt delta)
+ O(l^{2D}(N^{-1/2} + log N/N)). (9.6)
Choose D large enough that l^{-D/2} = o(l^{-A}), then A_cube > A. The class
count is at most 2^{N l^{-A}}, and eta_N plus the rounding errors plus the
two O(sqrt delta) errors sum to at most l^{-A} for large N. Substituting
(9.6) into (9.5) proves (9.3). Every precision was fixed before N grew and
was independent of the quotient and exposed columns. QED
We next extract a uniform cost for retaining a noticeable total weight.
Set
R = ceil(l^2), sigma = R^{-6}. (9.7)
Proposition 9.2 (retained-layer cost). Typically for nonsingular binary
C of size m in I_N: let h in {1,2} and v_1,...,v_h independent uniform
columns in bits^m, conditionally on C. Starting from G^{(0)} = G_C, let
G^{(j)} be the quotient of G^{(j-1)} by the image of v_j. For each
1 <= j <= h, conditionally on any preceding columns,
Pr( sum_{retained in G^{(j-1)} ->> G^{(j)}} nu_p >= sigma
| C, v_1,...,v_{j-1} ) <= 2^{-N sigma/2}. (9.8)
The typical set imposes one fixed precision on C, independent of the
preceding columns; no nonsingularity of the destination matrix is needed.
Proof. Apply Proposition 9.1 at precision A_0 = 40. For the j-th quotient
condition on C and v_1,...,v_{j-1} (fixing the map to G^{(j-1)}), so v_j
stays uniform. Use one category of all layers, w_1 = 1, mark all retained
layers (prefixes by Lemma 7.3). On the subevent of (9.8) a representative
has marked weight s >= sigma, so choose x = sigma^2. The total layer
weight s+u is <= 1/2 by (2.1). With H_2(t) <= t log_2(e/t), (9.2) gives
0 <= E(s,u,sigma^2) <= (s+u) H_2(sigma^2/(s+u))
<= O(sigma^2 log(1/sigma)),
uniform over the representatives. The profile satisfies c(q) = 2 sqrt q +
O(q) as q -> 0 (because u = 2q/(1-2q) = 2q + O(q^2)); in particular
c(q) >= (3/2) sqrt q for small q. So each class probability is at most
2^{-N((3/2) sigma - O(sigma^2 log(1/sigma)) - l^{-40})},
and there are at most 2^{N l^{-40}} classes. Since sigma = R^{-6} is
asymptotic to l^{-12}, both sigma^2 log(1/sigma) = o(sigma) and
l^{-40} = o(sigma); summing the class probabilities proves (9.8).
Only the quotient by the selected column is tested; no new principal block
is used. Conditional uniformity for a second column and the simultaneous
cube estimate over lattices containing C Z^m give the stated uniformity
over the preceding column. QED
==========================================================================
10. PAYING FOR AN INCREASE OF POTENTIAL
==========================================================================
We prove Proposition 7.2. For a width-one transition, two order bounds on
the endpoint groups restrict how layers can change; a scalar optimization
shows the certificate cost pays for the rise of Psi. Width two is paid by
the gate directly. This section has three parts: the layer accounting and
budgets (10.1), the reduction of Proposition 7.2 to one scalar inequality
(10.2), and that inequality (10.3).
--------------------------------------------------------------------------
10.1 Layer changes and order budgets
--------------------------------------------------------------------------
Fix a width-one transition C -> B between nonsingular matrices, and let Q
be the common quotient (from G_C by the new column, from G_B by the new
coordinate). For an old layer (p,e) write k = k_C(p,e), k' = k_Q(p,e).
Interlacing (7.11) gives
k' in {k-1, k}, k_B(p,e) in {k', k'+1}.
If k_C(p,e) = 0 the same statement gives k_B(p,e) <= 1, so the layer
contributes nothing to either potential.
Use weights nu_p throughout. In the HEIGHT-ONE category (old height 1),
mark exactly the layers that reach height two; in the category of old
height >= 2, mark every retained layer. Let g, v_0 be the marked and
unmarked weights of the first category, and a, u those of the second. The
following six types define L and P; the last column bounds the change of
potential per unit weight.
weight old ht retention dest ht potential change/unit
------------------------------------------------------------
g 1 retained 2 +beta
v_0 1 (may occur) <=1 0
a-L k>=2 retained k+1 +(6-beta)
L k>=2 retained k 0
u-P k>=2 NOT retained k-1 -beta
P k>=2 NOT retained k 0
(The g-row is retained because k_B(p,e) = 2 forces k' = 1. Since
phi(2) = beta, phi(k) = 2k for k >= 3: an increase from height >= 2 costs at
most phi(k+1) - phi(k) <= 6 - beta per unit weight (equality at k = 2), a
decrease saves at least phi(k) - phi(k-1) >= beta, and staying flat costs
nothing.)
Both categories are unions of plateaus of G_C, and the marks are prefixes
(second category by retention; first because k_B(p,e) is nonincreasing in
e). So the marks have the form required by Proposition 9.1.
Flat compensation. We claim
P <= L, a_0 := a - L + P in [0, a]. (10.1)
(Then a_0 is an effective scalar mass; the actual marked family of the
second category has mass a >= a_0, so every 0 <= y <= a_0 is a valid
certificate target.) For the first assertion fix p and let t be the last
exponent with k_C(p,e) >= 2 (t = 0 if none); write the p-contribution to
each weight with subscript p. A retained layer in this range raises the
height by one unless flat; an unmarked layer lowers it unless it persists.
Lemma 7.5 with h = 1 gives
(a_p - L_p) - (u_p - P_p) = nu_p (F_B(p,t) - F_C(p,t))
<= nu_p (t - 2 U_t) = a_p - u_p,
the last step because U_t counts the unmarked layers in this range. Hence
P_p <= L_p; summing over primes gives P <= L. Also L <= a, so a_0 in
[0,a].
Potential increment. Summing the per-unit bounds over the table,
Psi(B) - Psi(C) <= beta g + (6-beta)(a-L) - beta(u-P)
= I - (6-2 beta) P <= I,
I := beta g + (6-beta) a_0 - beta u, (10.2)
using 6 - 2 beta > 0 and I - (6-2 beta)P = beta g + (6-beta)(a-L) -
beta(u-P) rearranged via a_0 = a - L + P.
Budgets. The total height-times-weight is at most 1/2 at both endpoints.
At B it is at least
2g + 3(a-L) + 2L + (u-P) + 2P = 2g + 3a + u - L + P >= 2g + 3a_0 + u,
and at C it is at least g + v_0 + 2a + 2u >= g + v_0 + 2a_0 + 2u. Hence
2 g + 3 a_0 + u <= 1/2, g + v_0 + 2 a_0 + 2 u <= 1/2. (10.3)
--------------------------------------------------------------------------
10.2 Reduction to a scalar inequality
--------------------------------------------------------------------------
Lemma 10.2 (budget optimization). Let c and E be from (8.2) and (9.2),
beta = 7/5. If g, v_0, a_0, u >= 0 satisfy (10.3), then there are
x in [0,g] and y in [0,a_0] with
c(x + 2y) - E(g,v_0,x) - E(a_0,u,y)
>= beta g + (6 - beta) a_0 - beta u = I. (10.4)
The inequality says: certificate concentration, after paying both entropy
costs, covers the upper bound I for the potential increase. Its proof is
the whole of Section 10.3.
Proof of Proposition 7.2. Fix the desired precision A > 0 and set
A_1 = A + 2.
WIDTH ONE. Take nonsingular C in the typical set of Proposition 9.1 at
precision A_1 for (w_1,w_2) = (1,2). Extend the marking rule to singular
outcomes by leaving all layers unmarked. Apply Proposition 9.1 with
exposed information C, starting quotient G_C, and subevent {det B != 0}.
The tested column is uniform conditional on C, and the marks may depend on
the new diagonal bit. This gives at most 2^{N l^{-A_1}} classes; in each
nonempty class C choose a representative B_C maximizing Psi in that class
(the outcome space is finite).
For this representative form g, v_0, a, u, L, P, a_0, I as in (10.2);
Lemma 10.2 supplies x in [0,g], y in [0,a_0]. These are admissible
certificate targets for the two categories (minimum heights one and two),
since a_0 <= a. The monotonicity of E in its first argument gives
c(x+2y) - E(g,v_0,x) - E(a,u,y)
>= c(x+2y) - E(g,v_0,x) - E(a_0,u,y) >= I.
So Proposition 9.1, on this representative in the restricted outcome space,
gives Pr(C | C) <= 2^{-N(I - l^{-A_1})}. And since
Psi(B_C) - Psi(C) <= I,
E[ 1_C 2^{N Psi(B)} | C ] <= 2^{N Psi(B_C)} Pr(C | C)
<= 2^{N(Psi(C) + l^{-A_1})}.
Summing over the classes,
E[ 1_{det B != 0} 2^{N Psi(B)} | C ] <= 2^{N(Psi(C) + 2 l^{-A_1})}
<= 2^{N(Psi(C) + l^{-A})}
for large N.
WIDTH TWO. Take C also in the typical set of Proposition A at precision
A_1, and let m be its size. Conditional on C the cross columns v_1, v_2 are
independent uniform on bits^m, and the gate is G_2 = {v_1, v_2 in S(C)}.
Proposition A gives
Pr(G_2 | C) = 2^{-2m} |S(C)|^2 <= 2^{-2m + 2N(Psi(C) + l^{-A_1})}.
On nonsingular outcomes Psi(B) <= 1, so
E[ 1_{det B != 0} 1_{G_2} 2^{N Psi(B)} | C ]
<= 2^{N - 2m + 2N(Psi(C) + l^{-A_1})}
<= 2^{N(Psi(C) + 2(1 - m/N) + 2 l^{-A_1})}
<= 2^{N(Psi(C) + l^{-A})},
using Psi(C) <= 1, 1 - m/N <= N^{-3/10} = o(l^{-A}), and A_1 = A + 2.
Intersecting the two typical sets proves both conditional assertions of
Proposition 7.2 with arbitrary fixed precision and the stated indicators.
QED
--------------------------------------------------------------------------
10.3 Proof of the budget optimization (Lemma 10.2)
--------------------------------------------------------------------------
Throughout, c is the profile (8.2) and E(s,u,x) = (s+u)H_2(x/(s+u))
- s H_2(x/s) is (9.2). For w, t >= 0 put
c*(w) = max_{0 <= q <= 1/2} ( c(q) - w q ),
F_t(s,u) = max_{0 <= x <= s} ( t x - E(s,u,x) ).
When s = 0 both are read as their values at x = q = 0; for t = 0 they
vanish.
STEP 1: a dual characterization. Write I = beta g + (6-beta) a_0 -
beta u. We first show that it suffices to prove, for every w >= 0,
c*(w) + F_w(g,v_0) + F_{2w}(a_0,u) >= I. (10.5)
That (10.5) implies (10.4): if g = a_0 = 0 take x = y = 0. Otherwise let
(x_*,y_*) maximize the left side of (10.4) on the compact rectangle
[0,g] x [0,a_0], and put q_* = x_* + 2 y_*. The objective at (0,0) is
zero. Near zero E(g,v_0,x) = O(x) and E(a_0,u,y) = O(y) (the derivative of
H_2 at 0 is infinite, but for fixed g+u bounded away from 0 the cost is
O(x log(1/x)) = O(x) here); since c(q) >= (3/2) sqrt q for small q
(Section 9), the maximum is positive, so q_* > 0.
Take w = c'(q_*) if q_* < 1/2, and the left derivative of c at 1/2 if
q_* = 1/2. This is a nonnegative supporting slope of the concave function
c, so c(q) - w q <= c(q_*) - w q_* for all q, i.e. c*(w) = c(q_*) - w q_*.
Let K(x,y) = E(g,v_0,x) + E(a_0,u,y), which is convex. Claim: (x_*,y_*)
maximizes w(x+2y) - K(x,y) on the same rectangle. If some (x,y) gave
strictly more, take the point a fraction theta along the segment from
(x_*,y_*) to (x,y). Convexity of K and one-sided differentiability of c in
this feasible direction give, as theta -> 0, an increase in the objective
of (10.4) of at least
theta( w(x+2y-q_*) - K(x,y) + K(x_*,y_*) ) + o(theta) > 0,
contradicting maximality. This maximum separates, so it equals
F_w(g,v_0) + F_{2w}(a_0,u). Hence the maximum of the left side of (10.4)
is exactly c*(w) + F_w(g,v_0) + F_{2w}(a_0,u), which (10.5) bounds below by
I. Done.
STEP 2: entropy minimum and a criterion. Put D(t) = -log_2(1 - 2^{-t}) for
t > 0. For r >= 0, maximizing H(z,r) - tz over 0 <= z <= 1 at
z = min{1, r/(2^t-1)} gives
F_t(1,r) = t - H(1,r) + D(t) r for 0 <= r <= 2^t - 1,
F_t(1,r) = 0 for r >= 2^t - 1.
For h >= 0 the derivative of F_t(1,r) + hr on the first branch is
D(t) + h - log_2(1 + 1/r); it increases in r and vanishes at
r = (2^{D(t)+h} - 1)^{-1} <= 2^t - 1 (equality only when h = 0); on the
second branch hr is nondecreasing. Evaluating at that minimum gives, for
t > 0,
min_{r>=0} ( F_t(1,r) + h r ) = t - D(D(t) + h)
=: L(t,h) = log_2( 1 + (2^t - 1)(1 - 2^{-h}) ), (10.6)
and L(0,h) = 0 (so (10.6) holds at t = 0 too, with value zero).
Criterion. For a given w it suffices to find lambda, mu >= 0 with
2 lambda + mu + L(w, mu) >= beta, (10.7a)
3 lambda + 2 mu + L(2w, beta+lambda+2mu) >= 6 - beta, (10.7b)
(lambda + mu)/2 <= c*(w). (10.7c)
Indeed, F_t is homogeneous of degree one in its first two arguments, so
from (10.6)
F_w(g,v_0) + mu v_0 >= g L(w, mu),
F_{2w}(a_0,u) + (beta+lambda+2mu)u >= a_0 L(2w, beta+lambda+2mu);
both remain valid when g = 0 or a_0 = 0. Adding and using (10.7a)-(10.7b),
F_w(g,v_0) + F_{2w}(a_0,u)
+ lambda(2g + 3a_0 + u) + mu(g + v_0 + 2a_0 + 2u) >= I.
Then the budgets (10.3) and (10.7c) turn "lambda(...) + mu(...)" into
"-(lambda+mu)/2 >= -c*(w)", yielding (10.5). So it remains to select
lambda, mu for each w.
STEP 3: input estimates. We will use the support bounds
2 c*(w) >= max{ 2 - w, 3/2 - w/2, 23/24 - w/6, 2/(w+2) }. (10.8)
The first three follow by testing q = 1/2, 1/4, 1/12 in c*(w): here
c(1/2) = 1, c(1/4) = 3/4, and c(1/12) = 23/48 (at q = 1/12 the argument of
z is 1/5, its square root is 3/5, so c(1/12) = 1 - (5/6)(5/8) = 23/48).
For the last, on 0 <= q <= 1/4 put r = 2 sqrt(q(1-3q))/(1-2q); then
r^2 - 4q = 4q^2(1-4q)/(1-2q)^2 >= 0 and (r+2q)/(1+r) increases in r, so
c(q) = (r+2q)/(1+r) >= (2 sqrt q + 2q)/(1 + 2 sqrt q) >= 2 sqrt q - 2q,
whose difference is 4q sqrt q/(1 + 2 sqrt q); testing q = (w+2)^{-2} <= 1/4
gives 2c*(w) >= 2(2/(w+2) - (w+2)/(w+2)^2) = 2/(w+2), including w = 0.
One global estimate handles the middle range:
L(w, 1/4) > (w - 1)/2 for all w >= 0. (10.9)
For this let b = 2^{-1/4}; the integer inequality 20^4 < 2 * 17^4 gives
1/2 < b < 17/20. Since b(1-b) decreases for b >= 1/2,
b(1-b) > (17/20)(3/20) = 51/400 > 1/8, so the AM-GM inequality gives
2^{L(w,1/4)} = b + (1-b) 2^w >= 2 sqrt(b(1-b) 2^w) > 2^{(w-1)/2},
which is (10.9).
STEP 4: the choice of (lambda, mu). Writing h = beta + lambda + 2mu, take
(lambda, mu) =
( max{2 - w, 3/2 - w/2}, 0 ) for 0 <= w <= 8/5,
( 17/24 - w/6, 1/4 ) for 8/5 <= w <= 3,
( 0, 3 * 2^{-w} ) for w >= 3.
Either choice works at a shared endpoint. The next step verifies
(10.7a)-(10.7c) for these, which completes the proof of Lemma 10.2.
STEP 5: verification of (10.7a)-(10.7c). beta = 7/5, 6 - beta = 23/5. We
check the three ranges; in each, (10.7c) comes directly from a support
bound (10.8), and (10.7a)-(10.7b) from the input estimates (10.8)-(10.9)
and monotonicity of L in both arguments.
RANGE 1: 0 <= w <= 8/5, lambda = max{2-w, 3/2-w/2}, mu = 0, so L(w,0)=0.
(a) For w <= 1, 2lambda = 4-2w >= 2 > beta; for 1 <= w <= 8/5,
2lambda = 3 - w >= 3 - 8/5 = 7/5 = beta. Good.
(c) lambda = 2-w (w<=1) is the first support quantity, and
lambda = 3/2-w/2 (w>=1) the second, so lambda <= 2c*(w) always; hence
(lambda+mu)/2 = lambda/2 <= c*(w).
(b) 3lambda + L(2w, beta+lambda) >= 23/5. At w = 0 this is 6. On
[0,1], 3lambda = 6-3w decreases and L(2w,beta+lambda) increases (2w up,
lambda down so the entropy rises); on [1,8/5] the term 3lambda = 9/2 -
3w/2 decreases by 3/2*(3/5) = 9/10 while L rises from 1.78 to 2.86.
The minimum is at w = 1, where 3 + L(2, 12/5) = 3 + 1.78 = 4.78 > 23/5.
RANGE 2: 8/5 <= w <= 3, lambda = 17/24 - w/6, mu = 1/4.
(c) (lambda+mu)/2 = (23/24 - w/6)/2, which is exactly (10.8)'s third
quantity halved, so it is <= c*(w).
(a) 2lambda+mu+L(w,1/4) = 5/3 - w/3 + L(w,1/4). By (10.9) this exceeds
5/3 - w/3 + (w-1)/2 = 7/6 + w/6, which is >= 7/5 because w >= 7/5
(here w >= 8/5).
(b) 3lambda+2mu+L(2w,h_2) = 21/8 - w/2 + L(2w,h_2) with
h_2 = 7/5+29/24-w/6. On [8/5,3] this is increasing (the gain in L
from t = 2w dominates the loss -w/2 and the small drop of h_2); the
values are 4.74 at w = 8/5, 5.32 at w = 2, and 6.76 at w = 3, all
>= 23/5.
RANGE 3: w >= 3, lambda = 0, mu = 3*2^{-w}.
(a) mu + L(w,mu) = 3*2^{-w} + log_2(1+(2^w-1)(1-2^{-3*2^{-w}})), equal to
1.755 at w = 3 and increasing to the limit log_2(1+3 ln 2) = 1.62 as
w -> infinity (using 1-2^{-mu} ~ mu ln 2 = 3*2^{-w} ln 2); both exceed
7/5.
(c) (lambda+mu)/2 = 1.5*2^{-w} <= 1/(w+2) <= c*(w) for w >= 3 (the last by
the fourth bound in (10.8), since 1.5(w+2) <= 2^w there).
(b) 6*2^{-w} + L(2w, 7/5+6*2^{-w}) >= 23/5: equal to 6.39 at w = 3 and
growing, since L(2w,.) ~ 2w + log_2(1-2^{-7/5}) for large w.
All three ranges satisfy (10.7a)-(10.7c); STEP 2 then gives (10.5), and
STEP 1 gives (10.4). This proves Lemma 10.2, hence Proposition 7.2, and
completes Section 10. QED
==========================================================================
11. PATHS OF PRINCIPAL MINORS: PROOF OF PROPOSITION B
==========================================================================
We prove the potential moment E[1_{det != 0} 2^{N Psi}] <= 2^{o(N)}. The
idea: grow a nonsingular principal minor by one or two coordinates at a
time; each step is priced by Proposition 7.2 (width one, via certificates)
or by the gate (width two). A path exists in reverse by gated deletion.
A tail statistic controls layers of large height; on a short terminal
window either the potential is small at some node (and the step errors are
then only o(N)) or a second statistic decreases so much that many costly
steps are forced, which is exponentially unlikely.
--------------------------------------------------------------------------
11.1 The tail statistic and its recursion
--------------------------------------------------------------------------
For nonsingular B and s >= 0 put
W_s(B) = sum_{p,e} (k_B(p,e) - s)_+ nu_p, x_+ = max{x,0},
and W_s(B) = 0 on singular B when it appears next to a nonsingularity
indicator. The budget (2.1) gives 0 <= W_s(B) <= 1/2, and for s >= 1
W_{s-1}(B) - W_s(B) = sum_{k_B(p,e) >= s} nu_p. (11.1)
In the layer diagram (Figure 1) the factor (k_B - s)_+ counts boxes in row
e beyond the first s columns, weighted by nu_p. So W_s is the weight of
layers taller than height s: the "tail" beyond level s.
Lemma 11.1 (tail recursion). Let C -> B be a transition of width h in
{1,2} between nonsingular matrices. In the i-th successive quotient of
G_C write k_{i-1}(p,e) for the height before that quotient and R_i for its
retained layers. For every integer s >= h,
W_s(B) <= W_{s+h}(C) + 2 sum_{i=1}^{h}
sum_{(p,e) in R_i, k_{i-1}(p,e) >= s+1-h} nu_p. (11.2)
Proof. Fix a prime p, put F_D(p,t) = sum_{e=1}^{t} k_D(p,e) for D = C, B.
Let t be the largest e with k_B(p,e) > s (t = 0 if none). Then
sum_{e>=1}(k_B(p,e)-s)_+ = F_B(p,t) - s t,
and for e <= 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, and
interlacing (7.9) gives, for e <= t and 1 <= i <= h,
k_{i-1}(p,e) >= k_B(p,e) - h >= s+1-h >= 1.
Let u_i(p,t) be the total drop in the first t layers at the i-th quotient
and U_p(t) = sum_i u_i(p,t). Each layer here has positive starting height
and each drop is zero or one, so
h t - U_p(t) = sum_{i=1}^{h} #{ e <= t : (p,e) in R_i },
and every layer on the right has the height bound above. Lemma 7.5 then
gives
F_B(p,t) - s t
<= F_C(p,t) - (s+h)t + 2(h t - U_p(t))
<= sum_{e>=1}(k_C(p,e)-s-h)_+
+ 2 sum_{i=1}^{h} #{ e : (p,e) in R_i, k_{i-1}(p,e) >= s+1-h }.
Multiply by nu_p and sum over p. QED
--------------------------------------------------------------------------
11.2 Paths, the typical set, and the covering
--------------------------------------------------------------------------
We prove the potential moment E[1_{det != 0} 2^{N Psi}] <= 2^{o(N)}. The
idea: grow a nonsingular principal minor by one or two coordinates at a
time, pricing each step by Proposition 7.2 (width one, via certificates)
or by the gate (width two). A path exists in reverse by gated deletion.
The tail statistic (11.2) controls layers of large height; on a short
terminal window either the potential is small at some node (and the step
errors are then only o(N)) or a second statistic decreases so much that
many costly steps are forced, which is exponentially unlikely.
Throughout, eps in (0,1/10), eps' = eps/20, and
J_* = 2 ceil(N^{3/5}), L_* = ceil(R^{12}), R = ceil(l^2). (11.3)
The following comparisons hold for large N (R asymptotic to l^2, every
fixed power of l is o(N^a) for a > 0):
2 J_* + 1 < N^{7/10}, L_* asymptotic to l^{24} = o(N^{3/5}),
J_* - L_* > ceil(N^{3/5}),
L_* l^{-60} = O(l^{-36}) = o(1),
L_* sigma / R^3 asymptotic to R^3 -> infinity,
N sigma / log R = N/(R^6 log R) -> infinity. (11.4)
The first line keeps every node in I_N and leaves enough preceding steps
to drive the tail threshold past N^{3/5}; sigma = R^{-6} is from (9.7).
The typical set. For m in I_N let T_m be the set of nonsingular matrices
satisfying the conclusions of Propositions 5.4 (prime corank), 9.2
(retained-layer cost), A (admissible columns) and 7.2 (potential step, both
widths) at precision A = 60. These are finitely many properties, so for
some f(N) -> infinity
Pr{ det B_m != 0, B_m not in T_m } <= 2^{-N f(N)} (m in I_N).
Write m_* = N - 1 and consider all principal submatrices of B_{m_*}
obtained by deleting at most 2 J_* indices. Their sizes lie in I_N by
(11.4), and their number is at most
sum_{d <= 2J_*} C(m_*,d) <= 2^{O(N^{3/5} log N)} = 2^{o(N)}.
Let E_N be the event that any nonsingular one of these fails its typical
properties. Each fixed submatrix is a binary matrix, so the union bound
gives
Pr(E_N) <= 2^{-N(f(N) - O(N^{-2/5} log N))} = 2^{-omega(N)}. (11.5)
Since 2^{N Psi} <= 2^N, this event contributes at most
2^N Pr(E_N) = 2^{-omega(N)} to the moment.
The covering by paths. Starting from a nonsingular realization on [m_*],
apply Lemma 7.1 (gated deletion) backwards J_* times. It produces a path
of nonsingular principal minors, each deletion of width one or two, with
every width-two deletion satisfying the gate when read forward. At most
2 J_* indices are deleted, so all nodes stay in range, and on E_N^c every
node is typical.
The path is chosen backwards as a function of the realized terminal
matrix; we use it only to cover the terminal event. Let Pi_N be the
collection of all FIXED index paths
I_0 subset I_1 subset ... subset I_{J_*} = [m_*],
h_t = |I_t \ I_{t-1}| in {1,2},
with an ordering of the two indices of a pair fixed once per path. At each
backward step there are at most 2 N^2 choices, so
|Pi_N| <= (2 N^2)^{J_*} = 2^{O(N^{3/5} log N)} = 2^{o(N)}. (11.6)
For pi in Pi_N put B_t = B_{m_*}[I_t]. Let Gamma_t be the event G_{h_t}
from (7.2) for step t, and define
A_pi = (intersection_t {B_t in T_{|I_t|}}) ∩ (intersection_t Gamma_t).
The backward construction shows every nonsingular terminal matrix outside
E_N lies in at least one A_pi, so
E[1_{det B_{m_*} != 0} 2^{N Psi(B_{m_*})}]
<= sum_{pi in Pi_N} E[1_{A_pi} 2^{N Psi(B_{J_*})}]
+ 2^{-omega(N)}. (11.7)
--------------------------------------------------------------------------
11.3 Heavy retention and costly steps
--------------------------------------------------------------------------
Now fix pi in Pi_N and study A_pi. Write F_{t-1} for the sigma-field of
all bits exposed through B_{t-1}.
Retained-layer cost. For a nonsingular start C, cube concentration
(Proposition 8.1) with c(q) >= (3/5) q on 0 <= q <= 1/2 (since
c(q) >= 2 sqrt q - 2q >= (3/5)q there) gives, for a set E of retained
layers of height >= R-1 with weight q(E) = sum_{(p,e) in E} nu_p and a
uniform column v,
Pr( v in K_E | F ) <= 2^{-m} M_{K_E} <= 2^{-3 N q(E)/5 + o(q(E)N)}.
The o(qN) absorbs the polynomial count of possible "prefix masks" (the
retained layers on each plateau form a prefix; there are at most
2^{o(qN)} such masks, since sum k_H <= log_2|H| = O(N log N) and only
primes p <= N^{1/2} contribute). (11.8)
Costly steps. For each quotient of step t let V_{t,i} be the total weight
nu_p of all its retained layers. On A_pi, call a step of the terminal
window {J_*-L_*, ..., J_*} costly if some V_{t,i} >= sigma, or if it has
width two and its starting node C = B_{t-1} satisfies Psi(C) <= 1 - 1/R.
To price this without conditioning on A_pi, define the exposure event D_t:
the starting node is in T_m and either some V_{t,i} >= sigma, or the step
has width two, Psi(C) <= 1-1/R, and its gate Gamma_t holds. On A_pi every
costly step satisfies D_t.
Pr(D_t | F_{t-1}) <= p_N := 3 * 2^{-N sigma/2}. (11.9)
Indeed, each event {V_{t,i} >= sigma} has probability <= 2^{-N sigma/2} by
Proposition 9.2. For the other alternative, the two cross columns are
conditionally independent and the gate needs both in S(C); Proposition A
gives
Pr(Gamma_t | F_{t-1}) = (|S(C)|/2^m)^2
<= 2^{-2N(1 - Psi(C) - l^{-60} - (1-m/N))},
and if Psi(C) <= 1-1/R then l^{-60} + N^{-3/10} = o(R^{-1}) and
sigma = R^{-6} = o(R^{-1}), so this is <= 2^{-N/R} <= 2^{-N sigma/2}.
There are at most two quotients, so (11.9) holds by the union bound, and
successive conditioning gives, for any fixed set T of positions,
Pr( intersection_{t in T} D_t ) <= p_N^{|T|}. (11.10)
The heavy-window moment. Set q_min = eps'/(100 log N) and, for a cross
column with quotient weight Q,
tQ = Q if Q >= q_min, tQ = 0 otherwise,
with tQ = 0 for a singular start (works because Q <= 1/2 there is
automatic). Introduce dyadic q_j = 2^j q_min up to 1/2. Conditionally on
everything exposed before a cross column, (11.8) gives
E[ 2^{N tQ/4} | previous ] <= 1 + sum_j 2^{N q_j/2} 2^{-3N q_j/5}
<= 1 + sum_j 2^{-N q_j/10} <= 1 + delta_N,
delta_N = 2^{-eps' N/(2000 log N)}. (11.11)
With d_pi = sum_t h_t <= 2 J_* = O(N^{3/5}) cross columns, successive
conditioning gives
E 2^{(N/4) sum_a tQ_a} <= (1+delta_N)^{d_pi}
<= exp(O(N^{3/5} delta_N)) = 1 + o(1). (11.12)
Large tails in the window. On A_pi suppose W_R(B_t) > eps' at some node
{J_*-L_* <= t <= J_*}. Iterate the tail recursion (11.2) backwards,
increasing s by the width at each step, and stop when s > N^{3/5}. This
takes at most ceil(N^{3/5}) steps, available since J_*-L_* > ceil(N^{3/5})
by (11.4). At the last node the tail is zero: prime corank
(Proposition 5.4) gives k_B(p,e) <= k_B(p,1) = corank_{F_p}(B) <= N^{3/5}
at every typical node. Number the backwards steps j = 1,...,r. Before
step j, s = R + (widths of its j-1 predecessors), and each charged layer
has height >= s+1-h >= R+j-2, so the charge from one quotient is at most
2Q/(R+j-2). The terms with Q < q_min contribute at most
4 q_min sum_{j<=r} 1/(R+j-2) <= 4 q_min (1 + log N) <= eps'/2.
Hence the remaining charges exceed eps'/2, so
sum_a tQ_a >= eps'(R-1)/4.
By (11.12) and Markov,
Pr( A_pi, max_{window} W_R > eps' ) <= 2^{-eps' N(R-1)/16}
* exp(O(N^{3/5} delta_N)) = 2^{-Omega_eps(NR)} = 2^{-omega(N)}. (11.13)
--------------------------------------------------------------------------
11.4 Descent at noncostly steps
--------------------------------------------------------------------------
To force many costly steps on the window event below, combine two tails.
At width one the R^{-2}W_1 term uses the mass of layers of height >= 2; at
width two, W_2 uses the gap between W_2 and W_4, and the small coefficient
keeps the W_1 term from cancelling it. Define
Z(B) = W_2(B) + R^{-2} W_1(B).
The budget gives 0 <= Z(B) <= (1+R^{-2})/2 <= 1. At a NONCOSTLY step all
its V_{t,i} are < sigma.
Width one. Lemma 11.1 gives W_2(B) <= W_3(C) + 2 sigma <= W_2(C) + 2
sigma and W_1(B) <= W_2(C) + 2 sigma. For a node of the window with high
potential, (11.1) and the lower bound sum_{k>=2} nu_p >= eps/(10R)
(path-window-two, below) give W_1(C) - W_2(C) >= eps/(10R), hence
Z(B) - Z(C) <= 2 sigma(1+R^{-2}) - R^{-2}(W_1(C)-W_2(C))
<= 2 sigma(1+R^{-2}) - eps/(10 R^3) <= -eps/(20 R^3),
using sigma = R^{-6} = o_eps(R^{-3}).
Width two. A noncostly width-two step has Psi(C) > 1 - 1/R. Lemma 11.1
gives W_2(B) <= W_4(C) + 4 sigma, and (path-window-three) gives
W_2(C) - W_4(C) = sum_{k_C>=3} min{k_C-2,2} nu_p >= 1/(20R); with
W_1(B) <= 1/2,
Z(B) - Z(C) <= -1/(20R) + 4 sigma + 1/(2R^2) <= -1/(40R)
<= -eps/(20 R^3)
for large N. Every noncostly step therefore decreases Z by at least
delta = eps/(20 R^3). (11.14)
--------------------------------------------------------------------------
11.5 The high window and the count of costly steps
--------------------------------------------------------------------------
Consider the event
H_pi = A_pi
∩ { max_{J_*-L_* <= t <= J_*} W_R(B_t) <= eps' }
∩ { min_{J_*-L_* <= t <= J_*} Psi(B_t) > eps }.
At a node B of H_pi, phi(k) <= 2k with phi(0)=phi(1)=0 gives
sum_{k_B(p,e) >= 2} k_B(p,e) nu_p >= eps/2,
while sum_{k_B > 2R} k_B nu_p <= 2 W_R(B) <= 2 eps'. Dividing the
contribution of 2 <= k_B <= 2R by 2R,
sum_{2 <= k_B <= 2R} nu_p >= (eps/2 - 2 eps')/(2R) >= eps/(10R). (11.15)
If in addition Psi(B) > 1 - 1/R, then the height-two layers contribute at
most beta/4 = 7/20 to Psi (because 2 sum_{k_B=2} nu_p <= 1/2 by the order
bound), so
2 sum_{k_B >= 3} k_B nu_p = Psi(B) - beta sum_{k_B = 2} nu_p
> 1 - 1/R - 7/20.
The height-times-weight on the left, after division by two, is at least
1/4 for large N; deleting layers above 2R and dividing by 2R gives
sum_{k_B >= 3} nu_p >= (1/4 - 2 eps')/(2R) >= 1/(20R). (11.16)
Force many costly steps. Let n_cost be the number of costly steps in the
window. A costly step increases Z by at most one; at a noncostly step Z
drops by at least delta = eps/(20R^3) (11.14), and (11.15)-(11.16) supply
the required bounds on H_pi. Telescoping the L_* changes and using
0 <= Z <= 1,
-1 <= Z(B_{J_*}) - Z(B_{J_*-L_*})
<= n_cost - (L_* - n_cost) delta,
n_cost >= (L_* delta - 1)/(1+delta).
Now delta -> 0 and L_* delta asymptotic to R^9 -> infinity, so for large N
n_cost >= L_* eps/(100 R^3). Set t_* = ceil(L_* eps/(100 R^3)).
The event H_pi therefore forces D_t at at least t_* window positions.
With (11.10),
Pr(H_pi) <= C(L_*, t_*) p_N^{t_*},
and the entropy of choosing the positions satisfies
log_2 C(L_*, t_*) <= t_* log_2(e L_*/t_*) = O_eps(t_* log R).
Together with the factor 3^{t_*} (from p_N = 3*2^{-N sigma/2}), this is
o(N sigma t_*), because N sigma/log R -> infinity. Hence, for large N,
Pr(H_pi) <= 2^{-N sigma t_*/3}
<= 2^{-eps N L_* sigma/(300 R^3)}
= 2^{-Omega_eps(NR^3)} = 2^{-omega(N)}, (11.17)
and its weighted contribution is at most 2^{N - Omega_eps(NR^3)} =
2^{-omega(N)}.
--------------------------------------------------------------------------
11.6 Assembly and the moment bound
--------------------------------------------------------------------------
Fix pi and split E[1_{A_pi} 2^{N Psi(B_{J_*})}] into the part on H_pi and
the part on A_pi \ H_pi.
On H_pi, (11.17) gives contribution <= 2^N Pr(H_pi) = 2^{-omega(N)}.
On A_pi \ H_pi one of two things happens.
(a) max_{window} W_R > eps'. By (11.13) this has weighted contribution at
most 2^N * 2^{-Omega_eps(NR)} = 2^{-omega(N)}.
(b) max_{window} W_R <= eps' and min_{window} Psi <= eps. Choose the last
window position t0 with Psi(B_{t0}) <= eps; then J_* - t0 <= L_*. On
A_pi all nodes B_t (t >= t0) lie in their typical sets and all gates
hold, so the potential-step (Proposition 7.2) is available step by
step. The tower property, applied L_* times, gives
E[ 1_{A_pi, future} 2^{N Psi(B_{J_*})} | B_{t0} ]
<= 2^{N Psi(B_{t0}) + L_* N l^{-60}}
<= 2^{N eps + N l^{-36}} = 2^{N eps + o(N)}.
There are at most L_* = l^{24} choices of t0, and |Pi_N| = 2^{o(N)} paths,
so branch (b) contributes at most
2^{o(N)} * 2^{N eps + o(N)} = 2^{N eps + o(N)}.
The only place eps enters the final estimate is this factor 2^{N eps}.
Take eps = eps_N = l^{-5} (a slowly vanishing constant, admissible because
the descent needs 2 sigma <= eps/(20R^3), i.e. eps >= 40 R^3 sigma =
40 l^{-6}, which l^{-5} satisfies, while the rare-event bounds of (11.13)
and (11.17) and n_cost >= t_* need only eps N L_* sigma/R^3 -> infinity).
Then 2^{N eps} = 2^{N l^{-5}} = 2^{o(N)}, so branch (b) is 2^{o(N)}.
Summing (11.7) over the 2^{o(N)} paths, the three contributions
2^{-omega(N)} (H_pi and (a)) and 2^{o(N)} (branch (b)) give
E[ 1_{det B_{m_*} != 0} 2^{N Psi(B_{m_*})} ] <= 2^{o(N)}.
This is Proposition B with m_* = N-1. QED
==========================================================================
12. CONCLUSION: THE THEOREM
==========================================================================
We now assemble the pieces. Everything proven so far is deterministic or a
typical-probability statement; here we put them together.
First, Lemma 1.6. Split the expectation at the typical event of
Proposition A (for precision A):
E|S(B_{N-1})| = E[ 1_{typical} |S(B_{N-1})| ]
+ E[ 1_{atypical} |S(B_{N-1})| ].
On the typical event, Proposition A gives |S(B_{N-1})|
<= 2^{N(Psi(B_{N-1}) + l^{-A})}; and S(B) = empty when B is singular, so
the nonsingularity indicator may be inserted. Hence
E[ 1_{typical} |S(B_{N-1})| ]
<= 2^{N l^{-A}} E[ 1_{det != 0} 2^{N Psi(B_{N-1})} ]
<= 2^{N l^{-A}} * 2^{o(N)} = 2^{o(N)},
using Proposition B. On the atypical event, |S(B)| <= 2^{N-1} always, and
the atypical event (nonsingular but failing Proposition A) has probability
at most 2^{-N f(N)} for some f(N) -> infinity, so this term is at most
2^{N-1} * 2^{-N f(N)} = 2^{-omega(N)}.
Therefore
E |S(B_{N-1})| <= 2^{o(N)}. (12.1)
This is Lemma 1.6.
Now the corank-one probability. Lemma 1.5 gives
Pr(corank B_N = 1) <= N 2^{-N} E|S(B_{N-1})|
<= N 2^{-N} 2^{o(N)} = 2^{-N + o(N)}. (12.2)
Now the singularity probability of the binary model. Lemma 1.4 gives
Pr(det B_N = 0) <= 2^{o(N)} Pr(corank B_N = 1) + 2^{-Omega(N^{6/5})}
<= 2^{o(N)} 2^{-N+o(N)} + 2^{-Omega(N^{6/5})}
= 2^{-N + o(N)}. (12.3)
Conversely, a specified row of B_N is identically zero with probability
2^{-N}, so Pr(det B_N = 0) >= 2^{-N}. Hence
Pr(det B_N = 0) = 2^{-N + o(N)}. (12.4)
Finally the original model. Lemma 1.1 gives Pr(det A_n = 0) =
Pr(det B_{n-1} = 0). Applying (12.4) with N = n - 1,
Pr(det A_n = 0) = 2^{-(n-1) + o(n)} = 2^{-n + o(n)}
= (1/2)^{n} (1 + o(1))^n = (1/2 + o(1))^n.
That is,
Pr(det A_n = 0) = (1/2 + o(1))^n,
which is the theorem. QED