The polynomial method in combinatorics

Larry Guth

AMS joint meetings

4 January 2012

Larry Guth The polynomial method in combinatorics

Overview

In the last five years, several challenging problems in

combinatorics have been solved by introducing polynomials
into the problem in an unexpected way.

This approach is based on work in computer science. The main

idea comes from certain algorithms for solving problems about
polynomials.

The idea from these algorithms was then applied to other

combinatorial problems which have no obvious connection to
polynomials.

Larry Guth The polynomial method in combinatorics

The polynomial method in outline

1. Begin with a problem about some points in a vector space.

2. Find a polynomial of lowest possible degree that vanishes on

the points.

3. Use this polynomial to attack the problem.

Larry Guth The polynomial method in combinatorics

Finding polynomials with prescribed zeroes is just linear
algebra

Let F be a field.
Let p1 , ..., ps be points in Fn .

Question: Is there a non-zero polynomial of degree ≤ d that

vanishes at all the points p1 , ..., ps ?

This question is really just a linear algebra problem.

Larry Guth The polynomial method in combinatorics

Finding polynomials with prescribed zeroes is just linear
algebra
F a field. p1 , ..., ps ∈ Fn .

Let V (d) be the vector space of all polynomials in n variables

with degree ≤ d.

For example, if n = 2, then V (1) = {ax1 + bx2 + c|a, b, c ∈ F}.

Let E : V (d) → Fs be the evaluation map

E (Q) := (Q(p1 ), ..., Q(ps )) .

The map E is linear!
Lemma
There is a non-zero polynomial of degree ≤ d that vanishes at all
points if and only if E has a non-trivial kernel.

Larry Guth The polynomial method in combinatorics

Finding the lowest degree polynomial that vanishes at
prescribed points

Theorem
If p1 , ..., ps ∈ Fn , we can efficiently find a lowest degree non-zero
polynomial Q that vanishes at each pj .

Proof sketch. Check if there is a degree 1 polynomial that

vanishes at the points. Then check for a degree 2 polynomial...
Remarks.
The degree of Q is at most s, the number of points. But we
will give a much better estimate later.
Q will probably not be unique, but we can find one such
polynomial.
Intuition: This process finds the “algebraic structure” in the
given set of points.

Larry Guth The polynomial method in combinatorics

The first problem: recovering polynomials from corrupted
data

Let F be a finite field with q elements. (q large)

Suppose that P(x) is a polynomial over F with degree
d ≤ q 1/3 .
Suppose that F (x) is a function that agrees with P(x) for at
least (51/100)q values of x.

We are given the function F (x).

We want an efficient algorithm to recover P.

Larry Guth The polynomial method in combinatorics

Some basic facts about polynomials

Lemma
A non-zero polynomial of degree ≤ d in one variable has at most d
zeroes.

Corollary
If P and Q are polynomials of degree ≤ d in one variable, then
either
P(x) = Q(x) for ≤ d values of x.
P = Q.

Proof.
Consider P1 − P2 . Either P1 − P2 has ≤ d zeroes, or P1 − P2 = 0.

Larry Guth The polynomial method in combinatorics

There’s only one polynomial that fits the data

Review. F a finite field with q elements.

P(x) a polynomial of degree ≤ q 1/3 .
F (x) = P(x) for ≥ (51/100)q values of x.
We are given F , and we want to find P.

Lemma
If q > 104 , there is only one polynomial of degree ≤ q 1/3 that
agrees with F for at least (51/100)q values of x.

Proof.
Suppose Q has degree ≤ q 1/3 , Q(x) = F (x) for ≥ (51/100)q
values of x.
Then Q(x) = P(x) for at least (2/100)q values of x. But
(2/100)q > q 1/3 . So Q = P.

Larry Guth The polynomial method in combinatorics

The Berlekamp-Welch algorithm

Review. F a finite field with q elements.

P(x) a polynomial of degree ≤ q 1/3 .
F (x) = P(x) for ≥ (51/100)q values of x.
We are given F , and we want to find P.

Theorem
(Berlekamp-Welch, 1986) There is an efficient algorithm to recover
P from F . (The algorithm runs in polynomial time.)

Larry Guth The polynomial method in combinatorics

Recovering from 99 % corrupted data!

F is still a finite field with q elements, and P(x) is still a

polynomial of degree ≤ q 1/3 .
This time suppose F (x) = P(x) for ≥ q/100 values of x.

Question: Given F , can we recover P?

