# Points in General Position

Many Discrete Geometry problems study planar point sets in general position. Most commonly, this definition refers to point sets with no three collinear points and no four cocircular points (that is, no circle contains four points of the set). A few examples of such problems:

• What is the minimum number of distinct distances that are spanned by a set of $n$ points in general position?
• What is the minimum number of convex $k$-gons determined by $n$ points in general position?
• For even $n$, what is the maximum number of distinct ways in which one can cut a set of $n$ points in general position by a line into two halves, each of cardinality $n/2$?
• What is the maximum number of points that can be placed on an $n \times n$ grid so that no three points are collinear. What happens when we also forbid four cocircular points?
Randomly choosing $n$ points from the plane will lead to a set in general position, but this set is unlikely to have any interesting extremal structure. For example, we expect such a set to span many distinct distances, and it is not clear why such a set should span few convex $k$-gons. Problems such as the ones above ask for point sets that are in general position while also having some kind of structure. I often find it useful to have examples of such point sets as part of my “Discrete Geometry toolkit”. I am familiar with two very different constructions of such sets. This post describes these two constructions. If you are familiar with additional constructions, do let me know!

Construction 1: Subsets of the integer lattice. Our first construction involves finding a large subset of an $n \times n$ section of the integer lattice that is in general position. The basic idea for this construction seems to originate from Erdős (for example, see this paper of Roth), although we will follow a later variant of Thiele.

For a prime $p$, we consider the point set

