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

Neil Sloane njasloane at gmail.com
Sat Oct 2 04:53:47 CEST 2021

```Allan,  Good suggestion!  There are 2 versions, right?  New point has to be
a grid point, or, new point can be anywhere!

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 10:47 PM Allan Wechsler <acwacw at gmail.com> wrote:

> chosen points, and then alternate removing the point that participates in
> the fewest squares with adding the point that would introduce the most
> squares. There's no reason to think this would magically find a global
> optimum, but the general structure of what it did converge on might be
> enlightening.
>
> On Fri, Oct 1, 2021 at 6:42 PM Benoît Jubin <benoit.jubin at gmail.com>
> wrote:
>
> > 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.
> > > > > 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/
> > > >
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

```