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

[Benoît Jubin]

On Sun, Oct 10, 2021 at 12:58 PM Robert Gerbicz
<robert.gerbicz at gmail.com> wrote:
>
> That dilation doesn't help

You're right, my objection was nonsense.  This is a nice example of
grid-configuration versus general configuration.  This also explains
why the best configuration found by [AFR] uses two shifted grids in a
"face-centered" fashion.  It would be interesting to try the same
thing for squares.

I would phrase your new constraint as follows:
Given a grid configuration, consider the equivalence relation "x~y iff
the L^1 distance from x to y is even".  There are at most two
equivalence classes for this relation, say A of cardinality k in [1,n]
and B of cardinality n-k.  Two points form the hypothenuse of a grid
isosceles right triangle only when their L^1-distance is even (since
they are two equal sides apart), so a hypothenuse cannot have a point
in A and one in B.  Therefore, the number of isosceles right triangles
formed by this configuration is at most k(k-1) + (n-k)(n-k-1), and
four times less for squares.

Benoît