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

[Kurz, Sascha]

>> Exact values
>> Values for n <= 9 are exact and are the same for a and b
> I will send a proof for n <= 12 later on.

Please find below a proof of the exact values for a(n) and b(n) for n<=13.
It's a mix of different techniques, that most likely can be further
streamlined. On the other side, I am also relatively sure that almost
all auxilliary subresults can be improved or pushed a bit further.

Best wishes,
Sascha

-----------------------------------------------------------------------------

An (m,n)-configuration is a set of m squares spanned by n different points
in the Euclidean plane. By b(n) we denote the maximum possible value for
m in an (m,n)-configuration. If the points are restricted to lie on the integer
grid, then we denote the corresponding number by a(n).

An example is the unit square with points (0,0), (0,1), (1,0), (1,1) and
graphical representation

  XX
  XX

on the 2x2 integer grid. A set representation of an (m,n)-configuration is
set of m 4-subsets of {1,...,n}, where the points are labeled from 1 to n
and the squares are represented by the labels of their vertices. In our
example we the set representation is given by {{1,2,3,4}}.

Note that any three different points can be contained in at most one square,
i.e., the sets of vertices of two different squares intersect in at most two
elements. Thus, we have b(n)<=A(n,4,4), where A(n,d,w) is the maximum size of
a binary code with word length n, minimum distance d, and constant weight w.
While being very rough, this already gives b(0)=b(1)=b(2)=b(3)=0 and b(4)=b(5)=1.
Note that each pair of different points can be contained in at most three
squares, which gives further restrictions.

Adding a further square to an (m,n)-configuration P such that the number of
points increase by 1 or 2 is called 1- or 2-point extension, i.e., we end
up with an (>=m+1,n+1)- or (>=m+1,n+2)-configuration P'. Fixing three points
in P, there may be either no square containing all three points or the
fourth point of the square is uniquely determined. If P is on an integer grid,
so is P'. Choosing two points in P there are three uniquely determined choices
for the two other points of a square. If P is on an integer grid, so is P'
after eventually stretching with a factor 2. As an example we consider the
possible 2-point extensions of the unit square. Up to symmetry, i.e., up
to similarity, we have the two possibilities

___          _X_
XXX  and XXX          Figure 1
XXX          XX_

embedded on the 3x3 grid. Another 2-point extension through the unique line
contained in both squares gives the (3,8)-configuration

X_X_X
_X_X_                 Figure 2
X_X_X

with set representation {{1,2,3,4},{1,2,5,6},{1,2,7,8}} (using a suitable labeling)
in both cases.

Starting from the unit square an exhaustive search of iterative 1- and 2-point
extensions gives the lower bounds a(6)>=2, a(7)>=3, a(8)>=4, a(9)>=6, a(10)>=7,
a(11)>=8, a(12)>=11, a(13)>=13, a(14)>=15, a(15)>=17, a(16)>=20, a(17)>=22; see
https://github.com/hvds/seq/tree/master/A051602 for an implementation by Hugo
Pfoertner. We say that an (m',n')-configuration P' can be obtained  by <=2-point
extension from an (m,n)-configuration P, if there exists a sequence of 1- and 2-point
extensions starting from P and ending in P'. If P is the unique (1,4)-configuration,
then we just say that P' can be obtained by <=2-point extension.

Conjecture 1:
We have a(n)=b(n) for all n>=0 and for n>=4 an extremal configurations can be
obtained by <=2-point extension.

The aim of this note is to prove Conjecture 1 for n<=12. To this end we will show
several sufficient criteria that allow as to deduce that all (m,n)-configurations
can be obtained by <=2-point extension if m is sufficiently large. In order to avoid
technical subtleties, we call an (m,n)-configuration reduced if we cannot remove a
point without decreasing the number of generated square, i.e., there is no reduced
(1,5)-configuration

Lemma 1:
Let P' be a reduced (m',n')-configuration that contains a reduced (m,n)-configuration P.
Set x:=n'-n as abbreviation.
(a) If x<=2 then P' can be obtained from P by <=2-point extension.
(b) If x=3 and m'-m>=2 then P' can be obtained from P by <=2-point extension.
(c) If x=4 and m'-m>=5 then a reduced (>m,>n)-configuration P'' with P''\subseteq P'
    can be obtained from P by <=2-point extension.

Proof:
Let O={1,...,n} denote the points of P and N={n+1,...,n+x} denote the points
of P'\P. Square generated by the points in P' but not by the points in P
are called "new squares".

