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

[Kurz, Sascha]

 > Regarding the proof: for the moment, I stopped reading at "If x=3,
> there is at most one new square that intersects O in cardinality
> >=3.", which is not true (take a full 10x10 square and remove three
> corners).  Maybe you mean something else ?  Do you have a pdf, that
> you may send me privately ?

Sorry, there is a stupid typo. In your example we have O={1,...,97} and
N={98,99,100}. Fom the assumption that no <=2-point extension exists
we conclude that N (not O) is intersected in cardinality at least 3 by each
"new" square. (In the example the squares being attached to the three
removed corners almost all meet O in at least 2, i.e. N in at most 2 points.)

Unfortunately, I do not have a pdf right now, but, given some time, I may
produce one. If there is sufficient interest I may also create an overleaf
project or share tex/pdf privately.

> Regarding the computer generated larger values: what does the comment
> "octagon" mean in the table for discs ? Can you provide a "merged"
> table, with columns [ n ; S ; S/n^2 ; comment ] where S is the number
> of grid-squares for the best known configuration and "comment"
> describes the best known configuration (typically "disc" or "(k,
> l)-octagon" where k (resp. l) is the length of the horizontal and
> vertical (resp. slanted) sides in the L^\infty norm, or both or more
> if there is a tie) ?

Here is a new try. As Peter told me, there are circles centered at (0,0),
see A057961, and circles centered at (0.5,0.5), see A057962. I will write
circle(n) for the corresponding circle containing n grid points. I will also
need the following configurations

48 points generate 198 squares; contained in a 8x8-grid.

___XX___
_XXXXXX_
_XXXXXXX
XXXXXXXX
XXXXXXXX
_XXXXXXX
_XXXXXX_
__XXXX__

63 points generate 346 squares; contained in a 9x9-grid.

___XXX___
__XXXXXX_
_XXXXXXX_
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
_XXXXXXXX
_XXXXXXX_
__XXXXX__

74 points generate 480 squares; contained in a 10x9-grid.

___XXX___
_XXXXXXX_
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
XXXXXXXXX
_XXXXXXX_
___XXX___

91 points generate 731 squares; contained in a 11x11-grid.

____XXX____
__XXXXXXX__
_XXXXXXXXX_
_XXXXXXXXX_
XXXXXXXXXXX
XXXXXXXXXXX
XXXXXXXXXXX
_XXXXXXXXXX
_XXXXXXXXX_
__XXXXXXX__
____XXXX___

which I denote by s(n), where n is the number of grid points. For each "structure"
I will write structure-ext if the configuration can be obtained from the starting
configuration structure by recursive 1-point extensions that each meet the currently
best known upper bound.

