Polynomial method in combinatorics

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 (around 2016), 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.

## Contents

* 1 Mathematical overview
* 1.1 Example
* 1.2 Polynomial partitioning
* 2 Applications
* 3 See also
* 4 References
* 5 External links

## Mathematical overview

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

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

Finite Field Kakeya Conjecture: Let 𝔽q be a finite field with q elements. Let K⊆𝔽qn be a Kakeya set, i.e. for each vector y∈𝔽qnthere exists x∈𝔽qn such that K contains a line {x+ty,t∈𝔽q}. Then the set K has size at least cnqnwhere cn>0 is a constant that only depends on n.

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

Assume we have a Kakeya set K with

|K|<(q+n−3n−1)

Consider the set of monomials of the form x1d1x2d2…xndn of degree exactly q−2. There are exactly (q+n−3n−1) such monomials. Thus, there exists a nonzero homogeneous polynomial P(x1,x2,…,xn) of degree q−2 that vanishes on all points in K. Note this is because finding such a polynomial reduces to solving a system of |K| linear equations for the coefficients.

Now we will use the property that K is a Kakeya set to show that P must vanish on all of 𝔽qn. Clearly P(0,0…,0)=0. Next, for y≠0, there is an x such that the line {x+ty,t∈𝔽q} is contained in K. Since P is homogeneous, if P(z)=0 for some z∈𝔽qn then P(cz)=0 for any c∈𝔽q. In particular

P(tx+y)=P(t(x+t−1y))=0

for all nonzero t∈𝔽q. However, P(tx+y) is a polynomial of degree q−2 in t but it has at least q−1 roots corresponding to the nonzero elements of 𝔽q so it must be identically zero. In particular, plugging in t=0 we deduce P(y)=0.

We have shown that P(y)=0 for all y∈𝔽qn but P has degree less than q−1 in each of the variables so this is impossible by the Schwartz–Zippel lemma. We deduce that we must actually have

|K|≥(q+n−3n−1)∼qn−1(n−1)!

### Polynomial partitioning

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

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

* The finite field Kakeya conjecture[3] by Dvir
* The cap set problem by Ellenberg and Gijswijt[7] with the original framework developed on the analogous problem over ℤ4n by Croot, Lev and Pach[8]
* The Erdős distinct distances problem by Guth and Katz[4]
* The Joints Problem in 3D by Guth and Katz.[9] Their argument was later simplified by Elekes, Kaplan and Sharir[10]

## See also

* Combinatorial Nullstellensatz

## References

1. ↑ Guth, L. (2016). Polynomial Methods in Combinatorics. University Lecture Series. American Mathematical Society. ISBN 978-1-4704-2890-7. https://books.google.com/books?id=t9ZTDAAAQBAJ. 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.
3. ↑ 3.0 3.1 Dvir, Zeev (2008). "On the size of Kakeya sets in finite fields". Journal of the American Mathematical Society 22 (4): 1093–1097. doi:10.1090/S0894-0347-08-00607-3. ISSN 0894-0347.
4. ↑ 4.0 4.1 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. ISSN 0003-486X.
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. doi:10.1007/s00454-012-9443-3. ISSN 0179-5376.
6. ↑ Dvir, Zeev (2012). "Incidence Theorems and Their Applications". Foundations and Trends in Theoretical Computer Science 6 (4): 257–393. doi:10.1561/0400000056. ISSN 1551-305X. Bibcode: 2012arXiv1208.5073D.
7. ↑ Ellenberg, Jordan; Gijswijt, Dion (2017). "On large subsets of 𝔽qn with no three-term arithmetic progression". Annals of Mathematics 185 (1): 339–343. doi:10.4007/annals.2017.185.1.8. ISSN 0003-486X. http://resolver.tudelft.nl/uuid:24934b91-cb43-49ef-9423-731dd1fb9306.
8. ↑ Croot, Ernie; Lev, Vsevolod; Pach, Péter (2017). "Progression-free sets in ℤ4n are exponentially small". Annals of Mathematics 185 (1): 331–337. doi:10.4007/annals.2017.185.1.7. ISSN 0003-486X. http://real.mtak.hu/62116/1/prog_free.pdf.
9. ↑ Guth, Larry; Katz, Nets Hawk (2010). "Algebraic methods in discrete analogs of the Kakeya problem". Advances in Mathematics 225 (5): 2828–2839. 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. ISSN 0097-3165.

## External links

* Survey on the Polynomial Method by Terence Tao
* Survey on the Polynomial Method by Larry Guth

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Polynomial method in combinatorics. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Polynomial_method_in_combinatorics&oldid=4225913"