Incidences in a Recent Work of Walsh

Recently, Miguel Walsh posted a very interesting paper on arXiv. The main purpose of the paper is to study various properties of polynomials and varieties. These properties are related to incidence problems – some originally arose from studying incidences. Walsh also presents new incidence bounds as applications of his results. In this post I’ll briefly discuss the incidence aspects of Walsh’s paper. Since this is a rather specialized post for incidence researchers, it assumes familiarity with the problems and notation.

Miguel Walsh

It seems to me that Walsh’s paper makes three main contributions to the study of incidence problems. The first two contributions are explicitly stated in the paper:

  • The paper derives a new polynomial partitioning theorem for points on a variety, with a good dependency on the degree of the variety. This was the missing step for removing an extra \varepsilon  in the exponent from most of the existing incidence bounds in {\mathbb R}^d  . For example, it should remove the extra \varepsilon  in the results of several of my papers, such as this one and that one.
  • As an application of his results, Walsh introduces an incidence problem that I did not see before. In this problem we study incidences between points and varieties in {\mathbb R}^d  , but the degrees of the varieties are not constant. That is, the degrees of the varieties are allowed to depend on the number of points and on the number of varieties. It would be interesting to see how this variant develops. For example, what applications in other subfields it might have.

The two above incidence results are definitely interesting, but I suspect that the paper would have a more significant effect on the incidence community in a different way. The paper makes significant progress in our understanding of polynomials and varieties, which directly affect the algebraic methods used to derive incidence bounds. This improved understanding could potentially be what we need to address some of the main problems that we have been trying to solve for a while. Me and other incidences researchers will definitely spend time reading the paper carefully, and think how it might fit with these problems. Walsh also mentions a follow-up paper, and I wonder if he has something similar in mind. I am planning to soon write a post about the current main open problems in incidence theory, and will then mention more clearly what I am referring to.

It might also be worth discussing the lower bounds part of the paper. The paper contains matching lower bounds for some of its incidence results. However, these lower bounds seem to apply specifically to the new variant of incidences with varieties of non-constant degrees. The “standard” problem of incidences with bounded-degree hypersurfaces in {\mathbb R}^d  remains open. In particular, we have matching lower bounds only in some cases. For an up-to-date discussion of the known lower bounds, see for example the relevant part in the introduction of my recent work with Thao Do.

Incidences Outside of Discrete Geometry (part 2)

You may have noticed that I have a bit of an obsession with geometric incidences. I do believe that incidences are a natural mathematical object that is connected to many different parts of math. This belief seems at least partially justified by the developments of the recent years. Less than two years ago I posted a list of some applications of incidences outside of Discrete Geometry. The purpose of that list was to show how incidences are becoming useful in a variety of fields, such as Harmonic Analysis, Theoretical Computer Science, and Number Theory. It seems that this process did not slow down in the past two years – incidences have continued to demonstrate their usefulness in the aforementioned fields, and there is even a new interest in the subject by model theorists.

This post is part 2 of the list of incidence uses outside of Discrete Geometry. It is just a list of references, and does not include many details. In future posts I might focus on specific applications and provide actual explanations. Hopefully new applications will continue to appear and I’ll have to keep adding more and more parts to this list!

The Kakeya conjecture. Katz and Zahl derived an improved bound for the Kakeya conjecture. Specifically, they improved Wolff’s longstanding bound for the Hausdorff dimension problem in {\mathbb R}^3  . This is the latest in a sequence of Harmonic Analysis works that have strong connections to incidences (see the first part of this list and also below).

Model theory. In Logic, a group of model theorists generalized incidence results to Distal structures. Another similar work extended incidence results to o-minimal structures. In general, there seems to be some interest in generalizing incidence-related problems to various models.

Number theory. A very recent number theoretic result is relying on incidence bounds. Admittedly, I still do not understand what this paper is about, and am hoping to learn that soon.

Algorithms. Moving to Theoretical Computer Science, a recent work analyzes point covering algorithms using incidence results.

Quantum Information. A few years ago, incidences in spaces over finite fields were used to study a problem in Quantum Information. This result is not from the past two years, but I was not aware of it before (thanks Ben Lund).

More Harmonic Analysis. An older survey of Łaba contains a nice review of previous appearances of incidences in Harmonic Analysis. I write “older” although not even a decade have passed. I just mean that this survey appeared before the new era of polynomial methods in Discrete Geometry.

There are obviously more results that are still missing from this list. If you noticed anything that I missed, I would be happy to hear about it.

An End to the Happy Ending Problem

Andrew Suk just placed on arXiv a paper with an almost tight bound for the happy ending problem. These are exciting news for discrete geometers! I’ll use the opportunity to describe the problem and its non-technical history.

Andrew Suk and the Anonymous statue.