For x=0 the statement is trivial. Thus, we can assume the existence of a new square,
represented by a 4-subset S \subseteq {1,...,n+x}, in the following. For 1<=x<=2 we
have #(S\cap N)<=2, so that there is a <=2-point extension of P to a reduced
configuration P'' with P\subsetneq P''\subseteq P' and we can eventually apply recursion.

If x=3, there is at most one new square that intersects O in cardinality >=3. Since
m'-m>=2, pick a different one and apply recursion.

If x=4, there are at most four new squares that intersect O in cardinality >=3 (noting
that their pairwise intersection has cardinality at most 2 and there are only four 3-subsets
of a 4-set).
-- End of Proof

Note that the condition in Lemma 1(c) can be relaxed to m'-m>=4. To this end consider the
point set O from the proof of Lemma 1. Each new square generates either a square or
a right isosceles triangle. The maximum number of spanned right isosceles triangles minus
three times the spanned squares (each square contains four right isosceles triangles) gives
an upper bound on the number of new squares. From Figure 4 in [AJR] we conclude that
for #O=4 there can be at most three new squares.

Corollary 1
(a) Each (2,6)-configuration can be obtained from <=2-point extension, so that b(6)=2.
    Moreover, each (2,6)-configuration is similar to one of the two examples in Figure 1.
(b) Each (3,7)-configuration can be obtained from <=2-point extension, so that b(7)=3.
    Moreover, each (3,7)-configuration is similar to one of the two examples in Figure 3.

_X_           _XX
XXX  and XXX          Figure 3
XXX          XX_

Note that there exists a reduced (2,7)-configuration that can not be obtained by
<=2-point extension.

Lemma 2:
Let P be an (m,n)-configuration. Then we either have m<=A(n,6,4) or P contains two
squares sharing two common points. In the later case, one of the two (2,6)-configurations
in Figure 1 is contained as a subconfiguration in P.

Proof:
If no pair of different squares shares a common pair of vertices, then the intersection
has size at most 1, so that m<=A(n,6,4). Otherwise 2-point extension from one square
gives the cases in Figure 1.
-- End of Proof

Corollary 2:
(a) Each reduced (>=3,8)-configuration can be obtained from <=2-point extension, so
    that b(8)=4. Moreover, each (4,8)-configuration is similar to the unique example
    with 8 points in Figure 4.
(b) Each reduced (>=4,9)-configuration can be obtained from <=2-point extension, so
    that b(9)=6. Moreover, each (6,9)-configuration is similar to the unique example
    with 9 points in Figure 4.

Proof:
Let P' be an arbitrary reduced (>=3,8)-configuration. Since A(8,6,4)=2, a (reduced)
(2,6)-configuration P exists as a subconfiguration by Lemma 2. Then Lemma 1 gives (a).

Let P' be an arbitrary reduced (>=4,9)-configuration. Since A(9,6,4)=3, a (reduced)
(2,6)-configuration P exists as a subconfiguration by Lemma 2. Then Lemma 1 gives (b).
-- End of Proof

XX_           XXX
XXX  and  XXX          Figure 4
XXX           XXX


Lemma 3:
(a) Each reduced (>=6,10)-configuration can be obtained from <=2-point extension, so
    that b(10)=7.
(b) Each reduced (>=8,11)-configuration can be obtained from <=2-point extension, so
    that b(11)=8.
(c) Each reduced (>=11,12)-configuration can be obtained from <=2-point extension, so
    that b(12)=11.

Proof:
Let P' be an arbitrary (>=7,10)-configuration. Assume that P' contains a (>=5,9)-subconfiguration P.
Then, b(8)=4<5 implies that P is reduced, so that we can apply Corollary 2(b) to conclude
that P' can be obtained from <=2-point extension. If all ten 9-subsets of {1,...,10}
generate at most 4 squares, then we obtain at most 10*4=40 incidences between squares
and 9-subsets. On the other side, each square is contained in six 9-subsets, so that
there can be at most floor(40/6)=6 squares in total -- contradiction. This already
gives b(10)=7.

Let P' be an arbitrary (6,10)-configuration. Since floor(6*4/10)=2, there exists a
vertex v in P' that is contained in at most two different squares. Removing
v yields a (>=4,9)-configuration P. If P is reduced, then we can apply Corollary 2(b).
If P is not reduced, then there exists a reduced (4,8)-configuration and we can
apply Corollary 2(a). So, in all cases we can conclude (a).

