We argue that the symmetries of a property being tested play a
central role in property testing. We support this assertion in the
context of algebraic functions, by examining properties of functions
mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.
We consider $\F$-linear properties that are invariant under linear
transformations of the domain and prove that an $O(1)$-local
``characterization'' is a necessary and sufficient condition for
$O(1)$-local testability when $|\K| = O(1)$. (A local
characterization of a property is a definition of a property in
terms of local constraints satisfied by functions exhibiting a
property.) For the subclass of properties that are invariant under
affine transformations of the domain, we prove that the existence of
a {\em single} $O(1)$-local constraint implies $O(1)$-local
testability. These results generalize and extend the class of
algebraic properties, most notably linearity and low-degree-ness,
that were previously known to be testable. In particular, the
extensions include properties satisfied by functions of degree
linear in $n$ that turn out to be $O(1)$-locally testable.
Our results are proved by introducing a new notion that we term
``formal characterizations''. Roughly this corresponds to
characterizations that are given by a single local constraint and
its permutations under linear transformations of the domain. Our
main testing result shows that local formal characterizations
essentially imply local testability. We then investigate properties
that are linear-invariant and attempt to understand their local
formal characterizability. Our results here give coarse upper and
lower bounds on the locality of constraints and characterizations
for linear-invariant properties in terms of some structural
parameters of the property we introduce. The lower bounds rule out
any characterization, while the upper bounds give formal
characterizations. Combining the two gives a test for all
linear-invariant properties with local characterizations.
We believe that invariance of properties is a
very interesting notion to study in the context
of property testing, in general and merits a systematic study.
In particular, the class of linear-invariant and affine-invariant
properties exhibits a rich variety among algebraic properties and
offer better intuition about algebraic properties than the more
limited class of low-degree functions.