${\cal P} = \left\{\left(t,t^2 \mod p\right)\ :\ 0\le t

Note that ${\cal P}$ is a set of $\lfloor p/4\rfloor$ points from a $p\times p$ section of the integer lattice. We will now show that ${\cal P}$ does not contain three collinear points or four cocircular points.

An example of the first construction, created by Gábor Damásdi.

Three points $(x_1,y_1),(x_2,y_2),$ and $(x_3,y_3)$ are collinear if and only if

$\begin{vmatrix} 1 & x_1 & y_1 \\ 1 & x_2 & y_2 \\ 1 & x_3 & y_3 \end{vmatrix} = 0.$

It is not difficult to check that for three points $(t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2)$, we get

$\begin{vmatrix} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ 1 & t_3 & t_3^2 \end{vmatrix} = (t_2-t_1)(t_3-t_2)(t_3-t_1).$

For distinct integers $t_1,t_2,t_3$, this determinant is clearly nonzero. When we also have that $0\le t_1,t_2,t_3 < p$, this determinant is also not a multiple of the prime $p$. Thus,

$\begin{vmatrix} 1 & t_1 & (t_1^2 \mod p) \\ 1 & t_2 & (t_2^2 \mod p) \\ 1 & t_3 & (t_3^2 \mod p) \end{vmatrix} \neq 0.$

We conclude that no three points of ${\cal P}$ are collinear. We can use a similar argument for the case of cocircular points. Four points $(x_1,y_1),(x_2,y_2),(x_3,y_3),$ and $(x_4,y_4)$ are cocircular if and only if

$\begin{vmatrix} 1 & x_1 & y_1 & x_1^2 +y_1^2\\ 1 & x_2 & y_2 & x_2^2 +y_2^2\\ 1 & x_3 & y_3 & x_3^2 +y_3^2\\ 1 & x_4 & y_4 & x_4^2 +y_4^2 \end{vmatrix} = 0.$

(One can think of this test is as lifting the four points to the paraboloid defined by $z=x^2+y^2$ in ${\mathbb R}^3$, and checking if the four lifted points are coplanar. It is known that the intersections of the paraboloid with planes are exactly the lifting of circles to the paraboloid.)

Taking the points $(t_1,t_1^2),(t_2,t_2^2),(t_3,t_3^2),(t_4,t_4^2)$, we get

$\begin{vmatrix} 1 & t_1 & t_1^2 & t_1^2 +t_1^4\\ 1 & t_2 & t_2^2 & t_2^2 +t_2^4\\ 1 & t_3 & t_3^2 & t_3^2 +t_3^4\\ 1 & t_4 & t_4^2 & t_4^2 +t_4^4 \end{vmatrix} = (t_1+t_2+t_3+t_4)\prod_{1\le j

Since $0\le t_1,t_2,t_3,t_4 < p/4$, we have that $t_1+t_2+t_3+t_4$ is not a multiple of $p$. Assuming that the four integers are distinct, none of the elements of the product is a multiple of $p$. Repeating the above argument, we get that no four points of ${\cal P}$ are cocircular.

Now that we know that the above construction is in general position, let us mention a few of its applications:

• Erdős and Purdy asked for the size of the largest subset of the $n\times n$ integer lattice with no three points on a line and no four on a circle. The above construction provides the current best lower bound for this problem.
• Erdős, Hickerson, and Pach asked whether there exists a planar set of $n$ points in general position that spans no parallelograms and still determines $o(n^2)$ distinct distances. Dumitrescu provided a positive answer to this question by using the above construction.
• The Heilbronn triangle problem asks for the smallest $\Delta(n)$ such that every set of $n$ points in the unit square determine a triangle of area at most $\Delta(n)$. Erdős used a variant of the above construction to produce one of the first non-trivial lower bounds for the problem.
Construction 2: Projection from a hypersphere. In our first construction, the point set has some structure since it is a subset of a $p\times p$ section of the integer lattice. The structure in our second construction also originates from a lattice, although in a very different way. This construction comes from a paper of Erdős, Füredi, Pach, and Ruzsa, and seems to be influenced by earlier ideas of Behrend.

For a positive integer $d$, consider the section of the $d$-dimensional integer lattice

${\cal L} = \left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ 0\le x_1,\ldots,x_d <2^d \right\}.$

We claim that there exists a hypersphere around the origin that contains many points of ${\cal L}$. First, note that $|{\cal L}| = 2^{d^2}$. We also note that the distance between a point $x\in {\cal L}$ and the origin is $\sqrt{x_1^2+\cdots+x_d^2}$. Every such distance is the square root of an integer between zero and $d\cdot 2^{2d}$. That is, the points of ${\cal L}$ determine at most $d\cdot 2^{2d}$ distinct distances from the origin. By the pigeonhole principle, there exists a distance $\delta$ such that at least $2^{d^2}/(d\cdot 2^{2d})=2^{d(d-2)}/d$ points are at distance $\delta$ from the origin. In other words, the hypersphere $S_\delta$ centered at the origin and of radius $\delta$ contains at least $2^{d(d-2)}/d$ points of ${\cal L}$. Let ${\cal P}'$ be a set of exactly $n=2^{d(d-2)}/d$ of these points. To recap, ${\cal P}'$ is a set of $n$ points with integer coordinates on the hypersphere $S_\delta$.

Let $h$ be a generic two-dimensional plane in ${\mathbb R}^d$ (or, if you prefer, a random plane). Let ${\cal P}$ be the set of points that are projections of the points of ${\cal P}'$ on $h$. It is not difficult to verify that, on a generic plane, no two points of ${\cal P}'$ are projected to the same point. Similarly, when projecting four points on a generic plane, we do not expect the projections to be cocircular. That is, we may assume that ${\cal P}$ consists of $n$ distinct points, no four which are cocircular.

It is not true that the projections of any three points on a generic plane are not collinear. If three points are collinear in ${\mathbb R}^d$, then their projections on every plane would remain collinear. This is why we take the points of ${\cal P}'$ to be on the hypersphere $S_\delta$: Since every line intersects the hypersphere in at most two points, no three points of ${\cal P}'$ are collinear.

Now that we constructed a set ${\cal P}$ of $n$ points in general position, it remains to see what structure ${\cal P}$ has. For this purpose, we return to the lattice ${\cal L}$ in ${\mathbb R}^d$. It is not difficult to verify that the set of vectors determined by pairs of points of ${\cal L}$ is

$\left\{(x_1,\ldots,x_d)\in {\mathbb Z}^d :\ -2^d\le x_1,\ldots,x_d <2^d \right\}.$

That is, the number of distinct vectors determined by pairs of points of ${\cal L}$ is $O\left(2^{d(d+1)}\right)$. Since ${\cal P}' \subset {\cal L}$, the number of distinct vectors determined by pairs of points of ${\cal P}'$ is also $O(2^{d(d+1)})$. Let $p_1,p_2,p_3,p_4\in {\mathbb R}^d$ satisfy $p_1-p_2=p_3-p_4$, and let $\pi(\cdot)$ be a projection from ${\mathbb R}^d$ to a two-dimensional plane. Then $\pi(p_1)-\pi(p_2)=\pi(p_3)-\pi(p_4)$. This implies that the number of distinct vectors determined by pairs of points of ${\cal P}$ is also $O(2^{d(d+1)})$.

From the definition $n=2^{d(d-2)}/d$ we obtain $\log n = d(d-2) - \log d$, which in turn implies $2^{d(d+1)} = O(n2^{\sqrt{\log n}})$. Thus, the number of distinct vectors determined by pairs of points of ${\cal P}$ is $O\left(n2^{\sqrt{\log n}}\right)$. (If you are not used to such expressions, note that for every $\varepsilon>0$ we have $n2^{\sqrt{\log n}} = O\left(n^{1+\varepsilon}\right)$.) This property shows that ${\cal P}$ has a strong structure. For example, it immediately implies that the number of distinct distances determined by ${\cal P}$ is $O\left(n2^{\sqrt{\log n}}\right)$ (and similarly for the number of distinct directions). That is, a set in general position can still determine a relatively small number of distinct distances.

# Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space ${\mathbb R}^d$. The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

Ciprian Demeter and Nets Katz.

# (More) Local Properties that imply Many Distinct Distances

Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let $\phi(n,k,l)$ denote the minimum number of distinct distances that can be determined by a set ${\cal P} \subset {\mathbb R}^2$ of $n$ points, such that any $k$ points of $\cal P$ determine at least $l$ distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances. For more details and examples, see the original post.

A while ago I noticed another nice bound for this set of problems. Unfortunately the proof is very simple, which prevents it from being published in a “decent” journal. I’ve been trying to push it further, so far without success. Perhaps someone else would see how this idea can be extended.

As discussed in the previous post, Fox, Pach, and Suk proved that for every $k\ge 6$ and $\varepsilon>0$, we have

$\phi\left(n,k,\binom{k}{2}-k+6\right) = \Omega(n^{8/7-\varepsilon}).$

A simple argument shows that for every $k\ge 4$ we have

$\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2\right) = \Omega(n^2).$

