[seqfan] Re: How many squares can you make from n points in the plane?
Kurz, Sascha
Sascha.Kurz at uni-bayreuth.de
Sat Nov 13 15:38:14 CET 2021
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
More information about the SeqFan
mailing list