Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

In [31], the authors relate the analysis of the $t$-flat tester of the Reed-Muller code to expansion properties of the affine Grassmann graph. Here, the affine Grassmann graph is the graph whose vertex set is the set of all $t$-flats in $\mathbb{F}_{q}^{n}$, and two vertices are adjacent if they intersect in a $t-1$ dimensional affine subspace. In short, the approach of [31] starts with the assumption that the $t$-flat tester accepts $f$ with probability at least $1-\varepsilon$ (for $\varepsilon$ thought of as small) and proceeds to prove a structural result on the set of $t$-flats on which the tester rejects:

In particular, using a lemma from [21] they prove that the set $S$ has poor expansion properties in the affine Grassmann graph, and use it to prove that there exists a point $x^{\star}\in\mathbb{F}_{q}^{n}$ such that the tester almost always rejects when it selects a subspace $T$ containing $x^{\star}$. This suggests that $f$ is erroneous at $x^{\star}$ and should be corrected, and indeed using that a local correction procedure is devised in [31] to show that the value of $f$ at $x^{\star}$ could be changed and lead to an increase in the acceptance probability of additive factor $q^{t-n-O(1)}$. Iterating this argument, one eventually changes $f$ in at most $C(q)\cdot q^{-t}\varepsilon$ fraction of the inputs and gets a function $f^{\prime}$ on which the tester accepts with probability $1$. Such $f^{\prime}$ must be of degree at most $d$, hence one gets that $f$ is close to a degree $d$ polynomial.

While the approach of [31] seems to be more robust and thus potentially applicable towards analyzing a richer class of codes, it is not completely obvious how to do so. For the $t$-flat tester one may associate a very natural graph with the tester, but this is much less clear in the context of the sparse $t$-flat tester (which is the tester that we analyze). The pattern of inputs which are queried by the tester is no longer a nice-looking subspace (but this seems inherent in order to improve upon the query complexity of the flat tester).

At a high level, we show that another way of approaching this problem is by utilizing the symmetries of the code and constructing graphs on them. For that, we have to think of the tester as the composition of a “basic tester” and a random element from the group of symmetries of the code. In our case, the group of symmetries is the group of affine linear transformations over $\mathbb{F}_{q}^{n}$, and the graph that turns out to be related to the analysis of the sparse $t$-flat tester is the so-called Affine Bi-linear Scheme Graph.

At first sight, affine linear transformations seem to be morally equivalent to flats (identifying the image of an affine linear transformation with a subspace), and indeed there are many connections between results on the former graph and result on the latter graph. However, the distinction between affine linear transformations and flats will be crucial for us. Indeed, while two affine linear transformations $A_{1}$ and $A_{2}$ may have the same image, the performance of the tester when choosing $A_{1}$ and when choosing $A_{2}$ will not be the same whatsoever, and therefore we must capitalize on this distinction in our soundness analysis.

The construction of the sparse flat tester of [33] begins with the following observation. In the $p=2$ case, define the bivariate polynomial $P\colon\mathbb{F}_{q}^{2}\to\mathbb{F}_{q}$ by

In [33], the authors observe the following two crucial properties of $P$ that make it useful towards getting a local testing result:

1. 1.

   Sparse Support: the support of $P$ has size at most $3q$; indeed, if $x_{1}+x_{2}\neq 0$, $x_{1}\neq 0$ and $x_{2}\neq 0$, then by Fermat’s little theorem $(x_{1}+x_{2})^{q-1}=x_{2}^{q-1}=1$ and $x_{1}\neq 0$, so $P(x_{1},x_{2})=0$.

2. 2.

   Detects the Monomials $x_{1}^{q-i}x_{2}^{i}$: looking at the inner product of $P$ with a monomial $M$, defined as $\langle{P},{M}\rangle=\sum\limits_{x_{1},x_{2}}P(x_{1},x_{2})M(x_{1},x_{2})$, we get that if $M=x_{1}^{q-i}x_{2}^{i}$ for $i\in\{1,\ldots,q-1\}$ then $\langle{P},{M}\rangle\neq 0$. Indeed,

   $$\langle{P},{M}\rangle=\sum\limits_{j=0}^{q-2}\sum\limits_{x_{1}}x_{1}^{q-i+j}\sum\limits_{x_{2}}x_{2}^{q-2-j+i}=\sum\limits_{j=0}^{q-2}(q-1)1_{q-i+j=q-1}(q-1)1_{q-2-j+i=q-1},$$

   so we only have contribution from $j=i-1$ and it is non-zero. For any other monomial $M$, a similar computation shows that $\langle{P},{M}\rangle=0$, hence taking an inner product of a function $f$ with $P$ may be thought of detecting whether in $f$ there is some monomial of the form $x_{1}^{q-i}x_{2}^{i}$.

