Jump to content

Polynomial method in combinatorics

From Wikipedia, the free encyclopedia

In mathematics, the polynomial method is an algebraic approach to combinatorics problems that involves capturing some combinatorial structure using polynomials and proceeding to argue about their algebraic properties. Recently, the polynomial method has led to the development of remarkably simple solutions to several long-standing open problems.[1] The polynomial method encompasses a wide range of specific techniques for using polynomials and ideas from areas such as algebraic geometry to solve combinatorics problems. While a few techniques that follow the framework of the polynomial method, such as Alon's Combinatorial Nullstellensatz,[2] have been known since the 1990s, it was not until around 2010 that a broader framework for the polynomial method has been developed.

Mathematical overview

[edit]

Many uses of the polynomial method follow the same high-level approach. The approach is as follows:

  • Embed some combinatorial problem into a vector space.
  • Capture the hypotheses of the problem by constructing a polynomial of low-degree that is zero on a certain set
  • After constructing the polynomial, argue about its algebraic properties to deduce that the original configuration must satisfy the desired properties.

Example

[edit]

As an example, we outline Dvir's proof of the Finite Field Kakeya Conjecture using the polynomial method.[3]

Finite Field Kakeya Conjecture: Let be a finite field with elements. Let be a Kakeya set, i.e. for each vector there exists such that contains a line . Then the set has size at least where is a constant that only depends on .

Proof: The proof we give will show that has size at least . The bound of can be obtained using the same method with a little additional work.

Assume we have a Kakeya set with

Consider the set of monomials of the form of degree exactly . There are exactly such monomials. Thus, there exists a nonzero homogeneous polynomial of degree that vanishes on all points in . Note this is because finding such a polynomial reduces to solving a system of linear equations for the coefficients.

Now we will use the property that is a Kakeya set to show that must vanish on all of . Clearly . Next, for , there is an such that the line is contained in . Since is homogeneous, if for some then for any . In particular

for all nonzero . However, is a polynomial of degree in but it has at least roots corresponding to the nonzero elements of so it must be identically zero. In particular, plugging in we deduce .

We have shown that for all but has degree less than in each of the variables so this is impossible by the Schwartz–Zippel lemma. We deduce that we must actually have

Polynomial partitioning

[edit]

A variation of the polynomial method, often called polynomial partitioning, was introduced by Guth and Katz in their solution to the Erdős distinct distances problem.[4] Polynomial partitioning involves using polynomials to divide the underlying space into regions and arguing about the geometric structure of the partition. These arguments rely on results from algebraic geometry bounding the number of incidences between various algebraic curves. The technique of polynomial partitioning has been used to give a new proof of the Szemerédi–Trotter theorem via the polynomial ham sandwich theorem and has been applied to a variety of problems in incidence geometry.[5][6]

Applications

[edit]

A few examples of longstanding open problems that have been solved using the polynomial method are:

See also

[edit]

References

[edit]
  1. ^ Guth, L. (2016). Polynomial Methods in Combinatorics. University Lecture Series. American Mathematical Society. ISBN 978-1-4704-2890-7. Retrieved 2019-12-11.
  2. ^ Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing. 8 (1–2): 7–29. doi:10.1017/S0963548398003411. ISSN 0963-5483. S2CID 209877602.
  3. ^ a b Dvir, Zeev (2008). "On the size of Kakeya sets in finite fields". Journal of the American Mathematical Society. 22 (4): 1093–1097. arXiv:0803.2336. doi:10.1090/S0894-0347-08-00607-3. ISSN 0894-0347.
  4. ^ a b Guth, Larry; Katz, Nets (2015). "On the Erdős distinct distances problem in the plane". Annals of Mathematics: 155–190. doi:10.4007/annals.2015.181.1.2. hdl:1721.1/92873. ISSN 0003-486X. S2CID 43051852.
  5. ^ Kaplan, Haim; Matoušek, Jiří; Sharir, Micha (2012). "Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique". Discrete & Computational Geometry. 48 (3): 499–517. arXiv:1102.5391. doi:10.1007/s00454-012-9443-3. ISSN 0179-5376. S2CID 254037375.
  6. ^ Dvir, Zeev (2012). "Incidence Theorems and Their Applications". Foundations and Trends in Theoretical Computer Science. 6 (4): 257–393. arXiv:1208.5073. Bibcode:2012arXiv1208.5073D. doi:10.1561/0400000056. ISSN 1551-305X. S2CID 15932528.
  7. ^ Ellenberg, Jordan; Gijswijt, Dion (2017). "On large subsets of with no three-term arithmetic progression". Annals of Mathematics. 185 (1): 339–343. doi:10.4007/annals.2017.185.1.8. ISSN 0003-486X.
  8. ^ Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "Progression-free sets in are exponentially small" (PDF). Annals of Mathematics. 185 (1): 331–337. doi:10.4007/annals.2017.185.1.7. ISSN 0003-486X.
  9. ^ Guth, Larry; Katz, Nets Hawk (2010). "Algebraic methods in discrete analogs of the Kakeya problem". Advances in Mathematics. 225 (5): 2828–2839. arXiv:0812.1043. doi:10.1016/j.aim.2010.05.015. ISSN 0001-8708.
  10. ^ Elekes, György; Kaplan, Haim; Sharir, Micha (2011). "On lines, joints, and incidences in three dimensions". Journal of Combinatorial Theory. Series A. 118 (3): 962–977. doi:10.1016/j.jcta.2010.11.008. hdl:10831/47842. ISSN 0097-3165.
[edit]