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

[Benoît Jubin]

Erratum: read
----------
n = 4--11
435
0016
0027
----------

On Tue, Oct 5, 2021 at 1:09 AM Benoît Jubin <benoit.jubin at gmail.com> wrote:
>
> Hi all,
>
> Here is an attempt at summarizing what has been found so far on
> oeis.org/A051602.  Please tell me if I forgot something or if I
> misattributed some results or forgot to credit or mention you (knowing
> that the simpler or more trivial remarks and results can be left
> unattributed and considered folklore).  Since this will serve as a
> draft to my edit, please also tell me if I'm going against some OEIS
> conventions, in particular notational conventions.
>
> Sascha: what are you run-times ? How far can you compute these
> configurations ? Can you compute one around n = 140 ? This could
> probably tell circles and octagons appart (my bet is now on circles).
>
> Peter: I reworded your proof.  Your and my wordings may appeal to
> people with different backgrounds.  Should I copy yours in a txt file
> to be joined to the sequence ?  Or do you prefer the other way around
> ?
>
> Thanks,
> Benoît
> ________________________________________________________________________________
> New values
> a(0) = 0 (Neil: I'm sure you saw that coming!)
> ____________________
> General comments
> This sequence, a, enumerates squares whose vertices are grid points
> (points in G := ZZ x ZZ).  The similar sequence where vertices are not
> required to be on the grid is denoted by b.  One has a(n) <= b(n) and
> we do not know whether a = b.  If and when we find a value n such that
> a(n) < b(n), an OEIS entry will be added for b.  Given that a square
> with two vertices in G has its other two vertices either in G or in G
> + (1/2, 1/2), so that dilating the configuration yields a
> "grid-configuration", it is likely that a = b.
>
> The general problem of estimating the maximal number of similar
> figures within point-configurations was initiated in [Elekes--Erdos]
> and references can be found in [Matousek, p. 47] and [AFKK].  Note
> that the present problem concerning squares shares several properties
> with the case of right isosceles triangles treated in [AFR].
> ____________________
> Exact values
> Values for n <= 9 are exact and are the same for a and b (see proofs
> below by Hugo van der Sanden and Benoît Jubin for n<=7 and Sascha Kurz
> for n<= 9, which furthermore classify all optimal configurations for
> these values).
> Values for n > 9 are conjectural since they were obtained by
> exhaustive search for grid points within a square of side
> ceil(sqrt(n)), which is a reasonable assumption.  A proof that optimal
> configurations (with least side length equal to 1) have a diameter at
> most f(n) with f of reasonable growth would permit exact computation
> of values from exhaustive searches.
> ____________________
> Lower bounds
> Computer searches, using glutton algorithms starting with all grid
> points in a convex polygon and adding successive points, have given
> the following current record configurations, which thus yield lower
> bounds for a(n).  They are due mainly for n <= 36 to Sean A. Irvine
> and for 37 <= n <= 50 to Sascha Kurz, with preliminary work by Hugo
> van der Sanden.
> The representations below are given for ranges of n, and the integers
> indicate at what stage a given node is added (the letters A--Z encode
> the integers 10--36).  For instance, the first representation encodes
> the sequence of configurations
>                   X
> XX ; XXX ; XXX ; XXX ; etc.
> XX ; XX  ; XXX ; XXX
> ----------
> n = 4--11
> 435
> 00016
> 00027
> ----------
> n = 12--19
>   7
> 4003
> 00005
> 00006
> 1002
> ----------
> n = 20--36
>  GA78B
>  93100C
> E500000
> F400000
>  600000
>  D2000
> ----------
> n = 37--47
>  60007
> 5000008
> 0000000
> 00000009
> 0000000A
> 4000003
>  20001
> ----------
> n = 48--50
>   0000
>  000000
> 20000000
> 00000000
> 00000000
>  0000000
>  000000
>    001
> ----------
> In particular, a(37)>=117, a(48)>=198, a(49)>=207, a(50)>=216.
> ____________________
> Asymptotic behavior
> One has a(n), b(n) = Theta(n^2):
> Upper bound:  since squares are determined by two vertices, one has
> b(n) = O(n^2).  More explicitly: a pair of points uniquely determines
> the square who has it as diagonal, and a square has two diagonals, so
> b(n) <= n(n-1)/4 ~ n^2/4.
> Lower bound:  we give two proofs:
> First proof:  When n = m^2, the set of all grid points in [0, m-1]^2
> yields S = n(n-1)/12 squares.  Indeed, for a in [0, m-1] and b in [1,
> m], the square formed on (a,0) and (0,b) (as its "lower-left side")
> has other vertices (a+b,b) and (a,a+b), so there are (m-(a+b))^2
> translates of that square.  Therefore, S = sum_{a=0}^{m-1} sum_{b=1}^m
> (m-(a+b))^2.  By change of summation indices ((a,c):=(a,a+b)),
> expanding, using the sum of the first m integers, squares, cubes, and
> refactoring, one obtains S = n(n-1)/12. Since a is non-decreasing, one
> has a(n) >= (n-1)(n-2)/12 ~ n^2/12.
> Second proof (due to Peter Munn):  For r >= 0, denote by D(r) the disc
> centered at the origin with radius r.  If A is a point on the boundary
> of D(r), then the set of points B such that the square with diagonal
> AB is included in D(r) is a lense-shaped region of area (pi-2)r^2 (as
> a proportion of the disc area, this is twice A258146).  Therefore, the
> number S of grid-squares included in D(R) can be estimated as follows:
> since the set of squares with at least two vertices equidistant from
> the origin is negligible, we can assume that evey square has a unique
> vertex furthest from the origin, say at distance r, which corresponds
> to the A above.  Then, the opposite vertex B is in the region computed
> above, and the L^1 distance between A and B is even, so we have to
> divide that area by 2.  There are approximately 2*pi*r grid points at
> distance approximately r from the origin, so at first order, S \simeq
> int_0^R pi r (pi-2)r^2 dr = pi(pi-2)/4 R^4.  Since the disc D(R)
> contains approximately pi R^2 points, one obtains S \simeq (1-2/pi)/4
> n^2.  Therefore, a(n) >~ (1-2/pi)/4 n^2.
> That second proof actually gives liminf a(n)/n^2 >= (1-2/pi)/4.
> ______________________________________
> EXTENSIONS
> Revised following a rich discussion on the seqfan mailing list, with
> contributions by the persons cited in the text, Allan Wechsler, Alex
> Meiburg, and Benoît Jubin, Oct 5 2021.
>
> ________________________________________________________________________________
> LINKS/REFERENCES
> Elekes, Erdos, Similar configurations and pseudo grids
> Matousek, Lectures on Discrete Geometry
> Bernardo M. Abrego, Silvia Fernandez-Merchant, David B. Roberts, On
> the maximum number of isosceles right triangles in a finite point set,
> https://arxiv.org/abs/1102.5347
> Bernardo M. Abrego, Silvia Fernandez-Merchant, Daniel J. Katz, Levon
> Kolesnikov, On The Number of Similar Instances of a Pattern in a
> Finite Set, https://arxiv.org/abs/1501.00076