{"id":"92f865ea-0580-4f45-8af3-7c8202427b49","arxiv_id":"1908.11255","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For any fixed n×n complex matrix of norm up to 2^{n^0.001}, the least singular value of the matrix plus i.i.d. centered unit-variance complex noise is smaller than η with probability at most C(ξ) α, for α as small as 2^{-n^0.001}.","lead":"A new proof shows that adding random noise to a fixed matrix with enormous norm makes its smallest singular value very unlikely to be near zero, improving earlier smoothed-analysis bounds. The method avoids heavy additive-combinatorics machinery and instead counts Gaussian integer vectors, which may help other random matrix problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.3 is applied with p=2^{n^0.04} even though its stated hypothesis requires p ≤ 2n/s = 2n^{0.1}; the application is outside the theorem as written, and this large p is essential for the mod-p injection.","rationale":"The reader's weakest assumption pointed to Proposition 4.16 and the proof of Theorem 1.3 as load-bearing, which is correct. However, the specific failure mode I identified is not the one the reader emphasized. The reader noted that the local density ρ = 2^{-ℓ}/(128 n^{0.30}) must lie in the lower-bound regime ρ ≥ C_{1.3} max{e^{-s/k}, s^{-k/4}}; that condition does hold for the parameters used. The more serious issue is that Theorem 1.3 is stated with an upper bound on p, p ≤ 2n/s, and the application uses p = 2^{n^{0.04}}, which violates this bound. Since the entire reduction from the sphere to Gaussian integer vectors depends on the mod-p counting bound being injective on the relevant integer vectors, and since injectivity requires p to exceed the coordinate sup-norm bound 2^{n^{0.01}}, the contradiction between the theorem's hypothesis and the application's parameter regime is a genuine gap as written. The proof of Theorem 1.3 in Section 5 does not visibly use the upper bound, so the likely resolution is a corrected theorem statement; but until that correction is made and verified, the main claim is conditional. This aligns with the reader's CONDITIONAL verdict, though for a different and more substantive reason than the missing citation.","tokens_in":32187,"tokens_out":17696,"duration_ms":146289,"concrete_test":"Systematically check every step of the proof of Theorem 1.3 (Section 5, Steps 1-6 and Appendix A) for any argument that requires p ≤ 2n/s. If no such step exists, correct the statement of Theorem 1.3 by deleting or weakening the upper bound p ≤ 2n/s and confirm that the proof still goes through. Separately, test the alternative: re-run Proposition 4.16 with p chosen to satisfy p ≤ 2n^{0.1}; if the injectivity argument fails because integer coordinates can be as large as 2^{n^{0.01}} > p/2, this confirms that the large p = 2^{n^{0.04}} is essential and the theorem statement must be fixed for the main theorem to hold as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Proposition 4.16 (and its warm-up analogue Proposition 3.15) invokes Theorem 1.3 with parameters s=n^{0.9}, k=n^{0.1}, and p=2^{n^{0.04}}. However, Theorem 1.3 as stated requires the odd prime p to satisfy 2n/s ≥ p ≥ C_{1.3}ρ^{-1}. With s=n^{0.9}, the upper bound is 2n/s = 2n^{0.1}, while p=2^{n^{0.04}} is vastly larger. Thus the application violates a stated hypothesis of the counting theorem. This is not cosmetic: the large choice of p is used later in the same propositions to assert that the reduction map φ_p is injective on the approximating integer vectors, whose coordinates are only bounded by 2^{n^{0.01}} (see Proposition 4.16, 'each coordinate of v'' is an integer with absolute value at most ... ≪ 2^{n^{0.01}}'). If one were to respect the stated upper bound and choose p ≤ 2n^{0.1}, injectivity could fail because the integer coordinates can exceed p/2, so the counting bound on φ_p(V^ρ) would not transfer to ~R_{j,ℓ}(β). The proof of Theorem 1.3 in Section 5 never appears to use the upper bound p ≤ 2n/s, which suggests the statement may contain a typo; but as written, the main theorem's proof relies on applying a theorem outside its hypotheses. A referee must either remove or relax the upper-bound hypothesis in Theorem 1.3 (and verify the proof of Section 5), or supply an alternative argument that permits the large p required for injectivity.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the lower tail of the smallest singular value of an n-by-n matrix M_n = M + N_n, where M is a fixed complex matrix and N_n has i.i.d. entries distributed as an arbitrary complex random variable with mean 0 and variance 1. The main result, Theorem 1.1, gives Pr(s_n(M_n) <= eta) <= C_1.1 alpha for alpha as small as exp(-n^0.001) and for M with ||M|| <= exp(n^0.001), with eta subject to a quantitative upper bound. This improves on the Tao--Vu smoothed-analysis estimates in the allowed size of M and in the error probability. The proof avoids inverse Littlewood--Offord theorems and avoids serious net constructions; instead, it reduces the problem to counting Gaussian integer vectors near rich vectors and proves a counting theorem, Theorem 1.3, for general complex random variables. A subgaussian warm-up is given in Section 3, the general reduction in Section 4, and the proof of Theorem 1.3 in Section 5.","tokens_in":32578,"tokens_out":24865,"duration_ms":236785,"significance":"If the proof is correct, the paper is a substantial advance: it extends the smoothed-analysis regime for the least singular value from polynomial ||M|| to exponentially large ||M||, gives a probability bound exp(-n^c)-style even for Bernoulli noise, and provides a combinatorial route that avoids both inverse Littlewood--Offord structure theorems and nets. The extension of the counting problem in inverse Littlewood--Offord theory to general complex random variables (Theorem 1.3) is a useful contribution in its own right. The paper is clearly written and the reduction from the complex sphere to Gaussian integer vectors is a genuinely different approach. However, as detailed below, there is a load-bearing mismatch between the statement of Theorem 1.3 and its application, and a related gap in the proof of Theorem 1.3 for part of its stated range.","major_comments":[{"comment":"The application of Theorem 1.3 is outside the stated hypotheses. In Proposition 3.15 (and the same calculation used in Proposition 4.16), Theorem 1.3 is applied with s = n^0.9, k = n^0.1, and p = 2^{n^0.04}. The theorem as stated requires 2n/s >= p, but 2n/s = 2n^0.1, so p is exponentially larger than the permitted value. This is not a cosmetic issue: the proof immediately uses the large choice of p to assert that phi_p is injective on the approximating integer vectors, whose coordinates are bounded by about 2^{n^0.01} (see Proposition 4.16) or 2^{n^0.04} (Proposition 3.15). If one respected the stated upper bound and chose p <= 2n^0.1, the reduction map would not be injective on those vectors, and the counting bound on phi_p(V^rho) would not transfer back to R_{j,ell}(beta). The proof of Theorem 1.3 in Section 5 appears not to use the upper bound p <= 2n/s, which suggests that the upper bound in the statement may be a typo, but as written the main proof relies on applying a theorem outside its hypotheses. The authors should either remove or correct the upper-bound hypothesis in Theorem 1.3 and verify that the proof of Section 5 still goes through, or supply an alternative argument that permits the large p needed for injectivity.","section":"Section 5, Step 4, after Eq. (8)"},{"comment":"In the proof of Theorem 1.3, the displayed chain deduces |P'_M(I)| >> sqrt(M/m0)(|P'_m0(I)| - p) directly from the inequality |P'_{t^2 m}(I)| >= min{p^2, t|P'_m(I)| - tp}. This deduction is valid only when the un-truncated quantity does not exceed p^2; otherwise the minimum forces |P'_M(I)| = p^2, which can be smaller than the displayed lower bound. In terms of the later lower bound |P'_M(I)| >> sqrt(M) rho exp(m0/16) p^2, the missing condition is essentially rho sqrt(M) = O(1). This condition is not included in the hypotheses of Theorem 1.3, so the theorem as stated is not proved for all allowed rho (e.g. rho close to 1). The applications in the present paper satisfy rho sqrt(M) << 1 automatically, so this gap does not by itself invalidate Theorem 1.1, but the statement and proof of Theorem 1.3 need to be reconciled.","section":"Section 5, Step 4, after Eq. (8)"}],"minor_comments":[{"comment":"The Cauchy--Davenport theorem for F_p + iF_p is cited as '[?]'; a concrete reference is needed.","section":"Section 5, Step 4"},{"comment":"The proof of Proposition 3.7 is omitted with a pointer to Proposition 4.7; this is acceptable for a warm-up, but the text should state explicitly that Proposition 4.7 is the complete proof in the general case.","section":"Section 3, Proposition 3.7"},{"comment":"The notation switches between z and xi for the underlying random variable in the proof of Theorem 1.3; this should be made uniform.","section":"Section 5, Step 1 and Step 6"},{"comment":"The displayed lower bound 'rho >= C_{1.3}^{-1} 2^{-n^0.04/4}' does not match the hypotheses of Theorem 1.3 as used with s = n^0.9, k = n^0.1; the threshold should be compared with max{e^{-s/k}, s^{-k/4}} and the displayed expression should be corrected.","section":"Section 3.3"},{"comment":"The displayed application of Theorem 1.3 appears to omit the factor s in the denominator of the first term (5np^2/s)^s; this is likely a typesetting issue but should be fixed.","section":"Section 3.3, Proposition 3.15"}],"recommendation":"major_revision","confidential_remarks":"The p-bound mismatch in the application of Theorem 1.3 is the main issue; it looks reparable, either by correcting the statement of Theorem 1.3 or by adding a separate injectivity argument for large p. The Step 4 min{p^2, ...} gap is also fixable by adding an explicit hypothesis such as rho sqrt(M) = O(1), which the applications already satisfy. I therefore view the paper as promising but not yet ready in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real advance. It removes the polynomial-norm restriction in Tao–Vu's smoothed invertibility estimates, gives an exponential singularity tail for polynomial M, and the proof genuinely avoids inverse Littlewood–Offord theorems and sophisticated nets, replacing them with a direct counting argument. The extension of the Rademacher counting result to general complex variables (Theorem 1.3) is the technical core, and it is proved in detail in Section 5.\n\nWhat's good: Theorem 1.1 is cleanly stated, the reduction from the sphere to Gaussian integer vectors is carried out carefully, and the rich/poor vector decomposition plus counting argument is coherent. The dependence on the underlying distribution only through a C-goodness constant is nice. This paper deserves a serious referee.\n\nWhere it's soft:\n\n1. The stated Theorem 1.3 requires p <= 2n/s, but in Proposition 3.15 (and implicitly in Proposition 4.16) it is applied with s = n^0.9 and p = 2^{n^0.04}, so p is vastly larger than the allowed 2n^0.1. The large p is essential for the mod-p injection. The proof of Theorem 1.3 never appears to use the upper bound, so the likely fix is to drop or relax that hypothesis; but as written, the main proof relies on a theorem outside its stated hypotheses. A referee should confirm that the Section 5 proof works without the bound and adjust the statement.\n\n2. Minor: there is a missing Cauchy–Davenport citation ('[?]' in Step 4 of Section 5); Proposition 3.7's proof is deferred to Proposition 4.7, which is acceptable but worth flagging; and in Proposition 4.16 the notation slides between |V^rho| and |phi_p(V^rho)|, relying on injectivity for vectors with bounded coordinates—this should be made explicit.\n\nNone of these threaten the central idea, which looks sound. The counting theorem's proof is involved, but I did not see circularity; the use of [7] is for a lemma that is reproduced in the appendix, so that is normal.\n\nBottom line: this paper will matter for random matrix invertibility and smoothed analysis. Take it through review; the main fix is reconciling the p hypothesis in Theorem 1.3 with the application.","headline":"A genuinely new combinatorial approach to smoothed least-singular-value bounds, with strong results and one nontrivial formal gap: Theorem 1.3 as stated forbids the prime p used later in the proof.","tokens_in":33073,"tokens_out":13412,"would_cite":true,"duration_ms":110198,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","15B52"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exponential invertibility bounds for smoothed random matrices","keywords":["least singular value","smoothed analysis","random matrices","small-ball probability","Gaussian integer vectors","combinatorial counting","singularity probability"],"falsifier":"Set $\\xi$ to Bernoulli and $M$ to a fixed $n\\times n$ complex matrix with $\\|M\\|=2^{n^{0.001}}$, choose $\\alpha=2^{-n^{0.001}}$, and compute $\\Pr(s_n(M_n)\\le\\eta)$ for $\\eta$ at the threshold stated in Theorem 1.1; exceeding $C_{1.1}\\alpha$ would refute the theorem. A sharper falsifier targets Theorem 1.3 directly: take $s=n^{0.9}$, $k=n^{0.1}$, $p=2^{n^{0.04}}$, and $\\rho=2^{-\\ell}/(128n^{0.30})$ for $\\ell\\le\\log(\\beta^{-1})$, and check whether some collection $V^\\rho$ has more than $(5np^2/s)^s+(C\\rho^{-1}\\sqrt{s/k})^n$ distinct images under the mod-$p$ map.","tokens_in":31983,"feed_emoji":"🎲","tokens_out":10728,"duration_ms":94004,"temperature":0.7,"pith_summary":"The paper proves a quantitative lower-tail bound for the least singular value of an $n\\times n$ smoothed random matrix $M_n=M+N_n$: $M$ may be any fixed complex matrix with operator norm at most $2^{n^{0.001}}$, and $N_n$ has independent entries with mean 0 and variance 1. For any failure probability $\\alpha\\ge 2^{-n^{0.001}}$, it shows $\\Pr(s_n(M_n)\\le\\eta)\\le C\\alpha$ for all sufficiently small $\\eta$, with $C$ depending only on the entry distribution. This extends earlier smoothed-analysis estimates, which applied only to polynomially bounded $M$, and it upgrades the singularity probability from inverse-polynomial to exponentially small in a power of $n$ even for polynomially bounded $M$. The proof avoids inverse small-ball structure theorems and net constructions; instead it reduces the problem to counting Gaussian integer vectors and solves that counting problem by a combinatorial method over finite fields.","feed_headline":"Exponential invertibility bounds for smoothed random matrices","feed_subtitle":"A purely combinatorial proof beats polynomial bounds and handles exponentially large fixed matrices.","key_machinery":"The central object is the counting variant of the inverse small-ball problem. For Gaussian integer vectors $v\\in(\\mathbb Z+i\\mathbb Z)^n$ whose Levy concentration function (the maximum probability that $\\sum v_i\\xi_i$ falls in a small ball) is at least $\\rho$, Theorem 1.3 bounds the number of distinct vectors after reduction modulo a prime $p$ by $(5np^2/s)^s+(C_{1.3}\\rho^{-1}\\sqrt{s/k})^n$, provided $\\rho\\ge C_{1.3}\\max\\{e^{-s/k},s^{-k/4}\\}$. This counting bound carries the argument: rich unit vectors are rescaled until they nearly coincide with Gaussian integer vectors, Proposition 2.8 converts any Euclidean distance from the Gaussian integer lattice into exponential decay of the concentration function, and Proposition 4.16 bounds the number of approximating integer vectors in each scale class. The proof of Theorem 1.3 itself combines a Fourier anti-concentration step, sumset growth over $\\mathbb F_p+i\\mathbb F_p$, and a double-counting lemma (Theorem 5.4) that controls vectors admitting many balanced sign relations.","core_discovery":"On the paper's own terms, the discovery is Theorem 1.1: for any complex random variable with mean 0 and variance 1, any fixed complex matrix $M$ with $\\|M\\|\\le 2^{n^{0.001}}$, and any $\\alpha\\ge 2^{-n^{0.001}}$, the least singular value of $M_n=M+N_n$ satisfies $\\Pr(s_n(M_n)\\le\\eta)\\le C_{1.1}\\alpha$ whenever $\\eta\\le (C_{1.1}(\\|M\\|+\\sqrt n)\\alpha^{-1}n^2)^{-300\\log(\\alpha^{-1})/\\log n}$. The same result recovers the earlier polynomial-$M$ bounds while broadening the valid range of $\\|M\\|$ to exponential in a small power of $n$, and it yields exponential-type bounds on the probability that a perturbed matrix is singular. The paper also isolates Theorem 1.3, a counting estimate for vectors whose small-ball probability is at least $\\rho$, as the key new tool; this estimate extends the combinatorial counting approach to arbitrary complex random variables and may stand on its own.","pith_inferences":["A natural extension is to push the norm bound beyond $2^{n^{0.001}}$: the paper notes the exponent is arbitrary, so one would expect the same reduction to work for $\\|M\\|\\le 2^{n^{c}}$ with any fixed $c<1$, at the cost of a worse dependence of $\\eta$ on $\\alpha$ and $\\|M\\|$.","The same rich-vector counting scheme might be coupled with existing geometric net arguments to yield typical-order bounds, for instance $\\eta\\sim n^{-1/2}$, for heavy-tailed or dependent-coordinate complex entries, a regime the current theorem does not address.","Because the proof reduces the problem to the size of $V^\\rho$ modulo $p$, a numerical enumeration of Gaussian integer vectors for moderate $n$ could directly test the counting estimate in Theorem 1.3 before the full theorem is invoked."],"forward_implications":["Any fixed matrix with operator norm up to $2^{n^{0.001}}$ is, after an independent variance-one perturbation, invertible with least singular value at least $\\eta$ except with probability $C\\alpha$; in particular, smoothed-analysis guarantees now cover exponentially large input matrices.","For polynomially bounded $M$, the probability that $M_n$ is singular is at most $C2^{-n^{0.001}}$ up to the constant, so a random perturbation destroys exact singularity with exponentially high confidence.","Theorem 1.3 supplies a general complex-variable counting estimate for vectors with large small-ball probability, with no dependence on structural inverse theorems; it can be used as a drop-in tool in other union-bound arguments.","The proof demonstrates that the quantitative invertibility problem for smoothed random matrices can be solved through the discrete counting problem alone, without metric entropy nets or additive-combinatorial structure theory."],"supporting_citations":[{"why":"Supplies the previous smoothed-analysis bound for polynomially bounded M that Theorem 1.1 extends to exponentially large M.","marker":"[37]"},{"why":"Supplies the Fourier-analytic lemmas and pigeonholing scheme used to rescale rich vectors in the reduction.","marker":"[34]"},{"why":"Originates the combinatorial counting approach to inverse small-ball problems and supplies the double-counting template used in Theorem 5.4.","marker":"[7]"},{"why":"Gives the previous optimal inverse small-ball estimates that Theorem 1.3 improves by avoiding structural theorems.","marker":"[21]"},{"why":"Supplies the geometric-net baseline and the single-vector invertibility estimate used in poor-vector elimination.","marker":"[25]"},{"why":"Provides the Fourier anti-concentration technique used in the proof of Theorem 1.3.","marker":"[9]"},{"why":"Develops the rounding argument and row-regularization lemma that the general case adapts to large operator norms.","marker":"[11]"},{"why":"Provides the conditioning argument used to control poor vectors in the general proof.","marker":"[17]"}],"fun_headline_variants":["Combinatorial proof cracks random matrix invertibility","Beyond polynomial: combinatorial invertibility bounds","Exponential bounds for smoothed random matrices","Combinatorial counting beats polynomial limits","Huge perturbations tamed by pure combinatorics"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the number of Gaussian integer vectors with small-ball probability at least $\\rho$ stays exponentially small after reduction modulo a prime, in the precise sense of Theorem 1.3; if the true count were even slightly larger, the union bound over approximating rich vectors in Proposition 4.16 would fail and the main theorem would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Combinatorial proof cracks random matrix invertibility","Beyond polynomial: combinatorial invertibility bounds","Exponential bounds for smoothed random matrices","Combinatorial counting beats polynomial limits","Huge perturbations tamed by pure combinatorics"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000833,"raw_usage":{"total_tokens":3739,"prompt_tokens":1149,"completion_tokens":2590,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":765,"completion_tokens_details":{"reasoning_tokens":2525}},"tokens_in":765,"tokens_out":2590,"duration_ms":17813,"temperature":1.0,"reasoning_tokens":2525,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:20:41.494041+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $\\xi$ to Bernoulli and $M$ to a fixed $n\\times n$ complex matrix with $\\|M\\|=2^{n^{0.001}}$, choose $\\alpha=2^{-n^{0.001}}$, and compute $\\Pr(s_n(M_n)\\le\\eta)$ for $\\eta$ at the threshold stated in Theorem 1.1; exceeding $C_{1.1}\\alpha$ would refute the theorem. A sharper falsifier targets Theorem 1.3 directly: take $s=n^{0.9}$, $k=n^{0.1}$, $p=2^{n^{0.04}}$, and $\\rho=2^{-\\ell}/(128n^{0.30})$ for $\\ell\\le\\log(\\beta^{-1})$, and check whether some collection $V^\\rho$ has more than $(5np^2/s)^s+(C\\rho^{-1}\\sqrt{s/k})^n$ distinct images under the mod-$p$ map.","supporting_citations":[{"cited_title":"Tao and V","cited_arxiv_id":null,"evidence_quote":"Supplies the previous smoothed-analysis bound for polynomially bounded M that Theorem 1.1 extends to exponentially large M."},{"cited_title":"Tao and V","cited_arxiv_id":null,"evidence_quote":"Supplies the Fourier-analytic lemmas and pigeonholing scheme used to rescale rich vectors in the reduction."},{"cited_title":"On the counting problem in inverse Littlewood--Offord theory","cited_arxiv_id":"1904.10425","evidence_quote":"Originates the combinatorial counting approach to inverse small-ball problems and supplies the double-counting template used in Theorem 5.4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the previous optimal inverse small-ball estimates that Theorem 1.3 improves by avoiding structural theorems."},{"cited_title":"Rudelson and R","cited_arxiv_id":null,"evidence_quote":"Supplies the geometric-net baseline and the single-vector invertibility estimate used in poor-vector elimination."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Fourier anti-concentration technique used in the proof of Theorem 1.3."},{"cited_title":"The strong circular law: a combinatorial view","cited_arxiv_id":"1904.11108","evidence_quote":"Develops the rounding argument and row-regularization lemma that the general case adapts to large operator norms."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the conditioning argument used to control poor vectors in the general proof."}],"review_version":1}