In the early 1930’s in Budapest, several students used to regularly meet on Sundays in a specific city park bench. This was the bench next to the statue of Anonymous, the first medieval Hungarian chronicler. Among these students were Paul Erdős, George Szekeres, and Esther Klein.

On one such Sunday meeting, Klein pointed out that for any set of five points with no three on a line, four of the points are the vertices of a convex quadrilateral. This easy observation can be proved by considering the convex hull of the five points. If at least four of the points are on the boundary of the convex hull, then we are done. If the convex hull consists only of three of the points, then we consider the line \ell  that passes through the two interior points. We take the two interior points and the two points that are on the same side of \ell  .


The Budapest students started to think about whether there exists an n  such that every set of n  points with no three on a line contains the vertices of a convex pentagon. More generally, does a similar condition hold for every convex k  -gon? The first to prove the claim was Szekeres. A couple of years later, Esther Klein, who suggested the problem married George Szekeres who solved it. Since then, this problem is called the happy ending problem. They lived together up to their 90’s.


For every integer m \ge 3  , let N(m)  denote the smallest integer such that any set of N(m)  points with no three on a line contains a subset of m  points that are the vertices of a convex m  -gon. Erdős and Szekeres published a paper on the problem in 1935. They proved that

2^{m-2}+1 \le N(m) \le \binom{2m-4}{m-2}+1.

Erdős and Szekeres conjectured that N(m)=2^{m-2}+1  , and this is sometimes called “the Erdős–Szekeres conjecture”. Erdős offered a 500$ ` for proving or disproving this conjecture, and a few years ago Ron Graham (who is handling Erdős’ problem awards) increased the amount to 1000$. So far the conjecture was verified up to m=6  by a computer. Over the years several improved bounds were published, but the improvements were always sub-exponential. That is, the value of N(m)  remained between 2^m  and 4^m  (ignoring sub-exponential factors). In his new paper, Suk derives the impressive bound N(m)\le 2^{m+4m^{4/5}}  , settling the problem up to sub-exponential factors. Surprisingly, after 81 years of small progress, Suk’s impressive improvement requires a short proof that does not seem to rely on any kind of heavy machinery.

Local Properties that imply Many Distinct Distances

Jacob Fox, Janos Pach, and Andrew Suk just placed this paper on arXiv. The paper seems very nice, but unfortunately for Ben Lund, Frank de Zeeuw, and myself, it contains a result that is almost identical to one that we had but did not yet publish. Instead of sulking alone in the dark, in this post I describe the problem and our result.

Jacob Fox, Janos Pach, and Andrew Suk.

Let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set of n  points {\cal P} \subset {\mathbb R}^2  with the property that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances.

For example, the value of \phi(n,3,3)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any isosceles triangles (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines n-1  distinct distances with the other points of the set, and we thus have \phi(n,3,3) = \Omega(n)  . Erdős observed the following upper bound for \phi(n,3,3)  . Behrend proved that there exists a set A  of positive integers a_1<a_2<\cdots<a_n  , such that no three elements of A  determine an arithmetic progression and that a_n < n2^{O(\sqrt{\log n})}  . Therefore, the point set {\cal P}_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\}  does not span any isosceles triangles. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}  and D({\cal P}_2)< n2^{O(\sqrt{\log n})}  , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})}  .

In the same paper, Erdős derived the more general bound

\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n).

As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with \varepsilon  depending on k  )

\phi\left(n,k,\binom{k}{2}-k+4+\log k\right) = \Omega(n^{1+\varepsilon}).

We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the +5  being replaced with +6  . While there are some similarities between the two proofs, they do not seem to be identical.

Theorem 1. For every even k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+5\right) = \Omega(n^{8/7-\varepsilon}).

Continue reading

A list of recent papers

Lately I did not have much time to survey the recent developments in the polynomial method / algebraic combinatorial geometry / whatever it is called these days. Hopefully this will change soon, but for now here is a list of papers from the past year that were not discussed in this blog before. I think that these illustrate how active the field currently is (and I did not include several recent results that have been announced but are not available online yet). Feel free to point out other papers which I might have missed.

1. Polynomial partitioning for a set of varieties / Guth. This paper introduces a new type of polynomial partitioning. Instead of defining a partitioning with respect to a point set such that no cell contains a bounded number of points, this partitioning is defined with respect to a set of varieties and satisfies that every cells intersects a bounded number of varieties. It would be interesting to find new applications for such partitionings.

2. On the use of Klein quadric for geometric incidence problems in two dimensions / Rudnev and Selig. Studies the Elekes-Sharir(-Guth-Katz) framework from a somewhat new perspective. The paper generalizes several variants of the framework, bypassing the standard use of symmetry in such cases.

3. On the number of rich lines in truly high dimensional sets / Dvir and Gopi. The paper derives an upper bound for the number of r  -rich lines in {\mathbb C}^d  . For this purpose, Dvir and Gopi combine polynomial partitioning interpolation with a method relying on design matrices. In recent years, this method was used to obtain bounds for various higher dimensional variants of the Sylvester-Gallai problem.

Continue reading

Random Stories Pictures from IPAM – Part 3

We finished our IPAM semester with a workshop at lake arrowhead. You can find our “graduation pictures” at the IPAM facebook page (just don’t look at my horrible picture…). In honor of this amazing semester, here are some pictures that I have from it. If you have other nice pictures, you’re welcome to send them to me and I’ll place them here.

A farewell party to Micha, just before he was leaving LA.

The notorious reading group, trying to get through Harris’ algebraic geometry book.

Abdul Basit took us to what according to him is the best Pakistani food that he had outside of Pakistan.

Pool party!

Random Stories from IPAM – Part 2

If you are not in Los Angeles but are interested in these topics, you can now view videos of many of the talks that we had here. Talks from the tutorials week can be found here. Talks from the workshop “Combinatorial Geometry Problems at the Algebraic Interface” can be found here. I assume that talks from the workshop “Tools from Algebraic Geometry” will also be available soon.

A talk by Joseph Landsberg.

Another brief update: You might remember that in my previous IPAM post I was excited about a talk by Larry Guth. Not only that you can now watch the video of this talk, but you can also read the paper.

And now for quote of the week:

It is like defining a ham sandwich as “what you have in your lunchbox after taking the apple out”.

                Ben Lund, unsatisfied with a famous textbook’s definition of Grassmannians.

After three weeks without any main events, another workshop begins tomorrow. So more updates will follow.

Recent Results (Feb `14)

