Matpic
mathematics, in pictures
Concept

Polynomial method

Proving that a set must be large by building a polynomial of low degree that would vanish on it if it were small. A polynomial of low degree cannot vanish everywhere it is forced to, and the contradiction gives the bound.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

A line in every direction in the plane over GF(7), in 31 points. A square grid of the points of a small finite plane with the points of a Kakeya set filled, beside a list of the lines it contains, one for each direction.

No set with a line in every direction is small

In the plane over the integers modulo 7 there are 49 points and lines in 8 directions. A set holding a whole line in every direction needs 31 of the points — more than half — and in any dimension such a set fills a fixed share of the space. In the real plane the same sets can have area zero. Over a finite field one polynomial of low degree shows they cannot be small.

computation · Finite fields A + B modulo 13: 4 and 3 residues make 9. A clock face of residues with two sets marked on an inner ring and their sumset marked on an outer ring.

A sum of two sets modulo a prime cannot be small

Add every element of one set of residues to every element of another. Over the whole numbers the sums always number at least |A| + |B| − 1. Modulo a prime the sums can wrap round and collide, and still they never number fewer — the theorem Cauchy proved in 1813 and Davenport again in 1935. Modulo 12 they can. A polynomial of low degree explains the difference in a paragraph.

computation · Finite fields The polynomial bound falls exponentially behind the space. A log-scale plot against the dimension of the number of points of the space, the polynomial method's bound on a cap, and the known largest caps: the bound's line is less steep than the space's and pulls away from it.

The polynomial that bounds the caps

For forty years the best bound on a set of SET cards with no set among them shrank only like one over the dimension. In 2016 a two-page argument made it shrink exponentially, and the whole proof is a count of monomials: a table that is diagonal on a cap, one polynomial that describes it, and the fact that three parts of a degree cannot all be large.

computation · Finite fields

Named alongside it

The objects these essays reach for when they reach for this one.

Finite fieldCounting argumentPolynomialArithmetic progressionBinomial coefficientCap setDegreeHausdorff dimensionLarge deviationsMeasure zeroModular arithmeticNormal distribution

All concepts