On the Erdős distinct distances problem in the plane. (English) Zbl 1310.52019

Guth, Larry; Katz, Nets Hawk

Ann. Math. (2) 181, No. 1, 155-190 (2015).

Paul Erdős considered his greatest contribution to geometry posing the following two problems in 1946: what is the largest number of unit distances among \(n\) points in the plane? and what is the minimum number of distinct distances among \(n\) points in the plane? Both problems have been under intensive investigation and they are still unsolved. For the distinct distances problems lattice points with coordinates \(0\leq x,y\leq \sqrt{n} \) give \(O(n/\sqrt{\log n})\) distinct distances and Erdős conjectured that this is about the correct quantity. The paper under review makes a major breakthrough proving a \(\Omega(n/{\log n})\) lower bound. Terence Tao’s blog beautifully explains the history and the ideas behind the proof under https://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/.

Reviewer: László A. Székely (Columbia)

MSC:

52C10

Erdős problems and related topics of discrete geometry

Keywords:

distinct distances; incidence geometry; polynomial ham sandwich; polynomial method; ruled surface

References:

[1]	T. M. Apostol, Introduction to Analytic Number Theory, New York: Springer-Verlag, 1976. · Zbl 0335.10001 · doi:10.1007/978-1-4757-5579-4
[2]	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. · Zbl 0755.52005 · doi:10.1007/BF02187820
[3]	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. · Zbl 0748.68082 · doi:10.1016/0925-7721(92)90009-H
[4]	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. · Zbl 0704.51003 · doi:10.1007/BF02187783
[5]	Z. Dvir, ”On the size of Kakeya sets in finite fields,” J. Amer. Math. Soc., vol. 22, iss. 4, pp. 1093-1097, 2009. · Zbl 1202.52021 · doi:10.1090/S0894-0347-08-00607-3
[6]	P. Erdös, ”On sets of distances of \(n\) points,” Amer. Math. Monthly, vol. 53, pp. 248-250, 1946. · Zbl 0060.34805 · doi:10.2307/2305092
[7]	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. · Zbl 1232.05041 · doi:10.1016/j.jcta.2010.11.008
[8]	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. · Zbl 1222.52016 · doi:10.1017/S0963548311000137
[9]	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. · Zbl 1068.52032 · doi:10.1007/s00454-004-1093-7
[10]	J. Garibaldi, A. Iosevich, and S. Senger, The Erd\Hos Distance Problem, Amer. Math. Soc., 2011, vol. 56. · Zbl 1234.00002
[11]	L. Guth, ”The endpoint case of the Bennett-Carbery-Tao multilinear Kakeya conjecture,” Acta Math., vol. 205, iss. 2, pp. 263-286, 2010. · Zbl 1210.52004 · doi:10.1007/s11511-010-0055-6
[12]	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. · Zbl 1202.52022 · doi:10.1016/j.aim.2010.05.015
[13]	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. · Zbl 1259.52008 · doi:10.1007/s00454-012-9443-3
[14]	H. Kaplan, M. Sharir, and E. Shustin, ”On lines and joints,” Discrete Comput. Geom., vol. 44, iss. 4, pp. 838-843, 2010. · Zbl 1250.52012 · doi:10.1007/s00454-010-9246-3
[15]	N. H. Katz and G. Tardos, ”A new entropy inequality for the Erd\Hos distance problem,” in Towards a Theory of Geometric Graphs, Amer. Math. Soc., Providence, RI, 2004, vol. 342, pp. 119-126. · Zbl 1069.52017 · doi:10.1090/conm/342/06136
[16]	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. · Zbl 1067.14514 · doi:10.1515/crll.1999.030
[17]	L. Moser, ”On the different distances determined by \(n\) points,” Amer. Math. Monthly, vol. 59, pp. 85-91, 1952. · Zbl 0046.14101 · doi:10.2307/2307105
[18]	R. Quilodrán, ”The joints problem in \(\mathbb R^n\),” SIAM J. Discrete Math., vol. 23, iss. 4, pp. 2211-2213, 2009/10. · Zbl 1228.05106 · doi:10.1137/090763160
[19]	G. Salmon, A Treatise on the Analytic Geometry of Three Dimensions, New York: edited by C. H. Rowe, Chelsea Publishing Company, 1958.
[20]	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. · Zbl 0939.42012 · doi:10.1007/s000390050068
[21]	B. Segre, ”The maximum number of lines lying on a quartic surface,” Quart. J. Math., Oxford Ser., vol. 14, pp. 86-96, 1943. · Zbl 0063.06860
[22]	M. Sharir and E. Welzl, ”Point-line incidences in space,” Combin. Probab. Comput., vol. 13, iss. 2, pp. 203-220, 2004. · Zbl 1066.52028 · doi:10.1017/S0963548303005935
[23]	J. Solymosi and C. D. Tóth, ”Distinct distances in the plane,” Discrete Comput. Geom., vol. 25, iss. 4, pp. 629-634, 2001. · Zbl 0988.52027 · doi:10.1007/s00454-001-0009-z
[24]	A. H. Stone and J. W. Tukey, ”Generalized “sandwich” theorems,” Duke Math. J., vol. 9, pp. 356-359, 1942. · Zbl 0061.38405 · doi:10.1215/S0012-7094-42-00925-6
[25]	L. A. Székely, ”Crossing numbers and hard Erd\Hos problems in discrete geometry,” Combin. Probab. Comput., vol. 6, iss. 3, pp. 353-358, 1997. · Zbl 0890.05022 · doi:10.1017/S0963548397002976
[26]	E. Szemerédi and W. T. Trotter Jr., ”Extremal problems in discrete geometry,” Combinatorica, vol. 3, iss. 3-4, pp. 381-392, 1983. · Zbl 0541.05012 · doi:10.1007/BF02579194
[27]	G. Tardos, ”On distinct sums and distinct distances,” Adv. Math., vol. 180, iss. 1, pp. 275-289, 2003. · Zbl 1039.52014 · doi:10.1016/S0001-8708(03)00004-5