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

Abstract

To Endre Szemerédi on the occasion of his 70th birthday Szemerédi'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.

Locations

• Bolyai Society mathematical studies - View
• arXiv (Cornell University) - View - PDF
• Bolyai Society mathematical studies - View
• arXiv (Cornell University) - View - PDF