pith. sign in

arxiv: 2607.00495 · v1 · pith:GVBSX3CTnew · submitted 2026-07-01 · 🧮 math.PR

Rank deficiency of Bernoulli random matrices for growing corank

Zeyan Song , Hanchao Wang This is my paper

Pith reviewed 2026-07-02 07:29 UTC · model grok-4.3

classification 🧮 math.PR
keywords Bernoulli random matricescorankrank deficiencyprobability asymptoticsrandom matrices over finite fieldstail probabilities
0
0 comments X

The pith

An n by n Bernoulli random matrix has corank at least k with probability (1-p + o_n(1)) to the power of kn, when k grows as O(sqrt(log n)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the precise asymptotic probability that a random n by n matrix with independent Bernoulli(p) entries fails to have full rank by exactly k dimensions or more. This formula applies in the regime where the corank k grows slowly, up to order sqrt(log n). A reader would care because it gives an explicit exponential expression for the chance of small rank deficiencies rather than only upper or lower bounds. The result therefore describes the tail of the rank distribution in this sparse-deficiency window.

Core claim

Let A be an n x n Bernoulli random matrix whose entries are i.i.d. Bernoulli(p) random variables. In this paper, we determine the probability that the corank of A is at least k when k is of order O(sqrt(log n)): P(corank A >= k) = (1-p+o_n(1))^(kn).

What carries the argument

The asymptotic probability formula P(corank A >= k) = (1-p+o_n(1))^(kn) for k = O(sqrt(log n)), obtained by controlling the contribution of potential kernel vectors.

If this is right

  • The typical corank is o(sqrt(log n)) with high probability.
  • The probability of any fixed corank k decays exponentially in n for each fixed k.
  • The rank distribution concentrates near n in the small-corank window.
  • Similar tail estimates hold for the left and right null spaces simultaneously.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same counting argument might extend to k up to (log n)^c for small c if tighter concentration is applied.
  • The formula suggests that the dominant mechanism is the existence of k nearly independent kernel vectors each with support probability (1-p)^n.
  • Direct simulation for moderate n can test the transition point where the o_n(1) term becomes visible.

Load-bearing premise

The formula is derived under the restriction that k grows at most like the square root of log n, which keeps the number of candidate kernel vectors manageable for the union bound.

What would settle it

Compute the empirical fraction of n by n Bernoulli matrices with corank at least k for n around 500 and k=2 or 3, and check whether it matches (1-p)^{kn} within the claimed o_n(1) error.

read the original abstract

Let A be an n x n Bernoulli random matrix whose entries are i.i.d. Bernoulli(p) random variables. In this paper, we determine the probability that the corank of A is at least k when k is of order O(sqrt(log n)): P(corank A >= k) = (1-p+o_n(1))^(kn).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to determine the probability that the corank of an n×n Bernoulli(p) random matrix A is at least k, specifically when k = O(√(log n)): it asserts that P(corank A ≥ k) = (1−p + o_n(1))^{kn}.

Significance. If the stated asymptotic holds, the result supplies a clean tail probability for the corank distribution in the slow-growth regime k = O(√(log n)). This regime is precisely where first-moment or union-bound arguments become tractable while other linear-dependence events remain negligible, so the formula isolates the dominant zero-row contribution. The paper thereby gives a falsifiable, parameter-light prediction for a concrete range of k.

major comments (2)
  1. [Abstract] Abstract (and any § containing the main theorem): the equality P(corank A ≥ k) = (1−p + o_n(1))^{kn} is stated without an accompanying derivation, error bound, or explicit union-bound calculation. Because the central claim is an exact asymptotic identity, the absence of the controlling estimates (e.g., the contribution of identical-row events versus kernel-vector counting) makes it impossible to verify that the o_n(1) term is uniform in the stated range of k.
  2. [Abstract] The restriction k = O(√(log n)) is load-bearing: the manuscript must show that the binomial prefactor n^k contributes only o(1) inside the base after the kn-th root and that all other dependence events are o((1−p)^{kn}). No such comparison appears in the provided text.
minor comments (2)
  1. [Abstract] Notation: the o_n(1) term should be made explicit as a function of both n and k (or at least stated to be uniform for k ≤ C √(log n)).
  2. The paper would benefit from a short comparison with the known constant-corank results (e.g., the probability of a zero row) to clarify how the growing-k extension is obtained.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed reading and for identifying the need for greater explicitness in the presentation of the main asymptotic. The comments correctly note that the abstract states the result without accompanying estimates; we will revise the manuscript to incorporate the requested comparisons and bounds directly into the abstract and the statement of the main theorem.

read point-by-point responses

  1. Referee: [Abstract] Abstract (and any § containing the main theorem): the equality P(corank A ≥ k) = (1−p + o_n(1))^{kn} is stated without an accompanying derivation, error bound, or explicit union-bound calculation. Because the central claim is an exact asymptotic identity, the absence of the controlling estimates (e.g., the contribution of identical-row events versus kernel-vector counting) makes it impossible to verify that the o_n(1) term is uniform in the stated range of k.

    Authors: We agree that the abstract and theorem statement lack the explicit controlling estimates. The body of the paper contains the union-bound argument separating the zero-row contribution from other linear dependencies, but these estimates are not summarized at the level of the main claim. In the revision we will add a concise derivation outline, including the relevant error bounds, to the abstract and to the paragraph immediately following the statement of Theorem 1.1, making the uniformity of the o_n(1) term verifiable directly from the main result. revision: yes

  2. Referee: [Abstract] The restriction k = O(√(log n)) is load-bearing: the manuscript must show that the binomial prefactor n^k contributes only o(1) inside the base after the kn-th root and that all other dependence events are o((1−p)^{kn}). No such comparison appears in the provided text.

    Authors: The referee is correct that these comparisons are essential and are not visible in the abstract. The proof does establish that (n choose k)^{1/(kn)} = 1 + o(1) uniformly for k = O(√(log n)) and that the probability of non-trivial row dependencies is o((1-p)^{kn}), but these steps are not extracted as a separate remark. We will insert an explicit short lemma (or a dedicated paragraph in the introduction) that performs the kn-th root analysis of the binomial prefactor and bounds the remaining events, and we will reference this lemma from the abstract. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses standard first-moment methods in restricted regime

full rationale

The paper states an asymptotic probability for corank >=k only when k=O(sqrt(log n)), equating it to the contribution from zero rows via (1-p+o(1))^{kn}. This follows from union-bound or first-moment arguments that are valid precisely in this growth regime, where binomial prefactors and other dependence events contribute o(1) terms and are negligible. No self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations appear; the result is self-contained against external probabilistic tools without reducing to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the i.i.d. Bernoulli model and the O(sqrt(log n)) regime for k. No free parameters are fitted and no new entities are introduced. Only the abstract is available, so further assumptions in the proof cannot be audited.

axioms (1)
  • domain assumption Matrix entries are i.i.d. Bernoulli(p) random variables.
    Explicitly stated in the abstract as the definition of A.

pith-pipeline@v0.9.1-grok · 5567 in / 1335 out tokens · 34900 ms · 2026-07-02T07:29:05.145578+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

14 extracted references · 11 canonical work pages

  1. [1]

    On the singularity probability of discrete random matrices.J

    Bourgain, J., Vu, V.H., and Wood, P.M. On the singularity probability of discrete random matrices.J. Funct. Anal.258(2) (2010), 559–603.doi:10.1016/j.jfa.2009. 04.016

    work page doi:10.1016/j.jfa.2009 2010

  2. [2]

    Hunter, Z. et al. On random matrices with large corank.Int. Math. Res. Not. IMRN 2026(12) (2026), Article No. rnag126.doi:10.1093/imrn/rnag126

    work page doi:10.1093/imrn/rnag126 2026

  3. [3]

    Rank deficiency of random matrices.Electron

    Jain, V., Sah, A., and Sawhney, M. Rank deficiency of random matrices.Electron. Commun. Probab.27(2022), Paper No. 14, 9.doi:10.1214/22-ECP455

    work page doi:10.1214/22-ecp455 2022

  4. [4]

    On the probability that a random±1-matrix is singular.J

    Kahn, J., Koml´ os, J., and Szemer´ edi, E. On the probability that a random±1-matrix is singular.J. Amer. Math. Soc.8(1) (1995), 223–240.doi:10.2307/2152887

    work page doi:10.2307/2152887 1995

  5. [5]

    Inverse Littlewood-Offord problems and the singularity of random sym- metric matrices.Duke Math

    Nguyen, H.H. Inverse Littlewood-Offord problems and the singularity of random sym- metric matrices.Duke Math. J.161(4) (2012), 545–586.doi:10 . 1215 / 00127094 - 1548344

    2012

  6. [6]

    A large deviation inequality for the rank of a random matrix.Ann

    Rudelson, M. A large deviation inequality for the rank of a random matrix.Ann. Probab.52(5) (2024), 1992–2018.doi:10.1214/24-aop1695

    work page doi:10.1214/24-aop1695 2024

  7. [7]

    and Vershynin, R

    Rudelson, M. and Vershynin, R. Small ball probabilities for linear images of high- dimensional distributions.Int. Math. Res. Not. IMRN(19) (2015), 9594–9617.doi: 10.1093/imrn/rnu243

    work page doi:10.1093/imrn/rnu243 2015

  8. [8]

    and Vershynin, R

    Rudelson, M. and Vershynin, R. The Littlewood-Offord problem and invertibility of random matrices.Adv. Math.218(2) (2008), 600–633.doi:10.1016/j.aim.2008.01. 010

    work page doi:10.1016/j.aim.2008.01 2008

  9. [9]

    and Vu, V

    Tao, T. and Vu, V. On random±1 matrices: singularity and determinant.Random Structures Algorithms28(1) (2006), 1–23.doi:10.1002/rsa.20109

    work page doi:10.1002/rsa.20109 2006

  10. [10]

    and Vu, V

    Tao, T. and Vu, V. On the singularity probability of random Bernoulli matrices.J. Amer. Math. Soc.20(3) (2007), 603–628.doi:10.1090/S0894-0347-07-00555-3. 9

    work page doi:10.1090/s0894-0347-07-00555-3 2007

  11. [11]

    and Vu, V.H

    Tao, T. and Vu, V.H. Inverse Littlewood-Offord theorems and the condition number of random discrete matrices.Ann. of Math. (2)169(2) (2009), 595–632.doi:10.4007/ annals.2009.169.595

    2009

  12. [12]

    Singularity of random Bernoulli matrices.Ann

    Tikhomirov, K. Singularity of random Bernoulli matrices.Ann. of Math. (2)191(2) (2020), 593–634.doi:10.4007/annals.2020.191.2.6

    work page doi:10.4007/annals.2020.191.2.6 2020

  13. [13]

    Inversion of Randomness

    Vu, V.H. Recent progress in combinatorial random matrix theory.Probab. Surv.18 (2021), 179–200.doi:10.1214/20-ps346. AppendixA.Inversion of randomness In the appendix, we briefly explain how “Inversion of Randomness” argument in Tikhomirov

    work page doi:10.1214/20-ps346 2021

  14. [14]

    We first introduce the basic framework of Tikhomirov’s approach

    can be used to improve the upper bound of the probability to match that in Proposition 5.2. We first introduce the basic framework of Tikhomirov’s approach. LetN, n≥1 be some integers, and letδ∈(0,1] andK≥1 be some real numbers. We say that a subsetA ⊂Z n is (N, n, K, δ)-admissible if • A=A 1 ×A 2 ×· · ·×A n, where everyA i (i= 1,2, . . . , n) is an origi...