János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

Click here for the most recent polymath3 research thread.

Erdős and Pach celebrating another November day many years ago. The Wolf disguised as Little Red Riding Hood. Pach disguised as another Pach.

This post is authored by János Pach

A Festive Day: November 19

Today is a festive day. It was on this day, November 19, 1863, that Abraham Lincoln presented his famous Gettysburg Address. Seventy nine years later, on the same day (on his own birthday!), Georgy Zhukov, Marshal of the Soviet Union, launched Operation Uranus, turning the tide of the battle of Stalingrad and of World War II. Now sixty eight years later, here we stand (or sit) and experience my very first attempt to contribute to a blog, as Gil has suggested so many times during the past couple of years. But above all, this is a festive day, because earlier today Larry Guth and Nets Hawk Katz posted on arXiv
(http://arxiv.org/PS_cache/arxiv/pdf/1011/1011.4105v1.pdf) an almost complete solution of Erdös’s Distinct Distances Problem. The story started with Erdős’s 1946 paper published in the American Mathematical Monthly. In this paper, he posed two general questions about the distribution of distances determined by a finite set of points in a metric space.

1. Unit Distance Problem: At most how many times can the same distance (say, distance 1) occur among a set of n points?

2. Distinct Distances Problem: What is the minimum number of distinct distances determined by a set of n points?

Because of the many failed attempts to give reasonable bounds on these functions even in the plane, one had to realize that these questions are not merely “gems” in recreational mathematics. They have raised deep problems, some of which can be solved using graph theoretic and combinatorial ideas. In fact, the discovery of many important combinatorial techniques and results were motivated by their expected geometric consequences. (For more about the history of this problem, read my book with Pankaj Agarwal: Combinatorial Geometry, and for many related open problems, my book with Peter Brass and Willy Moser: Research Problems in Discrete Geometry.)

Erdős conjectured that in the plane the number of unit distances determined by n points is at most n^{1+c/loglog n}, for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only O(n^{4/3}). As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is n/\sqrt{log n}, while the best lower bound was n^{0.8641...}, thanks to combined efforts by J. Solymosi – C.D. Toth (2001) and N.H. Katz – G. Tardos (2004).

This was the situation until today! The sensational new paper of Guth and Katz presents a proof of an almost tight lower bound of the order of n/log n. Let us celebrate this fantastic development! In this area of research, it is already considered a great achievement if by introducing an ingenious new idea one is able to improve a bound by a factor of n^{\delta} for some positive δ. Indeed, it took more than 30 years, before F. Chung (1984) slightly improved on the first nontrivial lower bound of n^{2/3} for the Distinct Distances Problem, due to L. Moser (1952). It took another decade or so to further improve the exponent from 2/3, first to 3/4, and then to 4/5 (see K. Clarkson et al. (1990), F. Chung – E. Szemeredi – W. Trotter (1992), L. Szekely (1997)).

Of course, the Unit Distance Problem and the Distinct Distances Problem are closely related. The maximum number of times the same distance can occur among n points, multiplied by the minimum number of distinct distances, is at least n choose 2. Therefore, an n^{1+\epsilon}  upper bound on the first problem would immediately imply an (1/2)n^{1-\epsilon} lower bound on the second. However, no one has managed to break the n^{4/3} barrier for the first problem for more than a quarter of a century. Another common aspect of the two problems is that, according to Erdős’s conjectures, for both of them the order of magnitude of the optimum is attained for the integer grid. One has to be careful with such conjectures. It is a curious feature of this subject that it is very hard to come up with interesting nontrivial constructions. The situation is somewhat similar to Hilbert’s problem on the densest packing of spheres (also known, somewhat incorrectly, as Kepler’s conjecture, in 3 dimensions). In the lack of good constructions, most researchers conjecture that for any fixed d, the densest packing of spheres in d-dimensional space is lattice-like. Referring to the 3-dimensional space, C. A. Rogers famously remarked that “many mathematicians believe, and all physicists know” that this is the case. Following the work of T. Hales, it is now generally believed that the physicists were right. But why did they “know” that the densest packings were lattice-like? Because most molecular structures in nature that emerge under high pressure take some crystal formation. The physicists argued that if there existed more economical arrangements, “Nature” would have surely discovered them. At the moment we have no idea about Nature’s analogous behavior in higher dimensions. Similarly, we know no satisfying physical model forsimulating the problems of repeated distances that would give us a clue about Erdős’s conjectures. Nevertheless, without any help from Nature, Guth and Katz managed to show that Erdős’s conjecture on repeated distances was not far from the truth. This is a great achievement.

I do not really know what blogging is about. Therefore, I simply follow Gil’s instructions. He spent the last 24 hours in Lausanne, and gave a wonderful talk: the 3rd Bernoulli Lecture at the Special Semester on Discrete and Computational Geometry(http://dcgprogram.epfl.ch/). When he asked me to write this entry, he told me to “express my feelings about the new results.” I am not quite sure what he meant. But here are two things that come to my mind.

First, I have always felt the Distinct Distances Problem may have a nice solution that can be explained to a bright undergraduate. I was hoping that someone would come up with the right elegant approach. It seems that my gut feeling was correct. (I am afraid that it will take much longer to settle the Unit Distance Problem.)

Finally, a few words about the “elegant approach.” György Elekes, who died 2 years ago at the age of 60, was an excellent teacher, a great mathematician, and a very nice and straightforward person. I had the privilege to take some of his classes at Eotvos University and to have many conversations with him over the years on mathematics and just about everything else. Most of Elekes’s work was related to Erdős-type problems in geometry and number theory, and most of it was brilliantly elegant. It is hard to forget, for example, his “book proof” of a sum-product estimate based on the Szemeredi-Trotter theorem on
incidences, or his beautiful construction showing that n points in the plane can determine n^{3/2} unit circles. He had a “vision”: a plan how to get an n/log n lower bound on the Distinct Distances problem.

It had been sitting in the back of his mind for almost a decade, and he persistently returned to it and tried to complete the elements of the proof. He gave several talks about the subject, and left some unfinished manuscripts behind. To tell the truth, I did not believe in Elekes’s plan. It sounded too brave and too complicated at the same time. I was not convinced at all whether either of the steps he wanted to break the proof into was true and only a matter of hard work and better insight. Even the first obstacles appeared to be insurmountable. Luckily, Micha Sharir was much wiser. He believed in the program, and at the request of Marton Elekes (Gyuri’s son, a great mathematician on his own right), he completed Elekes’s notes, started exploring them, and published them in a joint paper. His presentation was fascinating, but still not sufficiently convincing for me. Larry Guth and Nets Hawk Katz did not share my feeling. As Paul Erdős would say, “their brains were open.” They found some beautiful shortcuts and brought this plan to fruition. What a treat!

This is a festive day, indeed. I can imagine how Erdős would react on the news: how happy he would be to pay the prize that he probably offered for such a breakthrough…

János Pach


An exposition of the main ideas of the proof of Guth and Katz can be found on Terry Tao’s Blog.  William Gasarch wrote about it in computational complexity and gave a link to a page listing previous results, and mentioned a forthcoming book by Julia Garibaldi, Alex Iosevich, and Steven Senger due out in Jan 2011 entitled “The Erdos Distance Problem“. A beautiful post listing several applications of continuous methods to geometric problems by Nabil Mustafa can be found here on the Geomblog.

About these ads
This entry was posted in Combinatorics, Geometry, Guest blogger, Open problems and tagged , . Bookmark the permalink.

13 Responses to János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem

  1. domotorp says:

    Just don’t show that top photo to Oleg Pikhurko!

  2. Gil Kalai says:

    Let me make one further comment on the method: One ingredient of Elekes’ programme which is discussed and studied in the paper of Elekes and Sharir was relating Erdos’s distance problem to certain incidence questions in three dimensions. A very effective method for studying those incidence problems is algebraic. The algebraic method plays a role in the paper by Elekes and Sharir as well as in the earlier solution by Katz and Guth to the “joints problem”. The solution of the “joints problem” relies on an idea by Zeev Dvir in Zeev’s solution of the finite field Kakeya problem.

    • Nets Katz says:

      Gil,

      Your comment is really on point. It was the algebraic method introduced by Dvir together with the Elekes-Sharir approach relating the Erdos problem to point-line incidences which made the problem seem possibly approachable.

      However, the main part of the incidence problem cannot be done by purely algebraic means, as it does not hold in finite fields. To carry out our argument,
      we needed to combine the algebraic method with the more topological approach associated with the Szemeredi-Trotter theorem. The tool which allows these approaches to be combined is the polynomial ham sandwich theorem of Stone and Tukey.

      The polynomial ham sandwich theorem was introduced into incidence theory
      when Larry Guth used it in his paper on the endpoint result for
      Bennett-Carbery-Tao’s multilinear Kakeya theorem. However, the
      use he and I find for it here is a little different. In his paper, he used it to
      find a polynomial bisecting delta-balls, thus giving him an ability to make
      in a continuous problem an analogous statement to “the polynomial
      vanishes on all the points.”

      Our problem, however, was discrete. Instead of using the polynomial
      ham sandwich theorem to cut volumes in two, we used it to divide in two
      the set of points. Doing this repeatedly, we create a cell decomposition
      with very three dimensional properties … unless the points are all in the
      zero set of a polynomial. If they are, it has low degree and we can apply the algebraic method.

      The reason the proof could not have happened until now is that although cell theoretic methods were very well developed, it was known that not all sets
      of points in space had a nice cell decomposition because they might be
      structured as a quite two dimensional set. The alternative of having them in
      the zero-set of a low degree polynomial could not be appreciated until the very recent development of the algebraic method.

      Nets

      • Gil Kalai says:

        Many thanks, Nets, for this interesting explanation of the beautiful picture. Gil

      • Gil Kalai says:

        Dear Nets, as there are two or more ingredients of your proof with Larry that are related to Kakeya’s conjecture, an obvious question is if there are some implications or expected applications of yours new ideas to the Kakeya’s conjecture?

      • Nets Katz says:

        Gil,

        Thanks for asking.

        For many years, I had always felt that there was a deep connection between the Erdos distance problem and the Kakeya problem.

        For instance, my work with Tardos on the sums-entries problem, which gave the previous record was in a kind of perfect analogy to work with Tao on the sums differences problem. But I never quite understood why the two problems should be so closely related.

        In light of the work of Elekes and Sharir, I think it is rather clear. Really, it was a big part of their contribution to transform
        a problem on counting distances in the plane, to a problem about counting incidences between lines and points in space.

        Now as to your question, I think it is important to understand that Kakeya is not strictly an incidence problem but
        in the language of this paper:
        http://lanl.arxiv.org/abs/math/0101195
        a delta-discretized problem.

        The most dramatic contribution of our paper is the use of the polynomial ham sandwich theorem to create a cell decomposition. Cell decompositions have a history of failing
        badly in delta-discretized problems. I do not really expect them to do much better now.

        However, the Elekes-Sharir construction is much more robust.
        Take two points at distance 1 and the set of
        “reasonable” rigid motions taking one to the other looks like a delta tube. What the work of Elekes and Sharir can do is convert
        delta-discretized distance problems like the Falconer conjecture into the same world as 3d Kakeya. This could take results from the 3d Kakeya problem even under somewhat heavy self-similarity conditions and possibly give quite satisfying looking
        results in Falconer.

        Nets

      • Gil Kalai says:

        That’s very interesting, Nets! –Gil

  3. Pingback: The Guth-Katz bound on the Erdős distance problem « What’s new

  4. Michael Lacey says:

    My warm congratulations to both Nets and Larry on a breakthrough result, one with a beautiful proof.

  5. Pingback: 지난 두 달 반 동안 유럽에 다녀왔습니다 « P 는 NP

  6. Raitis Ozols says:

    Hello! I am student from Latvia, my main interest is mathematics. Can anybody sent me Erdos proof that n points on plane can be placed so that there occur at least n^(1+c/log log n) unit distances? And what is value of constant c?
    Thank you!

  7. Gil Kalai says:

    Dear Raitis
    The basic idea is to take a \sqrt n by \sqrt n planar grid and choose the most popular distance occuring there. I dont know what c is.

  8. satbir singh malhi says:

    hii nets Hawk Katz
    i want to ionwork on your reseach paper Kakeya sets in cantor Directions .can you hepl me to understand some intial point of this paper .i have some question about it can u guide me how and from where i can start my reading

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s