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

Benoît Jubin benoit.jubin at gmail.com
Sat Oct 2 00:41:56 CEST 2021

```Thanks Alex. Since a(n) >= n^2/12 - O(n), circles are out.  Maybe try
octagons which are intersections of two concentric squares rotated by
pi/4 (so there are two side lengths) ?

I'm not sure I understand your computation: for each point with
coordinates (a,b) or (a+1/2, b+1/2) within the shape, you compute the
number of squares which have it as center (both the horizontal ones
and the slanted ones; this is easy to compute from the distance of the
center to the boundary of the shape).  For the cercle, this is
espacially easy.  Is that it ?  In that case, the octagon are a bit
more tedious (a few different cases to handle) but seems doable.

Side note: Peter corrected me: in the example above, I obtain a(49) >=
204.  Sascha found 205, so we may have to wait Monday to see his
configurations.

Benoît
On Sat, Oct 2, 2021 at 12:28 AM Alex Meiburg <timeroot.alex at gmail.com> wrote:
>
> 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.
> > > 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/

```