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

[Neil Sloane]

> Neil, I'll edit the entry on Sunday     GREAT, thanks!

If you can, please mention the smallest known example where the m X m
square array of points is not optimal.
I saw that Peter, Sascha, ... observed that moving corner points to just
outside the middle of the edges did better than the square array.  When
does this beat the square array?  And does it produce a case when b(n) >
a(n)?  That now seems very likely!

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



On Fri, Oct 1, 2021 at 9:15 AM Benoît Jubin <benoit.jubin at gmail.com> wrote:

> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>