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

About these ads

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

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


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

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


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

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

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

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