Abstract. An almost tight lower bound for the Erdős distinct distance problem was found by Guth and Katz[GK15] using a conversion into a set of 3-dimensional point-line incidence problems. A similar open problem is finding a lower bound on the number of equivalence classes of hinges, pairs of distances relative to a given point. We review the beginning of the Guth-Katz proof up to an incidence counting theorem, and present similar conversions into weighted incidence problems for the hinge problem, leaving specific bounds to be proven. Unfortunately, several of the controlling quantities for these latter incidence problems would, if known, imply the end-goal bound for the hinge problem. We also estimate the number of distinct distances for a class of regular lattices.
For a finite set with elements, we define an equivalence relation over pairs of points in so that when , where denotes the Euclidean norm. Each equivalence class, represented by , corresponds to the distinct distance , so that the set of equivalence classes is equivalent to the distance set defined by
The current best general lower bound known for the size of the distance set is from [GK15] and is given by .1 On the other hand, the smallest asymptotic distance set size observed for a class of sets is , expected for e.g square or hexagonal grids.2
The hinge problem, introduced in [IP18], is the problem of establishing a lower bound on the number of equivalence classes of hinges, namely triplets in for which iff and . A trivial upper bound is given by a generic set of points, in which case all hinges are unique (up to degenerate cases like ), leaving equivalence classes. We call the set of distance pairs produced by hinge equivalence classes .
There is a stronger conjecture which would immediately imply the hinge and distinct distance lower bounds: the Erdős pinned-distance conjecture. In its most relevant form, it claims, given pinned distance sets defined by
that . As the number of hinge equivalence classes represented by hinges with fixed is , this implies a hinge lower bound of . Similarly, since for all , it would imply that .
We introduce the symbol to concisely express and distinguish dyadic sums,
For later use, we define the point-line incidence function, applied to a set of points and set of lines :
Example 1. The square grid is the best known asymptotic example, within a constant.3 We pick , let , and define . Note that has significant translational and reflective symmetry; there are many isometries for which . The number of distinct distances is , as will be calculated later in Section 6. This asymptotic is significantly different for other distance metrics: under and distances, there are distinct distances, and a metric produced from a generic convex set produces distinct distances, since thanks to translational symmetry, where is a corner point, e.g., a point , , , or .
Example 2. Another extremal example is optimized to the Euclidean distance metric, rather than to translational symmetry. Here,
defines a regular -sided polygon with a central point . The pinned distance set , while for all other .
We can interpolate between this and the grid by creating , which has points for which points are a distance of away from .
A “generic” polygon is produced by taking a generic set for which , and ; then
Example 3. The Penrose tiling has high translational symmetry and does not immediately appear to have grid structure; however, there is a pentagrid construction method4 which implies that, if is the subset of a Penrose tiling filling a disk, then the projections of along five specific directions have size , so that is a constant-density subset of a lattice. By an argument similar to 7, one can show that .
In this section, we present an minor variation on the method used in [GK15] to convert the lower bound on into a set of incidence problem upper bounds. Let be the size of the equivalence class of distance :
Then, counting all nonzero equivalence classes, we find , after which by Cauchy-Schwarz we have
where we define to be the set of all quadruples for which . Rearranging,
| (3.1) |
To prove that , we must show that . (This upper bound is the tightest attainable, as shown in Section 7.) First, we split into two disjoint sets, and , namely the rotated and translated quadruples. The subset is defined as the set of quadruples for which the vector identity holds. Since each such tuple can be identified with , as , it follows
| (3.2) |
It remains to prove that . To do this, let be the set of positively oriented non-translational rigid motions of the plane, and establish a bijection between and the set , defined as the set of all , where , , and . By Prop 2.3 of [GK15], for a given tuple where , there is a unique for which and . Since and , it follows and , so that the tuple . On the other hand, given , we define and ; these exist since , and since is an isometry, , which is since . Thus . Correspondingly, we have
We partition into disjoint sets defined so that for all , . We also define , so that by dyadic decomposition
The set consists of all for which ; , as .
We now construct an incidence problem which will provide an upper bound on . To a given rigid motion which fixes the point and rotates by plane by angle around that point, we associate the point .5 As is non-translational, , so that the point is well defined. Next, we define the set of lines , where each individual line contains all which map to . This line, as proven by Prop 2.7 of [GK15], can be parameterized by as
| (3.4) |
where we consider and as points on the plane in , and the unit vector, and the (standard, right-handed) cross product.6 We claim that equals the total number of lines in which pass through (interpreted as a point of ). Specifically, for each , we let , which happens if and only if the line (by definition of ).
With Proposition 2.8 of [GK15], we can ensure that there are lines of inside a given plane, and such lines contained by any regulus (doubly-ruled surface7. Using the bound on the maximum number of lines per regulus, Guth and Katz proved their Theorem 2.10, which implies that there are possible intersection points between pairs of lines in . Splitting off the case , we can write Eq. 3.3 as
| (3.5) |
where the set is interpreted as a subset of , and is the point-line incidence counting function. They also find, via a lengthy argument based on polynomial partitioning,
Proposition. 4.22 of [GK15]: Let , and be a set of lines in with lines in any plane. The set of points in which meet between and lines of is , whose size can be bounded above by
Since each intersection in has line-intersection-richness in , the total number of incidences .
To apply Prop 4.22 of [GK15], we need an upper bound on the total number of lines in a given plane. We introduce
Lemma 4. Let be the horizontal () plane. For each non-horizontal plane in , let the line , and let be a direction vector chosen along . Then let be its slope relative to the horizontal plane (when seen as a graph on the vertical plane which has coordinate vectors and ), in which case we can define an associated glide reflection which reflects points across and shifts them by in the direction of . (When the plane is vertical.) Then the line iff .
Proof. We can establish coordinates in the -plane containing so that is the line , and . Then . The plane is the set , and points have coordinates and . Then
which fulfills for all iff
iff and , which is the case iff . □
As a given plane can contain no more than lines (since points in have unique image and pre-image under ), we can set . Since , combining Prop 4.22 of [GK15] with Eq. 3.5 produces
Combining Eq. 3.6 with Eq. 3.2, it follows , after which by Eq. 3.1 we have .
It is useful to define the circular weight functions for the set ,
These functions have several convenient properties: most importantly, when , so that we can be lazy with quantifiers. We have the identity , which counts points in grouped by distance from . Then . There are several upper bounds: trivially, , which is sharp by Example 2. By substituting Eq. 4.1, we find that gives the size of the equivalence class corresponding to distance ; thus by the argument from [GK15],
| (4.2) |
This expression is the strongest nontrivial bound of its type which has been proven so far.
Conjecture 5. Assuming maximum values are obtained for the grid example, it is not unreasonable to conjecture
For sufficiently large exponents, the assumption that the maximum is obtained for spatially uniform might break down, depending on how common very “concentrated” points, like the center of a polygon in Example 2, for which , may be.
4.1. Flipping the hinge problem.
As mentioned in the introduction, is the set of equivalence classes of hinges. We provide notation to count the number of elements in each equivalence class,
and identify each class with a pair . Then by Cauchy-Schwarz,
where is the set of tuples so that and . Using the circular weight functions, we count the number of hinges rooted at , and sum:
from which follows
| (4.4) |
If we assume Conjecture 5, then we get by AM-GM
which implies that if we must assume Conjecture 5 then our argument is either circular or recursive8.
4.2. Conversion to decision point before weighted incidence problems.
Next, we convert into a weighted computation over . After all,
As with the distinct distance problem, we first partition into disjoint subsets, the translational part and the rotational part , as defined in Section 3. We split into and in accordance with the split of . The former is easy to bound, since the last component of in is defined by the first three components, after which by Eq. 4.2
The second component, , is in bijection with , the set of where , the non-translational subset of the group of positively oriented rigid motions, and . Then we have
At this point, it is convenient to define the weights
and . As before, dyadic decomposition of by the richness of a given transformation yields
As in Section 3, we can identify each with a point in , and note that is the number of lines in the set which intersect with . Furthermore, since each line has the property that , and , it follows that if we associate a weight , the sum of the weights over all the lines intersecting gives . As the expression up to now is linear, we could alternatively associate weights , so that the total over all lines intersecting is .
4.3. Expected results conditional on the best possible generic lemma.
Assume that there is a lemma similar to Prop 4.22 of [GK15], which is agnostic to the structure of the line weights, except for their average value, and the maximum over all planes in of the average weight in a given line. In total, we have lines, and a maximum of lines per plane; and average line weight , and maximum average line weight in a plane. Based on Eq. 3.6, and assuming that all line weights are uniform, we would expect linearity in the line weights:9
To compute , we apply Eq. 4.2
More difficult is the computation of . Thanks to Lemma 4, we know that
for which is a trivial upper bound. For sets with perfect reflection symmetry across a given line , this upper bound is tight:
since a reflection is an isometry, and hence preserves the number of points within a given distance of . (Note that for , cannot be invariant under , since the shift operation increases the coordinates of all points when we set coordinates so that is aligned with . It may be that , and also , in which case .)
If we were to take , then
which is slightly more concentrated in than Eq. 4.2, and slightly less concentrated in than Conjecture 5.10 We could alternatively move the inside the weight expressions on 4.7; but the end result is equivalent to applying Cauchy-Schwarz on .
It may be that such an ideal generic lemma requires constraints on the norms of the weights; however, for , a bound in terms of would imply Conjecture 5 by Hölder’s inequality. Note also that Eq. 4.7 uses the lowest reasonable exponents on the line weights – the bound is false if they are less than linear – and it may be easier to prove a result for which is replaced by ; but then it makes a difference to the final result whether or not the incidence problems are computed with the line weights summed before, after, or interpolating between the two. However, with the example, if one computes incidences before summation, then the first term bounding becomes which is stronger than Conjecture 5.
Of course, including distribution information, such as the distribution of total line weights within planes, might provide a more complicated but tractable upper bound.
One of the obstacles to finding a “best possible generic lemma” is that the weights of an intersection are not always strictly greater than than the intersection multiplicity; it may often be that , or .
4.4. Double partitioning fails without further constraints.
There is a second way to compute the expressions at the end of 4.2: we can separately partition over points, by the number of lines they meet, and over lines, by their weight. We introduce notation for the second case: is the set of all lines in for which .
Specifically, Eq. 4.6 becomes
where is the point-line incidence counting function. The following theorem is particularly useful:
Theorem. 12.1 of [Gut16]. Let be a set of points and a set of lines in . Suppose that there are at most lines of in any plane, and that . Then the number of incidences is bounded as follows:
By this theorem, with the total number of lines , the total number of points , and maximum number of lines in a plane, , we get
By Chebyshev’s inequality, we find , which implies ; substituting this in yields:
While the first three terms might be reducible with Chebyshev bounds on e.g. and , the right hand side expressions and are difficult to control. The trailing term is an artifact of the specific incidence expression used: the term of Theorem 12.1 of [Gut16] is maximal when all points are placed on unique lines in , which is unlikely since there are, in total, more points than lines.
In this section, we present another approach to finding an upper bound for (which was defined in Section 4.1). In order to obtain an incidence problem for lines in , rather than lines in , we partition into three (not necessarily disjoint) components, , , and . First, we note that for each tuple , there are unique positively oriented rigid motions and for which , , and . First, if is a translation, then the tuple is in ; if is a translation, we put it in ; and . For sets , we fall back to the weighted incidence argument used to express as a sum over , after which applying Eq. 4.5 gives . As by - exchange symmetry, as well.
To control , we establish an isomorphism between and the set of triplets of transformation-representing lines , , in , defined as per Section 3, with the additional constraint intersects both and . Note, just as and , or and , need not be distinct, neither do and . However, and , so and . That maps injectively into is follows from the formula for a line, Eq. 3.4; for the reverse direction, note that and are precisely the unique positively oriented rigid motions between and , and and . Since and are independent of each other, with the set of all lines for , ,
where we define the weight as the total number of lines which intersect . As the uniform bound is not particularly useful, we partition into disjoint sets , so that iff , and then define . (A convenient upper bound for the weight is , since one can obtain for a generic polygon as described in Example 2, because there are distinct rotation angles corresponding to the maps which fix the polygon center.)
Then straightforward dyadic decomposition gives
in which case an upper bound on the number of lines in with line-richness between and would be required. As Example 10 shows, for the square grid it is possible that for ; the difficulty is in establishing the upper bound on for lines with line-richness . Of course, thanks to Proposition 2.8 of [GK15], there are at lines per regulus, and hence via their Theorem 2.10, total intersection points, so we can rule out the case that all lines each intersect all other lines.
One might expect that a double partitioning argument, as in Section 4.4, would be helpful; however, defining as the line-richness of point , we get
Applying Cauchy-Schwarz over the squared sum produces an expression amenable to such partitioning; however, for the square grid, for a constant fraction of lines there are intersections per line, for which but ; the resulting upper bound produced by Cauchy-Schwarz is then at least .
As noted by [CSS13], the method of finding a lower bound for by computing an upper bound for produces a lower bound which is off by a factor of in the square grid case, in large part because the equivalence class sizes are non-uniform.
An alternative approach to proving a tight lower bound on is to prove the bound for a class of sets , and then show, using symmetry or other constraints, that if is below some threshold then . For example, one might hypothesize that if , then either is almost a polygon (i.e., there is a polygon so that ), or is a constant density subset of a finite lattice . (“constant density subset”, just like “almost”, is a heuristic; perhaps .)
Definition 6. A finite lattice is a set of points describable as where and are distinct projections. Then . It is convenient to let be the smaller angle between and .
As the points in can be identified with their projections, we can use the law of cosines to compute distances, with .
The notation ; since is symmetric around , is unchanged if we replace with in the above expression. For lattices where and have high translational symmetry, that is, , and , it follows immediately that .
We now address the specific cases where and are both arithmetic progressions. We also define .
Lemma 7. Let and ; let be the finite lattice determined by the intersection of their inverse projections at cross angle . If or , then
Proof. Thanks to scale invariance, we can assume . Then and . For , and , the distance corresponding to is , for . Furthermore, when points have coordinates and , then . There are three cases: Case 1. , .
Proof. Assume that there are for which . If , then from , we derive , so all terms in the left hand side are in . If , then which has two solutions classes (, ), neither of which provides more than one solution per value of . Thus . □
Proof. Assume there are where for which . This would be a contradiction, since then
which is in since is closed under field operations. On the other hand, if there are where while , then . For fixed and , there are at most four solutions in , hence at most four solutions in . As, by the earlier argument, there cannot be more than one value of per value of (lest ), has at most four solutions. Thus . □
Proof. If , then we scale , , and exchange the roles of x and , falling back to case 1. Otherwise, the map is almost injective, since , , and form an independent basis over for the space of possible solutions; would then require , , and (since ) ; there are precisely two solutions, and . Thus . □
Combining all three cases gives . □
Lemma 8. Let and , and as before, with cross angle . Assume furthermore that and . Then for some constant depending on , , and .
Proof. We use a similar setup as for the proof of Lemma 7. Since , and , we can scale be an integral factor without affecting , so that we can write as a binary integral quadratic form, , where (i.e, is primitive). Then . Since computes a squared distance, it is positive definite, and its discriminant . Now, consider as a rectangular lattice, one which the level sets of are ellipses; with , there is some maximal for which for all , is contained in ; and some minimal for so that . According to Paul Bernay’s thesis[Ber12], the total number of integers which are representable by is for some . Thus
controls the size of the distance set. By [MO06], the hex lattice has minimal with , i.e, the number of distances per covolume11, so if the lattice is of similar aspect ratio as the level set ellipses, then , and there is a universal constant for which . □
Remark. It is easy to empirically investigate the distinct distance set sizes for lattices whose coordinates are arithmetic progressions. For quadratic binary forms , there is an time-and-memory algorithm, which, in addition to computing , incidentally produces for all . Consider the partial combined ( and )-sums of the distance set sizes, so that . Then , where to compute we first compute for all (the set of -representable integers) the lists of values for which , and remove all pairs which dominate some other pair in the list (so that and ). W initialize , and then for each dominating element, increment the corresponding counter. The remaining elements are sorted ascending by , after which, for each , we increment . This procedure ensures that for a rectangle containing the entire list , the squared distance is counted exactly once.
With suitable uniformity conditions, it is possible to show that as the lattices become progressively elongated (and cover progressively smaller fractions of any minimal ball containing them), . A specific case was proven by [CSS13], who showed that for , if , and , then , but their method does not easily generalize to general binary quadratic forms, and is incapable of handling e.g. and .
We define to be the number of points on for which . Following [BG06], we define to be the total number of for which . Clearly . By counting the pairs in and the mean number of values of that they contribute, we obtain
Note that for , , and the sum over evaluates to , while when we have , for almost all , and then . The tricky part in proving a lower bound on is showing that for close to , the sets of points representing a value are not very spatially clustered. Some work has been done in this area; for instance, Theorem 5.11 of [Dia15] considers the ideals of the ring of integers of (whose representation counting function is similar to that for binary quadratic forms) and finds a maximum discrepancy bound between the total number of representations in a sector of given angle and the number of representations that would be expected if all representations were uniformly distributed over a circle.
Example 9. For a constant fraction subset of points (the central quarter), and a constant fraction subset of radii (those are less than a quarter the diameter of ), it is the case that for all , since the circle of radius around intersects precisely the gridpoints which also lie in (which, for a point more than away from the boundary, is all of them.) Then equals the representation counting function for the quadratic form . Thanks to [BG06], the various asymptotic moments of are straightforward to compute, and so are lower bounds on the upper bounds for expressions based on . From their Corollary 1, for any binary quadratic form (such as ), and ,
and hence for any , we have specifically
This makes it straightforward to compute that, for the square grid, via Eq. 4.2,
where we use a single representative for all the . Similarly, for the hinge problem, we obtain for Eq. 4.4,
Example 10. The appendix of [GK15] shows that for the square grid, the number of -line-intersection-rich points in the 3d incidence problem is at least . We re-purpose their proof to show that, for the square grid, a constant fraction of lines have point-richness and line-richness ; i.e, , and .
Let be a grid of points centered on the origin. Then . We let be the set of lines in corresponding to non-translational positively oriented rigid motions mapping e.g. to , with parameterization according to Eq. 3.4. By Lemma A.1 of [GK15], there is a subset for which , where the lines are those which pass through the points and in , where . For every integer , and integer , the plane at height intersects all of the lines in . Furthermore, since the lines in pass through integer lattices at heights and , at height (with in lowest terms), the lines in pass through a uniform lattice with spacing and points in total.
We define to be the set of lines in for which ; we have. Then by translation invariance12 for motions shorter than , all lines in pass through the same number of lines in at height , namely, of them. As any pair of lines can intersect at most twice, the total number of intersections 13 between a line in and the lines of , is
where is Euler’s totient function and the identity is easily derived from . (See for instance [PS92], section 3.)
As for different lines , it follows . Furthermore, since each line intersects at least one other line in for different heights, .
Most of the contents of this paper were developed and presented during the Fall 2018 semester class on the polynomial method; special thanks to Jonathan Passant, who developed the line-based incidence conversion, to Alex Iosevich, for introducing the problem and to everyone else in the group, without which this paper would have even more holes.
Paul Bernays. Über die Darstellung von positiven, ganzen Zahlen durch die primitiven, binären quadratischen Formen einer nicht-quadratischen Diskriminante. Dieterich, Göttingen, 1912.
Valentin Blomer and Andrew Granville. Estimates for representation numbers of quadratic forms. Duke Math. J., 135(2):261–302, November 2006. doi: 10.1215/S0012-7094-06-13522-6. url: https://doi.org/10.1215/S0012-7094-06-13522-6.
David Brink, Pieter Moree, and Robert Osburn. Principal forms x2+ny2 representing many integers. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 81(2):129, September 2011. issn: 1865-8784. doi: 10.1007/s12188-011-0059-y. url: https://doi.org/10.1007/s12188-011-0059-y.
Javier Cilleruelo, Micha Sharir, and Adam Sheffer. On lattices, distinct distances, and the elekes-sharir framework. arXiv preprint arXiv:1306.0242, 2013.
N.G. de Bruijn. Algebraic theory of penrose’s non-periodic tilings of the plane. ii. Indagationes Mathematicae (Proceedings), 84(1):53–66, 1981. issn: 1385-7258. doi: https://doi.org/10.1016/1385-7258(81)90017-2. url: http://www.sciencedirect.com/science/article/pii/1385725881900172.
Dimitri Dias. Dénombrement dans les empilements apolloniens généralisés et distribution angulaire dans les extensions quadratiques imaginaires. PhD thesis, Université de Montréal, 2015.
Larry Guth and Nets Hawk Katz. On the erdös distinct distances problem in the plane. Annals of Mathematics, 181(1):155–190, 2015. issn: 0003486X. url: https://www.jstor.org/stable/24522951.
Larry Guth. Polynomial Methods in Combinatorics. American Mathematical Society, 2016. isbn: 978-1-4704-2890-7.
A. Iosevich and J. Passant. Finite point configurations in the plane, rigidity and Erdos problems. arXiv e-prints:arXiv:1805.08065, arXiv:1805.08065, May 2018. arXiv: 1805.08065 [math.CO].
P Moree and R Osburn. Two-dimensional lattices with few distances. Technical report math.NT/0604163, April 2006. url: https://cds.cern.ch/record/941374.
János Pach and Micha Sharir. Repeated angles in the plane and related problems. Journal of Combinatorial Theory, Series A, 59(1):12–22, 1992. issn: 0097-3165. doi: https://doi.org/10.1016/0097-3165(92)90094-B. url: https://www.sciencedirect.com/science/article/pii/009731659290094B.
1When we say , we mean that there is a universal constant for which . Furthermore, we define so that iff and .
2According to [CSS13], extremely elongated rectangular grids instead yield distances.
3The best asymptotic class is probably the intersection of a hexagonal/triangular grid with a disk.
4This generalizes to seven, nine, etc. sided patterns; see also https://www.mathpages.com/home/kmath621/kmath621.htm, and [dBru81] which introduced the method.
5It may be clearest to say that we assign coordinates to the set ; then it is valid to treat as both a point in and a non-translational positively oriented rigid motion of .
6Evaluating gives .
7Specifically, any linear transformation of a hyperbolic paraboloid/parabolic hyperboloid, or hyperboloid of one sheet ; reguli can be defined using three skew lines.
8For example, if then if ; but if , the inequality is useless.
9The exact tradeoff may differ, but the term almost certainly depends on , in which case the analysis of this section analysis is unchanged.
10Applying Muirhead, AM-GM, or Cauchy-Schwarz, we find Conjecture 5 implies Eq. 4.8 which implies Eq. 4.2.
11The computation of is covered in more detail by [BMO11].
12To be precise, this only ensures that the number of lines passing through at height is the same as the number passing through . Because shifting an endpoint of the line segment from to by one translates the intersection point of the line by (or ), and (so that we can attain any fractional or coordinate), we can transform the bundle of all lines passing through e.g. to pass through .
13, as we overcounted intersections between as a member of and as a member of .