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

[Benoît Jubin]

Hi Sascha,
Unless I misunderstood (and it's quite easy to misunderstand your
style), this is no proof.  For instance, where are you using that the
configuration is optimal ?

I tried a bit to prove that a = b but found flaws in all my attempts.
This looks like a hard result, and one has to consider the whole
configuration: local arguments cannot suffice.

Benoît

On Fri, Oct 8, 2021 at 11:55 AM Kurz, Sascha
<Sascha.Kurz at uni-bayreuth.de> wrote:
>
> Earlier Hugo wrote
> : Are we ready to conjecture that all maximal arrangements can be
> : generated by such [2-] extensions?  If we are, it's worth noting that this
> : also trivially implies a(n) = b(n).
>
>
> I would bet on this conjecture too.  However, a(n)=b(n), i.e. assuming
>
> that  all points are located on the integer grid, can be shown more directly.
>
> To this end let the n points be represented by real-valued coordinates
>
> (x_i,y_i) that we consider as variables. Each square j can be represented by
>
> two additional real-value variables (u_j,v_j) and generates 6 linear equations.
>
> To ease the notation, assume that the clockwise ordering of the vertices of the
>
> square is (x_1,y_1), (x_2,y_2), (x_3,y_3), (x_4,y_4). With this, the equations
>
> given by the square are
>
> x_2 = x_1 + u_j
>
> y_2 = y_1 + v_j
>
> x_3 = x_2 + v_j
>
> y_3 = y_2 - u_j
>
> x_4 = x_3 - u_j
>
> y_4 = y_3 + v_j
> (The intuition is to consider (u_j,v_j) as the vector from (x_1,y_1) to (x_2,y_2) and
> to consider its perpendicular versions, pointing into the chosen orientation).
>
> Starting from an arbitrary point set this equation system has a solution, that may
> contain irrational components, so that the solution space is a non-empty affine space.
> By small perturbation of the entire space we can assume that it contains a rational point,
> which then gives rational values for all variables (since the coefficients of the equations are
> all rational). The only technical issue are degenerations in terms of coinciding points or square
> sides of length zero (u_j^2+v_j^2=0), which is a special case of the former.
> Starting from an existing point set initially, no such degenerations occur. Choosing the
> perturbation sufficiently small, none will occur. Finally, by scaling, we reach a representation
> on the integer grid.
>
> So, in principal, we can check each hypothetical combinatorial description of the incidences between
> (oriented) squares and points whether it can be realized in the Euclidean plane. (Degenerations
> that cannot be resolved by small pertubations can be characterized easily.) We may also formulate
> an 3-extension step (if we deal with solution spaces of linear equation systems instead of exact coordinates)
> and perform an exhaustive search for the optimal configurations.
>
> The above equations smell a bit like a 2-dimensional sumset probem. Any experts on the list?
>
> Best regards,
> Sascha
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/