{"id":"64bb193e-c8cf-49de-9bfb-3e66bf2f6a46","arxiv_id":"2411.17577","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The singularity probability of an n by n random circulant Bernoulli matrix is asymptotically the p-th power sum of binomial probabilities, where p is the smallest prime divisor of n.","lead":"This paper gives the exact asymptotic probability that a random circulant Bernoulli matrix is singular, showing the rate is set by the smallest prime factor of the matrix size. The result settles an open question from earlier work on random circulant matrices and provides a clean power law for every fixed prime.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Proposition 2 relies on a false pointwise dominance claim (k∈I implies φ(k)≥φ(k') for k'∉I); for q=0.1, n=100, I=[1,19], φ(20)>φ(1). Since Theorem 1 invokes Proposition 2 in the S3 estimate, the main proof is currently incomplete.","rationale":"After reviewing the full proof, the main theorem's strategy is sound: the divisor union bound is partitioned correctly, and the S0–S3 estimates are largely valid. The S0 bound uses the totient lower bound φ(d) ≥ c d/log log d, which is standard but uncited; this is easily repaired. The S1 and S2 computations check out. The most insecure step is in Proposition 2, where the claim that the central interval I dominates the tail pointwise is false for skewed binomial distributions. This step is load-bearing because Proposition 2 is invoked in the S3 lower bound and in Corollaries 1 and 2. The asymptotic formula in Proposition 2 is nevertheless true, and for the bounded p(n) occurring in S3 a direct local-CLT argument over a window of width √(n/p) supplies the needed lower bound; however, the paper does not provide it. Hence the appropriate verdict is CONDITIONAL, exactly as the reader concluded; the condition is that the cited proof gap be repaired.","tokens_in":118,"tokens_out":32259,"duration_ms":327604,"concrete_test":"Evaluate the binomial masses for q=0.1, n=100 with c=3.3: compute φ_q(1,100) and φ_q(20,100). Since |1-10|≤9.9 and |20-10|=10>9.9, the former is in I and the latter is not; if φ(20)>φ(1), the pointwise dominance assertion in the proof of Proposition 2 is false. To check whether the weaker ratio inequality survives, compute R_m = ∑_{k=1}^{19}φ_q(k,100)^m / ∑_{k=0}^{100}φ_q(k,100)^m for m=1,2,3 and verify whether R_m ≥ R_1; if not, Proposition 2's proof strategy collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4, the proof of Proposition 2 asserts: \"φ_q(k,n) ≥ φ_q(k',n) for all k∈I_{c,n} and k'∉I_{c,n}\". This pointwise dominance is used to derive ∑_{k∈I} φ^m / ∑_{k=0}^{n} φ^m ≥ ∑_{k∈I} φ / ∑_{k=0}^{n} φ, an essential step in the Θ and asymptotic bounds. The claim is false for skewed binomials. Take q=0.1, n=100. With c chosen so that ∫_{-c}^{c}(2π)^{-1/2}e^{-t^2/2}dt ≥ 1-ε, e.g., c=3.3, the interval is I={1,...,19} (mean 10, σ=3). Then φ_q(1,100)=100·0.1·0.9^99 ≈ 2.95e-4, while φ_q(20,100)=C(100,20)0.1^20 0.9^80 ≈ 5.2e-4, so the exterior point 20 has larger mass than the interior point 1. The failure is not a small-n artifact: for q≠1/2 the binomial's skewness shifts the two boundaries by O(1/√n), while the step to the adjacent exterior point is also O(1/√n), so the ordering can reverse for all large n. Because Theorem 1 uses Proposition 2 to lower-bound P_q(p(n),n) in the S3 case, and Corollaries 1 and 2 rely on it, the present proof of the main results has a genuine gap. The proposition's statement is standard and true, and the bounded-m case in S3 can be recovered by a local-CLT window argument, but that argument is not supplied.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":37,"tokens_out":3545,"duration_ms":105109,"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":[{"comment":"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":"Section 4, Proposition 2"},{"comment":"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.","section":"Section 5, S0 estimate"}],"minor_comments":[{"comment":"The abstract contains a typo: \"all v alues\" should read \"all values\".","section":"Abstract"},{"comment":"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":"Section 1"},{"comment":"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.","section":"Section 5, S3 case"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a natural question in random matrix theory and the main theorem is likely correct. The central gap is localized: the false comparison in Proposition 2 can likely be repaired with a standard local central limit theorem window argument, and the totient bound in S0 is a routine citation. I therefore recommend major revision rather than rejection. The authors should also check that all constants in the S1 and S2 estimates are justified for all q ∈ (0,1), since the proof currently elides some dependencies on q in the notation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead 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.\n\nBut 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.\n\nThere 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.\n\nNeither 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.\n\nThis 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.\n\nFor a reading group, it's a good paper to dissect: the gap is instructive. I'd cite it once the fix is public.\n\nBest.","headline":"Main theorem likely true and new, but Proposition 2's proof has a false pointwise dominance claim; gap is repairable but current proof incomplete.","tokens_in":12720,"tokens_out":6003,"would_cite":true,"duration_ms":58333,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","15B52","11C08"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["random circulant matrices","Bernoulli matrices","singularity probability","cyclotomic polynomials","binomial distribution","smallest prime divisor","asymptotic probability"],"falsifier":"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.","tokens_in":11554,"feed_emoji":"🎲","tokens_out":10943,"duration_ms":92618,"temperature":0.7,"pith_summary":"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.","feed_headline":"Smallest prime factor sets the singularity odds for circulant matrices","feed_subtitle":"For composite n, the singularity probability decays as a power law set by the smallest prime factor.","key_machinery":"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.","core_discovery":"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}}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the local limit theorem for binomial probabilities used to estimate the maximum and the sums of powers of $\\varphi_q$.","marker":"[1]"},{"why":"Gives the asymptotic formula for sums of powers of binomial coefficients that Proposition 2 generalizes.","marker":"[6]"},{"why":"Provides the prior bound for signed circulant matrices and poses the question about the role of the prime factorization that the paper answers.","marker":"[10]"}],"fun_headline_variants":["Smallest prime drives singularity decay in circulant Bernoulli","Power-law singularity odds fixed by least prime divisor","Circulant Bernoulli singularity: exact asymptotics for all q","Random circulant matrices: singularity rates set by prime factors","Least prime factor governs circulant determinant singularity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Smallest prime drives singularity decay in circulant Bernoulli","Power-law singularity odds fixed by least prime divisor","Circulant Bernoulli singularity: exact asymptotics for all q","Random circulant matrices: singularity rates set by prime factors","Least prime factor governs circulant determinant singularity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000148,"raw_usage":{"total_tokens":1109,"prompt_tokens":785,"completion_tokens":324,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":401,"completion_tokens_details":{"reasoning_tokens":249}},"tokens_in":401,"tokens_out":324,"duration_ms":4307,"temperature":1.0,"reasoning_tokens":249,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:01:32.805893+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Bal ´azs and B","cited_arxiv_id":null,"evidence_quote":"Supplies the local limit theorem for binomial probabilities used to estimate the maximum and the sums of powers of $\\varphi_q$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the asymptotic formula for sums of powers of binomial coefficients that Proposition 2 generalizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the prior bound for signed circulant matrices and poses the question about the role of the prime factorization that the paper answers."}],"review_version":1}