Abstract: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 tools for quantitatively studying the curves contained in the image of a polynomial map, which is beyond the reach of standard rank 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 polynomial maps based solely on their image: if the image avoids curves of degree below $u$ then there is an arithmetic circuit of size $n^{\lfloor d/u \rfloor + o(1)}$, a power-saving bound compared to the typical $n^{d-o(1)}$ bound for degree-$d$ polynomials.
- 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.
From: Guy Moshkovitz [view email]
[v1]
Thu, 25 Sep 2025 20:22:43 UTC (70 KB)
[v2]
Wed, 5 Nov 2025 15:14:37 UTC (72 KB)
[v3]
Mon, 25 May 2026 15:42:32 UTC (34 KB)
[v4]
Sun, 2 Aug 2026 07:29:15 UTC (41 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。