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
$\begingroup$
$\endgroup$
14
-
1$\begingroup$ Let me know if I get this right. Given a set $X$ of points in the plane we denote by $Sq(X)$ the number of squares whose vertices are in $X$. Define $$ Sq_n=\max\big\{S(X);\;\;|X|=n\big\}.$$ Find $Sq_n$. For example $Sq_4=Sq_5=1$, $Sq_6=2$. Is this what you are asking? $\endgroup$– Liviu NicolaescuCommented Jul 5, 2020 at 18:51
-
7$\begingroup$ OEIS A051602 $\endgroup$– RobPrattCommented Jul 5, 2020 at 18:58
-
5$\begingroup$ I see you changed the answer for $6$ points: originally it was $2$ squares, now it's $3$ squares. Was this originally intended as a question about points in a $2$-dimensional plane, and now it's about points in $3$-dimensional space? Are we trying to hit a moving target? $\endgroup$– bofCommented Jul 5, 2020 at 22:08
-
6$\begingroup$ @GerhardPaseman, "let's leave this vague question open because there are lots of interesting questions similar to it" seems like a bad precedent to set that will discourage askers from posing precise questions. $\endgroup$– LSpiceCommented Jul 5, 2020 at 22:46
-
3$\begingroup$ In some cases I agree @Lspice. In this case I don't, because it reminds readers that there is more mathematics just lying below the surface. The original wording admitted a very specific interpretation which would occur to many. It also admitted other interpretations of interest, which would apply to the naive one (squares on the real two dimensional plane). Gerhard "There Are Other Bad Precedents" Paseman, 2020.07.05. $\endgroup$– Gerhard PasemanCommented Jul 5, 2020 at 22:52
|
Show 9 more comments
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
3$\begingroup$ " it is certainly easy to see that there exists point sets with at least $Ω(𝑛^2)$ squares." Yes $\mathbb{Z}^2\cap [0.\sqrt{n}]^2$ works. $\endgroup$ Commented Jul 6, 2020 at 8:41
$\begingroup$
$\endgroup$
2
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.
answered Jul 5, 2020 at 20:24
-
$\begingroup$ I quickly checked and at least in the case $n=16$, the 4-cube gives more squares than this prism (which gives 28). The 4-cube has 24 square faces alone, and there are others. But in the limit, the prisms are probably better. $\endgroup$ Commented Jul 6, 2020 at 10:26
-
$\begingroup$ By the way, the $2k$ points $\pm e_i\in\Bbb R^k, i\in\{1,...,k\}$ (where the $e_i$ form the canonical basis) also give rise to $k\choose 2$ squares. So the pattern noted by Gerry (about the regular octahedron) extends with the regular cross-polytope. $\endgroup$ Commented Jul 6, 2020 at 10:33