1
$\begingroup$

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.

$\endgroup$

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.