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

[Benoît Jubin]

Sascha:

Regarding the proof: for the moment, I stopped reading at "If x=3,
there is at most one new square that intersects O in cardinality
>=3.", which is not true (take a full 10x10 square and remove three
corners).  Maybe you mean something else ?  Do you have a pdf, that
you may send me privately ?

Regarding the computer generated larger values: what does the comment
"octagon" mean in the table for discs ? Can you provide a "merged"
table, with columns [ n ; S ; S/n^2 ; comment ] where S is the number
of grid-squares for the best known configuration and "comment"
describes the best known configuration (typically "disc" or "(k,
l)-octagon" where k (resp. l) is the length of the horizontal and
vertical (resp. slanted) sides in the L^\infty norm, or both or more
if there is a tie) ?

Thanks,
Benoît

On Tue, Oct 5, 2021 at 10:41 PM Kurz, Sascha
<Sascha.Kurz at uni-bayreuth.de> wrote:
>
>
> >> 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.
>
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/