With this in mind, the sparse tester follows. In [33] it is argued that to design a local tester for the generalized Reed-Muller code it suffices to design a tester that detects whether certain canonical monomials exist. Writing $d+1=s\cdot\frac{q}{2}+r$, where $s$ is even and $r<q$, it is sufficient to detect whether any monomials of the form $\prod_{i=1}^{s/2}x_{2i-1}^{q/2}x_{2i}^{q/2}\cdot\prod\limits_{i=s+1}^{s+t}x_{i}^{e_{i}}$ where $\sum_{i=1}^{t}e_{i}\geqslant r$ and $t$ is a small constant (say, $t=10$). Using $P$ from above, a detector for such monomials is given by

where $e^{\prime}+e=(q-1,\ldots,q-1)$ and $M_{e^{\prime}}(x_{s+1},\ldots,x_{s+t})=\prod\limits_{i=s+1}^{s+t}x_{i}^{q-1-e_{i}}$. We note that most of the degree of $H_{e^{\prime}}$ comes from the product of the $P$’s, while at most $t(q-1)-r$ of the degree comes from the rest. As the support of $P$ is rather sparse, it follows that the support of $H_{e^{\prime}}$ is also rather sparse. More precisely, the support of $H_{e^{\prime}}$ has size at most $(3q)^{\frac{s}{2}+t}$, and as $t$ should be thought of as small and $s$ is roughly $2d/q$, the support of $H_{e^{\prime}}$ has size roughly $(3q)^{d/q}$. This yields a query complexity of $(3q)^{d/q}$, which is quadratically better than $q^{\lceil\frac{d}{q-q/p}\rceil}\approx q^{2d/q}$ given by the flat tester.

As mentioned earlier, the soundness analysis in [33] relies on a black box result from [25]. They manage to show that the detector they construct implies a tester with the same query complexity that rejects functions that are $\delta$-far from Reed-Muller codewords with probability $\Omega((3q)^{-2(s/2+t)}\delta)$. To get constant rejection probability one has to repeat the tester $(3q)^{2(s/2+t)}$ times and drastically increasing the query complexity; we defer a more detailed discussion to Section 3.

Our first task in proving Theorem 1.1 is to design a tester based on the ideas from [33]. The tester is very natural:

1. 1.

   Sample a random affine map $T\colon\mathbb{F}_{q}^{s+t}\to\mathbb{F}_{q}^{n}$; here, $s$ and $t$ should be thought of as in the previous section. We are going to look at the function $f\circ T$, but not query all of its values (indeed, querying all of its values would amount to the $(s+t)$-flat tester).

2. 2.

   For any sequence of degrees $e=(e_{s+1},\ldots,e_{s+t})$ such that $\sum_{i=1}^{t}q-1-e_{i}\geqslant r$, take $H_{e}$ and compute $\langle{f\circ T},{H_{e}}\rangle$. Reject if this inner product is non-zero for any such degree sequence. Otherwise, accept.

In words, we first take the restriction of $f$ to a random $(s+t)$-flat, and then apply the detector polynomials of [33]. Although we test for multiple degree sequences (up to $q^{t}$), we will see in Section 3 that the support of $H_{e}$ is the same in each case. Therefore, we can perform the inner product for all of the degree sequences using the same $q^{s+t}$ queries. Another way to think about this tester is that we have the group of symmetries of the Reed-Muller code (affine linear transformations), and our tester proceeds by first taking a random symmetry from this group, taking a restriction, and then using the detector of [33].

With the above tester in mind, the next question is how to analyze it. In the case of the flat tester we had a very natural graph associated with the tester (the affine Grassmann graph). The above tester seems related to flats as well, since the image of an affine transformation is a flat; however, there is a key, crucial distinction between the two. In the above tester, we are only going to look at the value of $f$ at a few locations in $\operatorname{Im}(T)$, hence the tester may perform differently on $T$ and $T^{\prime}$ even if they have identical images. This lack of symmetry is crucial for the sparseness of the test, but makes the task of associating a graph with the tester trickier.

To gain some intuition as to what this graph is supposed to be, recall that in the flat testers, one could look at the $t$-flat tester for all $t$ (not necessarily the smallest one). The relations between these testers for different $t$’s play a crucial role in all of the works establishing optimal testing results, and in particular it is known that the rejection probability of the $(t+1)$-flat tester is at most $q$ times the rejection probability of the $t$-flat tester. We will elaborate on this property a bit later (referred to as the “shadow lemma” below). Another benefit of looking at various testers is that it gives a natural way of arriving at the affine Grassmann graph, by doing an up-down walk between these testers. To obtain the edges of the affine Grassmann graph, one can start with a $t$-flat, go up to a $(t+1)$-flat that contains it, and then back down to a $t$-flat contained in the $(t+1)$-flat. What is the right analog of this operation in the context of the sparse flat tester?

