Polynomial Methods (2021-22, 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

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:

  • • Section 4.1 in Chapter 4 from [M02]

    • Section 7.2 in Chapter 7 from [MR95]

    • Proof of Lemma 4 from [E11]

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:

  • • Section 4.2 in Chapter 4 from [D12]

    • Terence Tao's blog

    • For an alternative proof of Schwartz-Zippel Lemma see [M10]

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:

  • • Terence Tao's blog

    • See [KSS10, GK10]

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:

  • • Chapter 1 from [S20]

    • Section 2.1 in Chapter 2 from [D12]

    • Section 4.3 in Chapter 4 from [M02]

    • Sections 7.1 and 7.2 in Chapter 7 from [G16]

    • See Székely's paper [S97]

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:

  • • Chapter 1 from [S20]

    • Sections 2.1 and 2.2 in Chapter 2 from [D12]

    • Chapter 7 from [G16]

    • Section 4.4 in Chapter 4 from [M02]

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:

  • • Sections 2.1 and 2.2 in Chapter 2 from [D12]

    • Chapter 1 from [S20]

    • See Erdos' original paper [E46]

    • See Székely's paper [S97]

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:

  • • Section 1.7 in Chapter 1 from [S20]

    • Sections 2.2 in Chapter 2 from [D12]

Topics covered in Lecture 8 (4 July'21)

• Crossing number inequality for multigraphs

• Distinct distance problem for point sets with constant collinearity

• Readings:

  • • Sections 4.3 and 4.4 in Chapter 4 from [M02]

    • Chapter 7 from [G16]

    • Lectures 8 and 9 from [G12]

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:

  • • Lecture 9 from [G12]

    • Chapter 7 from [G16]

    • See Székely's paper [S97]

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:

  • • Chapter 5 from [GRS19]

    • Lecture 2 from [G12]

    • Chapter 4 from [G16]

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:

  • • Lecture 2 from [G12]

    • Chapter 4 from [G16]

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:

  • • Lecture 2 from [G12]

    • Chapter 4 from [G16]

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:

  • • Chapter 4 from [G16]

    • Lecture 2 from [G12]

• 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:

  • • Chapter 4 from [G16]

    • Section 4.2 in Chapter 4 from [D12]

• Additional references:

  • • Fefferman explaining Kakeya problem and Besicovitch's construction [Link]

    • Sections 4.1 and 4.3 in Chapter 4 from [D12]

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:

  • • Chapter 4 from [G16]

    • Section 4.2 in Chapter 4 from [D12]

    • Section 4 from Ellis' notes [E11]

    • Sections 1 and 2 from Alon's original paper [A99]

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:

  • • Section 1 from Alon's original paper [A99]

    • Section 4 from Ellis' notes [E11]

• Additional readings:

  • • For a simple proof of Hilbert's Nullstellensatz see [A] and [Z47]

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:

  • • Sections 1, 2 and 6 from Alon's original paper [A99]

    • Section 4 from Ellis' notes [E11]

• 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:

  • • Sections 1, 2, and 6 from Alon's original paper [A99]

    • Section 4 from Ellis' notes [E11]

    • Alon and Füredi's original paper [AF93]

• Additional readings:

  • • See the following papers [B11], [CFS17], and [BC18]

    • 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:

  • • Lecture 10 from [G12]

    • Chapter 7 from [G16]

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:

  • • Sections 1 and 2 from [KMS12]

    • Chapter 10 from [G16]

    • Lecture 18 from [G12]

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:

  • • Sections 2 and 3 from [KMS12]

    • Lecture 19 from [G12]

    • Section 2.5 from [D12]

    • Chapter 10 from [G16]