An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications

By Ben Joseph Green, Terence Tao. 2010

112 citations recorded by the source corpus.

To Endre Szemeredi on the occasion of his 70th birthday Szemeredi’s regularity lemma can be viewed as a rough structure theorem for arbitrary dense graphs, decomposing such graphs into a structured piece, a small error, and a uniform piece. We establish an arithmetic regularity lemma that similarly decomposes bounded functions f: [N] →ℂ, into a (well-equidistributed, virtual) s-step nilsequence, an error which is small in L2 and a further error which is minuscule in the Gowers Us+1-norm, where s ≥ 1 is a parameter. We then establish a complementary arithmetic counting lemma that counts arithmetic patterns in the nilsequence component of f.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/db9d5a36b1b02c4498af93352f3e7709bd209b23

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

Higher order Fourier analysis of multiplicative functions and applications (2014, methodology): “1 consists of a Fourier analysis energy increment argument, and avoids the use of finitary ergodic theory and the use of the Hahn-Banach theorem, tools that are typically used for other decomposition results (see [14, 15, 16, 21, 42]).”
Linear Forms and Higher-Degree Uniformity for Functions On $${\mathbb{F}^{n}_{p}}$$ (2010, background): “n ZN (the case k = 4 appears in [GrTZ09]), thereby raising the possibility of proving Conjecture 1.2 in full for ZN. As we were on the point of submitting this paper, Green and Tao did indeed do this [GrT10], which means that, at least from a qualitative point of view, the programme of which this pa”