[seqfan] Re: How many squares can you make from n points in the plane?
Kurz, Sascha
Sascha.Kurz at uni-bayreuth.de
Fri Oct 1 10:42:35 CEST 2021
> Benoit, There have been so many new developments (they are all in this
> email thread, though), that I have lost track of where we are.
Let me mention and summarize a few things.
The mxm square grid construction gives m^2*(m^2-1)/12 squares, see A002415, so that we get a lower bound of
roughly n^2/12 for b(n).
Sequence A186926 on the maximal number of isosceles right triangles in a set of n points in the plane is
somewhat related. Since each square contains 4 such triangles we obtain the upper bound floor(2/3 *(n-1)^2-5/3)/4,
which is roughly n^2/6.
Starting from an mxm or mx(m-1) grid and iteratively removing points quickly gives lower bounds. For 1<=n<=50 we get
b(n)>=
0,0,0,1,1,2,3,4,6,7,
8,11,13,15,17,20,22,25,28,32,
37,40,43,47,51,56,60,65,70,75,
81,88,92,97,103,109,117,123,130,137,
144,151,158,166,175,182,189,197,205,213
Especially, we have b(25)>=51, b(36)>=109, and b(49)>=205, which beats the mxm-square grid construction without removal.
As Peter demonstrated, this is true for all m>=7.
It can be shown that starting from the two optimal configurations for 7 points and the unique 8-point configuration
where a pair of points is contained in three squares, the iterative 1- and 2-point addition mentioned by Hugo will
safely reach all optimal configurations for 10, 11, and 12 points. Moreover, this extension strategy guarantees to
stay within integer grids, while the sizes of the necessary grids might roughly double after each iteration.
(The approach in "Á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." for the exact determination of A186926(n) for
n<=9 shows some similarities.)
Best,
Sascha
More information about the SeqFan
mailing list