Subsets with distinct volumes

Today I wish to mention another new result related to distinct distances. This time it is this paper by Gasarch, Harris, Ulrich, and Zbarsky. I (or rather, google scholar) found this paper on Gasarch’s website (next to a disclaimer stating that this is a work in progress and might be incorrect). [Update (Aug 2013): as commented by David Conlon, these results are not in their final form, and an updated version including also David Conlon and Jacob Fox should appear in the not-too-distant future.] [Update #2 (Jan 2014): The updated version, containing six authors, can be found here.]

The paper contains various results, all related to a generalization of a family of problems that I recently surveyed. Following the notation in the paper, h_{a,d}(n)  concerns distinct volumes of sets of (a-1)  -dimensional simplices (i.e., simplices that are determined by a  points) in {\mathbb R}^d  . Specifically, h_{a,d}(n)  denotes the maximum number satisfying that for every set of n  points in {\mathbb R}^d  , with no a  points on a common (a-2)  -flat, there exists a subset of h_{a,d}(n)  points that do not determine two (a-1)  -dimensional simplices with the same volume.

For example, the case of h_{2,2}(n)  is about distinct distances in the plane. That is, h_{2,2}(n)  is the maximum number such that any set of n  points in {\mathbb R}^2  contains a subset of h_{2,2}(n)  points that do not determine any distance more than once. Thus, the proof of Charalambides (which I also described here) implies the bound h_{2,2}(n) = \Omega(n^{1/3}/\log^{1/3} n)  .

As another example, h_{3,2}(n)  is the maximum number such that any set of n  points in {\mathbb R}^2  , with no three collinear, contains a subset of h_{3,2}(n)  points that do not determine two triangles with the same area. Consider the set of vertices of a regular n  -gon, as in the following figure.


Such a set does not contain three collinear points, and any triangle area appears \Omega(n)  times. This immediately implies h_{3,2}(n)= O(n^{2/3})  (since any asymptotically larger subset with no repeated triangle areas would determine \omega(n^2)  distinct areas). A somewhat similar result by Iosevich, Roche-Newton, and Rudnev states that for any set \cal P  of n  points in the plane (no three collinear), and for any point p\in{\cal P}  , there are \Omega(n/log n)  distinct areas of triangles that are spanned by p  together with two other points of \cal P  .

So what are the new results in the current paper? First, the authors generalize Charalambides’ bound for h_{2,2}(n)  to higher dimensions. Specifically, by induction on the dimension d  (with Charalambides’ bound for h_{2,2}(n)  as the induction base), they obtain

h_{2,d}(n) = \Omega(n^{1/(3d-3+o(1))}).

This slightly improves Thiele’s bound of h_{2,d}(n) = \Omega(n^{1/(3d-2)})  . Moreover, the current paper seems to be the first to study the case of h_{a,d}(n)  for a\ge 3  . Specifically, it derives the bound

h_{a,d}(n) = \Omega(n^{1/((2a-1)d)}).

As in other recent related papers, the authors rely on tools from algebraic geometry to obtain this result. The paper also studies cases where n  is infinite, but I will not discuss these in this post.


3 thoughts on “Subsets with distinct volumes

  1. I just thought I’d say that these results aren’t quite in final form. Jacob Fox and I have been added to the project and some of the results can be improved. I will not say more here but the final version should hopefully appear in the not-too-distant future.

  2. Pingback: Recent Results (Feb `14) | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s