##### Department of Mathematics,

University of California San Diego

****************************

### Combinatorics Seminar

## Kaave Hosseini

#### UCSD

## An Improved lower bound for arithmetic regularity

##### Abstract:

The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemeredi regularity lemma in graph theory. It shows that for any abelian group G and any bounded function $f : G \rightarrow [0, 1]$, there exists a subgroup $H \leq G$ of bounded index such that, when restricted to most cosets of $H$, the function f is pseudorandom in the sense that all its nontrivial Fourier coefficients are small. Quantitatively, if one wishes to obtain that for $1 - \epsilon$ fraction of the cosets, the nontrivial Fourier coefficients are bounded by $\epsilon$, then Green shows that $|G/H|$ is bounded by a tower of twos of height $1/\epsilon^3$. He also gives an example showing that a tower of height $\Omega(\log 1/\epsilon)$ is necessary. Here, we give an improved example, showing that a tower of height $\Omega(1/\epsilon)$ is necessary. Joint work with Shachar Lovett, Guy Moshkovitz, and Asaf Shapira.

Host: Jacques Verstraete

### February 24, 2015

### 3:00 PM

### AP&M 6402

****************************