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
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHow many squares can be formed by using n points on a 3 dimensional space?
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.