Authors Shachar Lovett,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82
www.theoryofcomputing.org
Unconditional Pseudorandom Generators for
Low-Degree Polynomials
Shachar Lovett∗
Received: July 14, 2008; published: May 27, 2008.
Abstract: We give an explicit construction of a pseudorandom generator against low-
degree polynomials over finite fields. Pseudorandom generators against linear polynomials,
known as small-bias generators, were first introduced by Naor and Naor (STOC 1990). We
O(d)
show that the sum of 2d independent small-bias generators with error ε 2 is a pseudoran-
dom generator against degree-d polynomials with error ε. This gives a generator with seed
length 2O(d) log (n/ε) against degree-d polynomails. Our construction follows the break-
through result of Bogdanov and Viola (FOCS 2007). Their work shows that the sum of d
small-bias generators is a pseudo-random generator against degree-d polynomials, assum-
ing a conjecture in additive combinatorics, known as the inverse conjecture for the Gowers
norm. However, this conjecture was proven only for d = 2, 3. The main advantage of this
work is that it does not rely on any unproven conjectures.
Subsequently, the inverse conjecture for the Gowers norm was shown to be false for
d ≥ 4 by Green and Tao (2008) and independently by the author, Roy Meshulam, and
Alex Samorodnitsky (STOC 2008). A revised version of the conjecture was proved by
Bergelson, Tao, and Ziegler (2009). Additionally, Viola (CCC 2008) showed the original
construction of Bogdanov and Viola to hold unconditionally.
ACM Classification: F.2.1, F.1.3, F.2.2, G.2, G.3
AMS Classification: 68Q10, 68Q17, 12Y05, 60C05
Key words and phrases: pseudorandom, explicit constructions, polynomials, low degree
∗ Research supported by the Israel Science Foundation (grant 1300/05)
2009 Shachar Lovett
Licensed under a Creative Commons Attribution License DOI: 10.4086/toc.2009.v005a003
S HACHAR L OVETT
1 Introduction
We are interested in explicitly constructing pseudorandom generators (PRG) against low-degree poly-
nomials over small finite fields. A pseudorandom generator against a family T of tests is a function G
mapping a small domain into a (much) larger one, such that any test T ∈ T cannot distinguish, with no-
ticeable probability, a random element in the large domain from an application of G to a random element
in the small domain. We say a PRG requires R random bits if the size of the small domain is 2R .
In our case, F is a finite field and a test is a polynomial p(x1 , . . . , xn ) over F. The image of the PRG
is a small subset of Fn , and it is pseudorandom against p(x1 , . . . , xn ) if the distribution of the outcome of
p, when applied to a random element in the small subset, is close to the distribution of the outcome of p,
when applied to a uniform element in Fn . We say the PRG has error ε against p if the statistical distance
between the two distributions is at most ε. We are interested in PRGs that are pseudorandom against all
degree-d polynomials with error ε, and use as few random bits as possible.
The case of pseudorandom generators against linear polynomials, usually called small-bias gener-
ators (or epsilon-biased generators, a term we do not use in this paper to avoid confusion), was first
studied (over F = F2 ) by Naor and Naor [14] and later by Alon, Goldreich, Håstad and Peralta [1]. They
and others gave explicit constructions, which were later generalized to arbitrary finite fields. These con-
structions have a seed length which is optimal up to a constant multiplicative factor. The construction
of small-bias generators is a major tool in derandomization, PCPs and lower bounds (see [4] and the
references within for details regarding small-bias generators).
The generalization of the problem to constant-degree polynomials was first studied by Luby, Velick-
ovic, and Wigderson [13]. Their results apply, in fact, to the more general model of constant depth
circuits. In p
the context of constant degree polynomials, they give an explicit construction of PRG requir-
ing exp(O( log n/ε)) random bits.
Bogdanov [6] gave a construction of a PRG in large fields. The minimum field size required for
his construction is polynomial in the degree, the required error and the log of the number of variables.
In these settings, his construction is optimal up to polynomial factors. The proof of his result uses
techniques and results from algebraic geometry and computational algebra.
Recently, Bogdanov and Viola [7] presented a novel approach for constructing a PRG for low-degree
polynomials over small fields. Their construction is the sum of d independent small-bias generators.
They showed that, if a conjecture in additive combinatorics called the inverse conjecture for the Gowers
norm holds, then their construction is a PRG for degree-d polynomials. At the time, the inverse con-
jecture for the Gowers norm was known to hold only for degrees 2 and 3, and was conjectured to hold
for all constant degrees. Thus, their construction was known to be correct only for quadratic and cubic
polynomials.
Our work [11] was inspired by the work of Bogdanov and Viola, with the goal of making their
construction unconditional, i. e., not relying on any unproven conjectures. We prove that the sum of 2d
independent small-bias generators is pseudorandom against degree-d polynomials, without relying on
any unproven conjectures. Our main theorem is:
Theorem 1.1. There exists a global constant c > 0 such that the following holds. Let G be a small-bias
cd
generator with error ε 2 . Then the sum of 2d independent copies of G is pseudorandom against degree-d
polynomials with error ε. In particular, this gives a pseudorandom generator for degree-d polynomials
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 70
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
with error ε using 2cd log(| F |n/ε) random bits for the seed.
1.1 Overview of proof method
This work is inspired by the recent result of Bogdanov and Viola [7]. We begin by providing a high level
description of it, since several ideas used in [7] are also used in our work.
The analysis of [7] crucially depended on the inverse conjecture for the Gowers norm. Although
we do not use this conjecture in our proof, we now briefly present and discuss it. The Gowers norm,
first defined by Gowers in his new proof for Szemerédi’s theorem [8], is a norm measuring the local
correlation of a function to low-degree polynomials. Let F = Fq be a prime finite field, and assume
f (x) : Fn → F is a function. The directional derivative of f in direction y ∈ Fn is defined to be
fy (x) = f (x + y) − f (x).
Notice that if f is a degree-d polynomial, then fy is a polynomial of degree at most d − 1, hence the
term derivative relates to the more common definition of analytical derivative. We define also iterated
derivatives: fy1 ,...,yk (x) is defined recursively, by taking the k derivatives in directions y1 , . . . , yk . Opening
brackets, this gives
fy1 ,...,yk (x) = ∑ (−1)k−|S| f (x + ∑ yi ).
S⊂{1,...,k} i∈S
The d-th Gowers norm of f is defined as
i 1d
y1 ,...,yd (x)
h f
2
Ud ( f ) = Ex,y1 ,... yd ∈Fq ωq
n ,
2πi
where ωq = e q is a root of unity of order q. It was proved to be a norm on functions (for d ≥ 2) by
Gowers [8].
Assume f is a degree-(d − 1) polynomial. Taking d derivatives results in the zero polynomial, so
fy1 ,...,yd ≡ 0 for any choice of y1 , . . . , yd and consequently Ud ( f ) = 1. It is relatively easy to see that the
converse also holds, that is, Ud ( f ) = 1 iff f is a polynomial of degree at most d − 1. Alon et al. [2]
proved a robust version of this equivalence: the d-th Gowers norm of f is very close to 1 iff the function
f is very close to a degree-(d − 1) polynomial.
The inverse conjecture for the Gowers norm studies the realm of functions with only a noticeable
Gowers norm, that is Ud ( f ) ≥ δ for some δ > 0. Gowers [8] showed that if f is only somewhat close
to a degree-(d − 1) polynomial, that is Prx [ f (x) = p(x)] ≥ 1/q + ε for some degree-(d − 1) polynomial
p(x), then f has a noticeable d-th Gowers norm, Ud ( f ) ≥ ε 0 , where ε 0 = Ω(ε).
The converse of this claim is known as the inverse conjecture for the Gowers norm: if Ud ( f ) ≥ ε,
then there exists a degree-(d − 1) polynomial p such that Prx [ f (x) = p(x)] ≥ 1/q + ε 0 , for some ε 0 > 0
depending on ε. The case of d = 2 can be proven using standard Fourier analysis tools [3]. The case
of d = 3 was proven by Green and Tao [10] and independently by Samorodnitsy [15]. Both works
conjectured this to hold for any constant degree.
Returning to the argument of [7], Bogdanov and Viola analyze the Gowers norm of a degree-d
polynomial p(x), and present a win-win argument, depending on whether the Gowers norm is either
small or large. In the first case, when the Gowers norm is small, they show that the sum of d small-bias
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 71
S HACHAR L OVETT
generators is pseudorandom against p(x), by relating the distribution of p(x1 + · · · + xd ) to the Gowers
norm of p. In the latter case, when the Gowers norm is large, and assuming the inverse conjecture for
the Gowers norm holds, p(x) is correlated to some degree-(d − 1) polynomial q(x). They use q(x) in
order to construct a circuit that computes p(x) for almost all values of x. The inputs to this circuit are
all degree-(d − 1) polynomials; thus they show that a PRG for degree-(d − 1) polynomials with small
enough error is also pseudorandom against p(x).
Our construction follows similar lines; however, instead of analyzing the Gowers norm of p(x), we
analyze its Fourier coefficients. We also divide our treatment into two cases: when p has some large
Fourier coefficient, and when all the Fourier coefficients of p are small.
In the first case, when p(x) has no large Fourier coefficients, we consider inputs to p of the form
x + y, where x and y are independent. We consider the polynomial
∆p(x0 , x00 , y0 , y00 ) = p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 ) .
We prove that it is enough to be pseudorandom against ∆p in order to be pseudorandom against
p(x + y), and also that it is sufficient to have x, x0 , x00 , y, y0 and y00 come from a PRG that is pseudorandom
against degree-(d − 1) polynomials. The reason is that ∆p contains no degree-d terms in just one of x0 ,
x00 , y0 or y00 . In the second case, when there is some large Fourier coefficient, we know that p(x) is
correlated to some linear function. Similarly to the second case in [7], we also show in that case, or
more generally when p(x) is correlated to some lower degree polynomial, a PRG for degree-(d − 1)
polynomials with small enough error is also pseudorandom against p(x). However, our proof technique
is more direct than the one used in [7], which results in better parameters and simpler analysis.
1.2 Subsequent work
This paper is a more polished version of the extended abstract of this work [11], first presented at STOC
2008. Subsequently, there were advances on two fronts.
First, the inverse conjecture for the Gowers norm was shown to be false for degrees ≥ 4 by Green and
Tao [9] and independently by Lovett, Meshulam, and Samorodnitsky [12]. A revised inverse conjecture
for the Gowers norm was proved by Bergelson, Tao and Ziegler [5, 17].
Additionally, Viola [18] proved the correctness of the construction of [7] without using the inverse
conjecture for the Gowers norm, or any other unproven conjectures, thus making the original construc-
tion of [7] unconditionally correct. His proof method also follows similar lines to the works of [7]
and [11]. He considers p(x + y), where x comes from a distribution which is pseudorandom against
degree-(d − 1) polynomials, and y is a small-bias generator (i. e., pseudorandom against linear polyno-
mials). He also uses a win-win analysis, based on the bias of the polynomial p, and proves that indeed
the sum x + y fools all degree-d polynomials.
The result presented here can thus be seen as an intermediate step in a sequence of works. The
proof of Viola uses some of the techniques developed in this work, in addition to some of the original
techniques introduced in [7] and some clever new ideas.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 72
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
2 Preliminaries
We work over an arbitrary finite field F. Let U = Un be the uniform distribution over Fn . We fix e : F → C
to be any non-trivial additive character. For example, in a prime field Fq we can have e(x) = ωqx where
2πi
ωq = 2 q is a root of unity of order q. When we refer to the degree of a multivariate polynomial, we
always mean its total degree. We denote elements of Fn by x = (x1 , . . . , xn ).
Definition 2.1. A distribution D over Fn is said to be pseudorandom against a polynomial p(x1 , . . . , xn )
with error ε if
Ex∈D e(p(x)) − Ex∈U e(p(x)) < ε .
Definition 2.2. A distribution D is said to be pseudorandom against degree-d polynomials with error ε
if for every degree-d polynomial p(x1 , . . . , xn ), D is pseudorandom against p with error ε.
We study explicit constructions for pseudorandom generators against degree-d polynomials.
Definition 2.3. A function G : {0, 1}r → Fn is said to be a pseudorandom-generator (PRG) against
degree-d polynomials if the distribution obtained by applying G to a uniform element in {0, 1}r is a
pseudorandom distribution against degree-d polynomials. The value in {0, 1}r is called the seed of G,
and r is the seed length of G.
The notion of pseudorandomness we use is different from more standard notions of pseudorandom-
ness. However, since we are working over small fields, they are tightly related. For example, the follow-
ing Lemma from [7] connects it with the common notion of pseudorandomness in statistical distance
(The proof in [7] is stated just for prime fields, but it remains correct over arbitrary fields):
Lemma 2.4 (Lemma 33 in [7]). Let D be a distribution that is pseudorandom against degree-d polyno-
mials with error ε. Let p(x1 , . . . , xn ) be a polynomial of degree at most d. Let p(D) be the distribution,
taking values in F, obtained by applying p to an input chosen according to D, and similarly p(U) be
n
the distribution of applying p to a uniformly pchosen input in F . Then the variation (statistical) distance
1
between p(D) and p(U) is bounded by 2 ε | F | − 1.
Remark 2.5. Definition 2.2 does not depend on which non-trivial character is used in Definition 2.1;
since we require pseudorandomness for all degree-d polynomials, we can multiply polynomials by any
non-zero constant, thus effectively achieving pseudorandomness for all non-trivial characters.
We use the Cauchy-Schwarz inequality over the complex numbers in the following form several
times in the proof.
Claim 2.6. Let Z be a random variable taking values in C, then
2
E[Z] ≤ E |Z|2 .
Fourier analysis plays a central role in our proof. In the following we define Fourier coefficients,
and discuss several properties of them required in the proof. We refer to the first chapter of [16] for a
more in-depth introduction to Fourier analysis.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 73
S HACHAR L OVETT
Definition 2.7. The Fourier coefficients of a function f : Fn → C are defined to be
fˆα = Ex∈U f (x)e(− hα, xi) ,
where α = (α1 , . . . , αn ) ∈ Fn and hα, xi = α1 x1 + · · · + αn xn is the inner product of α and x.
The set of functions {e(hα, xi) : α ∈ Fn } is an orthonormal basis of the Hermitian space of functions
Fn → C under the inner product
1
f · g = n ∑ f (x)g(x) .
| F | x∈Fn
Therefore f can be expressed as
f (x) = ∑ fˆα e(hα, xi) .
α∈Fn
For a polynomial p(x) ∈ F[x1 , . . . , xn ] we define p̂α to be the α Fourier coefficient of the function
e(p(x)), i. e.,
p̂α = Ex∈U e(p(x) − hα, xi) .
We will need the following simple fact, which follows from Parseval’s identity and the fact that
|e(p(x))| = 1 for all x ∈ Fn :
Fact 2.8. ∑ | p̂α |2 = 1.
α∈Fn
The basis elements of our analysis are PRGs for degree-1 polynomials. PRGs for this family have
been studied extensively, and are usually referred to as small-bias (or epsilon-biased) generators or
distributions. Formally we define:
Definition 2.9. A distribution D is called a small-bias distribution over Fn with error δ if for all linear
polynomials p(x) = a1 x1 + · · · + an xn we have
Ex∈D e(p(x)) − Ex∈U e(p(x)) < δ . (2.1)
Constructions of small-bias distributions were first studied by Naor and Naor over F2 in [14], and
optimal up to constant constructions were later given by Alon, Goldreich, Håstad, and Peralta [1] over
general fields. Such constructions can be achieved by explicit pseudorandom generators with seed length
O(log(| F |n/ε)).
3 Main theorem
We restate our main theorem with explicit constants:
d
Theorem 3.1. Let G : {0, 1}r → Fn be a small-bias generator over Fn with error (ε/10)4 . Then the
sum of 2d independent copies of G is pseudorandom against degree-d polynomials with error ε. That is,
d
G0 : {0, 1}r·2 → Fn defined as
G0 (x1 , . . . , x2d ) = G(x1 ) + . . . + G(x2d )
is a PRG against degree-d polynomials with error ε.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 74
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
Our proof is divided into two cases, based on whether p has some large Fourier coefficient, or does
not have any large Fourier coefficients. We show that when a degree-d polynomial p(x) has some large
Fourier coefficient, then a PRG for degree-(d − 1) polynomials, with better error, is also pseudorandom
against p. On the other hand, if p has no large Fourier coefficients, it is “pseudorandom” in a sense, and
then the sum of two PRGs for degree-(d − 1) is pseudorandom against p.
We divide the proof into two technical lemmas, dealing with the cases of whether p has some large
Fourier coefficient, or it does not.
Lemma 3.2. Let p(x1 , . . . , xn ) be a degree-d polynomial over Fn , such that for all α ∈ Fn , | p̂α | < ε 2 /10.
Let D be a distribution that is pseudorandom against degree-(d − 1) polynomials with error ε 4 /400.
Then x + y, where x, y are independently chosen from D, is pseudorandom against p with error ε.
Lemma 3.3. Let p(x1 , . . . , xn ) be a degree-d polynomial over Fn , such that | p̂α | ≥ ε 2 /10 for some
α ∈ Fn . Let D be a distribution that is pseudorandom against degree-(d − 1) polynomials with error
ε 3 /10. Then D is pseudorandom against p(x) with error ε.
Assuming these two lemmas, our main theorem now follows directly, by also using the following
simple observation. This observation allows us to add “extra” small-bias distributions without harming
our PRG construction.
Observation 3.4. Let D be a distribution that is pseudorandom against degree-d polynomials with error
ε. Let D0 be any other independent distribution. Then the distribution of x + y, where x ∈ D and y ∈ D0
is also pseudorandom against degree-d polynomials with error ε.
We now prove Theorem 3.1, assuming Lemmas 3.2 and 3.3 and Observation 3.4:
Proof. We prove, by induction on d, that the sum of 2d independent small-bias generators with error
d
(ε/10)4 is pseudorandom against degree-d polynomials with error ε. For d = 1 this is clear. For d > 1,
let D0 be the distribution of sum of the first 2d−1 small-bias generators, which is also the distribution of
the sum of the last 2d−1 small-bias generators. Observe that by the inductive hypothesis, D0 is pseudo-
random against degree-(d − 1) polynomials with error (ε/10)4 < min(ε 4 /400, ε 3 /10). Let p(x) be any
degree-d polynomial. Consider first the case that all the Fourier coefficients of p are at most ε 2 /10. By
Lemma 3.2, we know that the distribution of x + y, where x and y are chosen independently according
to D0 , is pseudorandom against p with error ε. Alternatively, consider the case that there exists some
Fourier coefficient of p of absolute value at least ε 2 /10. By Lemma 3.3, D0 is pseudorandom against p,
and by Observation 3.4 so is the distribution of x + y, where x and y are chosen independently according
to D0 .
The remainder of the paper is organized as follows: Lemma 3.2 is proven in Section 4 and Lemma 3.3
in Section 5.
4 Case I: No large Fourier coefficients
In this section we prove Lemma 3.2. We assume throughout this section that all the Fourier coefficients
of e(p(x)) are small, i. e., | p̂α | < ε 2 /10 for all α ∈ Fn .
We start by defining a derivation polynomial.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 75
S HACHAR L OVETT
Definition 4.1. Let p(x) : Fn → F be a polynomial. We define its derivation polynomial ∆p : (Fn )4 → F
as
∆p(x0 , x00 , y0 , y00 ) = p(x0 + y0 ) − p(x00 + y0 ) − p(x0 + y00 ) + p(x00 + y00 ) .
The following lemma is crucial to our analysis, and is a variation of a lemma proven in [7]. We
relate the distribution of evaluating p on the sum of two independent inputs to that of ∆p.
Lemma 4.2. Let p : Fn → F. Let D be a distribution over Fn . Let x, y be independently chosen from D,
then
4
Ex,y∈D [e(p(x + y))] ≤ Ex0 ,x00 ,y0 ,y00 ∈D [e(∆p(x0 , x00 , y0 , y00 ))] ,
where x0 , x00 , y0 , y00 are also independent.
Proof. The proof is essentially applying the Cauchy-Schwarz inequality twice. We start by showing
2
Ex,y∈D [e(p(x + y))] ≤ Ex,y0 ,y00 ∈D [e(p(x + y0 ) − p(x + y00 ))] ,
and then continue to show
4
Ex,y∈D [e(p(x + y))] ≤ Ex0 ,x00 ,y0 ,y00 ∈D [e(p(x0 + y0 ) − p(x00 + y0 ) − p(x0 + y00 ) + p(x00 + y00 ))] ,
which is what we want to prove, by the definition of ∆p. We prove the first part by applying the Cauchy-
Schwarz inequality
2 2
Ex,y∈D [e(p(x + y))] ≤ Ex∈D Ey∈D [e(p(x + y))] =
h i
Ex∈D Ey0 ∈D [e(p(x + y0 ))] Ey00 ∈D [e(p(x + y00 ))] =
Ex,y0 ,y00 ∈D [e(p(x + y0 ) − p(x + y00 ))] .
We prove the second part by applying the Cauchy-Schwarz inequality again
4
Ex,y∈D [e(p(x + y))] ≤
2
Ex,y0 ,y00 ∈D [e(p(x + y0 ) − p(x + y00 ))] ≤
2
Ey0 ,y00 ∈D Ex∈D [e(p(x + y0 ) − p(x + y00 ))] =
Ex0 ,x00 ,y0 ,y00 ∈D e(p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 )) .
In particular the following corollary follows:
Corollary 4.3. Ex0 ,x00 ,y0 ,y00 ∈D e(∆p(x0 , x00 , y0 , y00 )) ≥ 0 .
We analyze the expression Ex0 ,x00 ,y0 ,y00 ∈D e(∆p(x0 , x00 , y0 , y00 )) , in two cases: when D = U is the uni-
form distribution and when D is a PRG for degree-(d − 1) polynomials. We show that in both cases it
is at most ε/2. Combining this with Lemma 4.2 yields the required result. We start our analysis in the
uniform case.
We begin by showing the (well-known) connection between the average value of ∆p and the Fourier
coefficients of p, regarding ∆p as an affinity-test for p. A similar analysis, carried in more depth, can be
found in [3].
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 76
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
Lemma 4.4.
Ex0 ,x00 ,y0 ,y00 ∈U e(p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 )) = ∑ | p̂α |4 .
α∈Fn
Proof. We can write e(p(x)) in the Fourier basis as
e(p(x)) = ∑ p̂α e(hα, xi) .
α∈Fn
Notice that
e(−p(x)) = e(p(x)) = ∑ p̂α e(− hα, xi) .
α∈Fn
We now expand all four terms of p in
e(p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 )) .
This is equal to
∑ p̂α 1 e( α 1 , x0 + y0 ) p̂α 2 e(− α 2 , x0 + y00 ) p̂α 3 e(− α 3 , x00 + y0 ) p̂α 4 e( α 4 , x00 + y00 ) .
n
α 1 ,α 2 ,α 3 ,α 4 ∈F
Remember that we are interested in the expected value over uniform x0 , x00 , y0 , y00 ∈ Fn , i. e., in
Ex0 ,x00 ,y0 ,y00 ∈U e(p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 )) .
We now use the Fourier expansion and group elements by their related values. After doing so, the
above expectation is equal to
p̂α 1 p̂α 2 p̂α 3 p̂α 4 Ex0 ∈U e( α 1 − α 2 , x0 ) Ex00 ∈U e( α 4 − α 3 , x00 )
∑
α 1 ,α 2 ,α 3 ,α 4 ∈Fn
Ey0 ∈U e( α 1 − α 3 , y0 ) Ey00 ∈U e( α 4 − α 2 , y00 ) .
The term inside the sum for α 1 , . . . , α 4 is zero unless α 1 = α 2 = α 3 = α 4 = α, and in that case its
contribution is | p̂α |4 . This finishes the proof of the lemma.
We now use this relation between ∆p and the Fourier coefficients of p to show that the expected
value of ∆p is small.
Lemma 4.5. Ex0 ,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) < ε 4 /100.
Proof. We use Lemma 4.4. We have
Ex0 ,x00 ,y0 ,y00 ∈U e(p(x0 + y0 ) − p(x0 + y00 ) − p(x00 + y0 ) + p(x00 + y00 )) = ∑ | p̂α |4 .
α∈Fn
We now combine the fact that ∑α∈Fn | p̂α |2 = 1 and our assumption that | p̂α | < ε 2 /10 for all α ∈ Fn , to
yield the required bound.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 77
S HACHAR L OVETT
Combining Lemmas 4.2 and 4.5 we get that
1/4
ε4
ε
Ex,y∈U [e(p(x + y))] < < .
100 2
We now move on to handle the pseudorandom case. We start with the following observation:
Observation 4.6. The polynomial ∆p(x0 , x00 , y0 , y00 ) has total degree-d, but has no degree-d terms which
have variables from only one of x0 , x00 , y0 , y00 . Therefore, the total degree of variables from x0 in each
term is at most d − 1. The same is true for also x00 , y0 and y00 .
We now show that if D is a distribution that is pseudorandom against degree-(d − 1) polynomials,
then it is also pseudorandom against ∆p. We use a hybrid argument similar to the one in [7].
Lemma 4.7. Let D be a distribution that is pseudorandom against degree-(d − 1) polynomials with
error δ . Then
Ex0 ,x00 ,y0 ,y00 ∈D e(∆p(x0 , x00 , y0 , y00 )) − Ex0 ,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) < 4δ .
Proof. We change the inputs x0 , x00 , y0 and y00 from U to D, one at a time. We prove that the expected
value of e(∆p) changes by at most δ in each step, accumulating to a total of at most 4δ . Formally, let
Hk (k = 0, . . . , 4) be the joint distribution of x0 , x00 , y0 , y00 , when the first k are taken from D and the last
4 − k are taken from U. For example, H1 is the distribution where x0 ∈ D and x00 , y0 , y00 ∈ U, where x0 ,
x00 , y0 , y00 are independent.
We prove that the distance between e(∆p) under Hk−1 and Hk is at most δ , for all k = 1, 2, 3, 4. For
the sake of clarity, we focus on the proof for k = 1. The proof for the other three cases is essentially
identical.
For k = 1, we want to show that
Ex0 ,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) − Ex0 ∈D,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) < δ .
The joint distribution of x00 , y0 , y00 is identical in both terms, so we have
Ex0 ,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) − Ex0 ∈D,x00 ,y0 ,y00 ∈U e(∆p(x0 , x00 , y0 , y00 )) ≤
Ex00 ,y0 ,y00 ∈U Ex0 ∈U e(∆p(x0 , x00 , y0 , y00 )) − Ex0 ∈D e(∆p(x0 , x00 , y0 , y00 )) .
Now, for any fixing of values for x00 = a, y0 = b, y00 = c, ∆p(x0 , a, b, c) is a polynomial just in x0 .
Observation 4.6 tells us that it is a polynomial of degree at most d − 1. Since D is pseudorandom against
degree-(d − 1) polynomials, the inequality follows for every fixing of x00 , y0 , y00 . Hence, it also follows
for the expected value.
If we take D to be a PRG against degree-(d − 1) polynomials with error ε 4 /400 and combine this
with Lemmas 4.2 and 4.5, we get that
ε4 ε4 ε4
Ex0 ,x00 ,y0 ,y00 ∈D e(∆p(x0 , x00 , y0 , y00 )) <
+4 = ,
100 400 50
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 78
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
and so using Lemma 4.2 we get that
ε 4 1/4 ε
Ex,y∈D [e(p(x + y))] < < .
50 2
This finishes the proof of Lemma 3.2.
5 Case II: Some large Fourier coefficient exists
In this section we prove Lemma 3.3. We assume throughout this section that p has some large Fourier
coefficient. To be precise, there exists some α ∈ Fn such that
ε2
| p̂α | ≥ .
10
Let `(x) be the corresponding linear function, i. e., `(x) = hx, αi. Define
η = p̂α = Ex∈U e(`(x) − p(x)) .
η is a measure for the approximation of p(x) by `(x). By our assumption on p̂α , we know that |η| ≥
ε 2 /10. For any constant a ∈ Fn define the polynomial
qa (x) = p(x) − p(x + a) + `(x + a) .
Notice that qa (x) has degree at most d − 1, because `(x + a) is linear (and so of degree less than d), and
the degree-d terms in p(x) and p(x + a) cancel out.
We can think of qa (x) as using `(x), which approximates p(x) non-uniformly, and the derivative of
p(x) in a random direction a, to build a random degree-(d − 1) polynomial which approximates p(x)
uniformly. In order to show this formally, we define
1
νx (a) = e(qa (x)) ,
η
and prove that νx (a), taken on a random a ∈ Fn value, is exactly e(p(x)).
Lemma 5.1. For every x ∈ Fn , Ea∈U [νx (a)] = e(p(x)).
Proof. Ea∈U [νx (a)] = η1 e(p(x)) Ea∈U [e(`(x + a) − p(x + a))] = e(p(x)).
Effectively, we have shown that p(x) can be approximated uniformly by a (random) degree-(d − 1)
polynomial qa (x). We can now use this to show that a distribution that is pseudorandom against degree-
(d − 1) polynomials is also pseudorandom against p. First, we prove the following lemma:
Lemma 5.2. Let D be a distribution that is pseudorandom against degree-(d − 1) polynomials with
error δ . For every a ∈ Fn
δ
Ex∈D [νx (a)] − Ex∈U [νx (a)] < .
|η|
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 79
S HACHAR L OVETT
Proof. We have
1 δ
Ex∈D [νx (a)] − Ex∈U [νx (a)] = Ex∈D [e(qa (x))] − Ex∈U [e(qa (x))] < ,
|η| |η|
where we use the fact that qa is a polynomial of degree at most d − 1 and so D is pseudorandom against
qa with error δ .
We now conclude by proving Lemma 3.3.
Proof of Lemma 3.3. Let D be a distribution that is pseudorandom against degree-(d − 1) polynomials
with error ε 3 /10. Then
Ex∈D [e(p(x))] − Ex∈U [e(p(x))] = Ex∈D Ea∈U [νx (a)] − Ex∈U Ea∈U [νx (a)]
ε 3 /10
≤ Ea∈U Ex∈D [νx (a)] − Ex∈U [νx (a)] < ≤ε.
|η|
Acknowledgements I thank my supervisor, Omer Reingold, for his constant interest and encourage-
ment. I thank Andrej Bogdanov and Emanuele Viola for making an early version of their paper available
and for insightful comments. In particular I thank Bogdanov for an observation that somewhat simplifies
the analysis in the case where all the Fourier coefficients are small, which allowed the reduction of the
number of small-bias terms from 3d to 2d . I thank Zeev Dvir, Dana Moshkovitz and Ariel Gabizon for
helpful discussions. I also thank the anonymous reviewers for their useful comments.
References
[1] N. A LON , O. G OLDREICH , J. H ÅSTAD , AND R. P ERALTA: Simple construction of almost
k-wise independent random variables. Random Structures Algorithms, 3(3):289–304, 1992.
[doi:10.1002/rsa.3240030308]. 70, 74
[2] N. A LON , T. K AUFMAN , M. K RIVELEVICH , S. L ITSYN , AND D. RON: Testing low-degree
polynomials over GF(2). In RANDOM-APPROX 2003, volume 2764 of Lecture Notes in Computer
Science, pp. 188–199. Springer, 2003. [doi:10.1007/b11961]. 71
[3] M. B ELLARE , D. C OPPERSMITH , J. H ÅSTAD , M. K IWI , AND M. S UDAN: Linearity testing in
characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. [doi:10.1109/18.556674].
71, 76
[4] E. B EN -S ASSON , M. S UDAN , S. VADHAN , AND A. W IGDERSON: Randomness-efficient low
degree tests and short PCPs via epsilon-biased sets. In Proc. 35th STOC, pp. 612–621. ACM Press,
2003. [doi:10.1145/780542.780631]. 70
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 80
U NCONDITIONAL P SEUDORANDOM G ENERATORS FOR L OW-D EGREE P OLYNOMIALS
[5] V. B ERGELSON , T. TAO , AND T. Z IEGLER: An inverse theorem for the uniformity seminorms
associated with the action of F∞p , 2009. [arXiv:0901.2602]. 72
[6] A. B OGDANOV: Pseudorandom generators for low degree polynomials. In Proc. 37th STOC, pp.
21–30. ACM Press, 2005. [doi:10.1145/1060590.1060594]. 70
[7] A. B OGDANOV AND E. V IOLA: Pseudorandom bits for polynomials. In Proc. 48th FOCS, pp.
41–51. IEEE Comp. Soc. Press, 2007. [doi:10.1109/FOCS.2007.42]. 70, 71, 72, 73, 76, 78
[8] W. T. G OWERS: A new proof of Szemerédi’s theorem. Geom. Funct. Anal., 11(3):465–588, 2001.
[doi:10.1007/s00039-001-0332-9]. 71
[9] B. G REEN AND T. TAO: The distribution of polynomials over finite fields, with applications to the
Gowers norms, 2007. [arXiv:0711.3191]. 72
[10] B. G REEN AND T. TAO: An inverse theorem for the Gowers U 3 (G) norm. Proc. Edinburgh Math.
Soc. (Ser. 2), 51(1):73–153, 2008. [doi:10.1017/S0013091505000325]. 71
[11] S. L OVETT: Unconditional pseudorandom generators for low degree polynomials. In Proc. 40th
STOC, pp. 557–562. ACM Press, 2008. [doi:10.1145/1374376.1374455]. 70, 72
[12] S. L OVETT, R. M ESHULAM , AND A. S AMORODNITSKY: Inverse conjecture for the Gowers norm
is false. In Proc. 40th STOC, pp. 547–556. ACM Press, 2008. [doi:10.1145/1374376.1374454].
72
[13] M. L UBY, B. V ELICKOVIC , AND A. W IGDERSON: Deterministic approximate counting of depth-
2 circuits. In Proc. of the 2nd Israeli Symposium on Theoretical Computer Science (ISTCS’93), pp.
18–24. IEEE Comp. Soc. Press, 1993. 70
[14] J. NAOR AND M. NAOR: Small-bias probability spaces: Efficient constructions and applications.
In Proc. 22nd STOC, pp. 213–223. ACM Press, 1990. [doi:10.1145/100216.100244]. 70, 74
[15] A. S AMORODNITSKY: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506–515.
ACM Press, 2007. [doi:10.1145/1250790.1250864]. 71
[16] D. Š TEFANKOVI Č: Fourier transforms in computer science. Master’s thesis, University of Chicago,
Department of Computer Science, 2000. http://www.cs.rochester.edu/∼stefanko/
Publications/Fourier.ps. 73
[17] T. TAO AND T. Z IEGLER: The inverse conjecture for the Gowers norm over finite fields via the
correspondence principle, 2008. [arXiv:0810.5527]. 72
[18] E. V IOLA: The sum of d small-bias generators fools polynomials of degree d. In Proc. 23rd
IEEE Conf. on Computational Complexity (CCC), pp. 124–127. IEEE Comp. Soc. Press, 2008.
[doi:10.1109/CCC.2008.16]. 72
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 81
S HACHAR L OVETT
AUTHOR
Shachar Lovett
graduate student
Weizmann Institute of Science
Rehovot 76100, Israel
shachar.lovett gmail com
www.wisdom.weizmann.ac.il/∼shalov
ABOUT THE AUTHOR
S HACHAR L OVETT is a Ph. D. student at the Weizmann Institute of Science under the guid-
ance of Omer Reingold. His research interests include pseudorandomness, explicit con-
structions, and polynomials over finite fields.
T HEORY OF C OMPUTING, Volume 5 (2009), pp. 69–82 82