{"id":"8eb2729d-84af-4859-b078-791b6a547ed9","arxiv_id":"2509.21536","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A weak regularity lemma decomposes polynomial maps into few approximately independent homogeneous parts, with bounds polynomial in the number of polynomials, and implies stronger quantitative versions of rank and arithmetic formula results.","lead":"This paper proves a new weak regularity lemma for polynomials over finite fields whose bounds are polynomial in the number of polynomials, unlike earlier tower-type regularity lemmas. The lemma yields new quantitative bounds for polynomial rank and for the top fan-in of depth-4 arithmetic formulas, based only on the curves contained in the image of a polynomial map.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.2's proof chooses t too small by a factor exponential in d; the stated bias inequality fails at k≈S, so the central proof is incomplete as written.","rationale":"The paper's main contribution is a weak regularity lemma with a doubly-exponential-in-d but polynomial-in-m bound, plus applications to rank and depth-4 formulas. The overall strategy is credible: the rank-regularity lemma (Theorem 2.5) is self-contained, the Fourier step (Lemma 2.11) is sound, and the applications largely follow from the decomposition machinery. The reader's concern about the black-box use of [MZ24] is reasonable, but the paper itself remarks that earlier published bounds could be substituted, so that concern is not decisive. However, checking the actual inequality in the proof of Theorem 2.2 reveals a quantitative mismatch: the asserted t does not satisfy the required bias bound at the maximal decomposition size k≈S. Since this step is the bridge from rank regularity to weak regularity, the proof as written does not establish the stated bound unless the choice of t is corrected. The correction is likely routine and the final asymptotic bound may be unchanged, so the appropriate disposition remains conditional rather than rejection.","tokens_in":19451,"tokens_out":33624,"duration_ms":274926,"concrete_test":"Recompute the displayed condition in the proof of Theorem 2.2 for an explicit small case, e.g. d=2, q=5, m=2, r=1, with c_d ≈ 1/4, using S=((2t+1)dm)^{2^d} and the asserted t=2^{d^{1+o(1)}}(r+1)^{1+o(1)} ln m. Check whether q^{-c_d t k/L_F(tk)} < q^{-r-k} for k=S; if it fails, the asserted t is insufficient. Then solve numerically for the least t satisfying the inequality for all k≤S and compare the resulting S with the claimed (2m(r+1))^{2^{d(1+o(1))}}; this determines whether the final bound survives with a corrected choice of t.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Theorem 2.2, t is selected so that for every k ≤ S := ((2t+1)dm)^{2^d}, the inequality q^{-c_d t k / L_F(tk)} < q^{-r} q^{-k} holds, equivalently c_d t / L_F(tk) > (r/k)+1. The paper asserts that t = 2^{d^{1+o(1)}} (r+1)^{1+o(1)} log m suffices. This assertion fails at the largest admissible k. Indeed, for k=S, log_q(tk) ≈ (2^d+1) log_q t + 2^d log_q m, so L_F(tS) ≈ 2^d(log_q t + log_q m), while c_d t ≈ (r+1)^{1+o(1)} log m up to subpolynomial factors. Hence c_d t / L_F(tS) ≈ 2^{-d}, far below the required threshold of roughly 1. The missing factor is exponential in d and is not absorbed by the o(1) in the claimed t. A correct choice needs t roughly 2^d c_d^{-1} times a logarithmic factor, which changes the intermediate bound but, plausibly, not the final asymptotic size (2m(r+1))^{2^{d(1+o(1))}}, since the exponent absorbs the extra 2^d. The displayed derivation is nevertheless invalid, and the proof of the central lemma is incomplete as written; this is independent of whether the cited [MZ24] theorem is correct.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines a weak regularity lemma for polynomial tuples over finite fields: every m-tuple of degree-d polynomials over F_q with d<char(F) is shown to have a decomposition into homogeneous polynomials X_1,...,X_k, with k polynomial in m, such that the top-degree part is approximately uniform even after conditioning on the others. The main theorem claims a size bound k ≤ (2m(r+1))^{2^{d(1+o(1))}} for approximation parameter ε=q^{-r}. The proof proceeds through a rank-regularity lemma for polynomial pencils, a bias bound from Moshkovitz–Zhu, Fourier analysis to convert low bias into weak regularity, and then applications to curves in the image of polynomial maps. The applications include a quantitative bound for Karam's generalized rank rk_{d/u}(P) in terms of the univariate degree u=udeg(P), a rank_{d/2} bound when the image contains no line, and depth-4 formulas with bounded top fan-in.","tokens_in":19726,"tokens_out":24432,"duration_ms":212708,"significance":"If the proof gap discussed below is repaired, the paper makes a substantial contribution: it replaces tower-type or non-explicit bounds in polynomial regularity lemmas with an explicit polynomial-in-m bound, and it shows that this weak form of regularity is strong enough for image and curve questions that standard rank methods cannot address. The applications to Karam's rank problem and to top fan-in of depth-4 formulas are concrete and new. The notion of univariate degree of a polynomial map is natural and well motivated. The proof is mostly self-contained after Theorem 2.10, the reductions are clean, and no parameters are fitted to make the final bounds work; the paper is also explicit that its central bias step relies on the MZ24 theorem.","major_comments":[{"comment":"The choice of t does not satisfy the displayed bias inequality. The proof requires that for every k ≤ S := ((2t+1)dm)^{2^d} we have q^{-c_d t k / L_F(tk)} < q^{-r} q^{-k}, equivalently c_d t / L_F(tk) > (r/k)+1. With the stated t = 2^{d^{1+o(1)}} (r+1)^{1+o(1)} log m, the condition already fails at k=1: the left-hand side is about (r+1)^{1+o(1)} log m divided by log_q(t)+1 ≈ d^{1+o(1)}, which tends to 0 in d for bounded m,r; when m=1 the formula gives t=0. At k=S the failure is even more transparent: L_F(tS) is on the order of 2^d(log_q t + log_q m), so c_d t / L_F(tS) is roughly 2^{-d} times the same ratio, again well below the required value 1+r/S. Thus the main lemma is not proved as written. This is fixable by taking t about 2^d c_d^{-1} times a logarithmic factor in t and m, and the extra 2^d is plausibly absorbed in the final 2^{d(1+o(1))} exponent, but the displayed derivation must be corrected.","section":"Section 2.3, proof of Theorem 2.2"},{"comment":"The proof of Theorem 2.2 is fully dependent on the bias bound of Moshkovitz–Zhu, which is cited as an unpublished submitted paper and is coauthored by the first author. This theorem is load-bearing: the rank-regularity lemma gives rank, and Theorem 2.10 is the only bridge from rank to the bias values needed in Lemma 2.11. The manuscript should either include a proof of Theorem 2.10 or cite a published/accepted version. Moreover, the corrected choice of t in the previous comment depends on the exact value c_d = 2^{-d^{1+o(1)}}; if the constant in [MZ24] has a different dependence on d, the final bound in Theorem 2.2 needs to be rechecked.","section":"Section 2.2, Theorem 2.10"}],"minor_comments":[{"comment":"The abstract promises an arithmetic circuit size bound n^{⌊d/u⌋+o(1)} for polynomial maps whose image avoids curves of degree below u, but the body (Theorem 1.2) only states a depth-4 formula with top fan-in r ≤ (2m)^{2^{d(1+o(1))}} and bottom fan-in at most d/u. The circuit-size implication is not derived in the text; please add the derivation or revise the abstract.","section":"Abstract and Section 1.2"},{"comment":"The applications in Theorem 3.7 set ε = 1-d/q. In the boundary case d = q-1 this equals q^{-1}, i.e. r=1, while the introduction states Theorem 2.2 for ε=q^{-r} with r>1. Please clarify whether Theorem 2.2 is intended for all r>0, and adjust the statements accordingly.","section":"Section 2.3 and Section 3.2"},{"comment":"The displayed induction bound on r_i has an exponent that appears to be 2^i-1; with i=0 this would be negative and incompatible with the base case r_0 ≤ dm. The indexing should be cleaned up.","section":"Section 2.1.2, proof of Theorem 2.5"},{"comment":"Proposition 3.9 item 2 states udeg(P)<|F|, but Definition 3.5 sets udeg(P)=∞ for constant P. Please exclude the constant case there or adjust the statement.","section":"Section 3.1, Proposition 3.9"},{"comment":"There are minor typographical issues, including 'the the finite-field Gowers inverse conjecture' in Section 1 and the duplicate reference [LZ24] with different titles in the bibliography.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":"The central idea is good and the final theorem may well survive the fix to the choice of t, but the proof gap in Theorem 2.2 is load-bearing and must be repaired before the paper can be accepted. I also recommend that the editor verify the status of the MZ24 paper, since the main result depends on an unpublished theorem coauthored by the first author. The abstract/body mismatch about circuit-size bounds should be corrected as part of the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things. The paper introduces a genuinely new weak regularity lemma for polynomials, with decomposition size polynomial in the number of polynomials m—roughly (2m)^{2^{d(1+o(1))}}—and the applications to rank bounds and depth-4 top fan-in are new. But there is a real gap in the proof of the central lemma, Theorem 2.2. The stress-test note is correct: the asserted choice of t is too small by a factor exponential in d. At the maximal k, the inequality q^{-c_d t k/L_F(tk)} < q^{-r-k} fails because L_F(tS) is about 2^d(log t + log m), while c_d t is only (r+1)^{1+o(1)} log m, giving a ratio of roughly 2^{-d} instead of the required ≥ 1. A larger t, about 2^{O(d)} times the stated value, restores the inequality, and the final bound (2m(r+1))^{2^{d(1+o(1))}} should survive up to the usual o(1). But as written the proof is incomplete, and this is not a typo-level issue.\n\nWhen that is repaired, the paper is a solid contribution. The rank-regularity lemma (Theorem 2.5) is a nice new tool, the Fourier step isolating one free variable is elegant, and the application to curves in the image is genuinely beyond what standard rank methods give. I also think the paper is honest about its dependencies: the MZ24 theorem is not proved here, but the authors note that Janzer's or Milicevic's bounds can be substituted at the cost of weaker constants, so that reliance is not load-bearing. The mechanical problems the reader flagged—duplicate [LZ24], the exponent typo in the intro, and the U/U_i notation clash in Theorem 3.7—are real but easily fixed.\n\nMy bottom line: this deserves a serious referee, but the referee should be told to focus on the choice of t in Theorem 2.2 and on whether the final bound survives a correct choice. I would not cite it as-is, and I would not bring it to a reading group until the gap is sorted. If the authors fix the proof, this becomes a genuinely useful paper for additive combinatorics and algebraic complexity.\n\nBest.","headline":"A genuinely new weak regularity lemma with attractive applications, but the main proof has a repairable gap in the choice of t that must be fixed before the results are trustworthy.","tokens_in":20262,"tokens_out":10639,"would_cite":false,"duration_ms":78563,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11T06"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every polynomial map over a finite field of characteristic larger than its degree has a weak regularity decomposition of polynomial size, replacing tower-type bounds, and uses it to bound generalized rank and…","keywords":["weak regularity lemma","polynomial rank","finite fields","structure versus randomness","arithmetic circuits","depth-4 formulas","univariate degree","polynomial maps"],"falsifier":"The paper's bounds could be falsified by an explicit family of degree-$d$ forms over finite fields $\\mathbb{F}_q$ with $\\operatorname{char}(\\mathbb{F}_q)>d$ and $\\operatorname{rk}(P)\\ge r$ but $|\\operatorname{bias}(P)|>q^{-c_d r/L_{\\mathbb{F}_q}(r)}$ for $c_d=2^{-d^{1+o(1)}}$; computing the bias of, say, high-rank trilinear forms over moderately sized prime fields would locate such a counterexample if it exists. Alternatively, a polynomial map whose image avoids lines yet has $\\operatorname{rk}_{d/2}(P)$ exceeding $(2m)^{2^{d(1+o(1))}}$ would disprove the main rank application.","tokens_in":19216,"feed_emoji":"🧮","tokens_out":15778,"duration_ms":95618,"temperature":0.7,"pith_summary":"Standard regularity lemmas for polynomials decompose any low-degree polynomial into a bounded number of approximately independent pieces, but the number of pieces grows like a tower of exponentials. This paper proves a weaker regularity lemma whose size is polynomial in the number $m$ of input polynomials: for degree at most $d$, characteristic bigger than $d$, and error $\\epsilon=q^{-r}$, the decomposition has size at most $(2m(r+1))^{2^{d(1+o(1))}}$. The weaker notion only asks that one polynomial of maximal degree behaves approximately like a free variable, independent of the others, and that is enough to see curves contained in the image of a polynomial map, which standard rank methods miss. From this the paper derives quantitative bounds on generalized polynomial rank and on the top fan-in of depth-4 arithmetic formulas, as well as a power-saving upper bound on arithmetic circuit size for maps whose image avoids low-degree curves.","feed_headline":"Regularity for polynomials drops from towers to polynomial size","feed_subtitle":"A weak rank-based regularity lemma bounds polynomial rank and depth-4 formula fan-in for low-degree maps.","key_machinery":"The carrying mechanism is the rank-regularity lemma (Theorem 2.5), which produces a minimal decomposition $P\\subseteq\\mathbb{F}[Y]$ in which every linear combination of the forms $Y_i$ lying outside a fixed strict subspace $U$ of their span has rank at least $t|Y|$. This is a high-rank pencil: the relevant set is $V\\setminus U$ rather than the full nonzero span $V\\setminus\\{0\\}$, and that relaxation is what avoids tower-type bounds. The lemma iteratively replaces low-rank subspaces by quadratic forms in lower-degree forms, giving size at most $((2t+1)dm)^{2^d}$. To convert this rank information into probabilities, the proof invokes Theorem 2.10, a structure-versus-randomness theorem asserting that for $\\operatorname{char}(\\mathbb{F})>d$, $\\operatorname{rk}(P)\\ge r$ implies $|\\operatorname{bias}(P)|\\le |\\mathbb{F}|^{-c_d r/L_{\\mathbb{F}}(r)}$ with $c_d=2^{-d^{1+o(1)}}$; then Lemma 2.11 shows, by an additive-character expansion, that if every linear combination outside $U$ has bias at most $\\epsilon q^{-k}$, any basis of $V$ containing a basis of $U$ is weak $\\epsilon$-regular. For the applications, Lemma 3.10 and a zero-set counting argument turn weak regularity into the existence of a low-degree curve inside the image of $P$, which is exactly what bounds the generalized rank and the fan-in parameters.","core_discovery":"The paper's central discovery is that the usual regularity-lemma requirement, that all nontrivial linear combinations of the decomposition parts have high rank, can be relaxed without losing utility. The new weak regularity lemma (Theorem 2.2) states that for any finite field $\\mathbb{F}$ with $d<\\operatorname{char}(\\mathbb{F})$, every $m$-tuple $P$ of degree-at-most-$d$ polynomials has a weak $\\epsilon$-regular decomposition of size at most $(2m(r+1))^{2^{d(1+o(1))}}$ when $\\epsilon=q^{-r}$. In such a decomposition $P=F(X_1,\\ldots,X_k)$ with the $X_i$ homogeneous, the first part $X_1$ has maximal degree, $P$ genuinely depends on $X_1$, and conditioned on the other parts taking any fixed value, $X_1$ is distributed almost uniformly over $\\mathbb{F}$. The proof reaches this through a rank-regularity lemma for high-rank pencils, a structure-versus-randomness theorem that converts rank into bias, and a character-sum computation that converts bias into weak regularity. The same machinery yields the quantitative rank bound $\\operatorname{rk}_{d/u}(P)\\le (2m)^{2^{d(1+o(1))}}$ for $u=\\operatorname{udeg}(P)$, and the corresponding depth-4 formula bound.","pith_inferences":["Because the size bound is polynomial in $m$ but double-exponential in $d$, the method is most naturally useful in the low-degree regime $d=O(1)$; for large $d$ the constants would dominate.","Any improvement to the imported structure-versus-randomness constant $c_d$ would transfer directly to the weak regularity lemma, so the double-exponential dependence on $d$ is not intrinsic to the combinatorial part of the argument.","The image-avoidance condition offers a testable geometric handle: one could inspect zero sets or fibers of explicit polynomial maps to see where the $d/u$-rank bound is tight.","The same weak-regularity perspective may apply to other image-based questions, such as counting points of polynomial maps or bounding intersections of images with algebraic varieties, where standard rank methods give only equidistribution information."],"forward_implications":["Every degree-$d$ polynomial map over a finite field of characteristic greater than $d$ has a weak $\\epsilon$-regular decomposition whose size is polynomial in the number $m$ of polynomials, rather than a tower in $d$ and $m$.","If the image of such a map contains no line, then its $d/2$-rank is at most $(2m)^{2^{d(1+o(1))}}$, independent of the number of variables and of the field size.","For $u=\\operatorname{udeg}(P)$, the $d/u$-rank of any polynomial map $P$ is bounded by the same quantity, making the earlier qualitative generalized-rank bound quantitative and extending it to tuples of polynomials.","Any polynomial generated by an $m$-tuple of degree-at-most-$d$ polynomials with univariate degree at least $u$ is computable by a depth-4 formula with bottom fan-in at most $d/u$, top fan-in at most $(2m)^{2^{d(1+o(1))}}$, and at most $2u$ factors in each product.","A map whose image avoids curves of degree below $u$ is computable by an arithmetic circuit of size $n^{\\lfloor d/u\\rfloor+o(1)}$, so strong lower bounds for such maps would have to evade this power-saving upper bound."],"supporting_citations":[{"why":"Supplies the structure-versus-randomness theorem (Theorem 2.10) converting high rank into small bias; this is the key unproved input the proof relies on.","marker":"[MZ24]"},{"why":"States the qualitative generalized-rank bound that this paper makes quantitative and extends from single polynomials to polynomial maps.","marker":"[Kar23]"},{"why":"Defines the generalized rank notion and supplies the standard regularity lemma with tower-type bounds that the paper improves.","marker":"[GT09]"},{"why":"Gives a clean instance of the standard polynomial regularity lemma whose weak bounds motivate the relaxed notion of weak regularity.","marker":"[ESS19]"},{"why":"Provides the weak graph regularity lemma whose approach inspires the paper's weaker-but-bounded decomposition.","marker":"[FK99]"},{"why":"Introduces the rank/strength notion used in Definition 2.3 and gives the classical geometric analogue of structure-versus-randomness over infinite fields.","marker":"[Sch85]"}],"fun_headline_variants":["Weak regularity lemma shrinks tower bounds to polynomial","New weak lemma for polynomials: power-saving circuit bounds","Polynomial maps get bounded rank via weak regularity","Breaking the tower: weak regularity for polynomial maps","Tight polynomial rank via a weaker regularity lemma"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is an imported structure-versus-randomness theorem, not proved in this paper, claiming that over a finite field of characteristic greater than the degree, a polynomial of large rank must have correspondingly tiny bias; if that theorem were false or materially weaker, the polynomial-size regularity bounds would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Weak regularity lemma shrinks tower bounds to polynomial","New weak lemma for polynomials: power-saving circuit bounds","Polynomial maps get bounded rank via weak regularity","Breaking the tower: weak regularity for polynomial maps","Tight polynomial rank via a weaker regularity lemma"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00095,"raw_usage":{"total_tokens":4101,"prompt_tokens":1038,"completion_tokens":3063,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":2991}},"tokens_in":654,"tokens_out":3063,"duration_ms":328503,"temperature":1.0,"reasoning_tokens":2991,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:49:58.678316+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The paper's bounds could be falsified by an explicit family of degree-$d$ forms over finite fields $\\mathbb{F}_q$ with $\\operatorname{char}(\\mathbb{F}_q)>d$ and $\\operatorname{rk}(P)\\ge r$ but $|\\operatorname{bias}(P)|>q^{-c_d r/L_{\\mathbb{F}_q}(r)}$ for $c_d=2^{-d^{1+o(1)}}$; computing the bias of, say, high-rank trilinear forms over moderately sized prime fields would locate such a counterexample if it exists. Alternatively, a polynomial map whose image avoids lines yet has $\\operatorname{rk}_{d/2}(P)$ exceeding $(2m)^{2^{d(1+o(1))}}$ would disprove the main rank application.","supporting_citations":[],"review_version":1}