How many squares can be formed by $n$ points in general position in the plane?

Question

[This is much in the spirit (but different from) the questions from different posters: How many squares can be formed by using n points? and How many squares can be formed by using n points: revisited?]

Let $A$ be a set of $n$ points in the plane in general position. By general position we mean that no $3$ points are co-linear. What is the maximum number of squares that can be formed with vertices in $A$?

I note that there are trivial upper and lower bounds for this problem:

[Trivial Upper Bound] Given $n$ arbitrary points in the plane, noting that any two points determine at most $3$ squares it follows that there are at most $O(n^2)$ squares with vertices in $A$.

[Trivial Lower Bound] Place four points at the corner of a square, and repeat taking care to avoid all lines generated by pairs of points already placed in the plane until we've placed $n$ points. This clearly gives a lower bound of $\Omega(n)$.

I can improve the implied constant in both the upper and lower bound by being a bit more clever. The problem, however, is to

Improve (asymptotically) on either the upper or lower bound just given.

Answer 1

We can get a lower bound on the order of $n \log n$.

I'll describe how to arrange $4^n$ points in general position to get $n 4^{n-1}$ squares.

The arrangement is described recursively. For the base case $n=1$, we have $4^1 = 4$ points, and you can probably guess how we should arrange them to get $1 \cdot 4^{1-1} = 1$ squares. Now suppose we have an arrangement $A$ of $4^{n-1}$ points, in general position, giving us a total of $(n-1)4^{n-2}$ squares. Take $4$ copies of $A$ (a total of $4^n$ points). Place the $4$ copies of $A$ at the $4$ corners of a "large" square, and then rotate each copy of $A$ by a "random" angle $\theta$ (the same angle for each of our $4$ copies of $A$). This gives us our new arrangement of points.

If the square mentioned above is large enough, then no points from $3$ distinct copies of $A$ can lie on a line. And it is not hard to show that, with probability $1$, a randomly chosen $\theta$ will have the property that no two points from a given copy of $A$ will lie on a common line with a different copy of $A$. So for a "large" square and a "random" angle, we get a set of $4^n$ points in general position.

In each small copy of $A$, we get $(n-1)4^{n-2}$ small squares, for a total of $4(n-1)4^{n-2} = (n-1)4^{n-1}$ small squares in our new arrangement. In addition to these, we get $|A| = 4^{n-1}$ additional large squares, by connecting the $4$ corresponding points in each of our $4$ copies of $A$. This gives a total of $n4^{n-1}$ squares, as promised.