[seqfan] Re: How many squares can you make from n points in the plane?
Kurz, Sascha
Sascha.Kurz at uni-bayreuth.de
Wed Oct 6 14:18:09 CEST 2021
> 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
More information about the SeqFan
mailing list