Every locally characterized affine-invariant property is testable

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a
property of functions on F^n that is closed under taking affine
transformations of the domain. We prove that all affine-invariant property
having local characterizations are testable. In fact, we show a
proximity-oblivious test for any such property P, meaning that there is a test
that, given an input function f, makes a constant number of queries to f,
always accepts if f satisfies P, and rejects with positive probability if the
distance between f and P is nonzero. More generally, we show that any
affine-invariant property that is closed under taking restrictions to
subspaces and has bounded complexity is testable.

We also prove that any property that can be described as the property of
decomposing into a known structure of low-degree polynomials is locally
characterized and is, hence, testable. For example, whether a function is a
product of two degree-d polynomials, whether a function splits into a product
of d linear polynomials, and whether a function has low rank are all examples
of degree-structural properties and are therefore locally characterized.

Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low
characteristic fields that decomposes any polynomial with large Gowers norm
into a function of low-degree non-classical polynomials. We establish a new
equidistribution result for high rank non-classical polynomials that drives
the proofs of both the testability results and the local characterization of
degree-structural properties.

Joint work with Eldar Fischer, Hamed Hatami, Pooya Hatami, and Shachar
Lovett.