A weak regularity lemma for polynomials

Basic Information

• Paper ID: 2509.21536
• Title: A weak regularity lemma for polynomials
• Authors: Guy Moshkovitz (City University of New York), Dora Woodruff (Massachusetts Institute of Technology)
• Classification: math.CO (Combinatorics), cs.CC (Computational Complexity), math.AC (Commutative Algebra)
• Publication Date: arXiv v2, November 5, 2025
• Paper Link: https://arxiv.org/abs/2509.21536

Abstract

Regularity lemmas for polynomials provide methods for decomposing polynomials using a bounded number of approximately independent polynomials. Such regularity lemmas play important roles in numerous results but suffer from tower-type or worse bounds. This paper designs a new, weaker but with strong bounds, regularity lemma. This lemma particularly provides quantitative methods to study curves contained in the images of polynomial maps, which standard approaches cannot achieve. Applications include strong bounds on Karam's problem regarding generalized rank, as well as new methods for obtaining upper bounds on the fan-in parameters of arithmetic circuits. For example, if a polynomial map $\mathbf{P}: \mathbb{F}^n \to \mathbb{F}^m$ of degree d has an image that contains no lines, then $\mathbf{P}$ can be computed by a depth-4 arithmetic formula with bottom fan-in at most $d/2$ and top fan-in at most $(2m)^{C(d)}$ (where $C(d)=2^{(1+o(1))d}$). One implication of this work is that there exists a certain "barrier" to arithmetic circuit lower bounds, which relates to the minimum degree polynomial curves contained in the image of the given polynomial map.

Research Background and Motivation

1. Core Problem

Regularity lemmas for polynomials are key tools in additive combinatorics, higher-order Fourier analysis, commutative algebra, and coding theory. The classical regularity lemma represents an n-variable polynomial $P: \mathbb{F}^n \to \mathbb{F}$ (or more generally a polynomial map $P: \mathbb{F}^n \to \mathbb{F}^m$) as $P = F(X)$, where $X = (X_1, \ldots, X_k)$ is a bounded number of polynomials, and these polynomials $X_i$ are "approximately independent."

2. Importance of the Problem

• Theoretical Significance: Regularity lemmas play central roles in proofs of major problems including the Gowers inverse conjecture (finite field case), the Stillman conjecture, and the weight distribution of Reed-Muller codes
• Broad Applications: As a key component of higher-order arithmetic regularity lemmas, used to reduce the study of general functions to the study of low-degree polynomials
• Foundational Tool: Provides a fundamental framework for understanding the relationship between polynomial structure and randomness

3. Limitations of Existing Methods

Classical regularity lemmas suffer from fatal defects:

• Explosive Growth of Bounds: The bound on decomposition size k is at least tower-type, i.e., highly dependent on exponential towers of degree d with m at the top
• Poor Practicality: These weak bounds mean that any results depending on them can only obtain extremely weak quantitative bounds
• Root Cause: To ensure approximate independence, all $X_i$ and their linear combinations must have large rank (as a function of k), leading to extremely many construction steps

4. Research Motivation

Inspired by Frieze and Kannan's weak regularity lemma for graphs, the authors propose:

• Relaxed Requirements: Instead of requiring all $X_i$ to be approximately independent, require only one (the highest degree) to be approximately independent relative to the others
• Obtain Strong Bounds: Through this weakening, improve the decomposition size from tower-type to polynomial bounds (in m)
• Maintain Practicality: Despite the weakened conditions, still support important applications

Core Contributions

1. Weak Regularity Lemma: Designs a new polynomial regularity lemma such that for error $\epsilon = q^{-r}$ ($r > 1$), any m-variable polynomial group $\mathbf{P}$ of degree at most d has a weak $\epsilon$-regular decomposition of size at most $(mr)^{2^{d(1+o(1))}}$, which is a polynomial bound (in m)
2. Rank Regularity Lemma: As the technical core, proves the rank regularity lemma (Theorem 2.5), bounding the decomposition size by $((2t+1)dm)^{2^d}$, with the key innovation being requiring only linear combinations outside the "pencil" to have high rank
3. Univariate Degree Concept: Introduces the new concept $\text{udeg}(\mathbf{P}) = \min\{\deg(U) | U: \mathbb{F} \to \mathbb{F}^m \text{ non-constant and } \text{Im}U \subseteq \text{Im}\mathbf{P}\}$, characterizing the sparsity of polynomial map images
4. Strong Bounds for Karam's Problem: For $t = \deg(\mathbf{P})/\text{udeg}(\mathbf{P})$, proves $\text{rank}_t(\mathbf{P}) \leq (2m)^{2^{d(1+o(1))}}$, significantly improving the tower-type bounds of Karam's original result
5. Arithmetic Circuit Upper Bounds: Proves that if $\text{udeg}(\mathbf{P}) \geq u$, then $P$ has a depth-4 formula $\sum^{[r]} \prod^{[2u]} \sum \prod^{[d/u]}$, where $r \leq (2m)^{2^{d(1+o(1))}}$
6. Circuit Lower Bound Barrier: Reveals that arithmetic circuit lower bound methods must avoid application to polynomial maps with high univariate degree, providing new perspective on understanding lower bound difficulties

