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

Sat Oct 2 05:27:33 CEST 2021

I didn't think of the unconstrained version. Now that you suggest it,
though, I'm very curious to know: if you initialize with a gridded
collection of points, would the best new point ever be off the grid? If it
were, I think it has to have rational coordinates, and thus could be
captured in a new, finer grid.

I am having trouble explaining my skepticism that the unconstrained version
adds any actual possibilities. And yet, in the superficially similar
problem of maximally-dense unit distance graphs (see
https://oeis.org/A186705), I think the ungridded problem definitely gives
denser solutions. Is there a sequence already for the gridded analog of
A186705?

On Fri, Oct 1, 2021 at 10:54 PM Neil Sloane <njasloane at gmail.com> wrote:

> 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.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Fri, Oct 1, 2021 at 10:47 PM Allan Wechsler <acwacw at gmail.com> wrote:
>
> > Has anybody tried a greedy adjustment algorithm? Start with N arbitrarily
> > 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>