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

[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.

• Since there can't be three co-linear points, in fact two points determine at most 1 square (either an edge or a diagonal). Since a square has 6 pairs of vertices, this gives a trivial upper bound $n(n-1)/12$. Jul 27, 2020 at 19:28

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.