1.4. Equidistribution in finite fields 67
To conclude the proof of Theorem 1.4.4 from Lemma 1.4.5, it thus suffices
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 sufficiently 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
Previous Page Next Page