A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word
to the code can be tested by querying the received word in a few coordinates.
Locally testable codes have played a critical role in the construction of probabilistically checkable proofs and most such codes originate from simple affine invariant codes (in particular the Reed-Muller codes). Furthermore it turns out that the local testability of these codes can really be attributed to their affine-invariance. It was hoped that by studying broader classes of affine-invariant
codes, one may find nicer, or simpler, locally testable codes, and in particular improve (significantly) on the rate achieved
by Reed-Muller codes.

In this work we show that low-rate is an inherent limitation of
affine-invariant codes.
We show that any $k$-query affine-invariant
binary code is contained in an $2^k$-query testable Reed-Muller code.
In fact our result shows that any affine-invariant code that has
a $k$-local constraint (i.e., a weight $k$ codeword in its dual),
a necessary condition for $k$-query local
testability, is contained in a Reed-Muller code that is
$2^k$-locally characterized (i.e., its dual is spanned by
words of weight at most $2^k$).

While the structure of affine-invariant codes has been explored
quite extensively in the recent past [Kaufman and Sudan 2008; Grigorescu et al. 2008, 2009], relating the locality of constraints in such codes to the rate
has been a non-trivial challenge. Such questions lead
to the task of showing that a class of systems of multivariate
polynomial equations have no common zeroes over finite fields.
Our result effectively shows a certain class of such systems
(subclasses of diagonal systems) that have no common zeroes.