80 1. Higher order Fourier analysis

1.5.2. A partial counterexample in low characteristic. We now show

a distinction between classical polynomials and non-classical polynomials

that causes the inverse conjecture to fail in low characteristic if one insists

on using classical polynomials. For simplicity we restrict attention to the

characteristic two case F = F2. We will use an argument of Alon and

Beigel [AlBe2001], reproduced in [GrTa2009]. A different argument (with

stronger bounds) appeared independently in [LoMeSa2008].

We work in a standard vector space V =

Fn,

with standard basis

e1,...,en and coordinates x1,...,xn. Among all the classical polynomials

on this space are the symmetric polynomials

Sm :=

1≤i1 ···im≤n

xi1 . . . xim ,

which play a special role.

Exercise 1.5.4. Let L: V → N be the digit summation function L :=

#{1 ≤ i ≤ n : xi = 1}. Show that

Sm =

L

m

mod 2.

Establish Lucas’

theorem13

Sm = S2j1 . . . S2jr

where m =

2j1

+ · · · +

2jr

, j1 · · · jr is the binary expansion of m. Show

that S2j is the

2j

binary coeﬃcient of L, and conclude that Sm is a function

of L mod

2j1

.

We define an an aﬃne coordinate subspace to be a translate of a subspace

of V generated by some subset of the standard basis vectors e1,...,en. To

put it another way, an aﬃne coordinate subspace is created by freezing some

of the coordinates, but letting some other coordinates be arbitrary.

Of course, not all classical polynomials come from symmetric polyno-

mials. However, thanks to an application of Ramsey’s theorem observed in

[AlBe2001], this is true on coordinate subspaces:

Lemma 1.5.5 (Ramsey’s theorem for polynomials). Let P :

Fn

→ F be

a polynomial of degree at most d. Then one can partition

Fn

into aﬃne

coordinate subspaces of dimension W at least ωd(n), where ωd(n) → ∞ as

n → ∞ for fixed d, such that on each such subspace W , P is equal to a

linear combination of the symmetric polynomials S0,S1,...,Sd.

13These results are closely related to the well-known fact that Pascal’s triangle modulo 2

takes the form of an infinite Sierpinski gasket.