A weak regularity lemma for polynomials
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914598471335936 |
|---|---|
| author | Moshkovitz, Guy Woodruff, Dora |
| author_facet | Moshkovitz, Guy Woodruff, Dora |
| contents | A regularity lemma for polynomials provides a decomposition in terms of a bounded number of approximately independent polynomials. Such regularity lemmas play an important role in numerous results, yet suffer from the familiar shortcoming of having tower-type bounds or worse. In this paper we design a new, weaker regularity lemma with strong bounds. The new regularity lemma in particular provides means for quantitatively studying the curves contained in the image of a polynomial map, which is beyond the reach of standard methods.
The weak regularity lemma turns out to be powerful enough to yield results on arithmetic circuits and polynomial ranks that may be of independent interest:
- A general upper bound on the arithmetic circuit size of low-degree polynomials based solely on their image.
- An upper bound on the top fan-in of depth-4 arithmetic formulas under similar conditions.
- A quantitative bound for the Green-Tao notion of rank for polynomials, significantly improving on a result of Karam. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21536 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A weak regularity lemma for polynomials Moshkovitz, Guy Woodruff, Dora Combinatorics Computational Complexity Commutative Algebra 11T06, 11B30, 68Q06 A regularity lemma for polynomials provides a decomposition in terms of a bounded number of approximately independent polynomials. Such regularity lemmas play an important role in numerous results, yet suffer from the familiar shortcoming of having tower-type bounds or worse. In this paper we design a new, weaker regularity lemma with strong bounds. The new regularity lemma in particular provides means for quantitatively studying the curves contained in the image of a polynomial map, which is beyond the reach of standard methods. The weak regularity lemma turns out to be powerful enough to yield results on arithmetic circuits and polynomial ranks that may be of independent interest: - A general upper bound on the arithmetic circuit size of low-degree polynomials based solely on their image. - An upper bound on the top fan-in of depth-4 arithmetic formulas under similar conditions. - A quantitative bound for the Green-Tao notion of rank for polynomials, significantly improving on a result of Karam. |
| title | A weak regularity lemma for polynomials |
| topic | Combinatorics Computational Complexity Commutative Algebra 11T06, 11B30, 68Q06 |
| url | https://arxiv.org/abs/2509.21536 |