On the singularity probability of random circulant Bernoulli matrices

Niklas Miller

REVIEW 2 major objections 3 minor 13 references

On the singularity probability of random circulant Bernoulli matrices

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The singularity probability of a random circulant Bernoulli matrix is asymptotically a power law whose exponent is set by the smallest prime divisor of n.

desk verdict Main theorem likely true and new, but Proposition 2's proof has a false pointwise dominance claim; gap is repairable but current proof incomplete. read the letter →

arxiv 2411.17577 v1 pith:MRXEZN6X submitted 2024-11-26 math.CO math.PR

Niklas Miller This is my paper · ORCID

classification math.COmath.PR MSC 60B2015B5211C08

keywords randomcirculantmatricesBernoullisingularityprobabilitycyclotomicpolynomialsbinomialdistributionsmallestprimedivisorasymptotic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper claims a complete asymptotic characterization of the probability that an $n\times n$ random circulant matrix with i.i.d. Bernoulli($q$) entries is singular. For every fixed $q\in(0,1)$, the singularity probability $P_q(n)$ is asymptotic to a sum of powers of the binomial probability $\varphi_q(k,n/p(n))$, raised to the $p(n)$-th power, where $p(n)$ is the smallest prime divisor of $n$. For composite $n$ this collapses to a power law: $P_q(n)\sim p^{-1/2}(p/(2\pi q(1-q)))^{(p-1)/2} n^{-(p-1)/2}$. The result resolves the question of how the singularity probability depends on the prime factorization of $n$: asymptotically, only the smallest prime factor matters.

What carries the argument

The machinery is the factorization of the circulant determinant through cyclotomic polynomials: $\det(C_n)=\prod_{j=0}^{n-1}\lambda_j$ with $\lambda_j=\sum_k c_k \zeta_n^{kj}$, so the matrix is singular iff $f(x)\equiv 0\pmod{\Phi_d(x)}$ for some $d\mid n$. The cyclic group structure reduces the event $\mathcal{P}_{d,n}$ to counting independent binomial folded coefficients $s_j^{(d)}$, each distributed as a binomial with parameters $n/d$ and $q$. The key exact identity is $P_q(p,n)=\sum_{k=0}^{n/p}\varphi_q(k,n/p)^p$ for primes $p$, and the proof shows every other divisor contributes negligibly relative to this term. Proposition 2, which estimates sums of the form $\sum_k \varphi_q(k,n)^{m(n)}$ for $m(n)=O(\sqrt{n})$, converts the sums into the explicit power law.

What would settle it

Take $n=p^2$ for primes $p=2,3,5,\ldots$ and fixed $q=1/2$; Lemma 2 gives an exact formula for $P_q(n)$. Check whether $P_q(p^2)$ divided by the Corollary 1 asymptote $p^{-1/2}(p/(2\pi q(1-q)))^{(p-1)/2} n^{-(p-1)/2}$ tends to 1 as $p$ grows. A persistent deviation would falsify the theorem on a sequence where the exact value is computable.

Watch

Extended reading notes

Core claim

The central discovery is that the determinant of a circulant Bernoulli matrix is singular exactly when the random polynomial $f(x)=\sum_{j=0}^{n-1} c_j x^j$ vanishes modulo some cyclotomic polynomial $\Phi_d(x)$ for a divisor $d\mid n$, and the dominant contribution comes from the smallest prime divisor. Concretely, Theorem 1 states that for fixed $q$, $P_q(n)\sim \sum_{k=0}^{n/p(n)} \varphi_q(k,n/p(n))^{p(n)}$ as $n\to\infty$, and when $n$ is prime this is the equality $P_q(n)=q^n+(1-q)^n$. For composite $n$ with smallest prime divisor $p$, Corollary 1 gives the explicit power-law decay $P_q(n)\sim \frac{1}{\sqrt{p}}(\frac{p}{2\pi q(1-q)})^{(p-1)/2} n^{-(p-1)/2}$. The signed version $P_q^+(n)$ obeys the same asymptotics except for $q=1/2$ and even $n$, where it is $\sim \frac{2\sqrt{2}}{\sqrt{\pi n}}$.

