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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.