Issue: P may not be unique! There may be two polynomials of

degree ≤ q 1/3 that agree with F on at least q/100 values of x.

Theorem
(Sudan, 1997) There is a polynomial-time algorithm that lists all
the polynomials of degree ≤ q 1/3 which agree with F for ≥ q/100
values of x.

Larry Guth The polynomial method in combinatorics

The idea of the algorithm

Review. F a finite field with q elements.

P(x) a polynomial of degree ≤ q 1/3 .
F (x) = P(x) for ≥ (1/100)q values of x.
We are given F , and we want to find P.

Let G ⊂ F2 be the graph of F . G := {(x, F (x))|x ∈ F}.

Let Q(x, y ) be a non-zero polynomial that vanishes on G , of
minimal degree.

As we saw above, we can find Q efficiently!

Larry Guth The polynomial method in combinatorics

The idea of the algorithm 2
Review. F a finite field with q elements.
P(x) a polynomial of degree ≤ q 1/3 .
F (x) = P(x) for ≥ (1/100)q values of x.
We are given F , and we want to find P.
G ⊂ F2 the graph of F .
Q(x, y ) a non-zero polynomial that vanishes on G , of minimal
degree.

Let P1 , ..., PN be all the polynomials of degree ≤ q 1/3 that

agree with F for at least q/100 values of x. It turns out that
The graph of each Pi is contained in the zero-set of Q.
The polynomial y − Pi (x) divides the polynomial Q(x, y ) (for
each i).
So we can find all the Pi by factoring Q(x, y ) into irreducible
factors.
Larry Guth The polynomial method in combinatorics
Pictures of reconstructing polynomials from corrupted data

We begin with a low-degree polynomial P.

Here is the graph of P. Next the data will be corrupted.

Larry Guth The polynomial method in combinatorics

Pictures of reconstructing polynomials from corrupted data

Then the polynomial P gets corrupted. Some of the values are

changed, and the resulting function is called F .

Here is the graph of F . We don’t know which values of F are

right and which are wrong.

Larry Guth The polynomial method in combinatorics

Pictures of reconstructing polynomials from corrupted data

We don’t know which values of P were changed and which

remain the same. This is the information we are given.

We want to recover the polynomial P from this graph.

We start by finding a lowest-degree polynomial Q(x, y ) that
vanishes on the graph.

Larry Guth The polynomial method in combinatorics

Pictures of reconstructing polynomials from corrupted data

We find the lowest degree polynomial Q(x, y ) that vanishes on

the graph of F . Here is the zero set of Q.

Of course, it contains the graph of F . But it also contains the

graph of P!

Larry Guth The polynomial method in combinatorics

Pictures of reconstructing polynomials from corrupted data

Finally, we factor Q into irreducible factors. The zero-set of Q

gets divided into irreducible varieties, one for each factor.

One of the irreducible pieces is the graph of P.

Larry Guth The polynomial method in combinatorics
The polynomial method in outline: recovering polynomials
from corrupted data

1. Begin with a problem about some points in a vector space.

Given F which agrees with P for at least 51 % (or 1 %) of
values of x. We want to find P.
We consider the graph of F , G ⊂ F2 .

2. Find a polynomial of low degree that vanishes on the points.

Let Q(x, y ) be a non-zero polynomial of lowest degree that
vanishes on G .

3. Use this polynomial to attack the problem.

The zero set of Q contains the graph of P.
Moreover, y − P(x) divides Q(x, y ).

Larry Guth The polynomial method in combinatorics

Other kinds of problems

Next we will turn to a problem coming from geometry.

The problem is about points and lines. It does not have any
obvious connection to polynomials.
Nevertheless, we will attack it with the polynomial method.

Larry Guth The polynomial method in combinatorics

A problem from geometry
A set N ⊂ [0, 1]n is called a Nikodym set if, for each
x ∈ [0, 1]n , there is a line segment Lx with boundary points on
the edge of the cube so that
Lx contains x
Lx \ {x} ⊂ N.

In the figure, the circle denotes x and the line denotes Lx .

Larry Guth The polynomial method in combinatorics
Nikodym sets
Review. A set N ⊂ [0, 1]n is called a Nikodym set if, for each
x ∈ [0, 1]n , there is a line segment Lx with boundary points on
the edge of the cube so that Lx contains x and Lx \ {x} ⊂ N.

It may seem intuitive that a Nikodym set should fill up most of