The shadow lemma is a result asserting a relation between the rejection probability of a $(s+t+1)$ tester and the $(s+t)$ tester.

Equipped with the understanding that $S$ is a small set (as we assume the sparse flat tester rejects with small probability) and $\Phi(S)\leqslant 1-\frac{1}{q}$, the next question is what sort of structure this implies. In the bi-linear scheme graph there are natural examples of such sets, which are analogs of the zoom-in/ zoom-out sets in the context of subspaces. Roughly speaking, there is one type of examples which intuitively should be relevant for us, which is zoom-in sets:

There are other examples of small sets which have poor expansion in the bi-linear scheme graph, however these seem “irrelevant” in the present context. Indeed, after showing that our small set $S$ cannot be correlated with any of these other examples (a notion which is often referred to as pseudo-randomness with respect to zoom-outs and zoom-ins on the linear part), we use the theory of global hypercontractivity to prove that there must be $x^{\star}$ and $y^{\star}$ such that $\mu(S\cap\mathcal{C}_{x^{\star},y^{\star}})\geqslant(1-o(1))\mu(\mathcal{C}_{x^{\star},y^{\star}})$. In words, the sparse $(s+t)$-flat tester almost always rejects inside $\mathcal{C}_{x^{\star},y^{\star}}$.

We remark that the proof that $S$ has no “correlation” with any other non-expanding set in the bi-linear scheme is rather tricky, and much of the effort in the current paper is devoted to that. To do so, we have to build upon ideas from [31] as well as use a new relation between the sparse $(s+t)$-flat tester applied on a function $f$ and the $t$-flat tester applied on a related function $\tilde{f}$. As the construction of this related function is somewhat technical, we defer a detailed discussion of it to Section 3.5.

Intuitively, the only way that $S$ could be dense inside some $\mathcal{C}_{x^{\star},y^{\star}}$ is if we started with a Reed-Muller codeword $g$, and perturbed it on a small number of inputs, of which $y^{\star}$ is one. Indeed, in this case we would have that $\langle{g\circ T},{H_{e}}\rangle=0$ for all $T\in\mathcal{C}_{x^{\star},y^{\star}}$ and exponent vectors $e$ checked by the tester prior to perturbing, and after changing the value of $g$ at $y^{\star}$, we would also change the value of $g\circ T$ at $x^{\star}$, breaking our previous equality. This intuition suggests that $y^{\star}$ is a point in which we should fix the value of $f$ and get closer to a Reed-Muller codeword, and we show that this is indeed the case.

There are several difficulties that arise when inspecting this argument more deeply. If $H_{e}(x^{\star})=0$, then the above reasoning breaks (as the value of $f$ at $y^{\star}$ is multiplied by $0$); however, in this case it does not make sense that $S$ could be very dense inside $\mathcal{C}_{x^{\star},y^{\star}}$ (as essentially the only input of $f$ included in the inner product is $f(y^{\star})$, but in any case it is multiplied by $H_{e}(x^{\star})=0$). Indeed, in our argument we show that if $S$ is very dense in $\mathcal{C}_{x^{\star},y^{\star}}$, then it must be the case that $H_{e}(x^{\star})\neq 0$. Moreover, we show that the density of $S$ inside $\mathcal{C}_{x^{\star},y^{\star}}$ and inside $\mathcal{C}_{{x^{\star}}^{\prime},y^{\star}}$ is roughly the same for all $x^{\star}$ and ${x^{\star}}^{\prime}$ in the support of $H_{e}$. This last step is crucial for the analysis to go through and requires us to adapt and strengthen techniques from [31]. At the end of this step, roughly speaking, we conclude that the tester rejects with probability close to $1$ whenever it queries the value of $f$ at $y^{\star}$.

The last step in the argument is to show that we can change the value of $f$ at $y^{\star}$ and decrease the rejection probability of the tester by additive factor of $\Theta(q^{s+t-n})$ (which is proportional to the probability that the tester looks at $y^{\star}$). We do so by a reduction to the same problem over the standard flat tester (which was solved in [31]). The idea is to look at somewhat larger tester of dimension $s+t+100$, fix the first $s$ coordinates and let the rest vary, so that the tester becomes a local version of the standard flat tester.

Given that, and iterating the argument, we eventually reach a function $f^{\prime}$ that differs from $f$ on at most $\Theta(\varepsilon/q^{s+t-n})$ of the inputs (where $\varepsilon$ is the original rejection probability) and passes the test with probability $1$. Hence, $f^{\prime}$ is a Reed-Muller codeword, and so $f$ is $O(\varepsilon/Q)$ close to a Reed-Muller codeword.

It will be helpful for us to consider the following equivalent, two-step process for sampling a neighbor of $T_{1}=(M_{1},c_{1})\in\mathcal{T}_{n,\ell}$ in the affine bi-linear scheme graph:

