Category Archives: Polynomial Method

A coding theoretic application of the Alon-Füredi theorem

Posted on March 7, 2021 by Anurag Bishnoi

The Alon-Füredi theorem is something that I have written a lot about in this blog. I spent a considerable amount of time on this theorem during my PhD. In fact, it’s generalisation that I obtained and it’s applications in finite … Continue reading →

Posted in Coding Theory, Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method | Tagged Alon-Furedi, finite fields, finite geometry, linear codes, minimal codes, polynomials | 4 Comments

Covering the binary hypercube

Posted on October 19, 2020 by Anurag Bishnoi

A finite grid is a set , where is a field and each is a finite subset of . The minimum number of hyperplanes required to cover can easily be shown to be , with the hyperplanes defined by , … Continue reading →

Posted in Combinatorics, Extremal Combinatorics, Finite Geometry, Polynomial Method | Tagged Alexander Clifton, Alon-Furedi, Brouwer-Shcrijver, Hao Huang, hyperplane covers, Jamison, Lisa Sauermann, Shagnik Das, Simona Boyadzhiyska, Tamas Meszaros, Yuval Wigderson | 1 Comment

The footprint bound

Posted on March 25, 2018 by Anurag Bishnoi

Studying the set of common zeros of systems of polynomial equations is a fundamental problem in algebra and geometry. In this post we will look at estimating the cardinality of the set of common zeros, when we already know that … Continue reading →

Posted in Coding Theory, Combinatorics, Polynomial Method | Tagged algebraic geometry, Alon-Furedi, combinatorial nullstellensatz, combinatorics, finite fields, footprint, Groebner basis, standard monomials | 1 Comment

Introduction to polynomial method

Posted on November 25, 2017 by Anurag Bishnoi

(The following is a blog-friendly version of Chapter 7 of my PhD thesis, which is an introduction to the so-called polynomial method.) The polynomial method is an umbrella term for different techniques involving polynomials which have been used to solve … Continue reading →

Posted in Combinatorics, Incidence Geometry, Polynomial Method | Tagged additive-combinatorics, combinatorial nullstellensatz, combinatorics, finite geometry, polynomials | 2 Comments

The coefficient formula and Chevalley-Warning

Posted on July 17, 2017 by Anurag Bishnoi

We discuss the new simultaneous generalization of Chevalley-Warning and Morlaye’s result on polynomial equations over finite fields obtained by Pete Clark. Continue reading →

Posted in Number Theory, Polynomial Method | Tagged Baoulina, chevalley-warning, combinatorial nullstellensatz, finite fields, Morlaye, Pete Clark, polynomials | 2 Comments

Applications of Alon-Furedi to finite geometry

Posted on May 27, 2016 by Anurag Bishnoi

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 my … Continue reading →

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged Alon-Furedi, blocking set, polynomials | 1 Comment

The Ellenberg-Gijswijt bound on cap sets

Posted on May 18, 2016 by Anurag Bishnoi

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 can indeed be used to give a new bound on the size of subsets … Continue reading →

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged cap-set, Dion Gijswijt, Ernie Croot, Jordan Ellenberg, Peter Pach, Seva Lev | 7 Comments

The Erdős-Ginzburg-Ziv theorem

Posted on December 17, 2015 by Anurag Bishnoi

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 pigeonhole principle. And it’s … Continue reading →

Posted in Combinatorics, Polynomial Method | Tagged additive-combinatorics, Alon-Furedi, combinatorics, polynomials | 8 Comments

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

Posted on October 19, 2015 by Anurag Bishnoi

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 . It turns out that this combinatorial function is linked … Continue reading →

Posted in Combinatorics, Polynomial Method | Tagged Alon-Furedi, combinatorics, finite fields, polynomials | 4 Comments

A timeline of the polynomial method up-to combinatorial nullstellensatz

Posted on August 27, 2015 by Anurag Bishnoi

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s paper on the Kakeya conjecture, where he … Continue reading →

Posted in Combinatorics, Finite Geometry, Polynomial Method | Tagged combinatorics, finite fields, finite geometry, polynomials | 3 Comments