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 , for a positive constant c, but the best known upper bound, due to Spencer, Szemeredi, and Trotter is only . As for the Distinct Distances Problem, the order of magnitude of the conjectured minimum is , while the best lower bound was , 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 for some positive δ. Indeed, it took more than 30 years, before F. Chung (1984) slightly improved on the first nontrivial lower bound of 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   upper bound on the first problem would immediately imply an lower bound on the second. However, no one has managed to break the 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 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.