png im- age svg di- a- gram Approaches for the hinge and distinct distance problems

APPROACHES FOR THE HINGE AND DISTINCT DISTANCE PROBLEMS

MANUEL STOECKL

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.

1. Introduction

For a finite set ER2 with N elements, we define an equivalence relation over pairs of points in E2 so that (x,y)(x,y) when |xy|=|xy|, where |·| denotes the Euclidean norm. Each equivalence class, represented by (x,y), corresponds to the distinct distance r=|xy|, so that the set of equivalence classes is equivalent to the distance set defined by

(E):={|xy|:x,yE}

The current best general lower bound known for the size of the distance set is from [GK15] and is given by (E)N/logN.1 On the other hand, the smallest asymptotic distance set size observed for a class of sets is N/logN, 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 E3 for which (x,y,z)(x,y,z) iff |xy|=|xy| and |xz|=|xz|. A trivial upper bound is given by a generic set of N points, in which case all hinges are unique (up to degenerate cases like (x,x,x)), leaving N3 equivalence classes. We call the set of distance pairs produced by hinge equivalence classes H(E).

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

x(E):={|xy|:yE},

that maxxE|xE|N/logN. As the number of hinge equivalence classes represented by hinges with fixed x is |x(E)|2, this implies a hinge lower bound of |H(E)||x(E)|2N2/logN. Similarly, since (E)x(E) for all x, it would imply that |(E)|N/logN.

We introduce the symbol || to concisely express and distinguish dyadic sums,

||NX=mf(X):=log2(N/m)i=0fm2i.

For later use, we define the point-line incidence function, applied to a set of points S and set of lines L:

I(S,L):=|{(s,)S×L:s}|.

2. Distance set examples

Example 1. The square grid is the best known asymptotic example, within a constant.3 We pick SN, let N=S2, and define E=(x,y)Z2:0x,y<S. Note that E has significant translational and reflective symmetry; there are many isometries I for which |IEE||E|. The number of distinct distances is N/logN, as will be calculated later in Section 6. This asymptotic is significantly different for other distance metrics: under 1 and distances, there are N distinct distances, and a metric produced from a generic convex set produces N distinct distances, since thanks to translational symmetry, (E)=xcornersx(E) where x is a corner point, e.g., a point (0,0), (0,S1), (S1,0), or (S1,S1).

Example 2. Another extremal example is optimized to the Euclidean distance metric, rather than to translational symmetry. Here,

E={(0,0)}cos2πkN1,sin2πkN1:k=0...N2

defines a regular N1 -sided polygon with a central point O=(0,0). The pinned distance set O(E)={0,1}, while ||x(E)|N/2|2 for all other xE,x=O.

We can interpolate between this and the grid by creating E=0x,yk(E+(x,y)), which has k2 points Oi for which N/k2N points are a distance of 1 away from Oi.

A “generic” polygon is produced by taking a generic set FR/Z for which |F|=N1, and |F+F|=(N1)(N2)/2; then

E={(0,0)}{(cos2πf,sin2πf):fF}.

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 E is the subset of a Penrose tiling filling a disk, then the projections of E along five specific directions have size |E|, so that E is a constant-density subset of a lattice. By an argument similar to 7, one can show that |(E)|N.

3. Incidence formulations for the distinct distance problem

In this section, we present an minor variation on the method used in [GK15] to convert the lower bound on (E) into a set of incidence problem upper bounds. Let nr be the size of the equivalence class of distance r:

nr:=(x,y)E2:|xy|=r

Then, counting all nonzero equivalence classes, we find r>0nr=N2N, after which by Cauchy-Schwarz we have

N4r>0nr2r>01r>0n2r(|(E)|1)|Q(E)|

where we define Q(E) to be the set of all quadruples (x,y,x,y)E4 for which |xy|=|xy|>0. Rearranging,

|(E)|N4/|Q(E)|.
(3.1)

To prove that |(E)|N/logN, we must show that |Q(E)|N3logN. (This upper bound is the tightest attainable, as shown in Section 7.) First, we split Q(E) into two disjoint sets, Qr(E) and Qt(E), namely the rotated and translated quadruples. The subset Qt(E) is defined as the set of quadruples (x,y,x,y)E4 for which the vector identity xy=xy holds. Since each such tuple can be identified with (x,y,x)E3, as y=x+yx, it follows

