The question was recently asked How many squares can be determined by $n$ points in $\mathbb{R}^3$?
The main observations were:
- In $\mathbb{R}^2$ at most $O(n^2)$ as every pair of points determines at most 3 squares.
- In $\mathbb{R^3}$ at most $O(n^3)$ as every triple of points determines at most one square
- This can be improved to $O(n^{7/3}$) as it is known that this is sharp for the number of right triangles determined by $n$ points in $\mathbb{R}^3.$
However it would be more relevant to have a bound on the number of isosceles right triangles.
I would guess that in the long run the optimum arrangement in $\mathbb{R}^3$ is a square grid of side $s=\sqrt{n}.$
If I calculate correctly, a square grid of $n=s^2$ points determines $\frac{s^4-s^2}{12}$ squares, so indeed $O(n^2)$.
I would also guess that this might be best for $\mathbb{R}^3$ and, if not , then a cubic grid of side $s=\sqrt[3]{n}$ is best.
These aren't very educated guesses. So my main question (in two parts) is
Suppose $n=t^6$,
Does any arrangement of $n$ points in $\mathbb{R}^2$ determine more squares that a square grid of side $t^3?$
Does any arrangement of $n$ points in $\mathbb{R}^3$ determine more squares that a square grid in a plane of side $t^3?$
I picked $n=t^6$ to allow for a cube of side $t^2$ as well.
I think it best to ask one main question, but those seem related enough. Secondary questions are:
- Is anything known about the arrangements in $\mathbb{R}^3$ which achieve $O(n^{7/3})$ right triangles?
- Is anything known about bounds and arrangements for the number of isosceles right triangles?
- Are formulas or bounds known for the number of squares determined by the points of a cubic grid of $s^3$ points?
An answer to that last one might show that the answer to the second part of the main question is NO.
In a cubic grid of $s^3$ points one has $3s$ squares of side $s$ parallel to coordinate planes. So there are $3s\frac{s^4-s^2}{12}$ squares in those planes. That is only $O(n^{5/3})$. However any two orthogonal vectors of equal length determine a family of planar lattices with a certain number of squares. Determining the number of such squares within a cube may be known but is certainly more delicate that the planar case.
A particularly productive length is $15:$
The integer vectors of length $15$ are $(15,0,0),(14,5,2),(12,9,0),(11,10,2),(10,10,5)$ along with their permutations and changing the sign on some coordinates.
A number of orthogonal pairs are possible such as
- $(15,0,0),(0,15,0)$
- $(10,10,5),(10,-5,-10)$
- $(12,9,0),(-9,12,0)$
- $(15,0,0),(0,9,12)$
- $(14,5,2),(2,-10,11)$
- $(14,5,2),(-5,10,10)$
- $(11,10,2),(-10,10,5)$
And again the coordinates can be permuted and signs flipped.
