比利时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
****************************