|Qt(E)|N3.
(3.2)

It remains to prove that |Qr(E)|N3logN. To do this, let G be the set of positively oriented non-translational rigid motions of the plane, and establish a bijection between Qr(E) and the set Q, defined as the set of all (x,y,g), where gG, x,yg1EE, and x=y. By Prop 2.3 of [GK15], for a given tuple (x,y,x,y)E4 where |xy|=|xy|>0, there is a unique g for which g(x)=x and g(y)=y. Since g(x)E and g(y)E, it follows xg1E and yg1E, so that the tuple (x,y,g)Q. On the other hand, given (x,y,g)Q, we define x=g(x) and y=g(y); these exist since x,yg1E, and since g is an isometry, |xy|=|xy|, which is >0 since x=y. Thus (x,y,x,y)Qr(E). Correspondingly, we have

|Qr(E)|=|Q|=x,y,gQ1=gGx=yg1EE1gGg1EE2

We partition G into disjoint sets G=k defined so that for all gG=k, g1EE=k. We also define Gk=jkG=k, so that by dyadic decomposition

|Qr(E)|Nk=2|G=k|k2Nk=2k2|G=k|(3.3)||NK=22K1k=Kk2|G=k|4||NK=2K2|GK\G2K|

The set GK\G2K consists of all g for which g1EE[K,2K)N; GN+1=, as g1EE|E|=N.

We now construct an incidence problem which will provide an upper bound on GK\G2K. To a given rigid motion gx,yG which fixes the point (x,y) and rotates by plane by angle θ around that point, we associate the point x,y,cotθ2R3.5 As g is non-translational, θ≡0, so that the point is well defined. Next, we define the set of lines L={Lxy:x,yE,x=y}, where each individual line LpqR3 contains all gG which map p to q. This line, as proven by Prop 2.7 of [GK15], can be parameterized by tR as

p+q2+tˆz×p+q2+ˆz
(3.4)

where we consider p and q as points on the z=0 plane in R3, and ˆz the unit (0,0,1) vector, and × the (standard, right-handed) cross product.6 We claim that g1EE equals the total number of lines in L which pass through g (interpreted as a point of R3). Specifically, for each xg1EE, we let x=g(x)E, which happens if and only if the line Lxxg (by definition of Lxx).

With Proposition 2.8 of [GK15], we can ensure that there are N lines of L inside a given plane, and N 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 N3 possible intersection points between pairs of lines in L. Splitting off the case k=2, we can write Eq. 3.3 as

|Qr(E)|N3+||NK=3K2I(GK\G2K,L)
(3.5)

where the set GK\G2K is interpreted as a subset of R3, and I is the point-line incidence counting function. They also find, via a lengthy argument based on polynomial partitioning,

Proposition. 4.22 of [GK15]: Let k3, and L be a set of L lines in R3 with B lines in any plane. The set of points in R3 which meet between k and 2k lines of L is G[k,2k), whose size S can be bounded above by

SL3/2k2+LBk3+Lk1

Since each intersection in G[k,2k) has line-intersection-richness in [k,2k), the total number of incidences I(Gk\G2k,L)2kS.

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 H be the horizontal (z=0) plane. For each non-horizontal plane P in R3, let the line =PH, and let ˆ be a direction vector chosen along . Then let 1/s be its slope relative to the horizontal plane (when seen as a graph w↦→z on the vertical plane which has coordinate vectors ˆw=ˆ×ˆz and ˆz), in which case we can define an associated glide reflection R,s which reflects points across and shifts them by 2s in the direction of ˆ. (When s=0 the plane is vertical.) Then the line LpqP iff R,s(p)=q.

Proof. We can establish coordinates in the (x,y)-plane containing E so that is the line {(x,y,z):x=z=0}, and ˆ=ˆy. Then ˆw=ˆx. The plane P is the set {(x,y,z):z=x/s}, and points p,q have coordinates (px,py,0) and (qx,qy,0). Then

Lpq=px+qx2+tqypy2,py+qy2+tpxqx2,t

which fulfills sz=x for all t iff

px+py2+tqypy2=st

iff px=qx and qy=2s+py, which is the case iff q=R,s(p).

