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

[Kurz, Sascha]

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