Month: September 2013

by

Books and quotes

This post is about two popular-mathematics books the I recently read:

MY BRAIN IS OPEN: The Mathematical Journeys of Paul Erdős / Bruce Schechter

On one occasion, Erdős met a mathematician and asked him where he was from. “Vancouver,” the mathematician replied. “Oh, then you must know my good friend Elliot Mendelson”, Erdős said. The reply was “I AM your good friend Elliot Mendelson.”

Several years ago I read another biography of Erdős by Paul Hoffman, which was nice, though focused mainly on Erdős’s eccentricities. I think that Schechter’s biography would appeal more to mathematicians, since it consists of a lower dose of eccentricities and of a higher dose of details about the mathematical world. For example, it was very interesting to read about how a Hungarian mathematics journal for high school students helped in the nurturing of many great mathematicians, and about the events that led to the elementary proof for the prime number theorem by Selberg and Erdős. I definitely recommend this book.

For those who are looking for an even lower dose of eccentricities and more details about the mathematical world, I recommend the piece “In and Out of Hungary, Paul Erdös, His Friends, and Times” by László Babai. It can be found in volume 2 of Combinatorics, Paul Erdös is eighty, and it contains many details about the Hungarian mathematical world (and about 20-th century Hungarian history in general).

my-brain-is-open-mathematical-journeys-paul-erdos-bruce-schechter-paperback-cover-artMathCranks

Mathematical Cranks / Underwood Dudley

Represent heaven, the home of God, as a vector space of infinite dimension over some field F known to god but unknown to us, in which the activities of God are quantifiable. Lengths will be measured (Revelation chapter 21 verse 15) in the usual way, as the square roots of the inner self-products of vectors (assuming heaven to be euclidean).

Continue reading →

by

The limitations of the Elekes-Sharir framework

In a previous series of posts, we discussed the Elekes-Sharir(-Guth-Katz) framework. By using this framework, Guth and Katz derived the bound D(n)=\Omega(n/\log n) for the Erdős distinct distances problem (where D({\cal P}) denotes the number of distinct distances that are determined by pairs of points from \cal P , and D(n) = \min_{|{\cal P}|=n}D({\cal P}) ). The best known upper bound is D(n)=O(n/\sqrt{\log n}) , which leaves a gap of \Theta(\sqrt{\log n}) . The common belief is that D(n)=\Theta(n/\sqrt{\log n}) , and thus, that there should exist a way to strengthen the analysis of the lower bound.

In this post we briefly discuss the existence of point sets that determine \Theta(n/\sqrt{\log n}) distinct distances, for which the Elekes-Sharir framework can only yield a bound of \Omega(n/\log n) . Such configurations imply that to improve the Guth-Katz lower bound while by relying on the Elekes-Sharir framework, one either has to make a drastic change in the framework, or to separately handle the family of “problematic” point configurations. This observation is one of the results in a recent paper by Javier Cilleruelo, Micha Sharir, and myself. Embarrassingly, I did not notice that a similar result was added to the third version of Guth and Katz’s paper. The aforementioned paper still contains other interesting results.

JavierCilSharir2
Javier Cilleruelo and Micha Sharir.

Let us first recall the lower bound construction of Erdős. This construction relies on the following theorem from number theory.

Continue reading →

by

The second-partitioning-polynomial technique (part 2)

In the previous post we presented the second partitioning polynomial theorem. In this post we give an example of how to apply this theorem. After going over this example, it will be easier to discuss why so far this technique had been used only in {\mathbb R}^3 .

Let \cal P be a set of m points and let \Pi be a set of n planes, both in {\mathbb R}^3 . Consider a line \ell such that all the points of \cal P lie on \ell and all the planes of \Pi fully contain \ell , as in the following figure.

PlaneCommonLine

