On Sums of Locally Testable Affine Invariant Properties

Affine-invariant properties are an abstract class of properties that generalize some central algebraic ones, such as linearity and low-degree-ness, that have been studied extensively in the context of property testing. Affine invariant properties consider functions mapping a big field

$\mathbb{F}_{q^n}$

to the subfield

$\mathbb{F}_q$

and include all properties that form an

$\mathbb{F}_q$

-vector space and are invariant under affine transformations of the domain. Almost all the known locally testable affine-invariant properties have so-called “single-orbit characterizations” — namely they are specified by a single local constraint on the property, and the “orbit” of this constraint, i.e., translations of this constraint induced by affine-invariance. Single-orbit characterizations by a local constraint are also known to imply local testability. In this work we show that properties with single-orbit characterizations are closed under “summation”. To complement this result, we also show that the property of being an

n

-variate low-degree polynomial over

$\mathbb{F}_q$

has a single-orbit characterization (even when the domain is viewed as

$\mathbb{F}_{q^n}$

and so has very few affine transformations). As a consequence we find that the sum of any sparse affine-invariant property (properties satisfied by

q

O

(

n

)

-functions) with the set of degree

d

multivariate polynomials over

$\mathbb{F}_q$

has a single-orbit characterization (and is hence locally testable) when

q

is prime. We conclude with some intriguing questions/conjectures attempting to classify all locally testable affine-invariant properties.