the cube.
Larry Guth The polynomial method in combinatorics
The strange example of Besicovitch and Nikodym
Review. A set N ⊂ [0, 1]n is called a Nikodym set if, for each
x ∈ [0, 1]n , there is a line segment Lx with boundary points on
the edge of the cube so that Lx contains x and Lx \ {x} ⊂ N.

In the 20’s, Besicovitch and Nikodym gave a surprising

construction of a Nikodym set in [0, 1]2 with measure 0!
Larry Guth The polynomial method in combinatorics
The Nikodym conjecture

Although Nikodym sets can have measure 0, they still seem to

be pretty large. Each known example has full Hausdorff
dimension.
The Nikodym conjecture
Each Nikodym set in [0, 1]n has Hausdorff dimension n.

The Nikodym conjecture is true if n = 2.

For n ≥ 3, the Nikodym conjecture is a major open problem in
geometry and harmonic analysis.
Best current estimate: a Nikodym set in [0, 1]3 has dimension
≥ 5/2.

Larry Guth The polynomial method in combinatorics

Nikodym sets in finite fields

There is an analogous problem in finite fields, first posed by

Wolff in the mid-90’s.

Let F be a finite field with q elements.

A set N ⊂ Fn is called a Nikodym set if for each x ∈ Fn , there
is an (affine) line Lx so that
The line Lx contains x.
Lx \ {x} ⊂ N.
Question: What is the smallest possible number of elements of
a Nikodym set N ⊂ Fn ?

Larry Guth The polynomial method in combinatorics

The finite-field Nikodym conjecture

Review. F a finite field with q elements.

A set N ⊂ Fn is called a Nikodym set if for each x ∈ Fn , there
is a line Lx so that Lx contains x and Lx \ {x} ⊂ N.

Theorem
(Dvir 2007) Each Nikodym set N ⊂ Fn has at least cn q n elements.

Theorem
(special case) Each Nikodym set N ⊂ F3 has at least (1/30)q 3
elements.
Morally, Nikodym sets in finite fields have full dimension!
Although the result was expected to be true, many harmonic
analysts were shocked by the short proof.

Larry Guth The polynomial method in combinatorics

Polynomials that vanish on the Nikodym set

Theorem
(special case) Each Nikodym set N ⊂ F3 has at least (1/30)q 3
elements.
Review. F a finite field with q elements.
A set N ⊂ Fn is called a Nikodym set if for each x ∈ Fn , there
is a line Lx so that Lx contains x and Lx \ {x} ⊂ N.

In the proof, we’re going to look at a lowest degree polynomial

that vanishes on N.

Question: How big is the degree of this polynomial?

Larry Guth The polynomial method in combinatorics

Tool 1. The polynomial existence lemma

Polynomial existence lemma

If p1 , ..., ps ∈ F3 , then there is a non-zero polynomial Q of degree
≤ 2s 1/3 that vanishes on all the points pj .

Proof. Let V (d) be the vector space of polynomials in three

variables of degree at most d.
Let E : V (d) → Fs be the evaluation map:

E (Q) := (Q(p1 ), ..., Q(ps )) .

The map E is linear. If the dimension of the domain is larger
than the dimension of the range, then E has a non-trivial
kernel.
The dimension of V (d) is d+3 ≥ d 3 /6. If d is close to 2s 1/3 ,


3
dim V (d) ∼ (8/6)s > s.

Larry Guth The polynomial method in combinatorics

Comparison with a naive construction

Suppose p1 , ..., ps ∈ F3 .
Our method gives the following:
Polynomial existence lemma
There is a non-zero polynomial Q that vanishes at each pj with
degree ≤ 2s 1/3 .

Here is a naive method.

Let Lj be a linear polynomial that vanishes at pj . Then
Q s
j=1 Lj vanishes at each pj . It has degree s.

Larry Guth The polynomial method in combinatorics

Tool 2: vanishing on a line

Let L ⊂ Fn be a line, parametrized by

γ(t) = at + b.
(Here, t ∈ F and a, b ∈ Fn , a 6= 0.)

Vanishing Lemma
If P is a polynomial of degree ≤ d that vanishes at d + 1 points of
L, then P vanishes on L.

Proof.
Let R(t) := P(γ(t)). R is a polynomial of degree ≤ d with d + 1
zeroes. So R is identically zero. Hence P vanishes on L.

Larry Guth The polynomial method in combinatorics

Proof of the finite-field Nikodym theorem in 3 dimensions

