Gowers Norm, Function Limits, and Parameter Estimation

Abstract

Let $\{f_i:{\mathbb{F}}_p^i\to \{0,1\}\}$ be a sequence of functions, where $p$ is a fixed prime and ${\mathbb{F}}_p$ is the finite field of order $p$. The limit of the sequence can be syntactically defined using the notion of ultralimit. Inspired by the Gowers norm, we introduce a metric over limits of function sequences, and study properties of it. One application of this metric is that it provides a characterization of affine-invariant parameters of functions that are constant-query estimable. Using this characterization, we show that the property of being a function of a constant number of low-degree polynomials and a constant number of factored polynomials (of arbitrary degrees) is constant-query testable if it is closed under blowing-up. Examples of this property include the property of having a constant spectral norm and degree-structural properties with rank conditions.

arXiv admin note: text overlap with arXiv:1212.3849, arXiv:1308.4108 by other authors