Planar point sets with forbidden four-point patterns and few distinct distances

What's new 2024-09-04

I’ve just uploaded to the arXiv my paper “Planar point sets with forbidden ${4}$ -point patterns and few distinct distance“. This (very) short paper was a byproduct of my recent explorations of the Erdös problem website in recent months, with a vague emerging plan to locate a suitable problem that might be suitable for some combination of a crowdsourced “Polymath” style project and/or a test case for emerging AI tools. The question below was one potential candidate; however, upon reviewing the literature on the problem, I noticed that the existing techniques only needed one additional tweak to fully resolve the problem. So I ended up writing this note instead to close off the problem.

I’ve arranged this post so that this additional trick is postponed to below the fold, so that the reader can, if desired, try to guess for themselves what the final missing ingredient needed to solve the problem was. Here is the problem (Erdös problem #135), which was asked multiple times by Erdös over more than two decades (and who even offered a small prize for the solution on one of these occasions):

Problem 1 (Erdös #135) Let ${A \subset {\bf R}^2}$ be a set of ${n}$ points such that any four points in the set determine at least five distinct distances. Must ${A}$ determine ${\gg n^2}$ many distances?

This is a cousin of the significantly more famous Erdös distinct distances problem (Erdös problem #89), which asks what is the minimum number of distances determined by a set ${A \subset {\bf R}^2}$ of ${n}$ points in the plane, without the restriction on four-point configurations. The example of a square grid ${\{0,\dots,\sqrt{n}-1\}^2}$ (assuming for sake of argument that ${n}$ is a perfect square), together with some standard analytic number theory calculations, shows that ${A}$ can determine ${\asymp n/\sqrt{\log n}}$ distances, and it is conjectured that this is best possible up to constants. A celebrated result of Guth and Katz, discussed in this previous blog post, shows that ${A}$ will determine at least ${\gg n/\log n}$ distances. Note that the lower bound ${\gg n^2}$ here is far larger, and in fact comparable to the total number ${\binom{n}{2}}$ of distances available, thus expressing the belief that the “local” condition that every four points determine at least five distances forces the global collection distances to be almost completely distinct. In fact, in one of the papers posing the problem, Erdös made the even stronger conjecture that the set ${A}$ must contain a subset ${A'}$ of cardinality ${\gg n}$ for which all the ${\binom{|A'|}{2}}$ distances generated by ${A}$ are distinct.

A paper of Dumitrescu came close to resolving this problem. Firstly, the number of ways in which four points could fail to determine five distinct distances was classified in that paper, with the four-point configurations necessarily being one of the following eight patterns:

${\pi_1}$ : An equilateral triangle plus an arbitrary vertex.
${\pi_2}$ : A parallelogram.
${\pi_3}$ : An isosceles trapezoid (four points on a line, ${P_1,P_2,P_3,P_4}$ , where ${\overleftrightarrow{P_1P_2} = \overleftrightarrow{P_3P_4}}$ , form a degenerate isosceles trapezoid).
${\pi_4}$ : A star with three edges of the same length.
${\pi_5}$ : A path with three edges of the same length.
${\pi_6}$ : A kite.
${\pi_7}$ : An isosceles triangle plus an edge incident to a base endpoint, and whose length equals the length of the base.
${\pi_8}$ : An isosceles triangle plus an edge incident to the apex, and whose length equals the length of the base.

(See Figure 1 and Lemma 1 of Dumitrescu’s paper.) So the question is asking whether if an ${n}$ point set ${A}$ avoids all of these patterns ${\pi_1,\dots,\pi_8}$ , then it must generate ${\gg n^2}$ distances.

Given that the grid ${\{0,\dots,n-1\}^2}$ determine only ${\asymp n^2 / \sqrt{\log n}}$ distances, one could seek a counterexample to this by finding a set of ${\asymp n}$ points in the grid ${\{0,\dots,n-1\}^2}$ that avoided all of the eight patterns ${\pi_1,\dots,\pi_8}$ .

Dumitrescu then counted how often each of the patterns ${\pi_1,\dots,\pi_8}$ occured inside the grid ${\{0,\dots,n-1\}^2}$ . The answer is:

${\pi_1}$ does not occur at all. (This is related to the irrationality of ${\sin \pi/3 = \sqrt{3}/2}$ .)
${\pi_2}$ occurs ${\asymp n^6}$ times.
${\pi_3}$ occurs ${\asymp n^5}$ times.
${\pi_4}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_5}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_6}$ occurs ${\asymp n^5}$ times.
${\pi_7}$ occurs ${O(n^{14/3} \log n)}$ times.
${\pi_8}$ occurs ${O(n^{14/3} \log n)}$ times.

(The bounds involving ${O(n^{14/3} \log n)}$ were obtained using the Szemerédi-Trotter theorem, and might not be optimal for this problem.) In particular, with the exception of the parallelogram pattern ${\pi_2}$ , the other seven forbidden ${4}$ -point patterns ${\pi_1,\pi_3,\dots,\pi_8}$ occur at most ${O(n^5)}$ times.

Using this and a standard probabilistic argument, Dumitrescu then established the following “near miss” to a negative answer to the above problem:

Theorem 2 (First near miss) If ${n}$ is sufficiently large, then there exists a subset of ${\{0,\dots,n-1\}^2}$ of cardinality ${\asymp n}$ which avoids all of the patterms ${\pi_1, \pi_3,\dots,\pi_8}$ .

In particular, this generates a set of ${\asymp n}$ points with ${O(n^2/\sqrt{\log n})}$ distances that avoids seven out of the eight required forbidden patterns; it is only the parallelograms ${\pi_2}$ that are not avoided, and are the only remaining obstacle to a negative answer to the problem.

Proof: Let ${\varepsilon>0}$ be a small constant, and let ${A}$ be a random subset of ${\{0,\dots,n-1\}^2}$ , formed by placing each element of ${\{0,\dots,n-1\}^2}$ with an independent probability of ${\varepsilon/n}$ . A standard application of Hoeffding’s inequality (or even the second moment method) shows that this set ${A}$ will have cardinality ${\asymp \varepsilon n}$ with high probability if ${n}$ is large enough. On the other hand, each of the ${O(n^5)}$ patterns ${\pi_1,\pi_3,\dots,\pi_8}$ has a probability ${\varepsilon^4/n^4}$ of lying inside ${A}$ , so by linearity of expectation, the total number of such patterns inside ${A}$ is ${O( n^5 \varepsilon^4 / n^4 ) = O(\varepsilon^4 n)}$ on the average. In particular, by Markov’s inequality, we can find a set ${A}$ of cardinality ${\asymp \varepsilon n}$ with only ${O(\varepsilon^4 n)}$ such patterns. Deleting all of these patterns from ${A}$ , we obtain a set ${A'}$ of cardinality ${\asymp \varepsilon n - O(\varepsilon^4 n)}$ , which is ${\asymp n}$ if ${\varepsilon}$ is a sufficiently small constant. This establishes the claim. $\Box$

Unfortunately, this random set contains far too many parallelograms ${\pi_2}$ ( ${\asymp n^2}$ such parallelograms, in fact) for this deletion argument to work. On the other hand, in earlier work of Thiele and of Dumitrescu, a separate construction of a set of ${\asymp n}$ points in ${\{0,\dots,n-1\}^2}$ that avoids all of the parallelograms ${\pi_2}$ was given:

Theorem 3 (Second near miss) For ${n}$ large, there exists a subset ${S}$ of ${\{0,\dots,n-1\}^2}$ of cardinality ${\asymp n}$ which contains no parallelograms ${\pi_2}$ . Furthermore, this set is in general position: no three points in ${S}$ are collinear, and no four are concyclic. As a consequence, this set ${S}$ in fact avoids the three patterns ${\pi_1, \pi_2, \pi_3}$ (the pattern in ${\pi_3}$ is concyclic, and the pattern ${\pi_1}$ does not occur at all in the grid).

Proof: One uses an explicit algebraic construction, going back to an old paper of Erdös and Turán involving constructions of Sidon sets. Namely, one considers the set

$\displaystyle S := \{ (x,y) \in \{0,\dots,n-1\}^2: y = x^2 \hbox{ mod } p \} \ \ \ \ \ (1)$

where ${p}$ is a prime between ${4n}$ and ${8n}$ (the existence of which is guaranteed by Bertrand’s postulate). Standard Gauss sum estimates can be used to show that ${S}$ has cardinality ${\asymp n}$ . If ${S}$ contained four points that were in a parallelogram or on a circle, or three points in a line, then one could lift up from ${\{0,\dots,n-1\}^2}$ to the finite field plane ${{\mathbf F}_p^2}$ and conclude that the finite field parabola ${\{ (x,x^2): x \in {\bf F}_p \}}$ also contained four points in a parallelogram or a circle, or three points on a line. But straightforward algebraic calculations can be performed to show that none of these scenarios can occur. For instance, if ${P, P+H, P+K, P+H+K}$ were four points on a parallelogram that were contained in a parabola, this would imply that an alternating sum of the form

$\displaystyle (x, x^2) - (x+h, (x+h)^2) - (x+k, (x+k)^2) + (x+h+k, (x+h+k)^2)$

would vanish for some non-zero ${h,k}$ ; but this expression simplifies to ${(0, 2hk)}$ , which cannot vanish for non-zero ${h,k}$ as ${p}$ is odd.

Given that we have one “near-miss” in the literature that avoids ${\pi_1, \pi_3, \dots, \pi_8}$ , and another “near-miss” that avoids ${\pi_1, \pi_2, \pi_3}$ , it is natural to try to combine these two constructions to obtain a set that avoids all eight patterns ${\pi_1,\dots,\pi_8}$ . This inspired the following problem of Dumitrescu (see Problem 2 of this paper):

Problem 4 Does the set ${S}$ in (1) contain a subset of cardinality ${\gg n}$ that avoids all eight of the patterns ${\pi_1, \dots, \pi_8}$ ?

Unfortunately, this problem looked difficult, as the number-theoretic task of counting the patterns ${\pi_4,\dots,\pi_8}$ in ${S}$ looked quite daunting.

This ends the survey of the prior literature on this problem. Can you guess the missing ingredient needed to resolve the problem? I will place the answer below the fold.

The missing ingredient is to randomize the parabola appearing in (1). The crucial property of being free of parallelograms is preserved under affine transformations of the finite field plane ${{\bf F}_p^2}$ , so we apply a random invertible affine transformation to the parabola to create the candidate set

$\displaystyle A := \{ (x,y) \in \{0,\dots,n-1\}^2: (ax+by)^2 = cx+dy+e \hbox{ mod } p \}$

where ${a,b,c,d,e}$ are randomly chosen elements of ${{\bf F}_p}$ , subject to the non-degeneracy condition

$\displaystyle ad-bc \neq 0.$

A routine application of the second moment method shows that ${A}$ has cardinality ${\asymp n}$ with high probability. The algebraic calculation that showed that ${S}$ avoided the parallelogram pattern ${\pi_2}$ , also shows that ${A}$ avoids ${\pi_2}$ . We know that the grid ${\{0,\dots,n-1\}^2}$ avoids the pattern ${\pi_1}$ . What about the other six patterns ${\pi_3,\dots,\pi_8}$ ? I struggled with counting these patterns for a while. At first I tried to understand the discrete circles ${\{ (x,y) \in {\bf Z}^2: x^2+y^2 = r\}}$ for various ${r = O(n^2)}$ , focusing for instance of triples ${u,v,w}$ in that circle that obeyed some specified linear constraint ${w = au+bv}$ modulo ${p}$ ; but this looked like it required quite a bit of analytic number theory to properly control. I also briefly played around with the rotation group ${SO_2({\bf F}_p)}$ , hoping that its equidistribution properties would be helpful, but again this was a challenge. In the end, I found that abandoning any distance-related considerations was the most effective way forward. A key calculation is that any four distinct points ${P_1,P_2,P_3,P_4}$ of ${{\bf F}_p^2}$ (regardless of what pattern they form) will all lie in the parabola

$\displaystyle \{ (x,y) \in {\bf F}_p^2: (ax+by)^2 = cx+dy+e \}$

with a probability of ${O(1/p^4) \asymp O(1/n^4)}$ . There are two cases. If three of the points are collinear, then the probability is in fact zero, because a line cannot intersect a parabola in three points by Bezout’s theorem. If instead the four points are in general position, then by affine invariance one can normalize the four points as ${(0,0)}$ , ${(1,0)}$ , ${(0,1)}$ , ${(s,t)}$ for some non-zero ${s,t}$ . Then one is asking for solutions ${(a,b,c,d,e)}$ to the system of equations

$\displaystyle 0 = e$

$\displaystyle a^2 = c + e$

$\displaystyle b^2 = d + e$

$\displaystyle (as+bt)^2 = cs+dt+e$

and it is a routine matter to show that there are only ${O(p)}$ solutions to this system, giving the desired probability of ${O(1/p^4)}$ .

Once one has this calculation, the deletion argument finishes the job. Indeed, the expected number of patterns ${\pi_3,\dots,\pi_8}$ in ${A}$ is ${O(n^5/n^4) = O(n)}$ . If we refine further by an additional factor of ${\varepsilon}$ as in the proof of Theorem 2, we obtain (with high probability) a set of cardinality ${\asymp \varepsilon n}$ that contains ${O(\varepsilon^4 n)}$ forbidden patterns. Deleting these, we have finally obtained a set of cardinality ${\asymp n}$ in the grid ${\{0,\dots,n-1\}^2}$ (and thus generating ${O(n^2/\sqrt{\log n})}$ distances) that avoid all of the eight patterns ${\pi_1,\dots,\pi_8}$ , and thus give a negative answer to the original problem of Erdös.

There are still open problems in the area. One is the following: what is the best lower bound on the number of distances determined by ${n}$ points in the plane, for which every four points determine at least five distances (i.e., one avoids all eight patterns ${\pi_1,\dots,\pi_8}$ )? The Guth-Katz theorem gives the lower bound of ${\gg n/\log n}$ , but in this case we can get the better bound of ${\frac{n-1}{2}}$ by the following trivial argument: if ${P_0}$ is one point in the set, then the other ${n-1}$ points determine at least ${\frac{n-1}{2}}$ distinct distances to ${P_0}$ , because the same distance cannot occur three times as this would create a star ${\pi_4}$ . Can one do better than this? Specifically, can one achieve a super-linear bound? This was posed as Problem 3 in Dumitrescu’s paper. I do not know how to make progress on this question, other than a vague suspicion that the polynomial method might be relevant here, and that one should somehow try to capture many of the points in a set that only has a linear number of distances in a reasonably low degree algebraic curve.