Fix a real number p with 0 < p < 1 and p not equal to 1/2. Let A be the
symmetric n x n matrix whose entries on and above the diagonal are
independent, equal to +1 with probability p and to -1 with probability
b = 1 - p; entries below the diagonal are forced by A_{ji} = A_{ij}. The
assumption p < 1/2 is no loss of generality: multiplying A by -1
exchanges p and 1 - p and preserves singularity, so every constant
below is computed with b = 1 - p > 1/2 the larger atom.
Throughout, log is natural and log_2 is base two. Write
Q = p^2 + b^2 (agreement probability of two biased signs)
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 (entropy of one biased sign)
Both b and Q lie in (0,1). Two strict inequalities drive the whole
argument:
(I1) 2a > d_*
(I2) h_* > d_*
(I1) holds because b^2 < Q. (I2) is the strict convexity of the map
x -> -log_2 x evaluated at the unequal pair (p, b).
MAIN THEOREM. As n tends to infinity,
P(det A = 0) = (Q + o(1))^n.
The lower bound is the event that rows 1 and 2 of A agree. That event
forces det A = 0, and its probability is (p^3 + b^3) Q^{n-2}, so
P(det A = 0) >= (p^3 + b^3) Q^{-2} * Q^n = (Q + o(1))^n.
For independent 0/1 matrices, Komlos 1967 proved asymptotic
nonsingularity, and Kahn, Komlos and Szemeredi 1995 obtained the first
exponential decay for independent signs. In the independent-row models
Tikhomirov 2020 identified the sharp rate (1/2 + o(1))^n for
Bernoulli entries, and Jain, Sah and Sawhney 2021 extended that rate
to every fixed distribution. Symmetric matrices have dependent rows,
so none of those arguments applies directly. Costello, Tao and Vu 2006
proved asymptotic nonsingularity; Nguyen 2012, Vershynin 2014, and
Ferber-Jain 2019 improved the exponential bound; and Campos, Jenssen,
Michelen and Sahasrabudhe 2025 proved that the singularity
probability of a symmetric Bernoulli matrix is exponentially small.
Litvak and Tikhomirov 2022 handled sparse Bernoulli matrices via
inverse Littlewood-Offord methods that extend to any fixed bias, and
Hu, Song and Wu 2026 sharpened the independent-row case to the exact
asymptotic (2 + o(1)) n^2 2^{-n}. The biased-symmetric case below
is the next step of that programme.
./kahn-komlos-szemeredi-1995-1260107-2-random-pm1-singular.pdf
./costello-tao-vu-2006-13527-5-symmetric-nonsingular.pdf
./tikhomirov-2020-1812.09016-singularity-bernoulli.pdf
./jain-sah-sawhney-2021-2010.06554-singularity-discrete.pdf
./vershynin-2014-1102.0300-invertibility-symmetric.pdf
./nguyen-2012-1101.3074-inverse-littlewood-offord.pdf
./ferber-jain-2019-1809.04718-symmetric-combinatorial.pdf
./campos-jenssen-michelen-sahasrabudhe-2025-2105.11384-singularity-probability.pdf
./litvak-tikhomirov-2022-2004.03131-sparse-bernoulli.pdf
./hu-song-wu-2026-2609.39463-sharp-singularity.pdf
The nearest result, quoted verbatim to fix the target shape. Campos,
Jenssen, Michelen and Sahasrabudhe write:
Let A be drawn uniformly at random from the set of all n x n
symmetric matrices with entries in {-1, 1}. We show that
P(det(A) = 0) <= e^{-cn}.
The proof below reproduces that exponential shape for every fixed
bias, with Q = p^2 + b^2 in place of 1/2.
The route to the upper bound. A singular A has a nonzero kernel
vector v. Normalize by an anchor a_0 of largest absolute value,
rescale so the tail has unit norm, and reduce by elementary moves to
a symmetric bit matrix M with the same nullity. Deleting one chosen
coordinate of M yields a nonsingular principal minor B whose omitted
column z lies in a set S_{L_0}(B) of bit vectors satisfying a
quadratic congruence and a norm bound, defined fully below. Two
estimates close the upper bound: |S_{L_0}(B)| is at most 2^{e_0 n}
outside an event of probability 2^{-n(2a - 10 e_0)}, and each
compatible column costs close to 2^{-n h_*}. Both bounds leave a
strict margin below Q^n by (I1) and (I2).
CORANK REDUCTION LEMMA. For every fixed p,
P(det A = 0) <= 2^{o(n)} P(rank A = n - 1) + 2^{-Omega(n^{6/5})}.
Proof, two steps.
STEP 1. HIGH CO-RANK IS RARE. A symmetric matrix of rank r has a
nonsingular r x r principal submatrix: writing A = X S X^T with
X of size n x r, rank r, and S nonsingular, pick r independent rows
of X. The principal r x r submatrix of A on those rows is Y S Y^T
with Y invertible. Fix such a set J of size r. Reveal the r x r block on J
and the r x (n - r) cross block. When rank A = r, Schur
complementation forces every entry of the residual (n - r) x (n - r)
block, and there are exactly (n - r)(n - r + 1)/2 of these, each a
prescribed sign with conditional probability at most b. With
t = ceil(n^{3/5}) and b < 1,
P(n - rank A >= t) <= sum_{k=t}^n binom(n, k) b^{k(k+1)/2}
<= 2^n b^{t(t+1)/2}
<= 2^{-Omega(n^{6/5})}.
STEP 2. CORANK ONE SUFFICES. Suppose rank A = n - k with
1 <= k < t. Let K = ker A and choose a set I of k - 1 coordinates
such that x -> x_I is onto R^I on K. Let D_I(A) negate the i-th
diagonal of A for each i in I, so A + D_I(A) flips those diagonal
signs and is otherwise unchanged.
CLAIM. ker(A + D_I(A)) = {y in K : y_I = 0}, hence of dimension 1
since dim K = k and |I| = k - 1.
If (A + D_I(A)) y = 0, then for x in K,
0 = y^T (A + D_I(A)) x = (D_I(A) y)^T x, since A x = 0. As x_I
spans R^I over x in K and every diagonal of D_I(A) on I is +-2,
this forces y_I = 0, whence D_I(A) y = 0 and y in K. Conversely,
y in K with y_I = 0 gives D_I(A) y = 0 and (A + D_I(A)) y = 0.
MEASURE PRESERVATION. For any fixed I, A -> A + D_I(A) bijects the
symmetric sign matrices and preserves the law of A, since each
flipped diagonal is sign-symmetric about zero under any bias. So
for any such set S, sum_{A in S} P(A) = sum_{A in S} P(A + D_I(A)).
COUNTING. For A of rank n - k with 1 <= k < t, take I(A) to be the
lexicographically least good set of size k - 1. Then
P(rank A = n - k)
= sum_{|I| = k-1} sum_{A : I(A) = I} P(A)
<= sum_{|I| = k-1} P(rank A = n - 1),
because the map A -> A + D_I(A) sends {A : I(A) = I} into the set
{rank = n - 1}. Summing over k in [1, t - 1],
sum_{k=1}^{t-1} P(rank A = n - k)
<= t binom(n, t) P(rank A = n - 1)
<= 2^{O(t log n)} P(rank A = n - 1)
= 2^{o(n)} P(rank A = n - 1),
because t log n = O(n^{3/5} log n) = o(n). Combining the two steps
gives the lemma.
NEAR-SPARSE KERNEL TAILS ARE RARE. Fix epsilon > 0 small. Let v be a
nonzero kernel vector of A, let a_0 be a coordinate of largest absolute
value, and after rescaling assume the tail (v_j : j != a_0) has unit
norm. From A v = 0 read at row a_0,
|v_{a_0}| = |sum_{j != a_0} A_{a_0 j} v_j| <= sqrt(n - 1),
by Cauchy-Schwarz. Since the tail has unit norm and |v_{a_0}| is the
largest coordinate, 1/sqrt(n-1) <= |v_{a_0}| <= sqrt(n-1).
COMPRESSIBLE TAILS LEMMA. For every epsilon > 0 there exist fixed
lambda, delta in (0, 1/4) such that, for all sufficiently large n,
P(A has a kernel vector with normalized tail within delta of
some vector supported on at most lambda n coordinates)
<= 2^{(-d_* + epsilon) n}.
Proof. Put mu = 2p - 1 and W = A - mu J, J the all-ones matrix. A 3^n
net on the unit sphere plus Hoeffding's inequality for quadratic forms
of bounded independent signs gives, for a fixed L > 0 depending on p,
P(||W||_op > L sqrt(n)) <= 2 9^{n} exp(-c L n) <= 2^{-4n}.
The rank-one deviation mu J has operator norm at most n.
On ||W||_op <= L sqrt(n), a bad kernel vector v has a support T of
size |T| <= lambda n with ||v_{T^c \ {a_0}}||_2 <= delta. Net
the unit ball of R^T at scale delta (size at most (C/delta)^{lambda n})
and v_{a_0} in [-sqrt(n), sqrt(n)] at scale delta (size at most
O(sqrt(n)/delta)). For some net point (x, u),
||W x + mu u 1||_2 <= C_1 L delta sqrt(n). (*)
For a fixed pair (x, u) and any row i outside S = T + {a_0}, the i-th
coordinate of (*) is a linear expression in the independent signs
W_{i j} for j in S, plus a shift mu u. Two cases.
Case A. Some |x_j| >= u_0 > 0 for j in T, so |x_{a_0}| >= u_0/2 for
delta small enough. Condition on every W_{i j} in row i except
W_{i j} and W_{i a_0}. For w = u_0/4, the interval of radius w around
mu u holds at most two admissible vertices of the two-bit square,
opposite if two. Total probability at most
max(b^2, p^2, 2 p b, p^2 + b^2) = Q.
Case B. Every |x_j| < u_0 for j in T. The centered sum
Y = sum_{j in T} W_{i j} x_j has variance
sigma^2 = 4 p b sum_j x_j^2 >= c_p > 0, and third absolute centered
moments sum to at most C_p u_0 sum_j x_j^2. The Berry-Esseen
inequality (Berry 1941, Esseen 1945), in Tyurin's unequal-summand
form (Tyurin 2010, Russian Math. Surveys 65, 586), bounds the
Kolmogorov distance to the centered normal law by C_p u_0. Thus
P(Y + mu u in any interval of radius w) <= C_p (w + u_0). Choose
u_0 small, w small, then delta small, in that order, to force this
below Q.
./berry-1941-0003498-3-gaussian-approximation.pdf
Thus fixed w = w(p), delta_0 = delta_0(p) exist such that every pair
(x, u) with delta < delta_0 and every row i outside S satisfies
P(|(W x)_i + mu u| <= w) <= Q, call this (**). Rows i outside S use
disjoint entries, so (**) across i is independent. Provided
C_1^2 L^2 delta^2 / w^2 < gamma, inequality (*) permits at most
gamma n of the n - |S| - 1 tests outside S to fail, so
P((*) holds for fixed (x, u))
<= (sum_{i <= gamma n} binom(n, i)) Q^{n - |S| - 1 - gamma n}.
Union over the n anchors, the at most sum_{k <= lambda n} binom(n,k)
supports T, and the at most 3^n (C/delta)^{lambda n} O(sqrt(n)/delta)
net points gives total base-two log-probability at most
-d_* n + [d_*(lambda + gamma) + H_2(gamma) + H_2(lambda)
+ lambda log_2(C/delta) + o(1)] n,
where H_2(t) = -t log_2 t - (1 - t) log_2(1 - t) is the binary
entropy. With gamma, then delta, then lambda chosen small in that
order, the bracket is below epsilon/2, and adding the 2^{-4n} from
||W||_op closes the proof.
ROW COUNTS. For every fixed rho, w > 0, with probability
1 - exp(-Omega_{rho, w}(n^2)), fewer than rho n rows of A have their
number of +1 entries outside [pn - wn, pn + wn].
If rho n rows fail, at least half fail in the same direction. Fix
k = ceil(rho n / 3) such rows; the sum of their +1 counts is a sum of
independent upper-triangular indicators, with mean pk n and
coefficient-squared sum at most 2 k n. Hoeffding 1963 gives deviation
at least k w n probability at most 2 exp(-Omega_{rho, w}(n^2)), and
there are at most 2^n possible index sets plus two directions.
NON-COMPRESSIBLE TAILS. Fix delta, lambda from the compressible-tails
lemma for a given epsilon, and pick a fixed c with 0 < c < delta. If v
is a kernel vector whose normalized tail is not within delta of a
lambda n-supported vector, then at least lambda n / 2 coordinates of
the tail satisfy |v_i| >= c / sqrt(n). Otherwise, truncation to those
coordinates would have support size at most lambda n and would lie
within distance c < delta of the tail, a contradiction.
Apply row counts with rho = lambda/4 and any fixed w_1 > 0. Except on
a set of probability exp(-Omega(n^2)), some one of these lambda n / 2
coordinates has its original sign column with +1 count in
[pn - w_1 n, pn + w_1 n]. Fix such a coordinate i and call it the
deletion index.
ANCHOR CONGRUENCE. Fix anchor a_0 and condition on its entire row.
Then there exists a symmetric bit matrix M of size N = n - 1 with
entries on and above the diagonal independent, each with success
probability p or b (independently of the anchor row), such that
(i) the mean E M and every principal submatrix of E M has rank
at most two, and
(ii) dim ker M = dim ker A, and whenever a_0 is the anchor of a
kernel vector v of A, some signed copy of the normalized tail
of v lies in ker M as a unit vector.
Proof. Relabel so a_0 = 1 and put t = A_{11} in {+-1} and
u_j = A_{1 j} for j > 1. Let D = diag(1, t u_2, ..., t u_n). The
matrix t D A D has first row and column all equal to one. Its lower
principal block is
C_{i j} = t u_i u_j A_{i j} (2 <= i, j <= n).
Its Schur complement at the leading 1 is C - 1 1^T, and
C - 1 1^T = -2 M, M_{i j} = (1 - t u_i u_j A_{i j}) / 2.
For each pair (i, j), the product t u_i u_j is a fixed sign once the
anchor row is known. Then M_{i j} = 0 if t u_i u_j A_{i j} = +1, and
M_{i j} = 1 if the product equals -1. As A_{i j} takes +1 with
probability p and -1 with probability b, M_{i j} is a single bit
with probabilities p or b. Different pairs (i, j) use disjoint
upper-triangular entries of A, so the bits of M are independent.
For the mean, with mu = 2 p - 1,
E M = (1/2) 1 1^T - (mu t / 2) u u^T,
which is a sum of two rank-one Hermitian matrices and hence of rank at
most two; every principal submatrix of E M has the same form with u
restricted to the principal coordinates, so the rank bound persists.
Multiplication by the diagonal matrix t D, which is invertible,
preserves nullity, and the Schur complement of the invertible first
entry 1 preserves nullity as well. Consequently dim ker M = dim ker A.
Reading the diagram D A D (v_{1 : n}) = 0 columnwise, one obtains
ker(M) as the image of the normalized tail under a fixed sign change:
the lower block of t D A D applied to the tail, completed with the
anchor row, vanishes exactly when the tail lies in ker of the
(1 1^T - C)-related bit matrix M. The exact statement is:
the vector w = (t u_2 v_2, ..., t u_n v_n) lies in ker M.
ADMISSIBLE COLUMNS. For a fixed L_0 >= 1 and a nonsingular bit matrix
B of size m, define
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) },
where N is a reference dimension and m runs over a range
I_N = { m : N - N^{7/10} <= m <= N }. The quadratic condition is
exactly the Schur-complement condition for a bit diagonal to
complete B to a singular matrix: if z^T B^{-1} z = d in {0, 1} for a
bit vector z, then M = [[B, z], [z^T, d]] is a singular bit matrix.
DELETION COORDINATE. Continue from the anchor congruence. Suppose
A has corank one and v spans ker A with anchor a_0. Apply the anchor
congruence to obtain M of size N = n - 1 with tail w = (t u_2
v_2, ..., t u_n v_n) in ker M. The tail has unit norm and some
coordinate i satisfies |w_i| >= c / sqrt(n), where c is the fixed
constant from the row-count step.
Deleting the i-th coordinate of M produces a principal submatrix B of
size m = N - 1. The adjugate of a symmetric corank-one matrix is a
nonzero scalar multiple of the outer product w w^T, so B is
nonsingular. Write, after permuting the deleted coordinate to the
end,
M = [[ B, z ],
[ z^T, d ]]
with B nonsingular, z in {0,1}^m the omitted column, and d in {0,1}
the omitted diagonal entry. The kernel equation M w = 0, restricted
to the first m coordinates and to the last coordinate, gives
B w_{[N] \ {i}} + z w_i = 0,
z^T w_{[N] \ {i}} + d w_i = 0.
The first equation is
B^{-1} z = - w_{[N] \ {i}} / w_i,
so || B^{-1} z ||_2 = || w_{[N] \ {i}} ||_2 / | w_i | <= 1 / (c / sqrt(n))
= sqrt(n) / c. For fixed L_0 >= 2 / c and all sufficiently large n,
this is at most L_0 sqrt(N).
Substituting the first equation into the second,
z^T (-B^{-1} z * w_i) + d w_i = 0,
and dividing by the nonzero w_i gives
z^T B^{-1} z = d in {0, 1}.
Similarly, Schur complementation of [[B, z], [z^T, d]] at B gives
det(det B) * (d - z^T B^{-1} z) = det M = 0, an independent
confirmation. Hence z lies in S_{L_0}(B) with L_0 = max(1, 2 / c).
POINT PROBABILITY OF A COMPATIBLE COLUMN. Conditional on the anchor
row and on B, the column of the original biased sign matrix
corresponding to z involves m independent original signs, of which r
are +1 and m - r are -1. By the row-count step, the deletion
coordinate i has its original sign column count in
[pn - w_1 n, pn + w_1 n], so
| r - p (n - 1) | <= w_1 n + 2,
where the "+ 2" accounts for the deleted diagonal and anchor entries.
The point probability of that column is
p^r b^{m - r} = 2^{-(m h_* + (r - pm) log_2(b/p))},
and by the bound on |r - p (n - 1)|, for every fixed w_1 there is a
constant C_p such that
p^r b^{m - r} <= 2^{- n (h_* - C_p w_1 - o(1))}.
That is the cost of any single compatible column.
BIT MODEL AND COLUMN ESTIMATE. Let N be a reference dimension and
I_N = { m in Z : N - N^{7/10} <= m <= N }. A bit matrix B of size
m in I_N is a symmetric matrix whose entries on and above the
diagonal are independent bits, each with success probability in
{p, b}, with E B of rank at most two and every principal submatrix
of E B of the same form. The anchor-congruence construction produces
such a B; conversely every such array of probabilities arises from
some anchor row of A.
COLUMN ESTIMATE. Fix L_0 >= 1 and e_0 > 0 small. For B in the bit
model,
P(B nonsingular and |S_{L_0}(B)| > 2^{e_0 N})
<= 2^{-N (2 a - 10 e_0)}.
The estimate is proven by a path-of-principal-minors argument that
forces two independent column constraints when |S_{L_0}(B)| is
large; the two-constraint cost is about 2^{-2 N a}, cheaper than the
target by (I1).
UPPER BOUND ASSUMING THE COLUMN ESTIMATE. Fix epsilon > 0 small.
Choose lambda, delta from the compressible-tails lemma applied with
epsilon/4 in place of epsilon, so the near-sparse-tail contribution
is at most 2^{(-d_* + epsilon/4) n}. Choose c in (0, delta) and set
L_0 = max(1, 2 / c). Choose e_0, w_1 > 0 small enough that
2 a - 10 e_0 > d_*, h_* - e_0 - C_p w_1 > d_*,
both possible by (I1), (I2) and continuity.
For any singular A with corank exactly one and non-compressible
kernel, the anchor congruence and the deletion-coordinate step
produce a pair (a_0, i) of anchor and deletion coordinates, a
nonsingular principal minor B of a bit matrix M in the bit model,
and a compatible column z in S_{L_0}(B). Conditional on the anchor
row and on B, the probability that a specific z is the omitted
column is at most 2^{-N(h_* - C_p w_1 - o(1))}. Hence
P(corank one with non-compressible tail)
<= n^2 * E[ |S_{L_0}(B)| ] * 2^{-N(h_* - C_p w_1 - o(1))}.
Split the expectation by the column estimate. On |S_{L_0}(B)| <=
2^{e_0 N} the product is at most 2^{-N (h_* - e_0 - C_p w_1 - o(1))};
on the exceptional event, with |S_{L_0}(B)| <= 2^N by the trivial
bound, it is at most 2^{-N (2 a - 10 e_0)}. Therefore
P(corank one with non-compressible tail)
<= n^2 ( 2^{-N (h_* - e_0 - C_p w_1 - o(1))}
+ 2^{-N (2 a - 10 e_0)} )
<= n^2 2^{-N (d_* + delta_*)},
where delta_* = min(h_* - e_0 - C_p w_1, 2 a - 10 e_0) - d_* > 0 is
a constant depending only on p (and the fixed choices). Adding the
near-sparse-tail contribution 2^{(-d_* + epsilon/4) n}, the corank
reduction 2^{-Omega(n^{6/5})}, and the n^2 = 2^{o(n)} overhead gives
P(det A = 0) <= 2^{-n (d_* - epsilon)}
for all sufficiently large n. Since epsilon is arbitrary,
limsup (1/n) log_2 P(det A = 0) <= -d_* = log_2 Q.
Combined with the lower bound 2^{-n d_*} (1 - o(1)), the main
theorem follows.
FINITE-FIELD CORANK BOUND. Let A be a symmetric d x d matrix over a
field F whose upper-triangular entries are independent with largest
atom at most beta, and let H be a fixed symmetric matrix over F. For
1 <= k <= d,
P(corank_F(A + H) >= k) <= 2^d beta^{k(k+1)/2}.
Proof. Every symmetric d x d matrix of rank r has a nonsingular r x r
principal submatrix, over any field (including characteristic two):
writing it as Y C Y^T with Y of size d x r of rank r and C symmetric
nonsingular, choose r independent rows of Y. If corank(A + H) >= k,
then rank(A + H) = r <= d - k for some r, and A + H has a nonsingular
r x r principal block. Fix such a block J. Reveal the r x r block and
the r x (d - r) cross block. When rank(A + H) = r, Schur
complementation forces the (d - r) x (d - r) principal block, of which
(d - r)(d - r + 1)/2 entries are independent, each a prescribed value
with conditional probability at most beta. Summing over the
binom(d, k) choices of indices and over r < d - k + 1 bounds the
corank probability by 2^d beta^{k(k+1)/2}.
PRIME CORANK LEMMA. 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,
except on an event of probability 2^{-Omega_p(N^{6/5})}.
Proof. Fix a prime q. The two values 0 and 1 remain distinct in F_q,
and reduction modulo q preserves the atom bound max(p, b) = b for
0 < p < 1/2. Apply the finite-field corank bound with
H = 0 and 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})}.
Union over primes. Suppose B is nonsingular over R and q divides
det B. Then corank_{F_q}(B mod q) > 0. By Hadamard's inequality,
|det B| <= m^{m/2} <= N^{N/2}, so the relevant primes are all of
size at most N^{N/2}, and there are at most N^{N/2} of them. A union
bound over such primes costs 2^{O(N log N)}, which is negligible in
comparison with 2^{-Omega_p(N^{6/5})}.
GENERATOR COUNT. The finite abelian group G_B = Z^m / B Z^m
satisfies dim_{F_q}(G_B / q G_B) = corank_{F_q}(B mod q) for every
prime q, so its minimal generator count max_q dim_{F_q}(G_B / qG_B)
is at most ceil(N^{3/5}).
LATTICE TOOLKIT. A lattice L in R^d is a discrete subgroup of its
span, and det L is its Euclidean covolume in the span, det L = 1 for
the rank-zero lattice, and [L : M] = det M / det L for nested
full-rank lattices M <= L. A subspace F of R^m is rational if it has
an integer-vector basis; its height is H(F) = det(F intersect Z^m).
MINKOWSKI-REVERSE COUNT. Let L be a lattice of rank j >= 1 satisfying
det M >= T^{rank M} for every sublattice M <= L. Set
s_0 = T / (10 (log j + 2)). Then, for every R > 0,
#{ x in L : ||x||_2 <= R } <= (3/2) exp(pi R^2 / s_0^2).
For T = (log N)^4, j <= N and R = sqrt(N), this bound is
2^{O(N / (log N)^6)} = 2^{o(N)}. The bound also holds in rank zero,
where the count is exactly one. This is the Reverse Minkowski
Theorem of Regev and Stephens-Davidowitz 2024, Annals of
Mathematics 199, 1-49, Theorem 1.2.
./regev-stephensdavidowitz-2024-1611.05979-reverse-minkowski.pdf
LOW-HEIGHT COVER. Fix D, P > 0. For every sufficiently large N and
every m <= N there exists a finite list C_{m, N} of rational
subspaces of R^m, of size at most 2^{N^2 ell^{-P}} with
ell = log log N, depending only on m, N, D, P, such that every
rational F <= R^m with H(F) <= exp(N ell^D) is within rank distance
N ell^{-P} of some member of C_{m, N}, where distance is the
Euclidean distance between subspaces.
DETERMINANT MINIMIZER. For any lattice L and any T > 0, the
normalised determinant det M / T^{rank M}, over sublattices M of L
(the zero sublattice allowed, with the value 1), attains its minimum
at a primitive sublattice L_min. This sublattice satisfies
det L_min <= T^{rank L_min},
det M >= T^{rank M} for every sublattice M <= L / L_min.
Extremal sublattice constructions of this kind occur in Grayson's
reduction theory of Euclidean lattices (Grayson 1984, Comment. Math.
Helv. 59, 600-634, Section 1).
ROBUST EXTRACTION AND IMAGE LATTICE. Call a finite set V subset R^m
rho-robust on its affine span F if every codimension-t affine
subspace of F meets V in at most 2^{-rho t} |V| points. For any
nonempty A subset {0, 1}^m and any rho > 0, there is an affine
subspace E such that V = A intersect E is rho-robust on its affine span and
log_2 |V| >= log_2 |A| - rho m.
Further, if Phi : F -> R^d is injective rational affine and
||Phi(v) - Phi(w)||_2 <= C_0 sqrt(N) for every pair v, w in V with
V rho-robust, rho = ell^{-D}, m <= N, then the integer span of
image differences is a rank-r lattice of covolume at most
exp(O_{D, C_0}(N ell)), and H(span(V - V)) <= exp(O_D(N ell)).
PAIRING-IMAGE-AND-DETERMINANT. Let L be a lattice spanning a
Euclidean space V, and let q be a symmetric bilinear form with
q(L, L) <= Q. Put
K = L intersect rad q, S = V intersect (rad q)^perp.
If the image of the map L -> Hom(L, Q/Z) sending x to q(x, .) mod Z
has order t, then
|det_orth(q|_S)| >= (det K)^2 / (t (det L)^2),
where the determinant on the left is taken in an orthonormal basis
of S.
SIMULTANEOUS LATTICE INTERSECTION. Fix D > 0 and 0 < alpha < 1, and
put tau = ell^{-D}. Typically a nonsingular bit matrix B of size m in
I_N satisfies the following: for every lattice K with
B Z^m <= K <= Z^m, [Z^m : K] >= N^{tau N}, (*)
and every x in R^m,
| (x + K) intersect {0, 1}^m | < 2^{alpha N}.
The exceptional probability 2^{-omega(N)} is uniform in the bit
model. The conclusion is simultaneous in K: it holds for all such K
at once, since K may be chosen after B is observed.
PROOF, DETERMINISTIC SETUP. Assume B is nonsingular and satisfies the
prime corank lemma. Suppose some lattice K satisfying (*) has a coset
x + K with at least 2^{alpha N} cube points.
Apply the determinant minimizer to K with T = (log N)^4, obtaining a
primitive L_min <= K. Fix
F = span L_min, E = F^perp,
Lambda = pi_E(K), Pi = pi_E(Z^m),
where pi_E is orthogonal projection to E. Orthogonal covolume
factorization of K across F and E, and det K >= 1 in the integral
lattice K, give the two bounds
H(F) <= det L_min <= e^{4 N ell},
det Lambda >= N^{tau N} e^{-4 N ell}.
Since H(F) <= exp(N ell^2), the height cover yields a rational V
from the fixed list C_{m, N} with rank distance d(F, V) <= N ell^{-P}.
Put U = V^perp, so d(E, U) <= N ell^{-P} by orthocomplement invariance.
Set W_0 = E intersect U, a subspace of codimension r <= N ell^{-P}
in E with dim U <= (1 - alpha/3) N.
LARGE FIBER. Differences of points in the same coset lie in K with
norm at most sqrt(N). Reverse Minkowski rank-count on Lambda bounds
the number of distinct projections to Lambda by 2^{o(N)}. Fix a fiber
with at least 2^{alpha N - o(N)} cube points. Projection onto dim F
independent coordinate functionals is injective on F, so such a coset
meets {0,1}^m in at most 2^{dim F} points, forcing
dim F >= alpha N / 2,
for all sufficiently large N.
PROJECTED SCALE. Decompose E orthogonally as W_0 (+) W_0^perp with
codim_E W_0 = r <= N ell^{-P}. Fix C > D + 5 and define S : E -> E
to equal N^{-C-5} on W_0 and N on W_0^perp. The two scales provide
the covolume comparison across W_0.
ORDER OF THE MULTIPLIED QUOTIENT. The group Pi / Lambda is a quotient
of G_B = Z^m / B Z^m, so has at most g_N = ceil(N^{3/5}) generators.
Its order is |Pi / Lambda| = det Lambda * H(F) >= det Lambda
>= N^{tau N} e^{-4 N ell}, since det Pi = H(F)^{-1} and H(F) >= 1.
Multiplication by u has kernel of size at most |u|^{g_N} on any
g_N-generator group, and |u|^{g_N} <= N^{C g_N} = 2^{o(tau N)} for
|u| <= N^C, so
| u (Pi / Lambda) | >= N^{tau N - o(tau N)} (order)
uniformly for 1 <= |u| <= N^C.
SEPARATED SUBSETS LEMMA. Fix an absolute constant R_0 >= 100. For
every integer u with 1 <= |u| <= N^C there is a set I_u subset [m] of
size at least c_1 tau N, with c_1 > 0 absolute, such that the subset
sums of { u S pi_E e_i : i in I_u } are pairwise separated by more
than R_0 sqrt(N) modulo S Lambda.
Proof. Fix u. Choose a maximal set of indices i_1, ..., i_j such that
their subset sums are R_0 sqrt(N)-separated modulo S Lambda. Adding
any unselected index i creates a pair of subset sums at distance at
most R_0 sqrt(N) modulo S Lambda, with i occurring in exactly one
member; undoing S gives, for every i in [m],
u pi_E e_i == sum_{h = 1}^j a_{h i} u pi_E e_{i_h} + eps_i (mod Lambda),
with a_{h i} in {-1, 0, 1} and || S eps_i ||_2 <= R_0 sqrt(N). For
selected indices the representation is exact: coefficient column the
standard basis vector e_h, zero error.
Let M be the j x m integer matrix of coefficients a_{h i}, with
identity columns at the selected indices, and let t = dim span of the
{eps_i}. Choose t independent of these errors; their covolume in E is
at least H(F)^{-1}, since they belong to Pi and Pi has covolume
H(F)^{-1} there. On every t-dimensional subspace, S expands volume by
at least N^{2 t - (C + 7) r}, because at most r of the S-scales are
the small N^{-C-5} value. Hadamard's inequality applied to the
S-scaled errors gives
H(F)^{-1} N^{2 t - (C + 7) r} <= (R_0 sqrt(N))^{t}.
Using det Lambda >= N^{tau N} e^{-4 N ell} and r <= N ell^{-P},
t = O_C( r + N ell / log N ) = o(tau N). (rank t)
CLOSING THE SEPARATED SUBSETS. Let theta : Z^j (+) Pi -> Pi/Lambda be
theta(a, v) = sum_{h = 1}^j a_h u pi_E e_{i_h} + v (mod Lambda). By
the exact-representation step, theta(M e_i) = u pi_E e_i for every i,
so theta(MZ^m) is exactly u(Pi/Lambda) and
|u(Pi/Lambda)| <= [MZ^m : ker theta]. On the other hand,
theta(M B e_i) = u pi_E(B e_i), which vanishes since B Z^m <= K
implies pi_E B e_i in Lambda. The coefficient part of MB is
M_0 B with M_0 the j x m coefficients, of rank j (M_0 has j
identity columns and B is nonsingular). Choose j columns of MB
whose coefficient parts are independent; let L' be their integer
span. Standard index bookkeeping in the lattice Z^j (+) Pi gives
|u(Pi/Lambda)| <= [MZ^m : L'] <= det L' / det(MZ^m).
Each column of MB has coefficient part at most N and E-part at most
R_0 N^{C+5} sqrt(N), so its norm is at most N^{C+6}. Hadamard bounds
det L' <= (N^{C+6})^j. On the other side, the chosen independent
eps_i sit inside Pi of covolume H(F)^{-1}, so det(MZ^m) >= H(F)^{-1}.
Combining,
N^{tau N - o(tau N)} <= H(F) N^{(C + 6) j}.
Since H(F) <= e^{4 N ell} = N^{o(N)},
j >= c_1 tau N, c_1 = 1 / (2 (C + 6)),
which is the separated-subsets conclusion.
DUAL FOURIER AVERAGE LEMMA. Write phi(t) = b + p e^{2 pi i t}. 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},
where y is sampled from the dual lattice Lambda^* with density
proportional to exp(-pi ||S^{-1} y||^2).
Proof. Let X = xi - xi' with xi, xi' independent Bernoulli p vectors
on J, extended by zero outside J. Expanding the product 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),
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 lies in [0, 1]: positivity is clear, and the Gaussian
translate inequality (Banaszczyk 1993, Math. Ann. 296, 625-635)
bounds the numerator by the denominator. Discarding the phases
e^{2 pi i sum s_i X_i} bounds the original expectation by E_X f(uX).
Two cases.
If dist(u S pi_E X, S Lambda) >= (R_0/3) sqrt(N), retaining half of
each Gaussian exponent in the numerator gives
f(u X) <= e^{-pi R_0^2 N / 18} 2^{dim E / 2} <= e^{-c_4 N}
for absolute c_4 > 0.
If dist(u S pi_E X, S Lambda) < (R_0/3) sqrt(N), condition on xi'
and on all coordinates xi_i for i outside J intersect I_u. By the
separated-subsets lemma, at most one value of the remaining bits
satisfies the distance bound: otherwise two such sums would be at
mutual distance at most (2 R_0 / 3) sqrt(N), contradicting R_0
separation. Any single bit pattern has probability at most
b^{|J intersect I_u|} <= b^{c_2 tau N}. Combining and decreasing c_3 gives
the lemma.
MULTI-TESTERS. Fix kappa > 0 small and c_5 > 0 small. Set
k = floor( kappa tau N / log N ).
There exist y^1, ..., y^k in Lambda^* with
||y^g||_2 <= R_0 N^2 sqrt(N),
dist(y^g, U) <= R_0 N^{-C-5} sqrt(N),
prod_{i in J} |phi(sum_{g=1}^k w_g y_i^g)| <= e^{-c_5 tau N}
for every w in Z^k with 1 <= ||w||_inf <= N^C.
Proof. Sample the k vectors independently from the dual Gaussian with
density proportional to exp(-pi ||S^{-1} y||^2) on Lambda^*. On
S^{-1} Lambda^* the Gaussian scale estimate gives, for R_0 fixed,
P(||S^{-1} y^g||_2 > R_0 sqrt(N)) <= 2^{dim E / 2}
exp(-pi R_0^2 N / 2).
Outside this event, the two scales of S show ||y^g_{W_0}||_2
<= R_0 N^{-C-5} sqrt(N) and ||y^g_{W_0^perp}||_2 <= R_0 N sqrt(N).
Together, ||y^g||_2 <= R_0 N^2 sqrt(N), and since E and U differ by
rank distance N ell^{-P} the W_0-component bounds the perpendicular
component of y^g relative to U, giving dist(y^g, U)
<= R_0 N^{-C-5} sqrt(N).
For a fixed nonzero w in range, condition on all vectors except one
y^g with w_g != 0. Writing s_i = sum_{g' != g} w_{g'} y_i^{g'}, the
dual Fourier average lemma applied with u = w_g (in
1 <= |u| <= N^C) bounds the conditional expectation by e^{-c_3 tau N}.
Markov bounds the deviation probability by
exp(-(c_3 - 2 c_5) tau N). There are at most (3 N^C)^k = exp(k C log N
+ o(1)) possible w in range. Choosing c_5 < c_3/4, then kappa small
so that (C + 2) kappa < c_5/2, the union of failures has probability
at most exp(-c_3 tau N / 4). Adding the norm event 2^{-c N} bounds
the total failure probability below one for large N, giving existence.
CELL SELECTION. Fix U and J from the deterministic reduction. For
each g, write Y^g = (y_i^g : i in J) for the J-coordinates of a
possible tester. Each such coordinate is bounded by
R_0 N^2 sqrt(N). Partition the box into cells of side
4 N^{-C-2} sqrt(N). The number of cells per coordinate is at most
(R_0 / 4) N^{C + 4},
so the total number of cell tuples for all k testers is at most
( (R_0 / 4) N^{C + 4} )^{k |J|}.
For each cell tuple, decide whether it contains a coordinate tuple
that satisfies the geometric bounds and the Fourier bound; if so,
record one such tuple and denote it y-hat^1, ..., y-hat^k. This
selection is made after the deterministic reduction has fixed U and
J, and before B is tested; it depends only on U, J, the cell list,
and the tuple of Fourier coefficients, not on B.
Cell-count bound. Because |J| <= gamma N, the base-two log of the
number of cell tuples is at most
k |J| (C + 4) log_2 N + o(N) <= kappa (C + 4) gamma tau N^2.
This is the entropy source the row test must beat.
ROW TEST AND UNION BOUND. Fix a cell tuple and its recorded
representatives y-hat^1, ..., y-hat^k. Two facts hold.
GEOMETRIC BOUND PER ROW. For every row v,
dist( (B y-hat^g)_v, Z ) <= 4 N^{-C} sqrt(N) (1 <= g <= k).
Indeed, each y-hat^g lies in the same cell as the multi-tester y^g,
so their J-coordinates differ by at most 4 N^{-C-2} sqrt(N)
coordinatewise, giving || y-hat^g - y^g ||_2
<= 4 sqrt(gamma) N^{-C-1} on J and 0 elsewhere. Each row of B has
Euclidean norm at most sqrt(N), and B y^g is integral for every g,
so the deviation is at most sqrt(N) * 4 sqrt(gamma) N^{-C-1}
<= 4 N^{-C} sqrt(N).
INDEPENDENCE. Conditional on B's entries outside the cross-block
J x J^c, the row vectors (B_{v i})_{i in J} for v in J^c are
independent across v, since they use disjoint upper-triangular
entries.
FOURIER KERNEL. Put M_0 = floor(N^{C-3}) and consider the nonnegative
product kernel
K(t_1, ..., t_k) = prod_{g=1}^k
| (1/M_0) sum_{h=0}^{M_0-1} e^{2 pi i h t_g} |^2.
On the interval of radius 4 N^{-C} sqrt(N) around an integer, each
factor is at least 1/2 (because M_0 * 4 N^{-C} sqrt(N)
<= 4 N^{-2} sqrt(N) -> 0). Therefore K >= 2^{-k} on the product
interval. The Fourier coefficients c_w of K are nonnegative, satisfy
c_0 = M_0^{-k}, |c_w| <= M_0^{-k} for |w|_inf < M_0, and vanish for
|w|_inf >= M_0.
EXPECTATION ON ONE ROW. With the row vector X_v = ( (B y-hat^g)_v )_g,
E[ K(X_v) ] = sum_{w in Z^k} c_w
E[ prod_{g=1}^k e^{2 pi i w_g (B y-hat^g)_v} ].
For w != 0, the multi-tester Fourier bound applies and gives
|E[ prod_g e^{2 pi i w_g (B y-hat^g)_v} ]| <= e^{-c_5 tau N}. The
w = 0 term is c_0. There are at most (3 M_0)^k nonzero frequencies in
range. So, with (C - 3) kappa < c_5 / 2,
E[ K(X_v) ] <= M_0^{-k} + M_0^{-k} (3 M_0)^k e^{-c_5 tau N}
= M_0^{-k} (1 + o(1)).
MARKOV. The complementary event "K(X_v) >= 2^{-k}" (which contains
the test event) has probability at most 2^k E[K(X_v)]
<= (1 + o(1)) (2/M_0)^k = N^{-k(C-3) + o(k)}.
INDEPENDENCE AND PRODUCT. Conditional on the cross block, the
K(X_v) for v in J^c are independent, so
P(all v in J^c pass)
<= N^{-k(C-3)(1 - 2 gamma) N + o(kN)}.
UNION BOUND. The number of choices of (U, J, cell tuple) is at most
|C_{m, N}| times 2^m times the cell-tuple count, so the base-two
logarithm of the number of trials is at most
N^2 ell^{-P} + gamma N + k |J| (C + 4) log_2 N.
The base-two logarithm of the probability of one full trial passing
at every row is at most
- k (C - 3) (1 - 2 gamma) N log_2 N + o(k N log N).
Because |J| <= gamma N, the combined exponent of the union bound is
N^2 ell^{-P} + gamma N
+ k N log_2 N * ( gamma (C + 4) - (C - 3) (1 - 2 gamma) / 2 ).
Choose gamma small so the factor in parentheses is at most
-(C - 3)/3, and recall P > D + 5. Since k = kappa tau N / log N, the
last term dominates, and the total is
- Omega( tau N^2 ) <= - omega(N).
Hence the exceptional probability of the simultaneous intersection
theorem is at most 2^{-omega(N)}.
DISCRIMINANT PAIRING. For a nonsingular symmetric integer matrix B
of size m, define
lambda_B(x + BZ^m, y + BZ^m) = x^T B^{-1} y in Q/Z,
on the finite abelian group G_B = Z^m / BZ^m. It is well defined on
classes: replacing x by x + B u and y by y + B v changes the value
by the integers u^T y and x^T v.
Perfectness. The map x + BZ^m -> lambda_B(x, .) is injective: if
lambda_B(x, y) = 0 for every y in Z^m, then B^{-1} x is in Z^m, so
x = B(B^{-1} x) lies in BZ^m and the class is zero. Since the two
finite groups have equal cardinality, injectivity gives isomorphism
G_B = Hom(G_B, Q/Z).
Isotropy. An element x in G_B is isotropic if lambda_B(x, x) = 0.
Every z in S_{L_0}(B) satisfies z^T B^{-1} z in {0, 1} in Z, so the
class of z is isotropic. Uniqueness of primary decomposition in Q/Z
then makes each primary component of z isotropic in G_{B, l}.
INVARIANT EXPONENTS. Write G_{B, l} for the l-primary part of G_B
and let b_{l, 1} >= b_{l, 2} >= ... >= 0 be its invariant exponents.
Set nu_l = log_2 l and, for every integer s >= 1,
T_s(B) = sum_l b_{l, s}(B) nu_l,
W_s(B) = T_s(B) - T_{s+1}(B) = sum_l max(b_{l, s}(B) - b_{l, s+1}(B), 0) nu_l.
Necessarily T_1 + T_2 + ... = log_2 |det B|, and W_1 >= W_2 >= ....
COLORING INPUT. Fix a nonsingular bit matrix B of size m <= N and
put f_l = b_{l, 3}(B) for each prime l.
(i) The perfect pairing on G_{B, l} decomposes orthogonally as
G_{B, l} = U_l (+) V_l, where U_l has at most two cyclic summands
of exponents strictly larger than f_l, V_l has exponent dividing
l^{f_l}, and the isotropic elements of G_{B, l} can be colored
with C_l colors where
C_l <= 1 + 8 b_{l, 1}(B), C_l <= 2^{b_{l, 2}(B) - b_{l, 3}(B)} (l odd),
in such a way that any two elements x, y of one color satisfy
l^{f_l} lambda_B( x_{U_l}, y_{U_l} ) = 0 in Q/Z.
(ii) There is a fixed cost J_B <= 3 W_2(B), such that for every
subset X of G_B of isotropic elements having one fixed color at
every prime, the image of the restricted pairing
H = < x - y : x, y in X > -> Hom(H, Q/Z), u |-> lambda_B(u, .)|_H,
has order at most N^{N J_B}.
PROOF OF (i). The classification of nondegenerate symmetric bilinear
forms on finite abelian l-groups gives an orthogonal block
decomposition into cyclic blocks, with possible two-generator blocks
only at l = 2, and there the two exponents coincide. See Miranda
1984, Trans. AMS 284, 535-542 (Nondegenerate symmetric bilinear
forms on finite abelian 2-groups). The f_l cutoff does not split any
block. The linear bound 1 + 8 b_{l, 1} covers small primes; the
exponential bound 2^{b_{l,2} - b_{l,3}} controls the odd primes at
which the number of colors is dominated by the reduction at level
b_{l,2} - b_{l,3}. The color condition follows by annihilating V_l
and by l^{f_l}-killing the residual isotropic pairs in U_l.
./miranda-1984-0743731-1-bilinear-2-groups.pdf
PROOF OF (ii). Restricting to H discards denominators of size up to
|det B| = 2^{log_2 |det B|}, replacing them by the color constraints
of (i). Concretely, the pairing image of H injects into the subgroup
of prod_l l^{f_l + b_{l,2} - b_{l,3}} that is annihilated by the
f_l-multiplications, and the log-count over l is bounded by 3 W_2(B).
The factor 3 absorbs the l = 2 two-generator corrections and the
colimit structure. Compare Lemmas 6.1-6.4 of the companion
manuscript on the unbiased case.
COST OF SPECIFYING COLORS. Uniformly over nonsingular bit matrices B
of size m <= N,
(a) sum_l log_2 C_l = o(N) whenever T_2(B) < sigma, and
(b) whenever T_2(B) >= sigma there is a set P of primes with
sum_{l in P} (b_{l,2} - b_{l,3}) nu_l >= sigma and
sum_{l in P} log_2 C_l = o(N).
Proof. Hadamard gives |det B| <= m^{m/2} <= N^{N/2}, so for every
prime l, b_{l,1}(B) nu_l <= (N log_2 N)/2, and hence log_2 C_l <= O(log N)
uniformly. By the prime number theorem there are O(sqrt N/log N)
primes l <= sqrt N, so their total cost is O(sqrt N log N) = o(N).
For odd l > sqrt N the exponential color bound holds,
C_l <= 2^{b_{l,2} - b_{l,3}}, so
log_2 C_l <= b_{l,2} - b_{l,3}
= (b_{l,2} - b_{l,3}) nu_l / nu_l
<= 2 * (b_{l,2} - b_{l,3}) nu_l / log_2 N.
The prime 2 has already been counted in the small-prime case.
Case (a). T_2(B) < sigma gives, summing over odd l > sqrt N,
sum_{l > sqrt N, odd} log_2 C_l <= (2 / log_2 N) W_2(B)
<= (2 / log_2 N) T_2(B)
<= 2 sigma / log_2 N = o(N),
since sigma = ell^{-c} -> 0.
Case (b). Include every contributing small prime l <= sqrt N first.
If their total weight is already at least sigma, done. Otherwise add
odd contributing primes l > sqrt N in decreasing order of weight
(b_{l,2} - b_{l,3}) nu_l, until the threshold sigma is first reached.
Before the last prime, the accumulated weight is at most sigma, so
sum_{l in P, l > sqrt N, l not last} log_2 C_l
<= (2 / log_2 N) sigma = o(N).
The last prime has cost at most log_2 C_l <= O(log N) via the linear
bound 1 + 8 b_{l,1}. The total cost is therefore
O(sqrt N log N) + O(sigma / log_2 N) + O(log N) = o(N).
Both cases give the claim.
STATIC COLUMN ESTIMATE. Fix L_0 >= 1 and e_0 > 0 small. Set
sigma = ell^{-c} for a fixed c > 0, and choose zeta, xi > 0 small
enough that
6 zeta + 2 xi < e_0.
There is a typical event E_m for bit matrices B of size m in I_N
(failure probability 2^{-omega(N)}, uniform in sizes and probability
arrays) with the following property: every nonsingular B in E_m
satisfying W_2(B) <= zeta obeys
|S_{L_0}(B)| <= 2^{e_0 N}.
Proof. Two cases.
Case B (T_2(B) < sigma). By the cost-of-colors lemma (a), the total
cost sum_l log_2 C_l of the coloring is o(N). Take the largest color
class V_0 of S_{L_0}(B). Then |S| <= 2^{o(N)} |V_0|, and V_0 is
color-consistent, so the graph comparison lemma (stated and proved
below) applies with J_B <= 3 W_2(B) <= 3 zeta:
|V_0| <= 2^{(2 J_B + 2 xi + o(1)) N}
<= 2^{(6 zeta + 2 xi + o(1)) N}.
Then |S_{L_0}(B)| <= 2^{(6 zeta + 2 xi + o(1)) N} <= 2^{e_0 N} by
the choice of zeta, xi.
Case A (T_2(B) >= sigma). By the cost-of-colors lemma (b), there is a
set P of primes with weight_P := sum_{l in P} (b_{l,2} - b_{l,3}) nu_l
>= sigma and cost_P := sum_{l in P} log_2 C_l = o(N). Take the
largest P-color class V_0; then |S| <= 2^{cost_P} |V_0| = 2^{o(N)} |V_0|.
The class V_0 is P-color-consistent, so the graph comparison lemma
below, applied to the set P, gives
|V_0| <= 2^{(2 J_B + 2 xi + o(1)) N} <= 2^{(6 zeta + 2 xi + o(1)) N},
using J_B <= 3 W_2(B) <= 3 zeta. Then
|S| <= 2^{(6 zeta + 2 xi + o(1)) N} <= 2^{e_0 N}
by the choice of zeta, xi.
The typical event E_m is the intersection of the typical events used
for the coloring input, the cost-of-colors lemma, the graph
comparison lemma, and the auxiliary inverse-rank and small-spectrum
estimates (see below).
GRAPH COMPARISON LEMMA. Fix L_0 >= 1 and xi, w > 0. Let B be a
nonsingular symmetric bit matrix of size m in I_N. Suppose the
following two properties hold.
(i) For every rational F <= R^m with H(F) <= 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)].
Fix a set P of primes. Then every V subset S_{L_0}(B) whose elements
are P-color-consistent (all elements having one fixed color at every
prime l in P) satisfies
|V| <= 2^{(2 J_B + 2 xi + o(1)) N},
with the above bound holding for any P, since J_B(P) <= J_B. Taking
P = all prime divisors of |det B| recovers the fully color-consistent
case.
Proof. If V is empty there is nothing to prove. Otherwise, robust
extraction with rho = ell^{-2} gives V_0 subset V that is rho-robust
on its affine span F_0 = span(V_0 - V_0), and
log_2 |V_0| >= log_2 |V| - o(N).
Let r_0 = dim F_0. The rational graph map gamma : R^m -> R^m (+) R^m,
gamma(x) = (x, B^{-1} x), is injective, and for v, v' in V_0,
| gamma(v) - gamma(v') |_2^2
= |v - v'|_2^2 + | B^{-1} (v - v') |_2^2
<= m + 4 L_0^2 N
<= (1 + 4 L_0^2) N,
by definition of S_{L_0}(B). Apply the robust image lattice lemma
twice, 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) ),
where L is the integer span of gamma(v) - gamma(v') over v, v' in V_0.
Define the symmetric bilinear form q on Gamma = gamma(R^m) by
q(gamma(x), gamma(y)) = x^T B^{-1} y. Since V is color-consistent, the
image of L -> G_B sending gamma(u) to u + B Z^m is H = <v - v': v,
v' in V_0>, of order at most N^{N J_B} by the coloring input (ii).
Because q modulo Z pulls back to lambda_B on H, the pairing image
order of q|_L is at most t = N^{N J_B}.
Let K = L intersect rad(q|_{F_0}) and let S = F_0 intersect (rad q|_{F_0})^perp,
where q|_{F_0} denotes the restriction of the bilinear form. The
pairing-image-and-determinant lemma gives
|det_orth(q|_S)| >= (det K)^2 / (t (det L)^2)
>= N^{-N J_B} exp(-O_{L_0}(N ell)). (LB)
Let s = rank(q|_{F_0}). By hypothesis (i) applied to F_0, whose height
is at most exp(O(N ell)),
s >= r_0 - xi N. (rank)
Now the spectral side. If v is a unit eigenvector of B with nonzero
eigenvalue x, gamma(v) = (v, x^{-1} v) and
q(gamma(v), gamma(v)) = x^{-1},
| gamma(v) |^2 = 1 + x^{-2}.
Orthogonal eigenvectors of B give orthogonal image vectors in Gamma,
because q(gamma(u), gamma(v)) = u^T B^{-1} v which vanishes when u, v
are orthogonal eigenvectors with distinct eigenvalues. Hence the
eigenvalues of the self-adjoint operator representing q on Gamma are
x / (1 + x^2), for x ranging over the eigenvalues of B.
They all have absolute value at most 1. By hypothesis (ii), at most
xi N of them correspond to x in [-w sqrt(N), w sqrt(N)]; for such x,
|x / (1 + x^2)| <= w sqrt(N).
For any other x, so |x| > w sqrt(N), one has
|x / (1 + x^2)| < 1 / (w sqrt(N)).
Compression of a self-adjoint operator to a t-dimensional subspace has
absolute value at most the product of its t largest singular values.
Applying this to S (dim S = t):
|det_orth(q|_S)| <= (w sqrt(N))^{xi N} (1 / (w sqrt(N)))^{t - xi N} . (UB)
Combine (LB) and (UB) in base-two logarithms:
- N J_B log_2 N - O_{L_0}(N ell)
<= xi N log_2(w sqrt(N)) - (t - xi N) log_2(w sqrt(N)).
Divide by log_2 N and let N -> infinity:
t <= 2 J_B N + xi N + o(N).
Combining with (rank) gives r_0 <= 2 J_B N + 2 xi N + o(N).
Projection of r_0 independent coordinates is injective on V_0, so
|V_0| <= 2^{r_0}. Hence
|V| <= 2^{o(N)} |V_0| <= 2^{(2 J_B + 2 xi + o(1)) N},
which is the asserted bound.
INVERSE RESTRICTION RANK. Fix D > 0 and xi > 0. Typically (failure
probability 2^{-c_{p, xi} N^2}) a nonsingular bit matrix B of size m
in I_N satisfies, simultaneously for every rational subspace F <= R^m
with H(F) <= exp(N ell^D),
rank(B^{-1}|_F) >= dim F - xi N.
Proof. First fix an arbitrary real subspace U <= R^m of dimension d.
Choose a basis matrix V of U and a coordinate set I of size d for
which V_I is the identity. Conditional on all entries of B outside
the principal block I x I, the matrix of B|_U in the basis V is
V^T B V = B_{I, I} + H,
where H is a fixed symmetric matrix over R, determined by the
revealed entries of B outside I x I. The unrevealed entries of
B_{I, I} are independent bits, each with largest atom b. The
corank-tail bound applied over R with k = ceil(xi N/2) gives
P( dim rad(B|_U) >= ceil(xi N / 2) ) <= 2^{-c_{p, xi} N^2},
for all sufficiently large N; the event is empty if d < ceil(xi N/2).
For a fixed symmetric form, replacing U by V changes the nullity of
the restriction by at most the rank distance d(U, V). Concretely, if
Z subset U has codimension t, restriction to Z deletes t rows and t
columns of the representing matrix, changing the rank by at most 2t
and hence the nullity by at most t. Apply first to Z = U intersect V inside
U, then inside V.
Now apply the low-height cover with the given D and any fixed
P > D. For every list member U in C_{m,N}, bound the nullity event
above. Every rational F <= R^m with H(F) <= exp(N ell^D) has a
nearby list member U with d(F, U) <= N ell^{-P}, and on the
complementary event
dim rad(B|_F) <= ceil(xi N/2) + N ell^{-P} <= xi N
for large N. Union bound gives probability at most
2^{N^2 ell^{-P}} 2^{-c_{p, xi} N^2} = 2^{-Omega_{p, xi}(N^2)}.
Translation to B^{-1}. For every nonsingular B and every rational F,
the two radicals
rad(B|_{F^perp}) = F^perp intersect B^{-1} F,
rad(B^{-1}|_F) = F intersect B(F^perp),
are linked by multiplication with B, and their dimensions agree.
Consequently
rank(B^{-1}|_F) = dim F - dim rad(B^{-1}|_F)
= dim F - dim rad(B|_{F^perp})
>= dim F - xi N.
SMALL SPECTRUM. Fix xi > 0. There is w_xi > 0, depending on p and
xi, such that typically (failure probability 2^{-c_{p, xi} N^2}) a
bit matrix B of size m in I_N has at most xi N eigenvalues in
[-w_xi sqrt(N), w_xi sqrt(N)]. Nonsingularity is not needed.
Proof. Put X = (B - E B) / sqrt(m p b) and
mu_X = (1/m) sum_i delta_{lambda_i(X)}. The centered,
variance-standardized entries ((B - E B)_{i,j}) / sqrt(p b) have
mean zero, variance one, and uniformly bounded moments of every
fixed order, in every permitted array.
Moments. Expand (1/m) E Tr X^s over closed walks of length s.
Independence kills any summand that uses some edge exactly once.
Every remaining walk has at most s/2 distinct edges and at most
1 + s/2 vertices, so its contribution is O_{p, s}(m^{v - 1 - s/2})
= o(1) whenever v < 1 + s/2. Equality is possible only for even s
and walks that traverse each edge of a tree twice; such walks
contribute 1 + o(1), and their number is (s/2 + 1)^{-1} binom(s,
s/2), matching the s-th moment of the semicircle distribution
d mu_sc(x) = (1/(2 pi)) sqrt(4 - x^2) [|x| <= 2] dx. The method of
moments then gives
(1/m) E Tr X^s -> integral x^s d mu_sc(x),
for every fixed s, uniformly in m in I_N and in the probability
array. This is Wigner 1958, Ann. Math. 67, 325-327.
Tent function. Choose w > 0 small, fixed and depending on xi, and
put f(x) = (1 - |x|/w)_+. Since the semicircle mass of [-w, w]
tends to zero with w, for large N and uniformly,
E Tr f(X) <= xi m / 16.
Concentration. Write f = 1 - g_1 + g_2, with g_1(x) = |x|/w and
g_2(x) = (|x|/w - 1)_+. Both are convex and 1/w-Lipschitz. Their
matrix traces are convex in the entries: with M_+ the spectral
positive part, Tr M_+ = sup_{0 <= P <= I} Tr(P M). Hoffman and
Wielandt 1953, Duke Math. J. 20, 37-39, plus Cauchy-Schwarz gives,
for j = 1, 2 and any two entry arrays y, y' of X,
| 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.
Then Talagrand 1995, Publ. IHES 81, 73-205, Theorem 4.1.1, applies:
for convex L-Lipschitz F, P(|F - E F| > t) <= C exp(-c t^2 / L^2).
Taking F to be the two convex traces and t = xi m / 32 gives
P( Tr f(X) > xi m / 8 ) <= C exp(-c_{p, xi, w} m^2).
./talagrand-1995-numdam-concentration.pdf
Eigenvalue count. On the complementary event, f >= 1/2 on
[-w/2, w/2] forces at most xi m / 4 eigenvalues of X to lie in
[-w/2, w/2]. The matrix B / sqrt(m p b) differs from X by minus
E B / sqrt(m p b), which has rank at most two. Interlacing changes
the eigenvalue count in any interval by at most 4. Taking, for
example, w_xi = w sqrt(p b) / 4 gives w_xi sqrt(N/(m p b)) <= w/2
for large N, uniformly in m in I_N. So the requested eigenvalue
count is at most xi m / 4 + 4 <= xi N for large N.
DISSOCIATION LEMMA. Let C be nonsingular of size m <= N, and let
C Z^m <= K <= Z^m have index N^{qN}. If v is a random bit vector with
independent entries, each with largest atom at most b, then
P(v in K) <= b^{2 q N / 3}.
Proof. Write g_1, ..., g_m for the coordinate images in Z^m / K.
Choose a maximal dissociated set of coordinate images,
g_{i_1}, ..., g_{i_j}, meaning that their subset sums are all
distinct in Z^m / K. By maximality, every unselected g_i is a
{-1, 0, 1} combination of the selected ones:
g_i = sum_{h = 1}^j M_{h, i} g_{i_h} (mod K),
M_{h, i} in {-1, 0, 1}, M_{h, i_h} = delta_{h, positionof(i_h)}.
Condition on the v_i for unselected i. The condition sum_i v_i g_i
= 0 mod K becomes a linear condition on the selected coordinates
v_{i_1}, ..., v_{i_j}. By dissociativity, at most one assignment of
selected bits satisfies it. So the probability that v lies in K is at
most b^j.
Remains to show j >= 2 q N / 3. Let theta : Z^j -> Z^m / K denote
theta(a) = sum_h a_h g_{i_h}. Since C is nonsingular, the j x m
matrix M C has rank j; every column of M C lies in ker theta, because
substituting the representation of g_i yields theta(MC e_i) = 0 in
Z^m / K. The integer span L' of j independent columns of MC has
Hadamard bound det L' <= N^{3j/2} since each entry of MC is bounded
by m <= N.
Index count. Since ker M <= K, M sends K to a sublattice of image(M)
of index N^{qN}. Modulo the preimage-of-theta sublattice, which has
index at most |image theta| <= 2^j in image(M), this sublattice is
contained in ker theta, so
N^{qN} = [image(M) : MK] <= |image theta| det L'
<= 2^j N^{3j/2}.
Taking base-two logarithms, qN log_2 N <= j (1 + (3/2) log_2 N), so
j >= (2/3 - o(1)) qN.
GATED DELETION. Let B be a nonsingular symmetric bit matrix of
positive size. The empty principal minor has determinant one and
admissible column the empty vector. 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} and ||C^{-1} v_i||_inf <= 1 for
i = 1, 2.
In particular, every nonsingular C produced by (b) satisfies the
width-two gate v_1, v_2 in S_{L_0}(C) for suitable L_0.
This is the companion's Lemma 7.1; the proof uses Jacobi's
complementary minor identity to identify a two-coordinate deletion
with the desired quadratic condition when the cofactor diagonal
vanishes.
PRINCIPAL EXTENSIONS. A principal extension of width h in {1, 2} of
a nonsingular C has the form
B = [[ C, V ],
[ V^T, D ]],
with V = (v_1, ..., v_h) an m x h bit matrix, D symmetric. At width
two, impose the gate v_1, v_2 in S_{L_0}(C). At width one, no gate is
imposed.
RETENTION AND TAIL RECURSION (companion). Let pi : Z^m -> G be a
quotient map with C Z^m <= ker pi.
(i) For any set D of positive layers of G, there is a lattice K_D
depending only on pi, G, D such that C Z^m <= K_D <= Z^m and
[Z^m : K_D] = N^{N q(D)}, q(D) = sum_{(l, j) in D} k_G(l, j) nu_l.
Moreover, if every layer in D is retained on quotienting by pi(v),
then v lies in K_D.
(ii) If the extension 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 one has
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.
Both are the companion's Retention lattice lemma 7.4 and Tail
recursion lemma 11.1. The proofs use only the symmetry of the
discriminant pairing and the structure of principal minors, not the
entry distribution, so both apply in the biased bit model.
COSTLY STEP. Put sigma = R^{-6} and R = ceil(ell^2). Call an
extension of width h in {1, 2} costly if, in at least one of its
quotient operations, the retained layers have total weight
sum_{(l, j) in R_i} nu_l >= sigma.
COST OF A COSTLY STEP. Uniformly over nonsingular C with size in
I_N and over extensions of either width, conditional on C, the
probability that the extension is costly is at most
p_N := 2^{-N (a - 2 e_0)}.
For a width-2 extension with W_2(C) <= zeta, the joint probability
that the gate holds and the extension is costly is at most p_N^2.
For a single specified column, the probability that its retained
weight is at least sigma also satisfies p_N, even after exposing the
preceding column of a width-2 extension.
Proof. Apply the simultaneous intersection with tau = ell^{-20} and
alpha = e_0 to C. Any fixed set D of retained layers with
q(D) >= sigma is contained in a lattice K_D of index N^{q(D) N}. The
dissociation lemma gives
P(column in K_D) <= b^{2 N q(D) / 3} <= 2^{-N sigma (2a)/3}
<= p_N.
The number of layer sets D with q(D) >= sigma is 2^{o(N)}, so a union
bound preserves the bound p_N. The gate-plus-costly bound follows
from the static column estimate: |S_{L_0}(C)| <= 2^{e_0 N}, so each
column lies in S with conditional probability at most 2^{e_0 N}
b^{N-1}, and squaring gives
(2^{e_0 N} b^{N-1})^2 = 2^{2 e_0 N} b^{2 N - 2} <= p_N^2,
absorbing fixed factors into p_N.
TERMINAL WINDOW ALTERNATIVE. Put R = ceil(ell^2) and choose
0 < eta < min(1, zeta/4). Consider 5R consecutive nonsingular
principal extensions of widths in {1, 2}, satisfying their gates.
Suppose every node X_i has W_R(X_i) <= eta and the terminal X_{5R}
has W_2(X_{5R}) > zeta. Then for all sufficiently large N, either
at least two distinct steps are costly, or there is a width-two
step that starts at a node X_t with W_2(X_t) <= zeta.
Proof. At a noncostly step of width h, the tail recursion gives
W_s(B) <= W_{s+h}(C) + 4 sigma, s >= h.
Iterate from s = 2 backwards over any block of R noncostly steps:
each step raises the W-threshold by at least one, plus 4 sigma per
step, so the last R noncostly steps force W_2 <= eta + 4 R sigma on
the block start. Put delta = eta + 4 R sigma; delta < zeta for
large N.
Assume the window has at most one costly step. If there is no
costly step, the last R steps end at X_{5R}, whose W_2 exceeds
zeta, contradicting W_R(X_{5R - R}) <= eta < zeta. So there is
exactly one costly step, at a position t. To prevent the last R
steps ending at X_{5R} from forcing W_2 <= delta < zeta, that
costly step must satisfy t >= 4R + 1. Both X_{t-2} and X_{t-1} then
end blocks of at least R noncostly steps inside the window, so
W_2(X_{t-2}) <= delta, W_2(X_{t-1}) <= delta.
Suppose, for contradiction, that no width-two step in the window
starts at a node with W_2 <= zeta. Then the steps at positions
t-1 and t cannot have width two: if step t-1 had width two, its
start X_{t-2} satisfies W_2 <= delta < zeta, contradiction; if
step t had width two, its start X_{t-1} satisfies the same, another
contradiction. So both steps have width one. The height comparison
in the tail recursion at width one (with h = 1 and s = 1) gives
W_1(X_{t-1}) <= W_2(X_{t-2}) + 4 sigma <= delta + 4 sigma,
and since step t is width one,
W_2(X_t) <= W_1(X_{t-1}) <= delta + 4 sigma.
The single costly step is at position t, so its retained-weight set
R_t has sum_{(l, j) in R_t} nu_l >= sigma. But the tail recursion
already absorbed all costly weight into W_2(X_t) <= delta + 4 sigma,
which is below zeta < sigma for sufficiently large N. This is a
contradiction. The window therefore contains either two costly
steps or a width-two step starting below zeta.
PATH COUNTING AND FINISHING THE COLUMN ESTIMATE. Fix a path
I_0 subset I_1 subset ... subset I_{H_0} = [m_*],
with H_0 = 2 ceil(N^{3/5}), m_* = N - 1, and each difference
I_t \ I_{t-1} of size 1 or 2. The number of paths is at most
(2 N^2)^{H_0} = 2^{O(N^{3/5} log N)} = 2^{o(N)}.
Backward induction. Suppose B = B_{5R} is a nonsingular endpoint with
W_2(B) > zeta. Apply the terminal window alternative to the last 5R
steps. Either (a) two steps in the window are costly, or (b) there
is a width-two step in the window whose start X satisfies
W_2(X) <= zeta and whose gate holds.
Union bound. In case (a), by the width-one cost, the joint
probability of two costly steps is at most p_N^2, times 2^{o(N)}
choices of positions and paths. In case (b), by the gate-cost bound
and one expensive step, the joint probability is at most
p_N^2 . 2^{o(N)}. So
P(B nonsingular and W_2(B) > zeta)
<= 2^{-2 N (a - 2 e_0) + o(N)}.
If B has W_2(B) <= zeta, the static column estimate gives
|S_{L_0}(B)| <= 2^{e_0 N} except on an event of probability
2^{-omega(N)}. Combining the two branches,
P(B nonsingular and |S_{L_0}(B)| > 2^{e_0 N})
<= 2^{-N (2a - 10 e_0)},
for e_0 sufficiently small.
This is the column estimate.
COMPLETION. Combined with the reduction assembled above, the column
estimate implies
P(det A = 0) <= 2^{o(n)} ( 2^{-N(h_* - e_0 - C_p w_1)} + 2^{-N(2a - 10 e_0)} ) + 2^{-Omega(n^{6/5})}
<= 2^{-N (d_* - epsilon)} + 2^{-N d_*} * o(1).
Taking N-th roots and then epsilon -> 0 gives the upper bound of the
main theorem, and combined with the row-collision lower bound
(P >= (p^3 + b^3) Q^{n-2}) gives the sharp rate Q^n.
That completes the proof.