Our interest in this post lies in between these two bounds. That is, what happens between the values $\binom{k}{2}-k+6$ and $\binom{k}{2}- k/2 +2$. I am only aware of one previous result in thie range: Erdős and Gyárfás showed that $\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega(n^{4/3})$. We will now prove a stronger result.

Theorem 1. For every $k\ge 8$ that is divisible by four, we have

$\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right) = \Omega_k(n^{4/3}).$

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

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

Update July 2017: The conjecture is false, as pointed out by Cosmin Pohoata. A known construction is a counterexample, and I should be ashamed for not observing this on my own. Erdős, Füredi, Pach, and Ruzsa constructed a set of $n$ points in ${\mathbb R}^2$ with $O(n^{1+\varepsilon})$ distinct distances for any $\varepsilon >0$ and no four points on a common circle. Having a repeated bisector requires having four points on a circle, so there are no repeated bisectors. Oh well…

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.

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.

# Local Properties that imply Many Distinct Distances

Jacob Fox, Janos Pach, and Andrew Suk just placed this paper on arXiv. The paper seems very nice, but unfortunately for Ben Lund, Frank de Zeeuw, and myself, it contains a result that is almost identical to one that we had but did not yet publish. Instead of sulking alone in the dark, in this post I describe the problem and our result.

Jacob Fox, Janos Pach, and Andrew Suk.

Let $\phi(n,k,l)$ denote the minimum number of distinct distances that can be determined by a set of $n$ points ${\cal P} \subset {\mathbb R}^2$ with the property that any $k$ points of $\cal P$ determine at least $l$ distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances.

For example, the value of $\phi(n,3,3)$ is the minimum number of distinct distances that are determined by a set of $n$ points that do not span any isosceles triangles (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines $n-1$ distinct distances with the other points of the set, and we thus have $\phi(n,3,3) = \Omega(n)$. Erdős observed the following upper bound for $\phi(n,3,3)$. Behrend proved that there exists a set $A$ of positive integers $a_1, such that no three elements of $A$ determine an arithmetic progression and that $a_n < n2^{O(\sqrt{\log n})}$. Therefore, the point set ${\cal P}_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\}$ does not span any isosceles triangles. Since ${\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}$ and $D({\cal P}_2)< n2^{O(\sqrt{\log n})}$, we have $\phi(n,3,3) < n2^{O(\sqrt{\log n})}$.

In the same paper, Erdős derived the more general bound

$\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n).$

As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with $\varepsilon$ depending on $k$)

$\phi\left(n,k,\binom{k}{2}-k+4+\log k\right) = \Omega(n^{1+\varepsilon}).$

We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the $+5$ being replaced with $+6$. While there are some similarities between the two proofs, they do not seem to be identical.

Theorem 1. For every even $k\ge 6$ and $\varepsilon>0$, we have

$\phi\left(n,k,\binom{k}{2}-k+5\right) = \Omega(n^{8/7-\varepsilon}).$

# Point Sets with Few Distinct Distances

Ben Lund and I were sitting in a small Korean restaurant and discussing an old conjecture of Erdős. Erdős suggested that if a set of $n$ points in ${\mathbb R}^2$ spans $O(n/\sqrt{\log n})$ distinct distances, then the vertices of this set must span either a square or an equilateral triangle. Presumably, this conjecture was made because the two best-known examples of sets with $O(n/\sqrt{\log n})$ distinct distances are $n\times n$ subsets of the integer lattice and of the triangular lattice. (By the triangular lattice, I mean the vertices of a tiling of the plane with equilateral triangles.)

A subset of the integer lattice and a subset of the triangular lattice.