As a given plane can contain no more than N lines (since points in E have unique image and pre-image under R,s), we can set B=N. Since |L|=LN2, combining Prop 4.22 of [GK15] with Eq. 3.5 produces

|Qr(E)|N3+||NK=3K2N3/K2+N3/K3+N2/KN3+||NK=3N3+N3/K+N2KN3+N3logN+N3+N3N3logN(3.6)

Combining Eq. 3.6 with Eq. 3.2, it follows |Q(E)|N3logN, after which by Eq. 3.1 we have |(E)|N/logN.

4. Weighted incidence formulations of the hinge problem

It is useful to define the circular weight functions for the set E,

ωs(x):=|{yE:|xy|=s>0}|(4.1)

These functions have several convenient properties: most importantly, ωs(x)=0 when s/x(E), so that we can be lazy with quantifiers. We have the identity sωs(x)=N1, which counts points in E\{x} grouped by distance from x. Then xsωs(x)=N2N. There are several upper bounds: trivially, ωs(x)N1, which is sharp by Example 2. By substituting Eq. 4.1, we find that xωs(x) gives the size of the equivalence class corresponding to distance s; thus by the argument from [GK15],

|Q(E)|=sxωs(x)2N3logN.
(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

sxωs(x)2N2logN

For sufficiently large exponents, the assumption that the maximum is obtained for spatially uniform ωs(x) might break down, depending on how common very “concentrated” points, like the center of a polygon in Example 2, for which ω1(O)=N1, may be.

4.1. Flipping the hinge problem.

As mentioned in the introduction, H(E) is the set of equivalence classes of hinges. We provide notation to count the number of elements in each equivalence class,

nr,s=|{(x,y,z):|xy|=r>0;|xz|=s>0}|

and identify each class with a pair (r,s)R2. Then by Cauchy-Schwarz,

N6r,sH(E)nr,s2r,sH(E)1r,sH(E)n2r,s|H(E)||U(E)||H(E)|N6/|U(E)|(4.3)

where U(E) is the set of tuples (x,y,z,x,y,z)E6 so that |xy|=|xy|>0 and |xz|=|xz|>0. Using the circular weight functions, we count the number of (r,s) hinges rooted at x, and sum:

nr,s=xEωr(x)ωs(x)

from which follows

|U(E)|=r,sxωr(x)ωs(x)2
(4.4)

If we assume Conjecture 5, then we get by AM-GM

|U(E)|=r,sxωr(x)ωs(x)2=r,sx,xωr(x)ωr(x)ωs(x)ωs(x)14x,xr,sωr(x)2+ωr(x)2ωs(x)2+ωs(x)212Nxr,sωr(x)2ωs(x)2+12xxr,sωr(x)2ωs(x)212Nxtωt(x)2+12txωt(x)22N4+N2logN2=N4(logN)2

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 |U(E)| into a weighted computation over Q(E). After all,

|U(E)|=(x,y,z,x,y,z)U(E)1=(x,y,x,y)Q(E)|xz|=|xz|1=(x,y,x,y)Q(E)rωr(x)ωr(x)=r(x,y,x,y)Q(E)ωr(x)ωr(x)

As with the distinct distance problem, we first partition Q(E) into disjoint subsets, the translational part Qt(E) and the rotational part Qr(E), as defined in Section 3. We split U(E) into Ut(E) and Ur(E) in accordance with the split of Q(E). The former is easy to bound, since the last component of (x,y,x,y) in Qt(E) is defined by the first three components, after which by Eq. 4.2

|Ut(E)|=rx,y,x,yQt(E)ωr(x)ωr(x)r(x,y,x)E3ωr(x)ωr(x)Nrxωr(x)2N4logN(4.5)

The second component, Qr(E), is in bijection with Q, the set of (x,y,g) where gG, the non-translational subset of the group of positively oriented rigid motions, and x,yg1EE. Then we have

|Ur(E)|=rx,y,gQωr(x)ωr(g(x))rgGx,yg1EEωr(x)ωr(g(x))

At this point, it is convenient to define the weights

mr(g):=xg1EEωr(x)ωr(g(x)),

and m(g)=rmr(g). As before, dyadic decomposition of G by the richness k=g1EE of a given transformation yields

|Ur(E)|rgGg1EEmr(g)r||NK=2KgGK\G2Kmr(g)=||NK=2KgGK\G2Km(g)(4.6)

As in Section 3, we can identify each gG with a point in R3, and note that g1EE is the number of lines in the set L={Lpq:p,qE} which intersect with g. Furthermore, since each line Lxxg has the property that x=g(x), and xg1EE, it follows that if we associate a weight mr(Lxx)=ωr(x)ωr(x), the sum of the weights over all the lines intersecting g gives mr(g). As the expression up to now is linear, we could alternatively associate weights m(Lxx)=rωr(x)ωr(x), so that the total over all lines intersecting g is m(g).

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 R3 of the average weight in a given line. In total, we have L=|L|=N2 lines, and a maximum of B=N lines per plane; and average line weight µr, and maximum average line weight υr 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

|Ur(E)|rL3/2µr+L3/2µrlogN+LBµ1/2rν1/2r+rN(4.7)L3/2µ+L3/2µlogN+LBrµ1/2rν1/2r+LµN

To compute µ=rµr, we apply Eq. 4.2

µ=1N2Lxxm(Lxx)=1N2rx,xωr(x)ωr(x)NlogN

More difficult is the computation of rµ1/2rν1/2r. Thanks to Lemma 4, we know that

νr=1Nmax,sxR1,sEEωr(x)ωr(R,s(x))

for which N1xEωr(x)2 is a trivial upper bound. For sets with perfect reflection symmetry across a given line , this upper bound is tight:

xR1,0EEωr(x)ωr(R,0(x))=xEωr(x)ωr(R,0(x))=xEωr(x)2

since a reflection R,0 is an isometry, and hence preserves the number of points within a given distance of x. (Note that for s=0, E cannot be invariant under R,s, since the shift operation increases the y coordinates of all points when we set coordinates so that y is aligned with . It may be that R1,sEE|E|, and also ωr(x)ωr(R,s(x)), in which case µrxEωr(x)2.)

If we were to take νr=1NxEωr(x)2, then

rµ1/2rν1/2r=1N3/2rxωr(x)21/2xωr(x)(4.8)

which is slightly more concentrated in r than Eq. 4.2, and slightly less concentrated in r than Conjecture 5.10 We could alternatively move the r inside the weight expressions on 4.7; but the end result is equivalent to applying Cauchy-Schwarz on r(µrνr)1/2.

It may be that such an ideal generic lemma requires constraints on the p norms of the weights; however, for p2, a bound in terms of N 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 L3/2µr is replaced by L3/2µ3/2rN1/2; 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 L3/2µ3/2rN1/2 example, if one computes incidences before summation, then the first term bounding |Ur(E)| becomes Nr(xωr(x))3 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 m(g) of an intersection are not always strictly greater than than the intersection multiplicity; it may often be that mr()=0, or m()<N.

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: L[J,2J) is the set of all lines in L for which m()[J,2J).

Specifically, Eq. 4.6 becomes

|Ur(E)|||NK=2KgGK\G2KLxxgm(Lxx)||NK=2K||N2J=1gGK\G2KLxxgLxxL[J,2J)m(Lxx)||NK=2||N2J=1KJ·IG[K,2K),L[J,2J)

where I is the point-line incidence counting function. The following theorem is particularly useful:

Theorem. 12.1 of [Gut16]. Let S be a set of S points and L a set of L lines in R3. Suppose that there are at most B lines of L in any plane, and that BL1/2. Then the number of incidences is bounded as follows:

I(S,L)S1/2L3/4+B1/3L1/3S2/3+L+S

By this theorem, with the total number of lines LJ=L[J,2J), the total number of points SKN3/K2, and maximum number of lines in a plane, BN, we get

|Ur(E)|||NK=2||N2J=1KJS1/2KL3/4J+B1/3L1/3JS2/3K+LJ+SK||NK=2||N2J=1KJN3/2K1L[J,2J)3/4+N7/3K4/3L[J,2J)1/3+||NK=2||N2J=1KJL[J,2J)+N3/K2N3/2logN||N2J=1JL[J,2J)3/4+N7/3||N2J=1JL[J,2J)1/3+N||N2J=1JL[J,2J)+N5

By Chebyshev’s inequality, we find JL[J,2J)∈Lm(), which implies L[J,2J)N3logN/J; substituting this in yields:

|Ur(E)|N15/4(logN)7/4||N2J=1J1/4+N10/3(logN)1/3||N2J=1J2/3+N4(logN)2+N5N4N1/4(logN)7/4+N4N2/3(logN)1/3+N4(logN)2+N5

While the first three terms might be reducible with Chebyshev bounds on e.g. J4/3L[J,2J) and J3L[J,2J), the right hand side expressions ∈Lm()4/3 and ∈Lm()3 are difficult to control. The trailing N5 term is an artifact of the specific incidence expression used: the +S term of Theorem 12.1 of [Gut16] is maximal when all SK points are placed on unique lines in LJ, which is unlikely since there are, in total, more points than lines.

5. Line-based incidence formulations of the hinge problem

In this section, we present another approach to finding an upper bound for |U(E)| (which was defined in Section 4.1). In order to obtain an incidence problem for lines in R3, rather than lines in RP3, we partition U(E) into three (not necessarily disjoint) components, Uy, Uz, and U. First, we note that for each tuple (x,y,z,x,y,z), there are unique positively oriented rigid motions gy and gz for which gyx=gzx=x, gyy=y, and gzz=z. First, if gy is a translation, then the tuple is in Uy; if gz is a translation, we put it in Uz; and U=U\(UyUz). For sets Uz, we fall back to the weighted incidence argument used to express Uz as a sum over Qt, after which applying Eq. 4.5 gives |Uz|N4logN. As |Uz|=|Uy| by y-z exchange symmetry, |Uy|N4logN as well.

To control |U|, we establish an isomorphism between U and the set U of triplets of transformation-representing lines Lx,x, Ly,y, Lz,z in R3, defined as per Section 3, with the additional constraint Lx,x intersects both Ly,y and Lz,z. Note, just as y and z, or y and z, need not be distinct, neither do Ly,y and Lz,z. However, x=y and x=z, so Lx,x=Ly,y and Lx,x=Lz,z. That U maps injectively into U is follows from the formula for a line, Eq. 3.4; for the reverse direction, note that gy=Ly,yLx,x and gz=Lz,zLz,z are precisely the unique positively oriented rigid motions between (x,y) and (x,y), and (x,z) and (x,z). Since Lz,z and Ly,y are independent of each other, with L the set of all lines Lpq for p,qE, p=q,

|U|=Lxx∈LmL(Lxx)2(5.1)

where we define the weight mL(Lxx) as the total number of lines L\{Lxx} which intersect Lxx. As the uniform bound is not particularly useful, we partition L into disjoint sets L=r,L, so that LxxL=r,L iff r=mL(Lxx), and then define Lr,L:=N2s=rL=s,L. (A convenient upper bound for the weight mL(Lxx) is N2, since one can obtain mL(Lxx)N2 for a generic polygon as described in Example 2, because there are N2 distinct rotation angles corresponding to the maps which fix the polygon center.)

Then straightforward dyadic decomposition gives

|U|=N2k=1Lxx∈L=k,LmL(Lxx)2||N2K=1Lxx∈LK,L\L2K,LmL(Lxx)24||N2K=1K2|LK,L\L2K,L|

in which case an upper bound on the number of lines in L with line-richness between K and 2K would be required. As Example 10 shows, for the square grid it is possible that |LK,L\L2K,L|N2 for KNlogN; the difficulty is in establishing the upper bound on |LK,L\L2K,L| for lines with line-richness N. Of course, thanks to Proposition 2.8 of [GK15], there are at N lines per regulus, and hence via their Theorem 2.10, N3 total intersection points, so we can rule out the case that all N2 lines each intersect all N2 other lines.

One might expect that a double partitioning argument, as in Section 4.4, would be helpful; however, defining m(g):=|{LxyL:gLxy}| as the line-richness of point g, we get

|U|=N2k=1Lxx∈L=k,LgLxxm(g)2.

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 N intersections per line, for which gm(g)2(NlogN)2 but Ngm(g)2N3; the resulting upper bound produced by Cauchy-Schwarz is then at least N5.

6. Counting distances for sufficiently simple lattices

As noted by [CSS13], the method of finding a lower bound for |(E)| by computing an upper bound for |Q(E)| produces a lower bound which is off by a factor of logN in the square grid case, in large part because the equivalence class sizes nr are non-uniform.

An alternative approach to proving a tight lower bound on |(E)| is to prove the bound for a class of sets E, and then show, using symmetry or other constraints, that if |(E)| is below some threshold then EE. For example, one might hypothesize that if |(E)|N, then either E is almost a polygon (i.e., there is a polygon F so that |(E\F)(F\E)||E|), or E is a constant density subset of a finite lattice Ξ. (“constant density subset”, just like “almost”, is a heuristic; perhaps |Ξ|/|E|log|E|.)

Definition 6. A finite lattice Ξ is a set of points describable as π11Aπ12B where π1 and π2 are distinct projections. Then |Ξ|=|A||B|=N. It is convenient to let θ(0,π) be the smaller angle between π1 and π2.

As the points in Ξ can be identified with their projections, we can use the law of cosines to compute distances, with c=2cosθ.

(Ξ)=a2+b2+cab:aAA,bBB

The notation AA:={aa:a,aA}; since AA is symmetric around 0, (E) is unchanged if we replace c with c in the above expression. For lattices Ξ where A and B have high translational symmetry, that is, |A||AA|, and |B||BB|, it follows immediately that |(Ξ)||AA||BB||A||B|=N.

We now address the specific cases where A and B are both arithmetic progressions. We also define Uk:=Z[k,k].

Lemma 7. Let A=αUnA and B=βUnB; let Ξ be the finite lattice determined by the intersection of their inverse projections at cross angle θ. If (β)2/Q or (β)cosθ/Q, then

2maxpΞ|p(Ξ)||(Ξ)|N/4

Proof. Thanks to scale invariance, we can assume α=1. Then AA=U2nA and BB=βU2nB. For xAA, and y=βzBB, the distance corresponding to (x,z)U2nA×U2nB is f(x,z)=x2+β2y2+xy, for c=2cosθ. Furthermore, when points p,qΞ have coordinates (px,pz)=(nA,nB) and (qx,qz)=(nA,nB), then (Ξ)=p(Ξ)q(Ξ). There are three cases: Case 1. β2R\Q, Q.

Proof. Assume that there are x,z,x,z for which f(x,z)=f(x,z). If z=z, then from x2+β2z2+xz=x2+β2z2+xz, we derive x2x2+xzxz/z2z2=β2, so β2Q all terms in the left hand side are in Q. If z=z, then x2x2=(xx)(x+x)=z(xx) which has two solutions classes (x=x, x+x=z), neither of which provides more than one solution per value of f(x,z). Thus ||N/2.

Case 2. β2Q, R\Q.

Proof. Assume there are x,z,x,z where xz=xz for which f(x,z)=f(x,z). This would be a contradiction, since then

=x2x2+β2z2β2z2xzxz

which is in Q since Q is closed under field operations. On the other hand, if there are x,z,x,z where xz=xz while f(x,z)=f(x,z), then x2+β2z2=x2+β2z2. For fixed xz and x2+β2z2, there are at most four solutions in R, hence at most four solutions in N. As, by the earlier argument, there cannot be more than one value of xz per value of f(x,z) (lest Q), f(x,z)=f(x,z) has at most four solutions. Thus ||N/4.

Case 3. β2R\Q and R\Q.

Proof. If c=pqQ, then we scale x↦→x/β, z↦→z, and exchange the roles of x and z, falling back to case 1. Otherwise, the map (x,z)↦→x2+β2z2+xz is almost injective, since 1, β2, and form an independent basis over Z for the space of possible solutions; f(x,z)=f(x,z) would then require x2=x2, z2=z2, and (since /Q==0) xz=xz; there are precisely two solutions, (x,z)=(x,z) and (x,z)=(x,z). Thus ||N/2.

Combining all three cases gives ||N/4.

Lemma 8. Let A=αUnA and B=βUnB, and Ξ as before, with cross angle θ. Assume furthermore that (β)2Q and (β)cosθQ. Then |(Ξ)|Cα,βmin(na,nb)/logN for some constant Cα,β depending on α, β, and θ.

Proof. We use a similar setup as for the proof of Lemma 7. Since (β)2Q, and (β)cosθQ, we can scale Ξ be an integral factor without affecting , so that we can write f(x,z) as a binary integral quadratic form, f(x,y)=px2+qxy+ry2, where gcd(p,q,r)=1 (i.e, f is primitive). Then ||=|f(UnA,UnB)|. Since f computes a squared distance, it is positive definite, and its discriminant D=q24pr<0. Now, consider U2nA×U2nB as a rectangular lattice, one which the level sets of f are ellipses; with nA<nB, there is some maximal Kinnern2a for which for all k<Kinner, f1(k) is contained in Una×Unb; and some minimal Koutern2BD for so that f(U2nA×U2nB)Kouter. According to Paul Bernay’s thesis[Ber12], the total number of integers m which are representable by f is Bf(m)=C(D)mlogm+Om(logm)1/2+ for some >0. Thus

C(D)n2AlognABf(Kinner)||Bf(Kouter)C(D)Dn2BlognB

controls the size of the distance set. By [MO06], the hex lattice has minimal C(D)·D with D=3, i.e, the number of distances per covolume11, so if the lattice is of similar aspect ratio as the level set ellipses, then Kinnern2aD, and there is a universal constant for which ||min(na,nb)/logN.

Remark. It is easy to empirically investigate the distinct distance set sizes for lattices whose coordinates are arithmetic progressions. For quadratic binary forms f, there is an Θ(nanb) time-and-memory algorithm, which, in addition to computing |f(Una,Unb)|, incidentally produces f(Uk,Uj) for all kna,jnb. Consider the partial combined (x and y)-sums of the distance set sizes, so that |na,nb|=nax=0nby=0px,y. Then px,y=1dx,y, where to compute dx,y we first compute for all kGf (the set of f-representable integers) the lists k of values for which f(x,y)=k, and remove all (x,y) pairs which dominate some other pair (x,y) in the list (so that x<x and y<y). W initialize dx,y0, and then for each dominating element, increment the corresponding dx,y counter. The remaining elements (xk,i,yk,i)ski=1 are sorted ascending by xk,i, after which, for each i=2...sk, we increment dxk,i,yk,i1. This procedure ensures that for a rectangle containing the entire list k, the squared distance k 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), N. A specific case was proven by [CSS13], who showed that for f=x2+y2, if nA=N1/2, and nB=N1/2+, then =Θ(N), but their method does not easily generalize to general binary quadratic forms, and is incapable of handling e.g. nA=N1/2logN and nB=N1/2logN.

