On the Erdős distinct distances problem in the plane

Abstract

In this paper, we prove that a set of $N$ points in ${\bf R}^2$ has at least $c{N \over \log N}$ distinct distances, thus obtaining the sharp exponent in a problem of Erdős. We follow the setup of Elekes and Sharir which, in the spirit of the Erlangen program, allows us to study the problem in the group of rigid motions of the plane. This converts the problem to one of point-line incidences in space. We introduce two new ideas in our proof. In order to control points where many lines are incident, we create a cell decomposition using the polynomial ham sandwich theorem. This creates a dichotomy: either most of the points are in the interiors of the cells, in which case we immediately get sharp results or, alternatively, the points lie on the walls of the cells, in which case they are in the zero-set of a polynomial of suprisingly low degree, and we may apply the algebraic method. In order to control points incident to only two lines, we use the flecnode polynomial of the Rev. George Salmon to conclude that most of the lines lie on a ruled surface. Then we use the geometry of ruled surfaces to complete the proof.

  • [A] Go to document T. M. Apostol, Introduction to Analytic Number Theory, New York: Springer-Verlag, 1976.
    @book{A, mrkey = {0434929},
      author = {Apostol, Tom M.},
      title = {Introduction to Analytic Number Theory},
      series = {Undergraduate Texts in Mathematics},
      publisher = {Springer-Verlag},
      year = {1976},
      pages = {xii+338},
      mrclass = {10-01 (10AXX 10HXX)},
      mrnumber = {0434929},
      mrreviewer = {E. Grosswald},
      address = {New York},
      zblnumber = {0335.10001},
      doi = {10.1007/978-1-4757-5579-4},
      }
  • [CSzT] Go to document F. R. K. Chung, E. Szemerédi, and W. T. Trotter, "The number of different distances determined by a set of points in the Euclidean plane," Discrete Comput. Geom., vol. 7, iss. 1, pp. 1-11, 1992.
    @article{CSzT, mrkey = {1134448},
      author = {Chung, Fan R. K. and Szemer{é}di, E. and Trotter, W. T.},
      title = {The number of different distances determined by a set of points in the {E}uclidean plane},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {7},
      year = {1992},
      number = {1},
      pages = {1--11},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52C10},
      mrnumber = {1134448},
      mrreviewer = {L. M. Kelly},
      doi = {10.1007/BF02187820},
      zblnumber = {0755.52005},
      }
  • [CEGPSSS] Go to document B. Chazelle, H. Edelsbrunner, L. J. Guibas, and et al., "Counting and cutting cycles of lines and rods in space," Comput. Geom., vol. 1, iss. 6, pp. 305-323, 1992.
    @article{CEGPSSS, mrkey = {1172840},
      author = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas J. and et al.},
      title = {Counting and cutting cycles of lines and rods in space},
      journal = {Comput. Geom.},
      fjournal = {Computational Geometry. Theory and Applications},
      volume = {1},
      year = {1992},
      number = {6},
      pages = {305--323},
      issn = {0925-7721},
      mrclass = {68U05 (65Y25 68Q25 68R05)},
      mrnumber = {1172840},
      mrreviewer = {Henk Meijer},
      doi = {10.1016/0925-7721(92)90009-H},
      ZBLNUMBER = {0748.68082},
      }
  • [CEGSW] Go to document K. L. Clarkson, H. Edelsbrunner, L. J. Guibas, M. Sharir, and E. Welzl, "Combinatorial complexity bounds for arrangements of curves and spheres," Discrete Comput. Geom., vol. 5, iss. 2, pp. 99-160, 1990.
    @article{CEGSW, mrkey = {1032370},
      author = {Clarkson, Kenneth L. and Edelsbrunner, Herbert and Guibas, Leonidas J. and Sharir, Micha and Welzl, Emo},
      title = {Combinatorial complexity bounds for arrangements of curves and spheres},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {5},
      year = {1990},
      number = {2},
      pages = {99--160},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52B55 (68Q25 68U05)},
      mrnumber = {1032370},
      doi = {10.1007/BF02187783},
      zblnumber = {0704.51003},
      }
  • [D] Go to document Z. Dvir, "On the size of Kakeya sets in finite fields," J. Amer. Math. Soc., vol. 22, iss. 4, pp. 1093-1097, 2009.
    @article{D, mrkey = {2525780},
      author = {Dvir, Zeev},
      title = {On the size of {K}akeya sets in finite fields},
      journal = {J. Amer. Math. Soc.},
      fjournal = {Journal of the American Mathematical Society},
      volume = {22},
      year = {2009},
      number = {4},
      pages = {1093--1097},
      issn = {0894-0347},
      mrclass = {52C17 (05B25 42B25)},
      mrnumber = {2525780},
      mrreviewer = {Anthony Carbery},
      doi = {10.1090/S0894-0347-08-00607-3},
      zblnumber = {1202.52021},
      }
  • [E] Go to document P. Erdös, "On sets of distances of $n$ points," Amer. Math. Monthly, vol. 53, pp. 248-250, 1946.
    @article{E, mrkey = {0015796},
      author = {Erd{ö}s, P.},
      title = {On sets of distances of {$n$} points},
      journal = {Amer. Math. Monthly},
      fjournal = {The American Mathematical Monthly},
      volume = {53},
      year = {1946},
      pages = {248--250},
      issn = {0002-9890},
      mrclass = {48.0X},
      mrnumber = {0015796},
      mrreviewer = {I. Kaplansky},
      doi = {10.2307/2305092},
      zblnumber = {0060.34805},
      }
  • [EKS] Go to document G. Elekes, H. Kaplan, and M. Sharir, "On lines, joints, and incidences in three dimensions," J. Combin. Theory Ser. A, vol. 118, iss. 3, pp. 962-977, 2011.
    @article{EKS, mrkey = {2763049},
      author = {Elekes, Gy{ö}rgy and Kaplan, Haim and Sharir, Micha},
      title = {On lines, joints, and incidences in three dimensions},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {118},
      year = {2011},
      number = {3},
      pages = {962--977},
      issn = {0097-3165},
      coden = {JCBTA7},
      mrclass = {52B55 (05B25)},
      mrnumber = {2763049},
      doi = {10.1016/j.jcta.2010.11.008},
      zblnumber = {1232.05041},
      }
  • [ES] Go to document G. Elekes and M. Sharir, "Incidences in three dimensions and distinct distances in the plane," Combin. Probab. Comput., vol. 20, iss. 4, pp. 571-608, 2011.
    @article{ES, mrkey = {2805398},
      author = {Elekes, Gy{ö}rgy and Sharir, Micha},
      title = {Incidences in three dimensions and distinct distances in the plane},
      journal = {Combin. Probab. Comput.},
      fjournal = {Combinatorics, Probability and Computing},
      volume = {20},
      year = {2011},
      number = {4},
      pages = {571--608},
      issn = {0963-5483},
      mrclass = {52B55 (68U05)},
      mrnumber = {2805398},
      doi = {10.1017/S0963548311000137},
      zblnumber = {1222.52016},
      }
  • [FS] Go to document S. Feldman and M. Sharir, "An improved bound for joints in arrangements of lines in space," Discrete Comput. Geom., vol. 33, iss. 2, pp. 307-320, 2005.
    @article{FS, mrkey = {2121298},
      author = {Feldman, Sharona and Sharir, Micha},
      title = {An improved bound for joints in arrangements of lines in space},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {33},
      year = {2005},
      number = {2},
      pages = {307--320},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52C35 (68U05)},
      mrnumber = {2121298},
      doi = {10.1007/s00454-004-1093-7},
      zblnumber = {1068.52032},
      }
  • [GIS] J. Garibaldi, A. Iosevich, and S. Senger, The Erdős Distance Problem, Amer. Math. Soc., 2011, vol. 56.
    @book{GIS, mrkey = {2721878},
      author = {Garibaldi, Julia and Iosevich, Alex and Senger, Steven},
      title = {The {E}rdős Distance Problem},
      series = {Student Math. Library},
      volume = {56},
      publisher = {Amer. Math. Soc.},
      year = {2011},
      pages = {xii+150},
      isbn = {978-0-8218-5281-1},
      mrclass = {52-01 (05-01 11-01 42-01 51-01)},
      mrnumber = {2721878},
      mrreviewer = {Michael Weiss},
      zblnumber = {1234.00002},
      }
  • [G] Go to document L. Guth, "The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture," Acta Math., vol. 205, iss. 2, pp. 263-286, 2010.
    @article{G, mrkey = {2746348},
      author = {Guth, Larry},
      title = {The endpoint case of the {B}ennett-{C}arbery-{T}ao multilinear {K}akeya conjecture},
      journal = {Acta Math.},
      fjournal = {Acta Mathematica},
      volume = {205},
      year = {2010},
      number = {2},
      pages = {263--286},
      issn = {0001-5962},
      coden = {ACMAA8},
      mrclass = {42B15 (28A75 52A38)},
      mrnumber = {2746348},
      mrreviewer = {Dmitry Ryabogin},
      doi = {10.1007/s11511-010-0055-6},
      zblnumber = {1210.52004},
      }
  • [GK] Go to document L. Guth and N. H. Katz, "Algebraic methods in discrete analogs of the Kakeya problem," Adv. Math., vol. 225, iss. 5, pp. 2828-2839, 2010.
    @article{GK, mrkey = {2680185},
      author = {Guth, Larry and Katz, Nets Hawk},
      title = {Algebraic methods in discrete analogs of the {K}akeya problem},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {225},
      year = {2010},
      number = {5},
      pages = {2828--2839},
      issn = {0001-8708},
      coden = {ADMTA4},
      mrclass = {52B55 (14N05 51E99)},
      mrnumber = {2680185},
      doi = {10.1016/j.aim.2010.05.015},
      zblnumber = {1202.52022},
      }
  • [KMS] Go to document H. Kaplan, J. Matouvsek, and M. Sharir, "Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique," Discrete Comput. Geom., vol. 48, iss. 3, pp. 499-517, 2012.
    @article{KMS, mrkey = {2957631},
      author = {Kaplan, Haim and Matou{š}ek, Ji{\v{r}}{\'ı} and Sharir, Micha},
      title = {Simple proofs of classical theorems in discrete geometry via the {G}uth-{K}atz polynomial partitioning technique},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {48},
      year = {2012},
      number = {3},
      pages = {499--517},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52C10},
      mrnumber = {2957631},
      mrreviewer = {Pablo Sober{ó}n},
      doi = {10.1007/s00454-012-9443-3},
      zblnumber = {1259.52008},
      }
  • [KSS] Go to document H. Kaplan, M. Sharir, and E. Shustin, "On lines and joints," Discrete Comput. Geom., vol. 44, iss. 4, pp. 838-843, 2010.
    @article{KSS, mrkey = {2728035},
      author = {Kaplan, Haim and Sharir, Micha and Shustin, Eugenii},
      title = {On lines and joints},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {44},
      year = {2010},
      number = {4},
      pages = {838--843},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52C30 (52B05 68U05)},
      mrnumber = {2728035},
      mrreviewer = {Lyuba S. Alboul},
      doi = {10.1007/s00454-010-9246-3},
      zblnumber = {1250.52012},
      }
  • [KT] Go to document N. H. Katz and G. Tardos, "A new entropy inequality for the Erdős distance problem," in Towards a Theory of Geometric Graphs, Amer. Math. Soc., Providence, RI, 2004, vol. 342, pp. 119-126.
    @incollection{KT, mrkey = {2065258},
      author = {Katz, Nets Hawk and Tardos, G{á}bor},
      title = {A new entropy inequality for the {E}rdős distance problem},
      booktitle = {Towards a Theory of Geometric Graphs},
      series = {Contemp. Math.},
      volume = {342},
      pages = {119--126},
      publisher = {Amer. Math. Soc., Providence, RI},
      year = {2004},
      mrclass = {52C10 (05A10 11B75)},
      mrnumber = {2065258},
      mrreviewer = {Pavel Valtr},
      doi = {10.1090/conm/342/06136},
      zblnumber = {1069.52017},
      }
  • [Land] J. M. Landsberg, "Is a linear space contained in a submanifold? On the number of derivatives needed to tell," J. Reine Angew. Math., vol. 508, pp. 53-60, 1999.
    @article{Land, mrkey = {1676869},
      author = {Landsberg, J. M.},
      title = {Is a linear space contained in a submanifold? {O}n the number of derivatives needed to tell},
      journal = {J. Reine Angew. Math.},
      fjournal = {Journal für die Reine und Angewandte Mathematik. [Crelle's Journal]},
      volume = {508},
      year = {1999},
      pages = {53--60},
      issn = {0075-4102},
      coden = {JRMAA8},
      mrclass = {14J99 (14N99 32B10 53A20)},
      mrnumber = {1676869},
      mrreviewer = {Fyodor L. Zak},
      zblnumber = {1067.14514},
      }
  • [M] Go to document L. Moser, "On the different distances determined by $n$ points," Amer. Math. Monthly, vol. 59, pp. 85-91, 1952.
    @article{M, mrkey = {0046663},
      author = {Moser, Leo},
      title = {On the different distances determined by {$n$} points},
      journal = {Amer. Math. Monthly},
      fjournal = {The American Mathematical Monthly},
      volume = {59},
      year = {1952},
      pages = {85--91},
      issn = {0002-9890},
      mrclass = {48.0X},
      mrnumber = {0046663},
      mrreviewer = {P. Erd{ö}s},
      doi = {10.2307/2307105},
      zblnumber = {0046.14101},
      }
  • [Q] Go to document R. Quilodrán, "The joints problem in $\Bbb R^n$," SIAM J. Discrete Math., vol. 23, iss. 4, pp. 2211-2213, 2009/10.
    @article{Q, mrkey = {2594983},
      author = {Quilodr{á}n, Ren{é}},
      title = {The joints problem in {$\Bbb R\sp n$}},
      journal = {SIAM J. Discrete Math.},
      fjournal = {SIAM Journal on Discrete Mathematics},
      volume = {23},
      year = {2009/10},
      number = {4},
      pages = {2211--2213},
      issn = {0895-4801},
      mrclass = {05B25 (52C35 52C45)},
      mrnumber = {2594983},
      mrreviewer = {Joseph Zaks},
      doi = {10.1137/090763160},
      zblnumber = {1228.05106},
      }
  • [Salm] G. Salmon, A Treatise on the Analytic Geometry of Three Dimensions, New York: edited by C. H. Rowe, Chelsea Publishing Company, 1958.
    @book{Salm, mrkey = {0094753},
      author = {Salmon, George},
      title = {A Treatise on the Analytic Geometry of Three Dimensions},
      note = {revised by R. A. P. Rogers., 7th ed., Vol. 1},
      publisher = {edited by C. H. Rowe, Chelsea Publishing Company},
      address = {New York},
      year = {1958},
      pages = {xxiv+470},
      mrclass = {50.00},
      mrnumber = {0094753},
      jfmnumber = {55.0996.05},
      }
  • [Schl] Go to document W. Schlag, "A geometric inequality with applications to the Kakeya problem in three dimensions," Geom. Funct. Anal., vol. 8, iss. 3, pp. 606-625, 1998.
    @article{Schl, mrkey = {1631271},
      author = {Schlag, W.},
      title = {A geometric inequality with applications to the {K}akeya problem in three dimensions},
      journal = {Geom. Funct. Anal.},
      fjournal = {Geometric and Functional Analysis},
      volume = {8},
      year = {1998},
      number = {3},
      pages = {606--625},
      issn = {1016-443X},
      coden = {GFANFB},
      mrclass = {42B25},
      mrnumber = {1631271},
      mrreviewer = {Stephen Buckley},
      doi = {10.1007/s000390050068},
      zblnumber = {0939.42012},
      }
  • [Seg] B. Segre, "The maximum number of lines lying on a quartic surface," Quart. J. Math., Oxford Ser., vol. 14, pp. 86-96, 1943.
    @article{Seg, mrkey = {0010431},
      author = {Segre, B.},
      title = {The maximum number of lines lying on a quartic surface},
      journal = {Quart. J. Math., Oxford Ser.},
      fjournal = {The Quarterly Journal of Mathematics. Oxford. Second Series},
      volume = {14},
      year = {1943},
      pages = {86--96},
      issn = {0033-5606},
      mrclass = {14.0X},
      mrnumber = {0010431},
      mrreviewer = {V. Snyder},
      zblnumber = {0063.06860},
      }
  • [SW] Go to document M. Sharir and E. Welzl, "Point-line incidences in space," Combin. Probab. Comput., vol. 13, iss. 2, pp. 203-220, 2004.
    @article{SW, mrkey = {2047237},
      author = {Sharir, Micha and Welzl, Emo},
      title = {Point-line incidences in space},
      journal = {Combin. Probab. Comput.},
      fjournal = {Combinatorics, Probability and Computing},
      volume = {13},
      year = {2004},
      number = {2},
      pages = {203--220},
      issn = {0963-5483},
      mrclass = {52B55 (05B25 68U05)},
      mrnumber = {2047237},
      doi = {10.1017/S0963548303005935},
      zblnumber = {1066.52028},
      }
  • [SoTo] Go to document J. Solymosi and C. D. Tóth, "Distinct distances in the plane," Discrete Comput. Geom., vol. 25, iss. 4, pp. 629-634, 2001.
    @article{SoTo, mrkey = {1838423},
      author = {Solymosi, J. and T{ó}th, Cs. D.},
      title = {Distinct distances in the plane},
      journal = {Discrete Comput. Geom.},
      fjournal = {Discrete \& Computational Geometry. An International Journal of Mathematics and Computer Science},
      volume = {25},
      year = {2001},
      number = {4},
      pages = {629--634},
      issn = {0179-5376},
      coden = {DCGEER},
      mrclass = {52C10},
      mrnumber = {1838423},
      doi = {10.1007/s00454-001-0009-z},
      zblnumber = {0988.52027},
      }
  • [ST] Go to document A. H. Stone and J. W. Tukey, "Generalized “sandwich” theorems," Duke Math. J., vol. 9, pp. 356-359, 1942.
    @article{ST, mrkey = {0007036},
      author = {Stone, A. H. and Tukey, J. W.},
      title = {Generalized ``sandwich'' theorems},
      journal = {Duke Math. J.},
      fjournal = {Duke Mathematical Journal},
      volume = {9},
      year = {1942},
      pages = {356--359},
      issn = {0012-7094},
      mrclass = {27.2X},
      mrnumber = {0007036},
      mrreviewer = {N. Dunford},
      doi = {10.1215/S0012-7094-42-00925-6},
      zblnumber = {0061.38405},
      }
  • [Sz] Go to document L. A. Székely, "Crossing numbers and hard Erdős problems in discrete geometry," Combin. Probab. Comput., vol. 6, iss. 3, pp. 353-358, 1997.
    @article{Sz, mrkey = {1464571},
      author = {Sz{é}kely, L{á}szl{ó} A.},
      title = {Crossing numbers and hard {E}rdős problems in discrete geometry},
      journal = {Combin. Probab. Comput.},
      fjournal = {Combinatorics, Probability and Computing},
      volume = {6},
      year = {1997},
      number = {3},
      pages = {353--358},
      issn = {0963-5483},
      mrclass = {52C10 (05C10)},
      mrnumber = {1464571},
      mrreviewer = {W. Moser},
      doi = {10.1017/S0963548397002976},
      zblnumber = {0890.05022},
      }
  • [SzT] Go to document E. Szemerédi and W. T. Trotter Jr., "Extremal problems in discrete geometry," Combinatorica, vol. 3, iss. 3-4, pp. 381-392, 1983.
    @article{SzT, mrkey = {0729791},
      author = {Szemer{é}di, Endre and Trotter, Jr., William T.},
      title = {Extremal problems in discrete geometry},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal of the János Bolyai Mathematical Society},
      volume = {3},
      year = {1983},
      number = {3-4},
      pages = {381--392},
      issn = {0209-9683},
      coden = {COMBDI},
      mrclass = {52A37 (05B25)},
      mrnumber = {0729791},
      mrreviewer = {Thomas O. Strommer},
      doi = {10.1007/BF02579194},
      zblnumber = {0541.05012},
      }
  • [T] Go to document G. Tardos, "On distinct sums and distinct distances," Adv. Math., vol. 180, iss. 1, pp. 275-289, 2003.
    @article{T, mrkey = {2019225},
      author = {Tardos, G{á}bor},
      title = {On distinct sums and distinct distances},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {180},
      year = {2003},
      number = {1},
      pages = {275--289},
      issn = {0001-8708},
      coden = {ADMTA4},
      mrclass = {11B75 (52C10)},
      mrnumber = {2019225},
      mrreviewer = {Teturo Kamae},
      doi = {10.1016/S0001-8708(03)00004-5},
      zblnumber = {1039.52014},
      }

Authors

Larry Guth

Department of Mathematics, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA 02139-2387

Nets Hawk Katz

Mathematics 253-37, California Institute of Technology, Pasadena, CA 91125