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

[Robert Gerbicz]

That dilation doesn't help, because:
In this case q=(2*x,2*y) for all q points from the set then just contract
it to (x,y) and repeat it, this process is finite since
sum(abs(x)+abs(y): (x,y) is in the set)
[what is now really the point's L1 sum]
is a strictly decreasing (positive) function for n>1.
And with these operations the number of IRTs and squares remain the same.

You could ask what happens when f(p) is even for all points in the set,
then f(p)+f(q) is also even for every pair.
This game allows only EVEN and ODD points:
q=(x,y) is EVEN point if x and y is even,
q=(x,y) is ODD if x and y is odd.
The interesting, still easy fact that now an ODD and EVEN point couldn't
form a hypotenuse in an IRT, you would get a grid point, the problem is
that:
f(p1)=x0+y2 and f(p3)=x2+y0 and both of them is odd, and we allowed only
even f() values.

But you simply can't partition the points to EVEN and ODD points in the
induction for IRT counting, the trouble here is that it is possible that
p0,p2 is EVEN, but p1 is ODD, for example p0=(0,0); p2=(2,0) then p3=(1,1)
which is an ODD point.



Benoît Jubin <benoit.jubin at gmail.com> ezt írta (időpont: 2021. okt. 10., V,
0:17):

> 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>