Tags » Polynomial Method

Applications of Alon-Furedi to finite geometry

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


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,355 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:

Briefly:  it seems to me that the idea of the Croot-Lev-Pach paper I posted about yesterday…

1,076 more words

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