We define νΞ(k) to be the number of points (x,y) on Γ=U2nA×U2nB for which f(x,y)=k. Following [BG06], we define rf(k) to be the total number of (x,y)Z2 for which f(x,y)=k. Clearly νΞ(k)rf(k). By counting the pairs in U2nA×U2nB and the mean number of values of k that they contribute, we obtain

||=x,yΓ1νΞ(f(x,y))

Note that for k<Kinner, νΞ(f(x,y))=rf(f(x,y)), and the sum over kKinner evaluates to Kinner/logN, while when we have |x|<2na|y|<2nb, νΞ(f(x,y))=1 for almost all x,y, and then x,yΓ:f(x,y)Kinner1nanb=N. The tricky part in proving a lower bound on is showing that for k close to Kinner, the sets of points representing a value k 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 QiD (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.

7. Computations for the Grid

Example 9. For a constant fraction subset of points E (the central quarter), and a constant fraction subset of radii (those are less than a quarter the diameter of E), it is the case that ωs(x)=ωs(x) for all x,xE, since the circle of radius s around x intersects precisely the gridpoints which also lie in E (which, for a point x more than s away from the boundary, is all of them.) Then ωs(x) equals the representation counting function rfs2 for the quadratic form f=x2+y2. Thanks to [BG06], the various asymptotic moments of rf(x) are straightforward to compute, and so are lower bounds on the upper bounds for expressions based on ωs(x). From their Corollary 1, for any binary quadratic form f (such as x2+y2), and β1 ,

s2/4rfs2βN(logN)2β11

and hence for any xE, we have specifically

sωs(x)Nsωs(x)3N(logN)3sωs(x)2NlogNsωs(x)4N(logN)7

This makes it straightforward to compute that, for the square grid, via Eq. 4.2,

|Q(E)|=sxωs(x)2sxEωs(x)2N2sωs(x)2N3logN

where we use a single representative x for all the xE. Similarly, for the hinge problem, we obtain for Eq. 4.4,

|U(E)|=r,sxωr(x)ωs(x)2r,sxEωr(x)ωs(x)2=xExErsωr(x)ωs(x)ωr(x)ωs(x)=x,xEtωt(x)ωt(x)2N2rωr(x)22N4(logN)2

Example 10. The appendix of [GK15] shows that for the square grid, the number of k-line-intersection-rich points in the 3d incidence problem is at least |Pk(L)|N3/k2. We re-purpose their proof to show that, for the square grid, a constant fraction of lines have point-richness N and line-richness NlogN; i.e, |LN(P)|N2, and |LNlogN(L)|N2.

Let E=Z2N1/2,2N1/2×Z2N1/2,2N1/2 be a grid of points centered on the origin. Then |E|N. We let L={Lpq:p,qE} be the set of lines in R3 corresponding to non-translational positively oriented rigid motions mapping e.g. p to q, with parameterization according to Eq. 3.4. By Lemma A.1 of [GK15], there is a subset L0L for which |L0||L|, where the lines L0 are those which pass through the points (a,b,0) and (c,d,1) in R3, where a,b,c,dZN1/2,N1/2. For every integer 1qN1/2/2, and integer 0pq, the plane at height p/q intersects all N2 of the lines in L0. Furthermore, since the lines in L0 pass through integer lattices at heights z=0 and z=1, at height p/q (with p/q in lowest terms), the lines in L0 pass through a uniform lattice with spacing 1/q and Nq2 points in total.

We define L to be the set of lines in L for which |ac|,|bd|<N1/2; we have|L|N2. Then by translation invariance12 for motions shorter than N1/2, all lines in L0 pass through the same number of lines in L at height p/q, namely, N2/Nq2N/q2 of them. As any pair of lines can intersect at most twice, the total number of intersections 13 between a line in L0 and the lines of L, is

mL()=qN1/2p/qNq2=NN1/2q=1φ(q)q2NlogN

where φ(q) is Euler’s totient function and the identity N1/2q=1φ(q)q2logN is easily derived from nq=1φ(q)/q=6π2n. (See for instance [PS92], section 3.)

As mL()NlogN for N2 different lines L0, it follows |LNlogN(L)|N2. Furthermore, since each line L0 intersects at least one other line in L for qN1/2p/q1=N1/2q=1φ(q)N different heights, |LN(P)|N2.

8. Acknowledgements

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.

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.

[CSS13]

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

[dBru81]

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.

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

[Gut16]

Larry Guth. Polynomial Methods in Combinatorics. American Mathematical Society, 2016. isbn: 978-1-4704-2890-7.

[IP18]

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

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

1When we say xy, we mean that there is a universal constant C>0 for which xCy. Furthermore, we define so that xy iff xy and yx.

2According to [CSS13], extremely elongated rectangular grids instead yield N 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 G; then it is valid to treat g as both a point in R3 and a non-translational positively oriented rigid motion of R2.

6Evaluating gives ˆz×(p+q)/2+ˆz=((qypy)/2,(pxqx)/2,1).

7Specifically, any linear transformation of a hyperbolic paraboloid/parabolic hyperboloid{xy=z}, or hyperboloid of one sheet x2+y2z2=1; reguli can be defined using three skew lines.

8For example, if f(N)g(N)+αf(N) then f(N)g(N) if α<1; but if α>1, the inequality is useless.

9The exact µ1/2rν1/2r tradeoff may differ, but the term almost certainly depends on νr, 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 C(D) is covered in more detail by [BMO11].

12To be precise, this only ensures that the number of lines passing through (a+a/q,b+b/q) at height p/q is the same as the number passing through (c+c/q,d+d/q). Because shifting an endpoint of the line segment from (r,s,0) to (u,v,1) by one translates the intersection point of the line by p/q (or 1p/q), and gcd(p,q)=1 (so that we can attain any fractional x or y coordinate), we can transform the bundle of all lines passing through e.g. (a+a/q,b+b/q) to pass through (c+c/q,d+d/q).

13+N, as we overcounted intersections between as a member of L0 and as a member of L.


Return to main page | as PDF