Detailed Methodology

Task Definition

Input: m-variable polynomial group $\mathbf{P} = (P_1, \ldots, P_m) \in \text{Poly}^m_d(\mathbb{F})$ of degree at most d over finite field $\mathbb{F} = \mathbb{F}_q$, with $\text{char}(\mathbb{F}) > d$

Output: Weak $\epsilon$-regular decomposition $\mathbf{P} \subseteq \mathbb{F}[\mathbf{X}]$, where $\mathbf{X} = (X_1, \ldots, X_k) \in \text{Form}^k$ are k homogeneous polynomials (forms)

Constraints:

1. Probability Condition: $\forall y \in \mathbb{F}^k: |\Pr[\mathbf{X} = y] - q^{-1}\Pr[\mathbf{X}' = y']| \leq \epsilon q^{-k}$ (where $\mathbf{X}' = (X_2, \ldots, X_k)$)
2. Dependency: $\mathbf{P} \not\subseteq \mathbb{F}[\mathbf{X}']$ (ensures the decomposition truly depends on $X_1$)
3. Maximum Degree: $\deg(X_1) = \max_i \deg(X_i)$

Model Architecture

Overall Proof Structure

The proof employs a three-layer progressive structure:

Rank-Regularity (Rank-Regularity)
    ↓ [Theorem 2.5]
High-Rank Pencil (High-Rank Pencil)
    ↓ [Theorem 2.10 + Lemma 2.11]
Low Bias (Low Bias)
    ↓
Weak Regularity (Weak Regularity)

First Layer: Rank Regularity Lemma (Theorem 2.5)

Definition 2.4 (t-rank regular): $\mathbf{X} \in \text{Form}^r$ is t-rank regular if there exists a proper subspace $U \subsetneq \text{Sp}\mathbf{X}$ such that $\forall X \in \text{Sp}\mathbf{X} \setminus U: \text{rk}(X) \geq tr$

Key Innovation: Rather than requiring all nonzero linear combinations to have high rank (classical requirement), only require high rank outside the "pencil" $V \setminus U$

Construction Algorithm (Proof of Theorem 2.5):

Initialize: X₀ = all homogeneous parts of P (degrees 1 to d)
Iterate i = 0, 1, ..., s:
  1. Find minimal subspace W ⊆ Sp(Xᵢ) such that P ⊆ F[W]
  2. Take formal basis Y of W
  3. If Y is t-rank regular → terminate, return Xₛ = Y
  4. Otherwise:
     - Construct Y* (replace components of Y with degree <ℓ by degree ℓ components)
     - Apply Lemma 2.9 to decompose Y*
     - Merge to obtain Xᵢ₊₁, satisfying deg(Xᵢ₊₁) < deg(Xᵢ)

Lemma 2.9 (Decomposition Lemma): If $\mathbf{X} \in \text{Form}^r_d$ is not t-rank regular, then $\mathbf{X} \subseteq \mathbb{F}[\mathbf{Y}]$, where $\mathbf{Y} \in \text{Form}^R$ satisfies $\deg(\mathbf{Y}) < d$ and $R \leq 2tr^2$

Termination: Degree decreases by at least 1 each step; when $\deg(\mathbf{X}_s) \leq 1$, it must be t-rank regular (since degree-1 forms have infinite rank)

Bound Analysis:

• $r_0 \leq dm$
• $r_{i+1} \leq (2t+1)r_i^2 \leq (2t+1)^{2^{i+1}-1}(dm)^{2^{i+1}}$
• $s < d$, thus $r_s \leq ((2t+1)dm)^{2^d}$

Second Layer: From Rank to Bias

Definition (Bias): $\text{bias}(P) = \mathbb{E}_{x \in \mathbb{F}^n} \chi(P(x))$, where $\chi: \mathbb{F} \to \mathbb{C}$ is a nontrivial additive character

Theorem 2.10 (Structure vs Randomness): If $\text{rk}(P) \geq r$, then $|\text{bias}(P)| \leq |\mathbb{F}|^{-c_dr/L_{\mathbb{F}}(r)}$ where $c_d = 2^{-d^{1+o(1)}}$, $L_{\mathbb{F}}(r) = \log_{|\mathbb{F}|}(r+1) + 1$

Lemma 2.11 (Bias Implies Weak Regularity): If $U \subsetneq V \leq \text{Poly}$ satisfies $\forall X \in V \setminus U: |\text{bias}(X)| \leq \epsilon q^{-k}$, then a basis containing U's basis with $X_1 \notin U$, $\deg(X_1) = \deg(\mathbf{X})$ is a weak $\epsilon$-regular basis $\mathbf{X}$

Proof Technique: Using Fourier analysis, for a line $\ell$ with direction $e_1$: $\Pr[\mathbf{X} \in \ell] = \mathbb{E}_{a \in \mathbb{F}^k: a \cdot e_1 = 0} \text{bias}(a \cdot (\mathbf{X} - z))$ Combined with the point probability formula $\Pr[\mathbf{X} = y] = \mathbb{E}_{a \in \mathbb{F}^k} \text{bias}(a \cdot (\mathbf{X} - y))$ yields the weak regularity condition

Third Layer: Integrated Proof (Theorem 2.2)

Parameter Selection: Choose $t = 2^{d^{1+o(1)}}(r+1)^{1+o(1)}\log(m)$ such that $q^{-c_dtk/L_{F_q}(tk)} < \epsilon q^{-k}$ holds for all $k \leq ((2t+1)dm)^{2^d}$

Key Steps:

1. Apply Theorem 2.5 to obtain t-rank regular decomposition $\mathbf{P} \subseteq \mathbb{F}[\mathbf{Y}]$, $|\mathbf{Y}| = s \leq ((2t+1)dm)^{2^d}$
2. Define $V = \text{Sp}\mathbf{Y}$, $U = \text{Sp}\{X \in V | \text{rk}(X) < tk\}$
3. Prove $U$ is homogeneous (Lemma 2.7) and $V^\uparrow \setminus U \neq \emptyset$ (Corollary 2.8)
4. By Theorem 2.10, $U_\epsilon := \{X \in V | \text{bias}(X) \geq \epsilon q^{-k}\} \subseteq U$
5. Construct basis $\mathbf{X}$ containing U's basis and elements from $V^\uparrow \setminus U$, apply Lemma 2.11

Technical Innovations

1. Introduction of Pencil Concept: Relaxing from requiring "trivial pencil" $V \setminus \{0\}$ to have high rank to general pencil $V \setminus U$, which is key to obtaining strong bounds
2. Fine Control of Homogeneous Decomposition:
   • Lemma 2.6: Elements of degree less than $\deg(U_R(V))$ automatically belong to $U_R(V)$
   • Lemma 2.7: $U_R(V)$ of homogeneous space remains homogeneous
   • Corollary 2.8: $U_R(V) = V \Leftrightarrow U_R(V^\uparrow) = V^\uparrow$
3. Bridging Rank and Bias: Cleverly uses Moshkovitz-Zhu's quasi-linear structure vs randomness theorem to convert rank conditions to bias conditions
4. Fourier Analysis Techniques: Uses character sum formulas to precisely characterize the probability conditions of weak regularity
5. Degree Reduction Mechanism: Through Lemma 2.9 ensures degree strictly decreases each step, guaranteeing algorithm termination

Experimental Setup

Note: This is a pure theory paper with no experimental component. All results are mathematical theorems and rigorous proofs.

Experimental Results

Note: This paper contains no experimental results; all results are theoretical theorems.

Related Work

1. Classical Regularity Lemmas

• Gowers-Tao GT09: Lemma 2.4 provides tower-type bound regularity lemma
• Green Gree06: Lemma 3.11 used in higher-order Fourier analysis
• Erman-Sam-Snowden ESS19: Proposition 8.1 provides clear tower-type bound example

2. Regularization Results (Non-decomposition Type)

• Lampert-Ziegler LZ24, Lam23: Provide strong-bound regularization results, but do not provide decomposition in the form $P = F(\mathbf{X})$; instead place P into ideals generated by $X_i$

3. Structure vs Randomness

• Milićević Mil19: First polynomial rank bound
• Janzer Jan20: Improved rank bounds
• Cohen-Moshkovitz CM21: Prove partition rank and analytic rank equivalence over large fields
• Moshkovitz-Zhu MZ24: Quasi-linear bound $\text{rk}(P) \geq r \Rightarrow |\text{bias}(P)| \leq |\mathbb{F}|^{-c_dr/L(r)}$

4. Generalized Rank

• Green-Tao GT09: Define $\text{rank}_t(P)$
• Karam Kar23: Prove Theorem 1.1, but only with tower-type bounds

5. Arithmetic Circuits

• Kayal-Saha-Saptharishi KSS14: Superpolynomial lower bounds for depth-4 formulas
• Kumar-Saraf KS14: Depth-4 homogeneous formulas with top fan-in $\Theta(\log n)$ are already powerful

6. Weak Regularity for Graphs

• Frieze-Kannan FK99: Weak regularity lemma for graphs, inspiration for this paper

Advantages Over Related Work

• Qualitative Leap in Bounds: Improvement from tower-type to polynomial (in m)
• New Concept Introduction: Univariate degree provides new analytical perspective
• Unified Framework: Simultaneously addresses Karam's problem and arithmetic circuit problems

Conclusions and Discussion

Main Conclusions

1. Weak Regularity Lemma: Any m-variable d-degree polynomial group has a weak $q^{-r}$-regular decomposition of size $(mr)^{2^{d(1+o(1))}}$
2. Generalized Rank Bounds: $\text{rank}_{d/u}(\mathbf{P}) \leq (2m)^{2^{d(1+o(1))}}$, where $u = \text{udeg}(\mathbf{P})$
3. Arithmetic Circuit Upper Bounds: High univariate degree implies small top fan-in depth-4 formulas
4. Lower Bound Barrier: Circuit lower bound methods must consider the univariate degree parameter

Limitations

1. Finite Field Restriction:
   • Methods heavily depend on finite field probabilistic methods
   • Extension to infinite fields requires replacing bias concept with geometric or commutative algebra methods
   • Rank definition (Definition 2.3) needs adjustment for infinite fields
2. Characteristic Restriction: Requires $d < \text{char}(\mathbb{F})$ because:
   • Rank-to-bias conversion (Theorem 2.10) requires multilinear forms
   • Involves relationship between analytic rank and partition rank
3. Cost of Weakening:
   • Only guarantees one variable approximately independent, may be insufficient for all classical regularity lemma applications
   • Some results requiring global approximate independence cannot be directly generalized
4. Bound Dependencies:
   • While polynomial in m, the exponent $2^{d(1+o(1))}$ remains large for large degree d
   • For $\epsilon = q^{-r}$, bound's dependence on r is $(mr)^{2^{d(1+o(1))}}$
5. Univariate Degree Computation:
   • Definition of $\text{udeg}(\mathbf{P})$ involves minimization problem, actual computation may be difficult
   • For concrete polynomials, determining univariate degree may require nontrivial work

Future Directions

1. Infinite Field Generalization:
   • Replace probabilistic concepts with geometric concepts (e.g., dimension)
   • Explore applications of Kazhdan-Lampert-Polishchuk KLP24 results on Schmidt rank
2. Improved Bounds:
   • Can we further improve $2^{d(1+o(1))}$ to polynomial (in d)?
   • For special polynomial classes (e.g., symmetric polynomials), can we obtain better bounds?
3. Algorithmic Applications:
   • Design polynomial identity testing algorithms based on univariate degree
   • Explore applications in coding theory (e.g., Reed-Muller codes)
4. Lower Bound Techniques:
   • Develop circuit lower bound methods capable of handling high univariate degree
   • Understand relationships between univariate degree and other complexity measures
5. Generalization to Other Structures:
   • Can we develop analogous tensor weak regularity lemmas?
   • Generalizations to other algebraic structures (groups, rings)?

In-Depth Evaluation

Strengths

1. Breakthrough Bound Improvement:
   • Tower-type to polynomial is a qualitative leap
   • For constant degree $d = O(1)$, bound simplifies to $(2m)^C$, making results practically usable
   • Technical innovation (pencil concept) is elegant and natural
2. Conceptual Innovation:
   • Univariate degree $\text{udeg}$ is a new perspective for characterizing polynomial map images
   • Provides algebraic interpretation of understanding non-surjectivity
   • Connects combinatorics, algebra, and complexity theory
3. Proof Technique Depth:
   • Cleverly combines rank theory, Fourier analysis, and structure vs randomness
   • Fine analysis of homogeneous spaces (Lemmas 2.6-2.8) demonstrates deep understanding
   • Degree reduction mechanism's design for ensuring algorithm termination is ingenious
4. Breadth of Applications:
   • Simultaneously solves Karam's problem and arithmetic circuit problems
   • Reveals circuit lower bound barriers with deep complexity-theoretic implications
   • Methods likely applicable to more problems
5. Clear Exposition:
   • Clear structure, progressively developing from motivation to proof
   • Precise definitions, clear theorem statements
   • Examples and remarks aid understanding

Weaknesses

1. Absolute Bound Values:
   • While huge improvement relative to classical results, $2^{d(1+o(1))}$ remains large for large d
   • For $d = 100$, $2^{100}$ is still impractical
   • Unclear whether this is method limitation or problem's inherent difficulty
2. Finite Field Limitation:
   • Main results only proven for finite fields
   • Infinite field generalization path discussed but not realized
   • Limits direct use in some algebraic geometry applications
3. Univariate Degree Computability:
   • Definition involves minimization, computational complexity not discussed
   • For given polynomial, how to effectively determine $\text{udeg}$?
   • Lacks concrete examples showing computation
4. Insufficient Application Concreteness:
   • Theorem 1.2 provides arithmetic circuit upper bounds, but no concrete examples
   • For which specific polynomials or polynomial classes are these bounds tight?
   • Lacks comparison with known lower bounds
5. Technical Dependencies:
   • Critically depends on Moshkovitz-Zhu MZ24 results (Theorem 2.10)
   • If that result improves, this paper's bounds also improve, but currently limited by it
   • Loss of $c_d = 2^{-d^{1+o(1)}}$ ultimately reflects in bounds

Impact

1. Theoretical Contribution:
   • Major Breakthrough: First strong-bound regularity lemma
   • New Paradigm: Weak regularity may inspire similar relaxations in other fields
   • Bridge Role: Connects combinatorics, algebra, and complexity theory
2. Practical Value:
   • Medium-Degree Polynomials: Applications for $d \leq 10$ are practically feasible
   • Complexity Theory: Provides new perspective on understanding arithmetic circuit lower bound difficulties
   • Coding Theory: May improve Reed-Muller code analysis
3. Reproducibility:
   • Pure Theory Results: All proofs are constructive, verifiable in principle
   • Algorithmically Explicit: Theorem 2.5's proof provides explicit algorithm
   • No Experimental Dependence: Does not depend on computational experiments, strong reproducibility
4. Follow-up Research:
   • Existing work like Kar23 can be directly improved
   • May inspire new attempts at arithmetic circuit lower bounds
   • Univariate degree concept may become new research direction

Applicable Scenarios

1. Theoretical Research:
   • Problems needing regularity lemmas but sensitive to bounds
   • Studying structure of polynomial map images
   • Analyzing algebraic properties of non-surjective polynomials
2. Arithmetic Circuits:
   • Designing depth-4 formula upper bounds
   • Understanding top fan-in limitations
   • Developing lower bound methods considering univariate degree
3. Coding Theory:
   • Analyzing Reed-Muller code weight distribution
   • Studying polynomial code parameters
4. Additive Combinatorics:
   • Higher-order Fourier analysis of low-degree polynomials
   • Gowers norm estimation
5. Inapplicable Scenarios:
   • Problems requiring global approximate independence
   • High-degree polynomials ($d > 20$) quantitative analysis
   • Infinite field results needed in algebraic geometry

Key References

1. GT09 Green & Tao - The distribution of polynomials over finite fields (classical regularity lemma)
2. MZ24 Moshkovitz & Zhu - Quasi-linear relation between partition and analytic rank (best structure vs randomness bounds)
3. Kar23 Karam - Ranges of polynomials control degree ranks (main target of improvement)
4. FK99 Frieze & Kannan - Quick approximation to matrices (weak regularity inspiration)
5. ESS19 Erman, Sam & Snowden - Cubics in 10 variables vs. cubics in 1000 variables (clear tower-type bound example)

Overall Assessment: This is a breakthrough theoretical paper that achieves a qualitative leap from tower-type to polynomial bounds through introducing "weak" regularity concept. Technically profound, conceptually innovative, and broadly applicable. Despite limitations including finite field restriction and exponential dependence on degree, it makes important contributions to theoretical computer science and combinatorics. The univariate degree concept may become a new research direction, while revealed circuit lower bound barriers have deep complexity-theoretic implications. Recommended for researchers studying polynomial methods, arithmetic circuits, or additive combinatorics.