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 coefficient of L, and conclude that Sm is a function
of L mod
2j1
.
We define an an affine 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 affine 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 affine
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.
Previous Page Next Page