n    S    n^2/S    comment
1    0
2    0
3    0
4    1    16,00    circle(4)
5    1    25,00    circle(4)
6    2    18,00    rectangle(2x3)
7    3    16,33    rectangle(2x3)-ext
8    4    16,00    rectangle(2x3)-ext
9    6    13,50    circle(9)
10    7    14,29    circle(9)-ext
11    8    15,13    circle(9)-ext
12    11    13,09    circle(12)
13    13    13,00    circle(12)-ext
14    15    13,07    circle(12)-ext
15    17    13,24    circle(12)-ext
16    20    12,80    circle(12)-ext ,circle(16)
17    22    13,14    circle(12)-ext ,circle(16)-ext
18    25    12,96    circle(12)-ext ,circle(16)-ext
19    28    12,89    circle(12)-ext ,circle(16)-ext
20    32    12,50    circle(12)-ext
21    37    11,92    circle(21)
22    40    12,10    circle(21)-ext
23    43    12,30    circle(21)-ext
24    47    12,26    circle(21)-ext
25    51    12,25    circle(21)-ext
26    56    12,07    circle(21)-ext
27    60    12,15    circle(21)-ext
28    65    12,06    circle(21)-ext
29    70    12,01    circle(21)-ext
30    75    12,00    circle(21)-ext
31    81    11,86    circle(21)-ext
32    88    11,64    circle(32)
33    92    11,84    circle(32)-ext
34    97    11,92    circle(32)-ext
35    103    11,89    circle(32)-ext
36    109    11,89    circle(32)-ext
37    117    11,70    circle(37)
38    123    11,74    circle(37)-ext
39    130    11,70    circle(37)-ext
40    137    11,68    circle(37)-ext
41    144    11,67    circle(37)-ext
42    151    11,68    circle(37)-ext
43    158    11,70    circle(37)-ext
44    166    11,66    circle(37)-ext
45    175    11,57    circle(45),circle(37)-ext
46    182    11,63    circle(45)-ext,circle(37)-ext
47    189    11,69    circle(45)-ext,circle(37)-ext
48    198    11,64    s(48)
49    207    11,60    s(48)-ext
50    216    11,57    s(48)-ext
51    226    11,51    s(48)-ext
52    237    11,41    circle(52)
53    245    11,47    circle(52)-ext
54    254    11,48    circle(52)-ext
55    263    11,50    circle(52)-ext
56    272    11,53    circle(52)-ext
57    282    11,52    circle(52)-ext
58    293    11,48    circle(52)-ext
59    303    11,49    circle(52)-ext
60    314    11,46    circle(52)-ext
61    324    11,48    circle(52)-ext
62    334    11,51    circle(52)-ext
63    346    11,47    s(63)
64    358    11,44    s(63)-ext
65    370    11,42    s(63)-ext
66    382    11,40    s(63)-ext
67    394    11,39    s(63)-ext
68    407    11,36    s(63)-ext
69    421    11,31    circle(69)
70    431    11,37    circle(69)-ext
71    442    11,40    circle(69)-ext
72    454    11,42    circle(69)-ext
73    466    11,44    circle(69)-ext
74    480    11,41    s(74)
75    493    11,41    s(74)-ext
76    507    11,39    circle(76)
77    521    11,38    circle(76)-ext
78    535    11,37    circle(76)-ext
79    549    11,37    circle(76)-ext
80    564    11,35    circle(80)
81    578    11,35    circle(80)-ext
82    593    11,34    circle(80)-ext
83    608    11,33    circle(80)-ext
84    623    11,33    circle(80)-ext
85    638    11,32    circle(80)-ext
86    653    11,33    circle(80)-ext
87    669    11,31    circle(80)-ext
88    686    11,29    circle(80)-ext ,circle(88)
89    700    11,32    circle(80)-ext
90    715    11,33    circle(80)-ext
91    731    11,33    s(91)
92    748    11,32    s(91)-ext
93    765    11,31    s(91)-ext
94    782    11,30    s(91)-ext
95    799    11,30    s(91)-ext
96    817    11,28    s(91)-ext
97    836    11,25    circle(97)
98    853    11,26    circle(97)+ext
99    870    11,27    circle(97)+ext
100    887    11,27    circle(97)+ext

Of course, the construction mentioned in the comment has to be taken with a pinch of salt.
All best known values are just found heuristically (improvements more than welcome). Whenever
I can reach a value with a known simple construction I keep this and not the extension-description.
So, the extension chains, c.f. the pictures in earlier posts, can actually be longer.
Note that n=20 is special. It can be reached from circle(12) but not from circle(16)
(assuming the very restricted extension procedure). The four special starting configurations can be
found very easily and have a shape that is not too surprising. (Maybe a desription as an extension
of a hexagon is feasible and appropriate.) However, these descriptions are highly speculative and biased.
Please just ignore or replace them. If you wonder about my former octagon friends, they are replaced by:
(2,0)-octagon=circle(4), (3,0)-octagon=circle(9), (4,1)-octagon=circle(12), (4,0)-octagon=circle(16),
(5,1)-octagon=circle(21), (6,1)-octagon=circle(32), (7,2)-octagon=circle(37), (7,1)-octagon=circle(45),
(8,2)-octagon=circle(52), (9,2)-octagon=circle(69), (10,3)-octagon=circle(76), (10,2)-octagon=circle(88)
(11,3)-octagon=circle(97)

Benoît, I will send a spreadsheet privately.

Best regards,
Sascha