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

[Benoît Jubin]

Neil, I'll edit the entry on Sunday, with the results in this thread,
including Sascha's latest mail.

It would be nice to investigate a little further on Sascha's latest
remark (buiding on remarks by Hugo and Peter), and add/remove points
in adjacent layers of the boundary of the mXm grid (not limiting
oneself to configurations with m^2 points, but saving in memory
current records), going up to m/3 far away from the boundary (or more
or less depending on the shape of the more promising results).  Maybe
the limit configuration is an octagon, like for a(12) = 11.

Benoît

On Fri, Oct 1, 2021 at 10:42 AM Kurz, Sascha
<Sascha.Kurz at uni-bayreuth.de> wrote:
>
> > 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
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/