In this case we have I({\cal P},\Pi)=\Theta(mn) , which makes the problem not interesting. There exist several definitions of non-degenerate point-plane configurations, which make the problem of bounding the number of incidences more challenging (e.g., see this paper by Elekes and Toth; these non-degenerate configurations are not defined just for the sake of “making the problem less trivial”, and already have various applications). Since we are only interested in presenting the two partitioning polynomials technique, we consider the somewhat simple case where no three planes of \Pi contain a common line. This problem was already studied over 20 years ago by Edelsbrunner, Guibas, and Sharir, where partitioning of the space by cuttings has led to the bound I({\cal P},\Pi)=O(n^{3/5}m^{4/5} + m\log n) (they study the dual setting where no three points are collinear, though it is equivalent to our setting). A more general case is studied in a yet unpublished manuscript by Abdul Basit and myself, where the assumption is that no line is contained in k planes (and k can also depend on n ). To further simplify our scenario, we also assume that m=n .

Theorem 1. Let \cal P be a set of n points and let \Pi be a set of n planes, both in {\mathbb R}^3 , such that no line is fully contained in three planes of \Pi . Then I({\cal P},\Pi)=O(n^{7/5}) .

Proof.     We begin just as in the two-dimensional proof that was presented in this post. According to the assumption, any pair of points of \cal P can be contained in at most two planes of \Pi (or, recalling the notation that we used in the two dimensional case, the point-plane incidence graph does not contain a copy of K_{2,3} ). Thus, the Kővári–Sós–Turán theorem implies

I({\cal P},\Pi)=O(|{\cal P}|\sqrt{|\Pi|}+|\Pi|). \ \ \ \ \ (1)

Continue reading →

by

The second-partitioning-polynomial technique (part 1)

Thanks to Micha Sharir for helping in the preparation of this series of posts.

In a previous series of posts we introduced the basics of polynomial partitioning (see also the pdf version here). However, by presenting an example in {\mathbb R}^2 , we avoided the main difficulty in applying the technique, which arises only in dimensions d\ge 3 – bounding the number of incidences on the partitioning itself (i.e., on the zero set of the partitioning polynomial). In the plane, the partitioning is a one-dimensional curve, which is relatively simple to handle. Already when dealing with point-curve incidences in {\mathbb R}^3 , the partitioning is a two-dimensional surface which can fully contain all of the points and all of the curves, and curves that are fully contained in the partitioning can intersect in non-trivial ways.

Recently, two techniques for overcoming these difficulties in several special cases were introduced:

  • Using a constant-degree partitioning polynomial. This approach was introduced by Solymosi and Tao.
  • Applying a second polynomial partitioning that partitions the first partitioning. This approach was independently introduced both by Zahl and by Kaplan, Matoušek, Safernová, and Sharir (though Zahl was the first to upload his results to arXiv, exposing the technique to the community).
In a recent result by Abdul Basit and myself (which was submitted but is not yet available online), the two techniques are combined together to obtain an upper bound for the number of incidences between points and “restricted” configurations of spheres and planes. In this series of posts we discuss the technique of applying a second partitioning polynomial. The main idea in this technique is to partition the surfaces of a polynomial partitioning by using a second partitioning polynomial. The second partitioning should not overlap the first one in a (d-1) -dimensional patch, for otherwise no further partitioning would take place.

The technique is based on the following theorem. (As before, we regard the dimension d of the ambient space as a constant, and ignore the dependence on d of the various constants of proportionality in the bounds.)

Theorem 1 (Second polynomial partitioning). Given an irreducible polynomial f\in{\mathbb R}[x_1,\ldots,x_d] of degree D , a parameter E\ge D , and a finite point set \cal P in {\mathbb R}^3 , there exists a polynomial g\in{\mathbb R}[x_1,\ldots,x_d] of degree at most E , co-prime with f , which partitions \cal P into subsets Q_0 \subset Z(g) and Q_1,\ldots,Q_t , for t=O(DE^{d-1}) , so that each Q_i , for i=1,\ldots,t , lies in a distinct component of {\mathbb R}^d\setminus Z(g) , and |Q_i|=O(|Q|/t) .

The two proofs of Theorem 1, by Zahl and by Kaplan, Matoušek, Safernová, and Sharir, are quite different from each other. The latter is based on a simple combinatorial trick, while the former is more algebraic and is based on real varieties (not to be confused with varieties in a real space). In this post we present the simpler combinatorial proof. The algebraic proof is also interesting and has the advantage of yielding a partition whose components are all (d-1) -dimensional (the approach of Kaplan et al. also allows lower dimensional components).

Continue reading →