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

[Robert Gerbicz]

An improvement in some cases.
If x+y is odd in the n point grid set for k times [where q=(x,y) is in the
set] then the maximal number of isosceles right triangle (IRT) is at most

T<=k*(k-1)+(n-k)*(n-k-1)

For a random point selection or your nice dense circle/close to octagon
methods etc. this means that k~n/2, giving that
T~n^2/2 and for our problem "only" n^2/8 squares (this is much better than
the known 2/3*n^2 and n^2/6 upper bounds). Notice that here the worst case,
giving the smallest bound is the k=n/2 !

This nice T bound follows from the fact that f(P)+f(Q) should be even for
any IRT if P and Q is the hypotenuse and f((x,y))=x+y.
In details:
If p0,p1,p2,p3 are the four points in counter-clockwise order forming 2 IRT,
where [p0,p2] is the hypotenuse. [in the count p0,p2 is the fixed set, and
we see if p1 or p3 is in the set or not].

Then we can easily get that p3=(p0+p2)/2+i*(p2-p0)/2 where p0=(x0,y0);
p2=(x2,y2)

p3=((x0+x2)+i*(y0+y2)+i*(x2-x0+i*(y2-y0)))/2=
=((x0+x2+y0-y2)/2,(x2-x0+y0+y2)/2)

Similarly p1=((x0+x2+y2-y0)/2,(x0-x2+y0+y2)/2)

you may not noticed so far that x0+x2+y0-y2 should be even in p3 [otherwise
it is not even a grid point!], what is the
same in parity as (x0+y0)+(x2+y2), you can say the same for p1.

Let us define f((x,y))=x+y for a given (x,y) point. So if P=p0 and Q=p2 is
the two point set, then for an IRT we need that
f(P)+f(Q) should be even or in other words f(P) and f(Q) has the same
parity, giving at most:

T<=2*(binomial(k,2)+binomial(n-k,2))=k*(k-1)+(n-k)*(n-k-1) IRTs. Completing
the proof.

ps.
Today I had also a wrong proof claiming that
A(n)<=(n-1)^2/2 for (every) IRT counting
hence a(n)<=(n-1)^2/8 for square counting
you could say that it would be an ultra sharp result for smallish n values,
but very likely it is true for larger n also.


Benoît Jubin <benoit.jubin at gmail.com> ezt írta (időpont: 2021. okt. 9.,
Szo, 13:02):

> Is there an OEIS entry for the related sequence restricted to
> axis-parallel squares ?  That sequence is Theta(n^(3/2)) (whereas
> A051602 is Theta(n^2)), and it seems likely that an asymptotically
> optimal configuration is the full grid [1, \sqrt(n)]^2.  Computations
> are easier, and a proof that for most values of n, there exist optimal
> n-configurations which are grid configurations may be easier in that
> case.  A starting article, which gives algorithms to compute the
> sequence, is
>
> Kreveld, van, M. J., & Berg, de, M. T. (1989). Finding squares and
> rectangles in sets of points. (UniversiteitUtrecht. UU-CS, Department
> of Computer Science; Vol. 8910). Utrecht University.
> https://pure.tue.nl/ws/portalfiles/portal/4288742/369233.pdf
>
> Any volunteer to compute values and add that entry ?
>
> Benoît
>
> On Fri, Oct 8, 2021 at 2:05 PM Benoît Jubin <benoit.jubin at gmail.com>
> wrote:
> >
> > 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>