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

Benoît Jubin benoit.jubin at gmail.com
Sun Oct 10 00:16:55 CEST 2021

Hi Robert,

That's an interesting idea, but I don't think it gives much: if you
dilate a grid configuration by a factor two, then x+y will always be
even.

Side note: what you write f(P)+f(Q) is, modulo 2, the L^1 distance
between P and Q, which is even when PQ is a hypothenuse, since P and Q
are two equal sides apart (as noted in the OEIS entry).

Benoît

On Sat, Oct 9, 2021 at 8:57 PM Robert Gerbicz <robert.gerbicz at gmail.com> wrote:
>
> 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/