1.5. Inverse conjecture over finite fields 81
Proof. We induct on d. The claim is trivial for d = 0, so suppose that
d 1 and the claim has already been proven for smaller d. The degree d
term Pd of P can be written as
Pd =
{i1,...,id}∈E
xi1 . . . xid
where E is a d-uniform hypergraph on {1,...,n}, i.e., a collection of d-
element subsets of {1,...,n}. Applying Ramsey’s theorem for hypergraphs
(see e.g. [GrRoSp1980] or [Ta2009, §2.6]), one can find a subcollection
j1,...,jm of indices with m ωd(n) such that E either has no edges in
{j1,...,jm}, or else contains all the edges in {j1,...,jm}. We then foliate
Fn
into the affine subspaces formed by translating the coordinate subspace
generated by ej1 , . . . , ejm . By construction, we see that on each such sub-
space, P is equal to either 0 or Sd plus a polynomial of degree d 1. The
claim then follows by applying the induction hypothesis (and noting that the
linear span of S0,...,Sd−1 on an affine coordinate subspace is equivariant
with respect to translation of that subspace).
Because of this, if one wants to concoct a function which is almost or-
thogonal to all polynomials of degree at most d, it will suffice to build a func-
tion which is almost orthogonal to the symmetric polynomials S0,...,Sd on
all affine coordinate subspaces of moderately large size. Pursuing this idea,
we are led to
Proposition 1.5.6 (Counterexample to classical inverse conjecture). Let
d 1, and let f : F2
n

S1
be the function f :=
e(L/2d),
where L is as in
Exercise 1.5.4. Then
L/2d
mod 1 is a non-classical polynomial of degree at
most d, and so f
Ud+1(F2
n)
= 1; but one has
f, e(φ)
L2(F2
n)
= on→∞;d(1)
uniformly for all classical polynomials φ of degree less than
2d−1,
where
on→∞;d(1) is bounded in magnitude by a quantity that goes to zero as n
for each fixed d.
Proof. We first prove the polynomiality of
L/2d
mod 1. Let x |x| be the
obvious map from F2 to {0, 1}, thus
L =
n
i=1
|xi|.
By linearity, it will suffice to show that each function |xi| mod
2d
is a poly-
nomial of degree at most d. But one easily verifies that for any h F2
n,
∂h|xi| is equal to zero when hi = 0 and equal to 1 2|xi| when hi = 1.
Iterating this observation d times, we obtain the claim.
Previous Page Next Page