Polynomial Methods (2021, Masters and Ph.D. students)
Instructor Arijit Ghosh
Status Completed (Last lecture was on 5 October 2021)
Description Introduction to "Polynomial Method", and its applications in Combinatorics, Geometry, and Theoretical Computer Science
Intended Audience Finishing Bachelors, Masters, and Ph.D. students
References
[A] D. Allcock, Simple Proof of Hilbert's Nullstellensatz.
[A99] N. Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing, 1999
[AF93] N. Alon and Z. Furedi, Covering the Cube by Affine Hyperplanes, European Journal of Combinatorics, 1993
[BC18] A. Bishnoi, P. L. Clark, A. Potukuchi, and J. R. Schmitt, On Zeros of a Polynomial in a Finite Grid, Combinatorics, Probability, and Computing, 2018
[B11] D. Brink, Chevalley’s theorem with restricted variables, Combinatorica, 2011
[CFS17] P. L. Clark, A. Forrow, and J. R. Schmitt, Warning’s Second Theorem with restricted variables, Combinatorica, 2017
[D12] Z. Dvir, Incidence Theorems and Their Applications, Foundations and Trends in Theoretical Computer Science, 2012
[E97] G. Elekes, On the number of sums and products, Acta Arithmetica, 1997
[E11] D. Ellis, Lecture Notes on "The Polynomial Method", from the course Algebraic Methods in Combinatorics at Cambridge Univ., 2011
[E46] P. Erdos, On sets of distances of n points, American Mathematical Monthly, 1946
[G16] L. Guth, Polynomial Methods in Combinatorics, AMS, 2016
[G12] L. Guth, Lecture Notes on Polynomial Method, MIT course, 2012
[GK10] L. Guth and N. H. Katz, Algebraic methods in discrete analogs of the Kakeya problem, Advances in Mathematics, 2010
[GK15] L. Guth and N. H. Katz, On the Erdos distinct distances problem in the plane, Annals of Mathematics, 2015
[GRS19] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory, online, 2019
[I08] A. Iosevich, Fourier Analysis, and Geometric Combinatorics, Topics in Mathematical Analysis, pages 321-335, 2008
[KMS12] H. Kaplan, J. Matousek, and M. Sharir, Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique, Discrete & Computational Geometry, 2012
[KSS10] H. Kaplan, M. Sharir, and E. Shustin, On Lines and Joints, Discrete & Computational Geometry, 2010
[LR] Landau-Ramanujan Constant
[M10] D. Moshkovitz, An Alternative Proof of The Schwartz-Zippel Lemma, 2010
[M02] J. Matoušek, Lectures on Discrete Geometry, Springer, 2002
[MM10] M. Michalek, A Short Proof of Combinatorial Nullstellensatz, American Mathematical Monthly, 2010
[MR95] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995
[MU17] M. Mitzenmacher and E. Upfal, Probability and Computing, Second Edition, Cambridge University Press, 2017
[S15] A. Sheffer, Polynomial Method, Lecture notes CUNY, 2015
[S16] A. Sheffer, Additive Combinatorics Lecture Notes, 2016
[S20] A. Sheffer, Polynomial Methods and Incidence Theory, To be published by Cambridge University Press
[S97] L. A. Székely, Crossing Numbers and Hard Erdos Problems in Discrete Geometry, Combinatorics, Probability & Computing, 1997
[Z47] O. Zariski, A New Proof of Hilbert's Nullstellensatz, Bulletin of the American Mathematical Society, 1947.
[Z15] F. de Zeeuw, Algebraic Combinatorial Geometry, Lecture notes EPFL, 2015
[Z16] Y. Zhao, Polynomial Methods in Combinatorics, Graduate course at Univ. of Oxford, 2016
[Z21] Y. Zhao, Graph Theory and Additive Combinatorics, Lecture notes MIT, 2021
Lecture details
Topics covered in Lecture 1 (24 April'21)
Point lines incidence in the plane
Statements of Szemeredi-Trotter (ST) theorem
Point lines incidence over a finite field
Schwartz-Zippel Lemma and its proof via probabilistic method
Vanishing polynomial via linear algebra
Readings:
Topics covered in Lecture 2 (11 May'21)
Properties of polynomials
Finite field Kakeya Conjecture
Dvir's proof of Finite field Kakeya Conjecture
Alternative proof of Schwartz-Zippel Lemma for finite field
Readings:
Topics covered in Lecture 3 (2 June'21)
Recall some basic properties of polynomials
Definition and basic properties of gradient of a function
Joints problem: lower and upper bound
Readings:
Topics covered in Lecture 4 (5 June'21)
Point-line incidence problem
Crossing number of graphs, and crossing number inequality
Proof of Szemeredi-Trotter Theorem using crossing number inequality
Point lines incidence over a finite field (upper and lower bounds)
Readings:
Topics covered in Lecture 5 (12 June'21)
Different equivalent formulations of Szemeredi-Trotter (ST) Theorem
Elekes' lower bound construction for point-line incidence problem
Elekes' Sum-Product estimate via ST Theorem
Crossing number inequality for multigraphs
ST Theorem bound of some special family of curves (e.g. collection of unit circles) using the above result
Erdos' unit distance and distinct distances problems
Landau–Ramanujan constant
Upper bound for distinct distances problem via Landau–Ramanujan constant
Readings:
Topics covered in Lecture 6 (23 June'21)
Recall equivalent formulations of ST Theorem and Pach-Sharir's extension of ST Theorem to special curves (e.g. collection of unit circles)
Upper bound to unit distance problem via incidence bound
Erdos' lower bound to distinct distances problem
Lower to distinct distances problem via incidence geometry
Beck's Ramsey-type result for points in the plane
Readings:
Topics covered in Lecture 7 (26 June'21)
Bounding the number of unit area triangles in the plane
Bounding the number of lattice points on a strictly convex curve
Revisiting crossing number for multigraphs
Readings:
Topics covered in Lecture 8 (4 July'21)
Crossing number inequality for multigraphs
Distinct distance problem for point sets with constant collinearity
Readings:
Topics covered in Lecture 9 (8 July'21)
Székely's distinct distance lower bound using crossing number inequality for multigraphs and Szemeredi-Trotter Theorem
Readings:
Topics covered in Lecture 10 (28 July'21)
Brief introduction to error-correcting codes
Reed-Solomon (RS) codes and their basic properties
Berlekamp-Welch Algorithm and its application in RS codes
Readings:
Topics covered in Lecture 11 (4 Aug.'21)
Recap the proof of correctness of Berlekamp-Welch Algorithm
Recall some simple properties of polynomials in one and two variables
Structure of minimal "vanishing polynomial" used in the Berlekamp-Welch Algorithm
Readings:
Topics covered in Lecture 12 (6 Aug.'21)
Recovering all low degree polynomials that agree with a function at least 1% of the points, and list decoding
Introduction to locally decodable codes
Readings:
Topics covered in Lecture 13 (13 Aug.'21)
Recall the results proved in the last 3 classes
Locally decodable codes and local reconstruction of polynomials
Readings:
Additional readings:
See Chernoff bounds in Chapter 4 from [MU17]
Topics covered in Lecture 14 (18 Aug.'21)
Definitions of Kakeya sets and Nikodym sets
Polynomial interpolation problem on Nikodym sets
Lower bounding size of Nikodym sets using ideas from locally decodable codes
Readings:
Additional references:
Topics covered in Lecture 15 (23 Aug.'21)
Recall the proof lower bounding the size of Nikodym sets over finite fields
Recall Schwartz-Zippel Lemma
Alon-Tarsi's structural result on polynomials vanishing on a "grid"
Combinatorial Nullstellensatz
Readings:
Topics covered in Lecture 16 (28 Aug.'21)
Recall the statement of Hilbert's Nullstellensatz
Algebraic version of Combinatorial Nullstellensatz
Alternate proof of Combinatorial Nullstellensatz using the algebraic version
Readings:
Additional readings:
Topics covered in Lecture 17 (1 Sep.'21)
Applications of Combinatorial Nullstellensatz
Chevalley's Theorem and resolution of Artin's conjecture that finite fields are quasi-algebraically closed
Cauchy-Davenport Theorem
Sufficient condition for existence of p-regular subgraphs, where p is a prime number, in a loopless multigraphs
Readings:
Additional readings:
Section 3 from Alon's original paper [A99]
Topics covered in Lecture 18 (7 Sep.'21)
Applications of Combinatorial Nullstellensatz
Recall the proof, from the previous class, of existence of p-regular subgraphs in multigraphs
Alon-Furedi's result about covering Hamming cube using hyperplanes and its natural generalizations
Warning's generalization of Chevalley's Theorem from the previous class
Degree requirement of a polynomial covering every point of a grid except one
Alternate proof of Chevalley's Theorem, from previous the class, using the above result
Readings:
Additional readings:
See the Mathoverflow page on Chevalley-Warning Theorem
Topics covered in Lecture 19 (15 Sep.'21)
Few more remarks on Chevalley–Warning Theorem
Recall the degree requirement of a polynomial covering every point of a grid except one
Existence of at most degree two polynomials vanishing on three lines in three-dimensional Euclidean space (denoted by 3D)
Existence of irreducible degree two polynomials vanishing on three pairwise skew lines in 3D, i.e., showing the existence of Regulus
Readings:
See the Mathoverflow page on Chevalley-Warning Theorem
Lecture 10 from [G12]
Chapter 7 from [G16]
Section 5.2 in Chapter 5 from [S20]
Topics covered in Lecture 20 (22 Sep.'21)
Recall the existence of Regulus
Zarankiewicz problem, and Kővári-Sós-Turán's upper bound
Bounding the number of intersection points of a set of lines in 3-dimensional Euclidean space that contains at most a constant number of them lie on a plane or a degree two surface (note that an improved bound will be proved in a later lecture)
Readings:
Topics covered in Lecture 21 (24 Sep.'21)
Recall the discrete version of Ham-Sandwich Theorem in d-dimensional Euclidean space
Polynomial version of Ham-Sandwich Theorem using ``lifting technique'' from computational/combinatorial geometry
Polynomial Partitioning Theorem due to Guth and Katz
Readings:
Topics covered in Lecture 22 (5 Oct.'21)
Recall Polynomial Partitioning and Vanishing Polynomial Theorems
Properties for polynomials in two-dimensional Euclidean space
Point-Line Duality
Alternative Szemeredi-Trotter Theorem using polynomial partitioning and vanishing polynomial theorems
Readings: