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 +
for all h ∈ V ; averaging in V we conclude that
|Ex∈V e(ψ −
= 1 +
e(ψ) − e(Φ)
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
∂h1 . . . ∂hd+1 φ2(x) = 0
hold; note that one only has to inspect φ1,φ2 at
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 δ
ε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
≥ 1 − O(δ), and thus by Proposition 1.5.1, φ2 is very close
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.