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 aﬃne 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 aﬃne 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 suﬃce to build a func-

tion which is almost orthogonal to the symmetric polynomials S0,...,Sd on

all aﬃne 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 suﬃce 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.