printable pdf
比利时vs摩洛哥足彩 ,
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

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