Equal distances in a grid: the unit distance count

What this calculator does

Take a square grid of points and pick a distance. How many pairs of points are exactly that far apart? For a side-by-side distance of 1 in a 20 by 20 grid the answer is 760, which is a shade under two per point. Pick the distance 5 instead and the answer more than doubles to 1,688, from the same 400 points.

That jump is the whole subject in miniature. A distance occurs often when it can be written as a sum of two squares in many ways, because each way gives a new direction in which the pair can sit. Erdős asked in 1946 how large this count can be made, and that question stayed open until 2026.

The formula

Formulapairs = ½ × Σ (k − |dx|)(k − |dy|) over every integer vector with dx² + dy² = m, counted inside a k × k grid

Two lattice points are at squared distance m when their difference vector (dx, dy) satisfies dx² + dy² = m. For each such vector, the number of places it fits inside a k by k grid is (k − |dx|)(k − |dy|). Adding that over every signed vector counts each pair twice, so the total is halved. A distance whose square has no representation as a sum of two squares, such as 3, gives zero pairs however large the grid.

Term	Meaning
k	The side of the grid in points, so the grid holds k² points.
m	The squared distance. Using the square keeps it a whole number and makes the sum-of-two-squares structure visible.
Direction vectors	The signed integer vectors of that length. More vectors means more pairs.
n^(4/3)	The Szemerédi-Trotter ceiling: no set of n points in the plane can have more than a constant times n^(4/3) pairs at any one distance.

The inputs explained

Field	What to enter
Grid side (points)	Points along one side. The grid holds k² points in total, so 20 means 400 points.
Squared distance	The squared distance to count. Enter 1 for the unit distance, 2 for a diagonal, 25 for a distance of 5. Values with no representation as a sum of two squares return zero.

When to use it

Seeing why some distances are popular

Compare m = 1, m = 25 and m = 65 in the same grid. The number of direction vectors goes 4, 12, 16, and the pair count rises with it. 65 is 1 + 64 and also 16 + 49, which is what gives it so many directions.

Watching the count grow with the grid

Hold the distance at 1 and raise the side. The count grows like 2k², which is linear in the number of points. That is the honest reason the plain grid is a weak construction: doubling the points only doubles the pairs.

Comparing against the ceiling

The n^(4/3) figure is the proven upper limit on pairs at a single distance. The grid sits a long way below it, and the gap between what constructions achieve and what the bound allows is where the open problem lived.

Worked examples

Every figure in the tables below is produced by this page’s own calculator at build time, so the numbers and the tool always agree. Select any row to load that scenario.

Which distances occur most often in a grid?

The same points throughout. Only the distance being counted changes.

A 20 by 20 grid, 400 points

Squared distance	Pairs at that distance	Direction vectors of that length	The distance itself
1	760	4	1
2	722	4	1.41421356
3	0	0	1.73205081
4	720	4	2
5	1,368	8	2.23606798
25	1,688	12	5
65	1,744	16	8.06225775

A squared distance of 3 gives nothing at all, because 3 is not a sum of two squares. 1 and 2 each have four direction vectors and give 760 and 722 pairs. 25 has twelve vectors and 1,688 pairs, and 65 has sixteen and 1,744. The pattern is not about the size of the distance, it is about how many ways the square splits into two squares.

How does the count grow with the grid?

The grid doubles each row.

Unit distance, squared distance of 1

Grid side	Points in the grid	Pairs at that distance	Pairs per point
5×5	25	40	3.20
10×10	100	180	3.60
20×20	400	760	3.80
40×40	1,600	3,120	3.90
80×80	6,400	12,640	3.95
160×160	25,600	50,880	3.98

The pair count is exactly 2k(k − 1), so it grows in proportion to the number of points and the pairs-per-point figure creeps towards 4 without ever reaching it. This is a linear construction, and the interesting constructions beat it by a polynomial factor, which is exactly what the 2026 counterexample delivered.

Questions

What is the unit distance problem?

Erdős asked in 1946 how many pairs of points at distance exactly 1 can occur among n points in the plane. He conjectured the answer was n^(1+o(1)), barely more than linear. The best proven upper bound has been O(n^(4/3)) since 1984.

Why does squaring the distance help?

Because distances between lattice points are usually irrational while their squares are always whole numbers. Working with the square turns the question into one about representing an integer as a sum of two squares, which is classical number theory.

Why does a squared distance of 3 give zero?

A whole number is a sum of two squares only if every prime congruent to 3 modulo 4 appears in it an even number of times. 3 appears once, so no lattice pair is at that distance, in any grid of any size.

Is the grid the best construction?

No, and that turned out to be the point. The plain grid gives only about 2n pairs. Scaled and cleverly chosen point sets do much better, and in May 2026 a construction was found that beats n^(1+o(1)) outright.

Does this count pairs or ordered pairs?

Unordered pairs. Each pair of distinct points is counted once, which is the convention the problem uses.

For the number theory underneath, see prime check and factorisation, which decides whether a squared distance can occur at all, and the Pythagorean triple generator, which produces exactly the integer vectors counted here. For the plain calculation there is distance, midpoint and slope. The story of how the conjecture fell is in the piece on the unit distance conjecture.

Equal distances in a grid calculator