{"id":"a446e6ae-4e16-4cf5-be7f-6c73d9adac27","arxiv_id":"1909.02089","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"If a quadratic Bernoulli polynomial has a point probability much larger than 1/n, it is close to a quadratic form of low rank; a consequence bounds edge-count point probabilities in Ramsey graphs by n^{-1+o(1)}.","lead":"The authors prove new inverse Littlewood-Offord theorems: a quadratic polynomial of independent coin flips that lands on one value unusually often must be close to a low-rank quadratic form. They apply this to Ramsey graphs, showing the edge count of a random induced subset never concentrates beyond n^{-1+o(1)} per value.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the inverse theorems are internally consistent, and the Ramsey application's dependence on Lemma 2.2 is a standard regularity fact.","rationale":"The reader's weakest-assumption pick, Lemma 2.2, is indeed the only genuinely external ingredient, and it is confined to the Ramsey application. I agree that Theorem 1.3 would fail if the Ω(n^{4r}) induced-perfect-matching count were materially weaker. But this is a well-established regularity-lemma consequence, and the main algebraic inverse theorems do not rely on it. I found no gap in the core Fourier-decoupling argument or in the reduction from robust linear independence to symmetric low-rank approximation; the field cases R, C, and Q are handled consistently via real projections and finite-set S* construction. The proof is long, but the key estimates are internally coherent and the constants are used in the right places. Therefore the reader's ACCEPT verdict should stand unchanged, with the caveat that the Ramsey application inherits the correctness of the cited regularity-based counting lemma.","tokens_in":36759,"tokens_out":57177,"duration_ms":576512,"concrete_test":"Check the cited Conlon-Fox counting lemma ([10, Lemma 5.12]) and confirm it supplies Ω(m^h) induced copies of every fixed h-vertex graph from an ε-regular induced subgraph of density bounded away from 0 and 1; if the lemma only guarantees copies of a restricted class, rerun Claim 2.4 with H a perfect matching to see whether Ω(m^{2r}) strong tuples still follow.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central inverse theorems (Theorem 1.1 and Theorem 1.2) appear internally consistent. I checked the Fourier-decoupling estimate in Lemma 3.2, in particular the p(s,t) bound in Claim 3.7 and the final Esséen integration: the exponent n^{-r/(r+2)} follows from integrating t^{-r/2} on [1/n,1/sqrt(n)] and t^{r/2} on [1/sqrt(n),1/s], and the point-to-interval step is legitimate. I also checked the robust linear-independence reduction in Sections 5-7; Claims 7.1-7.5 and the finite-set adaptation in Lemma 5.7 are coherent. The only external dependency is Lemma 2.2, used solely for the Ramsey application (Theorem 1.3): Claim 2.4 would need an Ω(n^{4r}) induced-perfect-matching count to produce Ω(m^{2r}) strong tuples, and a weaker (say n^{4r-o(1)}) count would break the McDiarmid concentration step. However, Lemma 2.2 is a standard consequence of Szemerédi regularity and the counting lemma for ε-regular graphs, and it does not affect the main inverse theorems. I have no load-bearing objection.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves algebraic inverse theorems for the quadratic Littlewood–Offord problem. Theorem 1.1 states that if a quadratic polynomial f over F∈{C,R,Q} with coefficients of modulus at most 1 has point probability at least C(log n)^{r/2}/n^{1-2/(r+2)} for some r≥3, then f is within coefficient L1 distance εn^2 of a quadratic form of rank strictly less than r. Theorem 1.2 gives the analogous Hamming-distance conclusion when the degree-2 coefficients lie in a finite set S. Theorem 1.3 applies Theorem 1.2 to show that in any C-Ramsey graph, the number X of edges induced by a uniformly random k-vertex subset, with k=Θ(n), satisfies Pr(X=x)≤n^{-1+o(1)}. The proof strategy is a Fourier-decoupling anti-concentration lemma (Lemma 3.2), a complex-to-real reduction via random phases (Lemma 4.1), and a substantial development of robust linear-independence tools (Sections 6–7) culminating in symmetric low-rank approximation statements (Lemmas 5.5 and 5.7).","tokens_in":36973,"tokens_out":33377,"duration_ms":301485,"significance":"If correct, these are the first inverse theorems of this strength for quadratic Littlewood–Offord problems, giving structural conclusions at concentration levels well above the 1/√n barrier and making significant progress toward Costello's conjecture in the algebraic direction. The technical apparatus—decoupling inside the characteristic function, robust linear independence, and simultaneous symmetric low-rank approximation—is likely to be independently useful. The Ramsey application is a clean and nontrivial consequence. I explicitly note that the central inverse theorems (Theorems 1.1 and 1.2) do not rely on Lemma 2.2; that lemma is used only for the Ramsey application and is a standard regularity-method counting statement. The proofs of the key technical lemmas are complete, and I found no load-bearing error in the central derivation.","major_comments":[],"minor_comments":[{"comment":"In the proof of Claim 7.5, the same expression ‖(A′−B′)I‖1 is written twice in consecutive displayed equations, and the identity ‖(H−A′)I‖1=‖(H−A′)I‖1 also appears twice; one member of each pair should refer to the column-indexed submatrix rather than the row-indexed submatrix. Please clarify the notation distinguishing row and column submatrices in this claim.","section":"§7.1, Claim 7.5"},{"comment":"In the proof of Lemma 4.1, the definition of p(z) and the displayed formula for det Re(e^{iθ}A) should involve the conjugate matrix \\overline{A} rather than A, since Re(e^{iθ}A)=(e^{iθ}A+e^{-iθ}\\overline{A})/2. As written, both displays are missing the conjugation.","section":"§4, Lemma 4.1"},{"comment":"In the final Esséen integration, the limits of the first integral are written from 1/√n to 1/n but should be from 1/n to 1/√n, and the outer integral should read from −1/s to 1/s rather than from 1/s to −1/s. The numerical evaluation is correct under the intended limits.","section":"§3, proof of Lemma 3.2"},{"comment":"Several exponents such as α(6r)^{q−r} and α(6r)^{−r} are ambiguous in the typeset text and can be misread as products rather than nested powers; using explicit braces, e.g., α^{(6r)^{q−r}}, would improve readability.","section":"Throughout"}],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper deserves a serious review and should be accepted. It proves the first algebraic inverse theorems for the quadratic Littlewood–Offord problem with thresholds near 1/n, and it answers the Ramsey edge-statistics question from Kwan–Sudakov–Tran up to an n^{o(1)} factor. The main technique, decoupling the characteristic function rather than the point probability, is genuine and avoids the usual square-root loss. That is the real contribution.\n\nWhat's new: Theorems 1.1 and 1.2 are strictly stronger than Nguyen's coarse inverse theorem. The low-rank closeness in coefficient L1 distance (and in Hamming distance when the coefficients lie in a finite set) is new, and the threshold (log n)^{r/2}/n^{1-2/(r+2)} is essentially optimal in the sense that random-like quadratics have 1/n concentration. Theorem 1.3 gives n^{-1+o(1)} point probabilities for Ramsey edge statistics, asymptotically answering the KST question.\n\nI read the key steps: Lemma 3.2 is the engine, and the Esséen integration with the p(s,t) bound checks out. The robust linear independence lemmas in Sections 5–7 are carefully done. The finite-set adaptation for Theorem 1.2 is a clever twist and necessary for the Ramsey application. No load-bearing circularity: self-citations are contextual only.\n\nSoft spots: the Ramsey application depends on Lemma 2.2, the standard induced-copy count from Szemerédi regularity. That's fine, but it means Theorem 1.3 inherits the regularity method. The paper itself notes the results aren't optimal: the log factors probably shouldn't be there, and removing the bounded-coefficient restriction would be a step toward Costello's conjecture. There are a couple of duplicated expressions in Claim 7.5 that look like typos; they don't change the argument.\n\nBottom line: the math is solid, the new technique is real, and the Ramsey application is clean. This should go to peer review and be published. I'd cite it and bring it to reading group.","headline":"A substantial paper: new algebraic inverse theorems for the quadratic Littlewood–Offord problem at near-1/n thresholds, backed by a genuinely new Fourier-decoupling technique and a clean Ramsey application; the proofs hold up.","tokens_in":37550,"tokens_out":2114,"would_cite":true,"duration_ms":20513,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","05C55","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Unusually high point probabilities for quadratic polynomials force near-low-rank algebraic structure, and this yields an optimal anti-concentration bound for edge counts in Ramsey graphs.","keywords":["Littlewood-Offord problem","quadratic polynomials","anti-concentration","inverse theorems","low-rank quadratic forms","Ramsey graphs","edge-statistics","Rademacher variables"],"falsifier":"A sequence of quadratic polynomials with all coefficients in $\\{-1,0,1\\}$ whose exact point probabilities exceed $C(\\log n)^{r/2}n^{-1+2/(r+2)}$ for some fixed $r\\ge3$, while their coefficient matrices stay at $\\ell^1$-distance at least $\\varepsilon n^2$ from every symmetric matrix of rank less than $r$, would refute Theorems 1.1 and 1.2. A concrete starting point is exhaustive search over small $n$ with coefficients in $\\{0,1\\}$, computing both the maximum point probability and the minimal $\\ell^1$ distance to low-rank symmetric matrices.","tokens_in":36521,"feed_emoji":"🎲","tokens_out":10847,"duration_ms":107367,"temperature":0.7,"pith_summary":"This paper proves an inverse theorem for the quadratic Littlewood–Offord problem: if a quadratic polynomial in independent fair coin flips has an unusually high chance of taking one particular value, then the polynomial must be algebraically close to a low-rank quadratic form. The threshold is roughly $n^{-1}$, the natural scale for a quadratic with bounded coefficients, and the paper proves both an $\\ell^1$-coefficient version and a Hamming-distance version when the quadratic coefficients lie in a finite set. If the theorem is right, unusually strong concentration cannot occur without an algebraic reason: the polynomial is forced to sit near a form whose symmetric coefficient matrix has rank less than $r$. The paper also uses the finite-coefficient version to show that in every $C$-Ramsey graph, the number of edges in a random $k$-vertex subset has point probabilities at most $n^{-1+o(1)}$, asymptotically answering a question from earlier work on edge-statistics.","feed_headline":"High concentration in quadratic forms forces near-low-rank structure","feed_subtitle":"Point probabilities above 1/n can only come from low-rank algebraic forms, with a Ramsey graph payoff.","key_machinery":"The engine is a decoupling trick applied to the characteristic function of $f(\\xi)$: splitting the variables into two groups and subtracting an independent copy turns the quadratic polynomial into a linear one, with the usual square-root loss moved inside an integral where a sharp threshold in $|t|$ makes it negligible. The linear analysis then uses a multidimensional Littlewood–Offord theorem for robustly non-degenerate matrices, and Esséen's inequality converts the resulting Fourier decay into point-probability bounds. A separate layer of robust linear independence ($\\varepsilon$-independence) and a symmetric low-rank approximation lemma turn the condition 'far from a low-rank quadratic form' into the non-degeneracy that the Fourier argument requires. Here the rank of a quadratic form is the rank of its symmetric coefficient matrix, equivalently the minimum number of squares of linear forms needed to express it.","core_discovery":"The central claim is a rigidity principle: for a quadratic polynomial $f\\in F[x_1,\\ldots,x_n]$ with all coefficients of absolute value at most $1$, if $\\sup_x\\Pr(f(\\xi)=x)\\ge C(\\log n)^{r/2}n^{-1+2/(r+2)}$, then there is a quadratic form $h$ of rank strictly less than $r$ whose coefficients differ from those of $f$ by total absolute value at most $\\varepsilon n^2$. When the degree-$2$ coefficients of $f$ are drawn from a finite set, the same concentration forces $f$ and $h$ to differ in at most $\\varepsilon n^2$ coefficients. The statements hold over $\\mathbb{C}$, $\\mathbb{R}$, and $\\mathbb{Q}$, and in the finite-coefficient case $h$ can be chosen with coefficients in a finite set depending only on $r$ and the allowed coefficients. For the Ramsey application, the random edge count is represented as a quadratic polynomial whose coefficient matrix contains many full-rank $r\\times r$ submatrices, so it is far from every low-rank quadratic form, and Theorem 1.2 delivers the bound.","pith_inferences":["The two distance notions invite a computational test: for a candidate statistic, one can compute the robust rank of its coefficient matrix and compare the implied concentration bound with the true point probabilities, which could expose where the $\\ell^1$ approximation is too crude.","The proof does not obviously extend to degree $3$, since iterating the decoupling gives weaker control; testing the method on cubic forms with tensor-rank-type structure would show whether the low-rank conclusion is special to quadratics.","Removing the $o(1)$ in the Ramsey-graph bound would make the edge-count distribution exactly match the random-graph benchmark; a plausible route is to sharpen the symmetric low-rank approximation lemma from aggregate $\\ell^1$ control to control on almost every entry."],"forward_implications":["A quadratic polynomial with bounded coefficients whose point probabilities exceed $n^{-1+o(1)}$ must be within $\\varepsilon n^2$ coefficient-wise of a low-rank quadratic form, so strong concentration is a certificate of algebraic degeneracy.","With $r=3$, point probabilities much larger than $n^{-3/5}$ force the polynomial to be close to one that splits into linear factors over the complex numbers, the qualitative picture predicted by the earlier conjecture.","Every $C$-Ramsey graph has the property that the edge count of a uniformly random subset of size between $cn$ and $(1-c)n$ has point probabilities at most $n^{-1+o(1)}$, matching the random-graph benchmark up to the $o(1)$ term.","The finite-coefficient Hamming version gives a template for proving anti-concentration of graph statistics: exhibit many disjoint full-rank submatrices in the associated coefficient matrix, then invoke the inverse theorem."],"supporting_citations":[{"why":"Introduces the decoupling trick that Lemma 3.3 adapts to characteristic functions.","marker":"[12]"},{"why":"Supplies the multidimensional linear Littlewood–Offord bound (Theorem 3.5) used on the decoupled linear polynomial.","marker":"[24]"},{"why":"Provides the Esséen concentration inequality (Lemma 3.4) that converts Fourier decay into anti-concentration.","marker":"[46]"},{"why":"Provides the regularity and counting lemmas that produce many induced copies of every small graph in Ramsey graphs.","marker":"[10]"},{"why":"Establishes the edge-density bounds for Ramsey graphs needed in Lemma 2.2.","marker":"[19]"},{"why":"Gives the coupling that represents the random edge count as a quadratic polynomial with coefficients in a fixed finite set.","marker":"[27]"},{"why":"The old induced-copy result that Lemma 2.2 quantifies and generalises.","marker":"[17]"}],"fun_headline_variants":["Quadratic Littlewood-Offord: high point probabilities force low rank","Low-rank rigidity for quadratic forms with large point probabilities","Inverse theorem: large quadratic concentration implies near-low-rank","Ramsey graphs from quadratic inverse Littlewood-Offord rigidity","Algebraic inverse: high concentration in quadratics yields low rank"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The application to Ramsey graphs relies on the imported graph counting estimate that every $C$-Ramsey graph contains induced copies of every small fixed graph in numbers proportional to $n^h$; if that estimate fails with a full polynomial factor, the deduction of Theorem 1.3 breaks down, although the inverse theorems themselves do not depend on it.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic Littlewood-Offord: high point probabilities force low rank","Low-rank rigidity for quadratic forms with large point probabilities","Inverse theorem: large quadratic concentration implies near-low-rank","Ramsey graphs from quadratic inverse Littlewood-Offord rigidity","Algebraic inverse: high concentration in quadratics yields low rank"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000748,"raw_usage":{"total_tokens":3336,"prompt_tokens":952,"completion_tokens":2384,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":568,"completion_tokens_details":{"reasoning_tokens":2308}},"tokens_in":568,"tokens_out":2384,"duration_ms":15916,"temperature":1.0,"reasoning_tokens":2308,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:00:27.906507+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A sequence of quadratic polynomials with all coefficients in $\\{-1,0,1\\}$ whose exact point probabilities exceed $C(\\log n)^{r/2}n^{-1+2/(r+2)}$ for some fixed $r\\ge3$, while their coefficient matrices stay at $\\ell^1$-distance at least $\\varepsilon n^2$ from every symmetric matrix of rank less than $r$, would refute Theorems 1.1 and 1.2. A concrete starting point is exhaustive search over small $n$ with coefficients in $\\{0,1\\}$, computing both the maximum point probability and the minimal $\\ell^1$ distance to low-rank symmetric matrices.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the decoupling trick that Lemma 3.3 adapts to characteristic functions."},{"cited_title":"Halász, Estimates for the concentration function of combinatorial number theory and probability, Period","cited_arxiv_id":null,"evidence_quote":"Supplies the multidimensional linear Littlewood–Offord bound (Theorem 3.5) used on the decoupled linear polynomial."},{"cited_title":"Tao and V","cited_arxiv_id":null,"evidence_quote":"Provides the Esséen concentration inequality (Lemma 3.4) that converts Fourier decay into anti-concentration."},{"cited_title":"Conlon and J","cited_arxiv_id":null,"evidence_quote":"Provides the regularity and counting lemmas that produce many induced copies of every small graph in Ramsey graphs."},{"cited_title":"Erd˝os and A","cited_arxiv_id":null,"evidence_quote":"Establishes the edge-density bounds for Ramsey graphs needed in Lemma 2.2."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the coupling that represents the random edge count as a quadratic polynomial with coefficients in a fixed finite set."},{"cited_title":"Erd˝os and A","cited_arxiv_id":null,"evidence_quote":"The old induced-copy result that Lemma 2.2 quantifies and generalises."}],"review_version":1}