In this post I briefly mention several recent papers that are related to the topics of this blog (I might later write more detailed posts about some of these). This is not a comprehensive list, as there are many new relevant papers. Some other recent results can be found in the list of papers that were accepted to SoCG 2014, though I am not mentioning papers that still do not have a full version available online. Soon I will also add these to the related papers page.

1. Polynomials vanishing on grids: The Elekes-Rónyai problem revisited / Raz, Sharir, and Solymosi. In my previous post, about the partial Elekes-Sharir framework, I mentioned the existence of a couple of unpublished results that apply this technique to problems that do not directly involve distinct distances. This is the first of these papers, and the main result in it is the following improvement of a special case of recent result by Elekes and Szabó.

Theorem 1 (Raz, Sharir, and Solymosi). Consider a grid A\times B\times C \subset {\mathbb R}^3  , where |A|=|B|=|C|=n  , and a polynomial f\in{\mathbb R}[x,y,z]  which is of the form z=g(x,y)  . Then if f  vanishes on \Omega(n^{11/6})  points of the grid, it must be either of the form f=h(\varphi(x)+\psi(y))  or the form f=h(\varphi(x)\cdot\psi(y))  , for h,\varphi,\psi \in {\mathbb R}[x]  .

This appears to be a rather strong result with various applications, including subsuming several previous results that were obtained by applying the partial Elekes-Sharir framework. The paper by Elekes and Szabó is significantly more general in the sense that it applies to any f  (not just of the form z=g(x,y)  ), to grids in the complex space, and to more general scenarios in higher dimensions. However, it is not clear to me (or to other people that I have asked) what exactly are the bounds that were obtained in it (that is, compared to \Omega(n^{11/6})  ), which seem to also depend on the degree of f  .

2. Distinct volume subsets / Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky. I already had a post about a previous version of this paper (which back then I found through google scholar and by mistake thought that it was public). In one rather imprecise sentence: the paper shows that for every set \cal P  of n  points in {\mathbb R}^d  and for every 1 \le a \le d  , there exists a large subset {\cal P}' \subset {\cal P}  , such the points of {\cal P}'  do not span two a  -dimensional simplices with the same volume (hence the name Distinct volume subsets). The main results have remained more or less the same and you can find more details about them in my original post. However, the new (and official!) version of the paper is significantly shorter. As William Gasarch was describing it to me, the new version has “cleaner defintions, cleaner proofs, and more precise results.”

3. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory / Tao. This paper is a survey and is already three months old, but I think that it is worth mentioning. The survey discusses recent techniques such as polynomial partitioning, the existence of bounded-degree polynomials that vanish over a given point set, etc., but also other topics such as Alon’s combinatorial nullstellensatz.

In the survey, Tao dubs this (sub-)field as algebraic combinatorial geometry, so perhaps I should start saying that this is a blog that focuses on algebraic combinatorial geometry. I am quite happy about Tao uniting these various techniques under one roof and naming it. I hope that this would help making the field more known and to push it forward.