1. 1.

   Go Up: Choose a random $w\neq 0$. Let $M^{\prime}$ be the matrix obtained by appending the $w$ as a new column to $M_{1}$, and $T^{\prime}=(M^{\prime},c)\in\mathcal{T}_{n,\ell+1}.$

2. 2.

   Go Down: Choose a random $R=(A,b)\in\mathcal{T}_{\ell+1,\ell}$, where the first $\ell$ rows of $A$ are the identity matrix and the first $\ell$ entries of $b$ are $0$, and at least one entry out of the last row in $A$ and the last entry in $b$ is nonzero.

3. 3.

   Output $T_{2}=T^{\prime}\circ R$.

It is easy to see that for $T_{2}=(M_{2},c_{2})$, each column of $M_{2}$ is equal to the corresponding column in $M_{1}$ plus some multiple of $w$ and likewise for $c_{2}$ and $c_{1}$.

As explained in the introduction, our proof considers the set $\mathcal{S}$ of affine-transformations on which the test rejects as a set of vertices in the affine bi-linear scheme graph. We prove that $\mathcal{S}$ has small edge expansion in that graph, and then use global hypercontractivity in order to derive some conclusion about the structure of $\mathcal{S}$, which is in turn helpful towards a local correction argument.

To facilitate this argument, we must first understand the structure of a few canonical examples of non-expanding sets in ${\sf AffBilin}(n,\ell)$. In the affine Grassmann graph one has the following examples:

• •

  zoom-ins: $\mathcal{D}_{a}=\{U\in{\sf AffGras}(n,\ell)\;|\;a\in U\}$, for $a\in\mathbb{F}_{q}^{n}$.

• •

  zoom-outs: $\mathcal{D}_{W}=\{U\in{\sf AffGras}(n,\ell)\;|\;U\subseteq W\}$, for a hyperplane $W\subseteq\mathbb{F}_{q}^{n}$.

• •

  zoom-ins on the linear part: $\mathcal{D}_{a,\operatorname{lin}}=\{U=z+V\in{\sf AffGras}(n,\ell)\;|\;a\in V\}$, for $a\in\mathbb{F}_{q}^{n}$.

• •

  zoom-outs on the linear part: $\mathcal{D}_{W,\operatorname{lin}}=\{U=z+V\in{\sf AffGras}(n,\ell)\;|\;V\subseteq W\}$, for a hyperplane $W\subseteq\mathbb{F}_{q}^{n}$.

It is not hard to see that each example has expansion at most $1-1/q$; also, it is an easy calculation to show that the density of each one of these sets is small (and is vanishing provided that $\ell$ is significantly smaller than $n$ and both go to infinity). Each of these examples also has a counterpart in ${\sf AffBilin}(n,\ell)$:

• •

  zoom-ins: $\mathcal{C}_{a,b}=\{T\in\mathcal{T}_{n,\ell}\;:\;T(a)=b\}$, for $a\in\mathbb{F}_{q}^{\ell}$ and $b\in\mathbb{F}_{q}^{n}$.

• •

  zoom-outs: $\mathcal{C}_{a^{T},b,\beta}=\{(M,c)\in\mathcal{T}_{n,\ell}\;:\;a^{T}\cdot M=b,\;a^{T}\cdot c=\beta\}$, for $a\in\mathbb{F}_{q}^{n}$, $b\in\mathbb{F}_{q}^{\ell}$, and $\beta\in\mathbb{F}_{q}$.

• •

  zoom-ins on the linear part: $\mathcal{C}_{a,b,\operatorname{lin}}=\{(M,c)\in\mathcal{T}_{n,\ell}\;:\;M\cdot a=b\}$, for $a\in\mathbb{F}_{q}^{\ell}$ and $b\in\mathbb{F}_{q}^{n}$.

• •

  zoom-outs on the linear part: $\mathcal{C}_{a^{T},b,\operatorname{lin}}=\{(M,c)\in\mathcal{T}_{n,\ell}\;:\;a^{T}\cdot M=b\}$, for $a,\in\mathbb{F}_{q}^{n}$, and $b\in\mathbb{F}_{q}^{\ell}$.

Likewise, one can check that each example here also has expansion at most $1-1/q$ in ${\sf AffBilin}(n,\ell)$. Our argument will require us to show that, in a sense, these examples exhaust all small sets of vertices in ${\sf AffBilin}(n,\ell)$ whose edge expansion is at most $1-1/q$. To formalize this, we first define the notion of pseudo-randomness. Intuitively, we say that a set $S$ is pseudo-random with respect to some example – say zoom-ins for concreteness – if $S$ may only have little correlation with $\mathcal{C}_{a,b}$’s, in the sense that the density of $S$ inside such sets is still small. More precisely: