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 x and x to denote being bounded above and bounded below by a function of x; x may be omitted for laziness or when the constant is independent of x.

Let E be a set of points with size N.

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

T is the set of pairs of distances relative to a given point, a.k.a. hinges. Note that |Tx||x|2.

Conjecture 1. Distinct distance problem: ||N/logN. The pinned distinct distance problem claims maxx(|x|)N/logN.

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

Conjecture 3. Pinned hinge problem: |T|N2/logN. (Implied by pinned distinct distance, since |Tx||x|2; the current best bound is N2/(logN)2 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 x at the center. There are N1 radial points, and very close to (N1)/2 distinct distances. Thus |x|=1, ||N.

Example 5. Crossing circles. Given two points x,y, separated by distance N, let E be the set of all points whose distances to x and to y are in 0,1,...N. Then |x|=|y|=N.

Example 6. Multiple circles: duplicate 4 multiple (k) times; then there are multiple points for which a single distance is present N/k 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 N1/2 that are small convolutions of a simple arithmetic sequence. Calculations show that, for roughly circular domains and large N (4×105), ||1.0N, 0.06N|x|0.6N.

Example 8. Square grid. E=(x,y):x,yN,0xN1/2. Then ||N/logN, from the density of sums of squares of integers.[Tho73].

Also, following the appendix, if we consider the set of lines L={Lpq} for p,qE where Lpq denotes the line expressing of rigid transformations (except for pure translation) mapping p to q, then with Lk the subset of lines which intersect k other lines, we have for kNlogN. |Lk|N2. [TODO: copy proof in notes; mention [PS92] who get the same φ(k)/k2.] [TODO: also show that the hinge problem can not be resolved any better by this method]

Remark 9. Use D=b24ac for aX2+bXY+cY2. Note [MO06] shows that the hex lattice gives minimal C(D)·D at D=3, i.e., distances per covolume (weighted by D1/n). See also [BMO11]: in general, C(D) can get arbitrarily close to 0 with larger D, and is also unbounded above for both positive and negative D, although |D| grows much faster than C(D).

Remark 10. As expected of Cauchy-Schwarz (optimal when ni uniform), via [CSS13], Elekes-Sharir isn’t optimal. Furthermore, given a right angle integer lattice with ratios nα, n1α, for α=1/2, get Θ(n).

Remark 11. There is a Θ(nanb) algorithm to compute all dominated rectangle distance set sizes for e.g. f(x,y)=x2+y2. (Consider the partial combined (x and y)-sums of the distance set sizes, so that |na,nb|=nax=1nby=1px,y. Take px,y=1dx,y, where to calculate dx,y, we first compute, for all kGf, the lists k of values (xk,i,yk,i)ski=1 for which f(x,y)=k, sorted ascending. Then we add one for dxk,i,yk,i1 for all i=2...sk. See Figure1.)


image
Figure 1: Plots of dx,y for f=x2+y2 on the left, and f=x2+2y2 on the right. In the symmetric case, the main diagonal is very concentrated; i.e. d1000,1000=617.

Heuristically, since most rf(k)=2, px,y1 for large values, and the diagonal component is pz,z1z/logz (?); and if nanb, the total sum resolves to n2an2an2a/lognan2a/logna; if nab, then the diagonal component is not included beyond a point, leaving nbnan2an2a/lognananbna+na/logna. Which still yields incorrect results along na/nb=const, but at least has the correct behavior along na/nb→∈{0,1,∞}.

Under the hypothesis of radially uniformly distributed representations for rx2+y2, we find ||=x,y1ν(f(x,y)), and among the values of k which are present, ν(k)max1,rf(k)θkπ/2, where θkarcsinmin1,min(na,nb)k1/2; so that

||0xna,0ynbmin1,π/2rf(k)arcsinmin1,min(na,nb)k1/2

Note that for nanb, this is almost x,y:f(x,y)Krf(k)1(nanb)/log(nanb), and for nanb, rf(k) grows much more slowly than 1/k1/2 shrinks, so that the right part of the min(...) equals one for sufficiently elongated rectangular grids, leading to ||nanb. A result giving the distribution of rf(k) over some interval (k,2k) might help produce a closed form.

Alternatively, under the uniform hypothesis: let γf(k), approximated for x2+y2 as arcsinmin1,min[na,nb]k1/2/(π/2), be the length of the intersection of the level set of f with the (0,0)(x,y)(na,nb) rectangle. Then (sketchily)

||x,yna,nb,k=f(x,y)min1,1rf(k)γf(k)
(1)

Now, within a given dyadic interval (x,2x), using [BG06], k(x,2x)rf(x)x, k(x,2x)rf(x)2xlogx, etc. Since γf(k) changes slowly, we set γ=γf(2x)γf(k). Let b(x) be the fraction of the x/logx elements k(x,2x) for which 1>1/rf(k)γ, i.e., rf(k)γ1; clearly then xk(x,2x)rf(x)b(x)x/logx, so that b(x)γlogx; the other estimate gives, b(x)γ2(logx)3/2, although with a different constant. Either way, the sum 1 can be decomposed into ring sections Ri with f(x,y)2i,2i+1; on each ring, given suitable uniformity, x,yRimin1,1/rf(k)γf(k)x,yRi(1b(x)), since there is a 1b(x) chance that 1/rf(x)γf(x) is greater than one. On very elongated rectangles, each ring contains 2i/2na elements, and has γ2i/2, so that b(x)2i/2log2i/2na1, in which case the contribution to || of the ring section is approx |Ri|. Reasonably even rectangles have γ1, and those rings contribute |Ri|/logRi.

3 Distinct distance problem for lattices with uniform spacing

Consider E a set of points. Let A=π1E be a projection onto one direction, and B=π2E be a projection in some other direction. Assume |A||B|=E, so that E is the grid produced by the π11Aπ12B. Let θ be the larger angle between the two directions, and let c=2cosθ[0,2): then each element has coordinates (x,y), and

(x,y)=(xx)2+(xy)2+c(xx)(yy):xA,yB

and =(x,y)(x,y), is

=x2+y2+cxy:xAA,yBB

Theorem 12. If |AA||A|NA, and |BB||B|NB, |E|=N=NANB then ||N, which implies |x|N and |T|N.

Proof. |||AA||BB| since each value in is defined by a pair (x,y)(AA)×(BB). __

Definition 13. Let Uk={k,k+1...1,0,1...k1,k}.

Theorem 14. Let A=αUnA, and B=βUnB; let E be the lattice determined by their inverse projections at cross angle θ. (|E|=N=nAnB.) Then sup|x|N/logN, which implies ||N/logN and |T|N/logN.

Proof. Without loss of generality (by scaling everything), α=1. We choose θ to be the smaller angle between the projection directions, so that that 2cosθ=c(2,0]. Note also that AA=U2na, and BB=βU2nb; Then with y=βz, and writing f(x,z)=x2+β2z2+xz., ={f(x,z):xU2na,zU2nb}. Note that max|x|||/4, with (x,y)=(0,0) since |f(Una×Unb)|(N/4)/log(N/4). Case 1. β2Q and Q.

Proof. Let β2=pq, =rs be in least terms. Then evaluates to

x2+pqz2+rsxz:x,zUN,

which on rescaling gives qs||=qsx2+psz2+rqxz:···. According to Paul Bernays’s 1912 thesis[Ber12], the total number of integers N which are representable by in terms of the expression defining this last set is Bf(N)C(D)NlogN where C(D) is a constant function of the discriminant D, if D<0 (as D=b24ac) and the quadratic form is primitive and positive definite. (Note that f can not be factored over R, since D<0.) Dividing by the quadratic form by n=gcd(qs,ps,rq) ensures that it is primitive, at only constant factor change in ||, and the form is positive definite as a linear transformation of positive definite x2+y2. Consider Una×Unbas a rectangular lattice, on 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 Koutern2b so that f(Una×Unb)Kouter. Thus

n2alognaBf(Kinner)||Bf(Kouter)n2blognb

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

The paper [CSS13] finds a lower bound for x 2 + y 2 in the rectangular case when n b /n a (log N ) 2+ , but resolves to counting duplicates (and hence probably can’t bypass N/ log N), uses the weak bound k 1 k 2 , 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. β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 3. β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 4. β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 2. 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. __

__

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

Problem 15. General plan: first, solve the equivalent to Thm 14 for A and B generalized arithmetic progressions; second, use approaches like Green-Ruzsa [GR] / Cwalina-Schoen [CS13] to show that A is “close” enough to an arithmetic progression that the distinct distances are changed by at most a constant (which should be a function of |AA|/|A| and |BB|/|B|. 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 EE for E some offset grid). yUnb, xαUna,1+βUna,2, and c=2cosθ, so that ||=|{f(x,y)}|, where f(x,y)=(α1x1+α2x2)2+y2+cαx1y+2x2y. It is possible that all of 1, α21, α1α2, α22, 1, and 2 are in Q, and also possible that they (and their ratios) are all linearly independent. There are also additional constraints: if α21Q, then α1α2Q implies α22Q but not the other way around (For instance, αi=pi for pi the ith prime, and c=1.) If all values are in Q, one ranges from a Cantor-like set scenario na,i=1,αi=5i to full density (αiUna,i=Una.).

We pick a specific case: α1=π, α2=π2, c=1. Then f(x,y)=π2x21+π4x22+2π3x1x2+πx1y+π2x2y+y2. Assume we have multiple (x1,x2,y) with the same f(x,y)=z0+πz1+π2z2+2π3z3+π4z4; then matching terms, we find z2=x21+x2y=x21+x2y, z4=x22=x22, z3=x1x2=x1x2, z1=x1y=x1y, and z0=y2=y2, 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 y0 and y0; then, y2=y2 implies y=y, so if y=0, x1y=x1y implies x1=x1, so if x1=0 then x1x2=x1x2 implies x2=x2. If y=0, then we must solve x21=x21=z2, x22=x22=z4, and x1x2=x1x2=z3, and to counter symmetry we assume x10; continuing, we find either y=x1=x2=0 (trivial case, can be ignored) y=x2=0 (and we have two solutions), y=x1=0 (two solutions), only y=0 (two solutions), etc. Ultimately |||E|/2.

Alternatively, consider α1=2, α2=3, c=1; this gives f(x,y)=2x21+3x22+26x1x2+2x1y+3x2y+y2, which implies for values of f(x,y)=z0+2z2+3z3+26z6 that z6=x1x2, z2=x1y, z3=x2y, and 2x21+3x22+y2=z0; four quadratic equations, with three unknowns. If x1,x2,y=0, we have ±(z6z2z3)1/2/z6=y and similarly for x and z, yielding two symmetrical solutions. With y=0, we have z6=x1x2, z0=2x21+3x22 which as the intersection of a hyperbola and ellipse has 4 solutions; similarly for cases x2=0 and x1=0.

The Penrose tiling specifically produces x=x1+ϕx2, na,1N1/2, na,2=1, y=y1+ϕy2,nb,1N1/2,nb,2=1, and c=ϕ=2cos2π5=1251=0.618.... Then we have

f(x,y)=x21+ϕ2x22+2ϕx1x2+y21+ϕ2y22+2ϕy1y2+ϕx1y1+ϕ2x1y2+ϕ2x2y1+ϕ3x2y2

. Of course, ϕ2=1ϕ, and ϕ3=ϕϕ2=ϕ(1ϕ)=2ϕ1, so this reduces to

f(x,y)=1x21+x22+y21+y22+x1y2+x2y1x2y2+ϕx22+2x1x2y22+2y1y2+x1y1+2x2y2

Then for a given value f(x,y)=z0+ϕz1, we apply casework nine times on y2,y1{1,0,1}, each time resulting in z0=x21+y21+x1C+y1C+C, z1=x1C+y1C+x1y1+C, a pair of equations corresponding to an ellipse and to a parabola, whose intersection has 4 solutions in R2. Correspondingly, the grid associated with the Penrose tiling produces |||E|/36.

Just as irrationality can prevent multiply-counted pairs, so too can scale discrepancies. Let na,i=1, nbi=1 for i=1...m. Furthermore, αi=βi=3i; then |A|=|B|=U3m, and N=6m. This is the square grid case. Alternatively, use αi=4i+1, βi=4i1, c=0, in which case (xiαi)>1, (yiβi)<1, so that any r=f(x,y) can be uniquely split into large (>1) and small (<1) components depending on xand y respectively; this implies ||=|E|. A more difficult case is general c, αi=Bi, βi=Bi, for B=(2m+2). Then f(x,y)=Bixi2+Biyi2+cBiyiBixi. If c/Q, then we have f=zs+czx; at c=0, f=zs=Bixi2+Biyi2. This evaluates to 2mi=2Bii1k=1xkxik+i1k=1ykyik. There are two main symmetries, x/y exchange and negation symmetry; so WLOG y>max(x,0) as base 3 numbers. Evaluating zs/B2modB yields x21+y21{0,1,2}, which lets us determine how many of x1 and y1 are nonzero; the symmetry assumption resolves to one unknown case (x1,y1)=(1,±1). The next digit yields 2x1x2+2y1y2{4,2,0,2,4}, and after that, 2x1x3+x22+2y1y3+y22{2,1,0,1,2,3,4,5,6}, and taking mod2 lets us know if only one of x2 or y2 is nonzero; more extremal values provide more information. The space of minB2m,(2m+1)m1i=1(2i+1)2 possible digit combinations is much larger than the 6m possible x/y pairs, so one might conjecture that x, y are uniquely identifiable from their base B multiplication (convolution).

Conjecture 17. If any of αi,βi,c are /Q, then |N|/C for some constant C, possibly a function of dimai,bi,c.

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 ||N (e.g, transcendental grid, circle.) To get below N, 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 N?

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 k3, and L a set of lines with total weight L, average weight µ in R3 with weight B in any plane. The number of points whose total intersection weight with L is between k and 2k is S. Then SCL3/2µ1/2k2+LBµk3+Lk1. (This is chosen for homogeneity in µ, with fixed L=µN2, BµN, kµ|#lines|. 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 ER2, rR, and xE, define ωr(x)=|{yE:|xy|=r}|.

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

Theorem 20. We assume Conjecture 18. Then as defined above, E is a set of N points, and T(E) is the set of hinge classes of E. Then |T|N2/(logN)2.

Proof. Clearly, rω(x)=N1. Then by Cauchy-Schwarz,

N6r,sxEωr(x)ωs(x)2|T(E)|(E)

where

(E):=r,sxEωr(x)ωs(x)2
(2)

Then rearranging gives T(E)N6/(E). We claim (E)N4(logN)2. To prove this, we expand ωs and note that the conditions s=|xy| and s=|xy|, summed over all s, resolve to |xy|=|xy|:

(E)=rx,x,y,yE|xy|=|xy|ωr(x)ωr(x)

Next, let G be the group of positively oriented rigid motions of the plane, for given gG, let gE={g(x):xE}. We establish a bijection between the set J of tuples where (x,x,y,y)E4 with the additional constraint that |xy|=|xy|>0, and the set J of tuples (x,y,g)E2×G where x,yg1EE. By Prop 2.3 of [GK15], since |xy|=|xy|, there is a unique gG for which g(x)=x and g(y)=y; thus (x,x,y,y)J is mapped to (x,y,g)J. (Since x=g(x)E, g1(g(x))g1E, so x,yg1EE.) On the other hand, given (x,y,g)J, there is a unique (x,x,y,y)=(x,g(x),y,g(y)), which (as g is a rigid motion) has the property that |xy|=|g(x)g(y)|=|xy|; and since x,yg1E, it follows x=gxE and y=gyE, so that (x,x,y,y)J.

Reindexing and dyadically partitioning with G=, G2j giving sets of simple (intersection) multiplicity k, we find (defining weighted multiplicity m(g))

(E)=rgGx,yg1EEωr(x)ωr(g(x))(3)=rgGg1EEmr(g)=rNk=2kgG=kmr(g)rlogNj=02j+1gG2j\G2j+1mr(g)rlogNj=02jgG2jmr(g)

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

gGtx,yg1EEωr(x)ωr(g(x))=gGtg1EExg1EEωr(x)ωr(g(x))NgGtxg1EEωr(x)ωr(g(x))=NxExEωr(x)ωr(x)

where the last inequality is a reindexing: each pair (g,x)Gt×E corresponds to a unique (x,x)E2 (by x=g(x)), and vice versa (with g the translation by xx). Summing over all r, we find NrxEωr(x)2 which by 2 is N4logN. 2

For the rotational part, we embed the curves of rigid motions mapping point p onto q as lines LpqR3. There are two obvious ways of configuring the weights: with the sum over r 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 mr(Lxx):=ωr(x)ωr(x), so that the total weight/multiplicity of a point gR3 is

gm()=xg1EEmLx,g(x)=xg1EEωr(x)ωr(g(x))=mr(g).

Adding over all x,x gives the total line weight Lr=x,xωr(x)ωr(x)=(xωr(x))2. 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 Lxy and Lxy are in the same plane, then x=x and y=y. A straightforward upper bound – not involving much more geometric information – gives

Br=supσPerm[E]\{id}xEωr(x)ωr(σ(x))xEωr(x)2

where this last upper bound is by the rearrangement inequality. The exact upper bound for mr(g) does not matter in the upcoming argument; we take mr(g)NC2for some constant C2. The mean line weight is µr=Lr/N2.

Note that it is possible for mr(g)=0 for an intersection, just as Lxx=0 is possible. Consequently, there need not be a direct relationship between k (simple intersection count), and κ (weighed intersection count). This makes everything trickier.
Case 2. Weights summed over all distances. Observe then that m(Lxx):=rmr(Lxx)=rωr(x)ωr(x), in which case the point multiplicity is defined as m(g):=rmr(g). Adding over all x,x yields L=rx,xωr(x)ωr(x)=|Q(E)|N3logN, while the simple bound on B is rxEωr(x)2, for which the circular result is N2logN, presumably. The lowest possible weight of a line is 1 – consider the generic case, in which only for r=|xx| is there a contribution, and largest possible NC2, i.e. N3/2 which ωr(x)N1/2 and ωr(x)N1/2 over N1/2 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 Lpq=p+q2,0+tpq2,1:tR, where we label coordinates (x,y,t). Horizontal (t=const.) planes contain no lines, as lines always have nonzero z-slope. All other planes P intersect the t=0 plane on a line , and relative to the horizontal plane have maximum slope 1/|s|, where the case s=0 corresponds to vertical planes. Then a plane P contains precisely the transformation lines Lxx between x,xE for which x=M,sx, in which M,s denotes the transformation given by reflecting over the line and then translating along the direction of by 2s; flipping the direction of is equivalent to negating s. (This is straightforward to show geometrically: restricting to the t=0 plane, plane P is the line , and the line Lpq is the point (p+q)/2, which must be on the line. Without loss of generality, we fix coordinates so that is the y-axis, p=(a,b+γ), q=(a,b+γ); then the plane is defined by the equation st+x=0, and Lpq is t↦→(tb,ta+γ,t); so Lpq lies in P iff s(t)+(tb)=0 iff b=s.)

Consequently, consider any set E invariant under a glide-reflection symmetry M,s, i.e., so that M,sE=E. Since glide-reflection is an isometry, distances are preserved, and hence ωr(M,sx)=ωr(x). Then Br=12xEωr(x)2, and B=12xErωr(x)2; any general upper bound on B or Br would need to agree with this specific case.

Even assuming κk, via Conj. 18, the first case we arrive at an expression like (E)N1logNr(xωr(x))4+misc. which is significantly sharper than our goal (since N2a22N1a4), and evaluates, for the regular square or hex grid, to N4(logN)8. In the second case, we lose a factor of N and a few logN as the relationship between κ and k is still unclear; if we assume the counterfactual κNk, 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 N4(logN)2 bound we would expect in general; the same approach on the normal distinct distance problem gives N3 (using ω=1), 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