F a finite field with q elements.

Theorem
(Dvir 2007) Each Nikodym set in F3 has at least (1/30)q 3
elements.
Suppose that N is a Nikodym set with < (1/30)q 3 elements.
By the polynomial existence lemma, we can find a non-zero
polynomial P so that
P vanishes on N
Degree of P is ≤ (2/3)q.
Let x be any point of F3 . We know that P has q − 1 zeroes on
Lx . Hence P vanishes on Lx . So P vanishes at x. So P
vanishes at every point. But P was non-zero and has degree
≤ (2/3)q. Contradiction.

Larry Guth The polynomial method in combinatorics

Technical detail. Polynomials that vanish at every point
F a finite field with q elements.
Is it true that a polynomial that vanishes at each point of Fn is
the zero polynomial? Not necessarily. For example, x1q − x1
vanishes at every point.
Lemma
Let P be a polynomial in n variables which vanishes at each point
of Fn . If the degree of P is < q, then P is the zero polynomial.

Proof by induction. Base case is n = 1: a non-zero polynomial

of degree ≤ q − 1 has P ≤ q − 1 zeroes.
Induction. Write P = q−1 j
j=0 Pj (x1 , ..., xn−1 )xn .
Fix x1 , ..., xn−1 . We have a polynomial in xn of degree ≤ q − 1
with q zeroes. So every coefficient is zero.
Hence Pj (x1 , ..., xn−1 ) vanishes at each value of x1 , ..., xn−1 . Pj
has degree ≤ q − 1. By induction, each Pj vanishes identically.
So then P is zero.
Larry Guth The polynomial method in combinatorics
The polynomial method in outline: the finite field Nikodym
problem

1. Begin with a problem about some points in a vector space.

N ⊂ F3 . For each x ∈ F3 , there is a line Lx containing x with
Lx \ {x} ⊂ N. How big does N have to be?

2. Find a non-zero polynomial of low degree that vanishes on

N.
If N were small, then the degree of the polynomial would be
≤ (2/3)q.

3. Use this polynomial to attack the problem.

But that can’t be. If the degree were ≤ (2/3)q, we could show
the polynomial would vanish on the whole space F3 .
Lx \ {x} ⊂ N, so the polynomial vanishes there. But then it
vanishes at x also by the vanishing lemma.

Larry Guth The polynomial method in combinatorics

Influence of the finite-field Nikodym theorem

After Dvir’s paper, many harmonic analysts began to look at

the polynomial method.

Question: Will the polynomial method help us to make

progress on the Nikodym problem?

Nobody knows.

But the polynomial method has helped to solve a number of

longstanding problems in combinatorics.

Larry Guth The polynomial method in combinatorics

Applications of the polynomial method in combinatorics

Joints problem (posed in 1991, proven in 2008, Katz, G.)

Distinct distance problem in the plane (posed in 1946, proven
in 2010, Katz, G.)
New proof of Szemeredi-Trotter theorem and other important
known results in combinatorics/computer science. (2010,
Kaplan, Matousek, Sharir)
Generalizations of Szemeredi-Trotter theorem (posed in early
2000’s, proven in 2010, Solymosi, Tao)
Sum-product estimates in combinatorial number theory (a
variant of a problem posed in early 80’s, proven in 2010,
Iosevich, Roche-Newton, Rudnev)

Larry Guth The polynomial method in combinatorics

Why polynomials?

These problems are mostly about sets of lines in Rn .

(In some cases, the problem can be connected to lines in Rn by
a clever argument.)

Why do polynomials play a useful role?

They aren’t mentioned in the statements of the problems, and
they don’t even seem to be connected to the problem.

Will we find proofs of the finite field Nikodym theorem and

other results without using the polynomial trick?

Larry Guth The polynomial method in combinatorics

Isolate the key facts about polynomials

1. The space of polynomials is large. In 3 dimensions, V (d)

has dimension ∼ d 3 .
Polynomial existence lemma
If p1 , ..., ps ∈ F3 , then there is a non-zero polynomial that vanishes
on all the points pj with degree . s 1/3 .

2. The behavior of polynomials along a line is rather restricted.

Vanishing Lemma
If P is a polynomial of degree ≤ d that vanishes at d + 1 points of
a line L, then P vanishes on L.

If we restrict the polynomials in V (d) to a line L, we get a

vector space of dimension d + 1.

Larry Guth The polynomial method in combinatorics