An improved lower bound for arithmetic regularity
| Autor: | Shachar Lovett, Asaf Shapira, Kaave Hosseini, Guy Moshkovitz |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Lemma (mathematics)
General Mathematics 010102 general mathematics Szemerédi regularity lemma Graph theory 0102 computer and information sciences 01 natural sciences Upper and lower bounds Pure Mathematics 010201 computation theory & mathematics Bounded function FOS: Mathematics Coset Mathematics - Combinatorics Combinatorics (math.CO) 0101 mathematics Arithmetic Abelian group Fourier series Mathematics |
| Zdroj: | Mathematical Proceedings of the Cambridge Philosophical Society, vol 161, iss 2 Mathematical Proceedings of the Cambridge Philosophical Society Hosseini, K; Lovett, S; Moshkovitz, G; & Shapira, A. (2016). An improved lower bound for arithmetic regularity. MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 161(2), 193-197. doi: 10.1017/S030500411600013X. UC San Diego: Retrieved from: http://www.escholarship.org/uc/item/4p7012j5 |
| DOI: | 10.1017/S030500411600013X. |
| Popis: | The arithmetic regularity lemma due to Green [GAFA 2005] is an analogue of the famous Szemerédi regularity lemma in graph theory. It shows that for any abelian group G and any bounded function f : G → [0, 1], there exists a subgroup H ⩽ 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 − ε fraction of the cosets, the nontrivial Fourier coefficients are bounded by ε, then Green shows that |G/H| is bounded by a tower of twos of height 1/ε3. He also gives an example showing that a tower of height Ω(log 1/ε) is necessary. Here, we give an improved example, showing that a tower of height Ω(1/ε) is necessary. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|