Load-bearing premise

The proof assumes without proof or citation that every divisor $d \ge n^{1/2+\delta}$ of $n$ has $\phi(d) > n^{1/2+\delta/2}$; if $\phi(d)$ could be much smaller, the tail sum over large divisors might not be negligible.

Editorial extensions

If this is right

For all even $n$ and $q=1/2$, the singularity probability is asymptotic to $\sqrt{2/(\pi n)}$, refining the earlier $\Theta(1/\sqrt{n})$ bound for signed circulant matrices.
For a fixed prime $p$, along any sequence of composite $n$ whose smallest prime divisor is $p$, the singularity probability decays as $n^{-(p-1)/2}$; larger $p$ means faster decay, while primes themselves have exponentially small singularity probability.
The asymptotic probability is determined solely by the smallest prime factor, so the detailed divisor structure of $n$ is irrelevant to leading order.
The signed ($\pm 1$) version has the same asymptotic behavior except for the single exceptional case $q=1/2$, $n$ even, where the probability is twice the $q=1/2$ binary case.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A natural testable extension would be to other group-structured matrices whose determinants factor through group characters, where the same cyclotomic-lattice counting may yield similar formulae keyed to the group's order.
One could extract a quantitative, non-asymptotic upper bound with explicit constants from the proof, which would be useful for finite-size applications in coding and signal processing.
Because the constant depends on $q$ only through $q(1-q)$, one could check in small exact computations whether the ratio $P_q(n)/n^{-(p-1)/2}$ is universal in $q$ up to that factor.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Read the Miller paper on circulant Bernoulli singularity. Short version: the main theorem is likely correct and is a real step forward — first exact asymptotic for P_q(n) with the smallest prime divisor p(n) controlling the rate, resolving Meckes's question. The proof idea is clean: cyclotomic factorization, block-sum representation for P_q(d,n), and de Moivre-Laplace estimates. The result is new, and the corollaries (including the even-n, q=1/2 case) are derived honestly.

But the proof as written has a genuine gap. In Section 4, Proposition 2's proof claims that φ_q(k,n) ≥ φ_q(k',n) for all k in the central interval I_{c,n} and k' outside it. That is false for skewed binomials. Take q=0.1, n=100, c=3.3, so I = {1,...,19}; then φ(20) > φ(1). The pointwise comparison is used to move from sums of powers to sums of first powers, and without it the lower bound on the ratio in Proposition 2 does not follow. Since Theorem 1's S3 case invokes Proposition 2 for bounded p(n), the main proof currently rests on an unproven lemma. The proposition itself is standard and the bounded-m cases can be fixed by a local-CLT window argument, but that argument is not in the paper.

There is also a smaller unproven assertion: the S0 estimate in Section 5 uses φ(d) > n^{1/2+δ/2} for d ≥ n^{1/2+δ}, without proof or reference. The standard bound φ(d) ≥ c d / log log d covers it for large n, so this is minor, but it should be stated.

Neither issue undermines my belief that the theorem is true. The proof is repairable, and the missing pieces are standard. But as it stands, the proof is incomplete, and a referee should ask for the fix rather than accept the current text.

This paper deserves a serious referee. The result matters for random structured matrix theory, and the derivation is mostly self-contained and elegant. I'd support sending it to peer review, with the expectation that the author supplies a correct proof of Proposition 2 and cites the totient bound.

For a reading group, it's a good paper to dissect: the gap is instructive. I'd cite it once the fix is public.

Best.

Referee Report

2 major / 3 minor

