1.5. Inverse conjecture over finite fields 79

We may thus integrate φh and write φh = ∂hΦ, where Φ(x) := φx(0). Thus

∂hΦ is a polynomial of degree d − 1 for each h, thus Φ itself is a polynomial

of degree d. From (1.42) one has

Ex∈V e(∂h(ψ − Φ)) = 1 +

O(εc)

for all h ∈ V ; averaging in V we conclude that

|Ex∈V e(ψ −

Φ)|2

= 1 +

O(εc)

and thus

e(ψ) − e(Φ)

L1(V

)

=

O(εc)

and Proposition 1.5.1 follows.

One consequence of Proposition 1.5.1 is that the property of being a

classical polynomial of a fixed degree d is locally testable, which is a notion

of interest in theoretical computer science. More precisely, suppose one is

given a large finite vector space V and two functions φ1,φ2 : V → F. One

is told that one of the functions φ1,φ2 is a classical polynomial of degree at

most d, while the other is quite far from being such a classical polynomial,

in the sense that every polynomial of degree at most d will differ with that

polynomial on at least ε of the values in V . The task is then to decide with

a high degree of confidence which of the functions is a polynomial and which

one is not, without inspecting too many of the values of φ1 or φ2.

This can be done as follows. Pick x, h1,...,hd+1 ∈ V at random, and

test whether the identities

∂h1 . . . ∂hd+1 φ1(x) = 0

and

∂h1 . . . ∂hd+1 φ2(x) = 0

hold; note that one only has to inspect φ1,φ2 at

2d+1

values in V for this.

If one of these identities fails, then that function must not be polynomial,

and so one has successfully decided which of the functions is polynomials.

We claim that the probability that the identity fails for the non-polynomial

function is at least δ for some δ

d,F

εOd,F(1), and so if one iterates this

test Oδ(1) times, one will be able to successfully solve the problem with

probability arbitrarily close to 1.

To verify the claim, suppose for contradiction that the identity only

failed at most δ of the time for the non-polynomial (say it is φ2); then

e(φ2)

Ud+1(V )

≥ 1 − O(δ), and thus by Proposition 1.5.1, φ2 is very close

in

L1

norm to a polynomial; rounding that polynomial to a root of unity we

thus see that φ2 agrees with high accuracy to a classical polynomial, which

leads to a contradiction if δ is chosen suitably.