How many squares can be formed by using n points?

In the plane $n$ points can determine at most $O(n^2)$ squares. This is because any two distinct points can determine up to three squares.

In $R^3$ this argument no longer holds, since two points can form the corners of arbitrarily many squares. As Gerhard points out, $O(n^3)$ is an upper bound (in any dimension) given that three points determine at most one square.

One can do a bit better than this. Using the Szemerédi–Trotter theorem one can show that a set of $n$ points in $R^3$ determines at most $O(n^{7/3})$ right triangles. It follows that $n$ points determine at most $O(n^{7/3})$ squares (since a square will contain a right triangle). On the other hand, it is certainly easy to see that there exists point sets with at least $\Omega(n^2)$ squares. The bound of $O(n^{7/3})$ is known to be sharp for the less constrained problem of counting right triangles.

Update: A result of Sharir, Shefer and Zahl shows that the number of mutually similar triangles in a point set in $R^3$ is at most $O(n^{\frac{15}{7}})$, where $15/7 = 2.142\ldots$, which implies the same bound for the number of squares.

Closing the gap for squares, however, seems an interesting and non-trivial problem.


In k dimensions, take a regular unit k simplex on k points, and copy it an orthogonal distance of 1. This results in k choose 2 unit squares on 2k points. I invite others to count square arrangements in a hypercube.

Combinatorially, there can be no more squares than three sets of an n set. Indeed, since three points of a square determine the fourth, there are at most a fourth as many squares possible as three sets. I imagine Erdos may have an upper bound for planar arrangements, which should be on the order of n^2, since any two points in the plane determine one of three squares containing those two points.

Gerhard "Dots And Spots And Knots..." Paseman, 2020.07.05.