Sharp singularity rates for symmetric random sign matrices

Claims a random symmetric ±1 matrix is singular with probability (1/2 + o(1))ⁿ, with a matching biased-sign rate.

2 papers October 3, 2026 Explained by AI

Fill a symmetric square grid with random +1s and −1s. The papers ask how likely the grid's determinant is exactly zero as the grid grows. They claim the chance shrinks like (1/2)ⁿ, up to smaller factors, which matches the simple event that two rows are equal. A companion paper claims the matching rate for biased signs. Neither result has a Lean proof.

First step

2006

Kevin Costello, Terence Tao and Van Vu, asymptotic nonsingularity

Significance

Solid

It would pin down the exact exponential rate in a well-studied problem of random matrix theory.

Trust

Claimed, not checked

Field

Probability and statistical mechanics

2 papers

The explanation

Build a random symmetric matrix of size n. Flip a fair coin for each entry on or above the diagonal, writing +1 or −1. Copy each entry across the diagonal, so the entry in row i, column j equals the one in row j, column i. The matrix is singular when its determinant is zero. For n = 3 there are 6 free entries, so 2⁶ = 64 matrices. Exactly 32 are singular. For n = 6, a computer count gives 907,008 singular matrices out of 2,097,152, about 0.43. One easy way to be singular is for two rows to be equal. A fixed pair of rows agrees with probability exactly 2⁻ⁿSource 1. For n = 4 that is 1/16, and a direct count agrees.

For matrices with all n² entries independent, the story is known. Komlós showed such matrices are almost never singular for large n. Tikhomirov proved the sharp rate (1/2 + o(1))ⁿ for independent signsSource 2. The term o(1) means a correction that shrinks to zero as n grows. Symmetry breaks the old methods. Revealing one row also reveals entries in every later rowSource 3. Costello, Tao and Vu first showed symmetric sign matrices are nonsingular with probability tending to oneSource 4. Campos, Jenssen, Michelen and Sahasrabudhe later proved an exponential bound, exp(−cn) for some constant cSource 5. The exact rate stayed open.

The first paper claims the sharp answer. The probability of singularity is (1/2 + o(1))ⁿSource 6. So all ways of being singular together have the same exponential rate as two equal rows. Small sizes do not show this yet: the o(1) term is still large at n = 6. The proof turns the sign matrix into a symmetric matrix of 0s and 1s, one size smallerSource 7. Singularity then becomes a question about adding a new column to an invertible matrix. It suffices to show the expected number of bad columns grows slower than any exponentialSource 8. Lattices, regular grids of points, control that count.

The second paper fixes a bias p, the chance of a +1, with p not equal to 1/2. It claims the rate is p² + (1 − p)²Source 9. That is the chance that two independent biased signs agreeSource 10. For p = 0.3 it is 0.09 + 0.49 = 0.58.

How sure is this? Neither paper has a Lean proof. Both rest on long arguments with many interacting estimates. No specialist review of either paper has been published.

What it doesn't show. This does not give the exact constant or lower-order factor in front of the exponential rate, and it is not checked in Lean.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Notable if it holds. The rates match a simple lower bound, which is a good sign, but nothing is formalized and no specialist review is published.

Words used

Symmetric matrix: A square table of numbers that is unchanged when flipped across its main diagonal.
Singular: A matrix whose determinant is zero, so some row is a combination of the others and it has no inverse.
Determinant: A single number computed from a square matrix; it is zero exactly when the matrix is singular.
o(1): A correction term that shrinks to zero as n grows.
Bias p: The probability that an entry is +1 instead of −1.
Lattice: A regular grid of points in space, closed under adding and subtracting its points.

The original papers (2)

The sharp exponential rate of singularity for symmetric Bernoulli matrices (PDF, opens in a new tab)
October 3, 2026
The sharp singularity rate for biased symmetric sign matrices (PDF, opens in a new tab)
October 4, 2026

All quoted lines (10)

A specified pair of rows is equal with probability $2^{-n}$ : the $n-2$ comparisons away from the two diagonal positions and the two remaining diagonal conditions are independent.
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
Tikhomirov proved the sharp rate $(1/2+o(1))^n$ for independent uniform signs.
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
Symmetry changes the exposure of the matrix: revealing a row also reveals entries in all later rows.
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
Costello, Tao, and Vu proved that a random symmetric Bernoulli matrix is nonsingular with probability tending to one, obtaining the bound $O(n^{-1/8+\delta})$ for every fixed $\delta>0$ .
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
Campos, Jenssen, Michelen, and Sahasrabudhe proved an exponential bound $\exp(-cn)$ , using inverse Littlewood–Offord estimates for conditioned random walks and the method of inversion of randomness.
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
For the symmetric Bernoulli matrix $A_n$ , $\Pr(\det A_n=0)=\left(\frac12+o(1)\right)^n =2^{-n+o(n)} \qquad\text{as }n\to\infty.$
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
A Schur complement converts the sign matrix in dimension $n$ to a binary matrix in dimension $N=n-1$ .
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
It suffices to prove that their expected number is $2^{o(N)}$ .
The sharp exponential rate of singularity for symmetric Bernoulli matrices Back to text
We prove that $\Prob(\det A_n=0)=(p^2+(1-p)^2+o(1))^n$ .
The sharp singularity rate for biased symmetric sign matrices Back to text
The quantity on the right is the probability that two independent signs with this bias agree.
The sharp singularity rate for biased symmetric sign matrices Back to text

Other sources

openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

238Optimal logarithmic mixing of the Thorp shuffleProbability and statistical mechanics
232Gaussian fields and interfaces for triangular-lattice Lipschitz heightsProbability and statistical mechanics
230Exact Hausdorff gauges for SLEProbability and statistical mechanics
223Random-cluster interfaces: critical, disordered, thermal, and natural-time scalingProbability and statistical mechanics
221The Mézard–Parisi formula for diluted spin glassesProbability and statistical mechanics

Browse Probability and statistical mechanics Open since the 2000s Claimed, not yet checked Solid results