{"id":"fa9e1b30-ea51-4eed-8160-d59934ea7ba4","arxiv_id":"2501.12287","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A spectral inverse theorem and a spectral regularity theorem show that leading eigenvectors of Fourier-denoised matrices recover quadratic Fourier structure, giving new algorithms for quadratic denoising and character decomposition.","lead":"The authors prove that quadratic structure in a function on a finite abelian group can be recovered from the dominant eigenvectors of a matrix built by denoising the function's shifts. They provide two algorithms, for quadratic denoising and for decomposing a function into quadratic characters, with rigorous approximation guarantees.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 7.12 relies on the false inequality ∥g∥_{U^3} ≤ ∥g∥_2 when bounding the spectral-projection error, so the claimed U^3 bound 2ρ^{3/8} is not established.","rationale":"The reader's weakest_assumption identified the black-box nilspace regularity theorem and the balance-to-quasiorthogonality conversion as the load-bearing risk. That is a legitimate dependency concern, but it is not an internal flaw. My stress-test found a sharper, internally checkable problem: the proof of Theorem 7.12 (which yields the main Theorem 1.1) uses the assertion that the L^2 norm dominates the U^3 norm. This is false, with an elementary counterexample on Z_2. The step where ∥Pρ(f) − Σ gχ∥_{U^3} is replaced by its L2 norm is therefore unjustified, and the final bound 2ρ^{3/8} does not follow with the constants chosen. Because this error occurs in the proof of the central spectral regularization claim, the current version of the paper leaves Theorem 1.1 unproven. The flaw is likely repairable by using interpolation and a much smaller H(ρ0), but the submitted argument requires revision before the main claim can be accepted. This is a concrete correctness risk distinct from the external-dependency issue, so my assessment differs from the reader's weakest-assumption diagnosis.","tokens_in":70673,"tokens_out":14561,"duration_ms":137625,"concrete_test":"On the group Z_2, compute the Gowers U^3 norm of f = 1_{0} directly from the definition: U^3^8 = E_{x,t1,t2} ∏_{v∈{0,1}^3} f(x+v1t1+v2t2) = 1/8, so ∥f∥_{U^3} = 2^{−3/8}, while ∥f∥_2 = 2^{−1/2}. This disproves the claimed dominance. Then re-run the final estimate of Theorem 7.12 replacing ∥e∥_{U^3} ≤ ∥e∥_2 by the correct interpolation ∥e∥_{U^3} ≤ ∥e∥_2^{1/4}∥e∥_∞^{3/4}, with the actual choice H(ρ0)=ρ0/2; verify that for small ρ0 the resulting bound exceeds 2ρ^{3/8}, and determine the largest H(ρ0) (e.g., ρ0^{3/2}) that closes the proof.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"In the proof of Theorem 7.12, after inequality (49), the authors write: 'using the above estimates, the fact that the L2-norm dominates the U3-norm' and replace ∥Pρ(f) − Σ_{χ∈Sρ} gχ∥_{U^3} by its L2 norm. This domination is false. On Z_2, take f = 1_{0}. Then ∥f∥_2 = 2^{−1/2} but ∥f∥_{U^3} = 2^{−3/8} ≈ 0.812 > 0.707. The correct inequality for 1-bounded functions is ∥g∥_{U^3} ≤ ∥g∥_2^{1/4} (by interpolation with ∥g∥_{U^3} ≤ ∥g∥_∞ and the known U^3 ≤ L^2-type bounds), not ∥g∥_{U^3} ≤ ∥g∥_2. In Theorem 7.12 the L2 error ∥Pρ(f) − Σ_{χ∈Sρ} gχ∥_2 is only controlled as H(ρ0), and in Theorem 1.1 this is set to H(ρ0) = ρ0/2. Under the correct interpolation, the U3-norm of this error can be as large as (ρ0/2)^{1/4}, which for small ρ0 is much larger than ρ0^{3/8}; hence the displayed estimate ∥f − Pρ(f)∥_{U^3} ≤ 2ρ^{3/8} does not follow from the given argument. The theorem might be repairable by choosing H(ρ0) ≤ ρ0^{3/2} and using the correct interpolation, but as written the proof of the main spectral regularization claim is invalid.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a spectral approach to higher-order Fourier analysis, focusing on the quadratic case. Given a 1-bounded function f on a finite abelian group Z, the authors study the matrix Kε(f⊗f) obtained by applying the soft-thresholding Fourier denoising operator Kε to each Z-diagonal of f⊗f. The main results are: (1) a refined nilspace regularity theorem (Theorem 5.1) expressing the structured part of f as a sum of quasiorthogonal nilspace characters; (2) a structure theorem for Kε(f⊗f) (Theorem 6.1) as a sum of rank-one matrices from these characters plus a small error; (3) a spectral U3-regularization theorem (Theorem 7.12, implying Theorem 1.1) showing that the projection of f onto the leading eigenspace of Kε(f⊗f) is close to f in the U3-norm and is a structured function of order 2; and (4) a recovery theorem (Theorem 7.15) for individual quadratic characters from eigenvectors under a spectral separation assumption. The paper also presents two algorithms and a numerical illustration. The proofs are detailed and rely on the nilspace regularity theorem of [12] and on the authors' own refinements.","tokens_in":71026,"tokens_out":26420,"duration_ms":231921,"significance":"This is a substantial contribution that establishes a new connection between spectral decompositions of a natural self-adjoint operator and higher-order Fourier structure, yielding quantitative inverse and regularity theorems for the Gowers U3-norm. The algorithmic corollaries are plausible and the numerical demonstration, while preliminary, is suggestive. The proofs are rigorous and transparent in their use of the cited nilspace regularity theorem, and the paper honestly acknowledges the non-constructive nature of the parameters (Remark 1.3). The main theorems (Theorems 1.1, 6.1, 7.12) are well-supported, and the proofs are detailed enough to be checked. The only mathematical issue I found is a false statement in Lemma 5.8, which is local and does not affect the main results because the proofs use the valid s ≥ 3 case or the second inequality of that lemma.","major_comments":[{"comment":"As stated, the first inequality in (47) is false for s=2. Let Z be a finite abelian group and H a subgroup of density α ∈ (0,1), and take f = 1_H. Then ∥f∥_{U^2}^4 = α^3, while the expression inside the minimum in (47) for s=2 evaluates to min(α^8, α^3) = α^8, so the claimed inequality fails. The proof's two-disjoint-stars argument applies only for s ≥ 3, and the exponent in the first term should be 2s+2 rather than 2^{s+2}. Since the main theorems apply the lemma only with s = k+1 ≥ 3, or else use the second inequality which is valid for all s ≥ 2, this error is local and does not invalidate Theorem 7.12 or Theorem 1.1. However, the lemma as printed is mathematically false and should be corrected.","section":"Lemma 5.8, Eq. (47)"}],"minor_comments":[{"comment":"In the proof of Theorem 7.12, the sentence 'using the fact that the L2-norm dominates the U3-norm' is correct, since the inequality ∥g∥_{U^3} ≤ ∥g∥_2 follows from the s=3 case of Lemma 5.8 (with the corrected exponent), but a pointer to that lemma would help the reader.","section":"Theorem 7.12 proof"},{"comment":"Theorem 1.1 only asserts the existence of ε0 and ρ but does not provide a constructive method to find them. Since Algorithm 1 requires ε and ρ as inputs, the paper should state explicitly that the practical choice of these parameters is heuristic and not guaranteed by the theorem, especially given the paper's emphasis on 'simple and practical algorithms'.","section":"Remark 1.3"},{"comment":"No complexity bound is given for the algorithm. The authors could add a sentence noting that the construction of M involves |Z| applications of Kε (each O(|Z| log |Z|) via FFT) and that the eigendecomposition of a |Z|×|Z| matrix is O(|Z|^3) in a naive implementation, to substantiate the practical claim.","section":"Algorithm 1"},{"comment":"The definition of c1 in the proof is terse; it would be clearer to display the intermediate bound ∥P_{χ∈S∖S_ρ} g_χ∥_{U^{k+1}} ≤ ρ^{(k+1)/2^{k+1}}(1+c0)^{1/2^{k+1}} + |S|D(η,m)^{1/2^{k+1}} before taking the final estimate.","section":"Proof of Proposition 5.10"},{"comment":"The abstract states that the algorithms are 'simple and practical', but the parameter-dependence is deferred to future work. A caveat in the introduction (e.g., in Remark 1.3) would prevent overstatement of the current algorithmic contribution.","section":"Abstract and Introduction"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound and the stress-test concern about the U3/L2 inequality is unfounded: the inequality ∥g∥_{U^3} ≤ ∥g∥_2 is true and follows from the two-star argument in Lemma 5.8 for s=3. The only real issue is a false statement in Lemma 5.8 for s=2, which is local and easily fixed. The gap between the existence of parameters and the practical implementation is known to the authors and is acceptable for a theory paper. I recommend minor revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What should you know about Candela–Gonzalez-Sanchez–Szegedy? The paper delivers the first spectral, essentially non-iterative algorithms for quadratic Fourier decomposition on arbitrary finite abelian groups, and it proves new inverse and regularity theorems for the U3 norm using 2-step nilspace characters. The Fourier denoising operator Kε applied to the diagonals of f⊗f, and the recovery of dominant nilspace characters from dominant eigenvectors, are genuinely new relative to the Goldreich–Levin style algorithms, which are probabilistic and finite-field specific.\n\nThe proof core is Theorem 7.12. I checked the stress-test objection about the step “the L2-norm dominates the U3-norm.” The cited counterexample is miscalculated: for f = 1_0 on Z_2, the U3 norm is (1/16)^{1/8} = 2^{-1/2}, not 2^{-3/8}; that example does not violate the inequality. The inequality itself appears to hold for the functions appearing here, so the proof step looks sound.\n\nThe real soft spots are practical. The algorithms depend on parameters ε, ρ, δ whose existence is guaranteed but not constructively specified; the single illustrative experiment has no error bars or baseline; and the main theorems inherit substantial quantitative content from the nilspace regularity theorem [12, Thm 1.5], imported as a black box. These issues are real but not load-bearing: the mathematical claims are proven relative to that theory, and the “simple and practical algorithms” framing is somewhat overstated until parameter selection is addressed. The circularity burden is low—the spectral theorems are derived from the regularity theorem and Fourier-analytic inequalities, not tuned to match conclusions.\n\nWho is this for? Researchers in higher-order Fourier analysis and additive combinatorics, and theoretically inclined TCS people interested in spectral methods. It deserves a serious referee: the core results are new, the proofs are detailed, and the main weaknesses are in the applied framing, not in the mathematics itself.\n\nRecommendation: send to peer review.","headline":"Genuinely new spectral machinery for quadratic Fourier analysis, with a proof core that looks sound despite one misbegotten stress-test objection.","tokens_in":71568,"tokens_out":33196,"would_cite":true,"duration_ms":280527,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that the quadratically structured part of a 1-bounded function on a finite abelian group is algorithmically recoverable from the dominant eigenspaces of the denoised matrix $K_\\varepsilon(f\\otimes f)$, with $U^3$ error…","keywords":["higher-order Fourier analysis","Gowers norms","quadratic Fourier analysis","nilspace characters","nilspace theory","spectral algorithms","regularity theorems","inverse theorems"],"falsifier":"Numerically check the claimed bound on a cyclic group: fix $\\rho_0$, take $f$ to be a random 1-bounded function and also a quadratic phase $f(x)=e^{2\\pi i x^2/N}$ plus noise, diagonalize $K_\\varepsilon(f\\otimes f)$, form $f_{\\mathrm{reg}}$ from eigenvalues at least $\\rho$, and compute $\\|f-f_{\\mathrm{reg}}\\|_{U^3}$; a violation of $\\|f-f_{\\mathrm{reg}}\\|_{U^3}\\leq 2\\rho^{3/8}$ for any $N$, $\\rho\\in[\\rho_0/2,\\rho_0]$, and $\\varepsilon\\in[\\varepsilon_0,1]$ would refute Theorem 1.1, and sustained agreement would support it.","tokens_in":70452,"feed_emoji":"🧮","tokens_out":8478,"duration_ms":88520,"temperature":0.7,"pith_summary":"This paper sets out to make higher-order Fourier analysis algorithmic by tying it to spectral theory. Its central theorem, Theorem 1.1, says that for every 1-bounded function $f$ on a finite abelian group one can choose a soft Fourier threshold $\\varepsilon$ and an eigenvalue cut-off $\\rho$ so that projecting $f$ onto the eigenspaces of the denoised matrix $K_\\varepsilon(f\\otimes f)$ with eigenvalue at least $\\rho$ yields a quadratically structured approximation $f_{\\mathrm{reg}}$ with $\\|f-f_{\\mathrm{reg}}\\|_{U^3}\\leq 2\\rho^{3/8}$. The approximation is genuinely of quadratic order: $f_{\\mathrm{reg}}$ is $L^2$-close to a function of bounded $U^3$-dual norm. If correct, this replaces intricate nilspace decompositions by a direct, non-iterative computation using Fourier transforms and matrix diagonalization, and it points to a general order-increment principle for higher orders.","feed_headline":"One matrix reveals quadratic Fourier structure","feed_subtitle":"Soft-thresholding the diagonals of f⊗f and diagonalizing yields the quadratically structured part of f, up to U3 error 2ρ^{3/8}.","key_machinery":"The central objects are the Fourier denoising operator $K_\\varepsilon$ and nilspace characters. The operator $K_\\varepsilon$ acts on a function's Fourier expansion by keeping coefficients of magnitude at least $\\varepsilon$ and shrinking their magnitudes by $\\varepsilon$, a soft threshold; applied to every diagonal $x\\mapsto f(x+t)\\overline{f(x)}$ of $f\\otimes f$, it produces a self-adjoint matrix whose eigenvectors are candidates for quadratic characters. A 2-step nilspace character is a function $F_\\chi\\circ\\phi$, where $\\phi$ is a balanced structure-preserving map from the group into a compact finite-rank nilspace and $F_\\chi$ is a bounded Lipschitz function with vertical frequency $\\chi$ in the top structure group; these generalize Fourier characters to quadratic order. The balance property makes distinct nilspace characters nearly orthogonal and makes each one a pseudoeigenvector, so the spectral data of $K_\\varepsilon(f\\otimes f)$ can be converted into quadratic components.","core_discovery":"The central discovery is that the quadratic Fourier components of $f$ are encoded as pseudoeigenvectors of $K_\\varepsilon(f\\otimes f)$: up to small error, this self-adjoint matrix equals a sum of rank-one matrices $g_\\chi\\otimes g_\\chi$, where the $g_\\chi$ are nearly orthogonal 2-step nilspace characters. Consequently each normalized $g_\\chi$ almost satisfies the eigenvector equation, with pseudoeigenvalue $\\|g_\\chi\\|_2^2$, and when its eigenvalue is large and separated, the corresponding true eigenvector is close to $g_\\chi$. This yields the spectral inverse theorem and the spectral regularity theorem: a function with large $U^3$-norm correlates with a quadratic character, and the projection onto dominant eigenspaces is an order-2 structured function.","pith_inferences":["Editorial extension: the soft-thresholded matrix $K_\\varepsilon(f\\otimes f)$ functions as a quadratic analogue of a covariance or Gram matrix, so its top eigenvectors could serve as quadratic principal components for denoising ordered data or time series; the paper only sketches this through a numerical illustration.","Editorial extension: the order-increment principle suggests a spectral hierarchy—applying the same construction to eigenvectors of $K_\\varepsilon(f\\otimes f)$ should reveal cubic structure—but the paper leaves the higher-order algorithm to future work.","Editorial extension: the randomized separation step is likely replaceable by a deterministic choice of $h$ in the dominant eigenspace; the paper itself notes this as an open direction, and a deterministic version would make Algorithm 2 fully deterministic.","Editorial extension: the approximate diagonalization of the $U^{k+1}$-norm suggests a fast uniformity test—estimate a function's Gowers norm from the norms of its dominant nilspace characters instead of averaging over all cubes."],"forward_implications":["The projection computed in Algorithm 1 is a spectral $U^3$-regularisation: it is close to $f$ in the $U^3$-norm and is an order-2 structured function in the sense of Definition 2.23.","When the relevant eigenvalues are separated, or when separation is achieved by a random unit vector in the dominant eigenspace, Algorithm 2 recovers the individual quadratic characters of $f$ from eigenvectors of $K_\\varepsilon(h\\otimes h)$.","The refined regularity theorem decomposes the structured part into boundedly many nearly orthogonal nilspace characters, yielding approximate Parseval identities and approximate diagonalizations of the Gowers norms.","Theorem 5.3 is a new inverse theorem with nilspace characters: a function with $U^{k+1}$-norm at least $\\delta$ correlates with one of $O_\\delta(1)$ nilspace characters.","The method works on every finite abelian group and uses only Fourier transforms and eigendecompositions, so quadratic Fourier analysis becomes algorithmic without finite-field restrictions and without iterative probabilistic searches."],"supporting_citations":[{"why":"Supplies the nilspace regularity theorem (Theorem 1.5) imported in Theorem 5.1, the black-box decomposition into $F\\circ\\phi$ plus small $U^{k+1}$ error that all later bounds inherit.","marker":"[12]"},{"why":"Provides the foundational nilspace definitions—cubes, morphisms, structure groups—used to define nilspace characters and their orthogonality.","marker":"[6]"},{"why":"Gives the structure of compact finite-rank nilspaces as iterated principal abelian bundles and the Haar measure properties used for vertical-frequency decomposition and balance.","marker":"[7]"},{"why":"Supplies the higher-order cube and Haar-measure facts used to prove vanishing of cross-frequency Gowers products in Proposition 4.21.","marker":"[11]"},{"why":"Introduces the Gowers norms and the $U^2$-Fourier identity that anchor the definition of the norms and the quadratic case.","marker":"[22]"}],"fun_headline_variants":["Eigenvectors expose quadratic Fourier structure","Spectral method cracks Gowers norms","Quadratic Fourier via spectral eigen decomposition","Pseudoeigenvectors reveal quadratic characters","A spectral route to higher-order Fourier analysis"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire spectral recovery inherits its quantitative strength from the imported nilspace regularity theorem [12, Theorem 1.5]: every 1-bounded function decomposes, up to arbitrarily small $U^{k+1}$ error, as $F\\circ\\phi$ with $\\phi$ a highly balanced nilspace morphism and $F$ a bounded Lipschitz function; if that decomposition theorem or the balance-to-quasiorthogonality conversion in Proposition 4.21 fails, the spectral inverse and regularity theorems do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Eigenvectors expose quadratic Fourier structure","Spectral method cracks Gowers norms","Quadratic Fourier via spectral eigen decomposition","Pseudoeigenvectors reveal quadratic characters","A spectral route to higher-order Fourier analysis"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001216,"raw_usage":{"total_tokens":4927,"prompt_tokens":789,"completion_tokens":4138,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":405,"completion_tokens_details":{"reasoning_tokens":4076}},"tokens_in":405,"tokens_out":4138,"duration_ms":31558,"temperature":1.0,"reasoning_tokens":4076,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:17:55.502041+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically check the claimed bound on a cyclic group: fix $\\rho_0$, take $f$ to be a random 1-bounded function and also a quadratic phase $f(x)=e^{2\\pi i x^2/N}$ plus noise, diagonalize $K_\\varepsilon(f\\otimes f)$, form $f_{\\mathrm{reg}}$ from eigenvalues at least $\\rho$, and compute $\\|f-f_{\\mathrm{reg}}\\|_{U^3}$; a violation of $\\|f-f_{\\mathrm{reg}}\\|_{U^3}\\leq 2\\rho^{3/8}$ for any $N$, $\\rho\\in[\\rho_0/2,\\rho_0]$, and $\\varepsilon\\in[\\varepsilon_0,1]$ would refute Theorem 1.1, and sustained agreement would support it.","supporting_citations":[{"cited_title":"Candela, B","cited_arxiv_id":null,"evidence_quote":"Supplies the nilspace regularity theorem (Theorem 1.5) imported in Theorem 5.1, the black-box decomposition into $F\\circ\\phi$ plus small $U^{k+1}$ error that all later bounds inherit."},{"cited_title":"Candela, Notes on nilspaces: algebraic aspects, Discrete Anal","cited_arxiv_id":null,"evidence_quote":"Provides the foundational nilspace definitions—cubes, morphisms, structure groups—used to define nilspace characters and their orthogonality."},{"cited_title":"Candela, Notes on compact nilspaces, Discrete Anal","cited_arxiv_id":null,"evidence_quote":"Gives the structure of compact finite-rank nilspaces as iterated principal abelian bundles and the Haar measure properties used for vertical-frequency decomposition and balance."},{"cited_title":"Candela, B","cited_arxiv_id":null,"evidence_quote":"Supplies the higher-order cube and Haar-measure facts used to prove vanishing of cross-frequency Gowers products in Proposition 4.21."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Gowers norms and the $U^2$-Fourier identity that anchor the definition of the norms and the quadratic case."}],"review_version":1}