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

[Kurz, Sascha]

Let b(n) denote the maximum number of squares spanned by n different points in the Euclidean plane. For brevity,
call an extremal set n-configuration and label the points by 1,...,n. The aim is to determine b(n) and to classify
n-configurations up to symmetry for n<=9 (without assuming an integer grid).

Since each square is spanned by four points we have b(0)=b(1)=b(2)=b(3)=0 and the points can be chosen arbitrarily
in the plane. Since two squares share at most 2 vertices, the n points form a constant weight code with weight 4 and
minimum Hamming distance at least 4. Thus, we have b(4)=b(5)=1 with the obvious isomorphism types. If no two squares
share 2 common vertices, then the code has minimum Hamming distance at least 6. Since the known constructions on the
integer grid contain more squares than the maximum possible size of the code for n<=12, we can assume the existence
of two squares sharing two vertices. Up to symmetry there are just two non-isomorphic cases, both consisting of six
vertices and two squares, so that b(6)=2.

For n=7 any additional square contains three of the six vertices of a contained 6-configuration, so that the coordinates
of the 7th point are also defined. Up to symmetry there are just two cases, both consisting of 3 squares, so that b(7)=3.

For n=8 there exists an, up to symmetry, unique extension of a 7-configuration by one further square (and 4 squares in
total, so that b(8)>=4). Now let C be an 8-configuration that does not contain a 7-configuration. Considering the the eight
7-element subsets of vertices yields that C contains at most 8*2/4=4 squares, i.e., b(8)=4 and every 7-subset of the vertices
of C contains exactly 2 squares. If a vertex of C would be contained it at most one square, then removing that vertex would
yield a 7-configuration. Thus, all 8 vertices are contained in exactly two squares. Now consider the two possible 6-configurations
and pick an arbitrary vertex v1 that is contained in a single square. For each of the other three possibilities of a vertex v2
that is also contained in a single square consider the three possible squares containing v1 and v2. We only have to consider
the cases where the new square produces two new vertices. In all cases we can easily check that at least one vertex is contained
in a single square. Thus, there is just one non-isomorphic 8-configuration.

Let C be a 9-configuration. If C contains an 8-configuration, then there is an unique extension by an additional square showing
b(9)>=6. If all of the nine 8-subsets of the vertices of C contain at most three squares, then C contains at most 9*3/5<6 squares.
Thus, b(9)=6 and there is a unique isomorphism type.

The same problem in 3-space is discussed here:
https://mathoverflow.net/questions/364907/how-many-squares-can-be-formed-by-using-n-points

Best,
Sascha
--
Email: sascha.kurz at uni-bayreuth.de