THE SHARP SINGULARITY RATE FOR BIASED SYMMETRIC SIGN MATRICES
A complete proof, written plainly.
ABSTRACT
Fix a real number p with 0 < p < 1 and p != 1/2. Flip a biased coin for
each entry on and above the diagonal of an n x n matrix A. Put +1 for
heads (probability p) and -1 for tails (probability 1-p). Fill below the
diagonal by symmetry so A is symmetric. The theorem below computes,
to exponential precision, how often this random matrix is singular.
THEOREM 1.1 (main result). As n -> infinity,
P(det A_n^(p) = 0) = (p^2 + (1-p)^2 + o(1))^n.
The number p^2 + (1-p)^2 is exactly the probability that two independent
biased coins with the same bias agree. That is no accident: the most
likely way for A to be singular is for two rows to become identical.
The proof has two halves.
LOWER BOUND: force rows 1 and 2 to be equal. Cheap; Section 2.
UPPER BOUND: show every singular A forces a rare column condition, and
that this condition is itself exponentially rare. The bulk of the proof.
We first reduce to the case where A has a one-dimensional kernel (Section
4), then replace the kernel vector by a bit matrix (Section 5), exclude
kernel vectors whose tail is nearly sparse (Section 6), and pick a
deletion coordinate with a typical row (Sections 7-8). All of this
reduces the theorem to a single column estimate (Proposition 8.1).
Sections 9-26 prove the column estimate. Section 27 restates the whole
argument as a one-page story.
References to [C] point to the companion manuscript on the unbiased
case (October 3, 2026). Every fact we use from [C] is quoted explicitly,
so the present document is self-contained for a careful reader.
Symbols used throughout: b = 1-p (assumed > p from Section 3 on),
Q = p^2 + b^2, a = -log_2 b, d_* = -log_2 Q, h_* = -p log_2 p - b log_2 b,
log without subscript is natural, log_2 is base two. "[m]" means {1,...,m}.
SECTION 0. THE QUESTION
Fix p in (0,1) with p != 1/2. Let A = A_n^(p) be the symmetric n x n
matrix whose entries on and above the diagonal are independent with
P(A_{ij} = +1) = p, P(A_{ij} = -1) = 1 - p (i <= j),
and whose entries below the diagonal are forced by A_{ji} = A_{ij}.
We want to understand the event det A = 0. Equivalently A has a
nonzero vector v with A v = 0. Equivalently rank A < n.
This problem has a long history. Komlos proved asymptotic
nonsingularity for independent 0/1 matrices in 1967. Kahn, Komlos and
Szemeredi got exponential decay for independent ±1 entries in 1995.
Tikhomirov (2020) identified the exact exponential rate (1/2 + o(1))^n
for the unbiased independent-entry model. Jain, Sah and Sawhney (2021)
did the same for every fixed nonuniform distribution of independent
entries. All of those models have independent rows.
Symmetry is what makes the present problem hard: the rows of A are not
independent. Costello, Tao and Vu (2006) proved asymptotic
nonsingularity for the symmetric Bernoulli case. Nguyen, Vershynin,
Ferber-Jain, and finally Campos-Jenssen-Michelen-Sahasrabudhe (2025)
all improved the exponential bound. The unbiased sharp rate
(1/2 + o(1))^n is the main theorem of [C]. The present paper proves
the analogous sharp rate for every fixed bias p != 1/2.
Throughout, we may multiply A by -1 without changing singularity;
this exchanges p and b = 1-p. From Section 3 on we assume 0 < p < 1/2,
so b > 1/2 is the largest atom.
SECTION 1. THE MAIN THEOREM
Theorem 1.1. Fix 0 < p < 1 with p != 1/2. Then
lim_{n -> inf} P(det A_n^(p) = 0)^{1/n} = p^2 + (1-p)^2.
Equivalently, writing Q = p^2 + b^2 = p^2 + (1-p)^2, we have
P(det A_n^(p) = 0) = (Q + o(1))^n.
We prove a limsup bound <= Q using the column estimate, and a matching
liminf bound >= Q by forcing rows 1 and 2 to be equal.
SECTION 2. LOWER BOUND: FORCE TWO ROWS TO MATCH
Lemma 2.1. P(det A_n^(p) = 0) >= (p^3 + b^3) Q^{n-2}.
Proof. Consider the event E that rows 1 and 2 of A are identical:
A_{1k} = A_{2k} for every k = 1, ..., n.
If E holds, the two rows are equal, hence A is singular, det A = 0.
Break E down by column index k.
k = 1: requirement is A_{11} = A_{21} = A_{12}.
By symmetry A_{21} = A_{12}; so the requirement is
A_{11} = A_{12}.
k = 2: requirement is A_{12} = A_{22}.
Together: A_{11} = A_{12} = A_{22}. All three are independent biased
signs with P(+1) = p. Probability of three +1's is p^3; probability of
three -1's is b^3. Total p^3 + b^3.
k = 3, ..., n: requirement A_{1k} = A_{2k}, with A_{1k} and A_{2k}
independent biased signs. Probability of agreement is
p*p + b*b = p^2 + b^2 = Q.
All of these concern disjoint entries on and above the diagonal, so
the events are independent. Multiplying:
P(E) = (p^3 + b^3) * Q^{n-2}. QED.
Since (p^3 + b^3)^{1/n} -> 1 as n -> infinity, Lemma 2.1 gives
liminf P(singular)^{1/n} >= liminf Q^{(n-2)/n} = Q.
The delicate part is the reverse inequality.
SECTION 3. NOTATION AND CONSTANTS
From now on, p in (0, 1/2) is fixed (Sections 0-1 discussion), b = 1-p.
Put
Q = p^2 + b^2 (agreement/collision probability)
a = -log_2 b (cost of one b-likely bit)
d_* = -log_2 Q (target decay exponent)
h_* = -p log_2 p - b log_2 b (Shannon entropy of one biased sign)
The quantity h_* is the entropy of the biased distribution: for a
random ±1 column with bias p, the number r of +1 entries is typically
~ p n, and the point-probability of any particular such column is
p^r b^{n-r} which is 2^{-n (h_* + o(1))}.
Strict inequalities we will need:
(I1) 2a > d_* <-- because b^2 < Q = p^2 + b^2.
(I2) h_* > d_* <-- strict concavity of log; see below.
Proof of (I1): b^2 < Q implies -log_2(b^2) > -log_2 Q, i.e., 2a > d_*.
Proof of (I2): the function x -> -log_2 x is strictly convex, and p,
b are unequal. Therefore
p * (-log_2 p) + b * (-log_2 b) > -log_2 (p * p + b * b) = d_*.
The left side is h_*. QED.
Notation. "log" is natural, "log_2" is base 2. [m] = {1, ..., m}. For
a sequence of events depending on n we say a property "holds typically"
if it fails with probability 2^{-omega(N)} where N is a reference
dimension; in practice our exceptional probabilities are at most
2^{-c N^{6/5}} or 2^{-c N^2}, far stronger than 2^{-omega(N)}.
Reference dimensions and layer window. We will sometimes want a
"reference dimension" N and study bit matrices B of size m close to N.
Set
ell = log log N
I_N = { m in Z : N - N^{7/10} <= m <= N }.
All estimates are uniform for m in I_N, over all admissible arrays of
probabilities, and over N -> infinity. Any "holds typically" statement
means: fails with probability 2^{-omega(N)}, uniformly in m and in the
probability array.
SECTION 4. REDUCTION TO CORANK ONE
Lemma 4.1. For A = A_n^(p),
P(det A = 0) <= 2^{o(n)} P(rank A = n - 1) + 2^{-Omega_p(n^{6/5})}.
So up to a subexponential factor we may assume A has rank exactly n-1.
Proof. Two independent pieces.
(4.1a) HIGH CODENsION IS RARE. A symmetric matrix of rank r has a
nonsingular r x r principal submatrix. Indeed write A = X S X^T with
X of size n x r, rank r, and S invertible r x r (S = principal block of
A on a "basis" of R^r). Choose r independent rows of X; the r x r
principal block of A on those indices is Y S Y^T with Y invertible, so
nonsingular.
Fix such a set of r indices. Reveal the r x r block M and the cross
block M -> complement. If A has the same rank r, the Schur complement
forces every entry of the (n-r) x (n-r) principal submatrix below the
top-right entry, above the diagonal. There are exactly
(n - r)(n - r + 1) / 2
such forced entries, each a ±1 sign with a specified value; the
conditional probability of matching is at most b (since b > p is the
maximum atom). Sum over all possible r-blocks and all ranks r:
P(n - rank A >= t) <= sum_{k = t}^{n} C(n, k) b^{k(k+1)/2}.
With t = ceil(n^{3/5}), the dominant term is C(n, t) b^{t(t+1)/2} <=
2^n 2^{-c t^2} = 2^{-Omega_p(n^{6/5})}, because b < 1 gives
b^{k(k+1)/2} = 2^{-Omega(k^2)} for k >= t.
(4.1b) PUSH TO CORANK EXACTLY ONE BY DIAGONAL FLIPS. Suppose corank A
is k with 1 <= k < t. Choose k-1 coordinate indices I such that the
restrictions x -> x_I, x in K = ker A, are independent linear
functionals (span R^{k-1}; possible since dim K = k). Let D be the
diagonal ±1 matrix that multiplies coordinate i of D by -1 for i in I
and leaves other diagonals alone.
Claim: if (A + D') y = 0 for D' = D applied as a diagonal flip of A's
diagonal (formally (A + D) as a matrix whose diagonal has been
multiplied), then Ay = 0 and y_I = 0.
Indeed, for any x in K, 0 = y^T (A + D) x = y^T A x + y^T D x = y^T D x
because Ax = 0. Rewrite y^T D x = (D y)^T x; D y is supported on I.
As x ranges over K, x_I ranges over all of R^I, so y_I = 0.
Therefore (A + D) y = 0 plus y_I = 0 implies Ay = 0 (since D only
touches coordinates in I).
Conversely, every vector in K vanishing on I satisfies (A + D) y = 0
because Dy = 0 when y_I = 0. So ker(A + D) = K ∩ {v : v_I = 0},
dimension 1.
Overhead. Fix one good choice of I for each corank-k matrix. The map
"flip the diagonal signs at I" has at most (b/p)^{|I|} preimages, since
|I| = k - 1 <= t and all flips are to the tiny-probability atom.
Also we need to count how many I to consider: at most
sum_{j <= t} C(n, j) = 2^{O(t log n)} = 2^{o(n)} choices. Both factors
are 2^{o(n)}. QED.
From now on, P(singular) reduces to P(rank A = n - 1) up to 2^{o(n)}.
SECTION 5. FROM ONE KERNEL VECTOR TO ONE DELETED BIT COLUMN
Now suppose rank A = n - 1. Let v be a nonzero kernel vector.
Anchor. Pick a_0 with |v_{a_0}| = max_i |v_i|. Multiply v by a scalar
so that
|| v_{[n] \ {a_0}} ||_2 = 1.
Call the off-anchor part the tail. Since rows of A are all-zero on no
coordinate (they are ±1 patterns), no component of v is zero. And by
considering the a_0-th row of A v = 0:
|v_{a_0}| <= sum_{j != a_0} |v_j| <= sqrt(n - 1). (5.0)
The last inequality is Cauchy-Schwarz on the unit-norm tail of length
n-1.
Lemma 5.1 (anchor congruence, adapted from [C] Lemma 2.1). Fix an
index a_0. Condition on the entire row of a_0 in A_n^(p). There is a
symmetric (n-1) x (n-1) bit matrix M with:
(i) entries of M on/above diagonal are independent; each has
success probability p or b, independently of everything
else not already conditioned upon in the anchor row;
(ii) rank(E M) <= 2, and the same is true of every principal
submatrix of M;
(iii) dim ker M = dim ker A. Whenever a_0 is an anchor of a kernel
vector v of A, changing some signs of tail(v) produces a
unit vector in ker M.
Proof. Relabel so a_0 = 1. Write t = A_{11} in {±1}, and u_i = A_{1i}
for i > 1. Set D = diag(1, t u_2, ..., t u_n). The matrix t D A D has
top row and left column equal to one (all entries +1). Its lower
principal (n-1) x (n-1) block is the sign matrix
C_{ij} = t u_i u_j A_{ij} (2 <= i, j <= n).
Its Schur complement at the top entry (which is 1) is
C - 1 1^T = -2 M, where M_{ij} = (1 - t u_i u_j A_{ij}) / 2.
What is M_{ij}? The product t u_i u_j is a fixed ±1 given the anchor
row. So M_{ij} = 0 when t u_i u_j A_{ij} = +1, and M_{ij} = 1 when
t u_i u_j A_{ij} = -1. If t u_i u_j = +1: A_{ij} = +1 means M_{ij} = 0
success probability p. If t u_i u_j = -1: A_{ij} = +1 means M_{ij} = 1,
success probability p. So M has independent entries on/above diagonal,
each with success probability p or b, always the same values
{p, b}. This proves (i).
For (ii): E M = (1/2) 1 1^T - (mu t / 2) u u^T where mu = 2p - 1.
Rank <= 2. A principal submatrix inherits the same form with u
restricted; rank <= 2 as well.
For (iii): the matrix map A -> t D A D is a sign change of certain
diagonal entries followed by a global scalar t. Both preserve nullity.
Schur complement at a nonzero top-left entry preserves nullity. So
dim ker M = dim ker A. A kernel vector v of A gives a kernel vector of
t D A D by applying D^{-1} = D (since D^2 = I). Project to the lower
coordinates; that projection lies in ker M. Multiplying by the top
coordinate of v scales it to a unit vector. Coordinate signs multiply
by the (fixed) signs in D. QED.
Now the key reduction. Suppose A has corank 1 with anchor a_0.
Apply the anchor congruence. We get a bit matrix M of size N = n - 1
with corank 1. Choose a coordinate i with |v_i| >= c / sqrt(n) for a
fixed c > 0 (Section 8 guarantees many such coordinates when the tail
is non-compressible). Delete coordinate i and obtain a nonsingular
principal minor B of size m = N - 1 = n - 2.
Why B is nonsingular. The adjugate of a symmetric corank-1 matrix is a
nonzero scalar multiple of v v^T. Every diagonal entry of the adjugate
on a coordinate where v_i != 0 is nonzero. The i-th diagonal entry of
adj(M) is det(B) (up to a sign), so B is nonsingular.
The omitted column. Write M in block form
M = [ B z ]
[ z^T d ], d in {0, 1}.
The kernel equation M v = 0 and the Schur complement give
B^{-1} z = - v_{[N] \ {i}} / v_i, z^T B^{-1} z = d in {0, 1}.
So z satisfies the admissibility condition
z in S_{L_0}(B) := { z in {0,1}^m :
z^T B^{-1} z in {0,1},
||B^{-1} z||_2 <= L_0 sqrt(N) },
with L_0 = max(1, 2/c). Indeed ||B^{-1} z|| = ||v_{[N]\{i}}|| / |v_i|
<= 1 / (c / sqrt(n)) = sqrt(n)/c <= sqrt(N) * (2/c) for large n.
So every non-compressible corank-1 kernel produces one (anchor,
deletion-coordinate) pair and one z in S_{L_0}(B).
SECTION 6. COMPRESSIBLE TAILS ARE RARE
We need to exclude the kernel vectors whose tail is close to a sparse
vector. This is Lemma 6.1.
Lemma 6.1. For every epsilon > 0, there exist fixed
lambda, delta in (0, 1/4) such that, for all sufficiently large n, the
following event has probability at most 2^{(-d_* + epsilon) n}:
A_n^(p) has a nonzero kernel vector v for which the normalized tail
(with respect to some anchor) lies within Euclidean distance delta of
a vector supported on at most lambda n coordinates.
Proof sketch. Write W = A - mu 1 1^T with mu = 2p - 1. A standard net
argument on the unit sphere gives a spectral bound:
P( ||W||_op > L sqrt(n) ) <= 2 * 9^n * exp(-c(L) n) <= 2^{-4n},
(6.0)
for L large enough. (For each fixed unit vector x, x^T W x is a sum
of independent centered bounded random variables; Hoeffding, then
2^{-4n} beat down a 9^n net.)
Fix a support T of size j <= lambda n and a "shape" x supported on
S = T ∪ {a_0} approximating a kernel vector with anchor a_0. Cover
the unit ball of R^T by a delta-net of size at most (C/delta)^j, and
cover the scalar sum sum_{i != a_0} v_i by a mesh of step <= delta on
a range of size <= 2 sqrt(n).
If ||W||_op <= L sqrt(n), then for some pair (x, u) from these nets:
|| W x + mu u 1 ||_2 <= C_1 L delta sqrt(n). (6.1)
The new (u) is a scalar approximation of sum_i v_i. Separating u from
x prevents the (possibly rank-2) mean matrix mu 1 1^T from amplifying
error.
We now show that each fixed pair (x, u) has small probability of
satisfying (6.1). Key claim: there exist fixed w > 0 and delta_0 > 0
(depending on p) such that, whenever delta < delta_0, every row
i outside S satisfies
P( |(W x)_i + mu u| <= w ) <= Q. (6.2)
All row shifts here may be arbitrary constants.
Case A: some |x_j| >= u_0 > 0 for j in T. Then |x_{a_0}| >= u_0/2 once
delta is small. Condition on all signs in row i except those at j and
a_0. For w < u_0/4, the interval of length 2w cannot contain two
outcomes that differ in only one of these two bits. So the allowed
"vertices of the two-bit square" form either one vertex or two
opposite vertices. Their total probability is at most
max{ b^2, p^2, 2 p b, p^2 + b^2 } = Q.
Case B: every tail coefficient is < u_0. Condition on the anchor sign
and use only the tail. The centered sum has variance
sigma_T^2 = 4 p b sum_{j in T} x_j^2 >= c_p > 0 and third absolute
moments bounded by C_p u_0 sum_{j in T} x_j^2. Berry-Esseen (unequal
summands, [Tyurin]) bounds the uniform distribution-function error by
C_p u_0. So the probability of any interval of length 2w is at most
C_p (w + u_0). Choose u_0, then w, small enough that this is < Q, then
shrink delta_0.
Now (6.2) is established. For fixed (x, u), the rows i outside S are
disjoint, so the tests in (6.2) are independent. Choose a fixed
gamma > 0 with C_1^2 L^2 delta^2 / w^2 < gamma; inequality (6.1)
allows at most gamma n of the n - j - 1 tests outside S to fail.
P( (6.1) for fixed pair ) <=
( sum_{i <= gamma n} C(n, i) ) Q^{n - j - 1 - gamma n}.
Union bound over anchors (n = 2^{o(n)} choices), supports T
(C(n, lambda n) = 2^{H_2(lambda) n} choices), and net points
((C/delta)^j * poly(n) = 2^{lambda log_2(C/delta) n + o(n)} choices)
gives base-2 logarithm of probability at most
-d_* n + [ d_*(lambda + gamma) + H_2(gamma) + H_2(lambda)
+ lambda log_2(C/delta) ] n + o(n). (6.3)
Choose gamma, then delta, then lambda all small enough that the
bracket in (6.3) is below epsilon/2; combine with the 2^{-4n} spectral
error from (6.0). This gives the asserted 2^{(-d_* + epsilon) n}
bound. QED.
SECTION 7. ROW COUNTS
Lemma 7.1. For every fixed rho, w > 0, with probability
1 - exp(-Omega_{rho, w}(n^2)), fewer than rho n rows of A_n^(p) have a
number of positive entries outside [pn - wn, pn + wn].
Proof. If at least rho n rows fail, at least half fail in the same
direction (all too many +1 or all too few). Fix a set I of
k = ceil(rho n / 3) such rows. The sum of their "+1 counts" is a sum
of independent upper-triangular Bernoulli variables, each contributing
one or two to the sum, mean p k n, coefficient-squared sum at most
2 k n. Deviation from the mean at least k w n. Hoeffding's inequality
bounds this probability by 2 exp(-k w^2 n) = 2 exp(-Omega_{rho, w}(n^2)).
There are at most 2^n choices of I and two directions, so a union
bound still gives exp(-Omega_{rho, w}(n^2)). QED.
SECTION 8. FINISHING THE MAIN THEOREM, ASSUMING THE COLUMN ESTIMATE
Here we state the one deferred estimate, and show it implies the
theorem. Everything else (Sections 9-30) is a proof of that estimate.
Proposition 8.1 (column estimate). For every fixed L_0 >= 1 and every
sufficiently small fixed e_0 > 0, a matrix B in the bit model of size
m = N - 1 satisfies:
P( B nonsingular AND |S_{L_0}(B)| > 2^{e_0 N} )
<= 2^{-N(2a - 10 e_0)}. (8.1)
Proof of Theorem 1.1 (upper bound), assuming Proposition 8.1.
Fix epsilon > 0. Let lambda, delta be the constants of Lemma 6.1 for
this epsilon.
Step 1 (Section 4): P(det A = 0) <= 2^{o(n)} P(rank A = n-1) +
2^{-Omega(n^{6/5})}. The second term is tiny compared with Q^n.
Step 2 (Section 6): discard the bad event of Lemma 6.1
(near-sparse tails). Its probability is at most 2^{(-d_* + epsilon) n}.
This is already of the target order (Q + o(1))^n, so it slips inside
the epsilon slack.
Step 3 (choose deletion coordinate). Take any remaining kernel vector
v with corank-1 A and non-compressible tail. Choose a fixed c with
0 < c < delta. At least lambda n / 2 off-anchor coordinates of v have
|v_i| >= c / sqrt(n). (If fewer, truncation to them has support
<= lambda n and residual norm <= c < delta, contradicting
non-compressibility.)
Apply Lemma 7.1 with rho = lambda / 4. Apart from probability
exp(-Omega_{lambda, w_1}(n^2)), some one of those lambda n / 2
coordinates has a "+1 count" in its original sign column lying in
[pn - w_1 n, pn + w_1 n]. Choose it as the deletion coordinate i.
Step 4 (reduce to bit model). Fix the anchor index a_0 and the
deletion index i. Condition on the anchor row. Apply Lemma 5.1: M is
an N x N bit matrix (N = n-1), corank 1, with 1-dim kernel, and
deleting the i-th coordinate leaves a nonsingular principal B of size
m = N - 1. The omitted column z lies in S_{L_0}(B) with
L_0 = max(1, 2/c). All this is deterministic given A.
Note: we do not condition on "i was selected by the kernel vector".
We take a union bound over (a_0, i) later. So B and z are distributed
as in the bit model conditional on the anchor row.
Step 5 (probability of a specified z). Conditional on the anchor row,
B and the entries of z in the original (biased sign) matrix are
independent. If z corresponds to a column of A with N - 1 = n - 2
original off-diagonal signs, of which r are +1, its point probability
is exactly
p^r b^{N - 1 - r}.
The row-count condition (Step 3) forces |r - pn| <= w_1 n + 2 (the
extra 2 accounts for the deleted diagonal and anchor entries). In this
range:
-log_2 ( p^r b^{N - 1 - r} ) = (N - 1) h_* + (r - p(N - 1))
log_2(b / p),
so p^r b^{N - 1 - r} <= 2^{-N(h_* - C_p w_1 - o(1))}. (8.2)
Step 6 (assemble). Conditional on the anchor row and B, the probability
that a specified row count is compatible with "some z in S_{L_0}(B)"
is at most:
- On the typical event (Prop 8.1, |S_{L_0}(B)| <= 2^{e_0 N}):
2^{e_0 N} * 2^{-N(h_* - C_p w_1 - o(1))} = 2^{-N(h_* - e_0 - C_p w_1 - o(1))}.
- On the exceptional event (prob <= 2^{-N(2a - 10 e_0)}):
contribute the whole event probability 2^{-N(2a - 10 e_0)}.
Both bounds are uniform in the anchor row and the choice of deletion
index. So no additional factor from those sources.
Step 7 (assemble over choices). Choices of (anchor, deletion) cost at
most n^2 = 2^{o(N)}. Therefore
P(det A = 0, rank A = n-1) <=
2^{o(N)} * ( 2^{-N(h_* - e_0 - C_p w_1 - o(1))}
+ 2^{-N(2a - 10 e_0)} )
+ 2^{-Omega(n^{6/5})}.
Step 8 (choose constants). After L_0 (equivalently c, delta) is fixed,
choose e_0 and w_1 > 0 small enough that
2a - 10 e_0 > d_* and h_* - e_0 - C_p w_1 > d_*.
Both hold by continuity from Section 3's (I1) and (I2). Then
limsup (1/n) log_2 P(det A = 0) <= -d_* + epsilon
= -log_2 Q + epsilon.
Step 9 (epsilon -> 0). Combined with the lower bound of Section 2,
Theorem 1.1 follows. QED.
So the entire remaining work is to prove Proposition 8.1.
END OF PART I (setup of the main theorem and its reduction).
SECTION 9. PRIME CORANK
We will use "corank modulo a prime" as a tool. This lets us bound the size
of the finite group G_B = Z^m / B Z^m by reducing B modulo primes and taking
advantage of a generic rank bound.
First, a general fact over any field F in which the two bit values (0 and 1)
remain distinct. (They do: in F_q for any prime q, 0 != 1.)
Fact 9.0. Let A be a symmetric d x d matrix over such an F whose entries on
and above the diagonal are independent and have largest atom at most beta
(i.e., every value is attained with probability at most beta). Let H be a
fixed symmetric matrix over F. Then for every integer 1 <= k <= d,
P( corank_F(A + H) >= k ) <= 2^d beta^{k(k+1)/2}.
Proof. A symmetric matrix of rank r has a nonsingular r x r principal
submatrix over any field (characteristic 2 included). To see this, write it
as Y C Y^T with Y of size d x r, full column rank r, and C symmetric
invertible r x r; choose r independent rows of Y; the principal r x r block
on those indices is Y_J C Y_J^T with Y_J invertible. So if corank_F(A+H) = c
>= k, then A+H has rank r = d - c <= d - k, hence has an r x r nonsingular
principal block.
Fix a set I of size r. Reveal the r x r principal block and the cross block
from I to I^c. If A+H has rank exactly r, the Schur complement forces every
entry of the remaining (d-r) x (d-r) principal block. There are exactly
(d - r)(d - r + 1) / 2
such entries (upper triangular of a (d-r)-square); each is a value with
probability at most beta. Sum over I of size at most d - k. QED.
Now the biased prime-corank lemma.
Lemma 9.1 (uniform prime corank, adapted from [C] Prop. 5.3). Typically a
nonsingular bit matrix B of size m in I_N satisfies
corank_{F_q}( B mod q ) <= N^{3/5} for every prime q. (9.1)
Consequently the finite abelian group G_B = Z^m / B Z^m can be generated by
at most ceil(N^{3/5}) elements. Exceptional probability at most
2^{-Omega_p(N^{6/5})}.
Proof. Fix a prime q. Bits in B have largest atom b (over R and over F_q;
0 and 1 both survive mod q). Fact 9.0 gives with k = floor(N^{3/5}) + 1:
P( corank_{F_q}(B mod q) >= k )
<= 2^{N} b^{k(k+1)/2} = 2^{-Omega_p(N^{6/5})}.
Because b < 1, b^{k(k+1)/2} = 2^{-Omega_p(k^2)}; with k ~ N^{3/5}, this is
2^{-Omega_p(N^{6/5})}, larger than 2^N.
Union over primes. If B is nonsingular over R, any prime q with
corank_{F_q}(B mod q) > 0 divides det B (a nonzero integer). Hadamard's
inequality:
1 <= |det B| <= m^{m/2} <= N^{N/2}.
So the set of relevant primes q is contained in { q prime : q <= N^{N/2} },
of size at most N^{N/2} = 2^{(N/2) log_2 N} = 2^{O(N log N)}. Union bound
over such q costs 2^{O(N log N)}, which is negligible compared with
2^{-Omega_p(N^{6/5})} (since N^{6/5} >> N log N). This gives (9.1).
Generator count. dim_{F_q}( G_B / q G_B ) = corank_{F_q}( B mod q ) (as
abelian groups: reducing B mod q has the same as kernel modulo q). The
structure theorem for finite abelian groups says the minimum number of
generators of G_B equals max_q dim_{F_q}(G_B / q G_B), which (9.1) bounds by
N^{3/5}. QED.
SECTION 10. LATTICE HEIGHT AND THE LOW-HEIGHT COVER
A lattice L in R^d is a discrete subgroup of a real vector space,
considered inside its real span. Its rank is dim(span L); its determinant is
its Euclidean covolume in the span. For a basis v_1, ..., v_r,
det L = det( <v_i, v_j>_{i, j = 1..r} )^{1/2}.
The rank-zero lattice has det 1 by convention.
A subspace F subset R^m is rational if it is spanned by integer vectors. Its
height is
H(F) = det( F ∩ Z^m ).
In particular H(0) = H(R^m) = 1. Every such height is at least one: the
wedge of an integer lattice basis is a nonzero integer vector whose norm is
exactly the determinant.
We measure closeness of subspaces by rank distance:
d(U, V) = dim U + dim V - 2 dim(U ∩ V).
This counts dimensions lost on intersection, not angles. Orthocomplements
preserve rank distance: d(U^⊥, V^⊥) = d(U, V).
The next theorem gives a fixed, finite list of rational subspaces that
approximates every rational subspace of bounded height, in rank distance.
Theorem 10.1 (low-height cover, [C] Theorem 4.1). Fix D, P > 0. For all
large enough N and every integer 0 <= m <= N there is a list C_{m,N} of
rational subspaces of R^m, depending only on m, N, D, P, such that
|C_{m,N}| <= 2^{N^2 ell^{-P}},
and every rational F subset R^m with H(F) <= exp(N ell^D) satisfies
min_{U in C_{m,N}} d(F, U) <= N ell^{-P}.
We cite Theorem 10.1 from [C]; it is a deterministic counting-of-rational-
subspaces argument, does not depend on the entry distribution, and applies
verbatim here.
SECTION 11. DETERMINANT MINIMIZER AND PROJECTED POINT COUNT
A sublattice L_0 subset L is saturated (or primitive) if L_0 = L ∩ span(L_0).
A basis of a saturated sublattice extends to a basis of L. If F = span L_0,
orthogonal projection onto F^⊥ realizes the quotient L / L_0 as a lattice
L / L_0 = pi_{F^⊥}(L),
and volume factorizes:
det L = det L_0 * det(pi_{F^⊥} L). (11.0)
The same factorization holds for the full preimage in L of any sublattice of
the quotient. Both facts hold in every rank, with the rank-zero
conventions det(0) = 1, L/0 = L. Reference: [C] Lemma 3.1.
Lemma 11.1 (determinant minimizer, [C] Lemma 3.6). For every lattice L and
T > 0 the quantity
det M / T^{rank M} (M <= L a sublattice, 0-lattice allowed)
attains its minimum at a saturated sublattice L_min. It satisfies
det L_min <= T^{rank L_min},
det M >= T^{rank M} for every sublattice M <= L / L_min.
Proof. The zero sublattice has normalized determinant 1; so the minimum is
at most 1. Fix a positive rank r <= rank L. The wedge of a lattice basis is
a nonzero element of the discrete lattice wedge^r L. Only finitely many such
wedge vectors have norm <= T^r (a discrete set inside a ball). So for each r
there are only finitely many possible values of det M (with rank M = r) that
are <= T^r. Hence the minimum is attained.
Saturation: replace any M by M_sat = L ∩ span M; this preserves rank and can
only lower det. So the minimizer L_min is saturated. Comparing to the zero
sublattice gives the first displayed bound.
For the second bound, take any sublattice M <= L / L_min; let M~ be the full
preimage in L. Volume factorization (11.0), applied at the level of the
quotient and to the full preimage, gives det M~ = det L_min * det M and
rank M~ = rank L_min + rank M. Minimality applied to M~ yields the stated
inequality. QED.
The point of removing L_min is that lower bounds on all sublattice
determinants give an upper bound on the number of short vectors in the
remaining quotient.
Lemma 11.2 (projected point count, [C] Lemma 3.5). Let T > 0. Suppose a
lattice Lambda of rank j >= 1 satisfies det M >= T^{rank M} for every
sublattice M <= Lambda. Then, with s_0 = T / (10 (log j + 2)),
#{ x in Lambda : ||x||_2 <= R } <= (3/2) * exp(pi R^2 / s_0^2).
In particular, with T = (log N)^4, j <= N, R = sqrt(N):
#{ x in Lambda : ||x||_2 <= R } <= 2^{O(N / (log N)^6)} = 2^{o(N)}.
The latter bound also holds in rank zero, where the count is exactly one.
Proof. For s > 0, write
rho_s(Lambda) = sum_{x in Lambda} exp( -pi ||x||^2 / s^2 ).
The Reverse Minkowski Theorem of Regev and Stephens-Davidowitz ([Reverse-
Minkowski] Theorem 1.2), in the scaled form [C] Theorem 3.4, gives
rho_{s_0}(Lambda) <= 3/2 under precisely the stated sublattice hypotheses.
Each vector of norm <= R contributes at least exp(- pi R^2 / s_0^2) to
rho_{s_0}(Lambda). So
#{ x : ||x|| <= R } * exp(-pi R^2 / s_0^2) <= 3/2,
which is the displayed count. Finally s_0 >= c (log N)^3 for 1 <= j <= N,
which gives the claimed exponent (pi R^2 / s_0^2 = O(N / (log N)^6) when
R^2 = N). QED.
SECTION 12. A SIMULTANEOUS BOUND FOR LATTICE INTERSECTIONS
This is the technical heart of the whole proof. The theorem below says: a
nonsingular random bit matrix B, with overwhelming probability, cannot be
put inside a "large-index" integer lattice K that has a translate holding
many cube points. Crucially the conclusion is simultaneous over all such
K, because in the applications the lattice K will be chosen after seeing
the matrix.
Theorem 12.1 (simultaneous lattice intersections). Fix D > 0 and
0 < alpha < 1, and put tau = ell^{-D}. Typically a nonsingular bit matrix
B of size m in I_N has the following property. For every lattice K with
B Z^m <= K <= Z^m, [Z^m : K] >= N^{tau N}, (12.0)
and for every x in R^m,
| (x + K) ∩ {0,1}^m | < 2^{alpha N}. (12.1)
The exceptional probability is uniform over the bit models (all m in
I_N and every admissible probability array).
Plan of the proof (paragraph form, before details). If some lattice K with
large index has a coset holding 2^{alpha N} cube points, we will find a
small set J of coordinates (|J| <= gamma N) and k test vectors
y^1, ..., y^k whose scalar products behave like independent random bits.
For fixed "representatives" of these vectors, each bit row of B must
almost lie in the integers simultaneously, which has probability
N^{-(C-3)k} per row, hence a total that vastly undercounts the possible
K's. Since the description only depends on B through the row-wise
inequality dist((B y-hat^g)_v, Z) <= 4 N^{-C} sqrt N, we obtain a bound
uniform over all K.
We first work deterministically. Assume B is nonsingular and satisfies the
prime-corank bound (Lemma 9.1), and suppose (12.0) admits a coset of K
containing at least 2^{alpha N} cube points. All constants are fixed before
N tends to infinity.
12.1. From a large intersection to separated quotient sums.
Apply Lemma 11.1 (determinant minimizer) to K with T = (log N)^4.
Write L_min for the resulting primitive sublattice, and set
F = span L_min, E = F^⊥,
Lambda = pi_E K, Pi = pi_E Z^m,
where pi_E denotes orthogonal projection. Both pi_E K and pi_E Z^m are
lattices in E, and Lambda <= Pi has full rank in E. Orthogonal covolume
factorization (11.0) gives
H(F) <= det L_min <= e^{4 N ell},
det Lambda >= N^{tau N} e^{-4 N ell}. (12.2)
First inequality: L_min <= F ∩ Z^m has the same span and rank, so det L_min
>= H(F) (adding vectors to go up to F ∩ Z^m can only increase covolume).
Second: det K = det L_min det Lambda, and det K >= 1 since K is integral
with [Z^m:K] = det K.
Difference of cube points in the chosen coset belongs to K and has norm
<= sqrt N. Lemma 11.2 bounds the number of distinct projections into
Lambda by 2^{o(N)}. Some fiber therefore contains 2^{alpha N - o(N)} cube
points. Every affine translate of F contains at most 2^{dim F} cube points
(project injectively to a set of dim F independent coordinate functionals).
Hence
dim F >= alpha N / 2 (12.3)
for sufficiently large N. This is the dimension saving that will make the
eventual net smaller than the collection of row constraints.
Choose a fixed P > D + 5. Since H(F) <= e^{N ell^2} for large N (from
(12.2) with ell = log log N), Theorem 10.1 with height exponent 2 supplies
a list member V with
d(F, V) <= N ell^{-P}. (12.4)
Put U = V^⊥. Orthocomplementation preserves rank distance, so
d(E, U) <= N ell^{-P}, (12.5)
and U belongs to a fixed list of at most 2^{N^2 ell^{-P}} subspaces.
Consequently
dim U <= (1 - alpha/3) N,
W_0 = E ∩ U,
r = dim E - dim W_0 <= N ell^{-P}. (12.6)
Rank distance controls intersections at the level of dimension; it does
not control angles between E and U. We will handle this by a two-scale
linear change of coordinates.
12.2. A two-scale map.
Fix 0 < gamma < alpha/20, and choose C > 10 large enough that
Delta := (C - 3)(1 - 2 gamma) - (C + 4)(1 - alpha/3) > 0. (12.7)
This is possible because alpha/3 - 2 gamma > 0.
Define a positive self-adjoint map S : E -> E by
S = N^2 I on W_0,
S = N^{-C-5} I on E ∩ W_0^⊥. (12.8)
The large scale on W_0 separates quotient sums (Section 12.3). The small
scale on its complement forces (via Gaussian tails of the dual lattice)
the eventual dual vectors close to U (Sections 12.4-12.5).
12.3. Covolume lower bounds and quotient index.
Because F ∩ Z^m is primitive in Z^m,
det Pi = H(F)^{-1}. (12.9)
More generally, every sublattice L <= Z^j ⊕ Pi (for any j >= 0) satisfies
det L >= H(F)^{-1}. (12.10)
To see this, take the full inverse image L~ in Z^j ⊕ Z^m under the map
(v, z) -> (v, pi_E z). Its primitive kernel is {0} ⊕ (F ∩ Z^m). Volume
factorization (11.0) gives covolume H(F) det L for L~, which is at least
one because L~ is an integer lattice. This uses the actual rank of L and
includes rank zero.
The finite group Pi / Lambda is a quotient of G_B = Z^m / B Z^m, hence
has at most g_N = ceil(N^{3/5}) generators (Lemma 9.1). Its order is at
least the lower bound on det Lambda from (12.2) (using det Pi = H(F)^{-1}
and H(F) >= 1). Multiplication by a nonzero integer u has a kernel of
size at most |u|^{g_N} on a group with g_N generators. Hence, uniformly
for 1 <= |u| <= N^C,
| u (Pi / Lambda) | >= N^{tau N - o(tau N)}. (12.11)
Here N ell / log N = o(tau N) and N^{3/5} = o(tau N).
12.4. Separated subsets of coordinates.
Fix an absolute constant R_0 >= 100 (we will use R_0 in two forms).
Lemma 12.2 (separated coordinate subsets). For every integer u with
1 <= |u| <= N^C, there is a set I_u <= [m], of size at least c_1 tau N,
such that the subset sums of
{ u S pi_E e_i : i in I_u }
have pairwise distance greater than R_0 sqrt N modulo S Lambda. The
constant c_1 > 0 is absolute, independent of u and N.
Proof. Fix u. Choose a maximal set of indices i_1, ..., i_j whose subset
sums are R_0 sqrt N separated modulo S Lambda. Adding any unselected
index i creates a pair of subset sums at distance <= R_0 sqrt N (modulo
S Lambda); the added index i occurs in exactly one of them. Undoing S,
we obtain for every i in [m]:
u pi_E e_i ≡ sum_{h=1}^j a_{hi} u pi_E e_{i_h} + eps_i
(mod Lambda),
a_{hi} in {-1, 0, 1}, ||S eps_i||_2 <= R_0 sqrt N, (12.12)
with eps_i in Pi. For i = i_h, use the exact representation: coefficient
column = standard basis e_h, zero error.
Let t be the dimension of span{ eps_i }. Choose t independent eps_i's.
Their covolume is at least 1/H(F) by (12.10). On every t-dimensional
subspace, S expands volume by at least N^{2 t - (C+7) r}: at most r
singular directions have the smaller scale N^{-C-5} in (12.8). Hadamard's
inequality applied to the S-scaled errors gives
H(F)^{-1} N^{2 t - (C+7) r} <= (R_0 sqrt N)^t.
Combining with (12.2):
t = O_C ( r + N ell / log N ) = o(tau N). (12.13)
Now define a real linear map M : R^m -> R^j ⊕ E with i-th column equal to
(a_{1i}, ..., a_{ji}, eps_i). Its integer image M Z^m is a sublattice of
Z^j ⊕ Pi of rank s <= j + t. Evaluation of a representation defines a
homomorphism
Psi : Z^j ⊕ Pi -> Pi / Lambda,
Psi(a, v) = sum_{h=1}^j a_h u pi_E e_{i_h} + v (mod Lambda).
By (12.12), Psi(M Z^m) = u (Pi / Lambda). Every column of M B lies in
ker Psi, because Psi is B-value: Pi(B pi_E e_i) is u pi_E B e_i in Lambda
(by the definition Lambda = pi_E K containing pi_E B Z^m; symmetry of B).
Moreover B is nonsingular, so rank(M B) = s. Choose s independent columns
of M B, and let L' be their integer span. Then
| u (Pi / Lambda) | <= [M Z^m : L'] = det L' / det(M Z^m). (12.14)
Each error has ordinary norm at most R_0 N^{C+5} sqrt N (undoing S:
N^{C+5} * R_0 sqrt N). Since the entries of B are in {0, 1}, the chosen
columns of M B have norm at most N^{C+9} for large N. Equation (12.10)
and Hadamard's inequality therefore yield
N^{tau N - o(tau N)} <= H(F) N^{(C+9) s}
<= H(F) N^{(C+9)(j + t)}.
Combined with (12.13), this gives j >= c_1 tau N, e.g. with
c_1 = 1 / [2(C + 9)] and sufficiently large N. QED.
There are only polynomially many integers u under consideration. Select
each coordinate of [m] independently with probability gamma/2. Binomial
concentration applied to [m] and to each I_u shows that some set
J <= [m] satisfies
|J| <= gamma N,
|J ∩ I_u| >= c_2 tau N (1 <= |u| <= N^C), (12.15)
with a fixed c_2 > 0. Indeed the failure probability for one I_u is
exp(-Omega(tau N)), which absorbs the polynomial union over u.
12.5. Dual vectors and Fourier bounds.
We have used coordinates J to separate quotient sums. We now convert that
separation into actual vectors y whose scalar product with random bit
rows is spread around the circle.
Define the dual lattice
Lambda^* = { y in E : <y, Lambda> <= Z }.
For every y in Lambda^*, symmetry of B and pi_E B Z^m <= Lambda give
B y in Z^m. (12.16)
Indeed, pi_E B Z^m <= Lambda; so <y, pi_E B e_j> is an integer for every
coordinate vector e_j; and pi_E B e_j = B e_j - (component of B e_j on F),
so up to symmetry <B y, e_j> = <y, B e_j> is an integer.
Sample y in Lambda^* with density proportional to exp(-pi ||S^{-1} y||^2).
The factor S^{-1} heals the two scales of S: Gaussian tails will place
the sample near W_0 <= U.
Write
phi(t) = b + p e^{2 pi i t}.
Lemma 12.3 (dual Fourier average). There is a fixed c_3 > 0 such that for
every 1 <= |u| <= N^C and every collection of real numbers (s_i)_{i in J},
E_y prod_{i in J} |phi(u y_i + s_i)|^2 <= e^{-c_3 tau N}. (12.17)
Proof. Let X = xi - xi' where xi, xi' are independent vectors of Bernoulli
p bits on J, extended by zero outside J. Expanding the product in (12.17)
and using <y, X> = sum_{i in J} y_i X_i gives
E_y prod |phi(u y_i + s_i)|^2
= E_X [ e^{2 pi i sum_i s_i X_i} E_y e^{2 pi i u <y, X>} ].
Poisson summation in E gives
E_y e^{2 pi i u <y, X>} = f(u X), (12.18)
f(u X) = [ sum_{lambda in Lambda} e^{-pi ||S(lambda - u pi_E X)||^2} ]
/ [ sum_{lambda in Lambda} e^{-pi ||S lambda||^2} ].
The ratio is nonnegative and at most one. (Nonnegative: sum of squares.
At most one: either via the characteristic-function interpretation, or
via the Gaussian translate inequality recorded below.) So we may discard
the phases involving s_i and bound the original expectation by E_X f(u X).
Gaussian estimates we use here. For every lattice L of rank d and every
z in its span, Poisson summation plus positivity of the Gaussian Fourier
transform imply
sum_{v in L} e^{-pi ||v - z||^2 / 2} <= sum_{v in L} e^{-pi ||v||^2 / 2},
[sum_{v in L} e^{-pi ||v||^2 / 2}] / [sum_{v in L} e^{-pi ||v||^2}]
<= 2^{d/2}. (12.19)
For the second, Poisson summation expresses the ratio as 2^{d/2} times a
ratio of dual Gaussian masses at decreasing scales. These estimates hold
for arbitrary lattices, with no additional regularity. See Banaszczyk and
Reverse-Minkowski [C] Equation (5) and Claim 2.2.
Apply them to L = S Lambda. If
dist(u S pi_E X, S Lambda) >= R_0 sqrt N / 3,
then retaining half of each Gaussian exponent in the numerator of (12.18)
gives
f(u X) <= e^{-pi R_0^2 N / 18} 2^{dim E / 2} <= e^{-c_4 N}, (12.20)
for an absolute c_4 > 0.
To bound the complementary event, condition on xi' and on all coordinates
of xi except those in J ∩ I_u. By Lemma 12.2, at most one of the
remaining subset sums lies within distance R_0 sqrt N / 3 of the prescribed
translate of S Lambda. Otherwise two such sums would be at distance
<= 2 R_0 sqrt N / 3. The probability of any one bit pattern is at most
b^{|J ∩ I_u|} <= b^{c_2 tau N}. Combining this bound with (12.20) proves
the result, after decreasing c_3. QED.
12.6. Choosing several testers at once.
Let
k = floor( kappa tau N / log N ), (12.21)
where kappa > 0 will be fixed small. There exist y^1, ..., y^k in Lambda^*
such that
|| y^g ||_2 <= R_0 N^2 sqrt N,
dist(y^g, U) <= R_0 N^{-C-5} sqrt N (1 <= g <= k),
(12.22)
prod_{i in J} |phi(sum_g w_g y_i^g)| <= e^{-c_5 tau N}
for all w in Z^k with 1 <= ||w||_inf <= N^C. (12.23)
For completeness, sample the k vectors independently from the dual
Gaussian. The Gaussian scale inequality (12.19), applied on the dual
S^{-1} Lambda^*, gives
P( ||S^{-1} y^g||_2 > R_0 sqrt N ) <= 2^{dim E/2} e^{-pi R_0^2 N / 2}.
Outside this event, the two scales of S give the geometry bound (12.22)
(the second part uses W_0 <= U).
For a fixed nonzero w in the stated range, condition on every vector
y^h except one with coefficient w_h != 0. The remaining vectors produce
arbitrary shifts in Lemma 12.3, and Markov's inequality bounds failure of
(12.23) by exp(-(c_3 - 2 c_5) tau N). There are at most (3 N^C)^k possible
w. Choose c_5 < c_3 / 4 and then kappa so small that
(C + 2) kappa < c_5 / 2. (12.24)
The union of these failures and the norm failures has probability less
than one for large N, establishing the asserted existence. The order of
choices is: gamma, C fixed first; c_1, c_2, c_3, c_5 follow; kappa is
chosen last. In particular the dependence of the Fourier constants on C
does not affect the positive margin (12.7).
We have now associated to every violating lattice a set J of at most
gamma N coordinates and k vectors satisfying (12.22)-(12.23), together
with B y^g in Z^m. The first two conditions will allow a fixed finite
description; the last will make such a description unlikely for a random
matrix.
12.7. Counting fixed descriptions and testing rows.
Fix a covering-list member U with dim U <= (1 - alpha/3) N. The region
for one vector in (12.22) can be covered by at most
N^{(C+4) dim U} (12.25)
sets of diameter 4 N^{-C}. Indeed cover its projection onto U (a ball of
radius at most R_0 N^{5/2}) at scale N^{-C}. The entire perpendicular
thickness is 2 R_0 N^{-C-9/2} = o(N^{-C}), so it needs no additional
covering directions. The same also covers the case dim U = 0 with a
single set.
Fix J and one such cell for each of the k vectors. If the cells admit a
tuple satisfying (12.22)-(12.23), choose one such tuple and denote it
y-hat^1, ..., y-hat^k. These choices are made independently of B: the
conditions just imposed involve only the fixed U, J and the vector
coordinates. The representatives need not belong to any dual lattice.
Nevertheless, existence of an actual witness in the same cells implies,
for every row index v and every g,
dist( (B y-hat^g)_v, Z ) <= 4 N^{-C} sqrt N, (12.26)
because B y^g is integral and ||B_{v, *}||_2 <= sqrt N (row entries in
{0,1}). This passage is what removes the dependence on the unknown K from
the probability estimate.
Now condition on every entry of B except those in the cross block between
J and J^c. For a row v in J^c, the remaining variables are independent bits
(B_{v i})_{i in J}. For different v in J^c these are disjoint collections
of upper-triangular variables, so the row events in (12.26) are
conditionally independent.
We bound the probability of one row by a finite Fourier expansion. Put
M_0 = floor(N^{C-2}) and define the nonnegative periodic Fejer kernel
F_{M_0}(t) = | (1/M_0) sum_{h=0}^{M_0-1} e^{2 pi i h t} |^2.
On the interval of radius 4 N^{-C} sqrt N around an integer this kernel is
bounded below by a fixed positive constant (because that radius times M_0
tends to zero). Its Fourier coefficients: c_0 = M_0^{-1}, |c_w| <= M_0^{-1}
for 1 <= |w| < M_0, zero for |w| >= M_0. Apply the product of k such
kernels to the row vector ( (B y-hat^g)_v )_{g=1}^k.
For every nonzero frequency vector w, the absolute value of its
conditional expectation is at most
prod_{i in J} |phi( sum_g w_g y-hat_i^g )| <= e^{-c_5 tau N}.
The deterministic contribution from J^c has modulus one. A bit with bias b
has the same characteristic-function modulus as one with bias p, since
|p + b e^{i t}|^2 = |b + p e^{i t}|^2. All frequencies in the product
kernel fall within (12.23). It follows, for an absolute constant C_2, that
the row probability is at most
C_2^k M_0^{-k} (1 + (3 M_0)^k e^{-c_5 tau N})
<= N^{-(C - 3) k}. (12.27)
The last inequality uses (12.24): the parenthetical is bounded, and fixed
factors per coordinate are absorbed by one power of N.
There are m - |J| >= (1 - 2 gamma) N tested rows for large N. The
conditional independence and (12.27) bound the probability for a fixed
(U, J, list of cells) by
N^{-(C - 3)(1 - 2 gamma) k N}. (12.28)
The cell choices cost at most N^{(C+4)(1 - alpha/3) k N} by (12.25). There
are at most 2^m choices of J, and at most 2^{N^2 ell^{-P}} choices of U.
Consequently the probability of any witness, together with
nonsingularity and the prime-corank bound, is at most
2^{m + N^2 ell^{-P}} * exp( -Delta k N log N )
<= exp( -c_6 tau N^2), (12.29)
for a fixed c_6 > 0. Here k ~ kappa tau N / log N, Delta > 0 is the
margin from (12.7), and P > D. Adding the exceptional probability from
Lemma 9.1 still gives 2^{-omega(N)}. Since every violating lattice
supplied a witness in the preceding construction, this proves Theorem
12.1. QED.
SECTION 13. LAYERS OF THE DISCRIMINANT GROUP
Every nonsingular integer matrix B lets us build a finite abelian group
G_B := Z^m / B Z^m.
Its size is |det B|. By Hadamard's inequality this is at most N^{N/2}
under the layer window (m in I_N).
For a finite abelian group G, write its l-primary part (l a prime) as
G_l ≅ ⊕_i Z / l^{b_{l,i}} Z, b_{l,1} >= b_{l,2} >= ... >= 0,
where we append zero exponents so the sequence is defined for all i.
For j >= 1 define the layer height and weight:
k_G(l, j) = #{ i : b_{l,i} >= j },
nu_l = log_N l / N = log l / (N log N).
A "layer" is a pair (l, j) with k_G(l, j) >= 1. Write k_B for k_{G_B}.
Group-order bound. For G_B and for every quotient of G_B (Hadamard used
twice: |G_B| <= |det B|, and any quotient of G_B has order dividing |G_B|),
we have
sum_{l, j} k_G(l, j) nu_l
= log |G| / (N log N) <= 1/2, m <= N. (13.1)
Indeed |G| <= |det B| <= m^{m/2} <= N^{N/2}, hence log |G| / log N <= N/2.
Tail potentials. For s >= 0, put
W_s(B) = sum_{l, j} (k_B(l, j) - s)_+ nu_l, (x)_+ = max{x, 0}.
Two intermediate quantities:
T_2(B) = sum_{k_B(l, j) = 2} nu_l
= sum_l (b_{l, 2} - b_{l, 3}) nu_l, (13.2)
J_B = sum_{k_B(l, j) >= 3} k_B(l, j) nu_l.
So T_2 counts layers of height exactly 2 (with weight nu_l), whereas J_B
counts their full heights when the height is at least 3. In particular
0 <= J_B <= 1/2, J_B <= 3 W_2(B), (13.3)
because k <= 3(k - 2) for every integer k >= 3.
(There is a useful picture. At a single prime, list the cyclic factors
as columns; each column has height b_{l,i}; drawing the layer of height j
as the set of columns of length >= j. W_2 sums column-weights of rows
of the diagram with height above the row s = 2. T_2 counts layers where
exactly two columns reach that height. J_B counts column-weights of
layers where at least three columns reach that height.)
The slowly varying scales:
R = ceil( ell^2 ), sigma = R^{-6}. (13.4)
They will also be used in Section 20 (paths).
Proposition 13.1 (static column estimate). For every fixed L_0 >= 1 and
e_0 > 0, there is a fixed zeta > 0 such that, typically for nonsingular
bit matrices B of size m in I_N,
W_2(B) <= zeta ==> | S_{L_0}(B) | <= 2^{e_0 N}. (13.5)
The proposition is proved at the end of Section 19. The proof splits by
the size of T_2(B). We will spend Sections 14-15 on pairings and colorings
(the T_2 >= sigma case) and Sections 17-19 on spectral bounds (the T_2 <
sigma case).
SECTION 14. THE DISCRIMINANT PAIRING AND ITS PRIMARY COLORINGS
The discriminant pairing of B is
lambda_B(x + B Z^m, y + B Z^m) = x^T B^{-1} y in Q / Z. (14.1)
It is well defined: replacing x by x + B u or y by y + B v changes the
value by an integer. It is SMOOTH in the sense that its value depends
only on the classes.
Perfectness. The map G_B -> Hom(G_B, Q/Z) given by x -> lambda_B(x, .)
is an isomorphism. To see injectivity: if lambda_B(x, y) = 0 for all y
then x^T B^{-1} y in Z for all y in Z^m, i.e., B^{-1} x in Z^m, i.e.,
x in B Z^m, so x = 0 in G_B. The two finite groups have the same order,
so injective implies isomorphic.
Distinct primary components are orthogonal, since their mutual pairing is
killed by coprime powers. An element x is isotropic if lambda_B(x, x) = 0.
Every z in S_{L_0}(B) has isotropic class: z^T B^{-1} z is an integer or
z^T B^{-1} z = 1 (i.e., zero in Q/Z). Its primary components are then
individually isotropic (uniqueness of primary decomposition in Q/Z).
Orthogonal block decomposition. A perfect primary pairing on a finite
abelian l-group splits into cyclic blocks (and at l = 2, possible
two-generator blocks of equal cyclic exponents). This is classical; see
Miranda. We use the following consequences, adapted from [C] Lemmas
6.1-6.3.
Lemma 14.1 (coloring input). Let B be a nonsingular symmetric integer
matrix. For each prime l put f_l = b_{l, 3}. The perfect pairing on
G_{B, l} admits an orthogonal decomposition
G_{B, l} = U_l ⊕ V_l, (14.2)
where U_l consists of the blocks with cyclic exponents strictly greater
than f_l, and the exponent of V_l divides l^{f_l}. There are at most
two cyclic factors in U_l. The isotropic elements of G_{B, l} can be
colored with C_l colors satisfying
C_l <= 1 + 8 b_{l, 1},
C_l <= 2^{b_{l, 2} - b_{l, 3}} (when l is odd), (14.3)
such that two elements of one color satisfy
l^{f_l} lambda_B( x_{U_l}, y_{U_l} ) = 0 in Q/Z. (14.4)
If X <= G_B consists of isotropic elements with one fixed color at every
prime, put H = < x - y : x, y in X >. Then the image of the restricted
pairing map
H -> Hom(H, Q/Z), u -> lambda_B(u, .)|_H, (14.5)
has order at most N^{N J_B}.
Remarks. The cutoff f_l does not split a block, since the two exponents in
each two-generator block are equal. Restricting the test characters to H
(rather than all of G_B) is what makes the pairing image order bounded
by N^{N J_B} rather than something larger.
For our purposes the same coloring has one more useful consequence.
Lemma 14.2 (a subgroup containing each color). For every prime l, each
primary color in Lemma 14.1 is contained in a subgroup of G_{B, l} whose
index is at least l^{b_{l, 2} - b_{l, 3}}.
Proof. Write f = f_l and U = U_l. Multiply the perfect pairing on U by
l^f, and quotient U by the radical of this new pairing. The resulting
pairing on the group U-bar is perfect. Its order is
| U-bar | = l^{ sum_i (b_{l,i} - f)_+ }. (14.6)
Indeed, under the original perfect pairing the new radical is
U[l^f] = {u in U : l^f u = 0}; each cyclic factor of exponent b > f
leaves a quotient of order l^{b - f}.
By (14.4), the images of one color generate a subgroup A <= U-bar with
A <= A^⊥. Perfectness gives |A| |A^⊥| = |U-bar|, so
[U-bar : A] >= |U-bar|^{1/2} = l^{(1/2) sum_i (b_{l,i} - f)_+}
>= l^{b_{l, 2} - f}. (14.7)
Take the preimage of A in U, and add the unrestricted summand V_l. This
subgroup contains the entire primary color and has the required index.
The argument also covers U = 0, when the asserted index is one. QED.
SECTION 15. SUBGROUPS OF LARGE INDEX AND THE COST OF SPECIFYING COLORS
The coloring price. Lemma 15.1 below controls how much entropy is spent
specifying colors. It uses both bounds in (14.3): the odd-prime bound is
efficient before a weight threshold is reached, the polynomial bound
controls the prime that crosses it.
Lemma 15.1 (cost of specifying colors). Uniformly over nonsingular
symmetric bit matrices of size at most N, the following hold as N -> inf.
(i) If T_2(B) >= sigma, there is a set of primes P such that
sum_{l in P} (b_{l, 2} - b_{l, 3}) nu_l >= sigma,
sum_{l in P} log_2 C_l = o(N).
(ii) If T_2(B) < sigma, then sum_l log_2 C_l = o(N).
Proof. The group-order bound (13.1) gives b_{l, 1} <= (N/2) log_2 N, so
the first bound in (14.3) costs O(log N) bits per prime. All primes
l <= sqrt N together therefore cost O(sqrt N log N) = o(N).
For larger primes, nu_l > 1/(2N); they are odd for large N, and hence
sum_{l in P, l > sqrt N} log_2 C_l
<= sum_{l in P, l > sqrt N} (b_{l, 2} - b_{l, 3})
<= 2N sum_{l in P} (b_{l, 2} - b_{l, 3}) nu_l. (15.1)
For (i): first include every contributing prime at most sqrt N. If their
total weight is below sigma, add larger contributing primes until that
threshold is first reached. Before the last prime, (15.1) costs at most
2 sigma N bits. Charge the last prime only O(log N) bits using the first
color bound, regardless of its weight. The total is o(N), since
sigma -> 0.
For (ii): (15.1) applies to all large primes with total cost at most
2 sigma N; the small-prime cost is unchanged. QED.
Fix 0 < alpha < min{e_0, 1} (the small parameter of Theorem 12.1). Impose
the typical event of Theorem 12.1 with D = 20. Since tau = ell^{-20} =
o(sigma), the preceding lemmas settle all matrices with T_2(B) >= sigma.
In fact, specify colors only at the primes selected in Lemma 15.1 (i).
There are 2^{o(N)} resulting parts of S_{L_0}(B). By Lemma 14.2 each
part lies in the preimage K <= Z^m of a subgroup of G_B with
B Z^m <= K <= Z^m, [Z^m : K] >= N^{sigma N} >= N^{tau N}. (15.2)
Theorem 12.1 bounds its size by 2^{alpha N}. Consequently
| S_{L_0}(B) | <= 2^{alpha N + o(N)} <= 2^{e_0 N} (15.3)
for sufficiently large N. This argument uses the simultaneity of Theorem
12.1 over all lattices: the color subgroups may depend on B. We have just
proved:
Lemma 15.2 (static column estimate, T_2 >= sigma case). On the typical
event of Theorem 12.1 (D = 20), nonsingular bit matrices B of size m in
I_N with T_2(B) >= sigma satisfy | S_{L_0}(B) | <= 2^{e_0 N}.
In particular, the hypothesis W_2 <= zeta of Proposition 13.1 is not even
needed in this case: T_2 >= sigma on its own forces |S_{L_0}(B)| <= 2^{e_0 N}.
To finish Proposition 13.1 we must handle T_2 < sigma. That is the
content of Sections 17-19; Section 16 first assembles the two real-matrix
inputs (inverse-rank and small-spectrum) that the T_2 < sigma case needs.
END OF PART II. CONTINUES WITH SECTIONS 16-19.
SECTION 16. REAL-MATRIX INPUTS: INVERSE RANK AND SMALL SPECTRUM
This section and Sections 17-20 together handle the T_2 < sigma case.
Here we set up the two real-matrix inputs the graph comparison needs:
inverse restriction rank (16.1) and small-spectrum (16.2). Geometric and
pairing inputs come in Sections 17-18; the graph comparison itself is
Section 19; the static column estimate is completed in Section 20.
Throughout "typically" for the two propositions means: fails with
probability at most 2^{-c N^2} where c > 0 is a large constant; this is
much stronger than 2^{-omega(N)}, so a union with the typical event of
Theorem 12.1 stays typical.
Notation: for a linear map A : R^m -> R^m written B^{-1} here, B^{-1}|_F
denotes the restriction of the BILINEAR FORM (x, y) -> x^T B^{-1} y to
F x F, and rank of the restriction means the rank of that bilinear form.
Proposition 16.1 (uniform inverse restriction rank). For every fixed
D > 0 and xi > 0, typically a nonsingular bit matrix B of size m in I_N
satisfies, simultaneously for all rational subspaces F <= R^m with
H(F) <= exp(N ell^D),
rank( B^{-1}|_F ) >= dim F - xi N. (16.0)
Proof. First fix an arbitrary real subspace U <= R^m of dimension d.
Choose a basis matrix V and a coordinate set I of size d such that V_I is
the identity (Gaussian elimination). Conditional on all entries of B
outside the principal block I x I, the matrix of B|_U in this basis is
V^T B V = B_{I, I} + H, (16.1)
where H is a fixed symmetric matrix over R (it depends on the entries of
B outside I x I, but is fixed after conditioning). The unrevealed entries
of B_{I, I} are independent bits, each with largest atom b.
Fact 9.0, applied with k = ceil(xi N / 2), gives
P( dim rad( B|_U ) >= ceil(xi N / 2) ) <= 2^{-c_{p, xi} N^2}. (16.2)
(The event is empty if d < ceil(xi N / 2).)
For a fixed symmetric form, the nullity of the restriction to U changes
by at most d(U, V) when U is replaced by V (rank distance). Indeed, if
Z <= U has codimension t, then restriction to Z deletes t rows and t
columns of a representing matrix; rank decreases between zero and 2t, so
nullity changes by at most t. Apply first to Z = U ∩ V inside U, then
inside V.
Now apply Theorem 10.1 (height cover) with the given D and any fixed
P > 0. Use (16.2) for the orthogonal complement of every list member.
The union of failures has probability at most
2^{N^2 ell^{-P} - c_{p, xi} N^2} = 2^{-Omega_{p, xi}(N^2)}.
Outside this event, approximate a given F by a list member U. The nullity
comparison and preservation of rank distance under orthocomplements give
dim rad( B|_{F^⊥} ) < ceil(xi N / 2) + N ell^{-P} <= xi N (16.3)
for large N. For nonsingular B, the two radicals satisfy the equalities
rad( B|_{F^⊥} ) = F^⊥ ∩ B^{-1} F,
rad( B^{-1}|_F ) = F ∩ B(F^⊥). (16.4)
Multiplication by B is an isomorphism from the first space onto the
second, so they have equal dimensions. Hence rank(B^{-1}|_F) = dim F -
dim rad(B^{-1}|_F) >= dim F - xi N, proving (16.0). QED.
Proposition 16.2 (small-spectrum bound). For every fixed xi > 0 there is
w_xi > 0, depending also on p, such that typically a bit matrix B of size
m in I_N has at most xi N eigenvalues, counted with multiplicity, in
[ -w_xi sqrt N, +w_xi sqrt N ]. (16.5)
Nonsingularity is not required. The exceptional probability is at most
exp(-c_{p, xi} m^2).
Proof. Set
X = (B - E B) / sqrt(m p b),
mu_X = (1/m) sum_i delta_{lambda_i(X)}. (16.6)
Step 1 (Wigner limit). We first verify that the expected measures E mu_X
converge uniformly over the permitted arrays to the semicircle law
d mu_sc(x) = (1/(2 pi)) sqrt(4 - x^2) 1{|x| <= 2} dx. (16.7)
This is the fixed-moment argument for Wigner's law. The centered,
variance-standardized entries (B_{i j} - E B_{i j}) / sqrt(p b) have mean
zero, variance one, and uniformly bounded moments of every fixed order.
Expand (1/m) E Tr X^s as a sum over closed walks of length s. Independence
makes a summand vanish whenever an unordered edge is used exactly once.
Every remaining walk has at most s/2 distinct edges and at most s/2 + 1
vertices. For each fixed walk pattern with v < 1 + s/2 vertices, its
contribution is O_{p, s}(m^{v - 1 - s/2}) = o(1). Equality is possible
only when s is even and the walk traverses each edge of a tree twice.
Each such pattern contributes 1 + o(1) (since it only uses variances),
and there are (s/2 + 1)^{-1} C(s, s/2) such tree patterns. There are
finitely many patterns for fixed s, so the errors are uniform. Limiting
moments are those of mu_sc, and its compact support makes them
determinate. Method of moments proves the asserted weak convergence
uniformly by applying the same argument to any sequence of permitted
arrays.
Step 2 (tent function). Choose a fixed w > 0, sufficiently small in
terms of xi, and put
f(x) = (1 - |x|/w)_+. (16.8)
The semicircle mass of [-w, w] tends to zero with w, so Step 1 gives,
for large N,
E Tr f(X) <= xi m / 16. (16.9)
To upgrade this expectation statement to a probability statement, write
f = 1 - g_1 + g_2, g_1(x) = |x|/w, g_2(x) = (|x|/w - 1)_+.
Both g_1, g_2 are convex and 1/w-Lipschitz, and their matrix traces are
convex functions of the entries. Indeed, if M_+ denotes the spectral
positive part of a symmetric M, then Tr M_+ = sup_{0 <= P <= I} Tr(P M);
expressing the two traces as sums of positive-part traces proves
convexity directly.
Let y denote the independent upper-triangular coordinates and write X(y)
for the corresponding centered, normalized matrix. Hoffman-Wielandt
together with Cauchy-Schwarz gives, for j = 1, 2,
| Tr g_j(X(y)) - Tr g_j(X(y')) |
<= (sqrt m / w) ||X(y) - X(y')||_F
<= (1/w) sqrt(2 / (p b)) ||y - y'||_2. (16.10)
Here ||.||_F is the Frobenius norm; the factor 2 accounts for reflecting
off-diagonal entries.
Talagrand's convex-distance inequality (in the convex-Lipschitz form
[Talagrand] Theorem 4.1.1) applies to independent coordinates in [0, 1]
with arbitrary distributions: if F is convex and L-Lipschitz then
P(|F - E F| > t) <= C exp(-c t^2 / L^2). The usual median formulation
implies this expectation formulation by integrating the tail and
adjusting absolute constants.
Applying it to the two convex traces, with deviations xi m / 32, and using
(16.9), gives
P( Tr f(X) > xi m / 8 ) <= C exp(- c_{p, xi, w} m^2). (16.11)
Step 3 (eigenvalue count). On the complementary event, f >= 1/2 on
[-w/2, w/2] implies that at most xi m / 4 eigenvalues of X lie in
[-w/2, w/2]. The matrix B / sqrt(m p b) differs from X by a matrix of
rank at most two (E B has rank at most two by Lemma 5.1(ii)). Interlacing
changes the eigenvalue count in any fixed interval by at most 4. Taking,
for example, w_xi = w sqrt(p b) / 4, we have w_xi sqrt(N / (m p b)) <= w/2
for large N, uniformly in m in I_N. The requested eigenvalue count is
therefore at most xi m / 4 + 4 <= xi N. QED.
SECTION 17. TWO GEOMETRIC INPUTS FROM [C]
We use two deterministic lemmas about "robust" subsets of the cube and
image lattices.
A nonempty finite set A <= R^m is rho-robust on its affine span F if every
affine subspace E <= F of codimension t satisfies
| A ∩ E | <= 2^{-rho t} |A|. (17.0)
Lemma 17.1 (robust extraction, [C] Lemma 3.7). If A is a nonempty subset
of {0,1}^m and rho > 0, there is an affine subspace E for which the
nonempty set V = A ∩ E is rho-robust on its affine span and satisfies
log_2 |V| >= log_2 |A| - rho m. (17.1)
Lemma 17.2 (determinant of a robust image lattice, [C] Lemma 3.8). Fix
D, C_0 > 0 and put rho = ell^{-D}. Let V be a nonempty subset of {0,1}^m,
m <= N, rho-robust on its affine span F of dimension r. Let
Phi : F -> R^d be an injective rational affine map such that
|| Phi(v) - Phi(w) ||_2 <= C_0 sqrt N for all v, w in V. (17.2)
Then the integer span of its image differences is a rank-r lattice of
covolume at most exp(O_{D, C_0}( N ell )).
Also H(span(V - V)) <= exp(O_D(N ell)).
The covolumes in rank zero are one.
We cite Lemma 17.1 and Lemma 17.2 from [C]. Both are deterministic,
involve only {0,1}^m and rational maps, and do not depend on the entry
distribution.
SECTION 18. PAIRING IMAGE AND DETERMINANT
For a symmetric matrix C and a linear subspace F <= R^m, the notation
C|_F denotes the restriction of the BILINEAR FORM (x, y) -> x^T C y to
F x F, not the restriction of the associated linear map. Its radical is
rad( C|_F ) = { x in F : x^T C y = 0 for every y in F }. (18.0)
Its dimension is nullity dim F - rank(C|_F).
The next lemma converts a bound on the image order of a discriminant-type
pairing into a lower bound on a determinant. It is a slight repackaging
of [C] Lemma 6.4; we give the short proof so that the role of the image
order (a power N^{N J_B}) is clear.
Lemma 18.1 (pairing image and determinant). Let L be a lattice spanning
a Euclidean space V, and q a symmetric bilinear form with q(L, L) <= Q.
Set
K = L ∩ rad q, S = V ∩ (rad q)^⊥. (18.1)
If the image of L -> Hom(L, Q/Z), x -> q(x, .) mod Z, has order t, then
| det_orth( q|_S ) | >= (det K)^2 / ( t (det L)^2 ). (18.2)
The determinant on the left is in an orthonormal basis of S.
Proof. The matrix of q in a lattice basis of L is rational; its radical
has a rational basis; so K spans the radical and is primitive in L.
Orthogonal projection of L onto S is a lattice L-bar, and
det L = (det K) (det L-bar). (18.3)
The form descends to L-bar with the same pairing-image order t, because
pullback of characters along L -> L-bar is injective.
Let M be the nonsingular matrix of the descended form in a basis of
L-bar. Its pairing kernel modulo Z in the coordinate lattice has index t.
If A is an integer basis matrix for that kernel, then |det A| = t and
A^T M is integral and nonsingular, hence
1 <= |det(A^T M)| = t |det M|. (18.4)
Changing from the lattice basis to an orthonormal basis divides this
determinant by (det L-bar)^2 = (det L / det K)^2. Combined with (18.3),
this gives (18.2). If S has dimension zero then K = L and t = 1, so
both sides of (18.2) are one. QED.
END OF MIDDLE PART. CONTINUES WITH SECTIONS 19-20.
SECTION 19. THE GRAPH COMPARISON
We now bring together everything from Sections 14-18. The result: for
T_2(B) < sigma, the column set |S_{L_0}(B)| is bounded by 2^{(2 J_B + small) N}
provided a certain inverse-rank hypothesis and a certain small-spectrum
hypothesis hold. Sections 16 and 20 together show these hypotheses are
typical.
Lemma 19.1 (the graph comparison). Fix L_0 >= 1 and xi, w > 0. Suppose
that B is a nonsingular symmetric bit matrix of size m in I_N, with
T_2(B) < sigma, and the following hold:
(i) for every rational F <= R^m of height at most exp(N ell^2),
rank( B^{-1}|_F ) >= dim F - xi N;
(ii) at most xi N eigenvalues of B lie in [-w sqrt N, w sqrt N].
Then
| S_{L_0}(B) | <= 2^{(2 J_B + 2 xi + o(1)) N}, (19.1)
where the o(1) is bounded uniformly over such B.
Proof. If S_{L_0}(B) is empty, done. Otherwise pick the largest overall
color A of the column set: at each prime l one color class, chosen so
that |A| is maximal. Each element of S_{L_0}(B) has one fixed color at
every prime; the S-partition into prod_l C_l parts has largest piece A.
So
log_2 |S_{L_0}(B)| <= sum_l log_2 C_l + log_2 |A|. (19.2)
By Lemma 15.1(ii), the T_2 < sigma case gives sum_l log_2 C_l = o(N).
Robust extraction. Apply Lemma 17.1 with rho = ell^{-2} to A. There is
an affine subspace E whose intersection V = A ∩ E is rho-robust on its
affine span and satisfies
log_2 |V| >= log_2 |A| - rho m >= log_2 |A| - o(N).
Putting this back into (19.2):
log_2 |S_{L_0}(B)| <= log_2 |V| + o(N). (19.3)
Setup. Set F_0 = span( V - V ), r_0 = dim F_0. The graph map
gamma(x) = ( x, B^{-1} x ) in R^m ⊕ R^m,
and the integer span L = < gamma(v) - gamma(v') : v, v' in V > of graph
differences in gamma(F_0). The differences themselves satisfy
|| gamma(v) - gamma(v') ||_2^2 <= m + 4 L_0^2 N
<= (1 + 4 L_0^2) N. (19.4)
(The first term bounds the |v - v'|^2 part with |v| <= 1 coordinatewise;
the second bounds the |B^{-1}(v - v')|^2 part via the definition of
S_{L_0}(B).)
Applying Lemma 17.2 (robust image) to gamma|_F_0 and to the identity map
on F_0, with C_0 = sqrt(1 + 4 L_0^2) and rho = ell^{-2}:
det L <= exp( O_{L_0}(N ell) ),
H(F_0) <= exp( O(N ell) ) <= exp( N ell^2 ) (19.5)
for large N.
The form q. On the full graph Gamma = gamma(R^m) define the symmetric
bilinear form
q( gamma(x), gamma(y) ) = x^T B^{-1} y.
Restricted to gamma(F_0), q has rank s satisfying
s >= r_0 - xi N (19.6)
by hypothesis (i) applied to F_0 (whose height is controlled by (19.5)).
Pullback of pairing. The map L -> G_B sending gamma(u) to u + B Z^m
has image
H = < v - v' : v, v' in V > (mod B Z^m),
which it surjects onto. The form q modulo Z on L pulls back to the
restricted pairing on H: for gamma(v) - gamma(v') and gamma(w) - gamma(w'),
q( ... , ... ) = (v - v')^T B^{-1} (w - w') = lambda_B( v - v',
w - w' ).
Pullback of characters is injective (two character maps having the same
values on H coincide). Hence the two pairing maps have equal image
orders. Lemma 14.1 bounds this order by
t <= N^{N J_B}. (19.7)
Let K be the radical lattice of the restriction to gamma(F_0) and S the
radical's orthogonal complement within gamma(F_0). First-coordinate
projection is injective on Gamma, takes K to an integer lattice of the
same rank, and orthogonal projection contracts volumes. Hence
det K >= 1. (19.8)
Lemma 18.1 (pairing image and determinant) applied with L and q:
| det_orth( q|_S ) | >= N^{-N J_B} exp(-O_{L_0}(N ell)). (19.9)
Determinant upper bound from the spectrum. If v is a unit eigenvector of
B with nonzero eigenvalue x, its graph vector gamma(v) has squared norm
1 + x^{-2} and q(gamma(v), gamma(v)) = x^{-1}. Orthogonal eigenvectors
of B give orthogonal graph vectors. Therefore the eigenvalues of the
self-adjoint operator representing q on Gamma are
x / (1 + x^2), for the eigenvalues x of B.
They all have absolute value at most 1. By hypothesis (ii), at most
xi N of them have absolute value greater than C_w / sqrt N, where
C_w = 1 / w (because x / (1 + x^2) ~ x for |x| small; |x| <= 1 for the
remaining ones; and |x| <= 1/w sqrt N gives |x/(1+x^2)| <= 1/w sqrt N).
Compression determinant bound. The absolute value of the compression of
a self-adjoint operator to any s-dimensional subspace is at most the
product of its largest s singular values: it equals
<omega, (Lambda^s T) omega> where omega is the unit exterior product of
an orthonormal basis of the subspace. Applying this to S (dimension s):
| det_orth( q|_S ) | <= ( C_w / sqrt N )^{(s - xi N)_+}. (19.10)
(For indefinite forms the same conclusion holds by taking absolute
values of eigenvalues; s = 0 is covered because then the right side is
1.)
Assembling. Combine (19.9) and (19.10), then use (19.6):
(s - xi N)_+ * ( (1/2) log N - log C_w )
<= N J_B log N + O_{L_0}(N ell),
r_0 / N <= 2 J_B + 2 xi + o(1). (19.11)
(The second inequality also holds when s < xi N because r_0 / N <= 1 and
2 J_B + 2 xi can be taken close to 1 by choosing xi small.)
Finally, projection to r_0 suitable coordinates is injective on the
affine span of V, so |V| <= 2^{r_0}. Combining with (19.3):
(1/N) log_2 | S_{L_0}(B) | <= r_0 / N + o(1)
<= 2 J_B + 2 xi + o(1). (19.12)
The error is bounded by O_{L_0, w}( ell^{-2} + sigma + N^{-1/2} log N +
ell / log N ); the first three terms come from extraction and colors,
the last from the determinant comparison, and we use J_B <= 1/2. This
establishes the asserted uniformity. QED.
SECTION 20. FINISHING THE STATIC COLUMN ESTIMATE
Proof of Proposition 13.1. Fix L_0 >= 1 and e_0 > 0. Choose fixed xi,
zeta > 0 with 6 zeta + 2 xi < e_0.
Intersect the typical event used for (15.3) with those of Propositions
16.1 and 16.2, taking height exponent D = 2 in Prop 16.1 and error xi
in both propositions. The latter supplies a fixed w_xi > 0. This finite
intersection is still typical, uniformly in the permitted models and
sizes.
Let B be nonsingular on this event, with W_2(B) <= zeta.
Case A: T_2(B) >= sigma. Equation (15.3) already gives
| S_{L_0}(B) | <= 2^{e_0 N}.
Case B: T_2(B) < sigma. Apply Lemma 19.1 with xi and w = w_xi. Since
J_B <= 3 W_2(B) by (13.3):
| S_{L_0}(B) | <= 2^{(2 J_B + 2 xi + o(1)) N}
<= 2^{(6 zeta + 2 xi + o(1)) N}
<= 2^{e_0 N} (20.1)
for all sufficiently large N (the o(1) is small, and 6 zeta + 2 xi is
strictly less than e_0). This proves Proposition 13.1. QED.
END OF STATIC COLUMN ESTIMATE. CONTINUES WITH SECTIONS 21+.
SECTION 21. PRINCIPAL EXTENSIONS, GATED DELETION, RETAINED LAYERS
Proposition 13.1 covers matrices with W_2(B) <= zeta. We now show that a
matrix with large W_2 must encounter two "rare column" constraints along
a short path of principal minors. Each such constraint costs almost b^N,
giving exactly the exceptional probability required by Proposition 8.1.
Definitions. A principal extension of width h in {1, 2} of a nonsingular
C has the form
B = [ C V ]
[ V^T D ], V = (v_1 ... v_h), (21.0)
with C nonsingular and D symmetric. At width two we impose the gate
v_1, v_2 in S_{L_0}(C). (21.1)
There is no gate at width one.
Lemma 21.1 (gated deletion, [C] Lemma 7.1). Let B be a nonsingular
symmetric bit matrix of positive size. The empty principal minor has
determinant one, and its admissible column set consists of the unique
empty column. Then either
(a) some one-coordinate principal deletion is nonsingular, or
(b) a two-coordinate principal deletion gives a nonsingular C for
which both deleted cross columns satisfy
v_i^T C^{-1} v_i in {0, 1}, || C^{-1} v_i ||_inf <= 1
(i = 1, 2). (21.2)
In particular, whenever the sizes belong to I_N, the two-coordinate move
satisfies the gate (21.1).
Proof. The cofactor identity gives (a) if some diagonal entry of B^{-1}
is nonzero. Otherwise choose distinct i, j maximizing the absolute value
of an entry of B^{-1}, and write kappa = (B^{-1})_{i j} != 0. The
corresponding principal block is [[0, kappa], [kappa, 0]]. Jacobi's
complementary minor identity makes the complementary matrix C
nonsingular. In the block notation of (21.0), the Schur complement
T = D - V^T C^{-1} V satisfies
T^{-1} = [ 0 kappa ],
[ kappa 0 ],
(B^{-1})_{I, {i, j}} = -C^{-1} V T^{-1}, (21.3)
where I is the set of remaining indices. The diagonal of T vanishes,
giving the two quadratic identities in (21.2). The two columns of the
inverse block on the right are -kappa C^{-1} v_2 and -kappa C^{-1} v_1.
Their entries have absolute value at most |kappa|, proving the norm
bound. Finally || C^{-1} v_i ||_2 <= sqrt(size(C)) <= sqrt(N) <=
L_0 sqrt(N). QED.
Quotient groups. For an extension (21.0) with nonsingular start C,
define the successive quotients
G_0 = G_C, G_i = Z^m / ( C Z^m + Z v_1 + ... + Z v_i )
= G_{i-1} / <v_i-bar> (21.4)
with m = size(C). These groups are defined even if the endpoint B is
singular. In a one-element quotient, each layer height drops by zero or
one. A positive layer whose height does not drop is called RETAINED. A
PLATEAU is a maximal interval of consecutive layers of equal positive
height at one prime. On each plateau, the retained layers form a prefix,
possibly empty. (These are [C] Lemma 7.3. For the prefix assertion: in a
one-element quotient, quotient heights are non-increasing and can only
equal the original height or one less; so heights above any level are
retained if and only if the level is above the quotient-drop point.)
Lemma 21.2 (retention lattices and tail recursion, [C] Lemmas 7.4 and
11.1). Let C be a nonsingular symmetric bit matrix of size m <= N.
(i) Let pi : Z^m -> G be a quotient map with C Z^m <= ker pi. For
any set D of positive layers of G, there is a lattice K_D, fixed
by pi, G, D, such that
C Z^m <= K_D <= Z^m,
[Z^m : K_D] = N^{N q(D)}, q(D) = sum_{(l, j) in D} k_G(l, j) nu_l.
(21.5)
If every layer in D is retained on quotienting by pi(v), then
v in K_D.
(ii) Suppose the extension (21.0) also has nonsingular endpoint B.
Then k_B(l, j) <= k_C(l, j) + h for every layer. Writing R_i
for the retained layers in G_{i-1} -> G_i, for every integer
s >= h,
W_s(B) <= W_{s+h}(C) + 2 * sum_{i=1}^h
sum_{(l, j) in R_i, k_{G_{i-1}}(l, j) >= s+1-h} nu_l.
(21.6)
Source and interpretation. Part (i) is the Retention lattice lemma
[C] Lemma 7.4, including arbitrary (non-consecutive) sets of layers.
Part (ii) is the Tail recursion lemma [C] Lemma 11.1 together with
common-quotient interlacing [C] Equation (7.11).
For the height comparison: projection onto the old coordinates
identifies G_h with the quotient of G_B by the h new coordinate classes.
A one-element quotient lowers each height by at most one, so
k_B <= k_{G_h} + h <= k_C + h.
The stronger recursion uses symmetry through the Symmetric kernel
inequality [C] Lemma 7.5; it needs no assumption on the entry
distribution. All of the displayed statements therefore apply to the
present biased model.
SECTION 22. THE COST OF RETAINING LAYERS
Fix L_0 >= 1, a sufficiently small fixed e_0 > 0, and the corresponding
zeta > 0 from Proposition 13.1. Recall from (13.4): R = ceil(ell^2) and
sigma = R^{-6}.
Costly extensions. Call a principal extension COSTLY if, in at least one
of its quotient operations,
sum_{(l, j) in R_i} nu_l >= sigma. (22.0)
Lemma 22.1 (almost full cost of retention). Typically for nonsingular
C with size in I_N, conditional on C, the probability that an
independent principal extension of either width is costly is at most
p_N := 2^{-N(a - 2 e_0)}. (22.1)
For one specified column, the probability that its retained weight is at
least sigma obeys the same bound, also after exposing the preceding
column of a width-two extension. Also, typically, when W_2(C) <= zeta,
the width-two gate has conditional probability at most p_N^2.
Proof. Impose Theorem 12.1 on C with tau = ell^{-20} and some fixed
0 < alpha < e_0. Then tau = o(sigma). We show that the retention
condition can be covered by 2^{o(N)} selected layer sets, each giving a
lattice of index at least N^{sigma N}.
Let G be the group before one column is tested. It is a quotient of
G_C, so its total height times weight is at most 1/2 (by the group-order
bound (13.1)).
At a prime l, let d_l be its number of plateaus. Distinct positive
plateau heights give d_l^2 <= 2 sum_j k_G(l, j). The group-order bound
sum_{l, j} k_G(l, j) = O(N log N) gives, by Cauchy-Schwarz,
sum_{l <= sqrt N} d_l <= sqrt( #{l <= sqrt N} * 2 sum_j k_G(l, j) )
= O( N^{3/4} sqrt(log N) ). (22.2)
Each prefix length has O(N log N) possible values. Thus the complete
retention pattern at these primes can be specified with
O( N^{3/4} (log N)^{3/2} ) = o(N) (22.3)
bits. Include all those retained layers in the selected set.
If their total weight is below sigma, add retained layers at primes
l > sqrt N until the total first reaches sigma. There are at most N
candidate layers in this prime range (since each has nu_l > 1/(2N)).
At most ceil(2 sigma N) + 1 additions suffice. The binomial bound
therefore contributes 2^{o(N)} further possibilities. This constructs
the claimed cover whenever the retained weight is at least sigma.
For every selected set D, positive heights and (21.5) give
q(D) >= sigma. The simultaneous cube estimate (Theorem 12.1) applies
to K_D, since it contains C Z^m, even when G depends on an earlier
column. Each cube point has probability at most b^m, where
m = N - o(N). The one-column probability is therefore at most
2^{o(N)} 2^{alpha N} b^m
= 2^{-N(a - alpha - o(1))}. (22.4)
The slack alpha < e_0 absorbs a union over at most two columns and
yields (22.1).
Finally, impose Proposition 13.1 on the start. When W_2(C) <= zeta, each
column belongs to S_{L_0}(C) with probability at most 2^{e_0 N} b^m.
The two cross columns are independent conditional on C, so the gate
probability is at most
(2^{e_0 N} b^m)^2 <= p_N^2. (22.5)
QED.
END OF PART IV. CONTINUES WITH SECTIONS 23+.
SECTION 23. DISSOCIATION AND HEAVY RETAINED LAYERS
We need a way to bound the probability that a random bit column falls
in a particular lattice K, without appeal to the simultaneous
intersection theorem. This is a purely combinatorial ``dissociation''
argument.
Lemma 23.1 (dissociation and a lattice constraint). Let C be a
nonsingular bit matrix of size m <= N, and let C Z^m <= K <= Z^m have
index N^{qN}. If v has independent bit coordinates, each with maximum
atom at most b, then
P( v in K ) <= b^{2 q N / 3}. (23.1)
Proof. Write g_1, ..., g_m for the coordinate images in Z^m / K.
Choose a maximal set of j of these images, say g_{i_1}, ..., g_{i_j},
whose subset sums are all distinct (a dissociated set). Once the other
bits are fixed, at most one assignment of these j bits makes the total
sum zero in the quotient; that assignment has probability at most b^j.
Maximality: for every unselected index i, adding g_i to {g_{i_h}}
breaks dissociativity, so g_i is a {-1, 0, 1} combination of the
selected ones:
g_i = sum_{h = 1}^j M_{h, i} g_{i_h} in Z^m / K,
M_{h, i} in {-1, 0, 1}. (23.2)
Set M_{h, i_h} = delta_{h, (position of i_h)} so that M is a j-by-m
integer matrix with identity columns at the selected indices.
Claim: every column of M C lies in ker(theta), where theta : Z^j ->
Z^m / K is theta(a_1, ..., a_j) = sum_h a_h g_{i_h}.
Check. Let i be any coordinate. (MC) e_i is a j-vector with h-th
component sum_k M_{h, k} C_{k, i}. Then theta((MC) e_i) =
sum_h (sum_k M_{h,k} C_{k,i}) g_{i_h} = sum_k C_{k,i} (sum_h M_{h,k}
g_{i_h}). But sum_h M_{h,k} g_{i_h} = g_k by definition of M (both for
selected and unselected k; use (23.2) for unselected). So theta((MC) e_i)
= sum_k C_{k,i} g_k = q(sum_k C_{k,i} e_k) = q(v_i) where v_i = i-th
column of C. Since C Z^m <= K, q(v_i) = 0. So the i-th column of MC is
in ker(theta). QED.
Rank and norm. Since C is invertible, rank(M C) = rank M = j (M has
identity columns at the selected indices, so rank j). Choose j
independent columns of MC; call their integer span L' <= Z^j. Each such
column has entries bounded by m in absolute value (M contributes {-1, 0,
1}^m times C's bits). Hence each column has norm at most N sqrt(j) <=
sqrt(j) m. Therefore Hadamard gives
det L' <= (N sqrt j)^j <= N^{3j/2}. (23.3)
The quotient map theta is surjective (by (23.2)) with kernel containing
L'. So [Z^j : L'] >= [Z^j : ker theta] = [Z^m : K] = N^{qN}. That is,
N^{qN} <= det L' <= N^{3j/2}. (23.4)
Solving, j >= 2qN/3. Since P(v in K) <= b^j (from dissociativity), we
get P(v in K) <= b^{2qN/3}. If j = 0, the quotient is trivial and the
assertion is P(v in K) <= 1 (empty product). QED.
Heavy retained layers. For one column with pre-test group G, write
Q_hi = sum_{retained (l, j), k_G(l, j) >= R - 1} k_G(l, j) nu_l. (23.5)
Lemma 23.2 (cost of heavy retained layers). Fix 0 < eta < 1, and put
q_min = eta / (100 log N). There is a constant c_p > 0 such that
uniformly for q_min <= q <= 1/2,
P( Q_hi in [q, 2q) | previous exposure )
<= 2^{-c_p q N}. (23.6)
This holds whenever the previous exposure fixes a nonsingular start C
of size in I_N and a quotient map to G whose kernel contains C Z^m,
while leaving the tested bits independent with success probabilities p
or b.
Proof. For a fixed set D of retained layers, the retention lattice
(21.5) together with Lemma 23.1 gives cost 2^{-(2a/3) q(D) N}. Enumerate
the sets consisting of all retained layers of height at least R - 1,
with their total height times weight in [q, 2q).
For primes at most sqrt N, prefix lengths on the eligible plateaus
specify the set. Equation (22.3) costs
O( N^{3/4} (log N)^{3/2} ) = o(N / log N) = o_eta(q N) (23.7)
bits uniformly over the stated range. At larger primes each eligible
layer contributes at least (R - 1) / (2N). There are therefore O(N/R)
eligible layers, and a set of weight below 2q contains at most
O(q N / R) of them. The binomial estimate, or the all-subsets bound
when q is bounded below, gives logarithmic count
O( (q N / R) (1 + log(1/q)) ) = o_eta(q N). (23.8)
Indeed 1 + log(1/q) = O_eta(ell), R ~ ell^2, and qN/R -> infinity
uniformly, so rounding has no effect. Every counted set has q(D) >= q.
Its probability cost absorbs both entropy bounds; for instance any fixed
0 < c_p < 2a/3 works for all sufficiently large N. QED.
SECTION 24. FIXED PATHS AND REMOVAL OF HIGH LAYERS
Now we turn the column estimates into a bound on terminal matrices.
Setup. Let
H_0 = 2 ceil(N^{3/5}), m_* = N - 1. (24.0)
Consider all fixed index paths
I_0 ⊂ I_1 ⊂ ... ⊂ I_{H_0} = [m_*],
h_t = | I_t \ I_{t-1} | in {1, 2}. (24.1)
Fix an ordering of each pair of new indices. At a backward step, there
are at most 2 N^2 choices, so the number of paths is at most
(2 N^2)^{H_0} = 2^{O(N^{3/5} log N)} = 2^{o(N)}. (24.2)
Every node size belongs to I_N, since at most 2 H_0 = o(N^{7/10})
indices are deleted.
Typical set. Let T_m be the set of nonsingular size-m matrices satisfying
Lemma 9.1 (prime corank bound), Proposition 13.1 (static column
estimate), and the simultaneous cube property used in Lemma 22.1 (i.e.
Theorem 12.1). Their exceptional probabilities are uniformly
2^{-omega(N)}. Every fixed principal submatrix remains in the bit model:
its upper-triangular entries are independent with the prescribed biases,
and its mean is a principal submatrix of the original mean, hence has
rank at most two. A union bound using (24.2) shows that the probability
of any nonsingular node on any path failing these requirements is still
2^{-omega(N)}.
Gated paths. For one fixed path, write B_t = B[I_t], and let A be the
event that all its nodes belong to their respective T_{|I_t|} and every
width-two gate holds. Lemma 21.1, applied backwards H_0 times, shows
that every nonsingular terminal matrix outside the exceptional event
belongs to A for at least one fixed path.
Exposure. For the probability estimates, expose a fixed path FORWARDS:
first B_0, then the cross columns and new symmetric block of each
extension. Conditional on everything already exposed, a cross column
has independent entries of the original prescribed biases. The second
cross column of a pair remains independent after the first has been
revealed. Future typicality, nonsingularity and gate requirements
enter only through the event A.
Terminal window. Call the last 5R steps, together with their 5R + 1
nodes, the TERMINAL WINDOW. We first remove paths with a large W_R
anywhere in that window.
Lemma 24.1 (small high-layer tails on the window). For every fixed
0 < eta < 1, each fixed path satisfies
P( A, max_{H_0 - 5R <= t <= H_0} W_R(B_t) > eta )
<= 2^{-Omega_{p, eta}(N R)}. (24.3)
Proof. At each tested column form Q_hi from (23.5), and put
Q-tilde = Q_hi if Q_hi >= q_min, else 0. (24.4)
Set Q-tilde = 0 for every cross column of a step with singular start.
This defines the quantities on the entire exposure space. At
nonsingular starts, Q_hi <= 1/2 by the group-order bound (13.1).
For dyadic values q_j = 2^j q_min <= 1/2, Lemma 23.2 gives, with any
fixed 0 < c'_p < c_p / 2,
E[ 2^{c'_p N Q-tilde} | previous exposure ]
<= 1 + sum_{j : q_j <= 1/2} 2^{2 c'_p N q_j} 2^{-c_p N q_j}
<= 1 + 2^{-Omega_{p, eta}(N / log N)}. (24.5)
The same bound holds at singular starts (where Q-tilde = 0). There are
at most 2 H_0 tested columns. Successive conditioning, including between
columns of a pair, yields
E 2^{c'_p N sum over tests Q-tilde} <= 1 + o(1). (24.6)
On A, suppose a window node has W_R > eta. Iterate (21.6) backwards
from that node, beginning with s = R and increasing s by the width at
each step. Stop once s > N^{3/5}. This takes at most ceil(N^{3/5})
steps; even the earliest window node has H_0 - 5R > ceil(N^{3/5})
predecessors for large N. The final tail vanishes because Lemma 9.1
bounds every layer height by N^{3/5}.
Number these backwards steps by j = 1, 2, ...; at step j, the threshold
in the recursion is R plus the preceding widths, so every charged layer
has height at least s + 1 - h >= R + j - 2 >= R - 1. The contribution
from one column is therefore at most 2 Q_hi / (R + j - 2). There are at
most two columns per step. All contributions with Q_hi < q_min total at
most
4 q_min sum_j 1 / (R + j - 2)
<= 4 q_min (1 + log N) < eta / 2. (24.7)
The remaining contributions must exceed eta / 2. Their denominators are
at least R - 1, and consequently
sum over tests Q-tilde >= (R - 1) eta / 4. (24.8)
This same necessary condition holds for a violation at any window node.
Markov's inequality and (24.6) prove the claim. QED.
END OF PART V. CONTINUES WITH SECTIONS 25+.
SECTION 25. THE TERMINAL WINDOW FORCES TWO CONSTRAINTS
Choose a fixed 0 < eta < min{1, zeta/4}. Lemma 24.1 leaves only windows
where W_R <= eta at every node. On such a window, the deterministic
argument below explains why two full column costs suffice.
Lemma 25.1 (the terminal-window alternative). Consider 5R consecutive
nonsingular principal extensions of widths one or two, satisfying their
gates. Suppose all their nodes have W_R <= eta and the terminal node has
W_2 > zeta. Then for all sufficiently large N, either at least two
distinct steps are costly, or a width-two step starts at a node with
W_2 <= zeta.
Proof. At a noncostly step of width h, the recursion (21.6) gives
W_s(B) <= W_{s+h}(C) + 4 sigma (s >= h). (25.1)
(The "4 sigma" comes from R_i being a union of at most two prefix sums
each bounded by sigma; a width-one step contributes at most 2 sigma,
a width-two step at most 4 sigma.)
Iterate (25.1) from s = 2 backwards over any block of R noncostly steps.
The threshold increases by at least R, so the endpoint satisfies
W_2 <= delta where delta := eta + 4 R sigma. (25.2)
Since sigma = R^{-6} = ell^{-12} and R = ceil(ell^2), we have
4 R sigma = 4 R^{-5} -> 0. Choosing N large enough, delta < zeta.
Also delta < 1 < 4 zeta (for zeta small enough).
Label the window nodes X_0, ..., X_{5R}. There are 5R steps, so 5R-1
"inter-nodal" positions. If there are no costly steps, the last R steps
contradict the terminal value W_2 > zeta (via (25.2)). Suppose there is
exactly one costly step, at position t. There must be fewer than R steps
after it, or (25.2) again applies to the last R steps ending at X_{5R}.
Thus t >= 4R + 1. Both X_{t-2} and X_{t-1} end blocks of R noncostly
steps inside the window, so (25.2) gives:
W_2(X_{t-2}) <= delta, W_2(X_{t-1}) <= delta. (25.3)
Assume for contradiction there is no width-two step whose starting
W_2 is at most zeta (i.e., every width-two step in the window has
starting W_2 > zeta). Then the two steps at positions t-1 and t must
both have width one: if step t-1 had width two, its start would be
X_{t-2} (W_2 <= delta < zeta), contradiction; likewise if step t had
width two, its start X_{t-1} would have W_2 <= delta < zeta,
contradiction.
Applying (25.1) with s = 1 and h = 1 to step t-1:
W_1(X_{t-1}) <= W_2(X_{t-2}) + 4 sigma <= delta + 4 sigma. (25.4)
Even though step t is costly, its width is one, so the height comparison
(21.6) with h = 1 gives
W_2(X_t) <= W_1(X_{t-1}) <= delta + 4 sigma. (25.5)
The remaining steps (positions t+1 through 5R) are noncostly. For either
width, (25.1) with s = 2 (using monotonicity of W_s in s: W_s(B) <=
W_{s-1}(B) since increasing s decreases the tail sample) shows that each
such step increases W_2 by at most 4 sigma. There are fewer than R such
steps, whence
W_2(X_{5R}) <= eta + 4 R sigma + (5R-1) * 4 sigma
<= eta + 24 R sigma
< zeta, (25.6)
contradiction. QED.
SECTION 26. FINISHING THE COLUMN ESTIMATE
Proof of Proposition 8.1 (column estimate). Outside a set of probability
2^{-omega(N)}, every nonsingular terminal matrix belongs to a required
fixed-path event A. By Lemma 24.1 and (24.2), we may also exclude, at
the same scale, all such path events having W_R > eta anywhere in
their windows.
For a fixed remaining path with terminal W_2 > zeta, Lemma 25.1 forces
either two costly positions or a width-two gate with starting
W_2 <= zeta. To make the conditional probability calculation explicit,
let F_t contain all entries exposed through step t. Define D_t to be the
event that the starting matrix is in its typical set and step t is
costly. Its starting-matrix indicator is F_{t-1}-measurable, and
Lemma 22.1 gives
E[ ind_{D_t} | F_{t-1} ] <= p_N. (26.1)
For any two positions r < t, including consecutive ones,
P( D_r ∩ D_t ) = E[ ind_{D_r} E[ ind_{D_t} | F_{t-1} ] ]
<= p_N P(D_r) <= p_N^2. (26.2)
For a specified width-two position, the event of a typical start with
W_2 <= zeta and a satisfied gate likewise has probability at most p_N^2.
These bounds require no conditioning on how a backwards path was
selected or on any future path requirement: we upper-bound by the
stated events after dropping all other conditions.
There are only O(R^2) pairs of positions, or individual gate positions,
in the window. Taking the union over these and all fixed paths gives
P( B nonsingular, W_2(B) > zeta )
<= 2^{-omega(N)} + 2^{o(N)} p_N^2
= 2^{-omega(N)} + 2^{-2 N (a - 2 e_0) + o(N)}. (26.3)
If W_2(B) <= zeta, Proposition 13.1 gives |S_{L_0}(B)| <= 2^{e_0 N},
apart from another typical exception of probability 2^{-omega(N)}. For
all sufficiently large N, the displayed bound and this exception are at
most 2^{-N(2a - 10 e_0)}, as required. QED.
END OF PROOF OF PROPOSITION 8.1.
SECTION 27. THE MAIN THEOREM, PUT TOGETHER
We have now assembled all the pieces. This section closes the loop.
Theorem 1.1 (restated). Fix 0 < p < 1 with p != 1/2. Then, writing
Q = p^2 + b^2 with b = 1-p,
lim_{n -> inf} P(det A_n^(p) = 0)^{1/n} = Q.
Proof.
Lower bound (Section 2). Lemma 2.1 gave P(det A = 0) >= (p^3 + b^3)
Q^{n-2}. Taking n-th roots and letting n -> infinity:
liminf P(det A_n = 0)^{1/n} >= Q.
Upper bound (Sections 4, 5, 6, 7, 8, with the analytical work in
Sections 9-26). Section 4 reduced to corank one (Lemma 4.1). Sections
5-7 set up the anchor congruence and picked a deletion coordinate with
a typical row count. Section 8 combined these with Proposition 8.1 to
show
limsup P(det A_n = 0)^{1/n} <= Q.
Proposition 8.1 is proved in Sections 9-26: Section 9 gave the prime
corank bound, Sections 10-11 the lattice decomposition tools, Section
12 the simultaneous lattice intersection theorem (Theorem 12.1),
Sections 13-15 the layer and pairing/color inputs, Sections 16-19 the
spectral and geometric tools, Section 20 the static column estimate
(Proposition 13.1), and Sections 21-26 the path argument (Propositions
22.1, 23.2, 24.1, 25.1, and finally Proposition 8.1 in Section 26).
Combining upper and lower bounds gives the theorem. QED.
Why the rate is exactly Q (intuition, in one paragraph). Any singular
A has a non-zero kernel vector. Careful reductions force us to consider
the rank-one case with a specific anchor coordinate and deletion
coordinate, and then the "possible deleted bit column" z must lie in
the admissible set S_{L_0}(B) of a bit matrix B. Each such z has
probability about 2^{-n h_*}, and the number of candidates is
typically at most 2^{e_0 n}. The exponent h_* of the deleted column is
strictly larger than d_* := -log_2 Q, so the whole event is
exponentially smaller than Q^n, EXCEPT on a rarer event with two
column constraints (each about 2^{-na}). That rarer event has
probability about 2^{-2 n a}, which is smaller than Q^n by the strict
inequality 2a > d_*. What remains is absorbed by the two-row-collision
event from the lower bound.
The whole proof, in one short paragraph. Two rows of A being identical
gives probability about Q^n and produces the matching lower bound. For
the upper bound, the two "competing rate" events for a singular A are
(a) a rare column of probability about 2^{-n h_*}, which is below Q^n
because h_*>d_*; and (b) two rare column extensions of probability
about 2^{-2 n a}, which is also below Q^n because 2a > d_*. Completing
a nonsingular minor B to a singular matrix with a single deleted column
is exponentially unlikely except for large W_2(B); a path argument
along 5R principal extensions then forces two costly steps, giving
case (b). Sections 9-26 make all of this rigorous.
SECTION 28. REFERENCES
Here we give the references cited above. The present document
reproduces all relevant numbered statements inline; a reader who
prefers the original sources can consult these.
[C] OpenAI, "The sharp exponential rate of singularity for
symmetric Bernoulli matrices", OpenAI Math Release preprint,
October 3, 2026. Available at:
github.com/openai/math/blob/main/preprints/
The-sharp-exponential-rate-of-singularity-for-symmetric-
Bernoulli-matrices-October-3-2026/
[Banaszczyk] W. Banaszczyk, "New bounds in some transference
theorems in the geometry of numbers", Math. Annalen 296
(1993), 625-635.
[Berry] A. C. Berry, "The accuracy of the Gaussian approximation
to the sum of independent variates", Trans. AMS 49 (1941),
122-136.
[Esseen] C.-G. Esseen, "Fourier analysis of distribution functions",
Acta Math. 77 (1945), 1-125.
[Hoeffding] W. Hoeffding, "Probability inequalities for sums of
bounded random variables", JASA 58 (1963), 13-30.
[HoffmanWielandt] A. J. Hoffman and H. W. Wielandt, "The variation
of the spectrum of a normal matrix", Duke Math. J. 20 (1953),
37-39.
[HuSongWu] X. Hu, Z. Song, X. Wu, "Sharp singularity asymptotics
for discrete random matrices", preprint, arXiv:2609.39463,
September 2026.
[JainSahSawhneyDiscrete] V. Jain, A. Sah, M. Sawhney, "Singularity
of discrete random matrices", GAFA 31 (2021), 1160-1218.
[KahnKomlosSzemeredi] J. Kahn, J. Komlos, E. Szemeredi, "On the
probability that a random +-1-matrix is singular", JAMS 8
(1995), 223-240.
[Komlos] J. Komlos, "On the determinant of (0,1) matrices", Studia
Scient. Math. Hungar. 2 (1967), 7-21.
[Miranda] R. Miranda, "Nondegenerate symmetric bilinear forms on
finite abelian 2-groups", Trans. AMS 284 (1984), 535-542.
[ReverseMinkowski] O. Regev and N. Stephens-Davidowitz, "A reverse
Minkowski theorem", Ann. Math. 199 (2024), 1-49. (We cite the
arXiv:1611.05979v6 version's numbering.)
[CamposJenssenMichelenSahasrabudhe] M. Campos, M. Jenssen, M.
Michelen, J. Sahasrabudhe, "The singularity probability of a
random symmetric matrix is exponentially small", JAMS 38
(2025), 179-224.
[CTV] K. P. Costello, T. Tao, V. Vu, "Random symmetric matrices
are almost surely nonsingular", Duke Math. J. 135 (2006), 395-
413.
[FerberJain] A. Ferber and V. Jain, "Singularity of random
symmetric matrices---a combinatorial approach to improved
bounds", Forum Math. Sigma 7 (2019), e22.
[Grayson] D. R. Grayson, "Reduction theory using semistability",
Comment. Math. Helv. 59 (1984), 600-634.
[LitvakTikhomirov] A. E. Litvak and K. E. Tikhomirov, "Singularity
of sparse Bernoulli matrices", Duke Math. J. 171 (2022),
1135-1233.
[Nguyen] H. H. Nguyen, "Inverse Littlewood-Offord problems and the
singularity of random symmetric matrices", Duke Math. J. 161
(2012), 545-586.
[Talagrand] M. Talagrand, "Concentration of measure and
isoperimetric inequalities in product spaces", Publ. Math. IHES
81 (1995), 73-205.
[Tikhomirov] K. Tikhomirov, "Singularity of random Bernoulli
matrices", Ann. Math. 191 (2020), 593-634.
[Tyurin] I. S. Tyurin, "Refinement of the upper bounds of the
constants in Lyapunov's theorem", Russian Math. Surveys 65
(2010), 586-588.
[Vershynin] R. Vershynin, "Invertibility of symmetric random
matrices", Random Structures & Algorithms 44 (2014), 135-182.
[Wigner] E. P. Wigner, "On the distribution of the roots of
certain symmetric matrices", Ann. Math. 67 (1958), 325-327.
That is the whole paper.
END OF FILE.