Limits of Boolean Functions on $\mathbb{F}_p^n$
| Autor: | Pooya Hatami, James Hirst, Hamed Hatami |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Discrete mathematics
Sequence Measurable function Applied Mathematics Order (ring theory) Regularization (mathematics) Theoretical Computer Science Combinatorics Computational Theory and Mathematics Affine space Discrete Mathematics and Combinatorics Geometry and Topology Limit (mathematics) Abelian group Boolean function Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 21 |
| ISSN: | 1077-8926 |
| Popis: | We study sequences of functions of the form $\mathbb{F}_p^n \to \{0,1\}$ for varying $n$, and define a notion of convergence based on the induced distributions from restricting the functions to a random affine subspace. Using a decomposition theorem and a recently proven equi-distribution theorem from higher order Fourier analysis, we prove that the limits of such convergent sequences can be represented by certain measurable functions. We also show that every such limit object arises as the limit of some sequence of functions. These results are in the spirit of similar results which have been developed for limits of graph sequences. A more general, albeit substantially more sophisticated, limit object was recently constructed by Balázs Szegedy [Gowers norms, regularization and limits of functions on abelian groups. 2010. arXiv:1010.6211]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|