Sparse affine-invariant linear codes are locally testable

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field $${\mathbb{F}_q}$$Fq and an extension field $${\mathbb{F}_{q^n}}$$Fqn, a property is a set of functions mapping $${\mathbb{F}_{q^n}}$$Fqn to $${\mathbb{F}_q}$$Fq. The property is said to be affine-invariant if it is invariant under affine transformations of $${\mathbb{F}_{q^n}}$$Fqn, linear if it is an $${\mathbb{F}_q}$$Fq -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.