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

Jack Grahl jack.grahl at gmail.com
Tue Oct 5 15:22:35 CEST 2021

```My instinct is that it would be surprising if circles are best — and that
some n-gon with n large will dominate over circles for large numbers of
points.

Octagons are better than squares because they allow more squares with (1,1)
sides. However they don't do well for other small squares, such as sides
(1,2), (1,3), (2,3), etc. However, there's only a limited number of angles
of such small squares that we want to cover. A configuration of points
which has 'sides' at all these basic rational angles might do well as lots
of the border could be filled with squares. While an approximate circle
will have pieces of the boundary at lots of other angles which can't be
covered by either small squares or large ones.

Of course, for smallish n the circle is very close to the (say) 48-gon with
sides of 4 small rational fundamental angles. When they start to become
different I think the latter might do better than the former.

Yours,
Jack

On Tue, 5 Oct 2021, 14:05 Kurz, Sascha, <Sascha.Kurz at uni-bayreuth.de> wrote:

>
> > Sascha: what are you run-times ? How far can you compute these
> > configurations ? Can you compute one around n = 140 ? This could
> > probably tell circles and octagons appart (my bet is now on circles).
>
> Prescribing a (12,3)-octagon
>
> 120 points generate 1286 squares; contained in a 12x12-grid.
> ___XXXXXX___
> __XXXXXXXX__
> _XXXXXXXXXX_
> XXXXXXXXXXXX
> XXXXXXXXXXXX
> XXXXXXXXXXXX
> XXXXXXXXXXXX
> XXXXXXXXXXXX
> XXXXXXXXXXXX
> _XXXXXXXXXX_
> __XXXXXXXX__
> ___XXXXXX___
>
> it took 4.32 seconds to compute the optimal extension by 20 points on the
> surrounding 14x14-grid. (I stopped the extension to an 16x16 grid after
> 30 minutes, where the LP bounds where between 1752 and 1789.)
>
> 140 points generate 1752 squares.
> contained in a 13x13-grid.
>
> ___XXXXXXX___
> __XXXXXXXXX__
> _XXXXXXXXXXX_
> _XXXXXXXXXXXX
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> _XXXXXXXXXXX_
> _XXXXXXXXXXX_
> __XXXXXXXXX__
> ____XXXXX____
>
>
>
> Prescribing a circle with radius  6.0828
>
> 121 points generate 1298 squares; contained in a 13x13-grid.
>
> _____XXX_____
> ___XXXXXXX___
> __XXXXXXXXX__
> _XXXXXXXXXXX_
> _XXXXXXXXXXX_
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> XXXXXXXXXXXXX
> _XXXXXXXXXXX_
> _XXXXXXXXXXX_
> __XXXXXXXXX__
> ___XXXXXXX___
> _____XXX_____
>
> it took 155.42 seconds to compute the optimal extension by 19 points on the
> surrounding 15x15-grid. The very same solution was computed
>
>
> My bet is now on circles too. However, for small numbers of points
> (k,l)-octagons perfom pretty well:
> k      l     n          m        n(n-1)/m    comment
> 2      0    4          1        12.000    optimal
> 3      0    9          6        12.000    optimal
> 4      1    12        11      12.000    optimal
> 4      0    16        20      12.000    best known
> 5      1    21        37      11.351    best known
> 6      1    32        88      11.273    best known
> 7      2    37        117    11.385    best known
> 7      1    45        175    11.314    best known
> 8      2    52        237    11.190    best known
> 9      2    69        421    11.145    best known
> 10    3    76        507    11.243    best known
> 10    2    88        686    11.160
> 11    3    97        836    11.139
> 12    3    120     1286    11.104
> 13    3    145     1880    11.106
> 14    4    156     2175    11.117
> 14    3    172     2643    11.128
> 15    4    185     3070    11.088
> 16    5    196     3425    11.159
> 15    3    201     3602    11.160
> 16    4    216     4190    11.084
>
> Circles seem to perform better if the number of points gets larger
> radius     n    m    n(n-1)/m    comment
> 1.4143    9    6    12.000    optimal
> 2.0001    13    11    14.182    2 off opimal
> 2.2361    21    37    11.351    best known
> 2.8285    25    50    12.000    1 off best known
> 3.0000    29    67    12.119
> 3.1623    37    117    11.385    best known
> 3.6056    45    175    11.314    best known
> 4.0000    49    204    11.529
> 4.1232    57    278    11.482
> 4.2427    61    323    11.331
> 4.4722    69    421    11.145    best known
> 5.0000    81    568    11.408
> 5.0991    89    698    11.221
> 5.3852    97    836    11.139    octagon
> 5.6569    101    905    11.160
> 5.8310    109    1051    11.201    octagon
> 6.0001    113    1128    11.220
> 6.0828    121    1298    11.186
> 6.3246    129    1476    11.187    octagon
> 6.4032    137    1678    11.104
> 6.7083    145    1880    11.106    octagon
> 7.0001    149    1977    11.154
> 7.0711    161    2304    11.181
> 7.2112    169    2546    11.152
> 7.2802    177    2812    11.078
> 7.6158    185    3070    11.088    octagon
> 7.8103    193    3336    11.108
> 8.0001    197    3469    11.131
> 8.0623    213    4065    11.108
> 8.2463    221    4387    11.083
> 8.4853    225    4544    11.092
> 8.5441    233    4874    11.091
> 8.6024    241    5228    11.064
> 8.9443    249    5566    11.095    octagon
> 9.0001    253    5743    11.102
> 9.0554    261    6113    11.101
> 9.2196    277    6901    11.078    better than octagon
> 9.4340    285    7311    11.071
> 9.4869    293    7745    11.047
> 9.8489    301    8155    11.073    octagon
> 9.8995    305    8368    11.080
> 10.0001    317    9031    11.092
> 10.0499    325    9505    11.078
> 10.1981    333    9987    11.070
> 10.2957    341    10485    11.058
> 10.4404    349    10991    11.050
> 10.6302    357    11497    11.054    better than octagon
>
> However, we will really need quite some points to see the asymptotical
> fraction 11.008 (and to see differences between
> circles and octagons).
>
> I have no glue whether choosing a different grid in a small circle inside
> another circle, as in Theorem 4 in the paper on
> isoclees right triangles, may get us below 11.008.
>
> Is it worth to collect "best known" lower bounds for all numbers of
> points? Up to which n?
>
> Best regards,
> Sascha
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

```