Erdős Unit Distance Problem

Author

Eric W. Weisstein
May 22, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/ErdosUnitDistanceProblem.nb.

For more information, see Eric's MathWorld entry https://mathworld.wolfram.com/ErdosUnitDistanceProblem.html.

©2026 Wolfram Research, Inc. except for portions noted otherwise

Bounds

Spencer-Szemerédi-Trotter (1984)

For n vertices, what is the maximum number of unit lengths?  Upper bound: n^(4/3)

TextGrid[
Select[
{#,#2,#3,N@((#2)^(4/3))}&@@@GraphData["UnitDistance",{"#","V","M"}],
#[[3]]>=#[[4]]&
],
Dividers->All
]

OpenAI

Cf. Shenghui Yang,

https://community.wolfram.com/groups/-/m/t/3719376

ω=-0.5+Sqrt[3]/2.*I;
r={-2,-1,0,1,2};
pt=Table[a+b*I+c*ω+d*I*ω,{a,r},{b,r},{c,r},{d,r}]//Flatten;
conn=Select[Subsets[pt,{2}],Abs[Abs[#[[1]]-#[[2]]]-1]<=0.00001&];
ComplexListPlot[Flatten[conn]//Union,PlotStyle->{StandardOrange},Prolog->{Opacity[0.4],StandardBlue,Line[ReIm/@conn]},Axes->False]

omega=-1/2+Sqrt[3] I/2;
toPoint[{a_,b_,c_,d_}]:=a+b I+c omega+d I omega;

steps={{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1},{1,0,1,0},{0,1,0,1}};

unitEdges[k_Integer]:=Module[{coords,coordSet},coords=Tuples[Range[-k,k],4];
coordSet=AssociationThread[coords->True];
Join@@Table[With[{q=p+s},If[KeyExistsQ[coordSet,q],{toPoint[p],toPoint[q]},Nothing]],{p,coords},{s,steps}]];

panel[k_Integer,range_:3.2]:=Module[{edges=unitEdges[k]},ComplexListPlot[Union[Flatten[edges]],PlotRange->{{-range,range},{-range,range}},PlotStyle->Directive[PointSize[0.005],StandardOrange],Prolog->{Opacity[0.6],StandardBlue,Line[ReIm/@edges]},Axes->False,Frame->False,ImageSize->280,PlotLabel->Row[{Style["k",Italic],"==",k}," "]]];

GraphicsRow[panel/@{1,2,3},Dividers->All,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,14,FontFamily->"Times"]}]