# Invariance in Property Testing

A property is said to be invariant under a permutation $\pi$ if permuting the data points by this permutation leaves the property unchanged.

Invariance under permutations seems to help with property testing, see e.g. Algebraic Property Testing: The Role of Invariance by Tali Kaufman and Madhu Sudan, Property Testing of Equivalence under a Permutation Group Action by Sourav Chakraborty and Laszlo Babai, and Invariance in Property Testing by Madhu Sudan.

What is the general intuition for the invariance under permutations helping testing properties, e.g. testing properties of graphs?

The idea is the following. Suppose you have a property $\mathcal{P}$, defined as a collection of subsets of some domain $D$, and suppose that $\mathcal{P}$ is invariant under a permutation $\pi : D \to D$. In other words, a subset $S \subseteq D$ is in $\mathcal{P}$ iff $\pi(S)$ is also in $\mathcal{P}$. In testing, we want to determine whether a given set $S$ is in $\mathcal{P}$ or "far" from $\mathcal{P}$ by choosing a small number of points $X_1,\dots,X_q \in D$, querying whether each of them is a member of $S$ or not, and then making a decision based on the results of the queries. Suppose that a particular choice of points $z_1,\dots,z_q \in D$ constitutes a valid test. Then, the observation is that $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ also must constitute a valid test. Because using the test $\pi^{-1}(z_1),\dots,\pi^{-1}(z_q)$ on $S$ is the same as using the test $z_1, \dots, z_q$ on $\pi(S)$, and we know that $S \in \mathcal{P}$ iff $\pi(S) \in \mathcal{P}$. So, if $\mathcal{P}$ has a group of symmetry $\Pi \leq \mathsf{Sym}(D)$, then the entire orbit $\{(\pi(z_1),\dots,\pi(z_q)): \pi \in \Pi\}$ consists of valid tests. Thus, the larger the group $\Pi$ is, the more tests can be generated from a single test, and in fact, for many natural invariance groups, all possible tests can be generated from the orbits of a very restricted class of tests. When this is the case, it becomes much easier to give conditions for when a property is testable and when it's not.