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

## 13 thoughts on “János Pach: Guth and Katz’s Solution of Erdős’s Distinct Distances Problem”

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

2. 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.

• 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

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

• 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?

• Gil,

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

• That’s very interesting, Nets! –Gil

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

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

5. 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!

6. 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.

7. 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