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

hv at crypt.org hv at crypt.org
Thu Oct 7 16:46:03 CEST 2021

I wrote:
:Earlier I wrote:
::I've [...] confirmed that the
::figures Sean derived using the "exhaustive search for grid points
::within a square of side ceil(sqrt(n))" are identical to those derived
::by "exhaustive search of all 1- and 2-points extensions starting from
::a unit square".
::Are we ready to conjecture that all maximal arrangements can be
::generated by such extensions? If we are, it's worth noting that this
::also trivially implies a(n) = b(n).
:Sascha Kurz has sent me some examples that refute this conjecture:
:these 8-point. 3-square arrangements cannot be generated using my
:iterative 1- or 2-point extension approach:
:xxx.   .xx.   xxx.
:.x.x   x.x.   xx.x
:x.x.   .x.x   x.x.
:..x.   .xx.

Oh, how embarrassing: they do not refute the conjecture, merely
highlight a mistake I made.

I somehow convinced myself early on that 2-point extensions in which
the source points formed the diagonal of the new square either could
not arise, or would only arise in ways that would be duplicated by
other extensions. That this conviction was incorrect is shown by these
examples, in which the initial unit square has been rotated 45 degrees
and scaled by sqrt(2).

Happily my results have only concerned themselves with demonstrating
lower bounds on a(n), so the only incorrect result I've posted is
the above claim of refutation.

The conjecture lives.


More information about the SeqFan mailing list