# 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.