Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points p,q\in {\mathbb R}^2  is the line that consists of the points a  satisfying |pa|=|qa|  (where |pa|  is the distance between a  and p  ). For brevity, we will simply refer to these as bisectors.

bisectors

We say that a set {\cal P}  of n  points in {\mathbb R}^2  has no repeated bisectors if for every four distinct points a,b,c,d\in {\cal P}  the bisector of a  and b  is not identical to the bisector of c  and d  (that is, the configuration in the above figure is forbidden).

Conjecture. Let {\cal P}  be a set of n  points in {\mathbb R}^2  with no repeated bisectors. Then for any \varepsilon>0  the points of {\cal P}  determine \Omega(n^{2-\varepsilon})  distinct distances, .

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield O(n)  distinct distances: the vertices of a regular n  -gon and lattices.

intGridnGon

We can also play a bit with these examples. For example, by taking two regular n  -gons whose vertices are on two concentric circles, or by taking n  evenly spaced points on a line (that is, an n\times 1  lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and O(\frac{n^2}{\sqrt{\lg n}})  distinct distances. From the other direction, I can only show that every such set determines \Omega(n)  distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.

Continue reading

Incidences Outside of Discrete Geometry

Starting the 1980’s, more and more applications of geometric incidences have been found in discrete geometry. By now, one can arguably claim that there are countless such applications. More surprising are the applications of incidences outside of discrete geometry. In the past decade such applications have been discovered in harmonic analysis, theoretical computer science, number theory, and more. This post is my attempt to list these applications. If you are familiar with additional applications that I did not include, I’d be very interested to hear about them (in the comments below or by email).

Additive combinatorics: One of the main milestones in the study of the sum-product problem is a seminal paper by Elekes, in which he reduced the problem to a point-line incidence problem in {\mathbb R}^2  . This led to a variety of results in additive combinatorics that rely on incidences. Tao and Vu’s additive combinatorics book contains a full chapter that is dedicated to incidences. Konyagin and Shkredov’s recent improvement of the sum-product bound also relies indirectly on incidences (to bound the number of collinear triples in a lattice). For more examples, see here and here. Also, several additive combinatorics results in finite fields rely on incidence bounds in finite fields (e.g., see this paper).

Fourier restriction problems: Bourgain and Demeter rely on incidences to derive bounds for the discrete Fourier restriction to the four and five dimensional spheres. Incidences also appear in several related papers by the same authors (e.g., see here and here).

Number theory: A recent paper of Bombieri and Bourgain studies a type of additive energy of the Gaussian integers by relying on incidences with unit circles in {\mathbb R}^2  .

Error correcting codes: A family of papers by Dvir, Saraf, Wigderson, and others use incidences to study error correcting codes. For example, see this paper and this paper. These papers rely mainly on Sylvester-Gallai problems, which do not exactly fit the standard incidence problem formulation. Still, the authors of these paper and others consider these as proper incidence problems.

Extractors: Yet another novel use of incidences by Jean Bourgain. Bourgain relied on a finite field point-line incidence bound to build 2-source extractors. Recently this result has been superseded, as far as I understand without relying on incidences in any way.

Minors of totally positive matrices: Farber, Ray, and Smorodinsky used incidences to bound the number of times that a d\times d  minor can repeat in d\times n  a totally positive matrix.

It might also be interesting to state results that do not rely on incidences but do rely on the same polynomial partitioning technique (applied in the same way):

More restriction problems: Guth recently relied on polynomial partitioning to derive improved restriction estimates for smooth compact surface in {\mathbb R}^3  with strictly positive second fundamental form.

Range searching algorithms: Agarwal, Matoušek,and Sharir used polynomial partitioning to derive range searching algorithms for semialgebraic sets. A later simplification of this result, also based on polynomial partitioning, was derived by Matoušek and Patáková.

Any comments, corrections, and additions to the above list are welcome.

Incidences: Lower Bounds (part 8)

We continue to survey the known lower bounds for incidence problems (the previous post in this series can be found here). After a couple of posts in {\mathbb R}^3  we now return to {\mathbb R}^2  , to introduce a new technique that I recently learned about. This technique was discovered by Jozsef Solymosi, and is described in a work of Solymosi and Endre Szabó that is unpublished at this point. As seems to often be the case with results of Solymosi, it is quite simple and elegent. In {\mathbb R}^2  this technique yields bounds that can also be obtained from Elekes’ technique (discussed in a previous post), but in higher dimensions it leads to new bounds that are also tight (which would hopefully discuss in a future post). I would like to thank Jozsef Solymosi for allowing me to describe his technique in this blog, and to Frank de Zeeuw for discussions that led to this post.

Solymosi
Jozsef Solymosi.

Continue reading

A Boxes Riddle

I just recalled a nice mathematical riddle. I can’t remember where I originally read it, but it was likely in one of the blogs that are in the blogroll to the right.

Riddle. A game takes place where person A and person B are on the same team while person Z is their adversary. There are 100 boxes and 100 notes containing the numbers 1 to 100 (that is, each number is on exactly one note). The game goes as follows:

  • First, only Z and A are in the room. Z places one note in each box.
  • A sees the actions of Z and may afterwards pick two boxes and switch the notes in them (with each other). He may only perform one such switch.
  • Z sees the actions of A and then chooses a number N between 1 and 100.
  • A leaves the room while B enters it (they cannot exchange information during this process). Z tells B the number N.
  • Finally, B needs to find the box that contains the note with the number N. For this purpose, B may open up to 50 boxes.
If A chooses the 50 boxes at random, his probability of success is obviously 0.5. Do A and B have a strategy for increasing their chances? Or does Z have a strategy for which 0.5 is the best possible?

phd032108s

Feel free to write the answer as a comment. However, I think that it would be nice not to provide a full explanation here (that is, only to write whether it’s 0.5 or what better probability you can get).

(Later edit: I seem to be getting senile! I just noticed that I wrote the same riddle in a post two years ago…)

John von Neumann by Norman Macrae

So far, in my posts I have only written about popular science books that I liked. In this post I am making an exception, writing a rather negative review for a book that somewhat bothered me. I hope that writing such a post is not a big mistake. I guess I’ll soon find out…

JohnvonNeumann-LosAlamos
John von Neumann.

This post is about the biography of the mathematician John von Neumann by Norman Macrae. Perhaps I should start by stating that this is not really a popular science book, in the sense that it seems to avoid any discussion that is even a bit technical. The mathematical research of Von Neumann is stated very vaguely, and one mostly finds statements such as “… number theory, a branch of mathematics that is at once fascinating and frustrating” without any further details. When mentioning various scientists, the focus is usually about anecdotes, political opinions, and how smart they were. This last point usually involves some sort of ranking. According to Macrae, Aristotle was definitely smarter than Von Neumann, which was in turn smarter than any other mathematician of the 20th century. As another example, Von Neumann’s tutor Gabor Szego “was later to become one of the half dozen most distinguished Hungarian mathematicians of the twentieth century.” No explanation is provided for what these rankings are based on (occasionally they appear together with a statement by one person saying that another is very smart).

After reading my previous paragraph, you might claim that having a non-scientific biography of a mathematician can be a good thing, especially for readers who are not mathematicians. So instead of describing what the book does not contain, I now move to describe what it does. One thing that the book is filled with is strong opinions by the author, sometimes stated as facts. These opinions concern which government systems are better, which countries have the best school systems (apparently Japan is at the top), various historical speculation (“If Haber had not found a way to fix nitrogen from the air to make nitrates for explosives, blockaded Germany would have had to surrender from the 1914-18 war in about 1915”), among other topics. Some of these opinions concern someone being right or wrong about a subjective issue, without any further explanation (“… Eckert, whom in 1945 he rightly still wanted in his Princeton project as chief engineer”).

There are two contexts in which I found this abundance of opinions rather problematic. The first is when they appear in relation to mathematics or other exact sciences. My possibly-false impression is that Macrae does not have much of a scientific background. This is of course fine, and many wonderful popular science books were written by non-scientists. However, it makes Macrae’s many unusual assertions about science seem rather awkward. For example, after mentioning how important Von Neumann was to the development of mathematics comes the sentence “happily, and this is not sufficiently realized, it should be possible to get more like him”. The following sentence then explains that this is due to the lower financial needs of a mathematician (that is, paper and pencil). Claiming that von Neumann had a wider conception about computers, Macrae writes “He did not envisage these machines as today’s glorified typewriters. He hoped that experimenting scientists could use computers to start scientific revolutions that would change the planet.” Many such statements gave me a somewhat awkward feeling while reading the book.

The second case in which I found the many opinions in the book somewhat troubling is in the context of people with left-wing opinions. The book is PACKED with anti-left-wing statements, sometime without any visible connection to Von Neumann. One example (that also involves an awkward “technical” statement) is “He thought that those who believed in communism or socialism deserved the same sympathy as other simpletons who could not understand even linear equations.” After mentioning that various scientists supported Stalin or did not sufficiently oppose Hitler, Macrae writes “A common feature of clever men who occasionally supped on too-short spoons with Nazism or Communnism was that as kids they had never adequately learned to laugh”. It is clear that Macrae feels strongly about the subject, as the book contains statements such as “Among people who wanted to believe optimistic nonsense about western Europe or Soviet Russia…” and “… speaks in volumes to those who want to hear.” Such statements appear throughout the book and are possibly the most common topic that is discussed. Often such opinions are attributed to Von Neumann, although almost never with a reference or an actual quote (unlike many of Von Neumann’s statements on other topics). In fact, one finds sentences such as “I cannot find anything in his papers that suggests that he advocated that, although a lot of honest people thought that he did.”

Another issue is the extreme glorification of Von Neumann. I don’t think that many people doubt that Von Neumann was a genius that made a large impact on many fields, but the book takes this to the next level. It actually contains statements such as “the cleverest man in the mathematical world” and “Because Johnny was the world’s leading mathematical logician, he could clearly improve its logical design” (of the EDVAC computer).

I have more to say but I probably wrote too much already, so let me conclude this post. If you would like to hear how the smartest man of the 20th century had hawkish opinions, and that these were much better than all of those silly left-wing scientists such as Einstein, definitely read Macrae’s book. Personally I would appreciate a recommendation for a more standard biography of Von Neumann.

Incidences: Lower Bounds (part 7)

In this post we continue our survey of the known lower bounds for incidence problems (click here for the previous post in the series). In the current post we finally start discussing incidences with objects of dimension larger than one. The simplest such case seems to be incidences with unit spheres in {\mathbb R}^3  (i.e., spheres of radius one). We present two rather different constructions for this case. I am not aware of any paper that describes either of these constructions, and they appear to be folklore. If you are aware of a relevant reference, I will be happy to hear about it.

First construction: Inverse gnomonic projection. Our first construction is based on lower bounds for the Szemerédi-Trotter problem (e.g., see the first two posts of this series). It shows that m  points and n  unit spheres in {\mathbb R}^3  can yield \Omega(m^{2/3}n^{2/3}+m+n)  incidences.

For the requested values of m  and n  , consider a set \cal P  of m  points and a set \cal L  of n  lines, both in {\mathbb R}^2  and with I({\cal P},{\cal L})=\Theta(m^{2/3}n^{2/3}+m+n)  . We place this plane as the xy  -plane in {\mathbb R}^3  . We then perform an inverse gnomonic projection that takes \cal P  and \cal L  to a sphere in {\mathbb R}^3  , as follows. We set p=(0,0,1/\sqrt{2})  and denote by S  the sphere that is centered p  and is of radius 1/\sqrt{2}  . Notice that S  is tangent to the xy  -plane at the origin. The inverse projection takes a point q  in the xy  -plane to the intersection point of the line segment pq  and S  . One can easily verify that this mapping is a bijection between the xy  -plane and the lower half of S  ; e.g., see the following figure.

Gnomonic

Continue reading

Incidences: Lower Bounds (part 6)

Last year I surveyed the known lower bounds for incidence problems in the plane (click here for the previous post in the series). I now return to this series of posts to survey the lower bounds that are known in higher dimensions.

From what is already known about incidences with curves in {\mathbb R}^d  , it seems likely that the maximum number of incidences is usually obtained when the points and curves lie in a constant-degree two-dimensional surface. For example, Guth and Katz proved that the maximum number of point-line incidences in {\mathbb R}^3  is obtained when the points and lines are in a common plane. While incidences with general curves are not fully understood even in the plane, various recent results hint that this is also the case for general curves in {\mathbb R}^d  (for example, see here and here).

Due to the above, incidences with curves in {\mathbb R}^d  are usually studied with a restriction on the number of curves that can be contained in various types of constant-degree surfaces; another reason for studying such restrictions is that they arise from interesting problems. For example, Guth and Katz proved the following theorem.

Theorem 1. Let \cal P  be a set of m  points and let \cal L  be a set of n lines, both in {\mathbb R}^3  , such that every plane contains O(\sqrt{n})  lines of \cal L  . Then

I({\cal P},{\cal L}) = O\left(m^{1/2}n^{3/4}+n+m\right).

Currently, all of the known lower bounds for incidences with curves in {\mathbb R}^d  are simple extensions of the planar bounds that we studied in the previous posts. In the current post we only present one such bound. Specifically, we extend Elekes’ planar construction to show that Theorem 1 is tight. The following posts will focus on the more challenging issues that arise for incidences with higher-dimensional objects.

Claim 1. Consider integers m  and n  that satisfy m \ge 4\sqrt{n}  and m\le n^{3/2}  . Then there exist a set \cal P  of m  points and a set \cal L  of n  lines, both in {\mathbb R}^3  , such that every plane contains O(\sqrt{n})  lines of \cal L  and

I({\cal P},{\cal L})= \Theta\left(m^{1/2}n^{3/4} \right).

Proof.     Set k = m^{1/2}/(2n^{1/4})  and \ell = \sqrt{2}n^{3/8}/m^{1/4}  , and let

{\cal P} = \left\{(r,s,t)\in {\mathbb N}^3 : 1\le r \le k \ \text{ and } \ 1\le s,t \le 2k\ell \right\}.

For our set of lines, we take

{\cal L} = \left\{y-ax-b,z-cx-d : 1 \le a,c \le \ell \ \text{ and } \ 1\le b,d \le k\ell \right\}.

First, notice that we indeed have

|{\cal P}| = k (2k\ell)^2 = 4k^3 \ell^2 = 4 \cdot \frac{m^{3/2}}{8n^{3/4}} \cdot \frac{2n^{3/4}}{m^{1/2}} = m,
|{\cal L}| = k^2\ell^4 = \frac{m}{4n^{1/2}} \cdot \frac{4n^{3/2}}{m} = n.

For any line \gamma \in {\cal L}  and 1\le r \le k  , there exists a unique point in \cal P  that is incident to \gamma  and whose x  -coordinate is r  . That is, every line of \cal L  is incident to exactly k  points of \cal P  . Thus, we have

I({\cal P},{\cal L}) = k \cdot n =  \frac{m^{1/2}}{2n^{1/4}} \cdot n= \frac{m^{1/2}n^{3/4}}{2}.

It remains to verify that every plane contains O(\sqrt{n})  lines of \cal L  . We first consider a plane h  that is defined by an equation of the form y=sx+t  (that is, a plane that contains lines that are parallel to the z  -axis). Such a plane h  contains exactly the lines that have a=s  and b=t  in their definition in \cal L  . There are k\ell^2= \Theta(\sqrt{n})  such lines.

Next, consider a plane h  that is not defined by an equation of the form y=sx+t  . In this case, for every choice of a,b  , the plane h' =Z(y-ax-b)  intersects h  in a unique line. That is, for every choice of a,b  as in the definition of \cal L  , there is at most one line of \cal L  with these parameters that is contained in h  . Thus, h  contains k\ell^2= \Theta(\sqrt{n})  lines of \cal L  .