Authors Elad Haramaty, Noga Ron-Zewi, Madhu Sudan,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2013
Absolutely Sound Testing of Lifted Codes
Elad Haramaty∗ Noga Ron-Zewi† Madhu Sudan
Received September 11, 2013; Revised February 23, 2015; Published August 13, 2015
Abstract: In this paper we present a strong analysis of the testability of a broad, and to
date the most interesting known, class of “affine-invariant” codes. Affine-invariant codes are
codes whose coordinates are associated with a vector space and in addition these codes are
invariant under affine transformations of the coordinate space. Affine-invariant linear codes
form a natural abstraction of algebraic properties such as linearity and low-degree, which
have been of significant interest in theoretical computer science in the past. The study of
affine-invariance is motivated in part by its relationship to property testing: affine-invariant
linear codes tend to be locally testable under fairly minimal and almost necessary conditions.
Recent work by Ben-Sasson et al. (CCC 2011) and Guo et al. (ITCS 2013) introduced a
new class of affine-invariant linear codes based on an operation called “lifting.” Given a base
code over a t-dimensional space, its m-dimensional lift consists of all words whose restriction
to every t-dimensional affine subspace is a codeword of the base code. Lifting not only
An extended abstract of this paper appeared in the Proceedings of the 17th International Workshop on Randomization and
Computation (RANDOM’13), pages 671-682, 2013.
∗ Research supported in part by NSF grant CCF-1319206. Research was mainly conducted while the author was an intern at
Microsoft Research New-England, Cambridge, MA.
† Supported in part by the Rothschild fellowship and NSF grant CCF-1412958. Research was conducted in part while the
author was visiting Microsoft Research New-England, Cambridge, MA, and supported in part by a scholarship from the Israel
Ministry of Science and Technology. The research leading to these results has received funding from the European Community’s
Seventh Framework Programme (FP7/2007-2013) under grant agreement number 257575.
ACM Classification: H.1.1, F.1.3
AMS Classification: 68W20, 68Q87
Key words and phrases: locally testable codes, affine-invariant codes, lifted codes, query complexity,
soundness
© 2015 Elad Haramaty, Noga Ron-Zewi and Madhu Sudan
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2015.v011a012
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
captures the most familiar codes, which can be expressed as lifts of low-degree polynomials,
it also yields new codes whose rate is better than that of the corresponding polynomial
codes, and all other combinatorial qualities are no worse, when applied to “medium-degree”
polynomials.
In this paper we show that codes obtained by lifting are also testable in an “absolutely
sound” way. Specifically, we consider the natural test: Pick a random affine subspace of
base dimension and verify that a given word is a codeword of the base code when restricted
to the chosen subspace. While this test accepts codewords with probability one, we show
that it rejects words at constant distance from the code with constant probability (depending
only on the alphabet size). This work thus extends the results of Bhattacharyya et al. (FOCS
2010) and Haramaty et al. (FOCS 2011), while giving concrete new codes of higher rate that
have absolutely sound testers. In particular, we show that there exist codes satisfying the
requirements of Barak et al. (FOCS 2012) for constructing small-set expanders with a large
number of eigenvalues close to the maximal one, with rate slightly higher than that of the
codes used in their work.
1 Introduction
We present results on the testability of “affine-invariant linear codes.” We start with some basic terminol-
ogy before describing our work in greater detail.
Let q be a prime power, Q be a power of q and let Fq (and FQ ) denote the finite fields of order q
(and Q, respectively). Finally, let {FnQ → Fq } denote the set of functions mapping FnQ to Fq . In this
work a code (or a family) will be a subset of functions F ⊆ {FnQ → Fq }. We use δ ( f , g) to denote the
normalized Hamming distance between f and g, i. e., the fraction of inputs x ∈ FnQ for which f (x) 6= g(x).
We use δ (F) to denote min f 6=g, f ,g∈F {δ ( f , g)} and δF ( f ) to denote ming∈F {δ ( f , g)}. A code F is said
to be a linear code if it is an Fq -subspace, i. e., for every α ∈ Fq and f , g ∈ F, we have α f + g ∈ F. A
function T : FnQ → FnQ is said to be an affine transformation if there exists a matrix B ∈ Fn×n Q and vector
c ∈ FnQ such that T (x) = Bx + c. The code F ⊆ {FnQ → Fq } is said to be affine-invariant if for every affine
transformation T and every f ∈ F we have f ◦ T ∈ F (where ( f ◦ T )(x) = f (T (x))).
When Q = q, affine-invariant linear codes form a very natural abstraction of the class of low-degree
polynomials: the set of n-variate polynomials of degree at most d over Fq is a linear subspace and
is closed under affine transformations. Furthermore, as shown by Kaufman and Sudan [18], affine-
invariant linear codes retain some of the “locality” properties of multivariate polynomial codes (or
Reed-Muller codes), such as local testability and local decodability, that have found many applications
in computational complexity. This has led to a sequence of papers exploring these codes, but most
of this work produced codes of smaller rate than known ones, or gave an alternative understanding of
known codes [12, 11, 6, 5, 4]. Recent work by Guo et al. [14], however, changes the picture significantly.
They study a “lifting” operator on codes and show that it leads to codes with, in some cases dramatic,
improvement in parameters compared to Reed-Muller codes. Our work complements theirs by showing
that one family of “best-known” tests manages to work abstractly for codes developed by lifting.
We start by describing the lifting operation. Roughly speaking, a lifting of a base code leads to a
code in more variables whose codewords are words of the base code on every affine subspace of the base
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 300
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
dimension. We define this formally next. For f : FnQ → Fq and S ⊆ FnQ , let f |S denote the restriction of f
to the set S. A set A ⊆ FnQ is said to be a t-dimensional affine subspace, if there exist α0 , . . . , αt ∈ FnQ such
that ( )
t
A= α0 + ∑ αi xi x1 , . . . , xt ∈ FQ .
i=1
We use some arbitrary FQ -linear isomorphism from A to FtQ to view f |A as a function from {FtQ → Fq }.
Given an affine-invariant linear base code B ⊆ {FtQ → Fq } and integer n ≥ t, the n-dimensional lift of B,
denoted Liftn (B), is the set
f : FnQ → Fq f |A ∈ B for every t-dimensional affine subspace A ⊆ FnQ .
The lifting operation was introduced by Ben-Sasson et al. [5] as a way to build new affine-invariant
linear codes that were not locally testable. Their codes were also of much lower rate than known affine-
invariant linear codes of similar distance. However, in more recent work, Guo et al. [14], showed that
lifting could be used positively; they used it to build codes with very good locality properties (especially
decodability) with rate much better than known affine-invariant linear ones, and matching qualitatively the
performance of the best known codes. The present paper attempts to complement their work by showing
that these codes, over constant sized alphabets, can be “locally tested” as efficiently as polynomial codes.
Testing and absolutely sound testing. A code F ⊆ {FnQ → Fq } is said to be a (k, ε, δ )-locally testable
code (LTC), if δ (F) ≥ δ and there exists a probabilistic oracle algorithm that, on oracle access to
f : FnQ → Fq , makes at most k queries to f and accepts f ∈ F with probability one, while rejecting f 6∈ F
with probability at least εδF ( f ).
For an ensemble of codes {Fm ⊆ {FnQm → Fq }}m for infinitely many m, where the code Fm is a
(k(m), ε(m), δ (m))-LTC, we say that the code has an absolutely sound tester if there exists ε > 0 such
that ε(m) ≥ ε for every m.
Any tester can be converted into an absolutely sound one by repeating the test 1/ε(m) times. However,
this comes with an increase in the query complexity (the parameter k(m)) and so it makes sense to ask
what is the minimum k one can get for an absolutely sound test.
Previous work by Bhattacharyya et al. [8] and Haramaty et al. [15] raised this question in the context
of multivariate polynomial codes (Reed-Muller codes) and showed that the “natural tester” for multivariate
polynomial codes is absolutely sound, without any repetitions! The natural test here is derived as follows
for prime fields:
To test if a function f : Fnq → Fq is a polynomial of degree at most d, let t be the smallest
integer such that there exist functions of degree greater than d in t variables. Pick a random
t-dimensional affine subspace A and verify that f |A is a degree-d polynomial.
The natural test thus makes roughly qt = q(d+1)/(q−1) queries. This number turns out to be optimal for
prime fields in that every function looks like a degree-d polynomial if queried at at most qt−1 points.
Such optimal analyses of low-degree tests are used in computational complexity: In particular, one of the
many ingredients in the elegant constructions of Barak et al. [3] is the absolutely sound analysis of the
polynomial codes over F2 .
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 301
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
The natural test above is less natural and not quite optimal when dealing with non-prime fields.
Namely, one needs to use a larger value of t than the one in the definition above (specifically, t =
(d + 1)/(q − q/p) where p is the characteristic of the field Fq ). While it is unclear if sampling all the
points in the larger dimensional space is really necessary for absolutely sound testing, the results so far
seem to suggest working with prime fields is a better option.
1.1 Our work: Motivation and results
The motivation for our work is twofold. Our first motivation is to understand “low-degree testing” better.
Low-degree testing has played a fundamental role in computational complexity and yet its proofs are
barely understood. They tend to involve a mix of probabilistic, algebraic, and geometric arguments, and
the only setting where the mix of these features seems applicable is the setting of low-degree polynomials.
Affine-invariant codes naturally separate the geometry of subspaces in high-dimensional spaces from the
algebra of polynomials of low degree. Thus extending a proof or analysis method from the setting of
low-degree polynomials to the setting of generic geometric arguments has the nice feature that it has the
potential to separate the geometric arguments from the algebraic ones.
Within the theme of low-degree testing, the previous works have revealed interesting analyses. And
several of these variations in the resulting theorems have played a role in the construction of efficient
PCPs or more recently in other searches for explicit objects. In particular, the literature includes tests
such as those originally given by Blum, Luby and Rubinfeld [9] for testing linearity and followed
by [23, 1, 17, 16] for testing higher-degree polynomials. The aspects of this family of tests are well
abstracted in Kaufman and Sudan [18]. But the literature contains other very interesting theorems,
such as those of Raz and Safra [21] and Arora and Sudan [2] which tend to work in the “list-decoding”
regime. The analysis of the former in particular seems especially amenable to a “generic proof” in the
affine-invariant setting and yet such a proof is not yet available. Our work explores a third such paradigm
in the analysis of low-degree tests, which was introduced in the above-mentioned “absolutely-sound
testers” of Bhattacharyya et al. and Haramaty et al.
Our work starts by noticing that the natural tests above are really “lifting tests.” Namely, the test
could be applied to any code that is defined as the lift of a base code with the test checking if a given
function is a codeword of the base code when restricted to a random small-dimensional affine subspace
of the base dimension. Indeed this is the natural way of interpreting almost all the previous results in
low-degree testing (with the exception of that of [22]). If so, it is natural to ask if the analysis can be
carried out to show the absolute soundness of such tests.
The second, more concrete, motivation for our work is the work of Guo et al. [14]. Over prime fields,
it was well-known that lifts of low-degree polynomials lead only to polynomials of the same degree (in
more variables). Guo et al. show that lifting over non-prime fields leads to better codes than over prime
fields! (Prior to their work, it seemed that working with non-prime fields was worse than working with
prime fields.) The improved rate gives motivation to study lifted codes in general, and in particular, one
class of results that would have been nice to extend was the absolutely sound tester of [15].
In this work we show that the natural test of lifted codes is indeed absolutely sound. The following
theorem spells this statement out precisely.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 302
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Theorem 1.1 (Main). For every prime power q and Q a power of q, there exists εQ > 0 such that the
following holds: Let t ≤ n be positive integers and let B ( {FtQ → Fq } be any affine-invariant linear
code. Then F = Liftn (B) is (Qt , εQ , Q−t )-locally testable.
We also note that the literature on property testing includes other general theorems which would
imply the testability of the families covered in Theorem 1.1 above. For instance the authors of [7] use
only the affine invariance of the families (and do not need the fact that F is a Fq -vector space). However,
such testability results are quantitatively much weaker than those of [19] and do not satisfy our (somewhat
strong) definition of (k, ε, δ )-testability for any positive ε.
We stress that the importance of the above is in the absolute soundness, i. e., the fact that εQ does not
depend on t or B. If one is willing to let εQ depend on t and B then such a result follows from the main
theorem of [18].
Our result also sets into proper light the previous work of Haramaty et al. [15] who show that the
“natural test” for degree-d polynomials over the field Fq of characteristic p makes q(d+1)/(q−q/p) queries
and is absolutely sound. Our result does not mention any dependence on p, the characteristic of the field.
It turns out that such a dependence comes due to the following proposition.
Let RM(n, d, q) denote the set of polynomials of degree at most d in n variables mapping Fnq to Fq .
Proposition 1.2. For positive integers d and q where q is a power of a prime p, let
d +1
t = td,q = .
q − q/p
Then for every n ≥ t, the Reed-Muller code RM(n, d, q) equals the code Liftn (RM(t, d, q)).
Applying Theorem 1.1 to RM(n, d, q) we immediately obtain the main results of [8] and [15]. And
the somewhat cumbersome dependence on the characteristic of q can be blamed on the proposition above,
rather than any weakness of the testing analysis. Furthermore, as is exploited by Guo et al. [14] if one
interprets the proposition above correctly, then one should use lifts of Reed-Muller codes over non-prime
fields with dimension being smaller than td,q . These will yield codes of higher rate while our main
theorem guarantees that testability does not suffer.
One concrete consequence of our result is in the use of Reed-Muller codes in the work of Barak et
al. [3]. They show how to construct small-set expander graphs with many large eigenvalues and one of
the ingredients in their result is a tester of Reed-Muller codes over the domain Fn2 (codes obtained by
lifting an appropriate family of base codes over domain Ft2 ). Until this work, the binary Reed-Muller
code seemed to be the only code with performance good enough to derive their result. Our work shows
that using codes over the domain Fn4 or Fn8 (or any constant power of 2) would serve their purpose at least
as well, and even give slight (though really negligible) improvements. We elaborate on these codes and
their exact parameters in Section 7. (In particular, see Theorem 7.3.)
Finally, unlike the works of Bhattacharyya et al., and Haramaty et al., we cannot claim that our testers
are “optimal.” This is not because of a weakness in our analysis, rather it is due to the generality of our
theorem. For some codes, including the codes considered in the previous works, our theorem is obviously
optimal (being the same test and more or less the same analysis as previously). Other codes, however,
may possess special properties making them testable much better. In such cases we cannot rule out better
tests, though we hope our techniques will still be of some use in analyzing tests for such codes.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 303
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
Future research directions. As noted earlier, the field of low-degree testing has seen several different
themes in the analyses. Combined with the work of Kaufman and Sudan [19] our work points to the
possibility that much of that study can be explained in terms of the geometry of affine-invariance, and
the role of algebra can be encapsulated away nicely. One family of low-degree tests that would be very
nice to include in this general view would be that of Raz and Safra [21]. Their work presents a very
general proof technique that uses really little algebra; and seems ideally amenable to extending to the
affine-invariant setting. We hope that future work will address this.
We also hope that future work improve the dependence of εQ on Q in Theorem 1.1 (which is
unfortunately outrageous). Indeed it is not clear why there should be any dependence at all and it would
be nice to eliminate it if possible.
Organization. We give an overview of the proof of Theorem 1.1 in Section 2, where we also introduce
the main technical theorem of this paper (Theorem 2.1). We also describe our technical contributions in
this section, contrasting the current proof with those of [8, 15], which we modify. The remaining sections
are devoted to the formal proof of Theorem 1.1. Specifically we introduce some of the background
material in Section 3. We then prove Theorem 2.1 in Section 4. In Section 5 we show how to prove
Theorem 1.1 for the special case in which Q = q using Theorem 2.1. In Section 6 we then prove
Theorem 1.1 for general Q via a simple reduction to the case in which Q = q. Finally, in Section 7 we
give an example of a family of lifted codes to which our main theorem applies.
2 Overview of proof
From now on we shall deal only with the special case in which Q = q. In Section 6 we show a simple
reduction from the general Q 6= q case to the case in which Q = q.
2.1 Some natural tests
Our proof of Theorem 1.1 follows the paradigm used in [8] and [15]. Both works consider a natural
family of tests (and not just the “most” natural test), and analyze their performance by studying the
behavior of functions when restricted to “hyperplanes.” We introduce the family of tests first.
From now onwards all codes we consider will be linear and affine-invariant unless we explicitly say
otherwise. Given a base code B ⊆ {Ftq → Fq } and n ≥ ` ≥ t, we let L` = Lift` (B), with F = Ln . The
`-dimensional test for membership in F works as follows: Pick a random `-dimensional affine subspace
A in Fnq and accept f if and only if f |A ∈ L` .
Let Rej` ( f ) denote the probability with which the `-dimensional test rejects. Our main theorem
aims to show that Rej` ( f ) = Ω(δF ( f )) when ` = t. As in previous works, our analysis will first lower
bound Rej` ( f ) for ` = t + O(1) and then relate the performance of this test to the performance of the
t-dimensional test.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 304
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
2.2 Overview of proof of Main Theorem 1.1
The analysis of the performance of the `-dimensional tests is by induction on the number of variables n
and based on the behavior of functions when restricted to “hyperplanes.” A hyperplane in Fnq is an affine
subspace of dimension n − 1.
The inductive strategy to analyzing Rej` ( f ) is based on the observation that Rej` ( f ) = EH [Rej` ( f |H )]
where H is a uniform hyperplane. If we know that on most hyperplanes δLn−1 ( f |H ) is large, then we
can prove the right hand side above is large by induction. Thus the inductive strategy relies crucially on
showing that if f is far from F, then f |H cannot be too close to Ln−1 on too many hyperplanes. We state
this technical result in the contrapositive form below.
Theorem 2.1 (Main technical). For every q there exists τ such that the following holds: Let B ⊆ {Ftq →
Fq } be an affine-invariant linear code and for ` ≥ t let L` = Lift` (B). For n > t, let f : Fnq → Fq
be a function and let H1 , . . . , Hk be hyperplanes in Fnq such that δLn−1 ( f |Hi ) ≤ δ for every i ∈ [k] for
δ < (1/2)q−(t+1) . Then, if k ≥ qt+τ , we have δLn ( f ) ≤ 2δ + 4(q − 1)/k.
The theorem thus states that if f is sufficiently close to a lift of B on a sufficiently large number of
hyperplanes, yet a very small number (independent of n) of hyperplanes, then f is close to a lift of B. The
dependence of the number of hyperplanes on q and t is actually important to our (and previous) analysis.
The fact that it is some fixed multiple of qt , where the multiple depends only on q and not on t, is crucial
to the resulting performance.
Going from Theorem 2.1 above to Theorem 1.1 is relatively straightforward. In particular, using
Theorem 2.1 we can get a lower bound on Rejt+τ ( f ) without any changes to the proof of [15]. However,
going from such an analysis to a lower bound on Rejt ( f ) involves some extra work, with complications
similar to (but simpler than), those in the proof of Theorem 2.1 so we omit a discussion here. Section 5
contains all the details.
The main contribution of this paper is the proof of Theorem 2.1. Here, the previous proofs, both in [8]
and [15] crucially relied on properties of polynomials and in particular, the first step in both proofs, when
testing degree-d polynomials, is to consider the case of f being a degree-(d + 1) (or a degree-(d + q))
polynomial. In our case there is no obvious candidate for the notion of a degree-(d + 1) polynomial and
it is abstracting such properties that forms the bulk of our work. In what follows we give an overview of
some of the issues arising in such steps and how we deal with them.
2.3 Overview of proof of Theorem 2.1
To understand our proof of Theorem 2.1 we need to give some background, specifically to the proofs
from the previous work of [15]. Recall the analogous statement in [15] attempted to show that if f was
far from being a polynomial of degree d, then the number of hyperplanes where f turns out to be close to
being a degree-d polynomial is at most O(qt ) (where t ≈ d/q, the exact number will not be important to
us). In [15], the authors reasoned about this in a sequence of steps:
(1) They first showed that any function of degree greater than d, stays of degree greater than d on at
least 1/q fraction of all hyperplanes (provided n > t).
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 305
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
(2) Next they reasoned about functions of degree d + 1 and showed that such a function reduces its
degree on at most O(qt ) hyperplanes.
(3) In the third step they consider a general function f that is far from being of degree d and show that
the number of hyperplanes on which f becomes a degree-d polynomial exactly is O(qt ). (This is
the step where the big-Oh becomes a really big-Oh.)
(4) Finally, they show that for functions of the type considered in the previous step the number of
hyperplanes where they even get close to being of degree d is at most O(qt ), thus yielding the
analog of Theorem 2.1.
In implementing the program above (which is what we will end up doing) in our more general/abstract
setting, our first bottleneck is that, for instance in Step (2) above, we do not have a notion of degree d + 1
or some notion of functions that are “just outside our good set F.” Natural notions of things outside our
set do exist, but they do not necessarily satisfy our needs. To understand this issue better, let us see why
polynomials of degree d + O(1) appear in the analysis of a theorem such as Theorem 2.1. Consider a
simple case where H1 , . . . , Hq are parallel hyperplanes completely covering Fnq and δ = 0 so f is known
to be a good function (member of F, or degree-d) when restricted to these hyperplanes. So, in the setting
of testing polynomials of degree at most d, the hypothesis asserts that f restricted to these hyperplanes
is a polynomial of degree at most d. For notational simplicity we assume that Hi is the hyperplane
given by x1 = ηi where Fq = {η1 , . . . , ηq }. Then f |Hi = Pi (x2 , . . . , xn ) for some polynomial Pi of degree
d. By polynomial interpolation, it follows that f can be described as a degree-(d + q − 1) polynomial in
x1 , . . . , xn . The bulk of the analysis in [8, 15] now attempts to use the remaining K − q hyperplanes on
which f reduces to degree at most d, in conjunction with the fact that f is a polynomial of degree at most
d + q − 1 to argue that f is of degree at most d.
For us, the main challenge is that in the generic setting of the lift of some code B, we do not have a
ready notion of a degree-(d + q − 1) polynomial and so we have to define one. Thus the first step in this
work is to define such a code. The formal definition appears in Section 4.1: For our current discussion
it suffices to say that there is an affine-invariant linear code, which we denote F+ , which contains all
“interpolating functions” of elements of F (so F+ contains every function f for which there exist some q
parallel hyperplanes H1 , . . . , Hq such that f |Hi is a function in Ln−1 for all i). Of course such a set is not
useful if it does not have some nice structure. The key property of our definition of F+ is that it is the lift
of a non-trivial code on at most t + q − 1 dimensions. We prove this in Section 4.1. This definition of
F+ and its analysis rely centrally on some of the structural understanding of affine-invariant linear codes
derived in previous works [18, 12, 11, 6, 5, 4]. Lemma 4.5 allows us to say that F+ is almost as nice as
F, roughly analogous to the way the set of degree-(d + q − 1) polynomials is almost as nice as the set of
degree-d polynomials.
The notion of F+ turns out to be easy enough to use to be able to carry out the Steps (3) and (4) in the
program above by directly mimicking the proofs of [15], assuming Step (2) holds. (See Section 4.3.) But
Steps (1) and (2) turn out to be more tricky. So we turn to these, and in particular, Step (2) next.
Our next barrier in extending the proofs of [15] is the notion of “canonical monomials” which plays a
crucial role in Step (2) of [15]. For a function f of degree d + 1, the canonical monomial is a monomial
M of degree d + 1 supported on very few variables such that M is in the support of f ◦ T for some affine
transformation T . The fact that the number of variables in the support is small, while the monomial
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 306
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
remains a “forbidden one” turns out to be central to their analysis and allows them to convert questions of
the form: “Does f become a polynomial of smaller degree on the hyperplane H?”(which are typically not
well-understood) to questions of the form “Does g become the zero polynomial when restricted to H?”
(which is a very well-studied question).
In our case, we need to work with some function f in F+ which is not a function of F. The fact that
F+ is a lift of a “few-dimensional” code, in principle ought to help us find a monomial supported on few
variables that is not in F. But isolating the “right one” to work with for f turns out to be a subtle issue
and we work hard, and come up with a definition that is very specific to each function f ∈ F+ \ F. (In
contrast the canonical monomials of [15] were of similar structure for every function f .) Armed with this
definition and some careful analysis we are able to simulate Step (2) in the program above. Details may
be found in Section 4.2. Finally, Step (1) is also dealt with similarly, using some of the same style of
ideas as in the proof of Step (2). (See Lemma 5.3.)
3 Background and preliminary material
In this section we fix some notation and provide some background material on affine-invariant linear
codes, needed later on. We start with some basic notation.
Recall we are working with the field Fq where q = pr , for prime p and integer r. Throughout we
will consider q as a constant, and so asymptotic notations such as O(·), Ω(·) in this work may neglect
dependence on q. All linear-algebraic terminology as subspaces, dimension, span, etc. will be over the
field Fq .
We will let Zq denote the set {0, . . . , q − 1} and N denote the set of non-negative integers. For n > t,
we think of {Ftq → Fq } as a subset of {Fnq → Fq } by using the standard embedding E : {Ftq → Fq } →
{Fnq → Fq } given by (E( f ))(x1 , . . . , xn ) = f (x1 , . . . , xt ).
We let Affn ⊆ {Fnq → Fq } represent the set of all the affine functions. I. e.,
n
Affn = L : Fnq → Fq ∃α0 , . . . , αn ∈ Fq such that L(x) = ∑ αi xi + α0 ∀x = (x1 , . . . , xn ) ∈ Fnq .
i=1
For L ∈ Affn define HL ⊆ Fnq to be the hyperplane x ∈ Fnq | L(x) = 0 . We let Affn×n represent the set of
affine transformations from Fnq to Fnq . I. e.,
Affn×n := T : Fnq → Fnq ∃B ∈ Fn×n n n
q , c ∈ Fq such that T (x) = Bx + c ∀x ∈ Fq .
For a function f ∈ {Fnq → Fq } and T ∈ Affn×n , we denote by f ◦ T the composition of f and T . I. e.,
∀x ∈ Fnq : f ◦ T (x) = f T (x) .
We view monomials defined on variables x1 , . . . , xn as functions mapping Fnq to Fq , given by the
evaluations of the monomials. The set Mn ⊆ {Fnq → Fq } denotes the set of such monomial functions. For
M = ∏ni=1 xiai ∈ Mn where {ai }ni=1 ⊆ {0, . . . , q − 1}, degxi (M) = ai . As usual, deg(M) = ∑ni=1 degxi (M).
Note that for a ∈ N, the monomials M = xia and M 0 = xia mod q−1 are equivalent when q − 1 - a or a = 0,
while when q − 1 | a and a 6= 0 the monomials M = xia and M 0 = xiq−1 are equivalent. Motivated by this,
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 307
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
we define the operation a mod∗ k as follows
(
a mod k, if a = 0 or k - a,
a mod∗ k =
k, otherwise.
For every function f ∈ {Fnq → Fq } there is a unique representation as a polynomial
f = ∑ cMf M for some coefficients
f
cM M ∈ Mn ⊆ Fq .
M∈Mn
We define the support of such a function f to be
supp( f ) := M ∈ Mn cMf 6= 0 ,
and we let
deg( f ) = max deg(M) M ∈ supp( f ) .
3.1 The structure of affine-invariant linear codes
One main feature of affine-invariant linear codes is that they can be characterized by the set of monomials
in the support of the functions in these codes. Let F ⊆ {Fnq → Fq } be an affine-invariant linear code.
The support supp(F) of F is simply the union of the supports of the functions in F, i. e., supp(F) =
S
f ∈F supp( f ). The following lemma from [18] says that every affine-invariant linear code is uniquely
determined by its support.
Lemma 3.1 (Monomial extraction lemma, [18, Lemma 4.2]). Let F ⊆ Fnq → Fq be an affine-invariant
linear code. Then F has a monomial basis, that is, F = span(supp(F)).
For a monomial M ∈ Mn , let Affn×n (M) denote the set of all monomials that can be obtained from M
by applying an affine transformation T ∈ Affn×n on M, that is,
Affn×n (M) = M 0 ∈ Mn ∃T ∈ Affn×n such that M 0 ∈ supp(M ◦ T ) .
We will call Affn×n (M) the n-dimensional affine set of M. When the dimension n is clear from the
context we will omit the subscript n × n. Note that if M ∈ F, M 0 ∈ Affn×n (M) and F is an affine-invariant
linear code then M 0 ∈ F. The following lemma, also from [18], gives a sufficient condition under which a
monomial belongs to Affn×n (M).
Lemma 3.2 (Monomial spread lemma, [18, Lemma 4.6]). Let
n n
M 0 = ∏ xiai , M = ∏ xibi
i=1 i=1
be a pair of monomials in Mn , where ai , bi ∈ {0, . . . , q − 1} for all 1 ≤ i ≤ n. For 1 ≤ i ≤ n, let
(i) (i)
ai = ∑ a j p j , bi = ∑ b j p j
j j
(i) (i)
be the base-p representation of ai , bi , respectively. Assume that for all j, ∑ni=1 a j ≤ ∑ni=1 b j . Then
M 0 ∈ Affn×n (M).
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 308
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
We shall also use the following theorem from [13] which says that if a linear code is invariant under
invertible affine transformations then it is also invariant under general affine transformations.
Theorem 3.3 ( [13, Theorem A.1]). If F ⊆ Fnq → Fq is an Fq -linear code invariant under invertible
affine transformations, then F is invariant under all affine transformations.
3.2 Lifts of affine-invariant linear codes
The following claim relates the support of the base code to the support of its lift.
Claim 3.4. Let B ⊆ {Ftq → Fq } be an affine-invariant linear base code and let F = Liftn (B) be its
n-dimensional lift. Then the following hold:
1. supp(B) = supp(F) ∩ Mt .
2. supp(F) = M ∈ Mn Affn×n (M) ∩ Mt ⊆ supp(B) .
Proof. For the proof of the first part of the claim, suppose first that M ∈ supp(F) ∩ Mt and let A ⊆ Fnq
be the t-dimensional subspace containing all vectors supported on the first t coordinates. The fact that
M ∈ F = Liftn (B) implies that M|A ∈ B. Since M ∈ Mt we thus have that M ∈ supp(B).
On the other hand, suppose that M ∈ supp(B). Then in this case we clearly have that M ∈ Mt . To see
that M is also contained in supp(F) let A be an arbitrary t-dimensional affine subspace of Fnq . Then the
fact that B is an affine-invariant code and M ∈ B implies that M|A ∈ B. Since F = Liftn (B) this implies
in turn that M ∈ F, so we conclude that M ∈ Mt ∩ supp(F).
We proceed to the proof of the second part of the claim. Suppose first that M ∈ supp(F) and let
M 0 ∈ Affn×n (M) ∩ Mt . Then there exists an affine transformation T ∈ Affn×n such that
M 0 ∈ supp M ◦ T |xt+1 =0,...,xn =0 .
But if we let e1 , . . . , en denote the standard basis for Fnq and we let A denote the t-dimensional subspace
containing all vectors of the form T (0) + ∑ti=1 (T (ei ) − T (0))xi for xi ∈ Fq then
M ◦ T |xt+1 =0,...,xn =0 ∈ B
if and only if M|A ∈ B. Since F = Liftn (B) and M ∈ F we have that M|A ∈ B and so M 0 ∈ supp(B).
For the other direction, suppose that M ∈ Mn is such that Affn×n (M) ∩ Mt ⊆ supp(B), we will show
that M ∈ supp(F). For this we need to show that M|A ∈ B for every t-dimensional affine subspace A. Let
A be a t-dimensional affine subspace and let α0 , α1 , . . . , αt be such that
( )
t
A= α0 + ∑ αi xi xi ∈ Fq .
i=1
Let T ∈ Affn×n be the affine transformation defined as T (ei ) = αi + α0 for all 1 ≤ i ≤ t and T (ei ) = 0 for
all t < i ≤ n. Then
supp M ◦ T |xt+1 =0,...,xn =0 ⊆ Affn×n (M) ∩ Mt
and so we also have that supp(M|A ) ⊆ Affn×n (M) ∩ Mt . Our assumption that Affn×n (M) ∩ Mt ⊆ supp(B)
implies in turn that supp(M|A ) ⊆ supp(B) and so M|A ∈ B as required.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 309
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
The following proposition bounds the distance of lifts of general affine-invariant linear codes from
FtQ to Fq .
Proposition 3.5 ( [18, Theorem 5.1]). Let Q be a power of q, let B ⊆ {FtQ → Fq } be an affine-invariant
linear base code and let F = Liftn (B) be its n-dimensional lift. Then δ (B) ≥ δ (F) ≥ δ (B) − Q−t .
From the above proposition one can derive the following corollary.
Corollary 3.6. Let B ( {FtQ → Fq } be some non-trivial affine-invariant linear code and let F = Liftn (B)
be its n-dimensional lift. Then δ (F) ≥ Q−t .
Proof. From Proposition 3.5 it is enough to show that δ (B) ≥ 2Q−t . Assume toward a contradiction that
δ (B) < 2Q−t . From linearity of B there is a function f ∈ B such that there is only one point v ∈ FtQ such
that f (v) 6= 0. To reach a contradiction we show that any function g : FtQ → Fq can be written as a linear
combination of affine transformations of f . Because B is affine-invariant linear code it will follow that
B = {FtQ → Fq }. Indeed, we can express any g : FtQ → Fq as
g(u)
g(x) = ∑ f (x + v − u)
u∈Ft
f (v)
Q
and the result follows.
4 Proof of Main Technical Theorem 2.1
In this section we prove our Main Technical Theorem 2.1. Our goal then will be to show that if f is far
from F then on most hyperplanes it remains far from F. In particular, if F is the lift of a t-dimensional
code, then f should get close on at most qt+O(1) hyperplanes. We start by studying the special case where
f results from an “interpolation” of several functions in F.
4.1 The code F+
We start with the definition of the code F+ which contains all functions obtained from interpolations
of functions in F. The code F+ is defined below as the n-dimensional lift of a non-trivial code B+ on
t + q − 1 variables. We will then show that the code F+ contains all interpolations of functions in F.
Definition 4.1 (The code F+ ). Let B ⊆ {Ftq → Fq } be an affine-invariant linear base code with support
+
supp(B) = D. Let t + = t + (q − 1) and D+ ⊆ {Ftq → Fq } be the set
q−1
+ q−1
D = Afft + ×t + M ∏ xt+i M∈D .
i=1
Finally, let B+ = span(D+ ) and F+ = Liftn (B+ ).
We first show that F+ is non-trivial (i. e., F+ 6= {Fnq → Fq }), provided the base code B is non-trivial.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 310
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Claim 4.2. If B 6= {Ftq → Fq }, then F+ 6= {Fnq → Fq }.
Proof. Since B 6= {Ftq → Fq } and since, by Lemma 3.2, every monomial on t variables is in the affine
set of the monomial ∏ti=1 xiq−1 , it follows that ∏ti=1 xiq−1 6∈ D = supp(B). Hence we have that for every
monomial M 0 ∈ D, deg(M 0 ) < t(q − 1). From the definition of D+ it follows that every monomial M ∈ D+
+
must have degree strictly less than t + ·(q−1). It follows that B+ 6= {Ftq → Fq } and F+ 6= {Fnq → Fq }.
Next we show that F+ contains all functions resulting from interpolation of functions in F, as per the
following definition.
Definition 4.3 (Interpolation of functions in F). We say that f is an interpolation of functions in F if
there exist q parallel hyperplanes H1 , . . . , Hq (so Hi ∩ H j = 0/ for i 6= j and i Hi = Fnq ) and q functions
S
f1 , . . . , fq ∈ F such that f |Hi = fi |Hi for every i ∈ [q].
Claim 4.4. A function f ∈ {Fnq → Fq } is an interpolation of functions in F if and only if there exists an
affine function L ∈ Affn and functions { fa ∈ F | a ∈ {0, . . . , q − 1}} such that f = ∑a∈{0,...,q−1} fa La .
Proof. The proof is straightforward by polynomial interpolation.
Lemma 4.5. If f is an interpolation of functions in F = Liftn (B), then f ∈ F+ .
fa ∈+F. We need to show that for every t -dimensional
Proof. Fix f = ∑a fa La for affine function L and +
affine subspace A it is the case that supp f |A ⊆ D . Equivalently, we need to show that for every
T ∈ Affn×n , the restriction of supp f ◦ T to the subspace
x ∈ Fnq xt + +1 = · · · = xn = 0
is contained in D+ .
First observe that for every T ∈ Affn×n ,
f ◦T = ∑ L0a fa0
a∈{0,...,q−1}
where L0 is an affine function and fa0 ∈ F (so it is of the same form as f ). Note that every monomial in
supp( f ◦ T ) is of the form M ∏aj=1 xi j where a ∈ {0, . . . , q − 1}, i1 , . . . , ia ∈ [n] and M ∈ supp(F). Further,
restricting f ◦ T to the subspace
x ∈ Fnq xt + +1 = · · · = xn = 0
allows us to focus only on the cases i1 , . . . , ia ∈ [t + ] and M ∈ Mt + .
We will show in this case that M ∏aj=1 xi j ∈ D+ . Fix M ∈ Mt + ∩ supp(F), i1 , . . . , ia ∈ [t + ] and let
+
I ⊆ [t + ] be such that |I| = q − 1 and {i1 , . . . , ia } ⊆ I. Write M = ∏tk=1 xkak and choose M 0 ∈ Mt to be a
monomial of the form ∏tk=1 xkbk where {bk | k ∈ [t]} = {ak | k ∈ [t + ]\I}. Then by Lemma 3.2,
a t q−1 q−1
ak ak +#{ j|i j =k} bk q−1 0 q−1
M ∏ xi j = ∏ xk ∏ xk ∈ Afft + ×t + ∏ xk ∏ xt+i = Afft + ×t + M ∏ xt+i .
j=1 k∈I
/ k∈I k=1 i=1 i=1
Observe, again by Lemma 3.2, that M 0 ∈ Affn×n (M), so M 0 ∈ supp(F) ∩ Mt . By Claim 3.4, this
implies in turn that M 0 ∈ supp(B). Consequently, M ∏aj=1 xi j ∈ D+ , which concludes the proof of the
lemma.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 311
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
4.2 Restrictions of functions in F+ to hyperplanes
Let F = Liftn (B) for a non-trivial affine-invariant linear code B ⊆ {Ftq → Fq }. Let B+ be the code
given by Definition 4.1 and let F+ = Liftn (B+ ). Our goal in this section will be to show that for
+
every f ∈ F+ \ F, the number of hyperplanes H for which f |H ∈ F is upper bounded by O(qt ). (See
Theorem 4.9 below for formal statement.) We remark that throughout this section one could replace
F+ by any affine-invariant linear code that is the lift of a non-trivial affine-invariant linear base code
+
contained in {Ftq → Fq } and that the same holds for F (so F+ does not have to be as in Definition 4.1
and F could be a lift of a base code defined over t + variables and not only t variables).
The overall strategy is as follows.
(1) We will first show in Lemma 4.6 that for every such f there exists an invertible affine transformation
T and a monomial M ∈ / F supported on the first t + variables such that M is in the support of f ◦ T .
We further assume that T is such that the degree of M is maximal. Since we can just prove the
theorem about f ◦ T , we assume that M is in the support of f .
+
(2) Next we partition the space of all possible hyperplanes into qt +1 sets (based on their coefficients
on the first t + variables). Our goal will be to show that in each set in the partition there are at most
some constant (depending on q) number of hyperplanes such that f restricted to these hyperplanes
becomes a member of F. To do so we extract from f a non-zero low-degree function g (this
function g depends on M and the set in the partition under consideration), such that for a hyperplane
H from this set, f |H ∈ F only if g|H ≡ 0. (See Lemma 4.7.)
(3) The final task, to bound the number of hyperplanes on which a low-degree polynomial becomes
zero, turns out to be relatively easy and we give this bound in Lemma 4.8.
Below we state the three lemmas mentioned above. We defer their proofs to later in this section. We
show how they imply Theorem 4.9 immediately after stating them.
The first of our lemmas isolates a “canonical monomial” for every function f ∈ F+ \ F. We note that
this is similar to such a step in [15] with the main difference being that the canonical monomials here
can be quite different for different functions f (whereas in [15] all canonical monomials of functions
f ∈ F+ \ F were of a similar structure).
Lemma 4.6. For every f ∈ F+ \ F there exists an invertible affine transformation T and a monomial
M ∈ Mt + such that M 6∈ F and M is in the support of f ◦ T .
Our next lemma, which is the bulk of this section, reduces the task of counting hyperplanes where f
becomes a member of F, to the task of counting hyperplanes where a related function becomes zero.
Lemma 4.7. Let M ∈ Mt + be a monomial in the support of f ∈ F+ \ F with M 6∈ F. Suppose furthermore
that for every invertible affine transformation T all monomials M 0 ∈ (supp( f ◦ T ) ∩ Mt + ) \ F satisfy
that deg(M 0 ) ≤ deg(M). Then for every α0 , α1 , . . . , αt + ∈ Fq there exists a non-zero function g with
deg(g) ≤ q2 (q − 1) such that the following holds: For every choice of αt + +1 , . . . , αn ∈ Fq the hyperplane
( )
n
H= x ∈ Fnq ∑ αi xi + α0 = 0
i=1
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 312
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
satisfies f |H ∈ F only if g|H ≡ 0.
Finally, we bound the number of hyperplanes where a non-zero low-degree function can become zero.
d
Lemma 4.8. Let f : Fnq → Fq be a non-zero polynomial of degree d. Then there are at most q q−1 +1
hyperplanes H such that f |H ≡ 0.
Remark 4.1. We remark that any bound that is constant for constant d and q would have been good
enough to suffice for our purpose. We also note that the bound above is close to the right one. In particular,
if d = t(q − 1) and
t
f (x1 , . . . , xn ) = ∏(xiq−1 − 1)
i=1
then f is zero on every hyperplane of the form
t−1
xt = ∑ αi xi + β ,
i=1
with the αi being arbitrary and β being non-zero, and there are at least (q − 1) · qd/(q−1)−1 of these.
We now state and prove our main theorem of this section.
Theorem 4.9. Let B ( {Ftq → Fq } be an affine-invariant linear code and let F = Liftn (B). Let B+ be
+ 2
the code given by Definition 4.1, let F+ = Liftn (B+ ) and let f ∈ F+ \ F. Then there are at most qt +q +2
hyperplanes H such that f |H ∈ F.
Proof. Let T and M be the invertible affine transformation and the monomial given by Lemma 4.6
above, respectively. Suppose furthermore that T maximizes the degree of M, in the sense that for
every other invertible affine transformation T 0 all monomials M 0 ∈ (supp( f ◦ T 0 ) ∩ Mt + ) \ F satisfy that
deg(M 0 ) ≤ deg(M).
Applying Lemma 4.7 to the function f ◦ T and the monomial M, we get that for every α0 , α1 , . . . , αt +
there is a non-zero polynomial g of degree at most (q − 1)q2 such that g|H ≡ 0 whenever ( f ◦ T )|H ∈ F.
2
By Lemma 4.8 there are at most qq +1 such hyperplanes H. Summing over all possible choices of
+ 2
α0 , α1 , . . . , αt + , we get that there are at most qt +q +2 hyperplanes H such that ( f ◦ T )|H ∈ F. The
theorem follows from the fact that there is a one-to-one correspondence between the hyperplanes for
which the restriction of f ◦ T is in F and the hyperplanes for which the restriction of f is in F.
In the remaining subsections of this section we prove the three lemmas mentioned above.
4.2.1 Proof of Lemma 4.6
Lemma 4.6 (restated). For every f ∈ F+ \ F there exists an invertible affine transformation T and a
monomial M ∈ Mt + such that M 6∈ F and M is in the support of f ◦ T .
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 313
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
Proof. Let F f ⊆ {Fnq → Fq } be the minimal affine-invariant linear code containing f . Note that
( )
Ff = ∑ cT · ( f ◦ T ) cT ∈ Fq ,
T ∈T
where T denotes the set of all invertible affine transformations in Affn×n (the fact that one can sum only
over invertible transformations follows from Theorem 3.3).
+
Let B∗ ⊆ {Ftq → Fq } be the code
B∗ = g|xt + +1 =0,...,xn =0 g ∈ F f .
By definition B∗ is an affine-invariant linear code and f ∈ Liftn (B∗ ). Since
f 6∈ Liftn (B) = Liftn (Liftt + (B)) ,
it follows that B∗ 6⊆ Liftt + (B). So there must exist a monomial M ∈ B∗ \ Liftt + (B) (since B∗ is spanned
by the monomials in it, by Lemma 3.1). Clearly, we have that M ∈ Mt + . Furthermore, by Claim 3.4
supp(Liftt + (B)) = supp(F) ∩ Mt + and so M ∈ / F. Finally, note that the definition of B∗ implies that M
belongs also to F f . By the fact that
( )
Ff = ∑ cT · ( f ◦ T ) cT ∈ Fq
T ∈T
it follows that there exists an invertible affine transformation T such that M ∈ supp( f ◦ T ). The lemma
follows.
4.2.2 Proof of Lemma 4.7
Lemma 4.7 (restated). Let M ∈ Mt + be a monomial in the support of f ∈ F+ \ F with M 6∈ F. Suppose
furthermore that for every invertible affine transformation T all monomials M 0 ∈ (supp( f ◦ T ) ∩ Mt + ) \ F
satisfy that deg(M 0 ) ≤ deg(M). Then for every α0 , α1 , . . . , αt + ∈ Fq there exists a non-zero function g with
deg(g) ≤ q2 (q − 1) such that the following holds: For every choice of αt + +1 , . . . , αn ∈ Fq the hyperplane
( )
n
H= x ∈ Fnq ∑ αi xi + α0 = 0
i=1
satisfies f |H ∈ F only if g|H ≡ 0.
Proof. As a first step, we perform a change of basis that will allow us to assume, without loss of generality,
that α1 = −1 and α0 = α2 = · · · = αt + = 0 and so restriction of f to the hyperplane given by αt + +1 , . . . , αn
is given by the function !
n
f ∑ αi xi , x2 , . . . , xn .
i=t + +1
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 314
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
We will analyze such functions in later steps.
Fix α0 , α1 , . . . , αt + ∈ Fq and let H = Hα0 ,...,αt + be the set of hyperplanes H such that there exist
αt + +1 , . . . , αn so that ( )
n
H= x ∈ Fnq ∑ αi xi + α0 = 0 .
i=1
First we dismiss the case α1 = · · · = αt + = 0. In this case for every hyperplane H ∈ H, the function
f |H still has the monomial M in its support and so f |H 6∈ F. (So formally, g = 1 satisfies the condition of
the lemma.) So from here on we assume there exists c ∈ [t + ] such that αc 6= 0. Without loss of generality
we assume c is the minimal such index, and that αc = −1. For notational simplicity we assume below
that c = 1. Now consider the affine transformation S ∈ Affn×n such that
t+
S(e1 ) = e1 + ∑ αi ei + α0
i=2
and S(ei ) = ei for all i ≥ 2. Let f 0 = f ◦ S. For hyperplane
( )
n
H= x ∑ αi xi + α0 = 0 ,
i=1
let H 0 be the hyperplane ( )
n
0
H = x x1 = ∑ αi xi .
i=t + +1
Notice that f |H ∈ F if and only if f 0 |H 0 ∈ F and H 0 corresponds to α10 = −1 and αi0 = 0 for i ∈
{0, 2, 3, . . . ,t + }.
Now let M 0 ∈ supp( f 0 ) ∩ Mt + be a monomial such that M ∈ supp(M 0 ◦ T ) for some invertible T ∈
Afft + ×t + . Note such a monomial M 0 must exist since S is an invertible transformation in Afft + ×t + . Since
M ∈ supp(M 0 ◦ T ) and M 6∈ F it follows that M 0 6∈ F. Furthermore, the fact that M ∈ supp(M 0 ◦ T )
implies that deg(M) ≤ deg(M 0 ) and hence M 0 is also maximal with respect to degree. That is, for every
invertible affine transformation T 0 it holds that all monomials M 00 ∈ (supp( f 0 ◦ T 0 ) ∩ Mt + ) \ F satisfy that
deg(M 00 ) ≤ deg(M 0 ).
In what follows we prove that the lemma holds for the polynomial f 0 with monomial M 0 and
coefficients α00 , . . . , αt0+ , i. e., we prove the existence of a non-zero polynomial g0 of degree at most
q2 (q − 1) such that g0 |H 0 ≡ 0 whenever f 0 |H 0 ∈ F. The lemma follows for f by setting g = g0 ◦ S−1 . For
notational simplicity we drop the primes below and simply assume α1 = −1 and αi = 0 for all other
i ≤ t + and so f = f 0 , M = M 0 .
Let M̄ ∈ Fq [x2 , . . . , xt + ] and let a ≥ 0 be an integer such that M = x1a M̄. Write f = g1 M̄ + r1 where
g1 ∈ Fq [x1 , xt + +1 , . . . , xn ] is such that g1 M̄ contains all monomials in supp( f ) whose degrees in variables
x2 , . . . , xt + equal their degrees in M̄ and r1 is the remaining terms. Further write g1 = g + g2 where g in-
cludes all monomials M 0 of degree deg(M 0 ) mod∗ (q − 1) = a and g2 includes all monomials M 00 of degree
deg(M 00 ) mod∗ (q − 1) 6= a. Rewriting we have f = g · M̄ + r where r = g2 M̄ + r1 , g ∈ Fq [x1 , xt + +1 , . . . , xn ]
and r ∈ Fq [x1 , . . . , xn ]. We show below, using a series of claims that g satisfies the conditions of the
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 315
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
lemma. Specifically, fix αt + +1 , . . . , αn , let L(x) be the linear function L(x) = ∑ni=t + +1 αi xi , and let H be
the hyperplane given by {x1 = L(x)}. We wish to show that g|H ≡ 0 if f |H ∈ F.
Let F f be the minimal affine-invariant linear code containing f . Let
F−M̄ = h ∈ Fq [x1 , xt + +1 , . . . , xn ] M̄ · h ∈ F ,
and let
F f ,−M̄ = h ∈ Fq [x1 , xt + +1 , . . . , xn ] M̄ · h ∈ F f .
Below we state and prove four claims about g (Claims 4.10- 4.13) from which the lemma follows
immediately. Specifically, the first two prove that g is non-zero and of low-degree. And the final two
prove that g becomes zero on H if f |H ∈ F. Claim 4.11 uses Lemma 4.14 which we state and prove after
we prove the current lemma.
Claim 4.10. g 6= 0 and g ∈ F f ,−M̄ .
Proof. The fact that g is non-zero follows from the fact that M is in the support of f and M = x1a M̄ and
so x1a is in the support of g. Since supp(g · M̄) ⊆ supp( f ) we have that g · M̄ ∈ F f and so by definition of
F f ,−M̄ we have g ∈ F f ,−M̄ .
Claim 4.11. Every function in F f ,−M̄ has degree at most q2 (q − 1).
Proof. In Lemma 4.14 we prove that for any affine-invariant linear code G, if there exists a monomial N
of degree at most ` that is not in G, then every function in G has degree at most (1/2)q2 · `. So to prove the
current claim it suffices to show that there is a monomial of degree at most 2(q − 1) that is not contained
in F f ,−M̄ . We now show that the monomial N = x1a xtq−1
+ +1 6∈ F f ,−M̄ . Notice that N is a monomial of degree
at most a + (q − 1) ≤ 2(q − 1), and so with Lemma 4.14 this suffices to prove the claim.
Assume for contradiction that
x1a xtq−1
+ +1 ∈ F f ,−M̄ and so M · xtq−1 a q−1
+ +1 = x1 xt + +1 M̄ ∈ F f .
+ +
Since B+ 6= {Ftq → Fq } and M ∈ supp(F+ ) ∩ Mt + = supp(B+ ), we have M 6= ∏ti=1 xiq−1 . We conclude
there exists i ∈ [t + ] such that di , degxi (M) 6= q − 1. But if x1a xtq−1
+ +1 M̄ ∈ F f then by exchanging the
variables xi and xt + +1 we also have the monomial
Mxiq−1−di xtd+i +1 ∈ F f and so Mxiq−1−di ∈ F f .
We show below that this contradicts the maximality of M.
Note first that Mxiq−1−di is a monomial in Mt + . Furthermore, since
( )
Ff = ∑ cT · ( f ◦ T ) cT ∈ Fq
T ∈T
we have that Mxiq−1−di ∈ supp( f ◦ T ) for some invertible affine transformation T . Finally, by Lemma 3.2
we have that M ∈ Affn×n (Mxiq−1−di ) and so the fact that M ∈ / F implies that Mxiq−1−di ∈ / F. Concluding,
q−1−di
we have just shown that Mxi is a monomial in variables x1 , . . . , xt + contained in supp( f ◦ T ) \ F for
some invertible affine transformation T . Given that deg(Mxiq−1−di ) > deg(M), this clearly violates the
maximality of M.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 316
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Claim 4.12. If f |H ∈ F then g|H ∈ F−M̄ .
Proof. Recall that
H = x ∈ Fnq x1 = L(xt + +1 , . . . , xn ) .
Let
f 0 (x2 , . . . , xn ) = f (L(xt + +1 , . . . , xn ), x2 , . . . , xn )
denote the function f |H . As in the partitioning of f , let f 0 = g01 M̄ + r10 where g01 M̄ includes all monomials
of f 0 whose degrees in x2 , . . . , xt + equal their degrees in M̄. Further let g01 = g0 + g02 where g0 includes all
terms of degree d for d mod∗ (q − 1) = a and g02 collects the remaining terms.
The proof of the claim relies crucially on the following property of g0 , namely that
g0 (xt + +1 , . . . , xn ) = g(L(xt + +1 , . . . , xn ), xt + +1 , . . . , xn )
is the function g|H . To see this, note that when substituting x1 = L(xt + +1 , . . . , xn ) degrees in x2 , . . . , xt + do
not change and so we have g01 = g1 (L(x), xt + +1 , . . . , xn ). Next we note that for every monomial of degree
d, the reductions modulo xiq − xi (for every i) can only change the degree of the monomial to d 0 which
satisfies d 0 mod∗ (q − 1) = d and so g0 = g(L(x), xt + +1 , . . . , xn ).
The claim now follows easily. From the property of the previous paragraph our claim can be rephrased
as asserting that if f 0 ∈ F then g0 ∈ F−M̄ . But if f 0 = g0 M̄ + r0 ∈ F, then it follows that g0 M̄ (with its
support being a subset of the support of f 0 ) is also in F and so g0 ∈ F−M̄ .
Claim 4.13. If g|H ∈ F−M̄ then g|H ≡ 0.
Proof. Assume for contradiction that g|H ∈ F−M̄ and g|H 6≡ 0. Let
g0 (xt + +1 , . . . , xn ) = g|H (x) = g(L(x), xt + +1 , . . . , xn ) .
Every monomial of g is of degree d where d mod∗ (q − 1) = a, and hence the same holds also for g0 . For
β = (βt + +1 , . . . , βn ), let
pβ (x1 ) = g0 (βt + +1 , . . . , βn )x1a .
Since g|H 6≡ 0, there exists β = (βt + +1 , . . . , βn ) such that g0 (βt + +1 , . . . , βn ) 6= 0 and so pβ (x1 ) has x1a in its
support. Note furthermore that pβ (x1 ) is obtained by an affine (although non-invertible) transformation
of the coordinates of g0 which is given by T (ei ) = βi e1 for all i ∈ {et + +1 , . . . , en }. Thus the fact that
g0 ∈ F−M̄ implies in turn that x1a ∈ F−M̄ . But, by the definition of F−M̄ this implies M = x1a M̄ ∈ F which
contradicts the hypothesis of the lemma.
This concludes the proof of Lemma 4.7.
We now state and prove a lemma which bounds the maximal degree of functions in any affine-invariant
linear code given a single monomial not in the code, which was used in the proof above.
Lemma 4.14. Let G ⊆ {Fnq → Fq } be an affine-invariant linear code and let M be a monomial of degree
` such that M 6∈ G. Then, for every function f ∈ G, we have deg( f ) ≤ (1/2)q2 `.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 317
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
Proof. We first note that we can assume, without loss of generality, that `q ≤ n. Else (if n < `q) we can
prove the result for the code G0 = Lift`q (G), and then use the identity G = G0 ∩ {Fnq → Fq } to derive the
result for G. So from now we have n ≥ `q.
Let p be a prime number and t be an integer such that q = pt . Let M 0 = ∏ni=1 xiai be a monomial in
f ∈ G, write any degree ai in base p as
t−1
(i)
ai = ∑ a j p j ,
j=0
(i)
where a j ∈ {0, . . . , p − 1} for all 0 ≤ j ≤ t − 1 and i ∈ [n].
We will show that
n
(i)
∑ a j < `pt− j
i=1
for every 0 ≤ j ≤ t − 1. This will show that
n n t−1 t−1
(i) 1
deg(M 0 ) = ∑ ai = ∑ ∑ a j p j < ∑ `pt− j p j = tq` ≤ q2 ` ,
i=1 i=1 j=0 j=0 2
thereby yielding the lemma.
Assume for contradiction that there is some j, such that
n
(i)
∑ a j ≥ `pt− j .
i=1
Then, by Lemma 3.2 the monomial
`pt− j j
M1 = ∏ xip
i=1
is in G. By applying the linear transformation T1 given by T1 (ei ) = ei mod ` for every i in the monomial M1 ,
we deduce that ∏`i=1 xiq ∈ G. In turn the resulting monomial is equivalent to the monomial M2 = ∏`i=1 xi
over Fq . Let `i denote the degree of xi in M so that ∑i `i = `. Now consider the transformation T2 defined
by ∀i ∈ [n], ∀k such that
i−1 i
∑ ` j < k ≤ ∑ ` j : T2 (ek ) = ei .
j=1 j=1
We have M2 ◦ T2 = M, yielding M ∈ G which contradicts our assumption. The lemma follows.
4.2.3 Proof of Lemma 4.8
We conclude the section by proving Lemma 4.8 which we restate below for convenience.
Lemma 4.8 (restated). Let f : Fnq → Fq be a non-zero polynomial of degree d. Then there are at most
d
q q−1 +1 hyperplanes H such that f |H ≡ 0.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 318
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Proof. Let H1 , . . . , Hk be all the hyperplanes that satisfy f |Hi ≡ 0. Consider the set
S , x ∈ Fnq | ∀i ∈ k, x ∈
/ Hi .
We will find an upper and lower bound on the density of the set S as a function of k and this will yield the
claimed bound on k.
Consider a point x ∈ Fnq , chosen uniformly at random. We first give an upper bound on the probability
that x ∈ S. Let Zi be a random variable such that Zi = 1 if and only if x ∈ Hi . Note that we wish to upper
bound the probability that ∑ki=1 Zi = 0. We bound this probability using the Chebychev bound.
Clearly, for all i ∈ [k],
|Hi | 1
E Zi2 = E Zi = n = .
Fq q
Moreover, for i 6= j, E Zi Z j ≤ 1/q2 . (E[Zi Z j ] = 1/q2 if Hi and H j are not parallel, and equals zero if
they are.) Calculating the variance,
k k 2 k 2 2
k 2 k
Var ∑ Zi = E ∑ Zi − E ∑ Zi = 2 ∑ E Zi Z j + ∑ E Zi −
i=1 i=1 i=1 i< j i=1 q
k(k − 1) k k2 k(q − 1)
≤ 2
+ − 2= .
q q q q2
We bound the density of S by Chebyshev’s inequality,
Var ∑ki=1 Zi ) q − 1
k k
k k
Pr[x ∈ S] = Pr ∑ Zi = 0 ≤ Pr ∑ Zi − ≥ ≤ ≤ .
q q k 2 k
i=1 i=1 q
On the other hand, by the well-known polynomial-distance lemma (see, for instance, [15, Lemma
3.2])
d
Pr x ∈ S ≥ Pr f (x) 6= 0 ≥ q− q−1 .
d
Combining the above, we have q− q−1 ≤ (q − 1)/k which yields
d d
k ≤ q q−1 (q − 1) < q q−1 +1 ,
as claimed.
4.3 Restrictions of general functions to hyperplanes
We finally turn to the proof of the Main Technical Theorem 2.1. The proof of this section is a straightfor-
ward adaptation of the proof of the corresponding theorem in [15], given Theorem 4.9. We give a brief
overview of the proof first.
Recall that Theorem 2.1 says that if a function f ∈ {Fnq → Fq } is δ -close to functions from F on k
hyperplanes (for sufficiently large k), then f is itself close to some function from F. It turns out that the
central difficulty in proving this theorem already arises when δ = 0, and the theorem for general δ follows
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 319
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
immediately. Theorem 4.15 states this special case, which we prove first. The proof of Theorem 2.1
follows easily and we prove it later in Section 4.3.4.
The proof of Theorem 4.15 is itself by induction on n, however, now the hardest part is the base case.
We prove the base case separately as Lemma 4.18 in Section 4.3.2. We then prove Theorem 4.15 as a
consequence in Section 4.3.3.
4.3.1 Interpolation from exact agreement
We start by stating Theorem 4.15 which implies the special case of Theorem 2.1 for the case of δ = 0.
Theorem 4.15. For every q there exists τ such that the following holds: Let n > t, let B ( {Ftq → Fq }
be an affine-invariant linear code and let F = Liftn (B). Let f : Fnq → Fq be a function and H1 , . . . , Hk
be hyperplanes in Fnq such that f |Hi ∈ F for every i ∈ [k]. Then, if k ≥ qt+τ , there exists a function h ∈ F
such that f |Hi = h|Hi for all i ∈ [k].
We will prove Theorem 4.15 in Section 4.3.3 by induction on n. Our proof will rely on a slightly
stronger (smaller) bound on k as n gets smaller. This makes the base case of small values of n more
challenging and we deal with this first.
4.3.2 The base case
Here we consider the case where n = t + O(1). In this case the number of hyperplanes k ≥ qt+τ is a
“constant” fraction of all the hyperplanes. We view these hyperplanes as points in a (n + 1)-dimensional
subspace (the hyperplane given by ∑ni=1 αi xi = α0 is associated with the point (α0 , . . . , αn ) ∈ Fn+1
q ), and
then use the well-known Hales–Jewett Theorem from additive combinatorics to infer that there are q
points in a straight line among this set of points. (Indeed by choosing our density to be slightly larger we
may conclude that there are many straight lines among the given set of points. We use such a version
that was already used in [15].) In terms of hyperplanes these lines lead to a small set that cover most of
Fnq . We use this set to derive that there is a function h from F+ that is consistent with f on all the given
hyperplanes. We then use Theorem 4.9 to conclude that h must actually be an element of F.
We start by stating the version of the Hales-Jewett theorem we will use after a basic definition.
Definition 4.16. Let v ∈ Fnq and u ∈ Fnq \{0}. A line through v in direction u is the set v + αu α ∈ Fq .
Notice that the direction of a given line is unique up to multiplication by an element of Fq \{0}.
The following theorem is a corollary of the Hales–Jewett theorem [10, 20].
Theorem 4.17 ([15, Corollary 3.5]). For every prime power q and every c > 0 there exists an integer
λq,c such that for every integer m ∈ N the following holds: if n ≥ λq,c + m then every set A ⊆ Fnq of size
|A| ≥ qn−c contains m lines whose directions are linearly independent.
The following lemma now states Theorem 4.15 for the special (base) case of n ≤ t + O(1).
Lemma 4.18. For every q, and constant c, there exists a constant τc such that the following holds:
Let n,t ∈ N be such that t < n ≤ t + τc . Let B ( {Ftq → Fq } be an affine-invariant linear code and let
F = Liftn (B). Let f : Fnq → Fq be a function and H1 , . . . , Hk be hyperplanes in Fnq such that f |Hi ∈ F for
every i ∈ [k]. Then, if k ≥ qt+τc −c , there exists a function h ∈ F such that f |Hi = h|Hi for all i ∈ [k].
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 320
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Proof. We prove the lemma for τc = λ + q + c where λ = max{λq,c+1 + 1, q2 + 4} and λq,c+1 is as given
by Theorem 4.17.
Overview: We start by giving an overview of the proof. Using a natural correspondence between hyper-
planes in Fnq and points in Fn+1
q (the hyperplane ∑ni=1 αi xi = α0 corresponds to the point (α0 , . . . , αn ) ∈
Fn+1
q ) and the Hales–Jewett theorem in Fq
n+1 we find many hyperplanes of a “somewhat structured” type.
We will formally describe these later below, but an example of hyperplanes corresponding to points on
a line would be the set of hyperplanes x1 + λ x2 = 0 for every λ ∈ Fq . This set of hyperplanes almost
covers the entire region Fnq , except the points with x1 6= 0 and x2 = 0.
We then proceed in three steps: We first observe that for every hyperplane of the form x2 = η for
η 6= 0, f restricted to this hyperplane is an element of F+ . Observing further that f |x2 =η is a function
of F when restricted to many hyperplanes in Fn−1 q , we use Theorem 4.9 to claim that f |x2 =η ∈ F. Now
if we only could claim that f |x2 =0 is also an element of F we would be done by a similar sequence of
observations. However, this is not necessarily true. To deal with this, we show in the first step, using the
fact that there are many hyperplanes, that for many variables xi we have f |xi =η ∈ F for every η 6= 0.
In the second step we apply some algebraic interpolations to show for every i ∈ [m] the existence of a
function hi : Fnq → Fq such that hi ∈ F+ and hi |xi =η = f |xi =η for every η 6= 0.
In the third and last step we show how to build a single function h ∈ F+ that agrees with f |xi =η for
every choice of i and for every η 6= 0, and then show that this function is in F and agrees with f on every
given hyperplane. We note that this step requires some non-trivial extensions of corresponding steps
in [15] as well. We now turn to the formal proof.
The formal proof: We start by showing that some very structured set of hyperplanes are included
among the given k hyperplanes. For a point α = (α0 , . . . , αn ) ∈ Fn+1
q let Hα denote the hyperplane
( )
n
Hα = x ∈ Fnq ∑ αi xi = α0 .
i=1
For an affine transformation T , let Hα ◦ T denote the hyperplane HT (α) .
Claim 4.19. Let m = t + q + 1. There exists an invertible affine transformation T and m invertible affine
functions L1 , . . . , Lm : Fnq → Fnq such that for every i ∈ [m] and γ ∈ Fq the hyperplane
Hi,γ , {x | Li (x) + γxi = 0}
is included in the set {H1 ◦ T, . . . , Hk ◦ T }.
Proof. Let P = {α (1) , . . . , α (k) } ⊆ Fn+1
q be a set of k points such that Hi = Hα (i) for every i ∈ [k]. We
(i) (i)
assume without loss of generality that α0 ∈ {0, 1} for all i ∈ [k] since the other α j can be scaled to
achieve this. Note furthermore that if n < logq k then there is nothing to prove since in this case one
cannot find k distinct hyperplanes inside Fnq . Hence we may assume that n ≥ logq k ≥ t + τc − c. Since
the density of P in Fn+1
q is k/qn+1 ≥ q−(c+1) and n ≥ t + τc − c ≥ t + λq,c+1 + 1 + q, by Theorem 4.17 we
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 321
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
have that there are at least m = t + q + 1 linearly independent lines in P. Since all points in P have their
0th coordinate in {0, 1} these lines must be constant in the 0th direction.
By applying an invertible linear transformation to the last n coordinates, we can assume without loss
of generality that the lines are parallel to the axes in directions x1 , . . . , xm . Let T be such a transformation
and let T (P) = {T (α)|α ∈ P}. Then we get that there are vectors β (1) , . . . , β (m) ∈ Fn+1 q such that for
(i) (i) (i)
every i ∈ [m] and every γ ∈ Fq , the vector β (i) + γ~e(i) ∈ T (P), where ~e(i) = (e0 , . . . , en ) has ei = 1 and
is 0 on every other coordinate. For i ∈ [m], let
n
(i) (i)
Li (x) = ∑ β j x j − β0 .
j=1
The claim follows for this choice of T and the Li .
In what follows, we assume that the affine transformation T above is the identity transform (or else
we can simply prove Lemma 4.18 for the function f ◦ T ).
First step
Claim 4.20. For every i ∈ [m], η ∈ F∗q , we have f |xi =η ∈ F (i. e., f is an element of F when restricted to
the hyperplane given by fixing xi to η).
Proof. In order to prove the claim we first prove that f |xi =η is in F+ and then use Theorem 4.9 to deduce
that f |xi =η is actually in F.
Fix x ∈ Fnq such that xi = η and let β = Li (x). By definition x ∈ HLi −η −1 β xi (note that here we use the
fact that η 6= 0). We thus conclude that
[
Hxi −η = Hxi −η ∩ HLi −γxi .
γ∈Fq
In other words the hyperplane Hxi −η is covered by q parallel hyperplanes in Fn−1
q . Thus, since for every
γ ∈ Fq we have f |HLi −γxi ∈ F, we get
f |Hxi −η ∩ HLi −γxi ∈ F
as well. We thus conclude, by Lemma 4.5, that f |xi −η ∈ F+ .
Now, consider the set
S = Hxi −η ∩ H j | j ∈ [k] .
Allowing for q of the H j to be parallel to Hxi −η and for q different subspaces H j to become identical when
2
restricted to Hxi −η , we still get (k/q) − 1 > qt+q +q+2 many distinct (n − 2)-dimensional affine subspaces
of Hxi −η in S. For each such subspace H j , we have
f |Hxi −η ∩H j = f |H j |Hxi −η ∈ F .
q ), we get f |xi =η ∈ F.
Therefore, by Theorem 4.9 (applied to functions over Fn−1
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 322
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Second step
Claim 4.21. For every i ∈ [m] there exists a function hi : Fnq → Fq with hi ∈ F+ and hi |xi =η = f |xi =η for
every η ∈ F∗q .
Proof. Let hi be defined as hi (x) = f (x) when xi 6= 0 and hi (x) = 0 otherwise. Clearly we have that
hi |xi =η = f |xi =η for every η ∈ F∗q , it remains to show that hi ∈ F+ . To see this note that Claim 4.20 above
implies that for every η 6= 0, hi |xi =η = f |xi =η ∈ F. Since F is linear we also have that the zero function
is contained in F and hence hi |xi =0 is also contained in F. Thus we have that hi is an interpolation of
functions in F as per Definition 4.3. Lemma 4.5 then implies that hi ∈ F+ .
Third step Our final step, which is the major step of this proof, is to collect the hi together consistently
to form the function h. Lemma 4.22 below proves that there is a function h ∈ F+ such that h agrees with
f on all the hyperplanes Hxi −η for η 6= 0 and i ∈ [m]. We now conclude the proof by going back to the k
hyperplanes H1 , . . . , Hk given by the hypothesis.
For every j ∈ [k], we first claim that h|H j = f |H j . To see this, let
!
m [
[
Sj = Hj ∩ Hxi −η .
i=1 η6=0
On the one hand f and h agree on every point in S j . On the other hand, we have |S j | ≥ qn−1 (1 − q−(m−1) ).
Finally, we also have that h|H j , f |H j ∈ F ⊆ F+ . Since δ (F+ ) ≥ q−(t+q−1) > q−(m−1) (since m > t + q) we
2
get f |H j = h|H j . We now have that h ∈ F+ is a function that on k > qt+q +q+2 hyperplanes h restricted to
the hyperplane is a function in F. By Theorem 4.9, we have h ∈ F as desired.
Lemma 4.22. Let G be an affine-invariant linear code and let h1 , . . . , hm , f : Fnq → Fq be functions such
that for every η 6= 0 and i ∈ [m], we have hi |xi =η = f |xi =η , and hi ∈ G for every i ∈ [m]. Then there exists
h ∈ G such that h|xi =η = f |xi =η for every i ∈ [m] and η 6= 0.
For the proof of the above lemma we shall need the following definition of non-standard monomials.
Definition 4.23 (Non-standard monomials). For integer j ∈ {0, . . . , q − 1} we define the “non-standard”
monomial N j (t) to be t j if j 6= q − 1 and t j − 1 if j = q − 1. For a vector a ∈ {0, . . . , q − 1}n we define
the non-standard monomial Na (x) to be ∏ni=1 Nai (xi ).
It is simple to see that non-standard monomials do form a basis for all functions from Fnq → Fq . We
mention this and some other properties we will be using below.
Proposition 4.24.
1. For every function f : Fnq → Fq there exists a unique set of coefficients denoted {ca }a∈{0,...,q−1}n
such that f (x) = ∑a ca Na (x).
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 323
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
2. For I ⊆ [n], let
AI = {a ∈ {0, . . . , q − 1}n | ai 6= q − 1 ∀i ∈ I} SI = x ∈ Fnq xi 6= 0 ∀i ∈ I .
and let
Then for every function f (x) = ∑a ca Na (x) the coefficients {ca }a∈AI are uniquely determined by
f |SI .
3. Let G be an affine-invariant linear code and suppose f = ∑a ca Na (x) is in G. Then for every a such
that ca 6= 0, it holds that Na (x) ∈ G.
Proof. The first part of the proposition is immediate and the second part is given as Lemma 4.13 in [15]
so it remains to prove the third part. For a vector a ∈ {0, . . . , q − 1}n denote by xa the (standard) monomial
a 0
∏ni=1 xi i . Let a be such that ca 6= 0 and let xa be a monomial of maximal degree such that ca0 6= 0 and
0 0
xa ∈ supp(Na0 (x)). Since xa is of maximal degree we must have that xa ∈ supp( f ) which by Lemma 3.1
0
implies that xa ∈ G.
Note that all monomials in supp(Na0 (x)) are of the form xb where bi = a0i if a0i 6= q − 1 and bi ∈ {0, q −
1} if a0i = q − 1. Since xa ∈ supp(Na0 (x)), in particular, we have that every monomial in supp(Na (x)) is of
0 0
this form. By Lemma 3.2 this implies in turn that supp(Na (x)) ⊆ Affn×n (xa ). Since xa ∈ G we conclude
that supp(Na (x)) ⊆ G so Na (x) ∈ G as required.
(i)
Proof of Lemma 4.22. We now use the non-standard monomials. For i ∈ [m], let {ca }a∈{0,...,q−1}n be
(i)
such that hi (x) = ∑a ca Na (x). Let
D = {a ∈ {0, . . . , q − 1}n | ∃i ∈ [m] s.t. ai 6= q − 1} .
For a ∈ D, let i(a) = min{i | ai 6= q − 1}. We define
(i(a))
h(x) = ∑ ca Na (x) .
a∈D
We argue below that h is a member of G and h agrees with f on the hyperplanes Hxi −η for every i ∈ [m]
and η 6= 0.
The first part is simple. We first notice that every term in the non-standard expansion of h = ∑a ca Na (x)
i(a)
is in G. Suppose Na (x) has a non-zero coefficient in the expansion of h. Then we have that ca = ca
and so Na (x) has a non-zero coefficient in the non-standard expansion of hi(a) . Since hi(a) ∈ G, it follows,
from Part (3) of Proposition 4.24, that Na (x) ∈ G. Thus, every term of h is in G and by linearity of G it
follows that h ∈ G.
It remains to argue that h equals f on every hyperplane of the form xi = η for i ∈ [m] and η 6= 0. To
(i) ( j)
see this we first claim that for i 6= j ∈ [m] and a ∈ {0, . . . , q − 1}n if ai , a j 6= q − 1 then ca = ca . To see
this, note that
hi |xi 6=0,x j 6=0 = f |xi 6=0,x j 6=0 = h j |xi 6=0,x j 6=0 .
(i) ( j)
But now, applying Part (2) of Proposition 4.24 to the set I = {i, j}, we get that ca = ca as claimed.
(i)
Thus, as a consequence, we have that ca = ca for every a such that ai 6= q − 1. Applying Part (2) of
Proposition 4.24 again, this time to the set I = {i}, we have that h and hi must agree in every x such that
xi 6= 0. The lemma follows.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 324
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
4.3.3 Proof of Theorem 4.15
We are now ready to prove Theorem 4.15.
Proof of Theorem 4.15. We will prove the theorem for τ = max{τ4 − 3, q2 + q + 1} where τ4 is the
constant given by Lemma 4.18 for c = 4.
Recall that we wish to prove that if f agrees with a function from F on k hyperplanes (where the
agreeing function may be different for each hyperplane), then there is a single function in F with whom f
agrees on all the given hyperplanes. We wish to prove this when k ≥ qt+τ , but we will prove a slightly
stronger result for the induction.
Inductive Hypothesis: Let n0 := n − t − τ, let
qt+τ
C(t, n) = n0 −3 0
2 ∏i=1 1 − q−n +i+1
and let k ≥ C(t, n). Let f : Fnq → Fq be a function such that there exist k hyperplanes H1 , . . . , Hk in Fnq
such that f |Hi ∈ F for every i ∈ [k]. Then there exists h ∈ F such that f |Hi = h|Hi for every i ∈ [k].
We first note that the hypothesis does imply the theorem. This is so since the denominator in the
above expression is
n0 −3 n0 −3 n0 −3
−n0 +i+1 −n0 +i+1 −n0 +1
2 ∏ 1−q ≥ 2 1− ∑ q = 2 − 2q ∑ qi
i=1 i=1 i=1
−n0 +1 n0 −2
> 2 − 2q ·q = 2 − 2q−1 ≥ 1 ,
and so C(t, n) ≤ qt+τ .
Base Case (n ≤ t + τ4 ): In this case we have
k ≥ C(t, n) ≥ qt+τ /2 ≥ qt+τ−1 ≥ qt+τ4 −4 .
Applying Lemma 4.18 with c = 4, we find that we have k ≥ qt+τc −c and n ≤ t + τc and so a function h as
desired exists.
Inductive step: In Claim 4.25 below we prove that there exists a linear function L such that for every
γ ∈ Fq the hyperplane HL(x)−γ is “good” in the sense that the set
Sγ = Hi ∩ HL(x)−γ i ∈ [k], dim(Hi ∩ HL(x)−γ ) = n − 2
is of size at least C(t, n − 1). By induction, we conclude that for every γ the functions f |HL(x)−γ belong
to F (since each agrees with a member of F on at least C(t, n − 1) hyperplanes). Using interpolation,
we conclude the existence of a function h ∈ F+ which agrees with f on all hyperplanes Hi . Applying
+ 2
Theorem 4.9 (using the fact that τ ≥ q2 + q + 1 and hence k ≥ qt +q +2 ) we now conclude that h ∈ F.
Details follow.
Claim 4.25. There exists a linear function L ∈ Affn such that for every γ ∈ Fq the set
Sγ = HL(x)−γ ∩ Hi i ∈ [k], dim HL(x)−γ ∩ Hi = n − 2
has cardinality at least C(t, n − 1).
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 325
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
Proof. Without loss of generality assume k = C(t, n). Let Li ∈ Affn be an affine function such that
Hi = HLi . For L ∈ Affn and i 6= j ∈ [k] such that Hi ∩ H j 6= 0/ the sets HL−γ ∩ Hi , HL−γ ∩ Hj are the same
only if there exist α, β ∈ Fq \{0} such that L = αLi + β L j + γ. Moreover, dim HL−γ ∩ Hi 6= n − 2 only
if there are α, γ 0 ∈ Fq such that L = αLi + γ 0 .
There are at most k2 q3 ways to represent a function in Affn as L = αLi + β L j + γ where i, j ∈ [k] and
α, β , γ ∈ Fq . Hence there is some function L ∈ Affn such that there are at most
k2 q3 k2
= n−2
|Affn | q
such different ways to represent it (we allow α, β and γ ∈ Fq arbitrary to be zero to deal with the case
where L = αLi + γ 0 ). As we saw, for any hyperplane that we lose in the set Sγ there is at least one such
representation for L. So |Sγ | ≥ k − (k2 /qn−2 ). Calculating
k2
k
|Sγ | ≥ k − n−2 = k 1 − n−2
q q
t+τ
q 0
≥ C(t, n) 1 − n−2 = C(t, n) 1 − q−n +2
q
0 qt+τ
= 1 − q−n +2
n0 −3 0
2 ∏i=1 1 − q−n +i+1
qt+τ
= n0 −3 0
2 ∏i=2 1 − q−n +i+1
qt+τ
= n0 −4 0
= C(t, n − 1) .
2 ∏i=1 1 − q−n +i+2
We are ready to continue the proof of Theorem 4.15. Consider the function L ∈ Affn as promised by
Claim 4.25 and fix some γ ∈ Fq . Observe that there are C(t, n − 1) hyperplanes of the space HL−γ of the
form Hi ∩ HL−γ where i ∈ [k]. On each one
f |Hi ∩HL−γ = f |Hi |Hi ∩HL−γ ∈ F .
So, by the induction hypothesis there exists some function hγ ∈ F such that
f |HL−γ |Hi ∩HL−γ = hγ |Hi ∩HL−γ
for all i ∈ [k] such that dim(Hi ∩ HL−γ ) = n − 2.
Define
L(x) − α
h(x) = ∑ ∏ · hγ (x) .
γ∈Fq α6=γ γ − α
By Lemma 4.5, h is in F+ . Let i ∈ [k] and x ∈ Hi . Define γ 0 = L(x), so clearly x ∈ Hi ∩ HL−γ 0 and hence
γ0 − α
h(x) = ∑ ∏ · hγ (x) = hγ 0 (x) = f (x) .
γ∈Fq α6=γ γ − α
We saw that h|Hi = f |Hi for any i ∈ [k]. We conclude by observing that h ∈ F+ is a function such that on
2
k ≥ qt+q +q+1 hyperplanes H, h|H ∈ F. Hence by Theorem 4.9 h ∈ F and we are done.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 326
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
4.3.4 The case of general δ
We finally turn to the proof of Theorem 2.1. To prove this theorem, we shall also need the following
proposition whose proof appears as part of the proof of Lemma 4.16 in [15].
Proposition 4.26. Let f , g : Fnq → Fq be a pair of functions such that there are k hyperplanes H1 , . . . , Hk
which satisfy δ ( f |Hi , g|Hi ) < δ for all 1 ≤ i ≤ k. Then
4(q − 1)
δ ( f , g) ≤ 2δ + .
k
We include the proof below for completeness.
Proof. Let S ⊆ Fnq be the set of points given by
n
S , x ∈ Fq Pr [x ∈ Hi ] ≤ 1/(2q) .
i∈[k]
We claim first that δ ( f , g) ≤ 2δ + |S|/qn . To see this consider the following experiment: Pick a
random hyperplane Hi by picking i uniformly from [k] and pick a point x uniformly at random from Fnq
and let I = I(i, x) = 1 if x lies on Hi and f (x) 6= g(x). On the one hand we have E[I] ≤ δ /q since the
probability that x lies on Hi is 1/q and conditioned on x ∈ Hi the probability that f and g disagree is at
most δ . On the other hand, the probability that f and g disagree on x and x 6∈ S is at least δ ( f , g) − |S|/qn
and conditioned on x 6∈ S, the probability that x ∈ Hi is at least 1/(2q). We conclude that
1 δ
(δ ( f , g) − |S|/qn ) ≤
2q q
and so δ ( f , g) ≤ 2δ + |S|/qn . Thus it suffices to show that |S|/qn ≤ 4(q − 1)/k, which we do next (by an
application of Chebychev bound).
Consider picking x ∈ Fnq at random and let Yi = Yi (x) = 1 if x ∈ Hi . Notice x ∈ S if and only if
k
Y (x) , ∑ Yi (x) < k/(2q) .
i=1
We have E[Yi ] = 1/q and E[YiY j ] ≤ 1/q2 (we have E[YiY j ] = 1/q2 if the hyperplanes are not parallel and
E[YiY j ] = 0 if they are). Thus Y = ∑ki=1 Yi has expectation k/q and variance
k k(k − 1) k2
2 2 1 1
E[Y ] − E[Y ] ≤ + − 2 =k 1− .
q q2 q q q
By the Chebychev bound it follows that
(2q)2 k(1/q)(1 − 1/q) 4(q − 1)
k k
Pr Y < ≤ Pr |Y − E[Y ]| ≥ ≤ = .
2q 2q k2 k
The proposition follows.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 327
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
We can now prove Theorem 2.1 as a corollary of Theorem 4.15 and Proposition 4.26.
Proof of Theorem 2.1. For all i ∈ [k] let gi be a function in F such that δ (gi |Hi , f |Hi ) ≤ δ . We will show
that the functions g1 , . . . , gk are consistent with each other, namely that
gi |Hi ∩H j = g j |Hi ∩H j
for all 1 ≤ i, j ≤ k.
For any i, j ∈ [k], if Hi ∩ H j = 0/ then there is nothing to prove. Else,
δ gi |Hi ∩H j , g j |Hi ∩H j ≤ δ gi |Hi ∩H j , f |Hi ∩H j + δ f |Hi ∩H j , g j |Hi ∩H j ≤ qδ + qδ < q−t .
But by Corollary 3.6, the distance of F is at least q−t , so gi and g j must agree on Hi ∩H j . Theorem 4.15
then implies the existence of a function g ∈ F such that g|Hi = gi |Hi for every i ∈ [k]. By Proposition 4.26,
δ (g, f ) ≤ 2δ + 4(q − 1)/k and so δF ( f ) ≤ 2δ + 4(q − 1)/k as required.
5 Proof of Main Theorem 1.1, Q = q case
In this section we prove our Main Theorem 1.1 for the special case in which Q = q. In order to prove
Theorem 1.1 in this case, we first show in Lemma 5.1 below, using probabilistic arguments, bounds on
the rejection probability of the `-dimensional test for the case in which f is relatively close to F and
` ≥ t + 1. In Lemma 5.2 we then use our Main Technical Theorem 2.1 to bound the rejection probability
of the `-dimensional test for the case in which f is relatively far from F and ` ≥ t + c for some absolute
constant c. Combining Lemmas 5.1 and 5.2 one can bound the rejection probability of the `-dimensional
test when ` = t + c. Relating this to the rejection probability of the t-dimensional test requires some extra
work given in Lemma 5.3 and Corollary 5.4 below.
We start by analyzing the rejection probability of the `-dimensional test for the case in which f is
relatively close to F and ` ≥ t + 1. Recall that Rej` ( f ) denotes the probability that the `-dimensional test
rejects the function f : Fnq → Fq .
Lemma 5.1. Let F = Liftn (B) for an affine-invariant linear base code B ⊆ {Ftq → Fq }. Then for every
n ≥ ` ≥ t + 1, and every f : Fnq → Fq , if δF ( f ) ≤ q−(t+1) /2 then
1 q` δF ( f )
Rej` ( f ) ≥ min , .
4q 2
Proof. The proof is similar to the proof of Lemma 5.1 in [15]. We will use the monotonicity of the
rejection probability and prove a bound on Rej`0 ( f ) for some `0 ≤ `.
Let `0 be such that t + 1 ≤ `0 ≤ ` and let A be an `0 -dimensional subspace. Let g ∈ F be the function
0
closest to f , so that δ ( f , g) = δ , δF ( f ). We now use the fact that δ ( f |A , g|A ) is the average of N = q`
random {0, 1}-valued variables of expectation δ that are roughly pairwise independent to derive a
lower bound on the probability that f |A and g|A disagree on exactly one point. Note that if f |A and g|A
0
disagree on exactly one point, then δ ( f |A , g|A ) = q−` < q−t due to our assumption that `0 ≥ t + 1. But by
Corollary 3.6 we have that δ (F) ≥ q−t and consequently f |A ∈ / F in this case. Thus the `0 -dimensional
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 328
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
test rejects whenever f |A and g|A disagree on exactly one point and this will imply a lower bound on
Rej`0 ( f ).
Let A be specified by α0 , . . . , α`0 ∈ Fnq such that
( 0
)
`
0
A= A(θ ) , α0 + ∑ θi αi θ = (θ1 , . . . , θ`0 ) ∈ F`q .
i=1
0
Fix θ ∈ F`q , and let X(θ ) denote the random variable that is 1 if f (A(θ )) 6= g(A(θ )) and 0 otherwise,
0
where A is a uniform `0 -dimensional affine subspace. We note that for every θ ∈ F`q , we have EA [X(θ )] =
0
δ . Furthermore, for every pair of distinct points θ , η ∈ F`q we have EA [X(θ )X(η)] ≤ δ 2 . (If the points
α1 , . . . , α`0 were not required to be linearly independent, this expectation would be exactly δ 2 . But
because we insist that they are independent we get that A(θ ) and A(η) are two distinct random points in
Fnq and so the bound above is a (strict) inequality.) Furthermore we have
0
δ ( f |A , g|A ) = q−` ∑ X(θ ) .
θ
Thus we have
−`0 −`0 −`0 0 0 0 0
Pr δ ( f |A , g|A ) = q = Pr q ∑ X(θ ) = q ≥ q` δ (1 − (q` − 1)δ ) ≥ q` δ (1 − q` δ ).
A
θ
When δ ≤ (1/2)q−` the bound above implies that Rej` ( f ) ≥ (1/2)q` δ . Else, let `0 be the largest integer
0 0
such that δ ≤ (1/2)q−` (and so δ > (1/2q)q−` ). Note that the assumption that δF ( f ) ≤ q−(t+1) /2
implies that `0 ≥ t + 1. We then get
1 0 1
Rej` ( f ) ≥ Rej`0 ( f ) ≥ q` δ > .
2 4q
The lemma follows.
Next we bound the rejection probability of the `-dimensional test in the case in which f is relatively
far from F and ` ≥ t + c for some absolute constant c.
Lemma 5.2. Let F = Liftn (B) for an affine-invariant linear base code B ⊆ {Ftq → Fq }. Then for every
q there exist ε > 0 and c such that if n ≥ ` ≥ t + c we have the following: For every f : Fnq → Fq with
δF ( f ) ≥ q−` we have
∞
1
Rej` ( f ) ≥ ε + q` ∑ q−i .
16 i=n+1
Proof. The proof is identical to the proof of Lemma 5.2 in [15]. Let c = max{τ + 3, 9} where τ is the
constant from Theorem 2.1.
We prove the lemma by induction on n. The base case n = ` is straightforward since in this case
Rej` ( f ) = 1 and
1 ` ∞ −i 1 1
q ∑ q ≤ ≤
16 i=n+1 16(q − 1) 16
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 329
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
and so this case holds for every ε ≤ 15/16.
For the inductive step, let H1 , . . . , Hk be all hyperplanes which satisfy δLn−1 ( f |Hi ) ≤ q−` . If k <
(1/16)q` then we are done by induction since
1 ` ∞ −i k 1 ∞
Rej` ( f ) = EH [Rej` ( f |H )] ≥ ε + q ∑ q − n ≥ ε + q` ∑ q−i
16 i=n q 16 i=n+1
as desired.
Finally we are left with the case where k ≥ (1/16)q` . In this case we use Theorem 2.1 to show that
δF ( f ) is small and then use Lemma 5.1 to show that Rej` ( f ) is large. Specifically, by Theorem 2.1 we
have
4(q − 1)
δF ( f ) ≤ 2q−` + ≤ (2 + 64q) · q−` ≤ (66q) · q−` .
k
Since ` ≥ t + c and c ≥ 9 we have δF ( f ) < q−t /2 and so by Lemma 5.1 we have
1 q` δF ( f )
∞
1 1 1
Rej` ( f ) ≥ min , ≥ ≥ε+ = ε + q` ∑ q−i
4q 2 4q 16(q − 1) 16 i=`+1
for every ε < 1/(32q). So the lemma is true for ε = 1/(32q).
As noted above, Lemmas 5.1 and 5.2 suffice to analyze the rejection probability of a sufficiently high
dimensional test (` = t + c), but not the t-dimensional test. To relate the two we use a lemma similar
to Lemma 4.7 from [15]. We note that the proof again gets new complications since our result is more
general.
Lemma 5.3. Let F = Liftn (B) for an affine-invariant linear code B ⊆ {Ftq → Fq }. Let f : Fnq → Fq be a
function such that f 6∈ F. Then PrH [ f |H ∈
/ F] ≥ 1/q where the probability is over a hyperplane H chosen
n
uniformly in Fq .
/ F there exists an affine transformation T ∈ Affn×n such that
Proof. Since f ∈
f ◦ T |xt+1 =···=xn =0
is not in B. To simplify notation, assume T is the identity. We now bound the number of hyperplanes H
such that f |H ∈ F. Each hyperplane can be written as
( )
n
Hα = x ∈ Fnq xc = ∑ αi xi + α0
i=c+1
for α = (α0 , . . . , αn ) ∈ Fn+1
q , where c ≥ 1 is the first coordinate such that αc 6= 0. For such a hyperplane
define !
n
fα := f x1 , . . . , xc−1 , ∑ αi xi + α0 , xc+1 , . . . , xn .
i=c+1
Observe that f |Hα ∈ F if and only if fα ∈ F.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 330
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
We divide into cases according to the value of c. For any hyperplane Hα for which c > t we will
show the existence of a hyperplane Hα 0 , where α 0 may differ from α only by the 0-th coordinate, such
/ F. Similarly, for any hyperplane Hα for which 1 ≤ c ≤ t we will show the existence of a
that f |Hα 0 ∈
/ F. This will
hyperplane Hα 0 , where α 0 may differ from α only by the n-th coordinate, such that f |Hα 0 ∈
prove the claim since it will map at most q different hyperplanes to one “good” hyperplane.
First, consider the case where c > t. In this case consider α 0 such that ∀i > 0 : αi0 = αi and α00 = 0.
Then
/ B,
fα 0 |xt+1 =···=xn =0 = f |xt+1 =···=xn =0 ∈
hence fα 0 ∈ / F which implies in turn that f |Hα 0 ∈
/ F.
Next assume that 1 ≤ c ≤ t and for a variable z, let α(z) ∈ Fn+1 q denote the vector which satisfies
α(z)i = αi for all i 6= n and α(z)n = z. Our goal will be to show that there exists an assignment β ∈ Fq
to z for which fα(β ) ∈ / F. In order to do so we shall show that there exists a monomial M in variables
/ F and the coefficient of M is a non-zero polynomial in the variable
x1 , . . . , xn in supp( fα(z) ) such that M ∈
z. This will imply in turn that there exists an assignment β ∈ Fq to z such that M has a non-zero coefficient
in fα(β ) and consequently fα(β ) ∈ / F.
Consider the affine transformation B ∈ Affn×n which satisfies
n−1
∀i 6= c : B(ei ) = ei and B(ec ) = ec + ∑ αi ei + α0
i=c+1
and the affine transformation B0 ∈ Afft×t which satisfies
t
∀i 6= c : B0 (ei ) = ei and B0 (ec ) = ec + ∑ αi ei + α0 .
i=c+1
Observe that
f ◦ B|xt+1 =···=xn =0 = f |xt+1 =···=xn =0 ◦ B0 ∈
/B.
Therefore, there exists a monomial M = ∏ti=1 xiai , containing only the variables x1 , . . . , xt , that is
in supp( f ◦ B) but not in supp(B). By Claim 3.4, we also have that M ∈ / supp(F). Note next that the
function fα(z) is obtained from f ◦ B by substituting xc with zxn . This implies in turn that the monomial
zac xnac ∏ xia i
i∈[t]\{c}
is a monomial of fα(z) when viewed as a function of the variables {xi }i6=c and z.
Now view fα(z) as a function of {xi }i6=c with coefficients that are functions of z. Then the coefficient
of the monomial
M 0 = xnac ∏ xiai
i∈[t]\{c}
is a non-zero polynomial in z. Hence, there is some value β ∈ Fq such that if we substitute z = β then
the coefficient of M 0 will be non-zero. In particular, fα(β ) has the monomial M 0 in its support. The
/ F implies that M 0 ∈
proof is completed by noting that M ∈ Affn×n (M 0 ) and hence the fact that M ∈ / F.
Consequently, fα(β ) ∈/ F.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 331
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
By applying the above lemma iteratively we obtain the following corollary.
Corollary 5.4. Let F = Liftn (B) for an affine-invariant linear code B ⊆ {Ftq → Fq } and let n ≥ ` ≥ k ≥ t.
/ F. Then Rejk ( f ) ≥ Rej` ( f ) · q−(`−k) .
Let f : Fnq → Fq be a function such that f ∈
Proof. The proof is by induction on k. The base case, where k = ` is trivial. Now assume the corollary
holds for k = r + 1 and we will prove it for k = r. Consider the following way of choosing a random
r-dimensional affine subspace. First choose a random (r + 1)-dimensional affine subspace V 0 ⊆ Fnq and
then choose a random r-dimensional affine subspace V ⊆ V 0 . Then
/ F ≥ Pr f |V ∈ / F f |V 0 ∈/ F Pr f |V 0 ∈
/F
Rejr ( f ) = Pr f |V ∈
1
≥ · Rej` ( f ) · q−(`−(r+1)) = Rej` ( f ) · q−(`−r) ,
q
where the last inequality is obtained by the induction hypothesis and Lemma 5.3.
Proof of Theorem 1.1, Q = q case. Follows immediately from Lemmas 5.1 and 5.2 and Corollary 5.4.
6 Proof of Main Theorem 1.1, general Q
In this section we prove Theorem 1.1 for the case in which Q 6= q via a simple reduction to the Q = q
case. For this we shall need several facts concerning affine-invariant linear codes from FnQ to Fq . The
following lemma is a generalization of the monomial extraction lemma (Lemma 3.1) for such codes.
Lemma 6.1 ([13, Proposition 2.2]). Let F ⊆ FnQ → Fq be an affine-invariant linear code. Then
F = f : FnQ → Fq | supp( f ) ⊆ supp(F) .
Let Q = qs for an integer s, and let Trace denote the trace function from FQ to Fq given by
s−1
Trace(x) = x + xq + · · · + xq .
The following lemma says that if a monomial belongs to the support of an affine-invariant linear code
then its trace belongs to the code.
Lemma 6.2 ([13, Lemma A.7.]). Let F ⊆ {FnQ → Fq } be an affine-invariant linear code, and suppose
that M ∈ supp(F). Then Trace(αM) ∈ F for every α ∈ FQ .
The above lemma yields the following corollary.
Corollary 6.3. Let F ⊆ {FnQ → Fq } be an affine-invariant linear code, and suppose that f ∈ F. Then
Trace(α f ) ∈ F for every α ∈ FQ .
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 332
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
Proof. Let f = ∑M∈Mn cM M for cM ∈ FQ . Lemma 6.2 implies that Trace(αcM M) ∈ F for every M ∈ Mn
and α ∈ FQ . By linearity of the trace function, we have that
Trace(α f ) = ∑ Trace(αcM M) ,
M∈Mn
and hence Trace(α f ) ∈ F by linearity of F.
Proof of Theorem 1.1, Q 6= q case. Let B0 be the FQ -span of B, i. e.,
0
B = ∑ αi fi fi ∈ B, αi ∈ FQ ,
i
and let F0 = Liftn (B0 ). Note that B0 is an affine-invariant linear code from FtQ to FQ .
We start by showing that B0 6= FtQ → FQ . To see this note that our assumption that B 6= FtQ → Fq ,
together with Lemma 6.1, imply that there exists a monomial M ∈ Mt such that M ∈ / supp(B). Since
B and B have the same set of monomials in their support, we have that M ∈
0 / supp(B0 ) and hence
B 6= FQ → FQ .
0 t
We have just shown that B0 ( FtQ → FQ is an affine-invariant linear code. Hence Theorem 1.1 for
ntester T for F0 which makes Q queries, accepts every function f ∈ F and
the Q = q case implies a local 0 t 0
rejects every function f ∈ FQ → FQ \ F with probability at least εQ δF0 ( f ).
We claim that T is also a local tester for F with the same soundness parameter εQ and consequently
F is (Qt , εQ , Q−t )-locally testable. For this it suffices to show that δF0 ( f ) = δF ( f ) for every function
f : FnQ → Fq .
Fix f : FnQ → Fq . Since B ⊆ B0 , we clearly have that F ⊆ F0 , and consequently δF0 ( f ) ≤ δF ( f ). It
remains to show that δF0 ( f ) ≥ δF ( f ). To see this, let g ∈ F0 be such that δF0 ( f ) = δ ( f , g). Then clearly
δ ( f , Trace(g)) ≤ δ ( f , g). Next we show that Trace(g) ∈ F and so δF0 ( f ) ≥ δF ( f ).
We need to show that Trace(g)|A ∈ B for every t-dimensional affine subspace A. Let A be a t-
dimensional affine subspace. Since g ∈ F0 we have that g|A ∈ B0 , so g|A = ∑i αi fi for fi ∈ B and αi ∈ FQ .
Hence Trace(g)|A = Trace(g|A ) = ∑i Trace(αi fi ) by linearity of the trace function. By Corollary 6.3 we
have that Trace(αi fi ) ∈ B for all i. Finally, by linearity of B, this implies that Trace(g)|A ∈ B which
completes the proof of the Theorem.
7 New testable codes
In this section, we give some examples of codes with “nice” parameters that are testable with absolute
soundness based on our main theorem (Theorem 1.1).
The need for such codes is motivated by the work of Barak et al. [3]. Their work used appropriate
Reed–Muller codes over the domain Fn2 . Our work gives the second family of codes that is known to
satisfy their requirements. We point out that Guo et al. [14] also give codes motivated by the work of [3],
but their codes are not, thus far, known to be testable with absolute soundness and so fail to meet all
the requirements of [3]. Our codes fall within the class of “lifted” codes studied by [14], but were not
analyzed there. Here we use analysis similar to their to analyze the rate and distance of our codes, while
the testing follows from our main theorem.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 333
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
The code. Our codes are defined by three parameters: a real number ε > 0 and a pair of integers s and
n. The code F = Fε,s,n is obtained as follows: Let Q = 2s , q = 2 and let ` = b(1/s) log 1/εc. Let
B = f : Fn−`Q → F q ∑ f (~
x) = 0 .
n−`
~x∈FQ
Let F = Liftn (B).
Basic parameters:
Proposition 7.1. For every ε, s and n the code F = Fε,s,n has block length N = 2sn , (absolute, non-
normalized) distance at least 1/ε and dimension at least
s s`−1 !
sn n ns
2 − +∑ .
` i=0 i
Proof. The block length can be easily verified and the distance follows from Proposition 3.5 and Lemmas
3.11 and 3.12 in Guo et al. [14] Lemmas 3.11 and 3.12 from Guo et al. [14] who analyzed the dimension
of the code Fε,s,n for the case in which s = log(1/ε) (so ` = 1). More specifically, given a degree pattern
( j)
a = (a1 , . . . , an ) with {ai }ni=1 ⊆ {0, . . . , Q − 1}, let ai denote the j-th bit of the binary expansion of ai .
( j)
Let M(a) denote the n × s matrix with entries M(a)i, j = ai . Guo et al. show that in the special case in
which ` = 1 the code Fε,s,n contains in its support all monomials with degree pattern a = (a1 , . . . , an ) such
that there exists a column in M(a) with at least two zeroes. This readily implies a bound of 2sn − (n + 1)`
on the dimension of their code.
A similar analysis shows that our code Fε,s,n contains all monomials with degree pattern a =
(a1 , . . . , an ) where the matrix M(a) has at least s` + 1 zeroes, or the matrix has s` zeroes and there
exists a column in M(a) with at least ` + 1 zeros. The lower bound on the dimension follows.
Testability: The following is an immediate application of Theorem 1.1.
Proposition 7.2. For every s there exists a constant τ > 0 such that for every ε and n the code F = Fε,s,n
is testable by a test that makes εN queries, accepts codewords with probability one, while rejecting all
functions f : FnQ → Fq with probability at least τ · δF ( f ).
We remark that the dimension of our codes, for any choice of N and ε is strictly better than that of the
codes used in [3] which have dimension
s`
sn sn 1
2 −∑ ≈ 2sn − √ (en/`)s` .
i=0 i 2πs`
An important parameter for them is the codimension of their code (block length minus the dimension, or
the dimension of the dual code), which thus turns out to be roughly
1
√ (en/`)s`
2πs`
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 334
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
from the above expression. (A smaller codimension is better for their application.) Simplifying the
dimension of our code from Proposition 7.1, we see that the codimension of our code is smaller by
a multiplicative factor of roughly O(`s/2−1 ), making our codes noticeably better. Unfortunately such
changes do not alter the essential relationship between N = 2sn , the parameter ε (which determines
the locality of the tester) and the codimension of the code. The following theorem summarizes the
performance of our codes.
Theorem 7.3. For every positive s there exists a constant τ such that for every sufficiently small ε and
sufficiently large N there exists a binary code of block length N, codimension
!log ε1
1 −s
e log N
log ·
ε log ε1
that is testable with a tester that makes ε · N queries accepting codewords with probability one, while
rejecting words at distance δ from the code with probability at least τ · δ .
To contrast, the corresponding result in [3] would assert the existence of a positive constant s for
which the above held.
References
[1] N OGA A LON , TALI K AUFMAN , M ICHAEL K RIVELEVICH , S IMON L ITSYN , AND DANA RON:
Testing Reed-Muller codes. IEEE Trans. Inform. Theory, 51(11):4032–4039, 2005. prrr RAN-
DOM’03. [doi:10.1109/TIT.2005.856958] 302
[2] S ANJEEV A RORA AND M ADHU S UDAN: Improved low-degree testing and its applications. Combi-
natorica, 23(3):365–426, 2003. Preliminary version in STOC’97 and ECCC. [doi:10.1007/s00493-
003-0025-0] 302
[3] B OAZ BARAK , PARIKSHIT G OPALAN , J OHAN H ÅSTAD , R AGHU M EKA , P RASAD R AGHAVEN -
DRA , AND DAVID S TEURER: Making the long code shorter, with applications to the unique games
conjecture. In Proc. 53rd FOCS. IEEE Comp. Soc. Press, 2012. Preliminary version in ECCC.
[doi:10.1109/FOCS.2012.83] 301, 303, 333, 334, 335
[4] E LI B EN -S ASSON , E LENA G RIGORESCU , G HID M AATOUK , A MIR S HPILKA , AND M ADHU
S UDAN: On sums of locally testable affine invariant properties. In Proc. 15th Internat. Workshop
on Randomization and Computation (RANDOM’11), pp. 400–411. Springer, 2011. Available at
author’s website and ECCC. [doi:10.1007/978-3-642-22935-0_34] 300, 306
[5] E LI B EN -S ASSON , G HID M AATOUK , A MIR S HPILKA , AND M ADHU S UDAN: Symmetric LDPC
codes are not necessarily locally testable. In Proc. 26th IEEE Conf. on Computational Com-
plexity (CCC’11), pp. 55–65. IEEE Comp. Soc. Press, 2011. Preliminary version in ECCC.
[doi:10.1109/CCC.2011.14] 300, 301, 306
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 335
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
[6] E LI B EN -S ASSON AND M ADHU S UDAN: Limits on the rate of locally testable affine-invariant
codes. In Proc. 15th Internat. Workshop on Randomization and Computation (RANDOM’11),
volume 6845 of Lecture Notes in Computer Science, pp. 412–423. Springer, 2011. Preliminary
version in ECCC. [doi:10.1007/978-3-642-22935-0_35] 300, 306
[7] A RNAB B HATTACHARYYA , E LDAR F ISCHER , H AMED H ATAMI , P OOYA H ATAMI , AND S HACHAR
L OVETT: Every locally characterized affine-invariant property is testable. In Proc. 45th STOC, pp.
429–436. ACM Press, 2013. Preliminary version in ECCC. [doi:10.1145/2488608.2488662] 303
[8] A RNAB B HATTACHARYYA , S WASTIK KOPPARTY, G RANT S CHOENEBECK , M ADHU S UDAN ,
AND DAVID Z UCKERMAN : Optimal testing of Reed-Muller codes. In Proc. 51st FOCS, pp. 488–
497. IEEE Comp. Soc. Press, 2010. Available at ITCS’10 and ECCC. [doi:10.1109/FOCS.2010.54]
301, 303, 304, 305, 306
[9] M ANUEL B LUM , M ICHAEL L UBY, AND RONITT RUBINFELD: Self-testing/correcting with appli-
cations to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. Preliminary version
in STOC’90. [doi:10.1016/0022-0000(93)90044-W] 302
[10] H ILLEL F URSTENBERG AND Y ITZHAK K ATZNELSON: A density version of the Hales-Jewett
theorem. J. d’Analyse Math., 57(1):64–119, 1991. [doi:10.1007/BF03041066] 320
[11] E LENA G RIGORESCU , TALI K AUFMAN , AND M ADHU S UDAN: Succinct representation of codes
with applications to testing. SIAM J. Discrete Math., 26(4):1618–1634, 2012. Preliminary versions
in RANDOM’09 and ECCC. [doi:10.1137/100818364] 300, 306
[12] E LENA G RIGORESCU , TALI K AUFMAN , AND M ADHU S UDAN: 2-Transitivity is insufficient
for local testability. Comput. Complexity, 22(1):137–158, 2013. Preliminary version in CCC’08.
[doi:10.1007/s00037-012-0055-3] 300, 306
[13] A LAN G UO , S WASTIK KOPPARTY, AND M ADHU S UDAN: New affine-invariant codes from lifting.
Electron. Colloq. on Comput. Complexity (ECCC), TR12-019, 2012. 309, 332
[14] A LAN G UO , S WASTIK KOPPARTY, AND M ADHU S UDAN: New affine-invariant codes from lifting.
In ITCS’13, pp. 529–540, 2013. Preliminary version in ECCC. [doi:10.1145/2422436.2422494]
300, 301, 302, 303, 333, 334
[15] E LAD H ARAMATY, A MIR S HPILKA , AND M ADHU S UDAN: Optimal testing of multivariate
polynomials over small prime fields. SIAM J. Comput., 42(2):536–562, 2013. Preliminary versions
in FOCS’11 and ECCC. [doi:10.1137/120879257] 301, 302, 303, 304, 305, 306, 307, 312, 319,
320, 321, 324, 327, 328, 329, 330
[16] C HARANJIT S. J UTLA , A NINDYA C. PATTHAK , ATRI RUDRA , AND DAVID Z UCKERMAN: Testing
low-degree polynomials over prime fields. Random Structures Algorithms, 35(2):163–193, 2009.
Preliminary version in FOCS’04. [doi:10.1002/rsa.20262] 302
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 336
A BSOLUTELY S OUND T ESTING OF L IFTED C ODES
[17] TALI K AUFMAN AND DANA RON: Testing polynomials over general fields. SIAM J. Comput.,
36(3):779–802, 2006. Preliminary verison found in FOCS’04. [doi:10.1137/S0097539704445615]
302
[18] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: The role of invariance. Electron.
Colloq. on Comput. Complexity (ECCC), TR07-111, 2007. 300, 302, 303, 306, 308, 310
[19] TALI K AUFMAN AND M ADHU S UDAN: Algebraic property testing: the role of invari-
ance. In Proc. 40th STOC, pp. 403–412. ACM Press, 2008. Expanded version in ECCC.
[doi:10.1145/1374376.1374434] 303, 304
[20] D. H. J. P OLYMATH: A new proof of the density Hales-Jewett theorem. Ann. Math., 175(3):1283–
1327, 2012. Preliminary version in CoRR. [doi:10.4007/annals.2012.175.3.6] 320
[21] R AN R AZ AND S HMUEL S AFRA: A sub-constant error-probability low-degree test, and a sub-
constant error-probability PCP characterization of NP. In Proc. 29th STOC, pp. 475–484. ACM
Press, 1997. [doi:10.1145/258533.258641] 302, 304
[22] N OGA RON -Z EWI AND M ADHU S UDAN: A new upper bound on the query complexity of testing
generalized Reed-Muller codes. Theory of Computing, 9(25):783–807, 2013. Preliminary version
in RANDOM’12. [doi:10.4086/toc.2013.v009a025] 302
[23] RONITT RUBINFELD AND M ADHU S UDAN: Robust characterizations of polynomi-
als with applications to program testing. SIAM J. Comput., 25(2):252–271, 1996.
[doi:10.1137/S0097539793255151] 302
AUTHORS
Elad Haramaty
Northeastern University
eladh cs technion ac il
Noga Ron-Zewi
Institute for Advanced Study, Princeton, and
Rutgers University
nogazewi ias edu
https://sites.google.com/site/nogazewi/
Madhu Sudan
Microsoft Research New England, Cambridge, MA
madhu mit edu
http://people.csail.mit.edu/madhu/
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 337
E LAD H ARAMATY, N OGA RON -Z EWI AND M ADHU S UDAN
ABOUT THE AUTHORS
E LAD H ARAMATY is a postdoctoral researcher at Northeastern University in the College of
Computer and Information Science, hosted by Emanuele Viola. He earned his Ph. D. from
the Technion - Israel Institute of Technology under the guidance of Amir Shpilka. His
research interests lie in a broad range of areas of theoretical computer science, especially
in algebraic complexity. In his work he has studied mostly the structure, testability and
applications of polynomials and algebraic codes. This paper was written while Elad was
a Ph. D. student at the Technion.
N OGA RON -Z EWI is an IAS-DIMACS postdoc with a joint postdoctoral position at the
Institute for Advanced Study (IAS) at Princeton and the Center for Discrete Mathematics
and Theoretical Computer Science (DIMACS) at Rutgers. Her hosts are Avi Wigderson
and Michael Saks. She received her Ph. D. from the Department of Computer Science at
the Technion in 2014, under the supervision of Eli Ben-Sasson. Her research interests are
in the theory of computation, with a focus on computational aspects of communication
and coding. This paper was written while Noga was a Ph. D. student at the Technion.
M ADHU S UDAN received his Ph. D. from the University of California at Berkeley in 1992.
From 1992 to 1997 he was a research staff member at IBM’s Thomas J. Watson Research
Center. From 1997 to 2009 he was a faculty member at the Electrical Engineering
and Computer Science Department at the Massachusetts Institute of Technology. He
is currently a Principal Researcher at Microsoft Research New England. His research
has focused on Probabilistic Checking of Proofs, List-Decoding, Property Testing, and
Semantic Communication.
T HEORY OF C OMPUTING, Volume 11 (12), 2015, pp. 299–338 338