How many squares can be formed by using n points on a 3 dimensional space?


* Like using 4 points, there is 1 square be formed
* Using 5 points, still 1 square
* Using 6 points, 3 squares can be formed



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](https://en.wikipedia.org/wiki/Szemer%C3%A9di%E2%80%93Trotter_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](https://arxiv.org/pdf/1208.0053.pdf) 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.