Summary. The paper claims a complete characterization, for every fixed q in (0,1), of the asymptotic singularity probability P_q(n) of an n×n circulant Bernoulli matrix with independent entries equal to 1 with probability q and 0 otherwise. The main result, Theorem 1, expresses P_q(n) asymptotically as the p(n)-th power of a binomial sum over k up to n/p(n), where p(n) is the smallest prime divisor of n. Corollary 1 derives an explicit power-law asymptotics, P_q(n) ~ p^{-1/2} (p/(2π q(1-q)))^{(p-1)/2} n^{-(p-1)/2}, for composite n with smallest prime divisor p. The proof strategy is based on the factorization of the circulant determinant into cyclotomic factors, an exact block-sum representation of the reduction modulo Φ_d(x), bounds on the individual probabilities P_q(d,n), and a de Moivre-Laplace analysis of sums of powers of binomial probabilities in Proposition 2. An analogous result for signed circulant matrices is given in Corollary 2.

Significance. If the proof is completed, the result is a clean and essentially complete asymptotic characterization for a structured random matrix model, going substantially beyond the known bounds for P_{1/2}^+(n). The main theorem is parameter-free: it gives an explicit asymptotic expression with no fitted constants, and the corollaries yield concrete, falsifiable rates depending only on the smallest prime divisor. The paper is also honest about the special cases where exact identities hold. The derivation is largely self-contained and uses standard tools (cyclotomic polynomials, binomial estimates), which makes the claimed result credible. However, a key inequality in the proof of Proposition 2 is false as stated, and this step is load-bearing for the main theorem, so the manuscript needs a substantive revision before it can be accepted.

major comments (2)

[Section 4, Proposition 2] The proof of Proposition 2 asserts: "φ_q(k,n) ≥ φ_q(k',n) for all k ∈ I_{c,n} and k' ∈ [0,n] \ I_{c,n}" and uses this to compare the ratio of sums of m-th powers to the ratio of sums of first powers. This pointwise dominance is false for q ≠ 1/2. For example, with q = 0.1, n = 100, and c chosen as in the proof, I_{c,n} = {1,...,19}; one has φ_q(20,100) ≈ 5.2·10^{-4} > φ_q(1,100) ≈ 2.95·10^{-4}. The inequality is used to derive the bound ∑_{k∈I} φ^m / ∑_{k=0}^n φ^m ≥ ∑_{k∈I} φ / ∑_{k=0}^n φ, which is essential for the Θ and asymptotic conclusions of the proposition. Since Theorem 1 uses Proposition 2 in the S3 case to lower-bound P_q(p(n),n), the proof of the main result is currently incomplete. The statement of Proposition 2 itself is standard and true, and a local-CLT window argument can repair the estimate, but that argument is not supplied in the manuscript.
[Section 5, S0 estimate] In the estimate of the sum over S0, the manuscript uses the bound φ(d) > n^{1/2 + δ/2} for every divisor d ≥ n^{1/2 + δ}, stated without proof or reference. This is a standard consequence of the lower bound φ(d) ≫ d / log log d, but as written the manuscript relies on an unproved number-theoretic input. The inequality is load-bearing because without it the sum over S0 of m_q^{φ(d)} may not be negligible relative to the lower bound for P_q(p(n),n). The authors should either prove the bound or, more simply, cite the standard estimate before using it.

minor comments (3)

[Abstract] The abstract contains a typo: "all v alues" should read "all values".
[Section 1] The notation p is used both for a generic prime and for the function p(n) mapping n to its smallest prime divisor. This can be confusing; consider using a different symbol for the function, or explicitly state that p(n) is the value of the function p at n.
[Section 5, S3 case] In the S3 estimate, the claim that "d and p(n) are bounded by 100" is correct but deserves a one-line justification: d composite and p(n)^2 ≤ d < 10p(n) forces p(n) < 10, so p(n) ∈ {2,3,5,7} and d < 100.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the singularity probability is derived from cyclotomic factorization and binomial estimates, not from its own conclusion.

full rationale

