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

[Alex Meiburg]

I ran the computation for what happens if you take a circular region of
points in a grid. It's fairly straightforward in the asymptotic case,
because it all just comes down to computing (and integrating) areas, and we
don't have to actually worry about the integrality of points; and a result
it becomes rotationally invariant. It comes out to 3(1/16 - 1/8pi)n^2
~=  0.0681338 n^2  ~=  n^2 / 14.677, assuming I didn't make a mistake. But,
this sounds pretty reasonable, given that for squares it's n^2/12. This
means that it performs worse, asymptotically, than a square of points.

In case anyone wants to check the work, I got that for a square with
sidelength r0 in a circle of radius r, there is a region of area
  A  -(1/2) r0 (-r0/2 + sqrt(r^2 - r0^2/4)) + r^2 (pi/2 - 2 arcsin(r0/2r))
where the center of the square can be. Then the full number of
possibilities is integral( A * (pi/2)r0,  for r0 from 0 to r).

It seems natural to think about symmetric convex shapes (squircles and
friends?) in the plane, and then optimize over the shape to find the one
that produces the largest number of squares inside. In theory, probably
possible to derive a diff eq for the ideal shape of the curve. In my
opinion, that would have a very high chance of being asymptotically optimal
for the sequence. (Although probably quite hard to prove!)

-- Alexander Meiburg


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

> > Benoit,  Thanks for the lovely example for n=49 !
>
> That shows that a(49)>=202 if I counted correctly, but Sascha has an
> example with 205 apparently.
>
> Peter, Sascha: can you give me your optimal configurations ? (best
> would be: in place of an "x" to denote a vertex, put the number of
> squares it belongs to)
>
> Neil: since Sascha is on a 3-day trip, I may wait Monday or Tuesday to
> update the entry, if that's ok with you.
>
> Benoît
>
>
> > 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 1:54 PM Benoît Jubin <benoit.jubin at gmail.com>
> wrote:
> >
> > > > 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!
> > >
> > >
> > > For the moment, all points are on the grid, so there is no witness
> > > that a(n) and b(n) may differ.  What they mean, I think, is for
> > > instance for m = 7:
> > > ....x....
> > > ..xxxxx..
> > > .xxxxxxx.
> > > .xxxxxxx.
> > > xxxxxxxxx
> > > .xxxxxxx.
> > > .xxxxxxx.
> > > ..xxxxx..
> > > ....x....
> > > This wins over the square, because a corner was in 6 squares (so we
> > > lose 4*6 - 1 squares), whereas the added midpoints are in 7 squares
> > > each, plus 1 common square through the four midpoints. So it should be
> > > a +6 win.
> > >
> > > Benoît
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>