A subset of the integer lattice spans many squares and no equilateral triangles, while a subset of the triangular lattice spans many equilateral triangles and no squares. We can create various similar configurations by taking one of these two configurations and then applying rotations, uniform scaling, and taking subsets. Such configurations still contain squares or equilateral triangles. Ben and I were wondering whether we can find additional configurations, which are not “related” to the integer lattice or to the triangular lattice. Surprisingly, we managed to find a large family of other configurations. Moreover, many of these configurations do not span any squares or triangles, disproving Erdős’ conjecture. We then discovered that these configurations were already known, and appeared in a paper by Moree and Osburn. I guess that this is another case of lack of communication between different mathematical communities…

# Distinct Distances: Open Problems and Current Bounds

If you have been following this blog for a while, you might have noticed that I have been slowly surveying the various open problems that are related to distinct distances, and the best known bounds for them. I think that my survey is now in a decent shape, so I uploaded it on arXiv.

For this occasion, I wish to mention an open problem concerning surfaces in ${\mathbb R}^3$. It is far from being one of the main problems of this subfield. However, since currently no non-trivial bounds are known for it, it seems like a good problem for a student or for someone who wishes to start working on distinct distances problems.

Recall that in bipartite distinct distances problems we have two sets of points ${\cal P}_1$ and ${\cal P}_2$, and are interested only in distinct distances that are spanned by pairs of ${\cal P}_1\times{\cal P}_2$ (i.e., distances between points from different sets). For simplicity, in this post we assume that both sets are of cardinality $n$. One example of such a result, by Pach and de Zeeuw, is that if each of the two point sets is on a planar curve that contains no lines or circles, then the number of distinct distances between ${\cal P}_1$ and ${\cal P}_2$ is $\Omega\left(n^{4/3}\right).$

In ${\mathbb R}^d$, the similar (yet non-bipartite) case where one point set is placed a curve was studied by Charalambides and by Raz, Sharir, and Solymosi. However, nothing non-trivial is known for point sets on two-dimensional surfaces. That is, consider, in ${\mathbb R}^3$, the minimum number of distinct distances between a set ${\cal P}_1$ of $n$ points on a two-dimensional surface $S_1$, and a set ${\cal P}_2$ of $n$ points on a two-dimensional surface $S_2$.

Before we properly formulate any questions for this scenario, let us first consider some examples. First, consider the case where $S_1$ and $S_2$ are non-parallel planes in ${\mathbb R}^3$. In this case there exist two orthogonal lines $\ell_1,\ell_2$ such that $\ell_1 \subset S_1$, $\ell_2 \subset S_2$, and $\ell_1 \cap \ell_2$ is a point on $S_1 \cap S_2$. We can place the two sets of points on $\ell_1,\ell_2$ such that the number of distinct distances between the two sets is $\Theta(n)$ (e.g., see Section 3 of the survey). The same bound can be obtained between two spheres and between a sphere and a plane (in both cases by placing the points on two parallel circles).

A slightly better bound can be obtained in the case where $S_1$ and $S_2$ are parallel planes. In this case we can place a $\sqrt{n}\times\sqrt{n}$ subset of the integer lattice on each of the planes. For example, we may assume that the planes are defined by $z=0$ and $z=1$, and that the points of the two sets are

${\cal P}_1 \cup {\cal P}_2 = \left\{ (x,y,z) | 1 \le x,y \le \sqrt{n} \quad \text{ and } \quad 1 \le z \le 2 \right\}.$

A variant of Erdős’ analysis of the planar lattice (e.g., see Section 2 of the survey) implies that the number of distinct distances between the two sets is $O(n/\sqrt{\log n})$.

Unlike the planar case, it is not immediately clear whether the above examples are tight. For example, the $n^{1/3}\times n^{1/3} \times n^{1/3}$ integer lattice determines only $O\left(n^{2/3}\right)$ distinct distances. This leads to the following conjecture.

Conjecture. Given a set ${\cal P}_1$ of $n$ points on a two-dimensional surface $S_1$, and a set ${\cal P}_2$ of $n$ points on a two-dimensional surface $S_2$, both in ${\mathbb R}^3$, the number of distinct distances between the two sets is $\Omega(n/\sqrt{\log n})$ (or at least $\Omega(n^{1-\varepsilon})$?).

Assuming that the conjecture is true, we have the following natural question.

Problem. Characterize which pairs of surfaces $S_1,S_2$ can yield $O(n)$ distinct distances. Moreover, provide a lower bound for the minimum number of distinct distances for the case of any other pair of surfaces.

This problem formulation is motivated by aforementioned result of Pach and de Zeeuw for the case of points on two planar curves, where the only “exceptional” cases are when the two curves contain parallel lines or concentric circles, and then the number of distinct distances can be $\Theta(n)$. For any other pair of curves, the number of distinct distances is $\Omega(n^{4/3})$.