Let P' be an arbitrary reduced (>=8,11)-configuration. Assume that P' contains a
(>=6,10)-subconfiguration P. If P is reduced that we can apply part (a) and Lemma 1(a).
If P is not reduced, then b(8)=4 implies that there exits a reduced (6,9)-subconfiguration
an we can again apply part (a) and Lemma 1(a). If all eleven 10-ssubsets of {1,...,11}
generate at most 5 squares, then we obtain at most 11*5=55 incidences between squares
and 10-subsets. On the other side, each square is contained in seven 10-subsets, so that
there can be at most floor(55/7)=7 squares in total -- contradiction. Thus, we conclude
part (b).

Let P' be an arbitrary (>=11,12)-configuration. If each 11-subset generates at most
7 squares, then we would have at most ten squares in total -- contradiction. Thus,
there exists a (>=8,10)-subconfiguration so that we can apply part (b) and Lemma 1(a).
-- End of Proof

Generalizing some ideas in the proof of Lemma 3 we may state:
Lemma 4:
(a) In each (m,n)-configuration there exists a vertex of degree at most r=floor(4m/n).
    Moreover, there exists an (>=m-r,n-1)-subconfiguration.
(b) Let P be an (m,n)-configuration. If each k-subset of points of P contains at most
    x squares, then we have binomial(n,k)*x >= m*binomial(n-4,k-4).

In order to proceed with the cases n>12 we have to refine our tools to the situation
where no pair of points is contained in three squares.

Lemma 5:
Let P be an (m,n)-configuration that contains a pair of points that is contained
in three squares. Then, a (3,8)-configuration as in Figure 2 is contained as a
subconfiguration.


Proposition 1:      b(13)=13

Proof:
Assume that P' is an arbitrary (>=14,13)-configuration. Let P be an (m,n)-subconfiguration
of P' that can be obtained by <=2-point extension and maximizes the number n of points.
Since A(13,6,4)=13, we have n>=6. Due to Lemma 1.(a) we can assume n<=10. The case
n=10 is excluded by b(10)=7 and Lemma 1.(b); the case n=9 is excluded by b(9)=6 and
Lemma 1.(c). If all 12-subsets of points in P' generate at most 10 squares, then we
end up with at most 14 squares in total. Since the case n=12 is excluded, we can use
Lemma 3.(c) to deduce b(13)<=14.

If P' contains a pair of points that is contained in 3 squares, then we can apply Lemma 5
to choose P as the (3,8)-configuration in Figure 2. Label the points in P by {1,...,8}.
Since we already know n<=8, each additional square contains at least three points from
O={9,...,13}. Since there are only ten 2-subsets from O, each 2-subset is contained in
at most 3 squares, and >=3-tuple of O contains at least three 2-subsets, the number of
new squares is at most 10*3/3=10, so that there are at most 3+10<13 square in total --
contradiction. Thus, we can assume 6<=n<=8 and each pair of points is contained in at most
two squares.

If n=8, then there can be at most floor(10*2/3)=6 new squares, so that there are at most
b(8)+6=10<14 squares in total -- contradiction. If n=7, then there can be at most
floor(15*2/3)=10 new squares, so that there are at most b(7)+10=13<14 squares in total
-- contradiction

In the remaining cases we have n=6. Note that each point is contained in at least 4 squares,
since otherwise we would obtain a (>=11,12)-configuration, which can be obtained by
<=2-point extension due to Lemma 3.(c). Let the set representation of P be given by
{{1,2,3,4},{1,2,5,6}}. Since P cannot be extended by a <=2-point extension, each further
square through vertex 3 meets O={7,...,13} in three points. There have to be two such
squares intersecting in a further point besides 3. W.l.o.g. we assume that they are given
by {3,7,8,9} and {3,7,10,11}, which also forms a (2,6)-configuration
{{3,7,8,9},{3,7,10,11}}, which cannot be extended. Thus, the fourth square through vertex 3
has to be disjoint to {1,2,4,5,6} and to {7,8,9,10,11}, i.e., its vertices have to be
contained in {3,12,13}, which is impossible.
-- End of Proof

References:
[AFR] Ábrego, B., Fernández, S., & Roberts, D. (2011). On the maximum number of isosceles
right triangles in a finite point set. Involve, a Journal of Mathematics, 4(1), 27-42.