1.4. Equidistribution in finite fields 67

To conclude the proof of Theorem 1.4.4 from Lemma 1.4.5, it thus suﬃces

to show

Proposition 1.4.6 (Rigidity). Let P : V → F be a limit polynomial of

degree d which is equal to a limit function Q: V → F of order d on at

least 1 − ε of V , where ε 0 is standard. If ε is suﬃciently small with

respect to d, then P is also of order d.

This proposition is somewhat tricky to prove, even in the high character-

istic case p d. We fix d p and assume inductively that the proposition

(and hence) Theorem 1.4.4 has been demonstrated for all smaller values of

d.

The main idea here is to start with the “noisy polynomial” Q, and per-

form some sort of “error correction” on Q to recover P ; the key is then to

show that this error correction procedure preserves the property of being

order d. From Exercise 1.4.14 we know that in principle, this error cor-

rection is possible if ε is small enough; but in order to preserve the order

d property we need a more explicit error correction algorithm which is

tractable for analysis. This is provided by the following lemma.

Lemma 1.4.7 (Error correction of polynomials). Let P : V → F be a (limit)

classical polynomial of degree at most d, and let Q: V → F be a (limit) func-

tion which agrees with P at least 1−ε of the time for some ε ≤

2−d−2.

Then

for every x ∈ V , P (x) is equal to the most common value (i.e., the mode) of

∑

ω∈{0,1}d+1\{0}

(−1)|ω|−1Q(x

+ ω1h1 + · · · + ωd+1hd+1) as h1,...,hd+1 vary

in V .

Proof. As P is a polynomial of degree at most d, one has

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

for all x, h1,...,hd+1 ∈ V . We rearrange this as

P (x) =

ω∈{0,1}d+1\{0}

(−1)|ω|−1P

(x + ω1h1 + · · · + ωd+1hd+1).

We conclude that

(1.37) P (x) =

ω∈{0,1}d+1\{0}

(−1)|ω|−1Q(x

+ ω1h1 + · · · + ωd+1hd+1ωd+1)

holds unless P and Q differ at x + h1ω1 + · · · + hd+1ωd+1 for some ω ∈

{0,

1}d+1\{0}.

On the other hand, if x is fixed and h1,...,hd+1 are chosen indepen-

dently and uniformly at random from V , then for each ω ∈ {0,

1}d+1\{0},

x + h1ω1 + · · · + hd+1ωd+1 is also uniformly distributed in V , and so the

probability that P and Q differ at x + h1ω1 + · · · + hd+1ωd+1 is at most