Notes on the Erdős distinct distance problem and variations

December 5, 2018

1 Notation and problems

The distinct distance problem is defined in [GK15]. We use and to denote being bounded above and bounded below by a function of ; may be omitted for laziness or when the constant is independent of .

Let be a set of points with size .

is the set of nonzero distinct distances. is the set of nonzero distinct distances relative to point .

is the set of pairs of distances relative to a given point, a.k.a. hinges. Note that .

Conjecture 1. Distinct distance problem: . The pinned distinct distance problem claims .

Theorem 2. (Guth-Katz, [GK15]). , as a corollary of the fact that, with the number of times a distance is present, .

Conjecture 3. Pinned hinge problem: . (Implied by pinned distinct distance, since ; the current best bound is from Thm 2.)

The number of pinned distances can be bounded below using upper bounds on a construct called the bisector energy[LP18].

2 Useful examples

Example 4. Polygon with a point at the center. There are radial points, and very close to distinct distances. Thus , .

Example 5. Crossing circles. Given two points , separated by distance , let be the set of all points whose distances to and to are in . Then .

Example 6. Multiple circles: duplicate 4 multiple () times; then there are multiple points for which a single distance is present times.

Example 7. The Penrose tiling has high translational symmetry and does not immediately appear gridlike; however, it turns out that all Penrose tilings can be constructed via the pentagrid method1, in which case the projections along each axis yield sets of size that are small convolutions of a simple arithmetic sequence. Calculations show that, for roughly circular domains and large (, , .

Example 8. Square grid. . Then , from the density of sums of squares of integers.[Tho73].

Also, following the appendix, if we consider the set of lines for where denotes the line expressing of rigid transformations (except for pure translation) mapping to , then with the subset of lines which intersect other lines, we have for . . [TODO: copy proof in notes; mention [PS92] who get the same .] [TODO: also show that the hinge problem can not be resolved any better by this method]

Remark 9. Use for . Note [MO06] shows that the hex lattice gives minimal at , i.e., distances per covolume (weighted by ). See also [BMO11]: in general, can get arbitrarily close to with larger , and is also unbounded above for both positive and negative , although grows much faster than .

Remark 10. As expected of Cauchy-Schwarz (optimal when uniform), via [CSS13], Elekes-Sharir isn’t optimal. Furthermore, given a right angle integer lattice with ratios , , for , get .

Remark 11. There is a algorithm to compute all dominated rectangle distance set sizes for e.g. . (Consider the partial combined ( and )-sums of the distance set sizes, so that . Take , where to calculate , we first compute, for all , the lists of values for which , sorted ascending. Then we add one for for all . See Figure1.) Figure 1: Plots of for on the left, and on the right. In the symmetric case, the main diagonal is very concentrated; i.e. .

Heuristically, since most , for large values, and the diagonal component is (?); and if , the total sum resolves to ; if , then the diagonal component is not included beyond a point, leaving . Which still yields incorrect results along , but at least has the correct behavior along .

Under the hypothesis of radially uniformly distributed representations for , we find , and among the values of which are present, , where ; so that

Note that for , this is almost , and for , grows much more slowly than shrinks, so that the right part of the equals one for sufficiently elongated rectangular grids, leading to . A result giving the distribution of over some interval might help produce a closed form.

Alternatively, under the uniform hypothesis: let , approximated for as , be the length of the intersection of the level set of with the rectangle. Then (sketchily)

 |∆|∼x,y≤na,nb,k=f(x,y)min1,1rf(k)γf(k) (1)

Now, within a given dyadic interval , using [BG06], , , etc. Since changes slowly, we set . Let be the fraction of the elements for which , i.e., ; clearly then , so that ; the other estimate gives, , although with a different constant. Either way, the sum 1 can be decomposed into ring sections with ; on each ring, given suitable uniformity, , since there is a chance that is greater than one. On very elongated rectangles, each ring contains elements, and has , so that , in which case the contribution to of the ring section is approx . Reasonably even rectangles have , and those rings contribute .

3 Distinct distance problem for lattices with uniform spacing

Consider a set of points. Let be a projection onto one direction, and be a projection in some other direction. Assume , so that is the grid produced by the . Let be the larger angle between the two directions, and let : then each element has coordinates , and

and , is

Theorem 12. If , and , then , which implies and .

Proof. since each value in is defined by a pair . __

Definition 13. Let .

Theorem 14. Let , and ; let be the lattice determined by their inverse projections at cross angle . (.) Then , which implies and .

Proof. Without loss of generality (by scaling everything), . We choose to be the smaller angle between the projection directions, so that that . Note also that , and ; Then with , and writing ., . Note that , with since . Case 1. and .

Proof. Let , be in least terms. Then evaluates to

which on rescaling gives . According to Paul Bernays’s 1912 thesis[Ber12], the total number of integers which are representable by in terms of the expression defining this last set is where is a constant function of the discriminant , if (as ) and the quadratic form is primitive and positive definite. (Note that can not be factored over , since .) Dividing by the quadratic form by ensures that it is primitive, at only constant factor change in , and the form is positive definite as a linear transformation of positive definite . Consider as a rectangular lattice, on which the level sets of are ellipses; with , there is some maximal for which for all , is contained in ; and some minimal so that . Thus

controls the size of the distinct distance set. When , a tight lower bound is harder to achieve.

The paper [CSS13] finds a lower bound for in the rectangular case when , but resolves to counting duplicates (and hence probably can’t bypass ), uses the weak bound , and relies on factorization tricks not applicable to the general case. A uniformity result for sectors of general integral binary quadratic forms, like the specific (to forms with fundamental discriminant) result [Dia15], perhaps with [BG06] for bounds on representations, could work, if suitably averaged to limit the effect of discrepancy terms. It may be necessary to unpack [Ber12], to finish the proof. __

Case 2. , .

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

Case 3. , .

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

Case 4. and .

Proof. If , then we scale , , and exchange the roles of x and , falling back to case 2. 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 . __

__

3.1 Extending to when e.g. |A−A|=s(|A|)|A| for s(x)∼x.

Problem 15. General plan: first, solve the equivalent to Thm 14 for and generalized arithmetic progressions; second, use approaches like Green-Ruzsa [GR] / Cwalina-Schoen [CS13] to show that is “close” enough to an arithmetic progression that the distinct distances are changed by at most a constant (which should be a function of and . Finding too-large upper bounds and lower bounds in this way is easy, so it may not pan out.

Example 16. Consider symmetric grids (i.e, like for some offset grid). , , and , so that , where . It is possible that all of , , , , , and are in , and also possible that they (and their ratios) are all linearly independent. There are also additional constraints: if , then implies but not the other way around (For instance, for the th prime, and .) If all values are in , one ranges from a Cantor-like set scenario to full density (.).

We pick a specific case: , , . Then . Assume we have multiple with the same ; then matching terms, we find , , , , and , yielding an overdetermined system (five doubled quadratic equations for six unknowns); by symmetry, there are an even number of solutions. Solving this by hand, we assume and ; then, implies , so if , implies , so if then implies . If , then we must solve , , and , and to counter symmetry we assume ; continuing, we find either (trivial case, can be ignored) (and we have two solutions), (two solutions), only (two solutions), etc. Ultimately .

Alternatively, consider , , ; this gives , which implies for values of that , , , and ; four quadratic equations, with three unknowns. If , we have and similarly for and , yielding two symmetrical solutions. With , we have , which as the intersection of a hyperbola and ellipse has solutions; similarly for cases and .

The Penrose tiling specifically produces , , , , and . Then we have

. Of course, , and , so this reduces to

Then for a given value , we apply casework nine times on , each time resulting in , , a pair of equations corresponding to an ellipse and to a parabola, whose intersection has solutions in . Correspondingly, the grid associated with the Penrose tiling produces .

Just as irrationality can prevent multiply-counted pairs, so too can scale discrepancies. Let , for . Furthermore, ; then , and . This is the square grid case. Alternatively, use , , , in which case , , so that any can be uniquely split into large () and small () components depending on and respectively; this implies . A more difficult case is general , , , for . Then . If , then we have ; at , . This evaluates to . There are two main symmetries, exchange and negation symmetry; so WLOG as base numbers. Evaluating yields , which lets us determine how many of and are nonzero; the symmetry assumption resolves to one unknown case . The next digit yields , and after that, , and taking lets us know if only one of or is nonzero; more extremal values provide more information. The space of possible digit combinations is much larger than the possible pairs, so one might conjecture that , are uniquely identifiable from their base multiplication (convolution).

Conjecture 17. If any of are , then for some constant , possibly a function of .

3.2 Translational vs rotational symmetry

Translational and rotational rigid motions are very different from each other. When only one symmetry type is considered, get (e.g, transcendental grid, circle.) To get below , require significant rotational symmetries – i.e., points relative to which others are relatively densely on circles, as well as translational symmetries – lines. Are there non-lattice-subset set classes which reach below ?

4 Guth-Katz-style weighted incidence problems resulting from the hinge problem

We conjecture a average-weighted variation on Prop 4.22 in [GK15], whose proof remains to be shown. It is useful in proving variants of a sum like that used for Guth-Katz. The distribution of weights may be required to prove this, and potentially introduce a factor-of-log loss.

Conjecture 18. Let , and a set of lines with total weight , average weight in with weight in any plane. The number of points whose total intersection weight with is between and is . Then . (This is chosen for homogeneity in , with fixed , , . However, it is not practically useful, because all too often, the line weights are zero, in which case there is no clear relationship between total intersection weight and simple intersection weight.)

Definition 19. Given a set , , and , define .

For the following theorem, we disregard distances which might be , as they contribute only small constants.

Theorem 20. We assume Conjecture 18. Then as defined above, is a set of points, and is the set of hinge classes of . Then .

Proof. Clearly, . Then by Cauchy-Schwarz,

where

 (E):=r,s∈∆x∈Eωr(x)ωs(x)2 (2)

Then rearranging gives . We claim . To prove this, we expand and note that the conditions and , summed over all , resolve to :

Next, let be the group of positively oriented rigid motions of the plane, for given , let . We establish a bijection between the set of tuples where with the additional constraint that , and the set of tuples where . By Prop 2.3 of [GK15], since , there is a unique for which and ; thus is mapped to . (Since , , so .) On the other hand, given , there is a unique , which (as is a rigid motion) has the property that ; and since , it follows and , so that .

Reindexing and dyadically partitioning with , giving sets of simple (intersection) multiplicity , we find (defining weighted multiplicity )

We can partition the group into two components: the translational part and , the rotational part. The Eq. 3 is simple to bound for the translational component: we have, for each , that

where the last inequality is a reindexing: each pair corresponds to a unique (by ), and vice versa (with the translation by ). Summing over all , we find which by 2 is . 2

For the rotational part, we embed the curves of rigid motions mapping point onto as lines . There are two obvious ways of configuring the weights: with the sum over pulled all the way in (so that nonlinearity applies to it), or kept outside.
Case 1. Weights specific to distances. We set the weight of a given line , so that the total weight/multiplicity of a point is

Adding over all gives the total line weight . Following Prop 2.8, within a given plane there cannot exist two distinct transformation lines whose elements share “start” and “end” points, i.e, if and are in the same plane, then and . A straightforward upper bound – not involving much more geometric information – gives

where this last upper bound is by the rearrangement inequality. The exact upper bound for does not matter in the upcoming argument; we take for some constant . The mean line weight is .

Note that it is possible for for an intersection, just as is possible. Consequently, there need not be a direct relationship between (simple intersection count), and (weighed intersection count). This makes everything trickier.
Case 2. Weights summed over all distances. Observe then that , in which case the point multiplicity is defined as . Adding over all yields , while the simple bound on is , for which the circular result is , presumably. The lowest possible weight of a line is – consider the generic case, in which only for is there a contribution, and largest possible , i.e. which and over different distances, which happens in the crossing circles case (Example 5).

Remark 21. For a given plane, which transformation lines does it contain? Each transformation line , where we label coordinates . Horizontal () planes contain no lines, as lines always have nonzero z-slope. All other planes intersect the plane on a line , and relative to the horizontal plane have maximum slope , where the case corresponds to vertical planes. Then a plane contains precisely the transformation lines between for which , in which denotes the transformation given by reflecting over the line and then translating along the direction of by ; flipping the direction of is equivalent to negating . (This is straightforward to show geometrically: restricting to the plane, plane is the line , and the line is the point , which must be on the line. Without loss of generality, we fix coordinates so that is the -axis, , ; then the plane is defined by the equation , and is ; so lies in iff iff .)

Consequently, consider any set invariant under a glide-reflection symmetry , i.e., so that . Since glide-reflection is an isometry, distances are preserved, and hence . Then , and ; any general upper bound on or would need to agree with this specific case.

Even assuming , via Conj. 18, the first case we arrive at an expression like which is significantly sharper than our goal (since ), and evaluates, for the regular square or hex grid, to . In the second case, we lose a factor of and a few as the relationship between and is still unclear; if we assume the counterfactual , then the end result resolves to terms controlled by Thm 2 and the circular argument.

TODO: either prove or prove unprovable by this method.

_

References

[Ber12]

Paul Bernays. Über die Darstellung von positiven, ganzen Zahlen durch die primitiven, binären quadratischen Formen einer nicht-quadratischen Diskriminante. Dieterich, Göttingen, 1912.

[BG06]

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.

[BMO11]

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.

[CS13]

Karol Cwalina and Tomasz Schoen. A linear bound on the dimension in green-ruzsa’s theorem. Journal of Number Theory, 133(4):1262–1269, 2013. issn: 0022-314X. doi: https://doi.org/10.1016/j.jnt.2012.09.012. url: https://www.sciencedirect.com/science/article/pii/S0022314X12003046.

[CSS13]

Javier Cilleruelo, Micha Sharir, and Adam Sheffer. On lattices, distinct distances, and the elekes-sharir framework. arXiv preprint arXiv:1306.0242, 2013.

[Dia15]

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.

[GK15]

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.

[GR]

Ben Green and Imre Z. Ruzsa. Freiman’s theorem in an arbitrary abelian group. Journal of the London Mathematical Society, 75(1):163–175. doi: 10.1112/jlms/jdl021. eprint: https://londmathsoc.onlinelibrary.wiley.com/doi/pdf/10.1112/jlms/jdl021. url: https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/jdl021.

[LP18]

B. Lund and G. Petridis. Bisectors and pinned distances. ArXiv e-prints, October 2018. arXiv: 1810.00765 [math.CO].

[MO06]

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.

[PS92]

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.

[Tho73]

George B Thomas. Density properties of primes, squares, and sums of squares. Advances in Mathematics, 10(3):383–386, 1973. issn: 0001-8708. doi: https://doi.org/10.1016/0001-8708(73)90120-5. url: https://www.sciencedirect.com/science/article/pii/0001870873901205.

1This generalizes to seven, nine, etc. sided patterns; see also https://www.mathpages.com/home/kmath621/kmath621.htm.

2This is tighter than the bound we would expect in general; the same approach on the normal distinct distance problem gives (using ), tighter than Lemma 2.12 of [GK15], but not unexpected when we consider the argument up to now could have been adapted for equivalence classes of vectors.

Return to main page | as PDF