In a previous post I discussed how the Alon-Furedi theorem serves as a common generalisation of the results of Schwartz, DeMillo, Lipton and Zippel. Here I will show some nice applications of this theorem to finite geometry (reference: Section 6 of… 973 more words

## Tags » Polynomial Method

#### A symmetric formulation of the Croot-Lev-Pach-Ellenberg-Gijswijt capset bound

A *capset* in the vector space over the finite field of three elements is a subset of that does not contain any lines , where and . 1,354 more words

#### Ellenberg's announcement of a solution to the cap-set problem

Jordan Ellenberg has just announced a resolution of the “cap problem” using techniques of Croot, Lev and Pach, in a self-contained three-page paper. This is a quite unexpected development for a long-standing open problem in the core of additive combinatorics. 787 more words

#### The Ellenberg-Gijswijt bound on cap sets

Four days back Jordan Ellenberg posted the following on his blog:

1,031 more wordsBriefly: it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday…

#### Croot-Lev-Pach on AP-free sets in (Z/4Z)^n

As you know I love the affine cap problem: how big can a subset of (Z/3Z)^n be that contains no three elements summing to 0 — or, in other words, that contains no 3-term arithmetic progression? 840 more words

#### The Erdős-Ginzburg-Ziv theorem

*Let be a sequence of integers (not necessarily distinct). Then there exists a subsequence of the sum of whose elements is divisible by . *

This is one of the first problems I saw when learning the… 658 more words

#### Alon-Furedi, Schwartz-Zippel, DeMillo-Lipton and their common generalization

In the post Balls in Bins I wrote about a combinatorial function which denotes the minimum value of the product among all distributions of balls (so ) in bins with the constraints . 728 more words