The paper's central task is to show P_q(n) is asymptotic to the sum over k of φ_q(k, n/p(n))^{p(n)}. That sum is, by the paper's own exact computation in equation (4), the probability P_q(p(n), n) that the random polynomial is divisible by Φ_{p(n)}. The theorem therefore asserts that the union-bound contribution of all other divisors is negligible, and the proof supplies direct estimates for the four divisor classes S0–S3 via Proposition 1, Lemma 4, and Proposition 2, with constants depending only on q. No parameter is fitted to the target probability, and the cited results (de Moivre–Laplace, Meckes's bounds for q = 1/2) are used as background or motivation, not as inputs that already contain the theorem. Proposition 2's asymptotic for sums of powers of binomial probabilities is argued from de Moivre–Laplace rather than imported from the conclusion; the citation to Farmer–Leth concerns only the special case m fixed and q = 1/2 and is not load-bearing. The only concern visible in the text is a correctness gap: Section 4 asserts the pointwise dominance φ_q(k, n) ≥ φ_q(k', n) for k in I_{c,n} and k' outside, which is not true for skewed binomials; but a false inequality is an error in the proof, not a reduction of the target to its inputs, so it does not affect the circularity score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters: q and the prime p(n) are inputs, and the binomial parameter is fixed. No invented entities. The proof relies on standard theorems from algebra and probability, plus two unproved technical estimates that are part of the proof rather than external evidence.

assumptions (5)

standard math The group determinant of a finite abelian group factors as a product of linear forms over C (Dedekind's theorem).
Used in Section 2, Theorem 2, to express the determinant of a circulant matrix as a product over characters and to reduce singularity to divisibility by cyclotomic polynomials.
standard math x^n-1 factors into cyclotomic polynomials Φ_d(x) over d|n, each with integer coefficients.
Used throughout to define the events P_{d,n} and to identify singularity with divisibility by some Φ_d.
standard math de Moivre-Laplace local limit theorem for binomial probabilities.
Cited as [1] and used in Lemma 3, Lemma 4, and Proposition 2 to estimate binomial probabilities and sums of their powers.
standard math Standard analytic number theory bounds: τ(n) = n^{o(1)} and φ(n) = n^{1-o(1)}, with φ(d) at least c d / log log d for divisors d used in S0.
Invoked in Section 5 without proof; the S0 estimate requires φ(d) > n^{1/2+δ/2}.
ad hoc to paper The binomial pmf is pointwise larger inside the central interval I_{c,n} than outside it.
Asserted in Section 4 in the proof of Proposition 2 to justify ignoring tail contributions; no proof is supplied.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the singularity probability of random circulant Bernoulli matrices." pith.science (2026). https://pith.science/paper/MRXEZN6X

@misc{pith2026241117577,
  author       = {Pith},
  title        = {Pith review of: On the singularity probability of random circulant Bernoulli matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MRXEZN6X}},
  note         = {Machine review of arXiv:2411.17577}
}

read the original abstract

A complete characterization of the asymptotic singularity probability of random circulant Bernoulli matrices is given for all values of the probability parameter.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Bal ´azs and B

M. Bal ´azs and B. T ´oth, Stirling’s formula and de Moivre-Laplace central limit theorem . https://people.maths.bris.ac.uk/~mb13434/ Stirling_DeMoivre_Laplace.pdf, 2014

work page 2014
[2]

Bose and J

A. Bose and J. Mitra , Limiting spectral distribution of a special circu- lant, Statistics & probability letters, 60 (2002), pp. 111–120. 14

work page 2002
[3]

Bourgain, V

J. Bourgain, V. H. Vu, and P. M. Wood , On the singularity probability of discrete random matrices , Journal of Functional Analysis, 258 (2010), pp. 559–603

work page 2010
[4]

Campos, M

M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe , The singularity probability of a random symmetric matrix is exp onentially small , Journal of the American Mathematical Society, (2024)

work page 2024
[5]

Catalan , R´ echerches sur les d´ eterminants, Bulletins de l’Acad´ emie Royale des Sciences, des Lettres et des Beaux-Arts de Belgique, 1 3 (1846)

E. Catalan , R´ echerches sur les d´ eterminants, Bulletins de l’Acad´ emie Royale des Sciences, des Lettres et des Beaux-Arts de Belgique, 1 3 (1846)

work page
[6]

J. D. F armer and S. C. Leth , An asymptotic formula for powers of binomial coeﬃcients , The Mathematical Gazette, 89 (2004), pp. 385–391

work page 2004
[7]

J. Kahn, J. Koml ´os, and E. Szemer ´ edi, On the probability that a ran- dom ±1-matrix is singular , Journal of the American Mathematical Society, 8 (1995), pp. 223–240

work page 1995
[8]

Kalman and J

D. Kalman and J. E. White , Polynomial equations and circulant ma- trices, The American Mathematical Monthly, 108 (2001), pp. 821–840

work page 2001

Show all 13 references

[9]

Koml ´os, On the determinant of (0-1) matrices , Studia Scientiarium Mathematicarum Hungarica, 2 (1967), pp

J. Koml ´os, On the determinant of (0-1) matrices , Studia Scientiarium Mathematicarum Hungarica, 2 (1967), pp. 7–21

1967
[10]

M. W. Meckes , Some results on random circulant matrices , in High di- mensional probability V: the Luminy volume, vol. 5, Institute of Math e- matical Statistics, 2009, pp. 213–224

2009
[11]

Tao and V

T. Tao and V. Vu , On random ±1 matrices: singularity and determinant , in Proceedings of the thirty-seventh annual ACM symposium on The ory of computing, 2005, pp. 431–440

2005
[12]

Tao and V

T. Tao and V. Vu , On the singularity probability of random Bernoulli ma- trices, Journal of the American Mathematical Society, 20 (2007), pp. 6 03– 628

2007
[13]

Tikhomirov , Singularity of random Bernoulli matrices , Annals of Mathematics, 191 (2020), pp

K. Tikhomirov , Singularity of random Bernoulli matrices , Annals of Mathematics, 191 (2020), pp. 593–634. 15

2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Bal ´azs and B

M. Bal ´azs and B. T ´oth, Stirling’s formula and de Moivre-Laplace central limit theorem . https://people.maths.bris.ac.uk/~mb13434/ Stirling_DeMoivre_Laplace.pdf, 2014

work page 2014

[2] [2]

Bose and J

A. Bose and J. Mitra , Limiting spectral distribution of a special circu- lant, Statistics & probability letters, 60 (2002), pp. 111–120. 14

work page 2002

[3] [3]

Bourgain, V

J. Bourgain, V. H. Vu, and P. M. Wood , On the singularity probability of discrete random matrices , Journal of Functional Analysis, 258 (2010), pp. 559–603

work page 2010

[4] [4]

Campos, M

M. Campos, M. Jenssen, M. Michelen, and J. Sahasrabudhe , The singularity probability of a random symmetric matrix is exp onentially small , Journal of the American Mathematical Society, (2024)

work page 2024

[5] [5]

Catalan , R´ echerches sur les d´ eterminants, Bulletins de l’Acad´ emie Royale des Sciences, des Lettres et des Beaux-Arts de Belgique, 1 3 (1846)

E. Catalan , R´ echerches sur les d´ eterminants, Bulletins de l’Acad´ emie Royale des Sciences, des Lettres et des Beaux-Arts de Belgique, 1 3 (1846)

work page

[6] [6]

J. D. F armer and S. C. Leth , An asymptotic formula for powers of binomial coeﬃcients , The Mathematical Gazette, 89 (2004), pp. 385–391

work page 2004

[7] [7]

J. Kahn, J. Koml ´os, and E. Szemer ´ edi, On the probability that a ran- dom ±1-matrix is singular , Journal of the American Mathematical Society, 8 (1995), pp. 223–240

work page 1995

[8] [8]

Kalman and J

D. Kalman and J. E. White , Polynomial equations and circulant ma- trices, The American Mathematical Monthly, 108 (2001), pp. 821–840

work page 2001