The OpenAI diagram is based on choosing c² = 65, which can be satisfied with 1² + 8² = 65 or 4² + 7² = 65. This means that if the grid spacing is 1/√65, each point will be one unit away from 16 other points: (1.8), (4.7), (7.4), (8.1), (-1.8), (-4.7), and so on. successively. Larger values of c², if chosen carefully, allow for more whole number diagonals and thus more unit-distance pairs.
However, if c² is too large compared to the number of points in the network, then many of the possible neighbors a unit away will be outside the network.
In short, we want to choose a c² that is big enough but not too big. Using ideas from number theory, including Jacobi’s two square theoremErdős was able to show that an optimally sized circle will allow the number of distance-unit pairs to grow faster than the number of points, but just barely.
The question was “can you do better?” To find an upper limit, Erdős used an argument from a quite different area of mathematics called graph theory to show that only a certain number of unit distances could be had. But your upper limit grows much, much faster than the best lower limit you could build.
Erdős’s conjecture was that the actual optimum was much closer to the lower limit than to the upper limit. He predicted, but could not prove, that the maximum number of distance-unit pairs grows slightly faster than the number of points.
To be more precise, Erdős conjectured that the number of unit distances would be n^(1+o(1)). In other words, for a sufficiently large n, the maximum number of unit distances would be less than n^(1+𝜖) for any 𝜖 > 0. That might end up growing a little faster than your lower bound construction, which was n^(1 + C/(log log n)) for some constant C, but within the same general ballpark.
