Guest Post: Distinct distances, and the use of continuous mathematics in discrete geometry.

Guest Post: Distinct distances, and the use of continuous mathematics in discrete geometry.: "Nabil Mustafa specializes in problems of discrete geometry, and has spent time on problems related to the distinct distance problem. He offers a broader perspective on the new distinct distances result and related breakthroughts in discrete geometry. For a detailed breakdown of the Guth/Katz paper, see Terry Tao's latest opus.As usual, I take responsibility for any mistakes introduced in the editing process.



I think the days when the 'Feynman method' was all that was needed to make progress on basic problems in Discrete Geometry are over. Recently there have been a slew of results which make progress on long-standing open problems in Discrete and Computational Geometry that use techniques from a variety of areas in mathematics: algebraic geometry, algebraic topology, complex analysis and so on.



This is wonderful news for the field. Though, two things to consider:



1. So far, apart from the kind of work going in 'Computational Topology', this has mostly been a one-way street. There have been fewer cases of discrete and computational geometers going into topology, algebraic geometry etc. and making a similar impact there. Similarly, there are very few collaborations between mathematicians in other areas, and discrete geometers (ed: Mulmuley also argues that the GCT program will only come to fruition when this reverse direction starts happening)



2. From my experience, current graduate students, by-and-large, still seem to be stuck with the general outlook that 'If I'm clever enough, and think hard enough, I can solve any problem directly'. Such optimism alwayscheers me up. I used to think that too, but the more I learn about other areas, and as the recent work reveals power of techniques, it has become clear to me that it is misguided to think that. I would really advise students to take courses in algebraic topology, differential geometry and so on.



Below I list some such recent breakthroughs.



First-selection Lemma.

Given n points in $R^d$, can one find a point in "many" simplices spanned by these points ?

This has been studied for more than 30 years, with several partial results. The current best result was published this year by M. Gromov, which in fact proves a stronger topological theorem, with better bounds than for restricted earlier cases. Matousek and Wagner have improved this bound slightly for 3D by improving a combinatorial part of Gromov's argument. Gromov's argument is a complicated topological argument that I did not have the background to follow. J. Matousek gave a nice talk at the Bernoulli conference in September with the title 'Also Sprach Gromov'!



2. Colored Tverberg Theorem.

Let be disjoint subsets of , called colors, each of cardinality at least . A -subset of is said to be multicolored if for . Let be an integer, and let denote the smallest value such that for every collection of colors of size at least there exist disjoint multicolored sets such that

The conjecture is that $T(r,d) = r$, and this was proved recently via topological arguments (for all $r$ such that $r+1$ is prime) by Blagojevic, Matschke, and Ziegler (see Gil Kalai's blog for a detailed post on this). Matousek, Tancer and Wagner have translated this argument to a geometric proof. As they state in the abstract, 'The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience.'



3. Distinct Distances problem.



The Guth-Katz dramatically improves the best known bound via techniques from algebraic geometry. Terry Tao has more details on this.



4. Joints problem.

A joint is a point formed by the intersection of three non-coplanar lines in 3D. What is the maximum number of joints achievable by a collection of $n$ lines in 3D ?

This was again solved by Guth and Katz via techniques from algebraic geometry. It was subsequently simplified wonderfully by Elekes, Kaplan and Sharir, and Kaplan, Sharir and Shustin.



5. Lower-bounds for eps-nets.



It was very widely believed that for "natural" geometric objects, eps-nets of linear-size should exist. Shockingly, Alon showed that an easy application of Hales-Jewett density version immediately gives a non-linear lower-bound for a simple geometric-system in the plane. While DHJ is a combinatorial result, it was first 'proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemeredi's theorem'. Like earlier proofs, it is possible to 'de-ergodicize' it (the polymath project).



6. Regression-depth partitioning conjecture.



(ed: see here for a description of regression depth - it's similar to halfspace depth)



Partial results were shown by Amenta-Bern-Eppstein-Teng in 2000. Recently almost proven by Karasev using topological techniques that I do not understand.



This is just a partial list, there are probably several others that I have missed.

"