[seqfan] Re: How many squares can you make from n points in the plane?

[Kurz, Sascha]

Last month I wrote:

> Unfortunately, I do not have a pdf right now, but, given some time, I may
> produce one. If there is sufficient interest I may also create an overleaf
> project or share tex/pdf privately.

In the meantime proofs for the maximum number of squares of
point sets with up to 16 points are written up. The proof that maximal
examples can be assumed to lie on the integer grid is spelled out. See
possibly https://www.overleaf.com/5434274833vmtzqpfthcsm

An improved general upper bound:
n points in the plane generate at most  (n^2-1)/8 squares


Proof:

Let < denote the strict lexicographic ordering on R^2. Given a square let its vertices be labeled and ordered

as v1 < v2 < v3 < v4. We call {v1,v2} the leftmost edge and {v1,v3} the second leftmost edge of the square

(noting that both pairs of verties indeed form edges of the square). Observe that while a pair of points can be

contained in three different squares, the number of cases where it is the leftmost or the second leftmost edge

is at most one.


Let P be an arbitrary n-point set.Using a suitable similarity transformation we can assume that at most (n+1)/2

points have negative and at most (n+1)/2 points have positive x-coordinates, while the y-axis is free of points.
By a_ij we denote the number of squares such that exactly i of its vertices have negative coordinates, where
0 <= i,j <= 4 with i + j = 4. If necessary by reflecting in the y-axis we can assume a_31 + a_40  >= a_13 + a_04 .
Counting leftmost and second leftmost edges consisting of vertices with negative x-coordinates gives

  a_22 + 2a_31 + 2a_40 <= (n+1)/2 choose 2=(n^2-1)/8,

so that P contains at most

  a_22+a_31+a_40+a_13+a_04 <=a_22 + 2a_31 + 2a_40 <=(n^2-1)/8

squares.  [qed]


Best regards,
Sascha