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

[Benoît Jubin]

Hi all,

I have just edited the entry with the more important results from this
thread.  I hope I credited everyone fairly.  This edit is basically
the summary I posted above with minor corrections and the addition of
the better upper bound from [AFR].

There is ongoing promising work, in particular by Hugo and Sascha,
towards extending the proof of exact values from n<=9 to n<=13, and
finding better configurations for larger values of n.  Since things
haven't settled down yet, I did not put them in this edit.

Best regards,
Benoît

On Thu, Oct 7, 2021 at 5:35 PM <hv at crypt.org> wrote:
>
> 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.
>
> Hugo
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/